Как написать интерпретатор 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 и других интерпретируемых языков.
Кому это важно
Студентам и начинающим разработчикам, изучающим теорию языков программирования. Специалистам по компиляторам, которые хотят быстро прототипировать идею. Людям, интересующимся функциональным программированием и Lisp-подобными языками. Разработчикам, которые пишут конфигурационные языки или DSL для своих систем. Любым программистам, которые хотят лучше понять, что происходит под капотом.
Как это применить
Прочитайте статью и скопируйте код интерпретатора (примерно 100-150 строк базовой версии). Запустите его в Python интерпретаторе. Напишите простые программы: определите переменные, создайте функции, используйте if и lambda. Модифицируйте интерпретатор: добавьте новые встроенные функции, расширьте синтаксис. Если изучаете компиляторы, используйте эту базу как отправную точку для своего языка. Для DSL просто адаптируйте eval для вашего синтаксиса вместо Lisp.
Можно ли доверять
Питер Норвиг, директор Google Research, автор классического учебника по ИИ. Статья написана в 2010 году и с тех пор десятки тысяч людей использовали её для обучения. Код работает и проверен. Однако это упрощённая версия Scheme, а не полный язык. На практике реальные интерпретаторы включают оптимизацию, обработку ошибок, и гораздо больше встроенных функций.
Риски и подводные камни
Код в статье работает на Python 2.x, поэтому некоторые функции (raw_input, print как функция) требуют адаптации для Python 3. Интерпретатор без оптимизации медленен на больших программах. Обработка ошибок минимальна, SyntaxError при неправильных вводе. Нет хвостовой рекурсии оптимизации, поэтому глубокая рекурсия приведет к переполнению стека. Не используйте этот интерпретатор в production, это только образовательный пример.
«If you don't know how compilers work, then you don't know how computers work.»
— Steve Yegge, цитируемый Peter Norvig