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

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

Проблема курицы и яйца

См. также: Проблема курицы и яйца

Пусть создан новый язык программирования L. Пусть на языке L составлен исходный код транслятора для языка L. Как получить транслятор, способный из этого кода создать исполняемый файл?

Методы решения проблемы перечислены ниже:

• Автор языка L может вручную выполнить трансляцию исходного кода с языка L на машинный язык или на язык ассемблера. Затем можно выполнить полученный код для создания исполняемого файла компилятора. Так поступили Никлаус Вирт с учениками при создании первого компилятора для языка «Паскаль», а также Дональд Кнут при создании своей системы грамотного программирования WEB.

• Автор языка L может составить исходный код транслятора на языке, для которого уже существует транслятор. Попытку такого рода (впрочем, неудачную) предпринимал Никлаус Вирт при создании первого компилятора для языка «Паскаль» на языке «Фортран».

• То же, но автор языка L сам не составляет исходный код, а поручает эту операцию другому лицу. Такой способ часто применяется при создании трансляторов для языка Scheme.

• Первая версия компилятора может быть написана на подмножестве языка L, для которого уже существует некий другой компилятор. Таким способом были получены компиляторы для подмножества языков Java, Haskell и Free Pascal.

• Создать транслятор для новой платформы можно путём кросс-компиляции — создания исполняемого файла транслятора для новой платформы на платформе, для которой транслятор уже существует. Таким способом обычно портируются компиляторы, написанные на языках C и Free Pascal.

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

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

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

Именно этот процесс и называют раскруткой.

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

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

Достоинства метода раскрутки:

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

Недостатки

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

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

История

Ассемблер можно считать первым транслятором, который относительно просто реализуется непосредственно в машинных кодах.

Neliac — диалект языка «Алгол 58» и одноимённый компилятор, разработанные в 1958 году; первый язык высокого уровня, для которого был использован метод раскрутки.

Первыми широко используемыми языками, которые были раскручены тем же способом, стали:

• Burroughs B5000 («Алгол 60») в 1961 году;
• «Лисп» в 1962 году.

В 1962 году Тим Харт (англ. Tim Hart) и Марк Левин (Mark Levin) в Массачусетском технологическом институте написали первый компилятор «Лиспа» на языке Lisp и проверили его на уже существующем интерпретаторе языка Lisp. Они перешли на него, как только разработанный ими компилятор смог откомпилировать свой собственный исходный код.

В СССР метод раскрутки использовался для создания компиляторов РЕФАЛ, «Сигма» и «Эпсилон».

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

• «Бейсик»
• «Алгол»
• C
• C++
• C#
• CoffeeScript
• Common Lisp
• Eiffel
• F#
• Factor
• Haskell
• Go
• Java
• Mercury
• «Модула-2»
• Nemerle
• Oberon
• OCaml
• «Паскаль»
• Perl 6
• «ПЛ/1»
• Rust
• Scheme
• Scala
• Standard ML
• Urn

История

Первый компилятор для языка ML, как для самостоятельного языка (после его выделения из LCF как встроенного и интерпретируемого) был написан Лукой Карделли целиком на языке «Паскаль» (включая среду выполнения (англ. runtime)). Вскоре компилятор был переписан на диалекте «VAX ML» и получил название «Edinburgh ML». Этот компилятор служил платформой для исследования языка, постепенно приблизив ML к виду SML’90. Далее на нём был написан SML/NJ, в то время как среда исполнения была переписана на языке Си. Затем был раскручен SML/NJ, и далее на его основе раскручивались все остальные реализации языка. В настоящее время существует более десятка компиляторов и несколько интерпретаторов, в том числе с нестандартными расширениями, все из которых написаны на SML и обычно способны компилировать друг друга. Единственным исключением является неактуальный для SML инкрементальный компилятор Poplog, написанный на Lisp-подобном языке POP-11, не поддерживающий современные стандарты языка SML и его библиотеки.

• 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.
• Вирт Н. Построение компиляторов, Москва, ДМК Пресс, 2010, ISBN 978-5-94074-585-3, ISBN 0-201-40353-6

Ссылки

• http://www.compiler.su/raskrutka-kompilyatora.php