Каким должен быть язык программирования?	Анализ и критика	Описание языка	Компилятор
Отечественные разработки	Cтатьи на компьютерные темы	Компьютерный юмор	Новости и прочее

Раскрутка компилятора

Можно ли написать компилятор совершенно нового языка программирования, используя только этот язык?
Раскрутка компилятора
Когда-то такая проблема не казалась высосанной из пальца. Когда появились первые компьютеры, для них не было написано ни одной программы и, естественно, для них не существовало компиляторов. Код программ вводился с пульта управления руками. Первым компилируемым языком стал язык ассемблера, и он был набран в кодах с пульта управления. И только потом появилась возможность переписать этот компилятор языка аcсемблера на языке ассемблера.

Создание компилятора для языка «икс» на языке «икс» — это и есть метод раскрутки. При знакомстве с идеей написания компилятора на целевом языке программирования у многих возникает недоумение: «А как такое возможно?». Как барон Мюнхаузен может вытащить сам себя из болота за волосы? Это очень красивая идея, типа вечного двигателя, но чем может быть полезен такой подход?

Преимущества метода раскрутки

Авторитетные источники (в терминах Википедии) описывают их так:

это — нетривиальная проверка языка, для которого делается компилятор. Действительно, это основательная проверка языка на непротиворечивость его концепций.
разработчику достаточно знать только этот язык. На самом деле, это верно не для всех способов воплощения.
дальнейшие улучшения компилятора можно делать на языке высокого уровня. Но языки Си, Паскаль, Оберон (нужное подчеркнуть) тоже неплохи, и компиляторов для них масса.
улучшение сгенерированного компилятором кода улучшает не только код программ вообще, но и код самого компилятора. Компиляторы Си уже хорошо оптимизированы, и код, ими генерируемый, тоже неплох.
это — всесторонняя проверка компилятора на непротиворечивость, поскольку он должен быть в состоянии воспроизвести свой собственный код. С этим трудно поспорить. Если компилятор, имеющий один размер исполняемого кода, выдаст при собственной компиляции другой размер кода, то тут есть повод призадуматься. И вообще, хорошо сравнивать код на этапе N и на этапе N + 1.

Реализация раскрутки компилятора

Опустим те способы, которые к нам не имеют отношения. Мы ведь придумываем новый язык программирования. Поэтому совет «воспользуйся компилятором для этого языка, уже написанный кем-то» нам не подходит. И так, способы:

Написать компилятор, а первую компиляцию в код произвести вручную. Далее имеешь готовый компилятор . У первопроходцев не было иного способа, они сделали именно так, «из ничего». Но насколько он практичен? Компилятор — всё-таки сложная вещь, и написать несколько тысяч строк кода, не допустив ни единой ошибки, а потом без единой ошибки вручную откомпилировать — это научный подвиг. Но поскольку ошибок избежать вряд ли удастся, ручную компиляцию придётся неоднократно повторять. Нет, обычно герои идут в обход.
Написать первый компилятор на другом языке программирования. Написать не для всего языка, а лишь для некого подмножества. Так проще. Это подмножество должно охватывать те части языка, которые достаточны для написания компилятора. Затем, используя первый компилятор, можно писать компилятор на подмножестве своего языка. И пошагово двигаясь, приходим от минимального подмножества к полной версии. Количество этапов можно свести к одному.

Метод раскрутки использовался при создании многих языков, но первый раз — для разработки языка ассемблера. Перечень языков и компиляторов к ним, разработанных таким способом, есть в в английской Википедии. К этому перечню можно добавить реализации языков Эпсилон, Сигма и Рефал в советскую эпоху. Из современности можно вспомнить одну из версий компилятора языка Context авторства Андрея Хохлова, которая так же была написана на самом языке. Утилита транслитерации русского C/C++ в стандартный тоже была написана методом раскрутки: первый версия была написана на обычном Си, остальные — на русифицированном Си.

Теперь следующий вопрос. Можно ли применять сторонние инструменты типа YACC и LEX при разработке методом раскрутки? Можно, но только на первом этапе, когда пишется первая версия компилятора на стороннем языке. Генератор синтаксических анализаторов YACC выдаёт код на Си, bison — для Си, С++ и Java, ANTLR — для C++, Java, C#, Python, Ruby. Но нет такого генератора парсеров, который бы выдавал код для ещё неизвестного языка программирования!

Недостатки метода раскрутки и причины его не использовать:

При создании новых языков программирования отказ от метода раскрутки и использование уже существующих языков может быть обоснован по следующим причинам:

Компиляторы уже существующих языков надёжны. Они проверены временем. Искать ошибки в готовом компиляторе, скорее всего, не придётся.
Для них имеются IDE, отладчики и другие полезные инструменты. Для вновь создаваемого языка этих удобств нет.
Использование метода раскрутки для создания интерпретатора — не самая удачная идея. Представим схему разработки такого интерпретатора.
1. на языке Y разработан интерпретатор подмножества языка X, имеется исполняемый код;
2. на подмножестве языка X написан интерпретатор, интерпретирующий сам себя;
3. при интерпретации пользовательской программы запускается интерпретатор на языке Y (исполняемый код), который интерпретирует интерпретатор полной версии языка X, который, в свою очередь, интерпретирует пользовательскую программу на языке X
Для скриптовых языков, не претендующих на производительность, такое вполне допустимо. В остальных случаях такая схема требует доработки. Например, не полная интерпретация, а сохранение исходного кода в байт-код без повторной трансляции.
Невозможность использования генераторов синтаксических анализаторов. Это мы уже рассмотрели выше.

Опубликовано: 2013.03.18, последняя правка: 2015.01.23 03:26

Оцените	Оценки посетителей
Нравится	███████████████████████████████ 22 (73.3%)
Неплохо	███████ 5 (16.6%)
Так себе	███ 2 (6.66%)
Не нравится	██ 1 (3.33%)

Отзывы

2014/03/18 18:26, Noname #

Некторые предпочитают раскручивать язык с уровня ассемблера — много примеров Форт систем — в силу достаточной простоты самого языка, а далее на базе него уже можно создать расширение до произвольного языка (даже пройдя несколько промежуточных языков разной специализации)

2015/09/23 15:50, rst256 #

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

Источники точно авторитетные, а то данная формулировка попахивает самоприменимостью?

2015/09/24 18:35, Автор сайта #

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

2016/09/17 14:07, rst256 #

Генератор синтаксических анализаторов YACC выдаёт код на Си, bison — для Си, С++ и Java, ANTLR — для C++, Java, C#, Python, Ruby. Но нет такого генератора парсеров, который бы выдавал код для ещё неизвестного языка программирования!

А собственно в чем проблема то? Подобный сгенерированный код состоит из набора шаблонных конструкций. Главное, чтобы в новом языке нашлись для них аналоги.
Конечно, если парсер генерирует код, в котором используется ООП, это может быть проблемой, но если парсер генерирует код, например на Си, то переделать его на любой иной процедурный язык с поддержкой оператора goto не займет много времени.

2016/10/27 18:25, Автор сайта #

Делать генерацию на Си можно. Но ведь цель раскрутки — написать компилятор языка на самом языке. Как промежуточный этап — да. Но не как конечный.

2017/05/05 20:34, utkin #

это — нетривиальная проверка языка, для которого делается компилятор. Действительно, это основательная проверка языка на непротиворечивость его концепций.

Непонятно откуда это следует.

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

Враки. Если это компилятор, то, как минимум, надо знать язык той системы, куда транслируется. Если Вы для Андроида пишите компилятор Паскаля, то знать Ява просто обязаны. Второе — разработка компилятора традиционно имеет высокий порог вхождения, человеку нужно знать кучу сторонних сведений и если создается новый язык программирования, а не очередной клон С++, то знать реальный язык программирования просто необходимо.

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

Ну, можно и можно, в чем плюс то? В отсутствии примеров, документации, библиотек и фреймворков?

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

Компиляторы Си хорошо оптимизированы, потому что за ними куча времени эволюции

это — всесторонняя проверка компилятора на непротиворечивость, поскольку он должен быть в состоянии воспроизвести свой собственный код. С этим трудно поспорить. Если компилятор, имеющий один размер исполняемого кода, выдаст при собственной компиляции другой размер кода, то тут есть повод призадуматься. И вообще, хорошо сравнивать код на этапе N и на этапе N + 1.

Почему он должен воспроизводить свой собственный код? Вот совершенно необоснованное утверждение — должен. Почему? Откуда это следует?

Самый распространенный способ и не указали — трансляция в программу на другом языке программирования.

2017/05/15 11:08, Автор сайта #

Непонятно откуда это следует.

Сделать робота, который будет строить таких же роботов, весьма нетривиально. Ведь у него задача не просто сделать, а сделать безошибочно. Иначе с каждым новым поколением роботов будет накапливаться ошибка. То же самое с самокомпилирующимся компилятором.

надо знать язык той системы, куда транслируется

Да, Вы правы. Но дело не только и не столько в этом. Возможность не знать никаких других языков, кроме того, на котором пишется компилятор — это возможность нереальная и утопическая. И не имеющая какой-то ценности. Разве это плохо — знать другие языки? Да и можно ли себе представить, что человек настолько хорош в программировании, что берется за сложнейшую задачу — разработку компилятора, но при этом удосужился не знать ни одного языка программирования. Это что-то: быть асом в программировании и не знать языков программирования.

в чем плюс то? В отсутствии примеров, документации, библиотек и фреймворков?

В том, то возникает self-hosting система, самодостаточная технология, не нуждающаяся в сторонних инструментах. Путь к технологической независимости.

Почему он должен воспроизводить свой собственный код? Откуда это следует?

Потому что здесь рассматриваются не все компиляторы, а только те, которые создаются методом раскрутки. На старте применяются разные методы, но на финише разработке получается компилятор, который сам себя компилирует. Берёт свой собственный исходный код и превращает его в исполняемый.

Самый распространенный способ и не указали — трансляция в программу на другом языке программирования.

Для компиляторов, созданных методом раскрутки, самый распространённый способ — компиляция в машинный код.

2018/05/28 19:22, Александр Коновалов aka Маздайщик #

Для компиляторов, созданных методом раскрутки, самый распространённый способ — компиляция в машинный код.

По-разному. Компиляторы Рефала, написанные в СССР, компилировали в интерпретируемый код RASL (Refal assembly language). Паскаль компилировался в стековый П-код. Про Java я вообще не говорю.

Метод раскрутки ни сколько не предопределяет целевой язык.

Я разрабатываю компиляторы двух диалектов Рефала (Модульный Рефал — github.com/Mazdaywik/mrefal.git, Простой Рефал — github.com/bmstu-iu9/simple-refal.git), оба самоприменимые.

Первым был Модульный Рефал, написан на Рефале-5, компилировал в Рефал-5 (строил дерево и обратно плющил в исходный код). Потом препроцессором (уже написанным на Модульном Рефале) сконвертировал исходники Рефала-5 в Модульный Рефал.

Потом написал препроцессор Простого Рефала в Модульный Рефал и, пользуясь им, написал самоприменимый компилятор Простого Рефала в Си++.

Сейчас Модульный Рефал компилируется в Си++, а Простой Рефал (переименованный в Рефал-5λ) — в интерпретируемый код.

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

Во-первых, проще с тестированием. Если писать компилятор на другом языке, то нужны тестовые примеры, а их писать лень. Да и обычно длинные не напишешь. А самоприменимый компилятор — это уже большая нетривиальная программа на языке компилятора.
Во-вторых, практика работы с языком сама подсказывает, что надо в язык добавить. Каких не хватает библиотечных функций. Какие были бы удобны синтаксические конструкции. Какой дополнительный инструментарий нужен, в частности, средства отладки.

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

Про синтаксические анализаторы скажу вот что. Для Простого Рефала был написан (конечно, на Простом Рефале) примитивнейший генератор лексического анализатора. Конечно, можно было без него обойтись, просто мне было интересно этим заняться.

Подытоживая: раскрутка полезна прежде всего тем, что с самого рождения двигателем языка и компилятора являются не умозрительные рассуждения, а практика. Кроме того, самоприменимый компилятор вызывает доверие уже тем, что он достоверно тестировался не на примерах уровня Hello, World!, а уже может собрать нетривиальную программу.

Недостаток могу выделить один: раскрутка приучает к аскетизму. Для Модульного Рефала нет ни IDE, ни пошагового отладчика, обхожусь Vim’ом (ранее обходился Far Manager’ом), отладочной печатью и подробной трассировкой стека при падениях. Для Простого Рефала оба инструмента есть, поскольку я их посчитал хорошими темами для курсовых проектов (я преподаю курс «Конструирование компиляторов» в Бауманке) — но они пока сырые.

2018/05/30 16:53, Автор сайта #

Метод раскрутки ни сколько не предопределяет целевой язык

Вы правы. Хотя машинный код остаётся, вероятно, распространённым вариантом. Ну и проекты у Вас, конечно, интересны. А почему Рефал? Чем он Вам приглянулся?

раскрутка приучает к аскетизму

Наверное, правильнее было бы сказать «принуждает» :)

2018/05/30 18:57, Александр Коновалов aka Маздайщик #

А почему Рефал? Чем он Вам приглянулся?

Синдром гусёнка. Первый функциональный язык, с которым я познакомился. Только и всего.

раскрутка приучает к аскетизму
Наверное, правильнее было бы сказать «принуждает» :)

Сначала принуждает, а потом и приучает :-) Сейчас я уже не вижу смысла ни в IDE для Рефала, ни в пошаговом отладчике.

2024/03/17 17:15, Городняя Лидия Васильевна #

Продуктивность раскрутки зависит от выбора последовательности шагов и инструментов. Для ЯП такими шагами могут быть подъязыки, а инструментами — конструкторы частей компилятора, например, анализаторы или оптимизаторы. При удачном выборе частей ЯП и инструментов на таких шагах можно получать предварительно работоспособные версии компилятора, отлаженные программы на которых сохраняют работоспособность при переходе к очередным версиям. По достижении полной версии компилятора дальнейшие можно строить уже целостно, без раскрутки, способной дать выигрыш при реализации решений новых ЯП, а при наличии прототипа компилятора воспринимается как избыточная нагрузка. Реализация решений новых задач обычно раз в 8 превышает трудоёмкость решения сравнимых по сложности типовых задач.

2024/03/17 17:18, Городняя Лидия Васильевна #

Особо отмечу, что раскрутка не сводится к самоприменимости, хотя часто подчинена этому принципу.

Даже весьма компетентные компиляторщики предпочитают остановиться на синтаксических конструкторах, зная на своём опыте, что главным для реализации компилятора является семантика.

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

2024/03/22 18:32, void #

Но нет такого генератора парсеров, который бы выдавал код для ещё неизвестного языка программирования!

Ну да, в чистом виде парсер сам за вас писать реализацию не будет. Но! есть техники переработки, рефакторинга уже написанной реализации под другую целевую платформу. Например, есть такой вот генератор парсеров: META, META II, OMeta. META II: https://en.wikipedia.org/wiki/META_II

Развитием этой идеи является https://en.wikipedia.org/wiki/TREE-META и более современный, объектно-ориентированный https://en.wikipedia.org/wiki/OMeta на основе PEG-грамматик, задействованный в проекте FoNC/STEP, Frank, Nile/Gezira и COLA by Ian Piumatra: https://www.piumarta.com/software/cola/ см. также здесь: https://www.piumarta.com/software/

По Meta II есть такой вот курс про перенацеливаемый самоприменимый метакомпилятор: http://www.bayfronttechnologies.com/mc_tutorial.html. Можете сами попробовать реализацию в браузере на JavaScript: http://www.bayfronttechnologies.com/mc_workshop.html. Сам курс — про то, как сделать перенацеливаемый самоприменимый метакомпилятор, перенацеливая его в другой язык.

Исходная реализация META II by Dewey Val Schorr была написана в 1962-1963 на ассемблере некоторого мейнфрейма. Этот инструмент — метакомпилятор, то есть, компилятор компиляторов (наподобие Yacc/Bison, lex, ANTLR и т.п.). В отличие них — реализация написана не на поддерживающем языке вроде C, Java и т.п. А фактически на "самом себе" — в виде "синтаксических уравнений". META II был раскручен из META I и "откомпилирован вручную", буквальным подстрочным переводом. В курсе http://www.bayfronttechnologies.com/mc_tutorial.html автор этого курса James M. Neighbors показывыет, как эту устаревшую реализацию на ассемблере мейнфрейма 1960-х годов можно раскрутить серией эквивалентных преобразований (и показывает, каких именно), перенацелив в другой поддерживающий язык (например, JavaScript или Си).

После этого становится очевидно, как эту реализацию можно адаптировать ещё раз в любой другой язык, который больше нравится. Например, в Scheme: https://github.com/siraben/meta-II или в С: https://github.com/dchapiesky/MetaIIVMInC/ То есть реализация является самоприменимой. И метациклической (в духе метациклического самоприменимого метаинтерпретатора Scheme из книги "Structure And Interpretation of Computer Programs", SICP). Метаинтерпретатор — интерпретатор интерпретатора (например, самоприменимая реализация Лиспа на основе eval/apply/evlis и ещё пары функций).

Самоприменимый — написанный в основном на себе самом, обеспечивая раскрутку полного языка. Метакомпилятор — компилятор компиляторов (например, компилятор метаязыка, языка-носителя описывающего грамматики синтаксические и семантические другого языка, объектного языка). В этом смысле META II является самоприменимым метакомпилятором.

TREE-META идёт дальше: описывая лес деревьев, синтаксических. OMeta by Alessandro Warth and Ian Piumarta developed in 2007 under the Viewpoints Research Institute (в рамках проекта FoNC/STEP). Дальше:

1. Формализован метаязык PEG, Parser Expression Grammar, позволяющий описывать
рекурсивный нисходящий парсер.

2. Реализована на SmallTalk первоначальная реализация, в дальнейшем переведённая на несколько
других языков, в том числе и компилируемых.

3. Написан ряд любопытных статей, в том числе и по применению в проекте FoNC/STEP и
касающиеся ООП реализации на SmallTalk. Например, "Parsers running backwards" для автоматизации перевода из любого языка на любой другой.

Для PEG грамматик есть также несколько реализаций. Некоторые из них, например на языке D полностью работают во время компиляции (используя CTFE, Compile-Time Function Execution). Например, вот такая реализация: https://github.com/PhilippeSigaud/Pegged. Здесь в примерах https://github.com/PhilippeSigaud/Pegged/tree/master/examples есть например, компилятора Оберона или extented pascal.

Вот этот исходник https://github.com/ PhilippeSigaud/ Pegged/blob/ master/examples/ oberon2/src/ pegged/examples/ oberon2.d — это по сути описание грамматики Оберона на PEG. Далее см. скрипты сборки и тесты.

Основное тело парсера параметризируется во время компиляции и сборки нужными модулями, описывающими макросы: PEG на CTFE в D, Оберон на PEG, раскручивающимися string mixin, template mixin из языка D. Поскольку константы описаны как enum, они становятся immutable. То есть, это гарантия того что раскрутка string mixin/template mixin произойдёт через СTFE практически почти полностью во время компиляции.

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

2024/03/22 19:08, void #

Использование метода раскрутки для создания интерпретатора — не самая удачная идея. Представим схему разработки такого интерпретатора. На языке Y разработан интерпретатор подмножества языка X, имеется исполняемый код; на подмножестве языка X написан интерпретатор, интерпретирующий сам себя; при интерпретации пользовательской программы запускается интерпретатор на языке Y (исполняемый код), который интерпретирует интерпретатор полной версии языка X, который, в свою очередь, интерпретирует пользовательскую программу на языке X. Для скриптовых языков, не претендующих на производительность, такое вполне допустимо. В остальных случаях такая схема требует доработки. Например, не полная интерпретация, а сохранение исходного кода в байт-код без повторной трансляции.

Не упомянуты очевидные достоинства этого метода самораскрутки метациклического интерпретатора: наглядность, очевидность, простота и самоприменимость. "Уравнения Максвелла" в программировании: https://michaelnielsen.org /ddi/lisp-as-the-maxwells-equations-of-software/ Вот изначальная реализация: https://michaelnielsen.org/ddi/wp-content/uploads/ 2012/04/ Lisp_Maxwells_ Equations.png. Сравните это с уравнениями Максвелла теории поля: https://s0.wp.com/latex.php? latex=+%5Cnabla+%5Ccdot+B+%3D+0+%5C hspace%7B1.1cm%7D+%5C nabla+%5Ctimes+B-%5C mu_0+%5Cepsilon_0+%5Cfrac%7B%5C partial+E%7D%7B%5Cpartial+t%7D+ %3D+%5Cmu_0+j+&bg= ffffff&fg=000000&s=0 — тоже красиво.

Например, реализация метациклического интерпретатора "Лиспа на Лиспе" может быть настолько простой, что поместится в бутсектор размером менее 512 байт, а реализация "сборщика мусора" может занимать ни много не мало, а целых 10 байт. Наглядная картинка: http://justine.lol/sectorlisp2/footprint2.png, https://github.com/jart/sectorlisp, http://justine.lol/sectorlisp, http://justine.lol/sectorlisp2/

Здесь в первой ссылке смотрите демонстрацию на ютубе. Монитор/отладчик blinkenlights и даже гипервизор blinky, под которым запуск всего этого демонстрируется? написан тем же автором, Justine Tunney. Реализация написана на Си и для наглядности, на JavaScript тоже (то есть, может работать и в браузере). Реализация Scheme Ribbit: https://github.com/udem-dlteam/ribbit от Marc Feeley также довольно-таки минималистична.

Есть ряд интересных публикаций по реализации: https://github.com/udem-dlteam/ribbit#research-and-papers и статей про реализацию: https://github.com/udem-dlteam/ribbit/tree/main/docs. Написана компактная виртуальная машина, для которой запросто можно сделать несколько альтернативных реализаций на любом языке (и уже есть несколько десятков). Также там довольно неплохо проработаны механизмы интеграции с Си, встраиваимости в/из Си приложение и библиотеки, настраиваемый гигиеническими макросами Схемы со всеми их достоинствами в виде модульности механизм кодогенерации.

То есть, подобная реализация может быть также и достаточно легко расширяемой и при том эффективной — при соответствующей поддержке compiler macros. Самоприменимых метакомпиляторов Форта тоже тьма-тьмущая. А поверх Форта например можно раскрутить компилятор Паскаля в духе книги Джека Креншоу (была также вариация про реализацию не Паскаля на Паскале, а Паскаля на Форте — на мой взгляд, она стала даже более наглядной). Либо взять реализацию Смоллтока из языка Фактор (эдакий объектно-ориентированный функциональный Форт), из примеров в стандартной поставке: есть PEG описание грамматики Смоллтока, которое раскручивается в реализацию кода на Фактор.

https://factor-language.blogspot.com/2009/04/sup-dawg-we-heard-you-like-smalltalk-so.html

Реализация очень компактна и наглядна. Фактически мы получаем возможность использовать объектно-ориентированную модель Смоллтока поверх всех возможностей стандартной библиотеки языка Фактор.

2024/03/22 19:59, void #

Но нет такого генератора парсеров, который бы выдавал код для ещё неизвестного языка программирования!

Есть. Смотрите подробнее про метакомпиляторы. Помимо известного META II и потомков, вот например ещё один: https://en.wikipedia.org/wiki/Compiler-compiler#CWIC

CWIC addressed domain-specific languages before the term domain-specific language existed From the authors of CWIC:

"A metacompiler assists the task of compiler-building by automating its non creative aspects, those aspects that are the same regardless of the language which the produced compiler is to translate. This makes possible the design of languages which are appropriate to the specification of a particular problem. It reduces the cost of producing processors for such languages to a point where it becomes economically feasible to begin the solution of a problem with language design."[4]

In 1968–1970, Erwin Book, Dewey Val Schorre, and Steven J. Sherman developed CWIC.[4] (Compiler for Writing and Implementing Compilers) at System Development Corporation Charles Babbage Institute Center for the History of Information Technology (Box 12, folder 21), CWIC is a compiler development system composed of three special-purpose, domain specific, languages, each intended to permit the description of certain aspects of translation in a straight forward manner. The syntax language is used to describe the recognition of source text and the construction from it to an intermediate tree structure. The generator language is used to describe the transformation of the tree into appropriate object language.

The syntax language follows Dewey Val Schorre's previous line of metacompilers. It most resembles TREE-META having tree building operators in the syntax language. The unparse rules of TREE-META are extended to work with the object based generator language based on LISP 2.

Есть также K framework:

Why K?

The K Framework is a programming language and system design toolkit made for practioners and researchers alike. K For Practioners: K is a framework for deriving programming languages tools from their semantic specifications.

Typically, programming language tool development follows a similar pattern. After a new programming language is designed, separate teams will develop separate language tools (e.g. a compiler, interpreter, parser, symbolic execution engine, etc). Code reuse is uncommon. The end result is that for each new language, the same basic tools and patterns are re-implemented again and again.

K approaches the problem differently — it generates each of these tools from a single language specification. The work of programming language design and tool implementation are made separate concerns. The end result is that the exercise of designing new languages and their associated tooling is now reduced to developing a single language specification from which we derive our tooling for free.

K For Researchers: K is a configuration- and rewrite-based executable semantic framework.

In more detail, K specifications are:
• Executable: compile into runnable and testable programs;
• Semantic: correspond to a logical theory with a sound and relatively complete proof system;
• Configuration-based: organize system states into compositional, hierarchical, labelled units called cells;
• Rewrite-based: define system transitions using rewrite rules.

K specifications are compiled into particular matching logic theories, giving them a simple and expressive semantics. K semantic rules are implicitly defined over the entire configuration structure, but omit unused cells, enabling a highly modular definitional style. Furthermore, K has been used to develop programming languages, type systems, and formal analysis tools

На языке описания спецификаций K framework описывается семантика, задающая концепцию, поведение исполнителя некоторого языка программирования. То есть, компилятор компиляторов раскручивается из семантики, а не из синтаксиса. Пример простого языка программирования (функционального): https://kframework.org/k-distribution/pl-tutorial/ В проектах https://kframework.org/projects/ есть примеры уже готовых семантик уже известных языков, уже описанных кем-то.

Есть также возможность использовать инструменты ~~литературного~~ грамотного программирования: FunnelWeb — это инструмент для реализации WEB идей ~~литературного~~ грамотного программирования в виде weave/tangle: http://ross.net/funnelweb/ Здесь (https://github.com/loa-in-/fw-utf8) находится версия, адаптированная для Utf8. Проверил, русский язык Xelatex поддерживается отлично (с родными TTF шрифтами даже, внедряемыми в итоговый PDF).

Пользуясь этим инструментом, был разработан "компилятор компиляторов" ELI: https://eli-project.sourceforge.net/ Основная идея: разработка языка посредством серии спецификаций семантики (то есть, в духе "K framework"). Генерируется "грамотная документация", вот например, для Алгола 60: https://eli-project.sourceforge.net/a60_html/a60.html

Из кода, описывающего парсер Алгола 60 в репозитории https://sourceforge.net/p/eli-project/ALGOL60/ci/master/tree/ рецепт сборки Odinfile https://sourceforge.net/p/eli-project/ALGOL60/ci/master/tree/Odinfile описывает, как делать weave и tangle. weave делает ~~литературную~~ грамотную документацию в PDF через LaTeX из https://sourceforge.net/p/eli-project/ALGOL60/ci/master/tree/TexALGOL60.fw, либо в HTML из исходного https://sourceforge.net/p/eli-project/ALGOL60/ci/master/tree/HtmlALGOL60.fw.

Оба варианта включают основную часть: https://sourceforge.net/p/eli-project/ALGOL60/ci/master/tree/ALGOL60.fw в которой и написана ~~литературная~~ грамотная спецификация парсера Алгола 60 и его грамматики. Из этой же самой спецификации tangle собирает исходники.

Также, рекомендую посмотреть на такой весьма любопытный проект "программирования на естественном языке", как Inform 7 by Gharam Nelson для интерактивной литературы. https://en.wikipedia.org/wiki/Inform. На Гитхабе в репозиториях Грэма Нельсона https://github.com/ganelson есть проекты: inform, inweb, intest и документация.

Inform 7 раскручен из Inform 6 в духе "грамотного программирования": tangle посредством инструмента inweb, написанном на Perl из программы на "естественноязычном" Inform 7 (точнее, конечно — контролируемом плановом языке раскручивается в более низкоуровневую реализацию на Inform 6: https://bootstrapping.miraheze.org/wiki/ Bootstrapping_ Specific_ Languages#Inform_7. В 2019 году Грэм Нельсон открыл исходники Inform 7 и выложил на Гитхаб: https://ganelson.github.io/inform-website/talks/2019/06/14/narrascope.html. До того он примерно с 1995 года разрабатывал Inform 6 (исходники которого выложил в public domain) и примерно с середины 2000х — 2006 — 2024 Inform7 (исходники которого оставались закрытыми до 2018-2019 года, при полном наличии инсталляторов под все основные операционные системы). Документация есть на https://ganelson.github.io/inform-website/ и в исходниках.

Здесь наиболее интересны исходники самого компилятора https://github.com/ganelson/inform и сопутствующая ему документация, сгенерированная посредством weave: https://ganelson.github.io/inform/ Inform:The Program and the book — в духе текстового процессора TeX Дональда Эрвина Кнута, "TeX: the program and the book", который и придумал ~~литературное~~ грамотное программирование как поддерживающий его "поток сознания" инструмент, обеспечивающую метатехнологию.

2024/03/22 20:41, void #

Ещё можно упомянуть очевидное преимущество: элементарную расширяемость, встраиваемость своих собственных языков, созданных поверх базовой метациклической реализации. Например, широкоизвестный и пересказываемый как удачный анекдот "уравнения Максвелла в программировании" метациклический интерпретатор Лиспа — это 10-15 строк. Метациклический интерпретатор Пролога на Прологе — это ещё меньше: https://www.metalevel.at/acomip/

Здесь в цикле статей по языку Пролог https://www.metalevel.at/prolog Markus Triska показает ряд интересных вещей (например, макросы или парсер DCG грамматик или поиск в ограничениях). В статье https://www.metalevel.at/acomip/ он показывает, как из базовой реализации "Пролога на Прологе" можно раскрутить оптимизированные и оценить их производительность. Далее в статье https://www.metalevel.at/alzint/ он показывает реализацию интерпретатора простого примитивного языка типа Паскаля: https://www.metalevel.at/alzint/alzint.pl. Тоже раскручивая, в основном, из семантики (присваивания, циклы, ветвления). В общем, полный текст интерпретатора на прологе не такой уж и большой. И может работать в том числе и под "метациклическим интерпретатором" Пролога на самом себе, то есть самоприменимым.

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

Например, META II это фактически метаинтерпретатор метаязыка описания грамматики "синтаксических уравнений" самого META II, и его модели вычислений. И уже во вторую очередь — реализация этой модели на каком-то ассемблере, Си, JavaScript, Scheme. То есть, метаинтерпретатор задаёт семантику реализации нового языка программирования, элементарно расширяемую поверх базовой реализации семантики метаинтерпретатора.

Можно и компилировать в байт-код какой-то виртуальной машины, например, Схемы Ribbit или некоторого Форта Retro на основе Ngaro VM (тоже довольно простая виртуальная машина). И дальнейшую специализацию проводить уже на уровне расширения возможностей этого Ribbit или Ngaro. Упрощая встраивание, расширяемость и оптимизацию.

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su

Содержание

Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

● Надо ли использовать YACC, LEX и подобные инструменты