Начальная загрузка (компиляторы) - Bootstrapping (compilers)
В Информатика, самонастройка это техника для создания самокомпилирующийся компилятор - это компилятор (или же ассемблер ) написано в источнике язык программирования что он намеревается скомпилировать. Первоначальная базовая версия компилятора ( компилятор начальной загрузки) создается на другом языке (который может быть языком ассемблера); последующие расширенные версии компилятора разрабатываются с использованием этого минимального подмножества языка. Проблема компиляции самокомпилируемого компилятора получила название проблема с курицей или яйцом в конструкции компилятора, и самозагрузка является решением этой проблемы.[1][2]
Многие компиляторы для многих языков программирования загружаются, включая компиляторы для БАЗОВЫЙ, АЛГОЛ, C, C #, D, Паскаль, PL / I, Фактор, Haskell, Модула-2, Оберон, OCaml, Common Lisp, Схема, Идти, Ява, Эликсир, Ржавчина, Python, Scala, Ним, Эйфель, и больше.
Процесс
Типичный процесс начальной загрузки состоит из трех или четырех этапов:[3][4][5]
- Этап 0: подготовка среды для компилятор начальной загрузки работать с.
- Этап 1: создается компилятор начальной загрузки.
- Этап 2: компилятор начальной загрузки создает полный компилятор.
- Этап 3: полный компилятор создается полным компилятором этапа 2.
Полный компилятор создается дважды для сравнения результатов двух этапов. Если они разные, значит, либо в начальной загрузке, либо в полном компиляторе есть ошибка.[3]
Преимущества
Начальная загрузка компилятора имеет следующие преимущества:[6][7]
- это нетривиальный тест компилируемого языка, и как таковой является формой собачье кормление.
- разработчикам компиляторов и сообщениям об ошибках необходимо знать только компилируемый язык.
- Разработка компилятора может выполняться на компилируемом языке более высокого уровня.
- улучшения в серверной части компилятора улучшают не только программы общего назначения, но и сам компилятор.
- это комплексная проверка целостности, поскольку он должен иметь возможность воспроизводить свой собственный объектный код.
Обратите внимание, что некоторые из этих пунктов предполагают, что язык время выполнения также написан на том же языке.
Методы
Если нужно скомпилировать компилятор для языка X, написанный на языке X, возникает проблема, как можно скомпилировать первый компилятор. Различные методы, которые используются на практике, включают:
- Реализация устный переводчик или же компилятор для языка X на языке Y. Никлаус Вирт сообщил, что написал первый Паскаль компилятор в Фортран.[нужна цитата ]
- Другой интерпретатор или компилятор для X уже был написан на другом языке Y; вот как Схема часто загружается.
- Более ранние версии компилятора были написаны в подмножестве X, для которого существовал какой-то другой компилятор; вот как некоторые надмножества Ява, Haskell, а начальная Free Pascal компилятор загружается.
- Компилятор, поддерживающий нестандартные языковые расширения или дополнительные языковые функции, может быть написан без использования этих расширений и функций, чтобы он мог компилироваться с другим компилятором, поддерживающим тот же базовый язык, но другой набор расширений и функций. Основные части C ++ компилятор лязгать были написаны на подмножестве C ++, которое может быть скомпилировано как g ++ и Microsoft Visual C ++. Расширенные функции написаны с использованием некоторых расширений GCC.
- Компилятор для X - кросс-скомпилированный из другой архитектуры, где существует компилятор для X; вот как компиляторы для C обычно переносятся на другие платформы. Также этот метод используется для Free Pascal после начальной загрузки.
- Написание компилятора в X; затем вручную скомпилировать его из исходного кода (скорее всего, не оптимизированным способом) и запустить его в коде, чтобы получить оптимизированный компилятор. Дональд Кнут использовал это для своего WEB грамотное программирование система.
Методы распространения компиляторов в исходном коде включают предоставление переносимого байт-код версия компилятора, чтобы бутстрап процесс компиляции компилятора с самим собой. В Т-диаграмма это обозначение используется для объяснения этих методов начальной загрузки компилятора.[7] В некоторых случаях наиболее удобный способ запустить сложный компилятор в системе, в которой мало или совсем нет программного обеспечения, включает в себя серию все более сложных ассемблеров и компиляторов.[8]
История
Ассемблеры были первыми языковыми инструментами, начавшими самостоятельную загрузку.
Первым языком высокого уровня, обеспечивающим такую загрузку, был NELIAC в 1958 году. Первыми широко используемыми языками для этого были Берроуз B5000 Алгол в 1961 г. и LISP в 1962 г.
Харт и Левин написали компилятор LISP на LISP в Массачусетском технологическом институте в 1962 году, тестируя его внутри существующего интерпретатора LISP. Как только они улучшили компилятор до такой степени, что он мог компилировать собственный исходный код, он стал самостоятельным хостингом.[9]
Компилятор в том виде, в котором он существует на стандартной ленте компилятора, представляет собой программу на машинном языке, которая была получена с помощью S-выражение Определение компилятора работает над собой через интерпретатор.
— Памятка AI 39[9]
Этот метод возможен только тогда, когда интерпретатор уже существует для того же самого языка, который должен быть скомпилирован. Он напрямую заимствует идею запуска программы на самой себе в качестве входных данных, которая также используется в различных доказательствах в теоретическая информатика, например, доказательство того, что проблема остановки неразрешима.
Текущие усилия
Из соображений безопасности относительно Доверие к доверительной атаке и различные атаки на надежность двоичных файлов, несколько проектов работают над сокращением усилий не только для начальной загрузки из исходного кода, но и для того, чтобы каждый мог проверить соответствие источника и исполняемого файла. К ним относятся проект сборки Bootstrappable[10] и проект воспроизводимых сборок.[11]
Список языков, имеющих компиляторы на собственном хостинге
Следующие языки программирования имеют компиляторы с собственным хостингом:[нужна цитата ]
- Ада
- БАЗОВЫЙ
- BASICO (пример начальной загрузки компилятора)
- BCPL
- BlitzMax
- Берроуз Алгол
- C
- C ++ (составители: Visual C ++, лязгать, наверное другие)
- C # и Visual Basic .NET через Microsoft Roslyn
- Чао
- Кобол
- CoffeeScript
- Common Lisp
- Кристалл
- Карри
- D
- Delphi
- Эйфель
- Эликсир
- F #
- FASM
- Фактор
- Четвертый
- Free Pascal
- Идти
- Haskell
- Ява
- Котлин
- LiveScript
- Меркурий
- Модула-2
- Nemerle
- Ним
- Оберон
- OCaml
- PL / I
- Паскаль
- Pyret[12]
- Python
- Раку (составители: Ракудо и Niecza являются собственными хостингами)
- Ржавчина
- Scala
- Схема
- Болтовня
- SML
- Tcl[13]
- Машинопись
- Вергилий[14]
- Umple
- XPL
Смотрите также
Рекомендации
- ^ Рейнольдс, Джон Х. (декабрь 2003 г.). "Загрузка самокомпилирующегося компилятора с машины X на машину Y". CCSC: Восточная конференция. Журнал компьютерных наук в колледжах. 19 (2): 175–181.
Идея компилятора, написанного на языке, который он компилирует, вызывает старую загадку «курица или яйцо»: откуда взялся первый?
- ^ Глюк, Роберт (2012). «Начальная загрузка генераторов компилятора из частичных оценщиков». В Кларке, Эдмунд; Вирбицкайте Ирина; Воронков, Андрей (ред.). Перспективы системной информатики: 8-я Международная конференция памяти Андрея Ершова, PSI 2011, Новосибирск, Россия, 27 июня - 1 июля 2011 г., Отредактированные избранные статьи. Конспект лекций по информатике. 7162. Springer. С. 125–141. Дои:10.1007/978-3-642-29709-0_13.
Приступая к работе, мы сталкиваемся с проблемой курицы и яйца, знакомой по созданию компиляторов: компилятор нужен для начальной загрузки компилятора, и начальная загрузка генераторов компилятора не является исключением.
- ^ а б «Установка GCC: Строительство». Проект GNU - Фонд свободного программного обеспечения (ФСПО).
- ^ "rust-lang / rust: bootstrap". GitHub.
- ^ «Расширенные конфигурации сборки - документация LLVM 10». llvm.org.
- ^ Компиляторы и генераторы компиляторов: введение в C ++. Патрик Д. Терри 1997. International Thomson Computer Press. ISBN 1-85032-298-8
- ^ а б «Построение компилятора и начальная загрузка» П.Д. Терри, 2000 г. HTML В архиве 2009-11-23 на Wayback Machine. PDF В архиве 14 декабря 2010 г. Wayback Machine.
- ^ «Загрузка простого компилятора с нуля» В архиве 3 марта 2010 г. Wayback Machine Эдмунд ГРИМЛИ ЭВАНС 2001
- ^ а б Тим Харт и Майк Левин. «AI Memo 39-Новый компилятор» (PDF). Архивировано из оригинал (PDF) на 2011-02-24. Получено 2008-05-23.
- ^ http://bootstrappable.org/
- ^ https://reproducible-builds.org/
- ^ https://www.pyret.org В архиве 2018-04-10 в Wayback Machine
- ^ «Архивная копия». В архиве из оригинала на 2017-06-04. Получено 2017-09-19.CS1 maint: заархивированная копия как заголовок (связь)
- ^ «Архивная копия». В архиве из оригинала 28.12.2014. Получено 2015-05-27.CS1 maint: заархивированная копия как заголовок (связь)