Идея о том, что язык программирования может реализовать сам себя, удивительна. Она вызывает сильное любопытство: «Как это вообще может выглядеть?» С момента своего появления в начале 60-х это мог делать Lisp.

В начале 60-х Джон Маккарти придумал серию примечательных идей, хорошо сочетающихся друг с другом и актуальных даже спустя десятки лет. Сначала он сформулировал их в статье о Lisp, а чуть позже — в руководстве по Lisp 1.5.


Джон Маккарти

Одной из таких идей стала гомоиконичность — поведение, при котором код и данные взаимозаменяемы. Обычно мы воспринимаем код как последовательность команд, оперирующих с данными. Такое понимание формирует наш взгляд на большинство современных языков программирования. Однако Lisp нарушает этот принцип, обращаясь с кодом и с данными одинаково — это называют его гомоиконичной природой. Эта уникальная характеристика, по сути, размывает границы между оператором (кодом) и операндом (данными).

Такая унификация кода и данных глубоко укоренилась в Lisp, она обеспечивает уровень выразительности, позволяющий языку естественным образом быть выраженным в самом себе.


Lisp на Lisp

Эта крошечная карточка — весь язык программирования Lisp! Язык программирования, написанный на нём самом. Есть знаменитая цитата Алана Кэя об этой части истории кодинга: «для меня стало большим откровением… когда я наконец понял, что половина страницы кода внизу страницы 13 руководства по Lisp 1.5 была Lisp в самом себе. Это были „максвелловские уравнения в разработке ПО“! Это был целый мир программирования в нескольких строках, которые можно закрыть ладонью».

Так что за магию увидел Кэй в этом произведении, заставившую его назвать его «максвелловскими уравнениями в разработке ПО»? Как весь мир программирования уместился всего в нескольких строках кода?

Ответить на этот вопрос можно одним интересным способом — применив принцип "чтобы что-то понять, нужно это закодировать".

А чтобы обеспечить интересность и свежесть реализации в духе исходного Lisp, я решил выбрать в качестве инструмента Python. Большинство программистов незнакомо с синтаксисом Lisp (слишком много скобок), но, вероятно, достаточно хорошо знают синтаксис Python. Я хочу переписать «Lisp на Lisp» на Python и попытаться максимально сохранить дух старого кода.

Странно, но знакомо

Изначально Lisp гениальным образом сочетал в себе два синтаксических стиля. Стиль кода под названием M-expression (сокращение от meta) и стиль данных под названием S-expression (сокращение от symbolic). Они семантически эквивалентны.


M-expression с эквивалентными им S-expression

Представленный выше код «Lisp на Lisp» написан как M-expression (в стиле кода) и реализует Lisp в S-expression (стиль данных).

Чтобы пойти дальше, мы можем выполнить небольшой трюк — транслировать M-expression Lisp в конструкции кода на Python, например, в вызовы функций и в условные операторы. Кроме того, мы можем представить S-expression Lisp при помощи списков Python. Lisp — это сокращение от List Processing («Обработка списков»), потому что в нём используется только одна структура данных: список. Так что совершенно логично использовать списки Python для симуляции S-expression Lisp. Ниже показан наш мини-словарь, который будет работать в качестве розеттского камня:


Это четыре способа выразить одно и то же. Они семантически эквивалентны.

Дополнительное преимущество такого способа отображения заключается в том, что теряется необходимость реализации парсера для нашего языка. Это упрощает кодовую базу и позволяет нам придерживаться истинного духа Lisp, не отвлекаясь на манипуляции со строками.

Первая итерация

Разобравшись с контекстом и мотивацией, можно перейти к самой реализации. Lisp требует реализации множества базовых функций за пределами его контекста, в основном это базовые строительные блоки для списков.


Примитивы списков Python, чтобы они работали как Lisp

• Эквивалентность
  • atom(x): является ли x списком?
  • eq(x,y): x равно y?
• Отсечение
  • car(x): первый элемент списка
  • cdr(x): остальная часть списка
• Слияние
  • cons(x,y): добавить атом к списку
  • append(x,y): объединить два списка

Закрыв глаза на несколько рекурсивных примитивов и воспользовавшись небольшой помощью Llama3-70b (на Groq), мы можем получить работающий интерпретатор подмножества кода «Lisp на Lisp»:


Работающая версия M-expression «Lisp на Lisp», транслированная на Python

Вот несколько примеров, с которыми вы можете поэкспериментировать:


Списки Python, используемые в качестве S-expression

Полный код выложен в github gist

Вторая итерация

Наша первая итерация почти закончена, но не хватает одного критически важного элемента: лямбд. Лямбды — это анонимные функции, служащие основным способом определения и вызова функций в Lisp. Без лямбд в Lisp мы не могли бы реализовать рекурсию, а без рекурсии наш Lisp не будет полным по Тьюрингу (это минимальный порог вычисления всего, что можно вычислить).

Чтобы добавить лямбды, нам нужно добавить пару функций, которые мы ранее игнорировали, и в частности два примитива: assoc(x,y) и pairlis(x,y). assoc(x,y) — это поиск в стиле словаря ключей и значений, но реализованный при помощи списков (ассоциативных списков). parlis — это просто zip(x,y) из Python (архивация двух списков вместе).


pairlis и assoc в том виде, в котором они появились в руководстве Lisp 1.5

Литеральная трансляция на Python будет выглядеть так:


Литеральная (рекурсивная) трансляция с Lisp на Python assoc и pairlis

Самому Lisp приходилось пользоваться рекурсией (функцией, вызывающей саму себя) даже для простых, линейных сканирований, потому что в нём нет циклов. Однако assoc и pairlis можно изящно транслировать на Python с помощью списковых включений:


Python поддерживает и списки, и рекурсию; если вы ещё не заметили, я на самом деле немного сжульничал с COND, потому что в Lisp был evcon, который тоже транслируется в цикл. Тот же самый трюк можно повторить с evlis для LAMBDA.


evcon и evlis — ещё одни примеры циклов в коде «Lisp на Lisp»

И мы уже почти закончили! Осталось последнее. В Lisp функция eval получает два аргумента. Первый — это, разумеется, выражение (s-exp). Второй — это окружение, то есть ещё один список (ключей/значений). Окружение поддерживает связывание переменных для LAMBDA case, отображая имена переменных на соответствующие им значения.

Например, когда мы определяем функцию с переменной x, а затем подставляем вместо этой функции данные, то данные связываются (при помощи pairlis) с символом x, а затем сохраняются/добавляются в список окружения. Когда необходима x, выполняется её поиск (при помощи assoc) и она снова подставляется в выражение. Конкретная методика этого связывания называется dynamic scoping (использованием динамических областей видимости переменных).

Вот полный код «Lisp на Lisp» на Python:



А вот и лямбды, наконец!

Полный код выложен в github gist.