Написание интерпретатора

Написать интерпретатор нового языка с нуля - это несколько сотен строк кода. Thorsten Ball написал книгу об этом за один уикенд. Ruby был интерпретатором на C в 1996 и был медленным - но это не помешало ему изменить веб-разработку через Rails. Интерпретатор - это кратчайший путь от идеи языка до работающего прототипа, и понять как он устроен значит понять как работают Python, Ruby, Lua изнутри.

• **Lua в Nginx (OpenResty)**: tree-walking интерпретатор Lua 5.1 обрабатывает 100k+ req/s для конфигурационной логики - скорость интерпретатора не bottleneck при правильной архитектуре
• **Rhai (Rust скриптовый язык)**: встраиваемый интерпретатор для игровых движков и конфигурации; tree-walking с ~80 наносекунд на простую операцию - достаточно для game scripting
• **Python CPython eval loop**: `ceval.c` - центральный dispatch loop CPython; каждый Python байткод - case в switch. Понимание этого кода открывает все тайны CPython performance

Tree-Walking Interpreter

Tree-walking interpreter рекурсивно обходит AST и вычисляет значения узлов на ходу. Простейший дизайн: функция `eval(node, env)` принимает AST-узел и окружение (переменные), возвращает значение. Это подход Ruby MRI до 1.9, Python CPython (частично), Lua 5.1 reference interpreter. Преимущество - простота; недостаток - медленнее байткод-интерпретатора в 3-10x.

Книга 'Writing An Interpreter In Go' (Thorsten Ball, 2016) - популярный туториал по tree-walking interpreters. Monkey language из книги реализован в Go за ~2000 строк. Ruby MRI до версии 1.8 использовал tree-walking подход; в 1.9 YARV (Yet Another Ruby VM) заменил его байткод-интерпретатором с 3x ускорением.

Environment Chains

Environment (окружение) - структура данных хранящая привязки имён к значениям. Chain environments: каждый вложенный scope создаёт новый environment с указателем на родительский. Поиск переменной: проверить текущий -> parent -> parent -> global. Это реализация lexical scoping.

Scheme, Python, JavaScript, Lua - все используют lexical scoping через environment chains. Dynamic scoping (Emacs Lisp до lexical-binding, bash) - переменная ищется в call stack, не в lexical scope. Первый - предсказуемее для программиста; второй - проще реализовать без closures. Python оптимизирует это: локальные переменные функций хранятся в массиве, а не в словаре.

Closures

Closure - функция вместе с captured environment: ссылка на окружение в котором функция была определена. При вызове closure исполняется в своём captured environment, а не в текущем. Это позволяет функциям 'запоминать' переменные из enclosing scope даже после того как enclosing функция завершилась.

V8 closure optimization: если переменная из enclosing scope не изменяется - она копируется в closure (flat closure), иначе - shared heap cell. Python closures используют 'cell objects' для mutable captured variables. Rust closures выбирают capture mode: `Fn` (shared ref), `FnMut` (exclusive ref), `FnOnce` (move) - компилятор выводит автоматически.

Error Handling в интерпретаторе

Runtime errors в интерпретаторе: undeclared variable, type mismatch, stack overflow (бесконечная рекурсия), division by zero. Два подхода: exceptions (бросать ошибку и раскручивать стек) или Result type (возвращать Either<Value, Error>). Хорошая диагностика требует location info: строка и столбец источника каждого AST-узла.

Dart использует 'zones' для structured error handling в async интерпретаторе. Lua implementации (LuaJIT, PUC-Lua) используют setjmp/longjmp для error propagation без C++ exceptions. Python Traceback объект строится инкрементально при раскрутке стека. Rust-based интерпретаторы (например, Rhai скриптовый язык) используют Result<Value, EvalAltResult> без исключений.

Итоги

• Tree-walking interpreter: `eval(node, env)` рекурсивно обходит AST; проще байткод-VM, медленнее в 3-10x из-за pointer chasing
• Environment chain реализует lexical scoping: каждый scope = новый env с parent; lookup идёт вверх по цепочке
• Closure = function + capturedEnv (ссылка, не копия); location info в каждом AST узле критична для понятных runtime errors

Связанные темы

Интерпретатор - практическое применение всех компиляторных концепций:

• Написание компилятора — Компилятор добавляет к интерпретатору этап кодогенерации вместо прямого вычисления AST
• JIT-компиляция основы — JIT - это интерпретатор который компилирует горячий код: сначала tree-walking, потом нативный
• DSL компиляторы — Многие DSL реализуются как простые интерпретаторы поверх AST основного языка

Вопросы для размышления

• Python CPython использует байткод-VM вместо tree-walking. Какие конкретно операции ускоряются больше всего при переходе к байткод-интерпретатору?
• Closure захватывает ссылку на environment. Что происходит с памятью когда closure живёт дольше создавшей её функции? Как это влияет на GC?
• Tail call optimization (TCO) позволяет бесконечную рекурсию без переполнения стека. Как реализовать TCO в tree-walking интерпретаторе?

Связанные уроки

• fl-01-intro