Здравствуйте, Аноним, Вы писали:
А>вставить после каждой строчки останов и скомпилировать?
Чё?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: на сколько сложно будет сделать интерпритатор Н2?
От:
Аноним
Дата:
16.04.12 18:29
Оценка:
Здравствуйте, VladD2, Вы писали:
А>> Генерация IL все еще существенно проще чем интерпретация
VD>Это заблуждение. Попробуй сам и поймешь, что это не так.
Это не "заблуждение", а практика. Я это делаю регулярно, предпочитаю тупой System.Reflection.Emit даже там, где другие использовали бы expression trees.
А>>(по той же причине — не надо заниматься контекстом, все VM сделает сама), IL все еще очень высокоуровневый.
VD>IL то? Акстись! В нем почти никаких проверок не делается.
А проверки-то тут при чем? Я про совсем уж тупое говорю — переменные, аргументы функций, и т.п.
VD> Ты с легкостью сможешь сгенерировать модуль которые вылетит в рантайме, не пройдет верификацию или вообще завалит приложение.
Смогу, но не стану. Система типов не позволит. Которую кстати для компилятора тоже проще реализовать, чем для интерпретатора.
А>>Компиляция в нейтив сложна только в двух местах — register scheduling и instruction selection.
VD>Она вообще сложна.
Не надо. Она тупа и тривиальна. Сам тот факт, что для написания компилятора даже Тьюринг-полного языка не надо ни на что не намекает?
VD> А качественная компиляция, да еще и под разные платформы — это вообще отдельная наука.
Эта отдельная наука возникает только на самом низком уровне, и если не нужно ядерной производительности, то ее можно проигнорировать.
VD> В разных GCC бэкэнды составляют основной объем кода.
Смотрим на tcc и lcc и ужасаемся. Или даже на backend-ы из OCaml, они настолько тупы, насколько это вообще возможно, а производительность при этом весьма неплохая.
А>>Если компилировать по тупой схеме (например, все переменные сразу на стеке, а регистры только для специальных случаев), наплевав на оптимизации, то все равно выходит на порядок проще чем интерпретация.
VD>Не фига не выходит. Интерпретировать можно прямо сразу.
Нельзя. Нужен тот самый "контекст", которым я уже, кажется, всех задолбал.
VD> Для компиляции в низкоуровневый язык вроде ассемблера по любому нужно городить огород с преобразованием древесной формы в линейную и т.п.
А что вообще может быть проще чем преобразование дерева в плоский код? Для стековой машины так и вовсе ничего кроме обхода вглубь не нужно, для регистровой есть пара тривиальных трюков, которые не намного сложнее тупого обхода.
VD>>>Кроме того для интерпретации ДСЛ-я не обязательно писать полный по тьюрингу движок. Достаточно придумать модель, а из ДСЛ-я "заполнить" ее. Написать же интерпретатор по этой модели задача довольно плевая.
А>> Опять же ровно до того момента, когда для DSL потребуется какой либо сложный контекст. Наличие переменных и функций этот контекст неизбежно предполагает.
VD>У тебя какой-то пунктик с этим контекстом. Модель полностью определяет весь контекст ДСЛ-я.
Под контекстом я понимаю все то, что у нас в лексическом контексте — переменные, параметры, и т.д., и реализацию lookup во всем этом деле при интерпретации.
VD> Если есть модель, то написание ее интерпретатора — это примитивнешая задача.
Нет, это написание компилятора примитивнейшая задача. А интерпретатор уже не настолько тривиален, и в нем можно очень легко накосячить.
VD> Может стать и так, что будет достаточно просто вызвать метод модели — это и будет интерпретацией.
Не понял.
VD>>>Скажем, вместо того чтобы генерировать код парсера, можно сделать интерпретатор его модели (по которой код и генерируется). Это будет в разы проще.
А>> Не. Генерировать код намного проще.
VD>Для тех кто этого не делал — да.
Я только этим и занимаюсь. Всегда предпочту компилятор интерпретатору, так проще.
VD> Займись этим на практике и увидишь, что это отнюдь не просто.
Откуда уверенность, что "увижу"? За последние лет двадцать так и не увидел.
VD> Это не просто даже при генерации высокоуровневого языка.
А уж высокоуровневый язык генерить вообще элементарнее некуда.
VD>Потом от компилируемого кода все ожидают быстрой работы. А сделать генерацию оптимального кода в разы сложней.
Кто и зачем ожидает? Быстрее интерпретатора — и ладно.
VD>Вот погляди. Это (включая все вложенные подкаталоги и файлы) — код связанный с генерацией кода для парсера.
Плохо, очень нерационально написано. Могу даже объяснить, что там не так — нельзя сразу генерить код из языка настолько более высокого уровня в язык низкого уровня без нескольких промежуточных представлений. Если помнить об этой простой штуке, то компиляторы становятся тривиальными. И, кстати, если писателям компиляторов не давать полноценного Тьюринг-полного языка, то они таких кошмаров и городить не станут, просто не смогут.
VD>И он еще очень компактен, так как сделан с помощью весьма выскороуровневых средств (квази-цитирования и паттерн-матчинга).
И эти средства слишком низкоуровневные, на самом деле. Вместо pattern matching нужен как минимум DSL в стиле Scrap your boilerplate (сразу в разы код сократится).
VD> Аналогичный код на C# будет раз в 5-10 больше.
При таком неправильном подходе — да. При многоуровневой кодогенерации — может и будет несколько больше, но весь будет совершенно тривиальным.
VD>А это код модели. Он существенно проще. Можно написать интерпретатор по нему всего лишь добавив по одной функции в каждый тип из этого списка.
Это все равно слишком сложно. Сплошной boilerplate, тогда как компилятор может быть чисто декларативным, таким, что и ошибиться-то негде.
Re[9]: на сколько сложно будет сделать интерпритатор Н2?
Здравствуйте, Аноним, Вы писали:
А> Это не "заблуждение", а практика. Я это делаю регулярно, предпочитаю тупой System.Reflection.Emit даже там, где другие использовали бы expression trees.
У тебя явно однобокая практика. А предпочтение SRE — убого и кривого API вообще мягко говоря странный выбор.
А> А проверки-то тут при чем? Я про совсем уж тупое говорю — переменные, аргументы функций, и т.п.
А типа если заложить на стек переменную одного типа, потом другого и вызвать оператор ожидающих соответствия типов, то проблем не возникнет?
SRE тупейший АПИ требующий особой осторожности. По сравнению с его использованием написание интерпретатора — это детская забава.
Короче, давай померемся пиписками. Пишем каждый свою реализацию простого вычислителя выражений (строчного калькулятора). Условия такие:
1. Приложение оформляем в виде консольного приложения.
2. Приложение позволяет последовательно выполнять следующие операции:
2.1. Определение переменной: x = 42 или x = y. Справа может быть любое выражение.
Если переменной справа нет, то должно выдаваться сообщение об ошибке.
2.2. Вычисление выражения: x + 3 * 8. Должны соблюдаться приоритеты
операторов (* и / приоритетнее бинарных + и -). Результат выражения должен выводиться
на консоль со следующей строки. Если в выражении ошибка, нужно сообщать об ошибке
и указывать место ошибки.
3. Платформа дотнет версии 4.0.
Ты пишешь свою версию с использованием SRE, а я свою интерпретируемую. Можно использовать любые языки дотнета, любые библиотеки и фрэймворки.
Далее сравним количество кода и вообще траха возникшего при реализации.
Если твое решение окажется короче моего, то я сниму шляпу и признаю, что ты прав и компиляторы делать проще чем интерпретаторы.
Чтобы облегчить тебе задачу может не сравнивать объем кода парсера, а только объем кода который потребуется для генерации кода и его запуска и его же интерпретации.
Пойдет?
А> Смогу, но не стану. Система типов не позволит. Которую кстати для компилятора тоже проще реализовать, чем для интерпретатора.
Для интерпретатора можно легко использовать динамическую типизацию. Так что систему типов особо и реализовывать не придется.
VD>> А качественная компиляция, да еще и под разные платформы — это вообще отдельная наука.
А> Эта отдельная наука возникает только на самом низком уровне, и если не нужно ядерной производительности, то ее можно проигнорировать.
А тут возникает вопрос... Если нам производительность не важна, то на фиг нам возиться с компиляцией и проблемами которая она вызывает? И интерпретатор становится лучшим выбором, так как просто и гибко (можно запускать в рантайме без проблем).
VD>> В разных GCC бэкэнды составляют основной объем кода.
А> Смотрим на tcc и lcc и ужасаемся.
На tcc и lcc чего? Это ведь метрики вроде как.
А> Или даже на backend-ы из OCaml, они настолько тупы, насколько это вообще возможно, а производительность при этом весьма неплохая.
Ну, давай ссылки будем сравнивать. За одно давай ссылки на тупые же интерпретаторы. Производительность тут вообще не причем. Понятно что компилированный статически-типизированный язык будет шустрее хренового интерпретатора.
VD>>Не фига не выходит. Интерпретировать можно прямо сразу.
А> Нельзя. Нужен тот самый "контекст", которым я уже, кажется, всех задолбал.
Ну, я тебе предложил сверху калькулятор написать. Сравним у кого какой контекст получится.
Давай, если ты такой смелый — покажи класс!
Для справки для этой задачи весь контекст пройдет через возвращаемое значение процедуры обхода АСТ в интерпретаторе. Я даже не напрягусь с таким контекстом. А вот ты затрахаешся.
VD>> Для компиляции в низкоуровневый язык вроде ассемблера по любому нужно городить огород с преобразованием древесной формы в линейную и т.п.
А> А что вообще может быть проще чем преобразование дерева в плоский код?
Прямая интерпретация по АСТ, ваш КО.
А>Для стековой машины так и вовсе ничего кроме обхода вглубь не нужно, для регистровой есть пара тривиальных трюков, которые не намного сложнее тупого обхода.
То-то в реальных компиляторах дотнета куча сложнейшего кода лепится. Одни зависимости между типами чего стоят.
А> Под контекстом я понимаю все то, что у нас в лексическом контексте — переменные, параметры, и т.д., и реализацию lookup во всем этом деле при интерпретации.
Ну, дык модель и должна их все описывать.
VD>> Если есть модель, то написание ее интерпретатора — это примитивнешая задача.
А> Нет, это написание компилятора примитивнейшая задача. А интерпретатор уже не настолько тривиален, и в нем можно очень легко накосячить.
Ну, вот давай и сравним на практике.
VD>> Может стать и так, что будет достаточно просто вызвать метод модели — это и будет интерпретацией.
А> Не понял.
А зря. Модель может быть просто объектом. ДСЛ тупо заполняет объект нужной информацией, а вызов некоторого метода этого объекта выполняет интерпретацию.
А> Я только этим и занимаюсь. Всегда предпочту компилятор интерпретатору, так проще.
Я как бы тоже. Но выводы у меня ровно обратные. Я если и предпочту компиляцию, то только по соображениям надежности и производительности. При этом я буду понимать, что с простотой я расстался намеренно.
VD>> Займись этим на практике и увидишь, что это отнюдь не просто.
А> Откуда уверенность, что "увижу"? За последние лет двадцать так и не увидел.
И чем ты занимаешься, если не секрет?
VD>> Это не просто даже при генерации высокоуровневого языка.
А> А уж высокоуровневый язык генерить вообще элементарнее некуда.
Я тебе кажется показал код из реальной задачей. Зачем спорить с очевидным?
VD>>Потом от компилируемого кода все ожидают быстрой работы. А сделать генерацию оптимального кода в разы сложней.
А> Кто и зачем ожидает? Быстрее интерпретатора — и ладно.
Тот кто выбирает компиляцию. Компилированный вариант тоже можно сделать медленным. Быстрее и ладно прокатывает только на очень примитивных задачах. А когда занимаешься разработкой генератора парсеров, то производительность получаемых парсеров становится критически важной фичей. Тут интерпретация может замедлить решение в 10 раз, а плохой выбор алгоритмов, структур данных и т.п. может и к экспоненте привести, что как понимаешь, будет уже не 10 раз, а в вплоть до полной непригодности.
VD>>Вот погляди. Это (включая все вложенные подкаталоги и файлы) — код связанный с генерацией кода для парсера.
А> Плохо, очень нерационально написано.
Умора, блин! Настоящий русский программист. Любой чужой код сразу кака.
А> Могу даже объяснить, что там не так — нельзя сразу генерить код из языка настолько более высокого уровня в язык низкого уровня без нескольких промежуточных представлений.
Какой ты молодец! И какой же промежуточный язык ты предложишь?
А>Если помнить об этой простой штуке, то компиляторы становятся тривиальными.
Это довольно безответственный треп не подкрепленный никакими фактами или соображениями.
Давай, предложи промежуточный язык и объясни какие проблемы он решит.
В прочем, после рассказов про простоту генерации IL-а через SRE я уже не знаю каким из твоих слов верить. Как-то странно слышать про простоту генерации сразу низкоуровневого языка, а потом вдруг довольно здравую, но аморфную, мысль о необходимости еще какого-то там промежуточного языка.
А>И, кстати, если писателям компиляторов не давать полноценного Тьюринг-полного языка, то они таких кошмаров и городить не станут, просто не смогут.
А как же SRE как самый простой способ генерации кода? Ты уж определись, как то.
VD>>И он еще очень компактен, так как сделан с помощью весьма выскороуровневых средств (квази-цитирования и паттерн-матчинга).
А> И эти средства слишком низкоуровневные, на самом деле. Вместо pattern matching нужен как минимум DSL в стиле Scrap your boilerplate (сразу в разы код сократится).
Вот результат этого проекта и будет выдавать такой ДСЛ. А пока что его нет, приходится использовать тоже не плохие средства вроде АлгТД и паттерн-матчинга.
В прочем, сложность тут отнюдь не в МП по модели. Он там в сущности примитивный. Сложность там как раз в оптимизациях и разного рода хитростях. Нужно сгенерировать код мемоизации, обеспечить возможность динамического расширения, выявления конфлитков, сгенерировать разный код для предикатов (он не возвращает значения и стало быть должен быт "легче") и для применения тех же правил без предикатов... В общем, много чего.
А вообще, вот это и есть отличный пример когда разговоры о великой силе ДСЛ-ей разбиваются о банальный факт того, что чтобы воспользоваться мощным ДСЛ-ем его сначана нужно сделать имеющимися средствами. Если эти средства C# или С++ то все вообще становится очень печально. Да и с более мощными инструментами тоже не все "фонтан". Появляется проблема курицы и яйца. Чтобы написать код ДСЛ-я для построения ДСЛ-ей нужно сначала написать этот код без ДСЛ-ей .
VD>> Аналогичный код на C# будет раз в 5-10 больше.
А> При таком неправильном подходе — да. При многоуровневой кодогенерации — может и будет несколько больше, но весь будет совершенно тривиальным.
ОК. Покажи правильный. Сравним объем кода.
Уверен, что показать тебе не чего.
VD>>А это код модели. Он существенно проще. Можно написать интерпретатор по нему всего лишь добавив по одной функции в каждый тип из этого списка.
А> Это все равно слишком сложно. Сплошной boilerplate, тогда как компилятор может быть чисто декларативным, таким, что и ошибиться-то негде.
Код в студию! Тогда и сравним. Пока что это самая простая реализация которую я видел. Придумать промежуточный язык я как-то не могу. Придумал бы — сразу бы его использовали бы.
У парсера есть модель. Ссылку на ее описание я давал. Во что можно ее перевести чтобы сократить разуницу между языками? Я с удовольствием послушаю рассказ об этом.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: на сколько сложно будет сделать интерпритатор Н2?
От:
Аноним
Дата:
17.04.12 12:35
Оценка:
Здравствуйте, VladD2, Вы писали:
А>> Это не "заблуждение", а практика. Я это делаю регулярно, предпочитаю тупой System.Reflection.Emit даже там, где другие использовали бы expression trees.
VD>У тебя явно однобокая практика.
Ну ну. У меня часто встречаются DSL весьма высокой сложности, уровня ML или Prolog (с WAM-ом). А бывают и DSL совсем низкого уровня, компилируемые в Verilog. Разнообразная практика, стало быть.
VD> А предпочтение SRE — убого и кривого API вообще мягко говоря странный выбор.
Естественно я его на напрямую использую.
А>> А проверки-то тут при чем? Я про совсем уж тупое говорю — переменные, аргументы функций, и т.п.
VD>А типа если заложить на стек переменную одного типа, потом другого и вызвать оператор ожидающих соответствия типов, то проблем не возникнет?
А зачем это делать? И почему нельзя точно так же накосячить с интерпретатором?
VD>SRE тупейший АПИ требующий особой осторожности. По сравнению с его использованием написание интерпретатора — это детская забава.
Да нет там ничего сложного, серьезно.
VD>Ты пишешь свою версию с использованием SRE, а я свою интерпретируемую. Можно использовать любые языки дотнета, любые библиотеки и фрэймворки.
Любые языки неинтересно, не спортивно. Только голый c#, только хардкор!
Сам компилятор — несколько строк. Парсер естественно жирноватый, потому как это всего лишь c#, и потому что мне вообще обычно на парсеры плевать. Пусть меня побьют и заклюют, но мне синтаксиса JSON или XML хватает для многих DSL. Про Лисп и говорить нечего, там синтаксис и вовсе не нужен.
Если выбирать какой попало язык, то можно было бы взять f# и получилось бы уже совсем не спортивно. Или вовсе найти один из многочисленных DSL-ей для компиляции DSL-ей под .NET. Например, находится такое (сам не пробовал, но DSL похож на scrap your boilerplate): http://bit.ly/I2LFdr
Если не под .NET, то я взял бы Clojure (и генерил бы байткод напрямую), ну а лучше всего, на данный момент мой наиболее предпочтительный вариант — Haskell с LLVM.
VD>Далее сравним количество кода и вообще траха возникшего при реализации.
Количество кода сравнивать надо только на одинаковых языках. Кроме количества надо сравнивать читабельность и поддерживаемость (например, насколько легко было бы расширить язык новыми возможностями).
VD>Если твое решение окажется короче моего, то я сниму шляпу и признаю, что ты прав и компиляторы делать проще чем интерпретаторы.
По одной из ссылок выше как раз сравнивается компилятор в IL и интерпретатор, и компилятор при наличии навороченного DSL получается заметно проще.
VD>Чтобы облегчить тебе задачу может не сравнивать объем кода парсера, а только объем кода который потребуется для генерации кода и его запуска и его же интерпретации.
Код для запуска скомпилированного тоже лучше не считать, он обычно одинаковый для всех DSL, получается копипастой и не сокращается только из-за уродства SRE и недостаточной выразительности языка.
VD>Для интерпретатора можно легко использовать динамическую типизацию. Так что систему типов особо и реализовывать не придется.
А для компилятора ее что, сложно использовать? Вовсе нет, проще чем для интерпретатора.
VD>А тут возникает вопрос... Если нам производительность не важна, то на фиг нам возиться с компиляцией и проблемами которая она вызывает? И интерпретатор становится лучшим выбором, так как просто и гибко (можно запускать в рантайме без проблем).
Затем, что компиляция проще интерпретации и проблем она не вызывает, проблемы она решает. Кроме того, даже неоптимальный компилятор все равно будет давать лучший результат чем даже очень сильно оптимизированный интерпретатор.
И я уж промолчу о том, что в большинстве случаев интерпретатор будет включать в себя и значительную часть компилятора.
VD>>> В разных GCC бэкэнды составляют основной объем кода.
А>> Смотрим на tcc и lcc и ужасаемся.
VD>На tcc и lcc чего? Это ведь метрики вроде как.
Это компиляторы C:
http://bit.ly/HQFKLu http://bit.ly/12Tufm
А>> Или даже на backend-ы из OCaml, они настолько тупы, насколько это вообще возможно, а производительность при этом весьма неплохая.
VD>Ну, давай ссылки будем сравнивать. За одно давай ссылки на тупые же интерпретаторы. Производительность тут вообще не причем. Понятно что компилированный статически-типизированный язык будет шустрее хренового интерпретатора.
http://bit.ly/kt4kR — и интерпретатор там не "хреновый", а один из лучших когда либо созданных. Очень красиво реализованный интерпретатор VM с использованием шитого кода (computed goto extension в gcc). А компилятор как раз совершенно в лоб написан, без каких либо оптимизаций, и все равно очень шустрый.
VD>Ну, я тебе предложил сверху калькулятор написать. Сравним у кого какой контекст получится. VD>Давай, если ты такой смелый — покажи класс!
Там весь контекст — переменные. Нет вложенных областей видимости. Так что интерпретатор лишь немного более сложный получается чем компилятор.
VD>Для справки для этой задачи весь контекст пройдет через возвращаемое значение процедуры обхода АСТ в интерпретаторе. Я даже не напрягусь с таким контекстом. А вот ты затрахаешся.
Да какое там вообще AST? Плоская последовательность выражений. Никаких вложенных блоков. Не интересно. А вот чтобы с интерпретатором затрахаться как раз достаточно ввести, ну, допустим, лексические замыкания. И чтоб чистый-чистый интерпретатор был, без каких либо проходов компиляции (то есть, lambda lifting делать нельзя). Голый "обход AST", с корректной поддержкой контекста. Слабо?
VD>>> Для компиляции в низкоуровневый язык вроде ассемблера по любому нужно городить огород с преобразованием древесной формы в линейную и т.п.
А>> А что вообще может быть проще чем преобразование дерева в плоский код?
VD>Прямая интерпретация по АСТ, ваш КО.
Нет, это сложнее, и намного проще ошибиться. Переписывание тривиально и легко отлаживать, можно посмотреть всегда на промежуточный код на каждом уровне. Отладка интерпретатора дело крайне нетривиальное, и чем сложнее язык, тем оно хуже, тогда как сложность отладки компилятора со сложностью языка практически не повышается.
А>>Для стековой машины так и вовсе ничего кроме обхода вглубь не нужно, для регистровой есть пара тривиальных трюков, которые не намного сложнее тупого обхода.
VD>То-то в реальных компиляторах дотнета куча сложнейшего кода лепится. Одни зависимости между типами чего стоят.
А инспектировать типы, пардон, и в интерпретаторе придется. Если хочется с дотнетом взаимодействовать в полной мере, то без всей этой дряни не обойтись, но к компиляции это никакого отношения не имеет.
А>> Под контекстом я понимаю все то, что у нас в лексическом контексте — переменные, параметры, и т.д., и реализацию lookup во всем этом деле при интерпретации.
VD>Ну, дык модель и должна их все описывать.
Как?
VD>Ну, вот давай и сравним на практике.
Дал. Сравним?
VD>А зря. Модель может быть просто объектом. ДСЛ тупо заполняет объект нужной информацией, а вызов некоторого метода этого объекта выполняет интерпретацию.
И опять не понял. Какая разница, какой там у него интерфейс, мне интереснее, что там за неонка внутри, и как оно ей думает.
А>> Я только этим и занимаюсь. Всегда предпочту компилятор интерпретатору, так проще.
VD>Я как бы тоже. Но выводы у меня ровно обратные. Я если и предпочту компиляцию, то только по соображениям надежности и производительности. При этом я буду понимать, что с простотой я расстался намеренно.
Я до сих пор не могу представить, что может быть проще чем компиляция. Компиляция это переписывание кода по простым правилам. Интерпретация же требует уже программирования, требует Тьюринг-полного языка. Накосячить проще простого.
А>> Откуда уверенность, что "увижу"? За последние лет двадцать так и не увидел.
VD>И чем ты занимаешься, если не секрет?
Компиляторами, чем же еще.
VD>Я тебе кажется показал код из реальной задачей. Зачем спорить с очевидным?
Так я уже сказал, что этот реальный код написан неправильно. Поддерживать его было бы кошмаром, я бы лично не взялся.
VD>Тот кто выбирает компиляцию. Компилированный вариант тоже можно сделать медленным. Быстрее и ладно прокатывает только на очень примитивных задачах. А когда занимаешься разработкой генератора парсеров, то производительность получаемых парсеров становится критически важной фичей.
Вот уж скорость парсера крайне редко представляет какой либо интерес. Не для DSL, как минимум. Это только для ЯВУ с навороченными IDE важно, или для коммуникационных протоколов.
VD>>>Вот погляди. Это (включая все вложенные подкаталоги и файлы) — код связанный с генерацией кода для парсера.
А>> Плохо, очень нерационально написано.
VD>Умора, блин! Настоящий русский программист. Любой чужой код сразу кака.
Я не сказал что это кака. Я сказал, что это плохой подход и написано нерационально. Причем объяснил, где именно косяк.
А>> Могу даже объяснить, что там не так — нельзя сразу генерить код из языка настолько более высокого уровня в язык низкого уровня без нескольких промежуточных представлений.
VD>Какой ты молодец! И какой же промежуточный язык ты предложишь?
Может мне сразу взять и все это переписать? Как-то мотивации маловато. На вскидку я там целых три промежуточных представления могу выделить. Может несколько позже и опишу, какие именно, для низкого уровня мне еще не хватает понимания алгоритма. Для высокого уровня все очевидно — сахар слой за слоем раскрывать надо, а не весь сразу. И, кстати, то, что я плохо понимаю смысл кода, который там генерится, уже само по себе говорит за качество генератора. Это должно быть очевидным с первого взгляда.
А>>Если помнить об этой простой штуке, то компиляторы становятся тривиальными.
VD>Это довольно безответственный треп не подкрепленный никакими фактами или соображениями. VD>Давай, предложи промежуточный язык и объясни какие проблемы он решит.
Общий метод — каждый следующий промежуточный язык должен отличаться от предыдущего только в одном аспекте. И преобразование между ними должно быть тривиальным.
Например — язык с лексической областью видимости на одном уровне, и язык с гарантированно уникальными именами переменных на следующем уровне. Один проход, одно преобразование, тривиально для отладки и для понимания.
Конкретно для этого генератора парсеров пока не скажу, может позже, если время будет. Когда мне пришлось свой генератор парсеров писать (PEG) то представлений там было довольно много: BNF с сахаром, голый BNF с раскрытыми макросами, потом Trie, потом Trie с аннотациями, потом PEG, потом комбинаторы.
VD>В прочем, после рассказов про простоту генерации IL-а через SRE я уже не знаю каким из твоих слов верить. Как-то странно слышать про простоту генерации сразу низкоуровневого языка, а потом вдруг довольно здравую, но аморфную, мысль о необходимости еще какого-то там промежуточного языка.
А я где-то сказал, что я сразу генерю низкоуровневый язык?
А>>И, кстати, если писателям компиляторов не давать полноценного Тьюринг-полного языка, то они таких кошмаров и городить не станут, просто не смогут.
VD>А как же SRE как самый простой способ генерации кода? Ты уж определись, как то.
Я знаю людей, которые считают, что ничего кроме Coq и макроассемблера вообще не нужно. И они умудряются быстро и эффективно писать неплохие компиляторы. Так что я по сравнению с ними вовсе не так радикален.
И конечно же они генерят код не в один проход, а через множество промежуточных языков. Как я с SRE (см. решение выше, там тупая обертка над SRE, заметно упрощающая и генерацию кода и отладку промежуточных вариантов).
VD>Вот результат этого проекта и будет выдавать такой ДСЛ.
Такой DSL пишется один раз и потом используется. И написать его не проблема. А лучше вовсе использовать язык, где он уже есть (т.е. Haskell).
VD> А пока что его нет, приходится использовать тоже не плохие средства вроде АлгТД и паттерн-матчинга.
См. выше — там примитивная форма такого DSL сделана в несколько строк на коленке.
VD>В прочем, сложность тут отнюдь не в МП по модели. Он там в сущности примитивный. Сложность там как раз в оптимизациях и разного рода хитростях. Нужно сгенерировать код мемоизации, обеспечить возможность динамического расширения, выявления конфлитков, сгенерировать разный код для предикатов (он не возвращает значения и стало быть должен быт "легче") и для применения тех же правил без предикатов... В общем, много чего.
Ну вот, это уже готовое описание кучи последовательных промежуточных языков. Почему же там нет такой цепочки, почему там все в одну кучу?
VD>А вообще, вот это и есть отличный пример когда разговоры о великой силе ДСЛ-ей разбиваются о банальный факт того, что чтобы воспользоваться мощным ДСЛ-ем его сначана нужно сделать имеющимися средствами.
И это не проблема. Их можно делать инкрементально. Каждый следующий на DSL попроще. Особенно если язык достаточно мощный (Лисп или Haskell).
VD> Если эти средства C# или С++ то все вообще становится очень печально. Да и с более мощными инструментами тоже не все "фонтан". Появляется проблема курицы и яйца. Чтобы написать код ДСЛ-я для построения ДСЛ-ей нужно сначала написать этот код без ДСЛ-ей .
Не так уж они и плохи. DSL инкрементально наращивать можно даже в шарпе. Ну а в C++ это вообще стандартный подход, весь Boost такой.
Re[11]: на сколько сложно будет сделать интерпритатор Н2?
Здравствуйте, <Аноним>, Вы писали:
А> Вот уж скорость парсера крайне редко представляет какой либо интерес. Не для DSL, как минимум. Это только для ЯВУ с навороченными IDE важно, или для коммуникационных протоколов.
Так тут именно тот случай.
А> Я не сказал что это кака. Я сказал, что это плохой подход и написано нерационально. Причем объяснил, где именно косяк.
Да я сам знаю, где там косяки.
Но приходится делать, так как сделано.
Ибо нужна скорость.
А другие способы ее получить будут еще сложнее.
Если бы компилятор немерла был умнее или еще лучше JIT .НЕТ'а не был убог, что писец все было бы намного проще.
А> Может мне сразу взять и все это переписать? Как-то мотивации маловато. На вскидку я там целых три промежуточных представления могу выделить.
Какие?
Все что там нужно это чтобы немерле нормально код оптимизировал.
Но он не умеет.
Тогда вместо всей этой химии с возвратом значений через переменные просто бы возвращались вариантные типы данных.
И все было бы тривиально.
И оно было. В первых вариантах. Когда АСТ не генерировался.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[11]: на сколько сложно будет сделать интерпритатор Н2?
Ну, вот какая-то конкретика! Тут уже заявлениями не отделаешься.
VD>>Ты пишешь свою версию с использованием SRE, а я свою интерпретируемую. Можно использовать любые языки дотнета, любые библиотеки и фрэймворки.
А>Любые языки неинтересно, не спортивно. Только голый c#, только хардкор!
Еще как спортивно. Ты на C#, я на Немерле. Он же по-твоему от шарпа ничем не отличается .
А мог и F# взять. Да хоть Boo, на языки ведь ограничений не было.
А>Мой вариант: А>Main.cs: http://pastebin.com/YfEfPGuU А> И куски от сильно порезанного фреймворка,
Гы. Твой фрэймворк — это реализация встроенных ДСЛ-ей. Один для парсинга. А второй для генерации кода с помощью эмита.
Это уже не прямое использование эмита!
В прочем, вот мой вариант интерпретатора:
SymbolTable : Hashtable[string, double] = Hashtable();
/// Вот это весь код интерпретатора. Как говорится - сравните, а разницу оставьте себе :)private Eval(ast : CalcParser.Expr) : double
{
| Rounds.Ast(_, ast, _) => Eval(ast)
| Num.Ast(Number.Ast(number=num)) => double.Parse(ast.GetText(num))
| Neg.Ast(_, v) => -Eval(v)
| Add.Ast(e1, _, e2) => Eval(e1) + Eval(e2)
| Sub.Ast(e1, _, e2) => Eval(e1) - Eval(e2)
| Mul.Ast(e1, _, e2) => Eval(e1) * Eval(e2)
| Div.Ast(e1, _, e2) => Eval(e1) / Eval(e2)
| DefVar.Ast(id, _, expr) =>
def result = Eval(expr);
SymbolTable[id.GetText()] = result;
result
| Var.Ast(id) =>
try SymbolTable[id.GetText()]
catch { _ is KeyNotFoundException => throw InvalidOperationException($"Variable '$(id.GetText())' not defined.") }
| _ => assert(false);
}
Как видно он один фиг короче и понятнее. И это не смотря на то, что мне вообще не понадобилось создавать какие то там фрэймворки.
А вот полная реализация включая парсер, поддержку скобок, чисел с плавающей точкой, унарного минуса и обработку ошибок (которой у тебя вообще нет).
using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Parser;
using Nemerle.Imperative;
using System;
using System.Collections.Generic;
using System.Console;
using CalcParser;
[ParserGrammar(Options = EmitDebugSources,
grammar
{
any = ['\u0000'..'\uFFFF'];
space = '\n' | '\r' | [Zs] | '\t' | '\v' | '\f';
s : void = space*;
[StartRule, Ast(expr)] start : Ast = s expr+ !any;
digit = ['0'..'9'];
numberBody = digit+ ('.' digit+)?;
[Ast(number)] number : Ast = numberBody;
letter = ['A'..'Z', 'a'..'z', '_'..'_'] ;//[Lu, Ll, Lt, Lm, Lo, Nl];
letterOrDigit = letter | digit;
identifierBody = letter letterOrDigit*;
[Ast(Body)] Identifier : Ast = identifierBody s;
[StartRule, Ast()]
expr : Ast;
[Ast(id, eq, expr)] defVar is expr = Identifier '='s expr;
[Ast(id)] var is expr = Identifier;
[Ast(l, expr, r)] rounds is expr = '('s expr ')'s;
[Ast(num)] num is expr = number s;
[Ast(op, expr)] neg is expr = '-'s expr : 100;
[Ast(l, op, r)] add is expr = expr : 10 '+'s expr : 10;
[Ast(l, op, r)] sub is expr = expr : 10 '-'s expr : 10;
[Ast(l, op, r)] mul is expr = expr : 20 '*'s expr : 20;
[Ast(l, op, r)] div is expr = expr : 20 '/'s expr : 20;
}
)]
public abstract class CalcParser { }
module Program
{
SymbolTable : Hashtable[string, double] = Hashtable();
/// Вот это весь код интерпретатора. Как говорится - сравните, а разницу оставьте себе :)private Eval(ast : CalcParser.Expr) : double
{
| Rounds.Ast(_, ast, _) => Eval(ast)
| Num.Ast(Number.Ast(number=num)) => double.Parse(ast.GetText(num))
| Neg.Ast(_, v) => -Eval(v)
| Add.Ast(e1, _, e2) => Eval(e1) + Eval(e2)
| Sub.Ast(e1, _, e2) => Eval(e1) - Eval(e2)
| Mul.Ast(e1, _, e2) => Eval(e1) * Eval(e2)
| Div.Ast(e1, _, e2) => Eval(e1) / Eval(e2)
| DefVar.Ast(id, _, expr) =>
def result = Eval(expr);
SymbolTable[id.GetText()] = result;
result
| Var.Ast(id) =>
try SymbolTable[id.GetText()]
catch { _ is KeyNotFoundException => throw InvalidOperationException($"Variable '$(id.GetText())' not defined.") }
| _ => assert(false);
}
/// Функция запускающая парсер и выводящая значение или сообщения об ошибках.public EvalAndPrint(code : string) : void
{
def parser = CalcParser.GrammarImpl();
match (parser.ParseStart(code))
{
| None =>
// Парсинг прошел неудачно. Выводим сообщения об ошибках.
WriteLine($"Ошибка в: \"$code\"");
def (pos, tokens) = parser.Parser.GetErrors();
def (line, pos) = parser.ParsingSource.PositionToLineColumn(pos);
foreach (token in tokens)
WriteLine($" $line:$pos expected \"$(token.Name)\" in rule $(token.Rule.Grammar.Name).$(token.Rule.Name)");
| Some(CalcParser.Start.Ast(exprs)) =>
// Все ОК. Парсер вернул последовательность выражений (exprs).
// Интерпретируем их по очереди и возвращаем значение последнего выражения.try WriteLine(exprs.Fold(0.0, (expr, _) => Eval(expr)))
catch { | e => WriteLine(e.Message) } // если что выводим сообщение об рантайм-ошибке
| _ => assert(false);
}
}
Main(args : array[string]) : void
{
if (args.Length != 1) WriteLine("Usage: calc \"expressions ... \"");
else EvalAndPrint(args[0]);
}
}
Думаю не надо объяснять, что будет если ты действительно попытаешься сгенерировать код с использованием SRE напрямую.
Парсер просто ужасный. Найди себе что-нибудь по приличней. Или тупо пиши рекурсивные парсеры. Кода будет примерно столько же.
PMatching порадовал .
А>Сам компилятор — несколько строк.
Но больше интерпретатора и использует дополнительный код. Плюс в нем еще черт ногу сломит.
Про томрознутую эмуляцию паттерн-матчингя я вообще молчу. Твой компилятор будет работать медленнее моего интерпретатора.
А>Парсер естественно жирноватый, потому как это всего лишь c#, и потому что мне вообще обычно на парсеры плевать. Пусть меня побьют и заклюют, но мне синтаксиса JSON или XML хватает для многих DSL. Про Лисп и говорить нечего, там синтаксис и вовсе не нужен.
Ну, тут трудно не согласиться. С нашим парсером вообще вряд ли что сравнится .
А>Если выбирать какой попало язык, то можно было бы взять f# и получилось бы уже совсем не спортивно. Или вовсе найти один из многочисленных DSL-ей для компиляции DSL-ей под .NET. Например, находится такое (сам не пробовал, но DSL похож на scrap your boilerplate): http://bit.ly/I2LFdr
А>Если не под .NET, то я взял бы Clojure (и генерил бы байткод напрямую), ну а лучше всего, на данный момент мой наиболее предпочтительный вариант — Haskell с LLVM.
Да хоть что возьми создать компилятор короче интерпретатора ты не сможешь. Плюс еще придется тонну кода поддержки нафигачить, в то время когда простой интерпретатор делается в два счета.
С парсером у тебя тоже будет облом, так как наш ДСЛ самый мощный на сегодняшний день. Еще немного синтаксис подстрогаем, доведем до ума и будет просто конфетка.
VD>>Далее сравним количество кода и вообще траха возникшего при реализации.
А> Количество кода сравнивать надо только на одинаковых языках. Кроме количества надо сравнивать читабельность и поддерживаемость (например, насколько легко было бы расширить язык новыми возможностями).
Зачем на одинаковых? Я же тебе предложил выбрать любой. Читай самый подходящий с твоей точки зрения.
Читабельность — это да. Сравни .
Еще хорошо бы сравнить тот объем кода который был наколбасен в PMatching.cs и Emit.cs, а так же качество реализации.
А теперь давай капельку усложним задачу. Сделаем так чтобы выражения можно было вбивать в консоли и тут же выполнять. Причем чтобы переменные были общими. Объявленная ранее переменная должна быть доступна в дальнейшем.
Как думаешь, насколько генерация кода будет удобной и приемлемой для такого сценария?
VD>>Если твое решение окажется короче моего, то я сниму шляпу и признаю, что ты прав и компиляторы делать проще чем интерпретаторы.
А>По одной из ссылок выше как раз сравнивается компилятор в IL и интерпретатор, и компилятор при наличии навороченного DSL получается заметно проще.
Это какое-то кривое сравнения. Я кажется показал тебе код. По-моему очевидно, что парсер проще.
А> Код для запуска скомпилированного тоже лучше не считать, он обычно одинаковый для всех DSL, получается копипастой и не сокращается только из-за уродства SRE и недостаточной выразительности языка.
Ну, вообще-то у тебя там объем кода будет расти. В прочем, ОК. Сравниваем только сам компилятор и интерпретатор.
VD>>Для интерпретатора можно легко использовать динамическую типизацию. Так что систему типов особо и реализовывать не придется.
А> А для компилятора ее что, сложно использовать? Вовсе нет, проще чем для интерпретатора.
Сложнее. Но главное — бессмысленно. Разу уж мы компилируем, то нужно делать это качественно. А то получается, что в твоем решении и кода больше, и работает оно сильно медленее. Так зачем оно нужно то тогда?
VD>>А тут возникает вопрос... Если нам производительность не важна, то на фиг нам возиться с компиляцией и проблемами которая она вызывает? И интерпретатор становится лучшим выбором, так как просто и гибко (можно запускать в рантайме без проблем).
А> Затем, что компиляция проще интерпретации и проблем она не вызывает, проблемы она решает. Кроме того, даже неоптимальный компилятор все равно будет давать лучший результат чем даже очень сильно оптимизированный интерпретатор.
Ой не вижу этого. Код у тебя явно больше вышел. Надежность его никакая. Я пару раз получил ошибки из эмита или вообще из джита. Попробуй скормить своему компилятору вот это: "x = 42 + 2 * 4 x * y".
А> И я уж промолчу о том, что в большинстве случаев интерпретатор будет включать в себя и значительную часть компилятора.
Да я на код хотел посмотреть. Что мне с этих описаний то. Если там все просто, то кода должно быть ведь не много.
А>а один из лучших когда либо созданных.
Дык сравнивать надо простенькие с простенькими, или сложные со сложными.
А> Там весь контекст — переменные. Нет вложенных областей видимости. Так что интерпретатор лишь немного более сложный получается чем компилятор.
В интерпретаторе все это пойдет через один единственный параметр. Ты при компиляции его тоже будешь использовать. Нет никакой разницы использовать таблицу символов для компиляции или для интерпретации. Ну, будет их стек. Не проблема.
А> Да какое там вообще AST?
Да такое же как ты создал.
А>Плоская последовательность выражений. Никаких вложенных блоков. Не интересно. А вот чтобы с интерпретатором затрахаться как раз достаточно ввести, ну, допустим, лексические замыкания.
Ты и с компилятором при этом попотеешь немного. Вообще разницы нет никакой. В одном случае ты будешь эмулировать замыкания при компиляции, в другом при интерпретации.
А>И чтоб чистый-чистый интерпретатор был, без каких либо проходов компиляции (то есть, lambda lifting делать нельзя). Голый "обход AST", с корректной поддержкой контекста. Слабо?
А в чем проблема то? Ну, придется завести таблицы имен и таскать их стек в параметре.
В общем, опиши как ты себе видишь это синтаксически — посмотрим.
А>>> А что вообще может быть проще чем преобразование дерева в плоский код? VD>>Прямая интерпретация по АСТ, ваш КО.
А> Нет, это сложнее, и намного проще ошибиться.
Пока что все с точностью наоборот.
А> Переписывание тривиально и легко отлаживать, можно посмотреть всегда на промежуточный код на каждом уровне.
Та же фигня с интерпретатором только метаязыка нет (не нужен он). А смотреть можно на колстекр. Там, если не императивить без надобности, как раз все лежать будет.
А> Отладка интерпретатора дело крайне нетривиальное, и чем сложнее язык, тем оно хуже, тогда как сложность отладки компилятора со сложностью языка практически не повышается.
Согласен, что чем сложнее код, тем сложнее отладка. Но интерпретатор тут не причем. Это справедливо для любого кода.
Короче, ставь задачу. Попробуем. Это даже интересно.
Но хочу заметить, что мы исходно говорили о ДСЛ-ях. И разговор о компиляции / интерпретации тоже в их контексте зашел. Так вот ДСЛ-и частенько бывает очень простыми. Так что твои аргументы не работают даже, если они окажутся верными. В чем я сильно сомневаюсь.
А> А инспектировать типы, пардон, и в интерпретаторе придется. Если хочется с дотнетом взаимодействовать в полной мере, то без всей этой дряни не обойтись, но к компиляции это никакого отношения не имеет.
В интерпретаторах типы по сути фиксированные. Вместо классов — хэш-таблицы. Встроенные типы вообще в общее объеденение загоняются. Так что в итоге получается просто.
А>>> Под контекстом я понимаю все то, что у нас в лексическом контексте — переменные, параметры, и т.д., и реализацию lookup во всем этом деле при интерпретации.
VD>>Ну, дык модель и должна их все описывать.
А> Как?
Да молча. Ты почему-то под языком понимаешь что-то сложное. А ДСЛ-и зачастую быват очень примитивными. Их модели можно описать 1-3 классами.
VD>>Ну, вот давай и сравним на практике.
А> Дал. Сравним?
Валяй!
VD>>А зря. Модель может быть просто объектом. ДСЛ тупо заполняет объект нужной информацией, а вызов некоторого метода этого объекта выполняет интерпретацию.
А> И опять не понял. Какая разница, какой там у него интерфейс, мне интереснее, что там за неонка внутри, и как оно ей думает.
"Неонка" там обычный класс или их набор. ДСЛ тупо конфигурирует класс, а далее вызвается некий метод типа Посчитать(). И все.
VD>>И чем ты занимаешься, если не секрет?
А> Компиляторами, чем же еще.
Какими?
VD>>Я тебе кажется показал код из реальной задачей. Зачем спорить с очевидным?
А> Так я уже сказал, что этот реальный код написан неправильно. Поддерживать его было бы кошмаром, я бы лично не взялся.
Ты извини, но это высосанное из пальца утверждение. К тому же код поддерживается дай дорогу. Он столько рефакторингов претерпел, что многим и не снилось.
А> Вот уж скорость парсера крайне редко представляет какой либо интерес. Не для DSL, как минимум. Это только для ЯВУ с навороченными IDE важно, или для коммуникационных протоколов.
Это если ты в бирульки играешь, то это так. А если парсер используется в огромном проекте, то скорость важнеший фактор. Для той же IDE скорость очень важна. Расширяемые языки крайне сложно парсить инкрементально. Если же парсер шустрый, то можно не заморачиваться с инкрементальностью.
Парсер ведь не только для ДСЛ-ей используется. Да и ДСЛ-кода в проекте может быть тонна.
А> Я не сказал что это кака. Я сказал, что это плохой подход и написано нерационально. Причем объяснил, где именно косяк.
ОК. Опиши что бы ты улучшиш. Только не абстрактно, плиз. А то всегда легко сказать, что ваш код дерьмо, я написал бы лучше. Раз знаешь как лучше, то не составит труда описать за счет чего это лучше будет.
VD>>Какой ты молодец! И какой же промежуточный язык ты предложишь?
А> Может мне сразу взять и все это переписать?
Если получится как в том фрэмворке для парсинга что ты привел, то лучше не надо.
Если серьезно, то будет достаточно общих идей. Ты вот заикнулся про промежуточную модель. Вот опиши как ты ее представляешь и что она даст.
А> Как-то мотивации маловато. На вскидку я там целых три промежуточных представления могу выделить.
Ну, вот опиши их в общих чертах. А то я жуть как не люблю общих слов. На словах все круты как вареные яйца. А так глядишь и правда интересную мысль подкинешь.
А> Может несколько позже и опишу, какие именно, для низкого уровня мне еще не хватает понимания алгоритма.
Это не проблема. Тут мы подскажем.
В прочем, не очень ясно как можно не понимая алгоритм видеть как его улучшить.
А>Для высокого уровня все очевидно — сахар слой за слоем раскрывать надо, а не весь сразу.
Не. Это я тебе и сам скажу. Только вот практика есть практика. У нас есть модель предметной области. И есть задача — сгенерировать максимально быстрый код на ЯОН. ЯОН не простой, а расширяемый, так что казалось бы есть простор для фантазии, но важна скорость парсинга. По сему приходится плевать на абстракции и генерировать тупейший код.
Лично я не очень представляю что тут может дать промежуточная модель и как она может выглядить.
Ну, дык поделись опытом, если правда есть что сказать.
А>И, кстати, то, что я плохо понимаю смысл кода, который там генерится, уже само по себе говорит за качество генератора. Это должно быть очевидным с первого взгляда.
Это так же может говорить о двух вещах:
1. Плохо знаешь язык в который происходит генерация.
2. Генерируется не просто прямолинейный код, а код с оптимизациями.
В прочем, я вот поглядел твой код комапилятора простенького языка и тоже не все места понятны. Хотя я то шарп знаю с его рождения. Сдается мне ты мой код интерпретатора и парсера поймешь куда лучше, чем я твой. И это на примитивной задаче. А там задача очень не простая. Парсер реально хайтечный.
А> Общий метод — каждый следующий промежуточный язык должен отличаться от предыдущего только в одном аспекте. И преобразование между ними должно быть тривиальным.
Общий метод я тоже знаю. Вот с применением его на практике бывают проблемы. Возможно я слишком упираюсь в оптимальность результата, но в конкретном случае мне трудно придумать хорошую промежуточную модель.
Есть идеи? Поделись!
А> Например — язык с лексической областью видимости на одном уровне, и язык с гарантированно уникальными именами переменных на следующем уровне. Один проход, одно преобразование, тривиально для отладки и для понимания.
С уникальностью имен проблем нет. Микросистема немерла в этом помогает. Проблема именно в преобразовании модели в эффективный код.
А> Конкретно для этого генератора парсеров пока не скажу, может позже, если время будет. Когда мне пришлось свой генератор парсеров писать (PEG) то представлений там было довольно много: BNF с сахаром, голый BNF с раскрытыми макросами, потом Trie, потом Trie с аннотациями, потом PEG, потом комбинаторы.
PEG — это формализм. А важны алгоритмы. Этот парсер далеко не тупой пег. Тут смешаны несколько алгоритмов и привнесено кое что от себя. Важной фичей алгоритма является тотальная расширяемость.
VD>>В прочем, после рассказов про простоту генерации IL-а через SRE я уже не знаю каким из твоих слов верить. Как-то странно слышать про простоту генерации сразу низкоуровневого языка, а потом вдруг довольно здравую, но аморфную, мысль о необходимости еще какого-то там промежуточного языка.
А> А я где-то сказал, что я сразу генерю низкоуровневый язык?
Я тебя именно так понял. Ты же не сказал, что предлагаешь использовать ДСЛ для инкапсуляции работы с SRE. Потому и спрашиваю. А то в одном случае много уровней, а в другом сразу SRE.
А> И конечно же они генерят код не в один проход, а через множество промежуточных языков. Как я с SRE (см. решение выше, там тупая обертка над SRE, заметно упрощающая и генерацию кода и отладку промежуточных вариантов).
Ага, видел. Только она еще накладных расходов добавляет и не безопасна, так как везде объекты да тайп-чеки. А в шарпе это чревато.
VD>>Вот результат этого проекта и будет выдавать такой ДСЛ.
А> Такой DSL пишется один раз и потом используется. И написать его не проблема. А лучше вовсе использовать язык, где он уже есть (т.е. Haskell).
И где же такой ДСЛ? А? Он никому был не нужен?
Все дело в качестве. Написать наколенную поделку действительно не сложно. В Хаскеле, да и где угодно ничего аналогичного нет в помине. В этот проект вложено уже несколько лет исследований. Мы перерыли все что было в этой области и нашли как соеденить перспективные идеи.
В общем, советую тебе не судить пока не разобрался.
VD>> А пока что его нет, приходится использовать тоже не плохие средства вроде АлгТД и паттерн-матчинга.
А> См. выше — там примитивная форма такого DSL сделана в несколько строк на коленке.
Ты не понимаешь о чем говоришь. Потому и делаешь такие заявления. То что ты сделал и есть примитив на коленке. Это же реально крутейший генератор парсеров. Нем нет упрощений и компромиссов.
Мы планируем сделать профессиональность средства коммерческого качества. Пока что там много чего нужно доделать. Но уже то что есть очень внушительно.
Реализация включает:
* Хитрый алогоритм позволяющий без проблем разбирать любые ЯП известные на сегодня. Причем без приседаний и извращений.
* Поддерживает динамическую расширяемость и модульность.
* Не смотря на предыдущие пункты порождает быстрые парсеры (сравнимые с рукописными по скорости). Как ПЕГ без лексерный, но не имеет проблем связанных с оператором приоритетного выбора.
* Предоставляет (точнее будет, так как тема не закрыта) средства для восстановления после ошибок.
* Высокоуровневый. Поддерживает силу связывания, предикаты.
* Собирает всю информацию о коде. Это позволяет по нему реализовывать все сервисы IDE.
В общем, в нем решены все проблемы которые только можно найти в современных парсерах.
Кроме того он будет так же (в процессе работы) генерировать код необходимый для работы с полученым деревом разбором с помощью квази-цитат и паттетн-матчинга. Это позволит упростить генерацию и распознование кода.
Сюда же будет прикручен ДСЛ для типизации (сейчас он тоже в проработке). Так что можно будет получить полностью типизированное дерево разбора и нарисовать по нему высокоуровневый код генерации более низкоуровневого языка.
Вот в этом месте есть некоторый вопрос. Возможно разумно было бы втиснуть сюда описание семантической модели и преобразование в оную. Тут есть над чем подумать.
Короче, на наколенную поделку которую можно создать за пять минут этот проект точно не тянет. Так что огромная просьба не повторять, что это можно было бы создать за... в будуещм. Это несколько разряжает.
А> Ну вот, это уже готовое описание кучи последовательных промежуточных языков. Почему же там нет такой цепочки, почему там все в одну кучу?
Наверное у нас опыта не хватает. Покажи класс!
VD>>А вообще, вот это и есть отличный пример когда разговоры о великой силе ДСЛ-ей разбиваются о банальный факт того, что чтобы воспользоваться мощным ДСЛ-ем его сначана нужно сделать имеющимися средствами.
А> И это не проблема. Их можно делать инкрементально. Каждый следующий на DSL попроще. Особенно если язык достаточно мощный (Лисп или Haskell).
Хаскель? Гы-гы.
Хаскель пока что рядом не валялся. Сделать тут что-то инкременатально не так то просто. Парсер в ближашее время будет переведен на бутсрап. Но для генерации кода особо ничего умнее пока придумать нельзя. Там и так весьма высокоуровневое решение аналогичное Лиспу.
В общем, рассуждать о ДСЛ-ях куда сложнее чем делать действительно мощные ДСЛ-и.
Немерл сам по себе позволяет делать многое. Но нам хочется бескомпромиссного (во всех отношениях) решения.
VD>> Если эти средства C# или С++ то все вообще становится очень печально. Да и с более мощными инструментами тоже не все "фонтан". Появляется проблема курицы и яйца. Чтобы написать код ДСЛ-я для построения ДСЛ-ей нужно сначала написать этот код без ДСЛ-ей .
А> Не так уж они и плохи. DSL инкрементально наращивать можно даже в шарпе. Ну а в C++ это вообще стандартный подход, весь Boost такой.
Это лажа а не ДСЛ-и. Как уже сто раз говорил — все дело в качестве.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: на сколько сложно будет сделать интерпритатор Н2?
От:
Аноним
Дата:
17.04.12 19:14
Оценка:
А>>Мой вариант: А>>Main.cs: http://pastebin.com/YfEfPGuU А>> И куски от сильно порезанного фреймворка,
VD>Гы. Твой фрэймворк — это реализация встроенных ДСЛ-ей. Один для парсинга. А второй для генерации кода с помощью эмита.
Естественно.
VD>Это уже не прямое использование эмита!
Никто и не собирался его использовать напрямую, извращенцев нет.
VD>В прочем, вот мой вариант интерпретатора:
Ладно — позже пришлю вариант компилятора на Nemerle, раз уж мою игру в хардкор никто поддержать не захотел.
VD>Как видно он один фиг короче и понятнее. И это не смотря на то, что мне вообще не понадобилось создавать какие то там фрэймворки.
А за 30 минут не-ужасный и не напишешь.
VD> Или тупо пиши рекурсивные парсеры. Кода будет примерно столько же.
А это и есть тупо рекурсивный, с комбинаторами как в Parsec.
VD>PMatching порадовал .
А что делать, если в шарпе нет ни черта полезного?
VD>Про томрознутую эмуляцию паттерн-матчингя я вообще молчу.
Она не такая уж и тормозная. Конечно с метапрограммированием можно намного быстрее, но его в шарпе нет, приходится интерпретаторы (столь тут любимые народом) городить на ровном месте.
VD> Твой компилятор будет работать медленнее моего интерпретатора.
Там один только jit будет медленнее всего остального работать. Это не важно.
VD>Ну, тут трудно не согласиться. С нашим парсером вообще вряд ли что сравнится .
Хорошие реализации GLR или Packrat не хуже будут.
А>>Если выбирать какой попало язык, то можно было бы взять f# и получилось бы уже совсем не спортивно. Или вовсе найти один из многочисленных DSL-ей для компиляции DSL-ей под .NET. Например, находится такое (сам не пробовал, но DSL похож на scrap your boilerplate): http://bit.ly/I2LFdr
А>>Если не под .NET, то я взял бы Clojure (и генерил бы байткод напрямую), ну а лучше всего, на данный момент мой наиболее предпочтительный вариант — Haskell с LLVM.
VD>Да хоть что возьми создать компилятор короче интерпретатора ты не сможешь.
Посмотри ссылку выше ( http://bit.ly/I2LFdr ) — там куча вариантов интерпретаторов и компиляторов. Компиляторы все короче (кроме компилятора в регистровую машину). В том числе и компилятор в IL. Я как раз оттуда архитектуру свистнул, только вот язык реализации крайне неудачно выбрал. Зато хардкор!
VD> Плюс еще придется тонну кода поддержки нафигачить, в то время когда простой интерпретатор делается в два счета.
Когда есть метапрограммирование как в Лиспе, то компилятор все же намного проще, см. тот пример.
VD>С парсером у тебя тоже будет облом, так как наш ДСЛ самый мощный на сегодняшний день. Еще немного синтаксис подстрогаем, доведем до ума и будет просто конфетка.
Я уже говорил, что как раз синтаксис мне интересен менее всего. Не вижу в нем никакого смысла. Да, я лиспер.
VD>Зачем на одинаковых? Я же тебе предложил выбрать любой. Читай самый подходящий с твоей точки зрения.
Ну так это просто не интересно. Мне бы мотивации не хватило что-либо делать. Хардкор интереснее.
VD>Еще хорошо бы сравнить тот объем кода который был наколбасен в PMatching.cs и Emit.cs, а так же качество реализации.
Это для компенсации уродства шарпа. Пишется один раз и потом используется.
VD>А теперь давай капельку усложним задачу. Сделаем так чтобы выражения можно было вбивать в консоли и тут же выполнять. Причем чтобы переменные были общими. Объявленная ранее переменная должна быть доступна в дальнейшем.
А это как раз уже не интересно — делает компиляцию бесполезной. Конечно, в Лиспе или любом другом языке с инкрементальной компиляцией это будет все равно намного проще чем с интерпретацией, но под .NET не существует приличных Лиспов. Могу под JVM на Clojure сделать.
А>>По одной из ссылок выше как раз сравнивается компилятор в IL и интерпретатор, и компилятор при наличии навороченного DSL получается заметно проще.
VD>Это какое-то кривое сравнения. Я кажется показал тебе код. По-моему очевидно, что парсер проще.
Я про Лисп говорю, там очевидно проще.
А>> А для компилятора ее что, сложно использовать? Вовсе нет, проще чем для интерпретатора.
VD>Сложнее. Но главное — бессмысленно. Разу уж мы компилируем, то нужно делать это качественно. А то получается, что в твоем решении и кода больше, и работает оно сильно медленее. Так зачем оно нужно то тогда?
Все равно быстрее интерпретатора будет. Потому все приличные интерпретаторы нынче и пользуются динамическими VM.
VD>Ой не вижу этого. Код у тебя явно больше вышел. Надежность его никакая. Я пару раз получил ошибки из эмита или вообще из джита. Попробуй скормить своему компилятору вот это: "x = 42 + 2 * 4 x * y".
Ну да, облажался. Не люблю парсеры. Интерпретатор в моем исполнении на шарпе точно так же не работал бы, проблема не в кодогенераторе.
А>> И я уж промолчу о том, что в большинстве случаев интерпретатор будет включать в себя и значительную часть компилятора.
VD>Да ну? Где? Я тебе ведь интерпретатор показал.
Язык слишком примитивный, в один ход исполняется.
А>> Это компиляторы C: А>> http://bit.ly/HQFKLu А>> http://bit.ly/12Tufm
А>> http://bit.ly/kt4kR — и интерпретатор там не "хреновый",
VD>Да я на код хотел посмотреть. Что мне с этих описаний то. Если там все просто, то кода должно быть ведь не много.
Ага, так его и есть не много. Качай и смотри. tcc вообще крошечный и супер-быстрый. Его даже для вот таких извращений используют: http://bit.ly/5yc3Lx
VD>В интерпретаторе все это пойдет через один единственный параметр.
Только если нет лексической области видимости. Только для самых тупых языков.
А>> Да какое там вообще AST?
VD>Да такое же как ты создал.
Не интересный язык. Примитивный.
А>>Плоская последовательность выражений. Никаких вложенных блоков. Не интересно. А вот чтобы с интерпретатором затрахаться как раз достаточно ввести, ну, допустим, лексические замыкания.
VD>Ты и с компилятором при этом попотеешь немного.
Не-а. Lambda lifting делается тривиально.
А>>И чтоб чистый-чистый интерпретатор был, без каких либо проходов компиляции (то есть, lambda lifting делать нельзя). Голый "обход AST", с корректной поддержкой контекста. Слабо?
VD>А в чем проблема то? Ну, придется завести таблицы имен и таскать их стек в параметре.
Намекаю — таскать в две стороны надо, вниз по AST и вверх. Чтоб в любом месте был список свободных и связанных пременных.
VD>В общем, опиши как ты себе видишь это синтаксически — посмотрим.
Да хотя бы чистое лямбда-исчисление.
VD>Короче, ставь задачу. Попробуем. Это даже интересно.
Ok, по остальным пунктам завтра отвечу — после того, как разберусь в генераторе парсеров.
VD>Но хочу заметить, что мы исходно говорили о ДСЛ-ях. И разговор о компиляции / интерпретации тоже в их контексте зашел. Так вот ДСЛ-и частенько бывает очень простыми. Так что твои аргументы не работают даже, если они окажутся верными. В чем я сильно сомневаюсь.
Именно, что очень простыми. И компилируются в одно простое переписывание. Для того и нужны метаязыки.
А>> А инспектировать типы, пардон, и в интерпретаторе придется. Если хочется с дотнетом взаимодействовать в полной мере, то без всей этой дряни не обойтись, но к компиляции это никакого отношения не имеет.
VD>В интерпретаторах типы по сути фиксированные. Вместо классов — хэш-таблицы.
Если нужно взаимодействие с .NET — то не выйдет. А если оно не нужно, то и с компилятором мучаться не придется.
VD>Хаскель? Гы-гы.
VD>Хаскель пока что рядом не валялся.
В Хаскеле есть scrap your boilerplate. В Nemerle аналога нет (хотя сделать было бы элементарно).
Re[13]: на сколько сложно будет сделать интерпритатор Н2?
Здравствуйте, Ziaw, Вы писали:
Z>Все равно все приходится выразить в примитивах процессора. Интерпретатор в лоб написать проще, да. Но нормальные интерпретаторы имеют сложность не меньше чем компиляторы. Просто там проблемы другие. Возьмем lua, python или v8 и сравним, например, с D/OCaml/Coffeescript (дада, последний тоже компилятор).
Это не совсем так. В теории написать интерпретатор компилирующего типа сложнее, чем компилятор, так как ты выполняешь три задачи (парсер, компилятор и виртуальная машина) вместо двух (парсер и компилятор). Но на практике интерпретатор — проще.
Тебе конечно приходится компилировать код в инструкции процессора, но есть одна тонкость — это *твой* процессор, созданный специально для твоего языка. Помимо низкоуровневых инструкций он может также поддерживать высокоуровневые, например, для поддержки ООП (как Мсил) или для ФП. Это *нереально* упрощает компиляцию. Когда ты берешь существующую машину, то там не просто не будет удобных высокоуровневых инструкций, но для реализации ряда фич придется сильно выкручиваться.
Настоящий русский программист. Любой чужой код сразу кака. 
.
.
