Сообщество » MCC/LiME

Существуют два разных базовых подхода к построению компиляторов, изложенные в двух основополагающих книгах: "Compilers: Principles, Techniques, and Tools" (книга Дракона) и "Design Concepts in Programming Languages" (DCPL).

Книга Дракона предлагает разработчикам технику синтаксически-управляемой трансляции. Практической вершиной которой является техника перевода исходного текста программы на каком-нибудь языке в промежуточное представление этой программы при помощи аннотированной грамматики. Метод хорошо проработан и является на сегодняшний день основным, используемым на практике. Однако, у него есть недостатки:

1. невозможно расширить язык со стороны пользователя, так как грамматика у языка фиксирована, а это было бы весьма желательно, при исследовании возможностей новых архитектур процессоров (фактически, современное состояние дел в архитектурах CPU заморожено подходом к разработке языков для системного программирования);
2. для каждого языка со своей грамматикой необходим отдельный модуль перевода из абстрактного синтаксического дерева (AST) программы в промежуточное представление;
3. каждый такой модуль -- сложная "ветвящаяся" конструкция, которая должна в каждом узле AST анализировать множество условий и вариантов сочетания выражений, задаваемых различными поддеревьями рассматриваемого узла;
4. кодом, накопленным при реализации модуля трансляции одного языка программирования, невозможно воспользоваться для программирования семантики другого языка, структура аннотированных грамматик, скорее всего, будет существенно разной.

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

DCPL описывает более фундаментальный подход к семантике языков программирования, и к их трансляции. Подходы эти очень сильно завязаны на lambda-абстракции в вычислениях и на концепцию доменов, особенно на суммы доменов (это когда мы говорим, что вот Value = Int + Char + Float + Double + Complex + Structure 1 + Structure 2 + и т.д.; что означает: Value может быть одним из: ...). При помощи lamda-абстракций, описывающих определённые функции, каждому узлу выражение программы на исходном языке, представленное в синтаксической алгебре S-выражения для этого языка (а любой язык можно перевести в такое представление), отображается в целевой язык.

Это всё замечательно, формально, корректно, открывающе различные чакры true-программиста. Есть и чисто технические достоинства подхода:

• некоторые lambda-абстракции можно использовать в трансляторах для разных языков программирования (язык S-выражений можно сделать достаточно универсальным, универсальными могут быть и некоторые семантические конструкции).

Но при этом, остаётся и сложность:

1. многие lambda-абстракции для конкретного языка программирования могут содержать большие операторы сопоставления с образцом (pattern matching), из-за того, что домены значений, которыми оперирует исходный язык могут быть очень сложными по своей структуре;
2. подход по-прежнему не позволяет программисту вводить новые языковые конструкции.

Оба этих недостатка обусловленны одним и тем же. Даже если рассмотреть простейшее выражение на Си "a + b" возникает множество контекстов его оценки. И то, как следует транслировать a зависит от того, чем является b. Комбинаций при этом множество: char + char, char + int, char + float, char + double, char + _Complex, char + pointer и так далее, int + char, int + int, int + float, ...

Сопоставление по образцу (pattern-matching) внутри lambda-абстракции должно быть жёстко запрограммированным, по определению этой конструкции. Его можно сделать иерархическим, если, например, разбить домен всех возможных значений для подвыражений Value так:

Value = (Arithmetic = Char + Int + Float + Double + _Complex + ...) + (Struct = struct tag1 + struct tag2 + ...) + ...

и рассматривать сначала выражения по вариантов для крупных доменов, но всё-равно операторы сопоставления получаются внушительными, и пользователь языка не может их изменять, без вмешательства в код транслятора.

Указанные проблемы исчезли бы (взамен, вероятно, мы можем получить много новых, пока не известных), если бы у нас было средство выражать процедуру сопоставления по образцу динамически, в зависимости от текущего контекста, это бы сэкономило нам силы на программирование разбора вариантов и, возможно, доло бы средство расширения семантики языка программирования с уровня пользователя для лингвистических экспериментов над архитектурой MCp (а там есть с чем экспериментировать).

Это мы и пытаемся сделать в технологии LiME.

Подходящим для этой цели вычислительным формализмом могут быть потоковые логические вычисления (мы же должны выдерживать стиль Мультиклета). Вероятно, таких в природе ещё не было, поэтому надо раскрыть суть явления. Логические вычисления - это, как известно, вычисления, позволяющие вывести некоторое выражение, ограниченное некоторыми правилами вывода. Обычно, набор правил задаётся в виде фиксированной программы (Prolog) или, допустим, графа целей (планирование). Однако, мы можем добавить в процесс вывода немного динамики, когда правила возникают по определённым событиям. Здесь можно выбрать примерно тот же подход, что и в системе RiDE, когда правила продолжения потока вывода (вычисления в случае RiDE) могут возникать по мере активации уже существующих правил или по внешним событиям.

Внешними событиями для LiME являются линейно-упорядоченная последовательность синтаксических инструкций, описывающих структуру S-выражения программы. Эта последовательность -- результат разбора по грамматике исходного языка вполне стандартным методом (для Си99 мы используем bison). Каждое такое событие вместе с типом выражения, находящимся на вершине стека разбора, определяют набор правил, который нужно добавить в текущий контекст вывода промежуточного представления.

Возможно, этот метод является переформулировкой метода, излагаемого в DCPL (которую, впрочем, можно считать более формально построенным вариантом книги Дракона, в конце концов, все преобразования данных сводятся к машине Тьюринга). Но можно ожидать, что эта переформулировка позволит реализовывать в языках некоторые интересные для практики конструкции.

Предлагаем Вам присоединиться к обсуждению достоинств и недостатков нашей технологии.

Форум: http://multiclet.com/community/boards/4/topics/53
Спецификация (в состоянии дописывания): http://multiclet.com/community/projects/mcc-lime/repository (см. source:txt/spec.txt)