Я, еще раз я и мой маленький Лисп

Работа с памятью

Алгоритм сборки мусора был изобретен Джоном Маккарти во время работы над первым Лиспом. В большинстве реализаций сборки используется тот же самый подход: «алгоритм пометок» (англ. 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 здесь зависит от глубины исполняемого дерева. Где-нибудь посреди исполнения кода может случится ошибка. Обрабатывать такую ошибку надобно на самом верхнем уровне, около корневого вызова eval.

Сообщение об ошибке можно передать либо через возвращаемое значение функции, что усложняет код всех функций интерпретатора, либо через великие и ужасные setjmp/longjmp (что-то вроде исключений, но в понимании C). Другими словами, мы должны установить обработчик ошибок через setjmp в начале исполнения кода.

Проблемы начинаются от того, что мы хотим разделить интерпретатор кода и его парсер: есть функции eval и read, и eval может вызвать read, и должен при этом еще как-то обрабатывать ошибки чтения… Т. е. функции эти не получается твердо разделить.

read и eval

В моем случае беда с read и eval сводится к тому, что очень хочется использовать read отдельно от eval, полностью вне интерпретатора. Например, для чтения файлов конфигурации или каких-то несложных данных. Но в случае независимого использования read хотелось бы иметь ручной учет ссылок, который удобно использовать для интеграции в код уровня C.

Ну и обработка ошибок: longjmp отлично работает при интерпретации, позволяя перепрыгивать весь стек вызовов, а возврат какой-нибудь специально структуры struct result с кодом ошибки удобней как интерфейс библиотеки.

Мораль

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