Начинаем открытое обсуждение LiME
LiME - это, в некотором смысле, необычная технология, на которой будет основана коллекция компиляторов Мультиклет. Предлагаем обсудить её достоинства и недостатки
Существуют два разных базовых подхода к построению компиляторов, изложенные в двух основополагающих книгах: "Compilers: Principles, Techniques, and Tools" (книга Дракона) и "Design Concepts in Programming Languages" (DCPL).
Книга Дракона предлагает разработчикам технику синтаксически-управляемой трансляции. Практической вершиной которой является техника перевода исходного текста программы на каком-нибудь языке в промежуточное представление этой программы при помощи аннотированной грамматики. Метод хорошо проработан и является на сегодняшний день основным, используемым на практике. Однако, у него есть недостатки:- невозможно расширить язык со стороны пользователя, так как грамматика у языка фиксирована, а это было бы весьма желательно, при исследовании возможностей новых архитектур процессоров (фактически, современное состояние дел в архитектурах CPU заморожено подходом к разработке языков для системного программирования);
- для каждого языка со своей грамматикой необходим отдельный модуль перевода из абстрактного синтаксического дерева (AST) программы в промежуточное представление;
- каждый такой модуль -- сложная "ветвящаяся" конструкция, которая должна в каждом узле AST анализировать множество условий и вариантов сочетания выражений, задаваемых различными поддеревьями рассматриваемого узла;
- кодом, накопленным при реализации модуля трансляции одного языка программирования, невозможно воспользоваться для программирования семантики другого языка, структура аннотированных грамматик, скорее всего, будет существенно разной.
Самыми неприятными пунктами для небольшой команды разработчиков являются 2 и 3. 2 подразумевает действительно очень сложный разбор вариантов, и проделывать его каждый раз для каждого языка заново -- черезмерно трудозатратно. 3 указывает на то, что труда понадобится ещё больше.
DCPL описывает более фундаментальный подход к семантике языков программирования, и к их трансляции. Подходы эти очень сильно завязаны на lambda-абстракции в вычислениях и на концепцию доменов, особенно на суммы доменов (это когда мы говорим, что вот Value = Int + Char + Float + Double + Complex + Structure 1 + Structure 2 + и т.д.; что означает: Value может быть одним из: ...). При помощи lamda-абстракций, описывающих определённые функции, каждому узлу выражение программы на исходном языке, представленное в синтаксической алгебре S-выражения для этого языка (а любой язык можно перевести в такое представление), отображается в целевой язык.
Это всё замечательно, формально, корректно, открывающе различные чакры true-программиста. Есть и чисто технические достоинства подхода:- некоторые lambda-абстракции можно использовать в трансляторах для разных языков программирования (язык S-выражений можно сделать достаточно универсальным, универсальными могут быть и некоторые семантические конструкции).
- многие lambda-абстракции для конкретного языка программирования могут содержать большие операторы сопоставления с образцом (pattern matching), из-за того, что домены значений, которыми оперирует исходный язык могут быть очень сложными по своей структуре;
- подход по-прежнему не позволяет программисту вводить новые языковые конструкции.
Оба этих недостатка обусловленны одним и тем же. Даже если рассмотреть простейшее выражение на Си "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)
Comments
Added by eugenk over 11 years ago
Михаил, прошу прощения, возможно туплю, но речь идет все-таки о языке, который позволяет пользователю расширять себя новыми конструкциями (п.1) ???
Вообще-то у меня была одно время задача писать для процессора, который сам находился в активной разработке. Но дальше ассемблера, управляемого неким файлом описания системы команд я не пошел. Языки высокого уровня боюсь требуют все-таки некоей стабильности и железа и концепций самого языка. А из расширяемых, что Вы формулируете в самом начале, я знаю только forth. Кстати в свое время, лет 15 назад, очень активно им пользовался именно для работы с самодельными железом для PC.
Added by m.bakhterev over 11 years ago
Речь о языке, в котором можно определить на уровне пользователя какой-нибудь свой
forили свой тип с какими-нибудь операциями, вродеstring + string.Это в общем-то делается всегда одинаково, путём предоставления программисту доступа к ядерным (kernel) конструкциям языка. В mainstream-языках такое редко явно используется, но в функциональных - это стандартная возможность. Тут только весь вопрос в том, что у нас будет этими kernel-конструкциями. Потому что, обычно, они работают с lambda-абстракциями, а нам всё же нужен императивный язык. Нам хочется сделать это на достаточно общем уровне, чтобы, например, в том же C иметь возможность определить всякие стандартные библиотеки (допустим те же функции
str*) как intrinsic-и без всяких изощрений, а на основе общих принципов: как определяемforтак будем определять иstrcmp. Речь примерно вот об этом. Чтобы программист мог написать:operator (for(exp init; exp cnd; exp inc) (exp body)) = (for implementation); operator (strcmp(char ptr str) = (how-to-do strcmp).Сам LiME давно развивается. Это уже вторая или третья (если считать самую первую корявую попытку в 2006 году) версия. Сейчас мы подгоняем ядро системы под возможность реализации Си99 (там есть свои тонкости, в виде хитрых инициализаторов структур и массивов, и достаточно сложной системы type-promotion). Это требует некоторого времени, но процесс идёт.
Forth, конечно - это классика. И, насколько я знаю, он до сих пор активно используется. Некоторые идеи мы в LiME тащим и из Forth, конечно же.
Added by eugenk over 11 years ago
С фортом это просто только по одной причине. У него нет синтаксиса. Всё сущее есть просто поток лексем. С функциональными даже не знаю. Если Вы о лиспе, то в некотором смысле наверно да. Но тоже исключительно из-за почти полного отсутствия синтаксиса. Как сделать что-то подобное с С - ума не приложу. Единственно что приходит в голову - сделать доступным пользователю какой-то метаязык, описывающий целевой язык. Но боюсь это только перенос проблемы на другой уровень во-первых, и боюсь этот метаязык окажется слишком сложен для обычного юзера во-вторых. Хотя тут тоже интересный момент. Если удастся такое изобрести, можно сделать систему описания фронтэндов. Чтобы например при создании нового языка не возиться с грамматиками, а сразу определять его высокоуровневыми средствами. А вообще конечно дико интересная задача. С удовольствием бы этим занялся.
P.S. Михаил, подскажите пожалуйста, как пользоваться репозитарием. Хотел всё скачать и неспеша посмотреть, но как это сделать совершенно не понял.
Added by m.bakhterev over 11 years ago
eugenk
Ну... Совсем отказаться от грамматики нельзя. Она всё-таки штука такая, врождённая в язык. В Forth и Lisp тоже есть грамматики, просто очень простые. У Lisp - это грамматика S-выражений (просто описание деревьев в скобочно-списковой записи). S-выражения хороши тем, что выражение в любой грамматике переводится в итоге в дерево, которое можно записать в виде S-выражения. Поэтому в MIT особо любят семантику всего и вся описывать на Lisp-подобных языках.
Но нам это не особо подходит. Потому что, если мы запишем конкретную семантику на Lisp для одного конкретного языка, то другой язык придётся делать заново, а силы у нас ограничены. Поэтому мы делаем ещё один шаг и записываем полученное S-выражение в виде потока определённых инструкций, которые однозначно описывают дерево. То есть, получается такая вполне себе Forth-подобная конструкция - последовательность простых выражений.
Далее, этот поток ситаксических инструкций мы передаём в ядро языка, которое по определённым правилам его пережёвывает, с использованием определённых пользователем синтаксических форм (которые можно использовать повторно, для другого языка, с другой грамматикой, потому что синтаксис превращается в нечто однообразное). Это описание в виде форм не самое тривиальное, конечно, но достаточно простое. Проще, чем большие if - else if - else if - else if - ... - else в традиционном подходе с аннотированными грамматиками или большие pattern-match операторы в подходе с Lisp.
Далее, имея эти формы и поток синтаксических инструкций наше ядро "просто" выводит целевое промежуточное представление программы, действуя как очень сильно упрощённая версия Prolog (потом, возможно, придётся усложнить алгоритм вывода).
Теперь, самое главное. Мы можем сделать так, чтобы в формах пользователь мог описать конструирование новых синтаксических форм. И тогда, начав с небольшого набора этих форм, пользователь может начать описывать свой язык на самом своём языке. Нечто примерно такое есть в Scheme, но в ограниченном S-выражениями виде, и там нет вывода промежуточного представления, формы там просто трансформируются в процессе, который называется desugaring (ну, типа, формы - это синтаксический сахар), в выражения на основном языке Scheme. Мы хотим пойти дальше. Тут, конечно, с очень абстрактной точки зрения можно сказать, что мы делаем то же самое (в конце концов, универсальная машина Тьюринга существует), но есть ощущение, что особенности нашего подхода могут иметь интересные эффекты.
В стандартной грамматике Си для такого нет места, конечно. Но можно же и другую грамматику взять. Или можно описывать один язык средствами другого.
Если Вы смотрите хранилище через Redmine, то там сверху показывается дерево каталогов и файлов. Если выбрать какой-нибудь файл (а процесс уточнения текущей спецификации у нас происходит в файле
txt/spec.txt), то будет показан список редакций, в которых изменялся файл. Это не особо интересно. Главное - вверху, под именем самого файла, написанного большими буквами, будут три ссылки. У меня, с англоязычным интерфейсом, они по-порядку называются View | Annotate | Download. Если Вы кликните View, Redmine покажет содержимое файла, там даже ссылки можно будет копировать на конкретные строки.Или Вы можете просто клонировать себе хранилище. Мы пользуемся системой контроля версий Git, поэтому клонировать его нужно командой
Это одно из пристанищ исходников проекта, завтра я на сайте MultiClet настрою такое-же.
Эта команда заставит склонировать ветку
lime-0.devв папкуlimeв текущем каталоге. Это так делается в *NIX средах.В Windows Git входит в состав Cygwin (*NIX-среда для Windows). Есть и отдельные пакеты: TortoiseGit и MSysGit, установив которые можно сделать то же самое (клонировать определённое хранилище к себе на компьютер), но уже при помощи графического интерфейса, интегрированного с Windows Explorer. Я, к сожалению, тут не особо могу рассказать, что делать. Но в интернете есть много руководств по использованию TortoiseGit.
P.S. Удобнее бы было перенести обсуждение на форум, та больше возможностей по работе с текстами постов: http://multiclet.com/community/boards/4/topics/53
Added by Smer4 over 11 years ago
Несколько туманно описана технология чтоб ее обсуждать, но на первый взгляд эта инновация напоминает старый лисп со множеством "макро"- фич как в Шеме и т.п.
то есть крайне неюзабельных на практике.
Во вторых, вам практически не надо вводить новые конструкции в сам язык. Выражения "a + b" для разных сложных типов диспатчатся по типу и в принципе являются лишь синтактическим сахаром, так как проще и частенько понятнее было бы употреблять стандартные ОО конструкции а.plus(b) или plus(a,b), потом удаляем
полиморфизм plus_int_struct(a,b) например, то есть компилятор будет рассматривать все действия как вызовы функций и будет их в основном инлаинить.
Помоему С++ что то такое делает. Инструменты, позволяющие транслировать любой синтактический сахар в любой другой есть))).
Можете посмотреть такие тулзы как JIT, SugarJ, там всякие эклипс тулзы с DSL, есть транслятор хаскеля в С.
Ну последовательность например
int * a;
a + b = 42;
Будет у нас:
init_ptr("a", адресс);// инициализация переменной а в пространстве имен переменных
mem_set(адресс+b, 42);// собственно это одна команда на ассемблере, примерно так на нем будет.
Ну и еще компилятор должен делать прочие неупомянутые тут вещи такие как оптимизация и удаление "ненужных" операций, позволяет ли эта технология сделать
так сперва на уровне абстракции?
Added by trott over 11 years ago
Склонировал у себя LiME, но не смог его собрать.
git clone git://0xfb.imm.uran.ru/lime.git -b lime-0.dev
кроме того в хранилище вижу проекты cfe, drv, gen, lcc, mcc, mkenv , однако их не могу склонировать с помощью git.
Опишите, пожалуйста, процедуру сборки LiME