Анатомия интерпретатора SOOT: три инженерных решения

Оглавление

• Введение
• Откуда взялся интерпретатор
• Как не потерять исходный код по дороге к выполнению
• Декларативная проверка аргументов
• Обработка ошибок: от сообщения к управлению выполнением
• Как эти решения дополняют друг друга
• Заключение

Введение

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

В этой статье рассмотрены три решения из интерпретатора SOOT:

• хранение информации об исходном коде отдельно от самих S-выражений, но с возможностью связать их друг с другом (TextDb);
• декларативное описание контракта аргументов встроенных функций (vararg_check);
• обработка ошибок с накоплением трассировки и пользовательскими обработчиками, написанными на самом языке.

Их объединяет одно: каждое избавляет от того, чтобы повторять сложную инфраструктурную логику во множестве мест программы.

Откуда взялся интерпретатор

Интерпретатор SOOT вырос из интерпретатора GOOS, скриптового Lisp проекта OpenGOAL, который распространяется как открытый проект. Идеи TextDb и vararg_check, а также часть устройства вычислителя восходят к нему. В статье описано, как эти механизмы работают в SOOT, включая то, что в них изменено. Названия проектов принадлежат их правообладателям, и SOOT с ними не связан.

Как не потерять исходный код по дороге к выполнению

Выражение — ещё не вся информация о программе

Пусть пользователь написал:

(+ 10 (* 2 3))

Reader, компонент, который читает текст и распознаёт выражения, превращает эту запись в дерево S-выражений: символы, числа и списки. Для вычисления исходный текст после этого почти не нужен. Интерпретатору достаточно знать, что надо вызвать + с числом 10 и результатом (* 2 3).

Но что будет, если пользователь напишет (+ 10 (* 2 "abc"))? Сообщить, что операция не удалась, мало. Нужно показать, где именно в исходном тексте возникла проблема, иначе поиск ошибки в большом файле превращается в мучение.

Проблема в том, что после чтения интерпретатор работает уже с объектами языка. Как связать эти объекты с местами текста, из которых они появились?

Два способа хранить позиции

Первый способ: класть информацию об исходнике прямо в узлы дерева. Каждый узел носит с собой файл, строку и позицию. Это разумно, но связывает представление выражения с диагностикой: данные нужно аккуратно протаскивать через все уровни представления.

Второй способ, который используется в SOOT: отдельное хранилище TextDb. Оно сопоставляет объекты языка с информацией об их происхождении, а сами объекты ничего о ней не знают. Ключом служит идентичность объекта.

Схема такая:

Исходный текст
      |
      v
    Reader ------- link(пара, источник, смещение) -------+
      |                                                  |
      v                                                  v
S-выражения                                           TextDb
      |                                                  |
      v                                                  |
 Вычисление                                              |
      |                                                  |
      v                                                  |
Ошибка в форме F  ---- get_info_for(F) ------------------+
                                  |
                                  v
                    файл, строка, текст строки и указатель ^

TextDb не участвует в вычислении. Его единственная задача — по объекту ответить на вопрос «откуда он взялся».

Как устроено хранилище

Внутри TextDb лежат две структуры:

• список источников текста (SourceText): файл, строка программы или ввод в REPL;
• таблица, сопоставляющая объект кучи с записью TextRef. Запись состоит из ссылки на источник и смещения в нём.

Когда Reader создаёт очередную пару, он сразу вызывает link(пара, источник, смещение). В SourceText заранее построена таблица смещений начала строк, поэтому по смещению легко найти номер строки, её текст и колонку.

Из таблицы позиций собираются два вида отчётов. Подробный, get_info_for, печатает файл и номер строки, саму строку и красную стрелку ^ под нужным символом. Краткий, get_short_info_for, возвращает структуру ShortInfo (файл, строка, колонка, текст строки), удобную для редакторов и REPL. Если смещение выходит за границы текста, оно прижимается к его концу, чтобы диагностика не падала сама.

Позиции есть только у пар

Есть важная деталь. Ключом может быть только объект кучи, поэтому link принимает только пары. Числа, символы (symbol) и отдельные символьные литералы (char) хранятся прямо внутри Object, и собственной идентичности у них нет. Кроме того, символы интернированы: один и тот же символ встречается в десятках мест и не может иметь единственную позицию.

Практический вывод: ошибка указывает на форму, то есть на ячейку списка, в которой она возникла, а не на конкретное число или символ внутри неё. Для вызова (string-length 42) диагностика покажет строку с этим вызовом и стрелку на начало формы.

Что происходит с позициями при преобразованиях

Код не всегда пишется руками. Квазицитата строит новые списки из шаблона, и у новых пар нет собственной позиции в исходнике. Для этого у TextDb есть операции переноса.

• copy_link(from, to) копирует позицию с одной пары на другую. Квазицитата использует её так: каждая новая ячейка получает позицию соответствующей ячейки шаблона. Поэтому форма, собранная из шаблона макроса, указывает на место этого шаблона. При unquote-splicing позицию получает только первый вставленный элемент, остальные идут следом без собственной ссылки.
• inherit_info(parent, child) обходит все пары внутри child и присваивает им позицию parent. Уже связанные пары не перезаписываются: если фрагмент пришёл из исходника, он сохраняет свою настоящую позицию. Обход при этом не заходит внутрь уже известных узлов.
• clear_info() сбрасывает всё хранилище, например между сеансами REPL.

Цена решения

Ключ таблицы — shared_ptr на объект, поэтому TextDb удерживает все связанные пары, пока не будет вызвана clear_info(). Для файлов и REPL-сеансов это приемлемо: память освобождается при очистке. Для долгоживущего процесса, который постоянно порождает код, это стоило бы учитывать.

Итог: TextDb отделяет диагностические данные от представления выражения и сохраняет возможность вернуться от объекта к месту в тексте. Это не единственный способ, но он выделяет работу с источниками и координатами в отдельную подсистему.

Декларативная проверка аргументов

Почему аргументы встроенных функций — отдельная задача

Вызов в Lisp выглядит как список: первый элемент — операция, остальные — аргументы. Но функции ожидают разное. Одной нужен ровно один аргумент определённого типа, другой два, третьей разрешены дополнительные параметры с ключами.

Что должно произойти при (string-length 42)? А при (string-length) или (string-length "a" "b")? Каждая встроенная функция обязана корректно обработать такие случаи. Если писать проверки вручную, код обрастает однотипными условиями: проверить число аргументов, тип первого, тип второго, сформировать сообщение. И чем больше встроенных функций, тем больше мест, где эти правила приходится поддерживать по отдельности.

Контракт в одной строке

В SOOT каждая встроенная функция начинается с вызова vararg_check. Он принимает форму вызова (для сообщения об ошибке), уже подготовленные аргументы и два описания: ожидаемые позиционные аргументы и ожидаемые именованные.

Вот реальные примеры:

// (string-length s) — одна строка
vararg_check(form, args, {{ObjectType::STRING}}, {});

// (string-ref s i) — строка и целый индекс
vararg_check(form, args, {{ObjectType::STRING}, {ObjectType::INT}}, {});

// (floor x) — число любого вида
vararg_check(form, args, {{ObjectType::INT, ObjectType::FLOAT}}, {});

// (define имя значение [:env окружение])
vararg_check(form, args, {{ObjectType::SYMBOL}, {}}, {{"env", {false, {}}}});

Правила чтения такого описания:

• внешний список описывает позиции аргументов, внутренний перечисляет допустимые типы для данной позиции;
• пустой внутренний список означает «любой тип»;
• если внешний список непустой, число позиционных аргументов должно совпадать с ним точно;
• именованные аргументы описываются словарём: имя, флаг обязательности и допустимые типы;
• именованный аргумент, не указанный в описании, считается ошибкой.

После этого функция может сосредоточиться на своей работе, не повторяя проверку контракта.

Единообразные сообщения

Все нарушения проходят через одни и те же функции формирования ошибок, поэтому сообщения у всех встроенных функций устроены одинаково:

• несовпадение числа аргументов: arity mismatch: expected N arguments, but got M;
• неверный тип: type error at argument [i]: expected one of [...], but got [...] (индекс отсчитывается от нуля);
• пропущенный, неожиданный или неверный по типу именованный аргумент: отдельные сообщения с именем ключа.

К каждому сообщению добавляется список переданных аргументов, а ошибка привязывается к форме вызова, поэтому TextDb может показать место в исходнике. Единообразие поведения здесь не менее важно, чем сокращение кода: пользователь получает последовательные сообщения, а автор интерпретатора избавлен от десятков похожих фрагментов.

Два механизма для двух задач

vararg_check проверяет типы внутри встроенной функции. Разбор самого вызова на позиционные и именованные аргументы (:key значение), а также вычисление аргументов выполняют get_args и eval_args ещё до входа в функцию. Для пользовательских функций и макросов контракт задаётся другой структурой, ArgumentSpec, которую строит разбор списка параметров (x y &key z &rest body). Так у встроенных функций и у пользовательского кода два разных, но совместимых способа описывать аргументы.

Что механизм не умеет

• Пустое описание позиционных аргументов означает «не проверять число аргументов», поэтому «ровно ноль аргументов» этим способом не выразить.
• Нельзя задать диапазон («от одного до трёх») или необязательный позиционный аргумент. Для такого случая используется ручная проверка.

Это осознанная умеренность. Типовые контракты обслуживаются общим механизмом, а нестандартные остаются нестандартными. Попытка заставить один механизм описывать все случаи привела бы к системе сложнее, чем сами проверки.

Обработка ошибок: от сообщения к управлению выполнением

Ошибка не должна терять контекст

Пользователь вызывает функцию A, она вызывает функцию B, и та находит ошибку. Если интерпретатор просто остановится и напечатает сообщение, понять, как программа дошла до проблемной операции, будет трудно. Поэтому ошибка должна нести с собой контекст: где она возникла и через какие вызовы к ней пришли.

Кроме того, ошибка — это вопрос управления выполнением. Глубоко внутри вычисления нужно корректно прекратить текущие операции, пройти назад через активные вызовы и решить, должен ли кто-то перехватить ошибку.

Как это сделано

Вычислитель рекурсивный: каждая форма вычисляется вызовом eval_with_rewind, который вызывает eval. Ошибка выбрасывается как C++-исключение EvalException, и «раскручивание стека» — это обычное распространение исключения через вложенные вызовы вычислителя.

На каждом уровне eval_with_rewind перехватывает исключение и добавляет к нему запись трассировки: форму, которая вычислялась, и имя окружения. Затем исключение либо уходит дальше, либо передаётся обработчику.

Когда трассировка доходит до верха, отчёт собирает три вещи:

1. сообщение об ошибке;
2. место в исходнике для формы, где ошибка возникла (TextDb);
3. список накопленных записей с файлом и строкой для каждой формы, у которой они есть.

Здесь все три решения работают вместе: vararg_check формирует сообщение, TextDb определяет место, а раскручивание стека накапливает контекст.

Важное замечание о терминах. Окружение вызова функции (EnvironmentObject) хранит форму вызова и саму функцию. Это не то же самое, что StackFrame виртуальной машины, описанный в другой статье цикла.

Обработчики ошибок на самом языке

Пользователь может перехватить ошибку специальной формой with-error-handler:

(with-error-handler
  (lambda (message form trace) ...)
  ...тело...)

Форма вычисляет лямбду-обработчик и выполняет тело в новом окружении, к которому она прикреплена. Если в теле, на любой глубине вызовов, возникает ошибка, исключение доходит до уровня тела, eval_with_rewind видит прикреплённый обработчик и вызывает его с тремя аргументами: сообщением, формой, в которой возникла ошибка, и списком накопленной трассировки.

То, что обработчик возвращает, определяет судьбу ошибки:

Благодаря пробросу обработчики можно вкладывать: внутренний может дописать контекст и передать ошибку внешнему.

Следует учитывать, что к моменту вызова обработчика стек уже раскручен до формы тела. Поэтому обработчик не может возобновить вычисление с места ошибки. Он способен лишь заменить результат формы, внутри которой ошибка произошла, или передать ошибку выше. Перехват ошибки не гарантирует, что состояние программы после неё пригодно для продолжения. Это инструмент управления, а не гарантия восстановления.

Что стоит знать

Вычислитель рекурсивный и не оптимизирует хвостовые вызовы, поэтому глубина рекурсии скрипта ограничена размером стека C++. Ошибки реализованы через исключения: на нормальном пути это не стоит почти ничего, но выброс исключения дороже обычного возврата.

Как эти решения дополняют друг друга

Три механизма отвечают на три вопроса, которые задаёт себе человек при ошибке.

• Где возникла проблема? Связь S-выражений с исходником (TextDb) указывает файл, строку и место в строке.
• Что именно не так с вызовом? Контракт аргументов (vararg_check) определяет типовые нарушения и формирует сообщение.
• Что делать дальше? Обработка ошибок решает, как она распространяется, какой контекст копится и когда управление переходит к пользовательскому обработчику.

Каждое решение локально и имеет понятную задачу, но вместе они делают диагностику цельной.

Заключение

Когда пишешь небольшой интерпретатор, внимание уходит на сам язык: числа, строки, списки, функции, формы вычисления. По мере роста проекта всё большую роль играют механизмы вокруг вычисления.

Нужно сохранять связь между выражениями и исходником, чтобы ошибки было легко искать. Нужно проверять аргументы так, чтобы встроенные функции вели себя одинаково. Нужно организовать распространение ошибок так, чтобы интерпретатор мог не только сообщить о проблеме, но и передать управление пользовательскому обработчику.

TextDb отделяет сведения об исходнике от представления выражения и сохраняет связь между ними. vararg_check выражает типовой контракт в одной строке вместо повторяющейся проверочной логики. Система ошибок использует контекст выполнения и позволяет программе участвовать в реакции на ошибку. Все три решения достаточно локальны, и ни одно не пытается превратить интерпретатор в универсальный фреймворк. Они устраняют конкретные источники сложности там, где это оправдано, и этим подход напоминает остальную архитектуру SOOT: простое решение выбрано везде, где сложное не окупается.

Статус проекта