Интерпретатор: явный стек, лимиты, хвостовые вызовы

flang/src/interpret.mjs — 827 строк, вычисление AST. Файл интересен одним решением, которое в учебных интерпретаторах обычно принимают наоборот.

Почему не рекурсия по стеку JS

Наивный интерпретатор — это функция evaluate(узел, среда), вызывающая себя на подузлах. Так пишут в большинстве примеров, и для языка, где программы завершаются, этого хватает.

Здесь не хватает, и причина названа в шапке модуля:

Обычные (не тотальные) функции flang могут не завершаться, и единственная защита от этого — лимит шагов и глубины. Если бы вычислитель рекурсивно вызывал сам себя, то раньше нашего лимита сработал бы RangeError движка («Maximum call stack size exceeded»), причём непредсказуемо: глубина стека JS зависит от размера кадров, флагов запуска и платформы. Поймать его нельзя надёжно (движок может упасть уже внутри обработчика), а диагностика вышла бы не FLANG_RECURSION_LIMIT.

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

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

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

Лимиты

const DEFAULT_MAX_STEPS = 1_000_000
const DEFAULT_MAX_DEPTH = 10_000

Обоснование записано рядом: миллиона шагов хватает на любую разумную программу (обход списка в 10⁴ элементов укладывается в сотни тысяч шагов), но зациклившаяся функция упирается в лимит за доли секунды. Глубина 10⁴ выбрана не из страха перед стеком движка — стек в куче, — а потому что «осмысленная нехвостовая рекурсия глубже 10⁴ почти всегда означает ошибку».

Проверяем на заведомо вечной программе:

модуль «Зацикливание»

функция «Вечность»
  принимает н: число
  возвращает число
  «Вечность» от (н плюс 1)

check её пропускает — функция не помечена тотальной, и претензий к ней нет:

{"valid":true,"module":"Зацикливание",
 "functions":[{"name":"Вечность","total":false}],"diagnostics":[]}

А запуск даёт:

{"code":"FLANG_RECURSION_LIMIT",
 "message":"функция «Вечность» исчерпала лимит шагов (1000000)
            на глубине вызовов 1",
 "severity":"error"}

«На глубине вызовов 1»

Эта деталь ответа — самое интересное в прогоне. Функция вызвала себя миллион раз, а глубина осталась единицей.

Дело в оптимизации хвостовых вызовов, которая описана в шапке модуля:

Хвостовые вызовы не увеличивают глубину: перед вызовом мы смотрим, стоит ли сразу за нами кадр возврата без постусловий, и переиспользуем его. Значит «пока не кончится список» пишется рекурсивно и работает в постоянной глубине.

Для языка без циклов это не оптимизация, а условие работоспособности: раз единственный способ пройти список — рекурсия, она обязана быть дешёвой.

Оговорка про постусловия существенна: функция, у которой есть постусловия, кадр не переиспользует — им нужно проверить именно свой результат. Постусловия приходят из FTS-свойств через мост (глава «flang и FTS»), и это единственный способ их получить: в синтаксисе .flang слова свойство нет.

Отметим ещё, что то же правило повторено во всех пяти бэкендах кодогенерации: хвостовой самовызов разворачивается в цикл с переприсваиванием параметров (for (;;) в C и JS, for { … } в Go, loop { … } в Rust, while True: в Python), а взаимная хвостовая рекурсия идёт через батут. Совпадение поведения между интерпретатором и напечатанным кодом здесь не побочный эффект, а явно поставленная цель (глава «Кодогенерация»).

Представление значений

Живёт в flang/src/builtins.mjs вместе со встроенными формами. Решение, достойное отдельного внимания:

Почему вариант — класс, а не объект с полем-меткой, объяснено в комментарии: запись flang это обычный JS-объект, «так значения совпадают с FtsValue ядра и сериализуются в JSON без потерь», поэтому служебное поле-метка могло бы столкнуться с пользовательским полем.

Тот же приём — «форма значения выбрана из требования совместимости, а не из удобства» — встречается в репозитории постоянно.

Семантика, которая обязана совпадать

flang/SPEC.md, раздел 5, содержит таблицу решений, обязательных для всех слоёв — интерпретатора, кодогенераторов и моста:

Две строки здесь особенно показательны. Object.is для скаляров означает, что 0.1 плюс 0.2 равно 0.3 — ложь, и это специально сохранено: бэкенд C сознательно не повторил решение ftsc сравнивать числа с допуском, потому что допуск сделал бы это выражение истиной, то есть расхождением с интерпретатором.

А к строке от признака, дающее да вместо true, — напоминание, что поверхность языка тут первична: кодогенераторы обязаны печатать да, а не удобное родное значение целевого языка.

Отказы без перехвата

Ещё одно свойство модели вычисления: отказ встроенной формы прекращает вычисление целиком. к числу от "abc", голова от пустого списка — всё это даёт ошибку, которую нечем поймать. Из шапки flang/stdlib/result.flang:

В языке нет исключений и нет способа перехватить FLANG_BUILTIN_ARGS […] Проверка должна идти ДО опасной встроенной формы, а не после: обработать её отказ уже нельзя.

Для факт-чекинга это как раз то, что нужно: детерминированный отказ вместо частично выполненного вычисления. Для прикладного кода — заметное неудобство, и оно записано в списке недостающего.

Что из этого стоит унести

Интерпретатор здесь — хороший образец того, как требование к диагностике определяет архитектуру. Захотели гарантию «зацикливание даёт код FLANG_RECURSION_LIMIT, а не исключение движка» — и получили явный стек кадров вместо рекурсии, с работой на пару сотен строк. Обратный порядок (сначала написать просто, потом «добавить лимиты») не сработал бы: поверх рекурсии по стеку JS такую гарантию не выдать.

Дальше — глава «Кодогенерация»: то же вычисление, но без интерпретатора.