Компиляторы
Написание компилятора
Go 1.5 выпущен в 2015 году и содержал один особенный факт: компилятор Go написан на Go и компилирует сам себя. Это не просто техническое достижение - это философский момент: язык достиг точки самодостаточности. Написать компилятор который компилирует себя - это вершина компиляторной инженерии, достигнутая Go, Rust, TypeScript, GCC. Этот урок - о том как туда добраться.
- **TypeScript tsc**: компилятор TypeScript написан на TypeScript и type-checked самим собой - добавление новой фичи типизации требует что код компилятора сам использовал эту фичу корректно
- **Go bootstrap за 45 минут**: команда `GOROOT_BOOTSTRAP=/usr/local/go1.4 go build` воспроизводит весь bootstrap процесс - это регулярно запускается в CI для верификации компилятора
- **csmith differential testing**: автоматически нашёл 300+ bugs в GCC, Clang, MSVC и ICC компиляторах генерируя случайные C программы и сравнивая output - без написания ни одного теста вручную
End-to-End Компиляция
Компилятор - это pipeline: исходный код -> лексер -> токены -> парсер -> AST -> семантический анализ -> IR -> оптимизации -> кодогенерация -> машинный код. Каждый этап трансформирует представление с добавлением информации (типы, области видимости, регистры). Ошибка на любом этапе должна давать точную диагностику.
Tiny C Compiler (TCC) - однопроходный компилятор C в ~15000 строк: лексер, парсер и кодогенерация в одном проходе без AST. Компилирует в 10x быстрее GCC но код медленнее. Это иллюстрирует tradeoff: separation of concerns (несколько проходов) vs скорость компиляции (один проход).
Почему большинство современных компиляторов используют несколько проходов (multi-pass) вместо одного?
Language Design Decisions
Решения при проектировании языка определяют сложность компилятора. Static vs dynamic typing: статика даёт лучший codegen и IDE support, динамика - гибкость. Garbage collected vs manual: GC проще для пользователя, manual даёт предсказуемую latency. Whitespace-significant (Python) vs брекеты (C): влияет только на лексер. Expression-oriented vs statement-oriented влияет на AST дизайн.
Zig язык (Andrew Kelley) имеет comptime - вычисления в compile time на том же языке что и runtime. Это упрощает компилятор: один интерпретатор для обоих фаз. TypeScript type system является Turing-complete (доказано 2021) что означает что некоторые type checking задачи алгоритмически неразрешимы - компилятор добавляет глубину рекурсии как защиту.
Почему добавление generics в язык является непрямолинейной задачей для компилятора?
Тестирование компиляторов
Тестирование компилятора сложнее тестирования обычного ПО: нужно проверять корректность кодогенерации, семантику языка, edge cases в парсере, производительность на больших файлах. Подходы: unit tests для отдельных phases, snapshot tests (golden files), fuzzing, differential testing против другой реализации.
TypeScript имеет ~60,000 conformance tests. Rust test suite запускается ~30 минут на CI. GCC test suite (dejagnu) содержит 100,000+ тестов собранных за 35 лет. Fuzzing (libFuzzer + afl++) находит crashes в парсерах: в 2021 году было найдено 200+ bugs в LLVM через continuous fuzzing в OSS-Fuzz.
Что такое differential testing для компиляторов?
Bootstrapping: компилятор компилирует себя
Bootstrapping - процесс написания компилятора на том же языке который он компилирует. Начало: написать компилятор языка X на языке Y (обычно C). Потом переписать его на X. Собрать с помощью компилятора на Y. Потом собрать себя собственным компилятором. Rust, Go, GCC, TypeScript - все bootstrapped.
TypeScript компилятор (tsc) написан на TypeScript и компилируется tsc. Это означает что исходный код TypeScript компилятора - это валидный TypeScript код который проходит type checking. Когда TypeScript добавляет новые фичи типизации - сначала пишут на JavaScript, потом мигрируют на новую TypeScript фичу. GHC (Haskell compiler) - один из самых сложных bootstrapped компиляторов: компилируется 40+ минут.
Bootstrapping невозможен без другого языка - нужен 'первый' компилятор на ассемблере
Bootstrapping требует лишь начальной точки: первый компилятор может быть минимальным интерпретатором, или написанным на другом языке. Дальше компилятор расширяет себя сам
Go 1.0 был написан на C - это была начальная точка. Go 1.5 заменил C реализацию Go реализацией, скомпилированной Go 1.4. Rust был написан на OCaml (rustboot) до первого Rust-on-Rust bootstrap. История языков - это всегда цепочка bootstrap шагов
Что такое 'stage2' в процессе bootstrapping Rust?
Итоги
- Компилятор = pipeline из независимых фаз: лексер->парсер->semantic->IR->оптимизации->codegen; каждая фаза добавляет информацию
- Language design decisions (типизация, evaluation strategy, generics) напрямую определяют сложность каждой фазы компилятора
- Bootstrapping: компилятор компилирует себя; stage2 check верифицирует корректность кодогенерации через идемпотентность
Связанные темы
Компилятор объединяет все компиляторные концепции:
- Написание интерпретатора — Интерпретатор - более простой первый шаг; компилятор добавляет кодогенерацию
- LLVM инфраструктура — Большинство современных языков (Rust, Swift, Julia) используют LLVM как backend компилятора
- Тестирование компиляторов — Компилятор требует специфических методологий тестирования: fuzzing, differential testing, conformance tests
Вопросы для размышления
- Труда атака (Ken Thompson, 1984) показывает что bootstrapped компилятор может содержать backdoor невидимый в исходном коде. Как reproducible builds помогают защититься от этого?
- TypeScript добавляет новые фичи типизации в tsc написанный на TypeScript. Как команда разрабатывает фичу до того как компилятор её поддерживает?
- Rust stage2 проверяет что два прохода дают идентичный binary. Что может вызвать расхождение в stage2 и что это означает о корректности компилятора?