Начальная загрузка (компиляторы)

Процесс написания самокомпилируемого компилятора

В информатике загрузка — это метод создания самокомпилируемого компилятора , то есть компилятора (или ассемблера ), написанного на исходном языке программирования , который он собирается скомпилировать. Исходная базовая версия компилятора ( загрузочный компилятор ) создается на другом языке (это может быть ассемблер); последующие расширенные версии компилятора разрабатываются с использованием этого минимального подмножества языка. Проблему компиляции самокомпилируемого компилятора в проектировании компиляторов назвали проблемой курицы или яйца , и загрузочная загрузка является решением этой проблемы. ^{[1] [2]}

Начальная загрузка — довольно распространенная практика при создании языка программирования . Многие компиляторы для многих языков программирования загружаются, включая компиляторы для BASIC , ALGOL , C , C# , D , Pascal , PL/I , Haskell , Modula-2 , Oberon , OCaml , Common Lisp , Scheme , Go , Java , Elixir , Rust. , Python , Scala , Nim , Eiffel , TypeScript , Vala , Zig и другие.

Процесс

Типичный процесс начальной загрузки состоит из трех или четырех этапов: ^{[3] [4] [5]}

• Этап 0: подготовка среды для работы загрузочного компилятора . Здесь выбираются исходный язык и язык вывода загрузочного компилятора. В случае « голой машины » (такой, где не существует компилятора для какого-либо языка) исходный код и выходные данные записываются как двоичный машинный код или могут быть созданы путем кросс-компиляции на какой-либо другой машине, кроме целевой. В противном случае загрузочный компилятор должен быть написан на одном из языков программирования, который существует на целевой машине, и этот компилятор будет генерировать что-то, что может выполняться на целевой машине, включая язык программирования высокого уровня , язык ассемблера , объект файл или даже машинный код.
• Этап 1: создается бутстрап-компилятор. Этого компилятора достаточно, чтобы преобразовать собственный исходный код в программу, которую можно выполнить на целевой машине. На этом этапе вся дальнейшая разработка осуществляется с использованием языка, определенного загрузочным компилятором, и начинается этап 2.
• Этап 2: бутстрап-компилятор создает полный компилятор. Обычно это делается поэтапно по мере необходимости, например, компилятор для версии X языка сможет скомпилировать функции из версии X+1, но этот компилятор фактически не использует эти функции. Как только этот компилятор будет протестирован и сможет скомпилироваться сам, теперь функции версии X+1 могут использоваться в последующих выпусках компилятора.
• Этап 3: полный компилятор создается полным компилятором этапа 2. Если необходимо добавить дополнительные функции, работа возобновляется на этапе 2, при этом текущий полный компилятор этапа 3 заменяет загрузочный компилятор.

Полный компилятор собирается дважды, чтобы сравнить результаты двух этапов. Если они разные, значит, либо загрузочный файл, либо полный компилятор содержат ошибку. ^[3]

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

Начальная загрузка компилятора имеет следующие преимущества: ^[6]

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

Обратите внимание, что некоторые из этих пунктов предполагают, что среда выполнения языка также написана на том же языке.

Методы

Если нужно скомпилировать компилятор для языка X, написанный на языке X, возникает вопрос, как можно скомпилировать первый компилятор. На практике используются различные методы:

• Реализация интерпретатора или компилятора языка X на языке Y. Никлаус Вирт сообщил, что написал первый компилятор Паскаля на Фортране . ^[7]
• Другой интерпретатор или компилятор X уже написан на другом языке Y; именно так часто загружается Scheme .
• Более ранние версии компилятора были написаны на подмножестве X, для которого существовал другой компилятор; именно так загружаются некоторые надмножества Java , Haskell и исходного компилятора Free Pascal .
• Компилятор, поддерживающий нестандартные расширения языка или дополнительные языковые функции, можно написать без использования этих расширений и функций, чтобы его можно было скомпилировать с другим компилятором, поддерживающим тот же базовый язык, но с другим набором расширений и функций. Основные части компилятора C++ clang были написаны на подмножестве C++, которое может быть скомпилировано как g++ , так и Microsoft Visual C++ . Расширенные функции написаны с использованием некоторых расширений GCC.
• Компилятор для X перекрестно компилируется из другой архитектуры, где существует компилятор для X; именно так компиляторы для C обычно портируются на другие платформы. Также этот метод используется в Free Pascal после начальной загрузки.
• Написание компилятора в X; затем вручную скомпилировать его из исходного кода (скорее всего, неоптимизированным способом) и запустить его в коде, чтобы получить оптимизированный компилятор. Дональд Кнут использовал это для своей системы WEB- грамотного программирования .

Методы распространения компиляторов в исходном коде включают предоставление переносимой версии компилятора с байт-кодом , чтобы запустить процесс компиляции компилятора самостоятельно. Т -диаграмма — это обозначение , используемое для объяснения методов начальной загрузки компилятора. ^[6] В некоторых случаях наиболее удобный способ запустить сложный компилятор в системе, в которой мало или совсем нет программного обеспечения, включает в себя ряд все более сложных ассемблеров и компиляторов. ^[8]

История

Ассемблерами были первые языковые инструменты, способные самозагружаться.

Первым языком высокого уровня, обеспечившим такую ​​загрузку, был NELIAC в 1958 году. Первыми широко используемыми языками, которые сделали это, были Burroughs B5000 Algol в 1961 году и LISP в 1962 году.

Харт и Левин написали компилятор LISP в Массачусетском технологическом институте в 1962 году, протестировав его внутри существующего интерпретатора LISP. Как только они улучшили компилятор до такой степени, что он мог компилировать собственный исходный код, он стал самостоятельным. ^[9]

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

—  Памятка AI 39 ^[9]

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

Текущие усилия

Из-за проблем безопасности, связанных с атакой Trusting Trust Attack (которая включает в себя злонамеренную модификацию компилятора с целью введения скрытых бэкдоров в программы, которые он компилирует, или даже дальнейшего копирования вредоносной модификации в будущих версиях самого компилятора, создавая постоянный цикл недоверия) и различных атак. В целях обеспечения надежности двоичного кода несколько проектов работают над тем, чтобы упростить не только загрузку из исходного кода, но и позволить каждому проверить соответствие исходного кода и исполняемого файла. К ним относятся проект сборок Bootstrappable ^[10] и проект сборок Reproducible. ^[11]

Смотрите также

• Самостоятельный хостинг
• Самопереводчик
• Косвенная самомодификация
• Схема надгробия
• Метакомпилятор

Рекомендации

1. Рейнольдс, Джон Х. (декабрь 2003 г.). «Загрузка самокомпилируемого компилятора с машины X на машину Y». CCSC: Восточная конференция. Журнал компьютерных наук в колледжах . 19 (2): 175–181. Идея компилятора, написанного на языке, который он компилирует, поднимает старую загадку «курица или яйцо»: откуда взялось первое?
2. Глюк, Роберт (2012). «Загрузка генераторов компиляторов из частичных вычислителей». В Кларке, Эдмунд; Вирбицкайте Ирина; Воронков, Андрей (ред.). Перспективы системной информатики: 8-я Международная конференция памяти Андрея Ершова, PSI 2011, Новосибирск, Россия, 27 июня – 1 июля 2011 г., Переработанное избранное . Конспекты лекций по информатике. Том. 7162. Спрингер. стр. 125–141. дои : 10.1007/978-3-642-29709-0_13. Начало работы представляет собой проблему курицы и яйца, знакомую по конструкции компилятора: для начальной загрузки компилятора нужен компилятор, и загрузка генераторов компиляторов не является исключением.
3. «Установка GCC: Сборка». Проект GNU — Фонд свободного программного обеспечения (FSF) .
4. "rust-lang/rust: начальная загрузка". Гитхаб .
5. «Расширенные конфигурации сборки — документация LLVM 10» . llvm.org .
6. Патрик Д. Терри (1997). «3. Создание компилятора и начальная загрузка». Компиляторы и генераторы компиляторов: введение в C++ . Международная компьютерная пресса Thomson. ISBN 1-85032-298-8. Архивировано из оригинала 23 ноября 2009 г.
7. Вирт, Никлаус (22 февраля 2021 г.). «50 лет Паскаля». Коммуникации АКМ . Ассоциация вычислительной техники (ACM). 64 (3): 39–41. дои : 10.1145/3447525. ISSN  0001-0782. S2CID  231991096.
8. Эдмунд Гримли-Эванс (23 апреля 2003 г.). «Загрузка простого компилятора с нуля». homepage.ntlworld.com . Архивировано из оригинала 3 марта 2010 г.
9. Тим Харт и Майк Левин. «AI Memo 39-Новый компилятор» (PDF) . Архивировано из оригинала (PDF) 13 декабря 2020 г. Проверено 23 мая 2008 г.
10. «Загрузочные сборки» . bootstrapable.org .
11. «Воспроизводимые сборки — набор методов разработки программного обеспечения, которые создают независимо проверяемый путь от исходного кода к двоичному коду». reproducible-builds.org .