Что такое * концептуально * наименьший * компилятор *, который может скомпилировать себя?

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

Что представляет собой концептуально самый маленький компилятор, который может скомпилировать свой собственный код?

Когда я говорю "концептуально наименьший", я имею в виду, что он использует только очень простые понятия и строит оттуда, а не содержит очень короткий код. Примером того, почему это важное различие, является OTCC очень крошечный компилятор C, который является небольшим, потому что он запутывается, не обязательно потому, что он концептуально простой (он также может быть концептуально простым, но я не знаю, он запутан).

Я также хотел бы добавить, что следующая также может быть очень концептуально маленькой программой, но она на самом деле ничего не говорит нам о том, что происходит, поэтому на самом деле это не то, что я ищу:

(writefile argv[2] (generate (parse (readfile argv[1]))))

То, что я действительно ищу, - это язык, который:

Тьюринг завершен.
Возможность компиляции.

Мне это интересно, потому что

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

Если он не существует, я могу просто написать его сам.:)

Ответ 1

Я не совсем понимаю, что вы подразумеваете под "концептуально наименьшим". Предположительно вас не интересует минимальные машины Тьюринга или представления в Lambda calculus? Если вы говорите о реализации физических компиляторов, то вы действительно говорите о компиляторе, который генерирует инструкции машинного кода. TCC, как упоминается комментарий Энтони Миллса, имеет значение. Еще одно интересное обсуждение, которое должно иметь практическое применение, - это подробное описание назад в группе новостей comp.compilers, которая стоит проверить.

Ответ 2

Вы не говорите, что такое целевая машина, или должен существовать или просто компилятор.

В мире воображения я бы сказал, что адаптация метациркулярного переводчика LISP Джона Маккарти придет довольно близко. Вы также можете посмотреть на статью Джона Рейнольда "Толкования определения" для языков более высокого порядка, хотя плотная модель простоты.

В мире реальности я бы поставил на Chez Scheme, но, к сожалению, компилятор собственного кода является запатентованным и закрытым источником. Тем не менее, вы можете научиться изучать переводчика. Еще одна система, заслуживающая изучения, - это компилятор Oberon, который был разработан для того, чтобы быть построенным и понятным одним человеком, и он очень чистый.

Ответ 3

[Я знаю, что это очень поздняя запись, но я думаю, что это действительно актуально].

Самый маленький компилятор компиляции, о котором я знаю, Val Schorre 1963 MetaII компилятор. Да, из девятнадцатой Шестьдесят Три. (На этой странице есть ссылка на его технический документ по этой теме). Если вам нравятся компиляторы, запустите эту бумагу; его газ и его только 10 страниц.

Это не теория; это практично. В его статье представлен исходный код компилятора (около 20-30 строк IIRC), описание метакомпиляционных машин и метакомпилированная программа обрабатывает исходный код и восстанавливает ту же самую метакомпилированную программу. Вы можете реплицировать этот результат самостоятельно в течение 1-2 дней, чтобы действительно забавно, если бы не ошеломительный код для реализации метамашины. [Я научился создавать компиляторы из этой статьи еще в 1970 году, делая именно это]. Или вы можете поиграть с современным учебным пособием по MetaII, в котором все готово в JavaScript.

Как только вы запускаете этот метакомпилятор, вы можете легко расширить синтаксис и метамашину для загрузки в более крупные метакомпиляторы с большим количеством функций и/или генерировать компиляторы для реальных приложений. (Таким образом, в начале 70-х я построил Pascal как BASIC-компилятор).

Вы можете пойти в другую сторону: вы можете начать разбирать вещи и посмотреть, сколько вы можете удалить и все еще сможете повысить уровень поддержки до уровня MetaII. Я сделал это один раз и сумел избавиться от около 30%, не теряя возможности или даже выразительности; он упал до 20 строк текста и, что примечательно, более простая мета-машина.

Умный товарищ по имени Дуг Михельс, связанный давным-давно с 80-х годов (поставщик Unix) Санта-Круз, сказал мне, что он значительно продвинулся и уменьшил самоописание метакомпилятора до очень небольшого числа персонажей. Я никогда не видел работу, поэтому я не знаю, как далеко он добрался.

[EDIT] Копай, копай, копай... нашел этот камень (на Linkedin):

Билл Маккеман, адъюнкт-факультет в Дартмуте сказал:

Дуг был моим студентом; его назначение старшего тезиса было простым: напишите кратчайший, расширяемый, самокомпилирующий компилятор. На лицевой стороне было 27 символов; все это заняло 63 года. Все они вписываются в одну карту IBM. Он опубликовал результат.

Копайте, копайте, копайте еще немного: Это, кажется, бумага с символом Doug 27. См. Рисунок 2. Под "передним концом" McKeeman автоматически означает "только парсер"; бумага содержит полные переводчики, которые немного больше.

Вы не можете получить компиляторы такими маленькими, если они не являются "концептуально простыми".

Ответ 4

Фон В какой-то момент мне захотелось, чтобы небольшая программа скомпилировала некоторые редактируемые сценарии Notepad и запускала их на лету. Это хороший проект под названием "С# Script: The Missing Puzzle Piece". Но это касается профессионалов. И затем, однажды ночью я пошел, чтобы сделать некоторую кодировку. И придумал компилятор кода. Но этого было недостаточно. Я хотел сохранить исходный код для этой программы в самой программе, и окончательная спецификация заключалась в том, чтобы сгенерировать этот же исходный код из программы.

Короче:

Существует только один исполняемый файл.
При запуске исполняемого файла он генерирует собственный исходный код.
При повторном запуске исполняемого файла он компилирует этот исходный код и выполняет его, показывая тот же пользовательский интерфейс!

Хорошим тестом является удаление исполняемого файла и компиляция сгенерированного исходного кода с помощью Visual Studio или компилятора командной строки С#:

 del SelfReplication.exe
 csc SelfReplication.cs
 move SelfReplication.cs SelfReplication-old.cs
 SelfReplication.exe

Последний оператор создает файл SelfReplication.cs. Старые и новые сгенерированные файлы точно такие же! Особенностью программы является изменение (изменение) исходного кода, добавление новых функций и создание совершенно нового исполняемого файла. Новая программа сможет реплицировать себя, включая вашу мутацию, так же, как и исходную.

https://www.codeproject.com/Articles/21297/Real-Self-Replicating-Program