Простой интерпретатор Lisp на Umka
Разработка моего статически типизированного скриптового языка Umka вошла в ту стадию, когда потребовалась проверка языковых возможностей на более сложных примерах, чем скрипты в пару десятков строк. Для этого я решил реализовать на своём языке интерпретатор Lisp. На это меня вдохновил педагогический эксперимент Роба Пайка, одного из создателей языка Go. Недавно Пайк опубликовал маленький интерпретатор Lisp на Go. Особенно впечатлило замечание Пайка, что описание интерпретатора заключено на одной странице 13 древнего руководства по Lisp 1.5. Учитывая синтаксическое родство Umka и Go, было трудно не поддаться соблазну построить такой интерпретатор на Umka, но не буквальным переносом кода Пайка, а полностью заново, от основ. Надеюсь, знатоки Lisp и функциональных языков простят мне наивное изумление от соприкосновения с прекрасным.
На непосвящённых Lisp может произвести впечатление, близкое к шоку. Где граница между кодом и данными? Где циклы? Где стек? Единственной структурой данных является дерево. Оно же может представлять список. Оно же становится абстрактным синтаксическим деревом при разборе программы. Оно же заменяет собой стек при вычислении выражений. Любое дерево можно попытаться исполнить как код или использовать как данные. Вместо циклов — рекурсия. В ядре языка нет даже арифметики. И тем не менее, это полный по Тьюрингу язык, который можно бесконечно расширять и посыпать синтаксическим сахаром.
Определение минимального интерпретатора Lisp действительно занимает меньше страницы. Конечно, с некоторой натяжкой: в нём используются функции, определённые на нескольких предыдущих страницах. Кажется, создатель Lisp Джон Маккарти из азарта старался превзойти сам себя в лаконизме и в итоге опубликовал микроруководство по Lisp, содержащее определение языка вместе с исходником интерпретатора — в общей сложности две журнальные страницы. Правда, добавил в заголовок:»Not the whole truth».
Ядро языка (здесь мы говорим о самых старых и простых диалектах) требует наличия пяти элементарных функций, четырёх ключевых слов и двух констант, которые не могут быть выражены средствами самого языка.
Базовые конструкции языка для тех, кто с ними не знаком
(car x)— выделение головы спискаx(cdr x)— выделение хвоста спискаx(cons x y)— соединение списковxиy(atom x)— проверкаxна атомарность(eq x y)— проверка атомарных элементовxиyна равенство(cond (a x) (b y))— выбор значенияxилиyпо условиюaилиb(quote x)— указание использоватьxкак есть, без вычисления((lambda (x) a) y)— вызов безымянной функции с теломa, формальным параметромxи фактическим параметромy((label ff (lambda (x) a)) y)— присвоение безымянной функции имениfft— истинаnil— ложь или пустое выражение
С помощью этих конструкций можно определять и вызывать рекурсивные функции, так что в одном выражении будет заключена целая программа. Если к этому добавить ещё и арифметические функции, то можно, например, рассчитать факториал 6:
((label fac (lambda (n) (cond ((eq n 0) 1) ((quote t) (mul n (fac (sub n 1))))))) 6)
В микроруководстве Маккарти этими средствами выражен весь интерпретатор Lisp, за исключением лексического и синтаксического разбора. В руководстве Lisp 1.5 на той самой странице 13 приведён почти такой же интерпретатор, но в более человекочитаемом псевдокоде. Его я и взял за основу своего маленького проекта. Потребовалось лишь добавить разбор текста программы, некое подобие REPL и импровизированную арифметику. Роб Пайк, видимо, поступил так же, но отказался от конструкции label в пользу defn, которая позволила ему не определять функцию заново всякий раз, когда требуется её вызвать. В ядре Lisp такой возможности не предусмотрено.
Поскольку весь интерпретатор пронизан рекурсией и обработкой деревьев, он послужил отличным тестом многих возможностей языка Umka — от формирования стековых кадров до сборки мусора. Думаю, Umka хорошо справился с испытанием. Исправлять пришлось лишь два-три мелких бага, связанных с экспортом имён и опережающим описанием типов. Весь код интерпретатора занял меньше 400 строк.
Желающим поиграть с моим интерпретатором и передать по эстафете вдохновение от Роба Пайка рекомендую взять папку с примерами из ветки master, а не из последнего выпуска.
