Раскрутка компилятора

Раскрутка компилятора (англ. bootstrapping) — это такой способ создания компилятора для некоего языка программирования, когда компилятор пишется именно на целевом языке. Раскрутка также используется для переноса компиляторов на новые платформы. Основные идеи раскрутки появились в середине 1950-х годов. Применение этой техники позволяет создать компилятор, который компилирует сам себя. Метод раскрутки применялся для создания компиляторов многих языков программирования, включая компиляторы BASIC, Алгол, Си, Паскаль, ПЛ/1, Factor, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Scheme, Java, Python, Scala, Nemerle и многих других.

Что вперёд: курица или яйцо

Если Вам нужен в компилятор для языка X, чтобы получить компилятор для языка X (который написан на языке X), то как написать первый компилятор? Решение проблемы курицы и яйца возможно следующими методами:

• Создать интерпретатор или компилятор для языка X на языке Y. Никлаус Вирт написал первый компилятор Паскаля на Фортране.
• Этот интерпретатор или компилятор для полной версии языка X уже может быть написан на языке Y кем-то другим; такая раскрутка часто применяется для языка Scheme.
• Первая версия компилятора может быть написана на подмножестве языка X, для которого уже существует некий другой компилятор; таким способом были раскручены некоторые подмножества Java, Haskell и Free Pascal.
• Для создания компилятора языка X можно провести кросс-компиляцию на другой платформе, на которой уже существует компилятор для X; таким способом обычно портируются компиляторы, написанные на Си. Такой же способ используется для Free Pascal после начальной раскрутки.
• Написание компилятора на языке X; затем компилирование вручную из исходного кода (вероятно всего, без оптимизации) и выполнение полученного кода для получения оптимизированного компилятора. Дональд Кнут использовал этот метод для своей системы грамотного программирования WEB.

Раскрутка компилятора с использованием компилятора существующего языка

Создание компилятора языка L методом раскрутки подразумевает последовательность некоторых шагов.

1. На первом шаге из языка L выделяется подмножество L₀, которое не требует больших усилий для реализации, но является достаточным для написания компилятора самого себя. Затем, используя какой-либо существующий для этой платформы язык (например, C) программируется компилятор L₀—С.
2. Затем на языке L₀ пишется компилятор самого языка L₀, то есть L₀—L₀, который можно скомпилировать с помощью компилятора, полученного на первом шаге. После этого у программиста имеется компилятор L₀, способный обработать свой исходный код.
3. Далее начинается постепенное расширение L₀ до L: добавляется какая-либо ранее не реализованная возможность языка L, после чего предыдущей версией компилируется новая, а вновь добавленную возможность можно использовать в компиляторе для последующего расширения языка. Именно этот процесс и называют раскруткой.

Этапы раскрутки можно сократить: после написания компилятора L₀—С можно сразу писать компилятор L—L₀.

Преимущества

У создания компиляторов методом раскрутки есть следующие преимущества:

• это - нетривиальная проверка языка, для которого делается компилятор;
• порою разработчику достаточно знать только этот язык;
• дальнейшие улучшения компилятора можно делать на языке высокого уровня;
• улучшение сгенерированного компилятором кода улучшает не только код программ вообще, но и код самого компилятора;
• это - всесторонняя проверка компилятора на непротиворечивость, поскольку он должен быть в состоянии воспроизвести свой собственный код.

Недостатки

В случае создания новых языков программирования использование уже существующих языков может быть вполне оправданным по следующим причинам :

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

История

Первыми языковыми инструментами, которые откомпилировали сами себя методом раскрутки, были ассемблеры. Первый язык высокого уровня, для которого был использован метод раскрутки, был Neliac в 1958 г. Первыми широко используемыми языками, которые были раскручены тем же способом, были Burroughs B5000 [1] Алгол в 1961 г. и Lisp в 1962 г. Харт и Левин написали компилятор Lisp на Lisp в Массачусетском технологическом институте в 1962 г., проверяя его на уже существующем интерпретаторе Lisp. Они перешли на него, как только разработанный ими компилятор мог откомпилировать свой собственный исходный код. Компиляторами, созданными в СССР и использовавшими технику раскрутки, были РЕФАЛ, Сигма и Эпсилон.

Список языков, имеющих самокомпилирующиеся компиляторы

• BASIC
• Алгол
• Си
• C++
• Common Lisp
• Eiffel
• F Sharp
• Factor
• Haskell
• Java
• Mercury
• Modula-2
• Nemerle
• Oberon
• OCaml
• Паскаль
• Perl 6
• ПЛ/1
• Python
• Rust
• Scheme
• Scala
• TypeScript
• XPL
• РЕФАЛ
• Сигма
• Эпсилон

Литература

• Альфред Ахо, Рави Сети, Джеффри Ульман. Раскрутка // Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — М.: Вильямс, 2003. — С. 681—684. — 768 с. — ISBN 5-8459-0189-8.
• С. З. Свердлов. Самокомпилятор. Раскрутка // Языки программирования и методы трансляции. — СПб.: Питер, 2007. — С. 427—431. — 638 с. — ISBN 5-469-00378-7.