Самозагрузка (компиляторы)

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

Bootstrapping — довольно распространённая практика при создании языка программирования . Многие компиляторы для многих языков программирования являются bootstrap-компиляторами, включая компиляторы для 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: подготовка среды для работы компилятора bootstrap . Здесь выбираются исходный язык и выходной язык компилятора bootstrap. В случае « голой машины » (та, которая не имеет компилятора для какого-либо языка) исходный и выходной код записываются как двоичный машинный код или могут быть созданы путем кросс-компиляции на какой-либо другой машине, отличной от целевой. В противном случае компилятор bootstrap должен быть написан на одном из языков программирования, который существует на целевой машине, и этот компилятор сгенерирует что-то, что может быть выполнено на целевой машине, включая язык программирования высокого уровня , язык ассемблера , объектный файл или даже машинный код.
Этап 1: создается компилятор bootstrap. Этого компилятора достаточно, чтобы перевести свой собственный исходный код в программу, которая может быть выполнена на целевой машине. На этом этапе вся дальнейшая разработка выполняется с использованием языка, определенного компилятором bootstrap, и начинается этап 2.
Этап 2: полный компилятор создается компилятором bootstrap. Обычно это делается поэтапно по мере необходимости, например, компилятор для версии X языка сможет компилировать функции из версии X+1, но этот компилятор фактически не использует эти функции. После того, как этот компилятор будет протестирован и сможет компилировать себя сам, функции версии X+1 могут использоваться последующими выпусками компилятора.
Этап 3: полный компилятор создается полным компилятором этапа 2. Если необходимо добавить больше функций, работа возобновляется на этапе 2, при этом текущий полный компилятор этапа 3 заменяет компилятор bootstrap.

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

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

Самонастройка компилятора имеет следующие преимущества: ^[6]

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

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

Методы

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

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

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

История

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

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

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

Компилятор, существующий на стандартной ленте компилятора, представляет собой программу на машинном языке, которая была получена путем обработки определения S-выражения компилятора над собой через интерпретатор.
— Записка ИИ 39 ^[9]

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

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

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

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

Ссылки

^ Рейнольдс, Джон Х. (декабрь 2003 г.). «Загрузка самокомпилирующегося компилятора с машины X на машину Y». CCSC: Восточная конференция. Журнал вычислительных наук в колледжах . 19 (2): 175–181. Идея компилятора, написанного на языке, который он компилирует, поднимает старую головоломку «курица или яйцо»: откуда берется первое?
^ Glück, Robert (2012). "Bootstrapping compiler generators from partial evaluators". В Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei (ред.). Perspectives of Systems Informatics: 8th International Andreas Ershov Memorial Conference, PSI 2011, Новосибирск, Россия, 27 июня – 1 июля 2011 г., Revised Selected Papers . Lecture Notes in Computer Science. Vol. 7162. Springer. pp. 125–141. doi :10.1007/978-3-642-29709-0_13. ISBN 978-3-642-29708-3. Приступая к работе, мы сталкиваемся с проблемой «курица или яйцо», знакомой по построению компилятора: для начальной загрузки компилятора нужен компилятор, и начальная загрузка генераторов компиляторов не является исключением.
^ ab "Установка GCC: Сборка". Проект GNU - Фонд свободного программного обеспечения (FSF) .
^ "rust-lang/rust: bootstrap". GitHub .
^ «Расширенные конфигурации сборки — документация LLVM 10». llvm.org .
^ ab Patrick D. Terry (1997). "3. Compiler Construction and Bootstrapping". Компиляторы и генераторы компиляторов: Введение в C++ . International Thomson Computer Press. ISBN 1-85032-298-8. Архивировано из оригинала 2009-11-23.
^ Вирт, Никлаус (2021-02-22). «50 лет Паскалю». Сообщения ACM . 64 (3). Ассоциация вычислительной техники (ACM): 39–41. doi :10.1145/3447525. ISSN 0001-0782. S2CID 231991096.
^ Эдмунд Гримли-Эванс (2003-04-23). "Bootstrapping a simple compiler from nothing" (Создание простого компилятора из ничего). homepage.ntlworld.com . Архивировано из оригинала 2010-03-03.
^ ab Тим Харт и Майк Левин. "AI Memo 39-The new compiler" (PDF) . Архивировано из оригинала (PDF) 2020-12-13 . Получено 2008-05-23 .
^ "Сборки с возможностью самозагрузки". bootstrapable.org .
^ «Воспроизводимые сборки — набор методов разработки программного обеспечения, которые создают независимо проверяемый путь от исходного кода до двоичного кода». reproducible-builds.org .