Как написать интерпретатор Lisp на Python за несколько сотен строк

В статье разобрана полная архитектура интерпретатора: сначала строка кода преобразуется в токены, потом в абстрактное синтаксическое дерево (AST), затем вычисляется в окружении переменных. На практике это всего несколько сотен строк Python. Показаны основные концепции: как парсить скобки Lisp, как устроена таблица символов (окружение), как работают замыкания и локальные переменные через вложенные окружения.

Примеры начинаются с простого калькулятора (define r 10; * pi r r), затем добавляются условные операторы (if), функции (lambda), и управление областью видимости. Каждая новая возможность объясняется через код, который легко скопировать и запустить. Финальный интерпретатор поддерживает всё необходимое для интерактивного REPL (read-eval-print loop).

Ключевые факты

Интерпретатор состоит из 4 этапов: tokenize (разбор на токены), parse (парсинг в AST), eval (вычисление), repl (интерактивная оболочка).
Lisp синтаксис минималист: скобки для списков, символы для переменных, числа для значений. Нет инфиксных операторов, всё префиксное (+ 1 2 вместо 1 + 2).
Окружение (Environment), это словарь {переменная: значение}. Вложенные окружения позволяют локальным переменным скрывать глобальные через цепочку поиска (outer environment).
Замыкание (Closure), функция, которая помнит окружение, в котором она была определена. Это реализуется классом Procedure с тремя полями: параметры, тело и окружение.
lambda создает процедуру, define добавляет её в текущее окружение, set! изменяет существующую переменную, if выбирает ветку. Всё это логически просто, но мощно.

Ред. Целый язык программирования укладывается в пару сотен строк и четыре функции. Интерпретатор, который кажется чёрной магией, оказывается коротким скриптом, который можно прочитать за обед.

Почему это важно

Это фундаментальное знание для понимания, как работают языки программирования. Steve Yegge сказал: «Если вы не знаете, как работают компиляторы, вы не знаете, как работают компьютеры». Статья показывает, что интерпретатор, не черная магия, а вполне реализуемая программа. Понимание этих концепций помогает отлаживать код, писать DSL (предметно-ориентированные языки), разбираться в устройстве Python, JavaScript и других интерпретируемых языков.

Ред. Главный эффект статьи демистификация: после неё «как работает Python» перестаёт быть тайной за семью печатями. Цитата Йегга про компиляторы тут работает как лёгкий укор всем, кто пишет на интерпретируемых языках и не заглядывал внутрь.

Кому это важно

Студентам и начинающим разработчикам, изучающим теорию языков программирования. Специалистам по компиляторам, которые хотят быстро прототипировать идею. Людям, интересующимся функциональным программированием и Lisp-подобными языками. Разработчикам, которые пишут конфигурационные языки или DSL для своих систем. Любым программистам, которые хотят лучше понять, что происходит под капотом.

Ред. Студентам, любителям Lisp и всем, кто собирается лепить свой DSL. Последним особенно: проще адаптировать готовый eval, чем заново выяснять, что замыкание это всего лишь функция со ссылкой на своё окружение.

Как это применить

Прочитайте статью и скопируйте код интерпретатора (примерно 100-150 строк базовой версии). Запустите его в Python интерпретаторе. Напишите простые программы: определите переменные, создайте функции, используйте if и lambda. Модифицируйте интерпретатор: добавьте новые встроенные функции, расширьте синтаксис. Если изучаете компиляторы, используйте эту базу как отправную точку для своего языка. Для DSL просто адаптируйте eval для вашего синтаксиса вместо Lisp.

Ред. Скопировать 150 строк и запустить это пять минут. Дальше начинается настоящее обучение: добавить свои функции, расширить синтаксис, и внезапно понять, на чём именно держится магия скобок.

Можно ли доверять

Питер Норвиг, директор Google Research, автор классического учебника по ИИ. Статья написана в 2010 году и с тех пор десятки тысяч людей использовали её для обучения. Код работает и проверен. Однако это упрощённая версия Scheme, а не полный язык. На практике реальные интерпретаторы включают оптимизацию, обработку ошибок, и гораздо больше встроенных функций.

Ред. Норвиг и пятнадцать лет читателей это солидный аргумент. Только не забывайте приставку «упрощённый Scheme»: в проде интерпретаторы на 90% состоят из обработки ошибок и оптимизаций, которых тут нет принципиально.

Риски и подводные камни

Код в статье работает на Python 2.x, поэтому некоторые функции (raw_input, print как функция) требуют адаптации для Python 3. Интерпретатор без оптимизации медленен на больших программах. Обработка ошибок минимальна, SyntaxError при неправильных вводе. Нет хвостовой рекурсии оптимизации, поэтому глубокая рекурсия приведет к переполнению стека. Не используйте этот интерпретатор в production, это только образовательный пример.

Ред. Код из 2010 года всё ещё на Python 2, так что начнётся знакомство с правкой raw_input и print. А отсутствие оптимизации хвостовой рекурсии означает, что красивый функциональный пример уронит стек на первой же серьёзной рекурсии.

«If you don't know how compilers work, then you don't know how computers work.»

— Steve Yegge, цитируемый Peter Norvig