Что такое * концептуально * самый маленький * компилятор *, который может компилироваться сам?
В духе этого вопроса я хотел бы задать аналогичный вопрос, но не о интерпретаторах, а о компиляторах.
Что такое концептуально маленький компилятор, который может компилировать свой собственный код?
Когда я говорю "концептуально наименьший", я имею в виду, что он использует только очень базовые понятия и строится оттуда, а не содержит очень короткий код. Примером того, почему это важное различие, является OTCC - очень крошечный компилятор C, который небольшой, потому что он запутан, не обязательно потому, что он концептуально прост (он также может быть концептуально прост, но я не знаю, он запутан).
Я также хотел бы добавить, что следующее также может быть очень концептуально небольшой программой, но на самом деле она ничего не говорит нам о том, что происходит, так что это не совсем то, что я ищу:
(writefile argv[2] (generate (parse (readfile argv[1]))))
Что я действительно ищу, так это язык, который:
- Тьюринг завершен.
- Способный к компиляции.
Я заинтересован в этом, потому что
- это было бы интересным примером и
- это может быть полезно в качестве отправной точки для начальной загрузки компиляторов.
Если этого не существует, я могу написать сам.:)
5 ответов
Мне не совсем понятно, что вы подразумеваете под "концептуально наименьшим". Предположительно, вас не интересуют минимальные машины Тьюринга или представления в лямбда-исчислении? Если вы говорите о физических реализациях компилятора, то вы действительно говорите о компиляторе, который генерирует инструкции машинного кода. TCC, как отмечается в комментарии Энтони Миллса, имеет отношение к делу. Еще одно интересное обсуждение, которое должно иметь практическое применение, - это подробное описание загрузочного компилятора, написанного с нуля.
Некоторое время назад была интересная дискуссия в группе новостей comp.compilers, которую стоит проверить.
[Я знаю, что это очень поздняя запись, но я думаю, что это действительно актуально].
Наименьший из известных мне компиляторов - это MetaII-компилятор Вала Шорре 1963 года. Да, с 1963. (На этой странице есть ссылка на его технический документ по теме). Если вам нравятся компиляторы, бегите за этой статьей; это газ, и его всего 10 страниц.
Это не теория; это практично. Его статья содержит исходный код компилятора (около 20-30 строк IIRC), описание механизма метакомпиляции и метакомпилированную программу, которая обрабатывает исходный код и генерирует точно такую же метакомпилированную программу. Вы можете воспроизвести этот результат самостоятельно в течение 1-2 дней по-настоящему весело, если не возражаете ошеломляющем кодировании для реализации мета-машины. [Я научился создавать компиляторы из этой статьи еще в 1970 году, делая именно это]. Или вы можете поиграть с современным учебником по MetaII, в котором все это предварительно встроено в JavaScript.
Запустив этот метакомпилятор, вы можете легко расширить синтаксис и метамашину для загрузки на более крупные метакомпиляторы с большим количеством функций и / или для генерации компиляторов для реальных приложений. (Я построил PASCAL-подобный BASIC-компилятор таким образом в начале 70-х).
Вы можете пойти другим путем: вы можете начать убирать вещи и посмотреть, сколько вы можете удалить, и все же сможете повысить уровень до уровня MetaII. Я сделал это однажды, и мне удалось избавиться примерно от 30%, не теряя способности и даже не слишком выразительной силы; он сократился примерно до 20 строк текста и, что примечательно, стал более простой метамашиной.
Умный парень по имени Даг Михельс, давно связанный с операцией Санта-Крус в 1980-х годах (поставщик Unix), сказал мне, что он пошел значительно дальше и сократил самоописание метакомпилятора до очень небольшого числа символов. Я никогда не видел работу, поэтому я не знаю, как далеко он зашел.
[РЕДАКТИРОВАТЬ] Копать, копать, копать... нашел этот драгоценный камень (на Linkedin):
Билл Маккиман, адъюнкт-факультет в Дартмуте, сказал:
Даг был моим студентом; его главная задача была проста: написать самый короткий, расширяемый, самокомпилируемый компилятор. Внешний интерфейс занял 27 символов; все это заняло 63. Все это помещается на одной карте IBM. Он опубликовал результат.
Копай, копай, копай еще: похоже, это бумага Дуга из 27 символов. См. Рисунок 2. Под "внешним интерфейсом" McKeeman явно означает "просто синтаксический анализатор"; бумага содержит полных переводчиков, которые немного больше.
Вы не можете получить такие маленькие компиляторы, если они не "концептуально просты".
Вы не говорите, что является целевой машиной, должен ли компилятор существовать или просто воображаться.
В мире воображения я бы сказал, что адаптация метациркулярного интерпретатора LISP Джона Маккарти подошла бы довольно близко. Возможно, вы также захотите взглянуть на статью Джона Рейнольда " Определительные переводчики для языков высшего порядка", которая, хотя и плотная, является моделью простоты.
В мире реальности я бы сделал ставку на Chez Scheme, но, к сожалению, компилятор нативного кода является проприетарным и закрытым исходным кодом. Тем не менее, вы можете учиться на изучении переводчика. Еще одна система, заслуживающая изучения, - это компилятор Oberon, который был спроектирован так, чтобы его мог понять и понять один человек, и он очень чистый.
Предыстория В какой-то момент я хотел, чтобы небольшая программа компилировала некоторые отредактированные в Notepad скрипты и запускала их на лету. Есть этот замечательный проект под названием "C# Script: The Missing Puzzle Piece". Но это для профессионалов. А потом, однажды ночью я пошла заняться кодированием. И придумал компилятор кода. Но этого было недостаточно. Я хотел сохранить исходный код этой программы в самой программе, и окончательная спецификация заключалась в том, чтобы сгенерировать этот же исходный код из программы.
Короче:
- Существует только один исполняемый файл.
- При запуске исполняемого файла он генерирует собственный исходный код.
- При повторном запуске исполняемого файла он компилирует этот исходный код и выполняет его, показывая тот же пользовательский интерфейс!
Хорошим тестом является удаление исполняемого файла и компиляция сгенерированного исходного кода с помощью Visual Studio или компилятора командной строки C#:
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
Возможно, какой-то старый ответ, но я думаю, что это, вероятно, самый простой самокомпилирующийся компилятор высокого уровня. Это всего лишь один файл, один проход, нулевые зависимости и собственный компилятор, единственная цель которого как компилятора — иметь возможность компилировать себя: https://github.com/t-edson/CreaTuCompilador