Компилятор, написанный на самом себе

Установка: brew install digitable-lol/tap/flang-package или curl -fsSL https://raw.githubusercontent.com/digitable-lol/flang/main/install.sh | sh. Числа в главе сняты на выпуске 0.7.29.

Компилятор flang написан на flang. Другой реализации нет: версию на JavaScript удалили 20 августа 2026 года (коммит fe8e8a37 в репозитории языка, «48 файлов, 56 072 строки»). Эта глава о том, как такой компилятор собирается, чем проверяется и что это дало тому, кто язык просто ставит.

Что написано на flang

Исходники компилятора лежат в flang/self/: 60 файлов плюс 4 в flang/self/bootstrap/, 129 458 строк. Там лексер, разбор, проверка типов, анализ завершения, ядро доказательств, интерпретатор, связывание модулей, генерация кода на всех десяти целевых языках, оболочка, языковой сервер. Объявленных функций 11 183, из них тотальных 8520: компилятору тотальность не обязательна (глава «Два класса программ»).

Рядом лежит flang/core/ — разбор старых моделей .fts (глава «Старые модели»): лексер, разбор, вычислитель и вывод JSON, 300 функций, и все с доказанным завершением. Этот слой отвечает факт-чекеру, поэтому зависнуть не вправе. Проверяется он как любая программа:

$ flang check flang/core/parser.flang
модуль «Парсер FTS»: функций 280, из них с доказанным завершением 280; типов 75; файлов вместе с импортами 3
flang/core/parser.flang: проверено — разбор, типы, завершаемость, ядро и примеры; замечаний нет

280, а не 208 объявленных в файле: после связывания к разбору прибавляются функции лексера и вывода JSON, которые он подключает.

Как разрывается круг

Чтобы собрать компилятор flang, нужен компилятор flang. Круг разрывается так: в каталоге bootstrap/ лежит закоммиченный C99 — тот же компилятор, заранее переведённый в C. Это девять файлов, самый большой из них compiler_flang.c — 47 МБ. Из них одним make собирается двоичный компилятор, и больше ничего не нужно: ни сети, ни другого компилятора flang, ни какого-либо языка сверх cc.

$ make -C bootstrap -j8 CFLAGS='-std=c99 -O1'
cc -std=c99 -O1   -c -o flang_runtime.o flang_runtime.c
cc -std=c99 -O1   -c -o compiler_flang.o compiler_flang.c
…
$ bootstrap/flang --version
flang 0.7.29
$ ldd bootstrap/flang
	libm.so.6 => /usr/lib/x86_64-linux-gnu/libm.so.6
	libc.so.6 => /usr/lib/x86_64-linux-gnu/libc.so.6

У нас сборка заняла 4 мин 37 с и до 2,3 ГБ памяти: почти всё время уходит на один файл compiler_flang.c, поэтому -j мало помогает. С флагами по умолчанию (-O2 -flto) README обещает около шести минут.

Дальше круг замыкается проверкой. Собранный компилятор (назовём его flang₁) переводит в C собственные исходники из flang/self/; из этого C собирается flang₂; и C, выданный flang₂, обязан совпасть с закоммиченным байт в байт. Совпали — компилятор, собранный собой, выдаёт себя без изменений, то есть понимает язык так же, как исходники, из которых собран. Не совпали — видно, в каком файле и на каком байте.

Делает это sh scripts/bootstrap-reprint.sh --check. Проверка долгая — часы, — поэтому в CI она идёт раз в неделю (.github/workflows/reprint.yml), а на каждом пуше (.github/workflows/binary.yml) работает быстрая сверка за секунды: те ли файлы исходников вошли в закоммиченный C, или их правили после перевода. Подробно — в docs/guide/bootstrap-circle.ru.md репозитория.

Чего круг не доказывает

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

Против этого есть две вещи. Таблицы ответов в flang/test/fixtures/ ловят регресс: «вчера отвечал так, сегодня иначе». А доказательства ядра перепроверяют независимые программы — о них следующий раздел.

Кто проверяет доказательства

flang check --proof не только выводит доказательства, но и умеет записать их в файл (--record). Такую запись читают и перепроверяют две программы, написанные отдельно от компилятора:

• flang/proof/checker/checker.c — проверка на C, собирается make -C flang/proof/checker;
• flang/proof/checker/second/ — вторая проверка на Lean 4, собирается make -C flang/proof/checker second и требует версии Lean из flang/proof/lean/lean-toolchain (v4.34.0; на 4.35 у нас сборка остановилась ошибкой deep recursion detected).

Обе идут в CI на каждом пуше (.github/workflows/binary.yml), и расхождение между ними — ошибка, а не повод подогнать одну под другую. Отчёт --proof говорит, сколько доказанного программа проверки сумела повторить, а сколько осталось только на слове ядра:

$ FLANG_CHECKER=flang/proof/checker/сверщик flang check --proof flang/proof/examples/corpus-factorial.flang
…: независимо, сверщиком, проиграно 1 из 1 доказанных; на слове ядра 0 — код сверщика 0

В готовой сборке v0.7.29 программы проверки нет, и --proof об этом говорит: «НЕЗАВИСИМО НЕ ПРОВЕРЕНО — сверщика нет … все N доказанных стоят на слове ядра». Чтобы получить перепроверку, нужно собрать её из клона и указать путь в FLANG_CHECKER.

Память без сборщика мусора

Один инженерный сюжет стоит рассказать отдельно: он общий для любого рантайма без сборщика мусора.

Значения программы на flang в C-рантайме живут в арене: она ничего не освобождает до конца вызова. Программа на flang — чистое вычисление, поэтому это честно: всё, что она построила, живёт ровно столько же, сколько вызов. Но отсюда следует ловушка. Если добавить каждый раз выделяет новый массив на n+1 элементов и копирует старый, то список из n элементов, собранный n вызовами добавить, оставляет около 16·n² байт, которые никто не соберёт. Под сборщиком мусора этого не видно — промежуточные копии умирают сразу.

Лечится это без отказа от неизменяемости — запасом ёмкости. У массива с запасом есть общая запись fl_grow, и в ней filled — сколько ячеек уже занято; число только растёт. Занять следующую ячейку может только тот, у кого длина списка равна filled. Значит, ячейка за концом списка пишется не больше одного раза, а второе добавить к тому же значению видит, что ячейка занята, и копирует. пусть а равно (добавить 1 к с) и пусть б равно (добавить 2 к с) дают два независимых списка и не портят с (flang/src/emit/c/flang_runtime.c).

Проверить можно на программе в восемь строк:

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

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

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

$ flang emit fill.flang --target c --out fc && make -C fc
$ printf '{"fn":"Размер","args":[{"n":"200000"}]}\n' | /usr/bin/time -v fc/flang_cli --json
{"ok":true,"value":{"n":"200000"}}
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.01
	Maximum resident set size (kbytes): 14336

Двести тысяч добавить — 14 МБ памяти. Без запаса только мусор от копий занял бы порядка 16·200 000² байт, то есть около 640 ГБ.

Что это дало установке

Раз компилятор написан на flang и переводится в C, выпуск везёт готовый двоичный файл без зависимостей. Сборка v0.7.29 для Linux x86-64 — статический исполняемый файл на 32 МБ (file отвечает statically linked), а рядом в share/flang/ лежат стандартная библиотека и рантаймы всех десяти целей. Путей установки несколько, и ни одному не нужны ни Node, ни компилятор C:

curl -fsSL https://raw.githubusercontent.com/digitable-lol/flang/main/install.sh | sh
brew install digitable-lol/tap/flang-package
asdf install flang latest
sudo apt install ./flang-package_0.7.29_amd64.deb

install.sh сверяет архив с SHA256SUMS выпуска. Тому, кто хочет собрать сам, по-прежнему хватает cc и make: make -C bootstrap и make -C bootstrap install PREFIX=$HOME/.local.

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

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

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

Дальше — глава «Чего в языке пока нет».