Питер Норвиг написал классический туториал по созданию интерпретатора для диалекта Scheme (Lisp), используя Python 3. Свою реализацию он назвал Lispy (lis.py). Норвиг хочет показать так называемые «уравнения Максвелла для софта» — минималистичную, но полную систему.
Синтаксис Scheme радикально отличается от Java или Python. В Java куча синтаксических конструкций: операторы, скобки разных видов, точки с запятой. В Scheme есть только выражения. Числа и символы — атомы. Всё остальное — список в скобках. Первый элемент списка определяет его смысл: ключевое слово (if, define) или вызов процедуры. Весь язык укладывается в 5 ключевых слов и 8 синтаксических форм. Для сравнения: в Python 33 ключевых слова и 110 форм, в Java — 50 и 133.
Интерпретатор состоит из двух частей. Парсинг (функция parse) разбивает строку на токены с помощью tokenize, а затем читатель read_from_tokens собирает из них абстрактное синтаксическое дерево. Пробелы и скобки обрабатываются примитивно — через замену и str.split. Числа распознаются как int или float, всё остальное — символ.
Выполнение (eval) обходит это дерево. Переменные ищутся в окружении (Env) — словаре, который хранит имена и их значения. Для чисел eval возвращает само число. Для list-выражений проверяется первый элемент. Если это if — вычисляется условие, и выбирается соответствующая ветка. Если define — в окружение добавляется новая переменная. Всё остальное трактуется как вызов процедуры: вычисляется процедура и аргументы, затем процедура применяется к аргументам. Стандартное окружение содержит все математические функции из модуля math Python и базовые операции вроде car, cdr, cons.
Для полной версии Scheme Норвиг добавляет lambda, set! и quote. Чтобы поддерживать локальные переменные и замыкания, Env переделывается в класс, который хранит ссылку на внешнее окружение. Поиск переменной идёт от внутреннего уровня к внешнему (лексическая область видимости). Процедура (класс Procedure) запоминает список параметров, тело и окружение, в котором была создана. При вызове создаётся новое окружение с аргументами, и тело вычисляется в нём.
В итоге Lispy умеет рекурсию, замыкания, функции высшего порядка. Например, (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) вычисляет факториал. Или (define make-account (lambda (balance) (lambda (amt) (begin (set! balance (+ balance amt)) balance)))) — создаёт банковский счёт с состоянием. Всё это работает в read-eval-print loop (REPL). Норвиг завершает рассказ историей про свою диссертацию 1984 года, где ему и коллеге понадобился интерпретатор для форматирования ссылок — и они оба написали такие интерпретаторы, но разными путями.