Ядро FTS на flang — и компилятор, который взялся за себя

Язык ставится одной командой: brew install digitable-lol/tap/flang. Номера версий в разборе ниже — те, что стояли на момент его написания.

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

Часть первая: ядро FTS

В каталоге flang/core/ лежат четыре файла на самом flang общим объёмом около 390 КБ (398 618 байт, 4573 строки). Это ядро FTS — лексер, парсер, вычислитель утилит и печать JSON, — переписанное с TypeScript на язык, который сам живёт в этом же репозитории.

Оговорка сразу: эта глава переписывалась трижды. В первой редакции парсер на flang не брал скобочный диалект FTS и на трёх моделях корпуса отвечал FTS_UNSUPPORTED_SURFACE; через час долг закрыли, и корпус сошёлся весь. Третью редакцию вызвало то, что описано во второй половине главы, — и заодно она исправляет число, которое мы здесь напрасно называли.

Цель сформулирована в первой строке flang/core/SPEC.md:

переписать ядро FTS (сейчас src/*.ts, 3155 строк) на flang, чтобы печатать его в C и получить нативный fts без Node — и дальше в остальные целевые языки.

То есть кодогенерация (глава «Кодогенерация») здесь не самоцель, а средство: если ядро написано на flang, а flang печатается в C, то fts становится нативным бинарником.

Почему это стало возможно только сейчас

Ответ объясняет, зачем flang вообще понадобился. В репозитории есть файл tools/ftsc/self/meta.fts с записанным ограничением:

в ядре FTS строка является типом поля, но не значением, над которым можно вычислять

Парсер — это вычисления над строками. Поэтому ядро FTS нельзя было написать на самом FTS. flang снимает ровно это ограничение: строки в нём данные.

Так что core/ — не демонстрация возможностей, а тест на состоятельность замысла. Язык создавался, чтобы на нём можно было написать инструментарий FTS; core/ проверяет, получилось ли.

Что написано

Мы проверили это запуском — flang check на каждом файле возвращает valid: true и ни одной функции с total: false. Считать при этом надо аккуратно: check показывает функции уже после связывания модулей, поэтому у parser.flang в ответе 280 функций — свои 208 плюс 41 из лексера и 31 из печати JSON.

300 функций, все с доказанным завершением. Для языка, чей анализ тотальности отвергает даже рекурсию n − 1, это не само собой разумеется — см. ниже про цену. За час до нашей сверки в лексере было 34 функции, а в парсере 131: разбор скобочного диалекта прибавил к ядру почти сотню функций и тысячу строк.

Файлы связаны импортом: parser.flang использует «Лексер FTS» и «Печать JSON», evaluate.flang — «Печать JSON». То самое связывание модулей, ради которого появился link.mjs (глава «Стандартная библиотека»).

Слои и границы

текст .fts ──[лексер]──> список «Токен» ──[парсер]──> «Документ»
                                                          │
                                        ┌─────────────────┴───────────────┐
                                   [вычислитель]                     [печать JSON]
                              значение / диагностика            строка, байт в байт
                                                                  как у ядра на TS

Правило границ жёсткое: «Никакой слой не разбирает текст повторно и не заглядывает внутрь чужого слоя». Стыкуются слои только через типы, объявленные в контракте:

тип «Токен»
  вариант ОтступБольше
  вариант ОтступМеньше
  вариант КонецСтроки
  вариант Имя содержит текст: строка
  вариант Строка содержит текст: строка
  вариант Число содержит значение: число
  вариант Знак содержит текст: строка
  вариант Конец

Два последних варианта — Строка и Знак — появились в контракте вместе с разбором скобочного диалекта, и оба обязательные, а не косметические. Знак нужен, потому что без него { прилипало к соседнему слову и structure B { давало два токена вместо трёх. Строка — потому что ядро на TypeScript различает kind: "identifier" и kind: "string": «да» в ёлочках это признак, "да" в обычных кавычках — строка, и слить их значило бы разойтись с эталоном.

Тот же коммит уточнил и разбор точки: она режется только там, где слово не является числом. 10.5 остаётся одним токеном, Individual.isHuman — тремя, «ровно там же, где останавливается регулярное выражение числа в ядре».

Критерий готовности

Вот это стоит перенять независимо от того, интересен ли вам flang.

Ядро считается верным не тогда, когда проходят его собственные тесты, а когда на всех .fts репозитория старое ядро на TS и новое на flang дают побайтово совпадающий JSON — включая коды и тексты диагностик.

Дифференциальная сверка против существующей реализации вместо собственного набора тестов. Своя тестовая база проверяет то, о чём подумал автор; сверка с работающим предшественником проверяет всё, что предшественник умеет, включая поведение, о котором никто не помнит.

Результаты записаны по слоям, и записаны с указанием того, что не сошлось:

• Печать JSON: весь корпус моделей, ноль расхождений с JSON.stringify(compile(…)).
• Вычислитель: 20 документов, 24 утилиты, 11 180 входов, ноль расхождений — «совпадают и значения (по Object.is, до последнего бита), и коды диагностик».
• Парсер: сквозная сверка текст → лексер → парсер → печать JSON — весь корпус, ноль расхождений, обе поверхности. Диагностики сверены отдельно: на 34 намеренно сломанных моделях отступной поверхности и на 13 моделях скобочной совпадают и код, и текст сообщения.
• Мост совместимости (compat.mjs, не на flang): 19 593 входа, ноль расхождений.

Ещё за час до первой нашей сверки парсер сходился не со всем корпусом: три модели были написаны скобками, он честно отвечал FTS_UNSUPPORTED_SURFACE, а тест закреплял это как долг. Такая формулировка была здоровее, чем округление до «работает», — и, судя по тому, что долг закрыли ближайшим коммитом, она же оказалась и полезнее. Записанный долг видно; «работает» не видно никому.

Почему здесь не написано, сколько моделей

Потому что мы уже написали — и ошиблись. В первых редакциях этой главы стояло «56 моделей из 56», и число было честно списано с flang/core/SPEC.md, где стоит до сих пор. Проверять его мы не стали: сошлось с тем, что показал наш прогон.

Сошлось потому, что прогон шёл на той же машине. Корпус теста (flang/test/core-parser.test.mjs) собирает все .fts репозитория — и дополнительно внешний каталог моделей, если тот есть на машине. В комментарии к функции это написано прямым текстом: «Внешний каталог не обязателен — тест не имеет права зависеть от чужого рабочего дерева». Тест и не зависит: он требует не «56», а «не меньше сорока».

Мы пересчитали, отключив внешний каталог: на чистом клоне моделей 47, а 56 получается только там, где рядом лежит ещё один репозиторий с моделями. Именно столько их оказалось на нашей машине — и ровно поэтому число выглядело подтверждённым.

Корневой README.md эту ловушку уже обошёл, и формулировка там образцовая:

47 of them on a clean clone […] If an external model directory is present on the machine, its models are added to the same run, so your local count may be higher than 47; the promise is the corpus, not the number.

Обещание — это корпус, а не число. Мы приводим этот случай не для покаяния, а потому что он типовой: цифра из документации совпала с цифрой из прогона, и обе были неверны одинаково, потому что происходили из одной машины. Совпадение двух источников — не проверка, если источник у них общий.

Как удалось остаться в тотальном классе

Никакой магии — те же приёмы, что в стандартной библиотеке (глава «Тотальность»), только применённые к настоящему компилятору.

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

Печать JSON. Экранирование строки сворачивается по таблице из 34 замен, каждая через разделить и соединить.

Вычислитель. Рекурсии нет вовсе: правила, свойства, условия и примеры — это списки, и обход каждого выражен свёрткой. Отдельно решена задача, которая в обычном языке решается break: короткое замыкание условий и «первая диагностика прекращает счёт» выражены состоянием свёртки — «сработавший отказ протаскивается дальше нетронутым, и тела остальных шагов не вычисляются».

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

Отступная поверхность разбирается тремя свёртками: поток режется на строки, строки собираются в группы «заголовок и всё, что глубже», и только потом каждая строка разбирается по первым словам — это разбор формы фиксированной длины. Рекурсия осталась в пяти вспомогательных функциях («Пропустить слова», «Взять слова», «Начинается словами», «Позиция слов», «Заменить слова»), и всюду это рекурсия по хвосту списка на одной и той же позиции аргумента.

Скобочная поверхность — та, что появилась последним коммитом, — спуск всё-таки использует, но не по потоку, а по дереву. Поток свёрткой сворачивается в «Узел» (стек открытых скобок, строки режутся тут же), и дальше поддерево — это поле варианта, а строка группы — элемент списка, то есть строго меньшая часть того же значения. Взаимная рекурсия там появилась («Утверждение из узлов» ↔ «Шаг тела утверждения» и три функции разбора произвольного значения), и в каждом цикле убывает первый аргумент — та самая единая позиция на каждом ребре, которой требует totality.mjs (глава «Тотальность»).

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

Долги, записанные честно

Раздел «Долги» в flang/core/SPEC.md занимает больше половины файла. Долг определён как «либо место, где не поставлен признак тотальная, либо расхождение с ядром на TS, о котором знают и которое пока оставлено». Несколько примеров:

• Нормализация NFC не выполняется. Ядро зовёт String.normalize на каждом имени, а в flang такой встроенной формы нет — «её нельзя выразить ни через „разделить“, ни через „подстрока“». Пока все модели репозитория в NFC, расхождение ненаблюдаемо.
• Одинокий суррогат не экранируется. Отличить суррогат нечем: нет формы «код символа». Долг закрывается не в json.flang, а в builtins.mjs. Отдельно отмечено, что закреплён тест с именем «известный долг: одинокий суррогат не экранируется» — «именно затем, чтобы закрытие долга не прошло молча».
• Экспоненциальная запись числа считается именем. Лексер на flang следует букве контракта, а регулярное выражение ядра шире. «Расширять придётся вместе с разделом 1, а не вместо него».
• executeUtility и сводка testUtilities не реализованы — им нужен «Документ» целиком, а слой видит только утилиту.
• Имя-неидентификатор печатается неполно. ts_compat ядра переводит такое имя в FTS_ и коды его символов шестнадцатеричными (FTS_4c_6f_79…), а формы «код символа» в языке нет — тот же долг, что у одинокого суррогата. В этой ветке остаётся один префикс. Долг новый: он записан тем же коммитом, который закрыл скобочный разбор, и снабжён тестом «известный долг», чтобы закрытие не прошло молча.

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

И один долг, который стоит привести как пример нормальной инженерной честности:

Скаляр — сумма типов, а не строка. В первой редакции этого файла скаляр был записан как строка, и печать JSON это сразу опровергла: 5, "5" и да дают три разные строки JSON, а по текстовому представлению их не различить. Ошибка контракта, найденная слоем печати.

Ошибка контракта, найденная нижним слоем, записана в контракт вместе с тем, как её нашли.

Часть вторая: самоприменение

До сих пор речь шла о ядре FTS. Компилятор самого flang к этому отношения не имел: лексер, парсер, типы, тотальность и интерпретатор лежали и лежат в flang/src/*.mjs — 6166 строк JavaScript, и это ещё без эмиттеров, с которыми получается вдвое больше. Пока это так, «язык, который работает везде» означает «везде, где есть Node», а это не то же самое.

С недавних пор в репозитории есть каталог flang/self/, и в нём компилятор языка переписан на самом языке. Контракт — flang/self/SPEC.md, и цель в нём названа без околичностей: снять зависимость от Node. Забегая вперёд: критерий, который контракт себе поставил, выполнен — но интереснее оказалось не это, а то, обо что работа споткнулась по дороге и чем эта стена оказалась на самом деле.

Почему это выполнимо, а не мечта

Ответ — первая половина этой главы. Ядро FTS уже переписано: 300 функций, все тотальные, побайтовое совпадение с эталоном на всём корпусе. «Компилятор языка — задача того же порядка, а не другого».

И одно обстоятельство делает её проще ядра, а не сложнее — то самое, которое разбиралось в главе «Два класса программ». flang/self/SPEC.md формулирует его первой же строкой раздела:

Главное, что делает её проще ядра: компилятору тотальность не нужна.

Ядро FTS обязано быть тотальным, потому что через него отвечает факт-чекер. Компилятор такого обещания не давал: он имеет право упереться в лимит шагов и честно об этом сказать. Поэтому в flang/self/ обычные функции разрешены прямо — «там, где доказательство убывания стоило бы дороже пользы», — но каждая такая обязана быть названа в разделе «Долги» с причиной.

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

Шесть слоёв, по одному файлу на слой:

Числа в четвёртой колонке мы считали по самим файлам (grep -c '^\(тотальная \)\?функция «'), а не по ответу flang check: тот показывает функции уже после связывания модулей и потому насчитывает больше — свои плюс импортированные. После связывания в компиляторе 1269 функций и 148 типов; проверяется это прямо:

$ node --input-type=module -e '
    const { loadProgram } = await import("./flang/bin/flang.mjs")
    const p = await loadProgram("flang/self/bootstrap/compiler.flang")
    console.log(p.functions.length, p.types.length,
                p.functions.filter(f => f.total).length)'
1269 148 797

Жирное число в первой строке — главное, что произошло здесь за сутки. Лексер самоприменения стал тотальным целиком: 84 функции из 84. В прошлой редакции этой таблицы стояло 54 из 88, и это была самая дешёвая на вид строка — «ну лексер, ну ходит по строке». Оказалось, что она держала половину всей арифметики: закрыли одну недостачу языка (встроенную форму разложить … на символы), и вместе с лексером прибавили печать в C — 33 доказанные функции — и парсер, 41. Разбор — в главе «Тотальность».

Слои на JS при этом выросли заметно сильнее, чем их двойники на flang: types.mjs за те же сутки вырос в два с половиной раза, потому что в него приехали параметрический полиморфизм и функции первого класса. Ни того, ни другого самоприменение пока не понимает, и это долг, названный в flang/PLAN.md прямо: пока self/ не разбирает новую форму, ни одна программа репозитория не вправе ею пользоваться — корпус сверки собирается по маске каталога, и первый же такой файл роняет неподвижную точку.

Два файла в этот список не попали, и оба по названной причине. builtins.mjs не переписывается вовсе: это встроенные формы самого языка, они есть в рантайме каждой цели. interpret.mjs не переписывается для запуска: «чтобы получить нативный компилятор, достаточно печати в C».

Шестого слоя в плане не было, а он понадобился

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

Файлов в flang/src/ девять, слоёв в плане было пять. Два не переписываются по названной причине. Остаются interpret.mjs, compat.mjs, factcheck.mjs — эти для нативного компилятора не нужны, — и src/link.mjs, 245 строк, который нужен. Это он разрешает использует … из "…": находит файл по относительному пути, обходит граф импортов, сливает объявления в одно пространство имён и режет его списками экспортирует и только (глава «Стандартная библиотека»).

Без него пять слоёв — это пять файлов, а не программа: self/parser.flang начинается с использует «Лексер flang» из "lexer.flang", и точно так же устроен каждый следующий. В редакции этой главы, написанной сутками раньше, здесь стояло: «пока она не решена, „компилятор, написанный на flang“ остаётся набором частей, собрать который умеет только Node». Так и было — ровно до появления flang/self/bootstrap/compiler.flang, 631 строки и 68 функций, где связывание написано на самом языке и сверено с src/link.mjs дифференциально: на синтетических наборах файлов совпадают и связанная программа целиком, и её диагностики. Наборы синтетические не от лени — чтобы поймать экспортирует, только, повтор имени, цикл импортов и несовпадение имени модуля, нужны файлы, которых в репозитории нет и быть не должно.

Первая проверка нового слоя — не «работает», а «слои вообще складываются в одну программу»: у пяти слоёв, писавшихся порознь, нашлось 52 общих имени («Узел ничто», «Диагностика», «Как в JS» — у каждого свои), а link.mjs сливает объявления в одно плоское пространство имён, где повтор имени это ошибка, а не перекрытие.

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

$ grep -c linkProgram flang/test/self-emit-c.test.mjs
$ echo $?
1

$ grep -a -c linkProgram flang/test/self-emit-c.test.mjs
3

Разница в ключе -a. В этом файле есть нулевой байт, и лежит он не случайно — в образце, на котором проверяется экранирование строк в C: рядом с ним 0x1F и 0x7F, и все три записаны сырыми байтами, а не escape-последовательностями, потому что печать сырых и проверяется.

Файл от этого читается как двоичный, и поиск, настроенный такие файлы пропускать, не ищет в нём вовсе. Существенно здесь второе: «не искал» он сообщает ровно тем же, чем сообщил бы «не нашёл», — пустым выводом и кодом возврата 1. GNU grep 3.11 на том же файле отвечает 3 и перечисляет все пять тестов; промолчала стоявшая у нас в PATH замена. Нулевой байт во всём flang/ ровно один, и он оказался в том самом файле, о котором спрашивали.

Мораль та же, которой держится весь трек, только повёрнутая неожиданной стороной. Проверять утверждение запуском — правильно; но инструмент проверки сам есть утверждение, и пустой вывод означает не «нет», а «ответа нет».

Как связывание вообще выразилось на языке без ввода-вывода, видно из сигнатуры: файлы приезжают в компилятор списком пар «путь и текст», а не читаются им с диска. Читает диск прогонщик; чистое вычисление получает уже прочитанное. Ровно поэтому шестой слой и оказался выразимым, хотя выглядел работой с файловой системой.

Критерий готовности — неподвижная точка

Здесь самое интересное. «Самоприменение считается достигнутым не тогда, когда „скомпилировалось“», — и дальше классический bootstrap, выписанный тремя строками:

1. Компилятор на JS печатает self/*.flang        → C → собирается → flang₁
2. flang₁ печатает те же self/*.flang            → C → собирается → flang₂
3. C, напечатанный flang₁, и C, напечатанный flang₂, совпадают побайтово

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

Тот же приём, что в первой половине главы, только доведённый до предела: там новая реализация сверялась со старой, здесь новая сверяется сама с собой. Дополнительно требуется и обычное: flang₁ обязан проходить весь существующий набор тестов языка с теми же кодами диагностик.

Что это даёт, названо тремя пунктами, и ни один не про красоту:

• flang ставится как обычная программа на C — «там, где есть cc, а не там, где есть Node»;
• ядро FTS, уже напечатанное в C, и компилятор языка перестают требовать разных сред;
• README перестаёт начинаться с требования установить Node.

Все три сбылись, и как именно — в разделе «Что это дало на практике» ниже.

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

Стена, которая стояла на шаге 2, и почему она не про язык

Цепочку долго не проходили целиком, и упиралась она не в понимание языка. Упиралась она в память — а механизм тут общий для любого рантайма без сборщика мусора, поэтому разобрать его стоит, даже если flang вам безразличен.

добавить — единственный способ удлинить список, и в рантайме на C он выделял новый массив на n+1 значений и делал memcpy. Арена же не освобождает ничего до конца запроса — это её договор: программа flang есть чистое вычисление, значит время жизни всего, что она построила, это время жизни вызова. Отсюда прямое следствие, которого договор не называет: список из n элементов, собранный n вызовами добавить, оставляет после себя ~16·n² байт мусора, который никто не соберёт. В шапке fl_b_dobavit это записано вместе с ценой: «Неподвижная точка самоприменения упиралась в 90 ГБ и не доходила».

Под сборщиком мусора этого не видно вовсе. В JavaScript [...list, x] копирует ровно так же, и время там тоже квадратично, но живой памяти всё время O(n): промежуточные копии умирают сразу. Разница между реализациями не в алгоритме, а в том, что одна отдаёт память, а другая — нет. Лексер, собирающий поток токенов, пишется одинаково в обеих — и в одной работает, а в другой нет.

Это стоит увидеть на своей машине; программа занимает восемь строк:

модуль «Наполнение»

функция «Наполнить»
  принимает н: число, накопитель: список числа
  возвращает список числа
  если н равен 0
    то накопитель
    иначе «Наполнить» от (н минус 1) и (добавить н к накопитель)

функция «Размер»
  принимает н: число
  возвращает число
  длина («Наполнить» от н и пустой список)

Печатаем её в C, собираем и просим построить список из двадцати тысяч элементов — сперва рантаймом до правки, потом после:

$ # рантайм до правки
$ printf '{"fn":"Размер","args":[{"n":"20000"}]}\n' | /usr/bin/time -v ./flang_cli
{"ok":true,"value":{"n":"20000"}}
  Elapsed (wall clock) time (h:mm:ss or m:ss): 1:38.19
  Maximum resident set size (kbytes): 6289536

$ # тот же исходник, рантайм после правки
$ printf '{"fn":"Размер","args":[{"n":"20000"}]}\n' | /usr/bin/time -v ./flang_cli
{"ok":true,"value":{"n":"20000"}}
  Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
  Maximum resident set size (kbytes): 3584

Шесть гигабайт против трёх с половиной мегабайт на одной и той же программе. И формула проверяется прямо тут же: 16·20 000² — это 6.4 ГБ, а измерено 6 289 536 КБ, то есть 6.44 ГБ. Механизм был назван, а не угадан.

Лечится это без отказа от неизменяемости — но первое лекарство оказалось негодным, и это самая полезная часть истории. В прошлой редакции мы описали здесь именно его, вслед за контрактом: раз арена умеет продлить последнюю выдачу, пусть добавить её и продлевает — тогда достаточно занять одну ячейку сверху, и ни одно существующее значение не меняется.

Рассуждение верное, эффект нулевой. Замер записан в рантайме вместе с числами — 20 000 вызовов добавить, байт арены на элемент:

между «добавить» ничего не выделяется:  321 018 → 316 691  (−1.3%)
между «добавить» выделяется значение:   379 882 → 379 882  (0%)

Причины две, и обе неустранимы в рамках «продлить последнее». Первая: последним массив почти никогда не бывает — список из чего-то состоит, и это что-то строится перед тем, как попасть в список. Ровно так работает лексер, и ровно поэтому вторая строка не сдвинулась ни на байт. Вторая: как только массив перерастает кусок арены (64 КБ, то есть 2048 значений), он получает кусок ровно по себе, и продлевать его некуда.

Работает другое: запас ёмкости, взятый заранее. Тогда между двумя добавить арена может выдать сколько угодно чужого — ячейка всё равно наша. Неизменяемость держится на одном инварианте, и он же её доказательство:

у массива с запасом есть общая на всех запись fl_grow, и filled в ней — число ячеек, УЖЕ кем-то занятых; оно только растёт. Занять ячейку count разрешено единственному — тому, у кого count == filled.

Отсюда прямо следует и то, ради чего всё затевалось, и то, что ничего не сломалось: ячейка за концом списка пишется не более одного раза за всю жизнь арены, ячейки 0…count−1 не трогаются вовсе, а второе добавить к тому же самому значению видит filled > count и честно уходит на копию. Разветвление пусть «а» равно (добавить 1 к «с») / пусть «б» равно (добавить 2 к «с») даёт два независимых списка, и ни один не портит «с».

Запас удваивается, поэтому за все перевыделения арена отдаёт около 4n ячеек вместо n²/2. Продление последней выдачи на месте при этом осталось — но как дополнение к запасу, а не как замена ему: в свёртке, где между двумя добавить не выделяется ничего, копий нет вовсе.

Мораль здесь не про арены. Приём был предложен, записан в контракт как решение — и опровергнут замером на 20 000 элементов, который стоило сделать до того, как писать. Опровержение оставлено в комментарии рядом с рабочим решением, вместе с числами; это дороже готового ответа, потому что следующий читатель придёт к той же идее и сразу увидит, чем она кончилась.

Неподвижная точка сошлась

Стена снята, шестой слой написан — и цепочка прошла целиком. Мы прогнали её сами; она занимает уже не минуту, а две с небольшим, и выглядит так:

$ node --test flang/test/self-bootstrap.test.mjs
✔ пять слоёв связываются в одну программу без столкновения имён
✔ связанный компилятор проходит проверку типов и анализ завершаемости
✔ примеры обёртки сходятся
✔ связывание на flang повторяет src/link.mjs: программа и диагностики
✔ шаг 1: эталон печатает компилятор в C, и этот C собирается
✔ flang₁ печатает тот же C, что эталон, побайтово
✔ flang₁ строит тот же связанный AST, что эталон, побайтово
✔ flang₁ выносит те же вердикты и диагностики, что эталон
✔ оболочка flang₁ отвечает то же, что оболочка на Node: значения, диагностика, код
✔ оболочка flang₁ без компилятора C не выключается, а продолжает проверять
✔ печать компилятора укладывается в память: поток токенов не копируется
✔ шаги 2 и 3: flang₁ печатает сам себя, flang₂ печатает то же самое
ℹ неподвижная точка сошлась: 7 файлов совпали побайтово у эталона, flang₁ и flang₂
ℹ tests 12
ℹ pass 12
ℹ fail 0
ℹ duration_ms 131581

Против прошлой редакции здесь две новые строки и одно новое число. Файлов стало семь — прибавился flang_repl.c. И это не просто ещё один файл в наборе: оболочка, напечатанная в C, обязана отвечать то же самое, что оболочка на Node, — значениями, диагностикой и кодом возврата. То есть в неподвижную точку въехала не только печать компилятора, но и его человеческий интерфейс.

Разберём, что здесь на самом деле проверено, потому что «сошлась» — слово громкое.

Шаг 1. Эталон на JavaScript печатает связанный компилятор в C: семь файлов — flang_runtime.h, flang_runtime.c, kompilyator_flang.h, kompilyator_flang.c, flang_cli.c, flang_repl.c и Makefile. Этот C собирается тем самым cc -std=c99 -Wall -Wextra -Werror -pedantic за шесть секунд, и получается flang₁. Одна оговорка в тесте стоит отдельного взгляда: -Wbidi-chars приходится гасить явно, потому что в self/lexer.flang лежит таблица блока U+2000…U+207F целиком. Это данные, а не подмена направления письма в исходнике, но предупреждение честное — и гасится явным ключом, а не понижением строгости.

Что flang₁ умеет. Дальше он гоняется как настоящий компилятор на 38 программах репозитория — вся stdlib, все решения LeetCode, core/parser.flang и self/parser.flang, самые крупные файлы, — и обязан выдать побайтово тот же C, что эталон, побайтово тот же связанный AST и те же диагностики и тот же вердикт: и на чистых программах, и на семи сломанных, покрывающих все шесть кодов, которые выдают слои (FLANG_TYPE, FLANG_UNKNOWN_NAME, FLANG_MATCH_NOT_EXHAUSTIVE, FLANG_MATCH_UNREACHABLE, FLANG_BUILTIN_ARGS, FLANG_NOT_TOTAL).

Шаги 2 и 3. flang₁ печатает собственные исходники, из этого собирается flang₂, и он печатает их снова. Сверяются три источника, и все побайтово: C от flang₁ против C от эталона, C от flang₂ против C от flang₁, и сам факт того, что flang₂ собирается тем же cc с теми же флагами.

Первое сравнение сильнее критерия из контракта, и не зря: совпадение с эталоном говорит, что flang₁ печатает правильно, а совпадение flang₂ с flang₁ — что правильно печатает и программа, собранная из этой печати. Разойтись они могут порознь.

Стоит заметить и то, чего в этом прогоне нет: слова «примерно». Совпасть обязаны байты — семь файлов из семи, у трёх независимых печатей.

Цена проверки названа прямо. Шаги 2 и 3 стоят двух сборок компилятора вместо одной, и это самая долгая проверка в наборе — минуты, а не секунды. Она всё равно идёт всегда, и обоснование в шапке теста стоит забрать себе: «„неподвижная точка сходится“ — не то утверждение, которое имеет смысл проверять по праздникам».

Что сходится по слоям

Каждый слой сверен с эталоном отдельно и тем же способом, что и ядро FTS: не собственными тестами, а побайтовым совпадением на всём, что есть в репозитории. Это не дублирование итоговой сверки — когда расхождение всё-таки случится, по слою видно, где оно возникло, а по неподвижной точке видно только, что оно есть.

Лексер (self/lexer.flang, 84 функции, и все 84 тотальны). Поток токенов совпадает с src/lexer.mjs на каждом .flang репозитория — вид, значение, признак закавыченности, строка и столбец, — плюс краевые случаи и триста случайных склеек.

Парсер (self/parser.flang, 374 функции). AST совпадает с эталоном побайтово — то есть «Печать значения» от построенного узла и JSON.stringify(parse(исходник)) дают одну и ту же строку — на всех .flang репозитория, включая собственный исходник, и на моделях .fts. Отказы сверяются так же: код, текст сообщения и место.

Печать в C (self/emit-c.flang, 328 функций). Напечатанный C совпадает с эталоном побайтово на программах репозитория, включая собственный исходник, и на моделях .fts через мост совместимости. Весь напечатанный C собирается cc -std=c99 -Wall -Wextra -Werror -pedantic без единого предупреждения.

Проверка типов (self/types.flang, 276 функций). Здесь способ сверки пришлось поменять, и причина поучительна: на чистых файлах верный ответ — «диагностик нет», а его выдаёт и функция, которая вообще ничего не делает. Поэтому сломанная половина корпуса обязательна, и требование к ней не «поймала ошибку», а «сказала о ней теми же словами в том же месте». Собрано три источника: 76 сломанных программ (часть из них — AST, собранный руками, потому что с поверхности до таких ошибок не добраться), 76 настоящих файлов репозитория с одной механической порчей каждый, и 200 случайных программ с зафиксированным сидом. Именно фаззинг нашёл единственный дефект, которого не видели ни чистые файлы, ни сломанные: в проверке значения записи лишние поля назывались раньше незаданных.

Анализ завершаемости (self/totality.flang, 124 функции). Вердикт совпадает с эталоном на всех программах репозитория — и совпадает дважды: на связанной программе и на сырой, разобранной без импортов. Второй прогон не для счёта: имена соседних модулей в нём неизвестны, и только он даёт ветку «тотальная функция вызывает неизвестную функцию», которой на связанных программах нет ни разу.

Один алгоритм здесь заменён другим сознательно: эталон раскладывает граф вызовов замыканием достижимости, слой на flang — алгоритмом Тарьяна. Разбиение выходит то же (компоненты сильной связности единственны), но порядок компонент разный, а порядок наблюдаем — диагностики идут покомпонентно, и имена цикла попадают в текст сообщения. Поэтому результат Тарьяна приводится к порядку эталона. Причина не брать замыкание дословно названа числом: на списках оно стоит куба от числа функций, а в flang/core/parser.flang их 280 после связывания.

Связывание (self/bootstrap/compiler.flang, 68 функций). Сверяется дифференциально с src/link.mjs на синтетических наборах файлов: слияние объявлений, только, экспортирует, повтор имени, цикл импортов, второй проход по вызовам без аргументов. Совпасть обязаны и связанная программа целиком (побайтово после сериализации), и диагностики — по коду и тексту.

Корпус .fts в сверке парсера — не для объёма. Конструкций наследия FTS (утилита, морфизм, теорема, файл-функтор, старая скобочная поверхность) нет ни в одном .flang репозитория, а разбирает их тот же parser.mjs. «Без .fts половина эталона осталась бы непроверенной», и тест отдельно требует, чтобы в корпусе встретились все семь видов узла наследия.

Печать, написанная на flang, нашла дефект в печати, написанной на JS

Это стоит отдельного абзаца, потому что показывает, зачем вообще писать вторую реализацию.

Бэкенд C печатает взаимную хвостовую рекурсию через батут. Компонента, у которой все хвостовые позиции — отскоки, давала шаг батута с неиспользованным параметром result: эталон гасил ctx, error, bounce и параметры, но не его. Под -Wextra -Werror это ошибка сборки, то есть src/emit/c.mjs печатал некомпилируемый C.

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

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

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

Цена, названная прямо

Ядро FTS тотально целиком. Компилятор — почти на две трети: из 1269 функций связанной программы завершение доказано у 797. В прошлой редакции здесь стояло «чуть больше чем наполовину, 687 из 1272»; сдвинуло цифру закрытие одной недостачи языка — встроенной формы разложения строки в список. В «Долгах» flang/self/SPEC.md перечислена каждая обычная функция с причиной. Причин формально несколько, но по существу они сводятся к одной, и она названа в файле трижды, в трёх разных слоях:

Долг этот закрывается не хитростью, а встроенной формой: будь в языке «символы строки» (разложение строки в список), весь проход стал бы рекурсией по хвосту списка и доказался бы.

Лексеру нужен посимвольный проход — экранирование \" и блочный комментарий поперёк строк приёмом «разделить и свернуть» не берутся. Печати в C нужен обход строки по индексу — считать байты UTF-8 и резать имена на слова. Парсеру нужно то же самое при разборе падежных окончаний. Во всех трёх случаях убывает не часть значения, а разность «длина минус позиция», то есть число, а числового убывания анализ не признаёт (глава «Тотальность»).

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

У парсера есть и своя, отдельная цена, и она тоже названа решением, а не упущением. Ядро FTS обошлось без рекурсивного спуска, потому что поверхность .fts построчная. Поверхность flang не построчная, и здесь спуск выбран сознательно: порядок вызовов повторяет parser.mjs функция в функцию, «поэтому расхождение всегда локально — видно, в какой именно функции оно возникло». Цена записана в той же строке: нетотальность.

Что это дало на практике: установка без Node

Ради этого всё и затевалось, и результат проверяется одной командой. В разделе Install корневого README.md теперь стоит:

brew install digitable-lol/tap/flang

Рядом объяснено, почему это работает: Node не нужен, потому что компилятор написан на самом flang и печатается в C, а релиз везёт этот C уже напечатанным — хватает компилятора C99. Формула лежит в репозитории — packaging/homebrew/flang.rb, — и в её шапке та же мысль, уже по-русски: «Так поступают самоприменяющиеся языки: Go долго возил сгенерированный C, Nim возит до сих пор. Проблема начальной загрузки остаётся только у того, кто развивает сам язык, — ему нужен Node, чтобы получить первый бинарник из исходников на flang. Тому, кто просто ставит flang, не нужен никто».

Оговорка прошлой редакции — «раздела этого нет в README.ru.md, русская версия отстала и всё ещё перечисляет пять целей печати вместо восьми» — снята. Оба README сегодня говорят «восемь целей», и раздел про установку через Homebrew в русском есть.

Проверим это без всякого brew — прямо из релизного архива. Готовит его node scripts/build-release-c.mjs, и файлов в нём теперь семь, а не шесть:

файлов в релизе: 7
   flang_runtime.h        19 978
   flang_runtime.c        59 587
   kompilyator_flang.h   570 230
   kompilyator_flang.c  3 331 342
   flang_cli.c            21 884
   flang_repl.c          128 025
   Makefile                  583

Седьмой — flang_repl.c, оболочка. Просит её скрипт релиза одним ключом (repl: true), а прогонщик разбирает argv[1] == "repl" и уходит в fl_repl_main. То есть язык, поставленный из brew, теперь можно потрогать, а не только запустить на файле; в прошлой редакции этой главы такого ещё не было.

Собираем в окружении, где Node в PATH нет вовсе:

$ env -i PATH=/путь/без/node sh -c 'command -v node || echo "node в PATH нет"; make'
node в PATH нет
cc -std=c99 -Wall -Wextra -Werror -pedantic -O2   -c -o flang_runtime.o flang_runtime.c
cc -std=c99 -Wall -Wextra -Werror -pedantic -O2   -c -o kompilyator_flang.o kompilyator_flang.c
ar rcs libkompilyator_flang.a flang_runtime.o kompilyator_flang.o
cc -std=c99 -Wall -Wextra -Werror -pedantic -O2   -c -o flang_cli.o flang_cli.c
cc -std=c99 -Wall -Wextra -Werror -pedantic -O2 -o flang_cli flang_cli.o …

$ ldd flang_cli
	libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6

2 465 048 байт нативного компилятора, слинкованного с libc и libm и больше ни с чем. Спрашиваем его о программе на flang — той же проверкой, которую ставит себе формула Homebrew:

$ printf '{"fn":"Число связанных функций","args":[…"модуль «Проба»…"…]}\n' | ./flang_cli
{"ok":true,"value":{"n":"1"}}

Обратите внимание, что проверяет формула: не «запустился», а «понял язык» — подаёт модуль и требует, чтобы компилятор насчитал в нём ровно одну связанную функцию.

Разделение получилось честное и стоит того, чтобы его запомнить:

Нативный компилятор печатает только в C — это прямо записано в README, и иначе быть не может: остальные семь бэкендов, интерпретатор и CLI написаны на JavaScript, и на flang их никто не переписывал. Полный инструментарий — это по-прежнему дерево репозитория, собираемое make -C bootstrap -j8.

Одну вещь прошлая редакция проверить не смогла: сам brew install digitable-lol/tap/flang требует опубликованного tap, а его тогда не было. Теперь он есть — тап digitable-lol/homebrew-tap публичен, и brew его разбирает:

$ brew info digitable-lol/tap/flang
==> digitable-lol/tap/flang: stable 0.6.2

Что проверено запуском: архив релиза скачивается, его sha256 сходится с объявленным в формуле, а распакованный архив собирается без Node и отвечает то же, что требует блок test do.

Насколько это самоприменение

Неподвижная точка сошлась — и вместе с ней ушла формулировка «строго говоря, пока нет», стоявшая здесь в первой редакции, и «пока не сошлась» из второй.

Что можно сказать без натяжки. На flang написаны лексер языка flang, парсер, проверка типов, анализ завершаемости, печать flang в C и связывание модулей — шесть слоёв, 1269 функций после связывания. Каждый доказан не тем, что «работает», а побайтовым совпадением с существующей реализацией на всём, что лежит в репозитории, включая их собственные исходники. Компилятор, напечатанный эталоном, печатает собственные исходники, и результат совпадает побайтово с третьим проходом — все семь файлов.

Чего это не значит, тоже стоит сказать, потому что здесь легко округлить в свою пользу.

• Эталон на JavaScript остаётся и никуда не денется: относительно него проверяется неподвижная точка, и его удаление сделало бы проверку невозможной. Самоприменение эталон не отменяет — оно им живёт.
• Нативный компилятор печатает только в C. Семь остальных бэкендов на flang не переписаны и переписываться не собираются: для снятия зависимости от Node хватило одного.
• Интерпретатор (interpret.mjs) на flang не переписан и для bootstrap не нужен — «чтобы получить нативный компилятор, достаточно печати в C», — но команды run, test и facts из этого следует, что останутся на Node дольше всех.

И одно наблюдение напоследок — не про flang, а про то, как читать такие проекты. Всё, что здесь сработало, сработало по одному правилу: утверждение о поведении проверяется совпадением с другой реализацией, а не собственным тестом. Ядро FTS сверялось с ядром на TypeScript. Каждый слой компилятора — со своим эталоном на JavaScript. Дефект в печати в C нашла вторая печать; дефект в проверке типов нашёл фаззинг; квадратичную память в арене показал замер. Ни одну из этих находок не дал бы набор тестов, написанный тем же человеком, который писал код.

Дальше — глава «Чего в языке пока нет»: проверенный перечень недостающего, в котором «символы строки» из этой главы занимают первое место по цене.