Я, еще раз я и мой маленький Лисп
Пару недель назад я делился впечатлениями от книги Lisp in Small Pieces, посвященной всяким
деталям реализации Лиспов и Схем. LiSP и Essentials of Programming Languages (обзор которой
обязательно напишу чуть позже) понадобились для небольшого
Уже в самых ранних научных публикациях по лиспостроению было принято демонстрационные языки писать
на самом Лиспе. Интерпретаторы в этом стиле называются
Чтобы понять масштаб проблемы я набросал небольшой лисп на C, использующий точную сборку мусора и самописный парсер; на этом примере и собрал предварительную пару шишек.
Работа с памятью
Алгоритм сборки мусора был изобретен Джоном Маккарти во время работы над первым Лиспом. В большинстве реализаций сборки используется тот же самый подход: «алгоритм пометок» (англ. mark and sweep).
В самом простом варианте здесь просто хранится список выделенных в куче объектов. Создание любого объекта помещает объект в этот список. Периодический запуск процесса сборки мусора сначала отмечает достижимые из программы объекты как активные, после чего удаляет все непомеченные объекты из списка.
Если с удалением все просто, то поиск активных объектов — задача тонкая. Активные объекты отмечаются, начиная от корневых объектов; а последние имеют неприятное свойство прятаться в самых неожиданных местах.
Вот, например, код встроенной функции add:
DECLARE_BUILTIN(add) { /* аллоцируем число, куда сложим сумму аргументов */ value_t *add = make_number(0); /* перебор аргументов функции */ DOLIST(current, args) { /* вычисление аргумента рекурсивным вызовом интерпретатора */ value_t *arg = interpreter_eval(interpreter, env, current); if (!IS_NUMBER(arg)) IERROR("cannot add a non-number"); /* прибавляем результат вычисления к сумме */ NUMBER_VALUE(add) += NUMBER_VALUE(arg); } /* результат либо жив, либо мертв - как повезет */ return add; }
Мы вставили
В данном случае можно либо добавить временный объект в список корневых объектов, либо вручную пометить его так, чтобы сборщик его не удалил.
Вообще, при разработке самостоятельных интерпретаторов/компиляторов часто используют libgc, консервативный сборщик мусора уровня C. Так делают, например, GNU Guile, Stalin и многие другие. Что удобно, высвобождением памяти в этом случае заниматься не приходится и никаких явных структур данных делать не придется.
Вариант рабочий, но при больших объемах памяти — а в БД именно такие — запуск алгоритма начнет занимать ощутимое время. Опять же, мои маленькие интерпретаторы хотелось бы изолировать в песочнице, да еще и так, чтобы глубина стека и максимальный объем памяти в куче были ограничены, что проще сделать вручную.
Обработка ошибок
Еще одна тонкость — обработка ошибок. Примитивные интерпретаторы для обхода деревьев исполняемых выражений, как правило, опираются на стек вызовов родительского языка. В коде обязательно будет функция типа следующей:
static value_t *interpreter_eval(interpreter_t *interpreter, value_t *env, value_t *value) { value_t *result = NULL; switch (value->type) { case VALUE_NUMBER: case VALUE_STRING: result = value; break; case VALUE_SYMBOL: result = interpreter_eval_symbol(interpreter, env, value); break; case VALUE_CONS: result = interpreter_eval_cons(interpreter, env, value); break; default: IERROR("attempt to evaluate an unevaluable type (addr=%p)", value); } gc_collect_maybe(env, value, interpreter->gc_root_stack, result); return result; }
Глубина стека вызовов функций C здесь зависит от глубины исполняемого дерева.
Сообщение об ошибке можно передать либо через возвращаемое значение функции, что усложняет код всех
функций интерпретатора, либо через великие и ужасные setjmp/longjmp (
Проблемы начинаются от того, что мы хотим разделить интерпретатор кода и его парсер: есть функции
eval и read, и eval может вызвать read, и должен при этом еще
read и eval
В моем случае беда с read и eval сводится к тому, что очень хочется использовать read
отдельно от eval, полностью вне интерпретатора. Например, для чтения файлов конфигурации или
Ну и обработка ошибок: longjmp отлично работает при интерпретации, позволяя перепрыгивать весь
стек вызовов, а возврат
Мораль
Судя по всему, надо будет все же сделать отдельную либу для чтения конфигов, с ручным подсчетом ссылок и возвратом кода ошибки и так далее. Интерпретатор — дело тонкое, со своими отдельными проблемами и требованиями к интерфейсу входных функций.
Комментарии
Comments powered by Disqus