Самозагрузка все еще требует внешней поддержки

Question

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

• написание исходного компилятора на другом языке.
• ручное кодирование исходного компилятора в Assembly, что выглядит как особый случай первого

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

Answer 1

Есть ли способ написать компилятор на его собственном языке?

У вас есть , чтобы иметь некоторый существующий язык для написания вашего нового компилятора. Если вы писали новый, скажем, компилятор C ++, вы просто написали бы его на C ++ и сначала скомпилировали его с существующим компилятором , С другой стороны, если вы создавали компилятор для нового языка, назовем его Yazzleof, вам сначала нужно написать новый компилятор на другом языке. Обычно это будет другой язык программирования, но это не обязательно. Это может быть сборка или, при необходимости, машинный код.

Если бы вы собирались загрузить компилятор для Yazzleof, вы вообще изначально не написали бы компилятор для полного языка. Вместо этого вы должны написать компилятор для Yazzle-lite, наименьшего возможного подмножества Yazzleof (ну, по крайней мере, довольно маленькое подмножество). Тогда в Yazzle-lite вы бы написали компилятор для полного языка. (Очевидно, что это может происходить итеративно, а не в одном прыжке.) Поскольку Yazzle-lite является подходящим подмножеством Yazzleof, теперь у вас есть компилятор, который может компилироваться сам.

Существует действительно хорошая запись о загрузке компилятора с самого низкого возможного уровня (который на современной машине является в основном шестнадцатеричным редактором) под названием Загрузка простого компилятора из ничего, Его можно найти на https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html.

Answer 2

Объяснение, которое вы прочитали, верно. Это обсуждается в Компиляторах: принципы, методы и инструменты (Книга Дракона):

• Написать компилятор C1 для языка X на языке Y
• Используйте компилятор C1, чтобы написать компилятор C2 для языка X на языке X
• Теперь C2 является полностью самостоятельной хостинговой средой.

Answer 3

Очень интересное обсуждение этого в со-создателе Unix Кен Томпсон Премия Тьюринга лекция.

Он начинает с:

То, что я собираюсь описать, является одной из многих проблем "курицы и яйца", которые возникают, когда компиляторы пишутся на их собственном языке. Для этого я буду использовать конкретный пример из компилятора C.

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

Второй шаблон предназначен для компилятора Си. Заменяющий код - это самораспространяющаяся программа Stage I, которая вставляет оба троянских коня в компилятор. Это требует фазы обучения, как в примере Стадии II. Сначала мы скомпилируем модифицированный исходный код с помощью обычного компилятора C, чтобы получить бинарный двоичный файл. Мы устанавливаем этот двоичный файл как официальный C. Теперь мы можем удалять ошибки из исходного кода компилятора, и новый двоичный файл будет повторно вставлять ошибки всякий раз, когда он компилируется. Конечно, команда входа в систему останется ошибочной без следа в источнике нигде.

Answer 4

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

Это определение начальной загрузки:

процесс простой системы, активирующей более сложную систему, которая служит той же цели.

РЕДАКТИРОВАТЬ: статья Википедии о загрузке компилятора охватывает концепцию лучше меня.

Answer 5

Дональд Э. Кнут фактически построил WEB , написав в нем компилятор, а затем скомпилировал его вручную в сборку или машинный код.

Answer 6

Проверьте подкаст Радиотехнический эпизод 61 (2007-07-06), в котором рассматриваются внутренние компоненты компилятора GCC, а также процесс начальной загрузки GCC.

Answer 7

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

Вы можете проверить сами, прочитав оригинальную статью Маккарти, Рекурсивные функции символьных выражений и их вычисление на машине, часть I .

Answer 8

Другая альтернатива - создать машину для байт-кода для вашего языка (или использовать существующую, если ее функции не очень необычны) и написать компилятор для байт-кода, либо в байт-коде, либо на желаемом языке, используя другой промежуточный продукт - такой как инструментарий синтаксического анализатора, который выводит AST в виде XML, а затем компилирует XML в байт-код, используя XSLT (или другой язык сопоставления с образцом и представление на основе дерева). Это не устраняет зависимость от другого языка, но может означать, что большая часть работы по начальной загрузке заканчивается в конечной системе.

Answer 9

Это компьютерная версия парадокса курица-яйцо. Я не могу придумать способ не написать первоначальный компилятор на ассемблере или другом языке. Если бы это могло быть сделано, я должен был бы сделать это Лисп.

На самом деле, я думаю, что Лисп почти готов. Проверьте его запись в Википедии . Согласно статье, функция Lisp eval может быть реализована на машинном коде IBM 704 , с полным компилятором (написанным на самом Lisp), который появится в 1962 году на MIT .

Answer 10

Каждый пример начальной загрузки языка, который я могу придумать ( C , PyPy ), был сделан после того, как появился работающий компилятор. Вы должны начать с чего-то, и для повторной реализации языка необходимо сначала написать компилятор на другом языке.

Как еще это будет работать? Я не думаю, что даже концептуально возможно сделать иначе.