Идея о том, что язык программирования может реализовать сам себя, удивительна. Она вызывает сильное любопытство: «Как это вообще может выглядеть?» С момента своего появления в начале 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
Закрыв глаза на несколько рекурсивных примитивов и воспользовавшись небольшой помощью 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.
В начале 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.