Здравствуйте, WolfHound, Вы писали:


WH>Твой LL(k) на левой рекурсии тоже сдохнет.

Ммм... LL(к) — это и есть грамматика без левой рекурсии. За то ее и любят писатели компиляторов. Если при построении ДКА получаем конфликт, то применяем один из методов устранения левой рекурсии или факторизацию.

WH>Так что тут комбинаторы не отстают.
WH>Но они очень гибкие. И это свойство очень ценно, когда нужно что-то по быстрому накатать.

Т.е. не более чем для экспериментов по отладке грамматики? Или же можно так и оставлять для продакшн кода?

WH>Но для серьезной работы они конечно не годяться.
WH>Как и рукопашный LL(k) тем более на С.
WH>Это же вообще застрелиться можно.

Да вроде автоматическое построение автомата для LL(1) идет как одна из лаб на 3-м курсе обучения. Не? Приведение грамматики к LL(к), а еще лучше к LL(1) — ИМХО отличная стадия работы перед началом кодирования любого парсера. Все-таки, эффективность LL(к) того стоит.

Здравствуйте, hardcase, Вы писали:


H>"Туда" я тоже смотрел Посему резюмирую:

H>1) работает лишь для структур из того же компилируемого модуля,

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

Заметь, что небольшие АлгТД чаще всего объявляют как объединение мини-туплов, а это идеальный вариант для исполнения в предложенной технике.

H>2) работает без наследования,

как и в C#, и никто не жалуется.

H>3) затруднено использование из C#.

Был дан пример IIOP.Net, который генерит размеченные объединения с безопасным для дотнетных языков интерфейсом. Когда-то давно я им как раз на эту тему патчи слал.

H>Я считаю что этот слишком специфический случай, лучше поддержать макробиблиотекой и активными паттернами.

Э нет. value-types имеют специфическую поддержку средой исполнения. Именно до нее охота достучаться.

Здравствуйте, VladD2, Вы писали:


VD>Выделение отдельных стадий и есть способ держать сложность в разумных пределах. Ведь сложность имеет привычку перемножаться. Засунь оптимизацию в парсер и кирдык. А кроме оптимизации есть еще куча стадий обработки.

Слушай, может я тут с другой планеты. Приведенный код — это и есть сложность, на твой взгляд? Просто мне подобное приходилось делать в разных проектах более 5-ти раз (точно уже и не вспомню), и как-то малость обыденно. И выделения регулярного подмножества пару раз для парсеров EDI-форматов в т.ч. Там парсеры строятся динамически по описанию, а док-ты бывают по многу мег, и без этой фичи работало в 2-3 раза хуже. Грамматика в общем виде с неустранимой левой рекурсией (LL(к), где К зависит от конкретного описания структуры и может быть неограниченно), но имеет довольно протяженные "куски", хорошо разбираемые ДКА. Вот и приходилось комбинировать техники разбора.

Здравствуйте, vdimas, Вы писали:

V>Слушай, может я тут с другой планеты. Приведенный код — это и есть сложность, на твой взгляд?

Пока он отделен от остального кода — нет. Но как если смешать его с другим не сложным кодом, то на выходе получится неприемлемая сложность.

Более обобщенно: Обычно все просто когда смотришь на аспекты проблемы по очереди. Но все сложно кода они смешиваются.

V> Просто мне подобное приходилось делать в разных проектах более 5-ти раз (точно уже и не вспомню), и как-то малость обыденно. И выделения регулярного подмножества пару раз для парсеров EDI-форматов в т.ч. Там парсеры строятся динамически по описанию, а док-ты бывают по многу мег, и без этой фичи работало в 2-3 раза хуже. Грамматика в общем виде с неустранимой левой рекурсией (LL(к), где К зависит от конкретного описания структуры и может быть неограниченно), но имеет довольно протяженные "куски", хорошо разбираемые ДКА. Вот и приходилось комбинировать техники разбора.

Ну, вот изучи и попользуйся PegGrammar... и с большой вероятностью оценишь эту вещь по достоинству. Это я так мягко выражаюсь, чтобы не оскорбить тебя фразами вроде "поймешь что потратил много времени в своей жизни зря" .

Здравствуйте, VladD2, Вы писали:

VD>Выдумки я твои пропустил. Обсуждать их не вижу никакгого смысла.

Ну нет, так нет.

ГВ>>Угу, спасибо за объяснение. Почему-то ничего нового для меня тут не прозвучало. Да, я действительно не придал значения локально связанным именам, но, в общем, на мой вывод (и на иллюстрацию) это никак не влияет.
VD>Ну, есссено! Только код что тебе привели компилируется и работает. И более того, работает очень шустро. А твой — это выдумка которая никогда не заработает. Вот и вся разница. Так что в деталях как всегда кроется черт.

Конечно, не заработает. На фига мне PEG-парсер? Хотя, если вдруг понадобится...

ГВ>>Кого обманываю и в чём?
VD>Приведением кода который по твоим словам аналогичен, а на практике является полной фигней.

ГВ>>Ясно, спасибо. Собственно, этого я и ждал (хотя надеялся на чудо) — да, контролируется полнота проверки по всем возможным вариациям данного АлгТД, но никак не его сочетаний.

VD>Ну, почему же? Убери вхождения:
VD>

VD>        | Not(rule)                     => Rule.Not(r.Location, optimize(rule))
VD>        | And(rule)                     => Rule.And(r.Location, optimize(rule))
VD>

VD>и компилятор проверит те что есть и выдаст предупреждения для каждого не покрытого случая. Если ты хотя бы одино из вхождений не укажешь будет сообщение. А укажешь все — не будет.

М-м-м... Разве такое поведение компилятора будет вызвано не тем, что в типе Rule прямо объявлено:

    | Not            { rule : Rule; }
    | And            { rule : Rule; }

?

ГВ>>Пожалуй, что мне теперь стоит зацепиться за твою фразу: "...что match-и обрабатывают все возможные сочетания" и поднять шум о том, какой ты бессовестный обманщик и как вводишь в заблуждение своих наивных слушателей.
VD>Ну, попробуй. Авось в процессе еще немного в тему въедешь .

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

ГВ>>Короче говоря, порядок перебора совпадений — "сверху-вниз" в порядке перечисления. В принципе, схоже с пролог-машиной, только там учитывается порядок занесения предикатов в базу данных. Правила перебора совпадают с точностью до деталей реализации вычислительной среды.

VD>Ну, в прологе механизм по круче. Там тот же ПМ, но на базе унификации. В конце сопоставления обе стороны унифицируются.

Угу, покруче в каком-то смысле. Понятно теперь, почему ПМ для меня не новость? И ни для кого не новость, кто знаком с Прологом.

VD>МП из ФЯ по слабее, но за то сильно шустрее. В результате получается очень эффективный код. Такой же если бы это дело писалось вручную на базе низкоуровневых средств.

VD>Но в общем, механизм действительно похожий на прологовский. Разница только в том, что он работает только в одну сторону.

Ну да, правильно, потому что предназначен для других вещей — не только для поиска набора унификаций.

VD>>>>>Так что описанная выше прямая трансляция является плохим стилем. Стало быть ее, по уму, нужно заменить на использование паттерна посетитель. Но как только ты это сделашь распознование вложенных паттернов (Not вложенный в Not, как в данном примере) превратится в мучение. Кода станет уже не в 5, а в 10-20 раз больше.
ГВ>>>>Влад, ты когда с самим собой разговариваешь, клавиатуру в сторону отодвигай. При чём тут паттерн "посетитель"?
VD>>>При том, что он описывает список веток которые нужно посещать и как и ПМ гарантирует, что ты не забудешь посетить их все.

ГВ>>Ценой распыления аналитического кода по всем классам?
VD>У меня закрадываются сомнения в том, что ты знаешь что такое паттерн посетитель.

Объясни, что ты имеешь в виду в данном контексте?

ГВ>>Ну, я не спорю, субъект с тяжёлым синдромом ООП головного мозга способен и на такое ради "гарантий". Только зачем болезнь выдавать за правило?
VD>Ты видимо очень крут. Но вот все компиляторы и системы обработки деревьев выражений (включая LINQ) создаваемые на ООЯ почему-то всегда реализуют Посетителя для своих структур. Видимо ООП головного мозга поразил всех окружающих. И меня в том числе. В R# я тоже его реализовывал. Правда средствами метапрограммирования, так что это не было так уж многословно.

Всё зависит от контекста. Если набор типов изначально не ограничен, как, например, ограничен набор вариаций для Rule, то "посетитель" может оказаться уместным. Но мы, вроде как, обсуждаем другой случай — Rule имеет строго определённый набор вариаций.

VD>>>Посетитель наилучший способ из имеющихся в арсенале ООП. Код обработки выделяется в одном месте. Есть возможность гарантировать, что посещены все ветки. Можно добавлять другие обработки не ломая уже существующие и не вводя тонны методов (по одному на каждую ветку).
ГВ>>Хм. Зачем ты так рьяно защищаешь такое убогое применение ООП?
VD>Я? Я его не защищаю. Но в арсенале ООП и ИП дугих средств нет. Точнее те что есть еще хуже. Уж лучше проиграть в обхеде кода посетителя, но потом не иметь тех проблем что можно огрести без него.

Какие это проблемы можно без него огрести, например, в коде транслятора? Забыть, что ли, switch/if вставить там, где он нужен? Так это, прости меня, детский сад, право слово. Корректность компилятора контролируется наборами тестов, а не языком реализации. Да и, собственно, ветку в ПМ тоже можно запросто "заглушить".

ГВ>>Ну, я как бы в курсе твоего любимого метода критики — взять нечто идиотское, реализованое на языке X и на этом основании заклеймить весь язык X, но это не совсем чистоплотно, не находишь?
VD>Если ты считаешь этот паттерн идиотским, то или ты его не понимаешь, или ты освоил ПМ и понимаешь, что Посетитель жалкое его подобие (частный случай).

Ну, в данном контексте другого применения Посетителю, кроме идиотского я придумать не могу. Поясню:

class Rule {
  virtual Rule *optimize() = 0;
};

class AndRule : public Rule {
  virtual Rule *optimize() {
    // "Самооптимизация" And либо что-то в этом духе:
    return host->optimizeAnd(this);
  }
};

Вполне возможно, что ты видишь другие варианты.

VD>>>Если тебе это не очевидно, я не виноват.
ГВ>>Ты понимаешь, в чём проблема, я переболел парадигмами и прочими идеологиями уже довольно давно.
VD>Да я заметил. Жаль что это случилось чуть раньше чем ты освоил их все.

Я? Да ну что ты, я ни одной так и не освоил, мне наука освоения парадигм программирования как неких цельных артефактов не под силу by design — не умею я бессмысленные вещи осваивать.

ГВ>> Поэтому то, о чём ты говоришь, мне очевидно, но очевидно ещё и то, что сейчас я (и не только я) без веских причин так не сделаю, чтобы там ни тарахтели разнообразные ООП-пуристы и прочие, сдвинутые на спасении мира посредством чистоты парадигмы.
VD>Я тебе назвал минимум три причины. Тебя не волнует дальнейшая поддержка кода? Тогда можно их игнорировать.

Э-э-э... А где они перечислены? Не ткнёшь пальцем?

ГВ>>Честно, мне плевать, как код реализации проецируется на некий идеал, взятый из той или иной химеры (aka парадигмы), я руководствуюсь вполне локальными соображениями.
VD>Да мне тоже. Лишь бы он был рабочим, простым и легким в поддержке.

Ну вот видишь, к чему тогда паттерн Посетитель там, где цепочка if-ов покрывает потребности без выкрутасов?

VD>Но у этой задачи есть только три решения. Посетитель, ПМ и неправильное. Последнее на первый взгляд выглядит разумно и даже порой красиво, но на самом деле это мина замедленного действия. Отложенные грабли.

Не, не так. У задачи подбора по структурному паттерну есть много решений, все они так или иначе связаны с перебором. ПМ, Посетитель, if/switch — это возможные реализации, только у ПМ реализация самого перебора неявная. Ну а оптимизация перебора может выполняться как вручную (скажем, подходящей декомпозицией), так и реализовываться компилятором (например, хэш где-нибудь вычислять). Впрочем, хэш можно и явно вычислять.

ГВ>>Я не спорю с тем, что ПМ полезен, но это далеко не то, ради чего стоит пускаться во все тяжкие (читай, непременно менять язык реализации и т.п.).
VD>Ну, это мнение того кто сам на практике это самое МП не использовал. Я так понимаю Пролог ты ведь тоже на практике не используешь?

Мимо. Не часто, но использую.

VD>А вот среди тех кто попользовался ПМ бытует другое мнение — что языки не поддерживающие ПМ сразу проигрывают тем что поддерживают. У многих просто ломка начинается когда они вынуждены возвращаться на язык без ПМ.

Меня их мнение не волнует, как и ломка. Забегая вперёд, я понимаю о чём идёт речь, когда люди говорят о "ломке" при переходе от одного языка к другому, и сам её испытывал некогда, но не считаю эту причину, в общем, сколь-нибудь существенной. Куда как сильнее "ломка" от осознания бессмысленности замены одного средства разработки на другое, когда, например, ясности с постановкой задачи как не было, так и нет. Или, скажем, когда решение задачи упирается в её теоретическую неразрешимость. А тасование языков программирования ради "комфорта" — это как в той басне про квартет: "А вы, друзья, как ни садитесь..."

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

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

ГВ>>Разницу между иллюстрацией и фрагментом рабочего кода объяснять нужно?
VD>Не надо. Но твой код не рабочий потому что бессмысленный, в не потому что он не полон.

Я это в цитатник занесу: "код не рабочий потому что бессмысленный, а не потому что он не полон". Махатма Ганди нервно протирает очки.

class Optimizer;

class Rule {
  virtual Rule *optimize(Optimizer *) = 0;
};

class AndRule : public Rule {
  virtual Rule *optimize(Optimizer *optimizer) {
    // "Самооптимизация" And либо что-то в этом духе:
    return optimizer->optimizeAnd(this);
  }
};

Это чтобы избежать очередного круга обсуждения моего невежества.

Здравствуйте, Геннадий Васильев, Вы писали:

ГВ>Конечно, не заработает. На фига мне PEG-парсер? Хотя, если вдруг понадобится...

Гы-гы.

VD>>и компилятор проверит те что есть и выдаст предупреждения для каждого не покрытого случая. Если ты хотя бы одино из вхождений не укажешь будет сообщение. А укажешь все — не будет.

ГВ>М-м-м... Разве такое поведение компилятора будет вызвано не тем, что в типе Rule прямо объявлено:

ГВ>

ГВ>    | Not            { rule : Rule; }
ГВ>    | And            { rule : Rule; }
ГВ>

ГВ>?

Именно. Но не только этих двух вхождений, а всех. Там очень хитрая штука делается. Строится так называемое дерево решения. А потом анализируется.

The algorithm used here is based on the ``ML pattern match compilation
and partial evaluation'' by Peter Sestoft, available at:

http://www.dina.kvl.dk/~sestoft/papers/match.ps.gz

However the partial evaluator used there is purely functional, while we use
a more imperative, but conceptually simpler approach.

The idea is to build a decision tree (type Decision) out of a list
of patterns. The nodes in the tree represent a constructor (type Con)
equality tests, while the leafs contains the result of matching (either
failure or a branch to be taken).

If given branch is not found in the output tree, then given pattern
never matches and is thus redundant.

If there is at least one Failure leaf, the matching is not exhaustive.
The counter example (type CounterExample) is constructed by walking the
path to the Failure leaf and adding positive and negative information
to it.

The idea used in building the decision tree is to use available static
information. It is encoded in a ``skeleton'' of a term we're currently
matching (type Skeleton). For example given a pattern: Foo (Bar), if the
head of the term matches Foo, but the argument ain't Bar, then in this
branch we're confident that the term is Foo(NOT(Bar)) (this Foo(NOT(Bar))
is an example of a skeleton) that is and if the next pattern to check
is Foo (Baz), we just need to check for Baz.

The data flow is:
list [Match_case] -> // input
list [Pattern * bool * int] -> // pattern, has_guard, id
the first element of the above list is used to construct the first
TopLevelPattern, rest of patterns are handled automatically by
TopLevelPattern in its failure branches ->
Decision // output

ГВ>Угу, покруче в каком-то смысле. Понятно теперь, почему ПМ для меня не новость? И ни для кого не новость, кто знаком с Прологом.

К сожалению, эти "все" (включая тебя) Пролог изучали так же. Побаловались и бросили. В прочем, я от вас не далеко ушел. Вот только разве что не гоню напраслину.

Раз ты знаком с прологом, то должен понимать, что похожие механизмы но обеспечивающие высокую скорость кода очень даже крутая штука. И по уму ты должен жалеть, что в "твоих" языках такого нет. Но тебя радует то что ты "это видел".

ГВ>Ну да, правильно, потому что предназначен для других вещей — не только для поиска набора унификаций.

Не для других, а для одной из целей — нахождения соответствия. А вот унификацию он как раз таки не обеспечивает.

VD>>У меня закрадываются сомнения в том, что ты знаешь что такое паттерн посетитель.

ГВ>Объясни, что ты имеешь в виду в данном контексте?

То что сказал. Похоже ты просто не понимаешь зачем этот паттерн был придуман.

ГВ>Всё зависит от контекста. Если набор типов изначально не ограничен, как, например, ограничен набор вариаций для Rule, то "посетитель" может оказаться уместным. Но мы, вроде как, обсуждаем другой случай — Rule имеет строго определённый набор вариаций.

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

ГВ>Какие это проблемы можно без него огрести, например, в коде транслятора?

Все те же. При очередном рефакторинге забыть обработать некоторые из типов (ветвей дерева).

ГВ>Забыть, что ли, switch/if вставить там, где он нужен?

Ага. Они то и приводят к проблемам.

ГВ>Так это, прости меня, детский сад, право слово.

Детский сад — это не знать детали паттерна и лезть спорить о нем.

ГВ> Корректность компилятора контролируется наборами тестов, а не языком реализации. Да и, собственно, ветку в ПМ тоже можно запросто "заглушить".

Ага! Разговоры о тестах это такая лакмусовая бумажка.

Ты понимаешь разницу между значением слов "гарантия" и "протестировано"?
Если есть возможность получить гарантию глупо делать тесты.

ГВ>Я это в цитатник занесу: "код не рабочий потому что бессмысленный, а не потому что он не полон". Махатма Ганди нервно протирает очки.

Занеси. Только не показывай никому. А то стыдно будет.

Здравствуйте, WolfHound, Вы писали:

V>>Настоящий нейтив во-плоти, без встроенных фокусов (если сравнивать с Паскалем, например). Что получится в итоге известно фактически до бит, что и требуется для ПО, непосредственно общающегося с кодом. С этого языка "взлетают" все современные аппаратные платформы, и уже поверх него работают все эти джавы, дотнеты и прочие экзотичности. Поверх него — т.е. поверх кода, созданного компилятором С. Фактически весь современный нейтивный код написан на С/С++, от операционок, офиса и БД, до дотнета и игрушек.
WH>Но должны взлетать вот с этого: Verve: типобезопасная ОС от MS Research

Автор: deniok
Дата: 07.12.10

WH>Там все известно еще лучше и что характерно все верифицировано.

Это которая была сингулярити?
И это масштабируется от систем с 64к памяти до систем с 64гиг памяти? Как стек TCP, например?

V>>Для императивных — Фортран/С/Паскаль.
WH>А фортран то нахрена? Чтобы людям жизнь поломать?

А что не так? Есть процедуры и ф-ии, циклы и ветвления, ввод и вывод, числовые операции. Что еще надо для программирования всяких численных методов?

WH>Тут нужно брать хаскель. Без вариантов. Ибо он вывернет руки но заставит писать функционально.

Можно взять Схему — допиленный до функциональной чистоты и имеющий стандарт новомодный диалект Лиспа. Ограничения алфавита Хаскеля, и не очень бросающийся в глаза синтаксис замыканий вряд ли будет способствовать пониманию происходящего. ИМХО, понимать происходящее лучше на чем-нить попроще, а к Хаскелю подступаться уже хоть с каким-то багажом.

V>>логический — Пролог.
WH>Он очень грязный.

Например?

WH>Лучше уж http://en.wikipedia.org/wiki/Mercury_%28programming_language%29

Да, есть что подчерпнуть. Но, как я же сказал, там много лишнего для целей логического программирования. Это довольно-таки мощный и универсальный язык.

Есть еще важный такой момент. Понимать ЯП — это понимать его до такой степени, чтобы знать, как написать компилятор этого языка. Если Фортран/С/Паскаль/Лисп/Пролог сильный студент 4-5-го курса вполне будет в состоянии написать (пусть не самым оптимальным образом или даже не в полном объеме стандартов, не суть), то вот с этим Меркури или с Хасклелем — 100% обломается. Значит, рано пока.

Хотя, шаблоны плюсов тоже писать обломается. Потому вчерашние студенты и не особо в них разбираются. Потому учить плюсам в полном объеме в ВУЗе мне тоже кажется не очень хорошей идеей. Наследование — да, виртуальные методы — да. Метапрограммирование на шаблонах — нет!

V>>Отличные языки для изучения парадигм. Почему отличные? — а ничего лишнего, никаких понтов, шелухи и синтаксического сахара.
WH>"Отличные они по тому", что ты других не знаешь.

Линейку сейчас прикладывать будем, или чуть потом?


V>>Если энергичные, то в топку, бо многопроходность, а оно вполне решаемо за один проход.
WH>Типа меня волнует производительность этого куска.

Ну блин, каждый лишний запуск обхода дерева с каждого его узла по мере обхода верхнего уровня, это +1 к показателю степени сложности. А тут +4. Итого, квадратичная изначальная сложность алгоритма превращается в 6-ю степень. Я понимаю, что глубина правил обычно маленькая, да и % правил именно такого вида может быть небольшой... Но для общего случая сразу режет по глазам.

WH>2)Это сейчас код похож. Раньше он был разным. И потом он тоже станет разным.
WH>Так что обобщение тут, мягко говоря, противопоказано.

Ну так, если предполагается дальнейшее независимая доработка, почему бы не вынести этот код за пределы этой одной мега ф-ии? И не дорабатывать независимо от остальной отлаженной части?

V>>Далее. Есть предложение для обоих случаев насчет возможности построения оптимизированного варианта сразу, по мере парсинга правил, а не "потом", за вот этот проход оптимизации.
WH>Ой лол. Там такая лапша получится что
WH>Причем на любом языке.

Это зависит от того, как ты строишь АСТ, больше ни от чего. Парсер даже знать не будет, что там что-то оптимизируется по ходу построения этого АСТ.

WH>А если вспомнить про инлайн

Я тут инлайна не увидел, хотя ты дважды его упоминал. Где он? И чем инлайн-подстановка принципиально отличается от других преобразований АСТ?

WH>Я теперь понимаю твоих коллег. И почему они говорят, что у тебя говнокод.

Потому что не с первого раза понимают, наверно.
Надо им твой показать, и запротоколировать комменты. Или проще будет еще по разику назвать друг друга ламерами и разбежаться? На радость читателям ветки.


WH>Ни один из известных мне алгоритмов минимальный ДКА в общем случае не строит.

Согласен, самый минимальный вариант можно вычислить в общем случае через полный перебор применения алгоритма минимизации, начиная от каждого уникального первого входного сигнала из начального состояния. Сойдемся на термине минимизированный. Обычно же полный перебор не делает. Просто от первого же состояния склеивают остальные возможные состояния до первого конфликта выходных сигналов, потом вводят новое подстановочное состояние и т.д. Если в общем случае кол-во состояний после минимизации уменьшается грубо на порядок, то разница в несколько % получившегося кол-ва состояний от варианта полного перебора не принципиальна. Тем более, что минимизация состояний влияет на кол-во памяти под таблицу переходов, но не на кол-во пройденных состояний при разборе входных цепочек, т.е. связь с быстродействием тут не совсем прямая, а коссвенная через кеши процессора и прочие такие вещи.

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

Давай, чтобы не ходить вокруг да около, попытаешься объяснить, что не так в рассуждениях.
Как организована структура парсеров обычно:
— сам парсер чего-то там парсит и выдает калбэки о об успешном разборе очередного правила (ветки/выражения/элемента). Как пример можно привести SAX парсер.
— построитель модели документа. Этот модуль ловит сигналы парсера, отслеживает его состояние, и строит по текущему состоянию и сигналам граф/модель документа. Например, АСТ программы, XML DOM, или линкованный электронный EDI-документ.

Остановимся на абстрактном построителе модели документа. Согласись, что никакие подробности его внутренней работы не усложнят и не повлияют на код собственно парсера входного потока. В свою очередь, при построении АСТ мы уже имеем диспетчеризацию либо через нужную ф-ию калбэка (что хорошо), либо через код нетерминала (что чуть хуже,но с выходом на первый вариант внутри). Что мешает там же не просто создать узел АСТ, а сразу его минимизированный вариант? Характерно, что тут процесс двухтактный — начало формирования узла, потом идет обработка низлежащих, и потом приходит сигнал окончания формирования низлежащих узлов (аргументов). Вот здесь и можно строить сразу оптимизированный вариант узла, без промежуточного построения неоптимизированного. Заметь еще один момент, если ты сейчас обходишь граф сверху, то описанный момент происходит наоборот — выражение "сворачивается" снизу вверх, что и требуется. В случае forward reference, к которым можно отнести и инлайн, сигнал об окончании формирования узла просто приходит позже, по мере парсинга этих forward references.

Согласен, что еще встречаются реализации, где оба модуля настолько диффузируют друг в друга, что их разделение — отдельная неплохая задача... И там код оптимизации АСТ будет усложнять код парсера... но это же не повод для подражательства?

Здравствуйте, VladD2, Вы писали:

VD>Ну, вот изучи и попользуйся PegGrammar... и с большой вероятностью оценишь эту вещь по достоинству. Это я так мягко выражаюсь, чтобы не оскорбить тебя фразами вроде "поймешь что потратил много времени в своей жизни зря" .

Что есть PEG я понял еще с того первого твоего поста на эту тему. Меня в нём напрягает приоритетность правил. Т.е. даже все эти вопросы оптимизированной его реализации мне пока пофиг абсолютно.

Какой вид грамматики получается после применения этой "приоритетности"? Не есть ли это способ "замыливания" неоднозначностей? Я не видел еще док-ва, что невозможна ситуация, когда мы строим корректное выражение согласно неким правилам PEG, но оно распознается (перехватывается) другим правилом (участком правила) за счет приоритетности. Т.е. отсутствие таких гарантий будет заставлять полагаться только на бесконечное тестирование парсера на основе PEG с целью обкатки решения в боевых условиях. В общем, это что-то вроде статической vs динамической типизации. Без нормальной диагностики конфликтов выражений систем правил остается надеяться на авось и на тесты. Даже парсер Эрли, выдавая все возможные варианты, дает нам шанс проанализировать их, например, на семантическом уровне, если у нас какая-нить совсем уж контекстно-зависимая грамматика или семантика управляется данными. А тут контекстно-свободное отсечение на основе приоритетов... Не могу пока побороть недоверие.

Здравствуйте, VladD2, Вы писали:

VD>Хочется собрать статистику (мнения) по поводу что останавливает людей от изучения новых языков.

А какие новые языки ты изучил в последнее время, и какие из них ты бы в первую очередь порекомендовал для изучения другим?

Здравствуйте, vdimas, Вы писали:

V>Что есть PEG я понял еще с того первого твоего поста на эту тему. Меня в нём напрягает приоритетность правил. Т.е. даже все эти вопросы оптимизированной его реализации мне пока пофиг абсолютно.

V>Какой вид грамматики получается после применения этой "приоритетности"?

PEG. Включает почти любой сложности контекстно свободную, однозначную грамматику.

V>Не есть ли это способ "замыливания" неоднозначностей? Я не видел еще док-ва, что невозможна ситуация, когда мы строим корректное выражение согласно неким правилам PEG, но оно распознается (перехватывается) другим правилом (участком правила) за счет приоритетности. Т.е. отсутствие таких гарантий будет заставлять полагаться только на бесконечное тестирование парсера на основе PEG с целью обкатки решения в боевых условиях. В общем, это что-то вроде статической vs динамической типизации. Без нормальной диагностики конфликтов выражений систем правил остается надеяться на авось и на тесты. Даже парсер Эрли, выдавая все возможные варианты, дает нам шанс проанализировать их, например, на семантическом уровне, если у нас какая-нить совсем уж контекстно-зависимая грамматика или семантика управляется данными. А тут контекстно-свободное отсечение на основе приоритетов... Не могу пока побороть недоверие.

Это тот случай когда надо пробовать.

Здравствуйте, VladD2, Вы писали:

VD>>>и компилятор проверит те что есть и выдаст предупреждения для каждого не покрытого случая. Если ты хотя бы одино из вхождений не укажешь будет сообщение. А укажешь все — не будет.

ГВ>>М-м-м... Разве такое поведение компилятора будет вызвано не тем, что в типе Rule прямо объявлено:

ГВ>>

ГВ>>    | Not            { rule : Rule; }
ГВ>>    | And            { rule : Rule; }
ГВ>>

ГВ>>?

VD>Именно. Но не только этих двух вхождений, а всех. Там очень хитрая штука делается. Строится так называемое дерево решения. А потом анализируется.

[...]

Лучше перескажи, а не отсылай меня к комментариям в коде компилятора.

Несколько вопросов:

1. Что является входными данными для Decision tree?
2. Что имеется в виду под 'given branch' и 'given pattern':

If given branch is not found in the output tree, then given pattern
never matches and is thus redundant.

?
3. Что такое и откуда берутся failure nodes в Decision tree?

Чую, что ответы достаточно простые, но пока это только чутьё "спинным мозгом".

ГВ>>Угу, покруче в каком-то смысле. Понятно теперь, почему ПМ для меня не новость? И ни для кого не новость, кто знаком с Прологом.
VD>К сожалению, эти "все" (включая тебя) Пролог изучали так же. Побаловались и бросили. В прочем, я от вас не далеко ушел. Вот только разве что не гоню напраслину.

Ну, насчёт побаловались и бросили — это оставляю на твоей совести. А напраслину ты прекрасно гонишь в адрес C++ и тех, кто на нём программирует — у тебя это получается даже лучше, чем у других в адрес N.

VD>Раз ты знаком с прологом, то должен понимать, что похожие механизмы но обеспечивающие высокую скорость кода очень даже крутая штука. И по уму ты должен жалеть, что в "твоих" языках такого нет. Но тебя радует то что ты "это видел".

Понимаю, отчасти сожалею. Отчасти, потому что для меня главной проблемой всегда было не "как" перебрать структуры, а "что" именно перебирать. Догадываешься, в чём разница?

ГВ>>Ну да, правильно, потому что предназначен для других вещей — не только для поиска набора унификаций.
VD>Не для других, а для одной из целей — нахождения соответствия. А вот унификацию он как раз таки не обеспечивает.

Нахождения первого соответствия, заметь. В остальном согласен (замнём терминологические тонкости для ясности).

VD>>>У меня закрадываются сомнения в том, что ты знаешь что такое паттерн посетитель.
ГВ>>Объясни, что ты имеешь в виду в данном контексте?
VD>То что сказал. Похоже ты просто не понимаешь зачем этот паттерн был придуман.

Ну-ка, ну-ка, я весь внимание.

ГВ>>Всё зависит от контекста. Если набор типов изначально не ограничен, как, например, ограничен набор вариаций для Rule, то "посетитель" может оказаться уместным. Но мы, вроде как, обсуждаем другой случай — Rule имеет строго определённый набор вариаций.

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

Да ты что? То есть разносить реализации управления посещением по классам нужно только тогда, когда этот набор редко расширяется? А я-то всегда считал, что Посетитель нужен для того, чтобы предоставить "посещаемым" возможность самостоятельно выбрать метод(ы) их обработки. То есть набор доступных методов у "посетителя" как правило должен отличаться от набора "посещаемых" классов. Иначе на хрена оно вообще нужно-то при фиксированном наборе классов? Так просто, из принципа?

Короче, кроме шуток. Влад, тебя, похоже, намертво заклинило на иллюстративной реализации

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

Посетителя:

public interface IVisitor
{
  void VisitRoot(RootNode node);
  void VisitType1(Type1Node node);
  void VisitType2(Type2Node node);
  void VisitType3(Type3Node node);
}

На самом деле, общий случай тут совсем не такой, а вот такой:

public Interface IVisitor
{
  void VisitRoot(RootNode node);
  void Action1ForNode1(Type1Node node);
  void Action2ForNode1(Type1Node node);
  void Action3ForNode(RootNode node);
  // ...
}

То есть набор операций IVisitor вовсе не обязан соответствовать набору имеющихся "внешних" классов. А иначе реализация этого паттерна являет собой просто паттерн ради паттерна с вырожденной реализацией посещаемых классов типа такой:

class A {
virtual void visit(IVisitor *visitor)
{
  visitor->visitTypeAnode(this);
}
};

Хотя это по сути двойная диспетчеризация, но, тем менее, она служит хорошим примером к тезису о вреде работоспособных иллюстраций — людей клинит на иллюстративном материале, как на истине в последней инстанции. Весьма показательны в этом смысле истории с примерами из книг Буча — их тоже, почему-то иной раз пытаются прямо перенести в рабочий код.

ГВ>>Какие это проблемы можно без него огрести, например, в коде транслятора?
VD>Все те же. При очередном рефакторинге забыть обработать некоторые из типов (ветвей дерева).

Ясен перец, копаться в десятке реализаций удобнее, чем в одном case, кто бы спорил... Влад, не гони, а?

ГВ>>Забыть, что ли, switch/if вставить там, где он нужен?
VD>Ага. Они то и приводят к проблемам.

Ага, я даже представляю, что ты вспомнишь следующим. LSP, да?

ГВ>>Так это, прости меня, детский сад, право слово.
VD>Детский сад — это не знать детали паттерна и лезть спорить о нем.

Какие ещё детали паттерна? О чём ты?

ГВ>> Корректность компилятора контролируется наборами тестов, а не языком реализации. Да и, собственно, ветку в ПМ тоже можно запросто "заглушить".
VD>Ага! Разговоры о тестах это такая лакмусовая бумажка.

VD>Ты понимаешь разницу между значением слов "гарантия" и "протестировано"?
VD>Если есть возможность получить гарантию глупо делать тесты.

Если хоть один компилятор сможет мне дать гарантию, что никто из разработчиков не напишет вот такой:

| Not(Not(rule))                => r // Пока не знаю, что тут делать

или такой код:

virtual Rule *optimize(RuleOptimizer *)
{
  return this; // TODO: Разобраться, что тут писать
}

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

ГВ>>Я это в цитатник занесу: "код не рабочий потому что бессмысленный, а не потому что он не полон". Махатма Ганди нервно протирает очки.
VD>Занеси. Только не показывай никому. А то стыдно будет.

Кому? Тебе? Не бойся, я никому не скажу!

Здравствуйте, alpha21264, Вы писали:

A>Здравствуйте, VoidEx, Вы писали:

VE>>

A>Метро всё равно быстрее их обоих.

VE>>Сам придумал, сам не знаешь?

A>Не хами. Метро быстрее — очевидный факт. В большинстве случаев просто в разы.

Я не хамил, я лишь процитировал, что аналогию увёл в сторону не я.

A>Тебе сколько лет?

Максималист тут не я.

A>Я тебе уже сказал. Для сложных задач (не ларек об1Сивать) язык не важен.
A>Совсем не важен, как авторучка для писателя, нужно чтобы просто была какая-нибудь.

Даже я ручку выбираю не от балды. Писать-то всякая может, но некоторыми удобнее. А уж писатели и подавно.

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

Разумеется. Но если знаю, то мерседес предпочтительней.

A>Я тут уже предлагал простенькую задачку (с сайта Яндекса). Есть список глаголов русского языка.
A>Сформировать список пар глаголов "делал"-"сделал".
A>Какие преимущества в этой задаче может дать язык программирования?
A>В качестве эталона берем С++.

GC, замыкания, АлгТД, лямбды, ФВП, легковесные потоки, иммутабельность: все эти на твой взгляд незначимые плюшки дают возможность писать тот самый алгоритм, а не в очередной раз бороться с языком (в этом плане C++ и правда эталон). Для неспецифических задач (где легковесные потоки, например, позволят на порядок проще написать) разница в простоте написания будет не в разы, но всё же будет заметна.

Здравствуйте, vdimas, Вы писали:


V>Есть еще важный такой момент. Понимать ЯП — это понимать его до такой степени, чтобы знать, как написать компилятор этого языка. Если Фортран/С/Паскаль/Лисп/Пролог сильный студент 4-5-го курса вполне будет в состоянии написать (пусть не самым оптимальным образом или даже не в полном объеме стандартов, не суть), то вот с этим Меркури или с Хасклелем — 100% обломается. Значит, рано пока.

Тогда схема (без макросов) идеальный вариант, функциональный и императивный язык в одном флаконе плюс очень легко написать транслятор.
То же самое и ML, императивная часть не хуже паскаля, функциональщина полноценная, транслятор тоже несложен и уже есть готовый курс
его написания для студентов http://min-caml.sourceforge.net/index-e.html

Здравствуйте, VladD2, Вы писали:

C>>>>а не все ли равно на чем писать?
VD>>>Нет конечно. Иначе все бы писали на ассемблерах или хотя бы на Фортране 77.
C>>я не это имел ввиду.

VD>Именно это ты и имел в виду.
преклоняюсь перед твоими телепатическими способностями.

C>>>>а если так, то зачем учить очередной язык пока он не понадобился?
VD>>>А как ты поймешь что что-то тебе нужно, если ты даже не знаешь что там внутри и что это тебе может дать?
C>>А для того чтобы понять что там внутри не надо язык изучать, обычно достаточно прочитать какой нибуть обзор или полистать домашнюю страничку.
VD>Не недостаточно. Чтобы понять новое его нужно пробовать. Ну, то есть в принципе можно понимать возможности языка просто прочитав про него, но при этом все концепции этого языка должны быть известны. Например, зная Немерле или ОКамл можно прочитать книгу об F# и понять что из себя представляет этот язык. Но зная С++ или C# недостаточно прочитать что-то про F#, Немерле или ОКамл. Это просто бесполезно.
в цитате на следующей строчке именно это и сказано.
C>>>>понадобится, потрачу неделю чтобы выучить синтаксис и примерно прикинуть как семантика ложится на известные мне концепции и всех делов.
VD>>>Попробуй заменить в своей логике язык на телевизор. Скажем ты пользуешься радио.
VD>>>Тебе говорят, что есть же телевизор. И что он как радио, то только лучше. А ты в ответ — "понадобится, потрачу неделю чтобы понять что это такое".
C>>нет, такой ответ последует если мне предложат радио новой модели которое принимает сигнал улавливая нейтрино.
C>>а на телевизор я согласен.

VD>Вот модель радио тут не причем.
VD>Ну, разве что если сравнивать гетеродинный приемник метрового диапазона и современные стереофонический FM-риемник.
мы говорим про сферический язык в вакууме или ты опять рекламируеш какойто конкретный язык?
я вот могу тебе чесно сказать что стерео звук от моно не отличаю, и ни капельки не страдаю от этого.
VD>Но и это не корректное сравнение, так как кроме повышения качества тут ничего не будет. А в случае языков разница приципиальная. С языком ты получаешь новые концепции. После изучения которых ты сможешь мыслить другими категориями. Это именно как сменить звук на картинку со звуком.
а кто сказал что я этих концепций не знаю?

Здравствуйте, cvetkov, Вы писали:

C>а кто сказал что я этих концепций не знаю?

Если б знал, писал бы на Nemerle.

B>>Отсутствие практической необходимости. Имеющегося знания asm,C,Java,JavaScript,HTML,SQL достаточно для решения любых задач, которые у меня появляются или могут возникнуть. Ради интереса смотрел на Scala, haskell, C#, но в этом всем нет никакого смысла. Может быть, изучил бы Ceylon, когда под него будет IDE.
VD>Необходимость появится точас же как ты поймешь концепции заложенные в эти языки и научишься применять их на практике.
VD>А до тех пор все эти языки для тебя будут непонятными хреновинвами.
Вы, видимо, считаете себя носителем сокровенного знания, недоступного другим, и очень этим гордитесь, раз делаете такие выводы. Я не писал, что там что-то для меня не понятно, как раз наоборот.

V>я бы переделал твое предложение так
V>Необходимость МОЖЕТ ПОЯВИТСЯ, если ты поймешь концепции заложенные в эти языки и научишься применять их на практике.

Осталось завершить логическую конструкцию с учетом моего исходного комментария:
Необходимость могла появиться, когда я понял концепции, заложенные в эти языки, и научился применять их на практике.

Увы и ах.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Здравствуйте, alvas, Вы писали:

A>>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>>Ну вот, например, "концепт" универсальной обверточки, через которую в Ela можно скормить любой объект:

A>>Код ниже из http://code.google.com/p/elalang/wiki/GettingStarted
A>>Выдает 3 ошибки

ВВ>(+) — это в дефолтных настройках компиляция происходит без прелюда, вот никакого (+) и нет. А с аргументами — бага, да. В текущей версии аргументы поломаны, надо чинить.

ВВ>Чтобы починить (+) надо сделать так (потом добавлю в дефолт):

ВВ>

ВВ>var opts = new LinkerOptions();
ВВ>opts.CodeBase.Directories.Add(new DirectoryInfo(@"Папка с Prelude.ela"));
ВВ>var l = new ElaIncrementalLinker(opts, new CompilerOptions {
ВВ>            WarningsAsErrors = false,
ВВ>            ShowHints = true,
ВВ>            Optimize = true,
ВВ>            Prelude = "prelude"
ВВ>        });
ВВ>

ВВ>Или можно прям по месту плюсик объявить:

ВВ>

ВВ>let (+) = __internal add
ВВ>

Не помогло — теперь такая ошибка


Ela.ElaTranslationException was unhandled
Message=(1,6): Error ELA610: An argument 'y' is unresolved. No argument with such name were provided.
(1,1): Error ELA610: An argument 'x' is unresolved. No argument with such name were provided.

Source=ElaWrapper
StackTrace:
at ElaWrapper.Program.Eval(String source, Object args) in c:\Downloads\Ela-0-9-3\ElaWrapper\ElaWrapper\Program.cs:line 50
at ElaWrapper.Program.Main(String[] args) in c:\Downloads\Ela-0-9-3\ElaWrapper\ElaWrapper\Program.cs:line 57
at System.AppDomain._nExecuteAssembly(RuntimeAssembly assembly, String[] args)
at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args)
at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
at System.Threading.ThreadHelper.ThreadStart_Context(Object state)
at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean ignoreSyncCtx)
at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
at System.Threading.ThreadHelper.ThreadStart()
InnerException:

Здравствуйте, VoidEx, Вы писали:

VE>Здравствуйте, alpha21264, Вы писали:

A>>Здравствуйте, VoidEx, Вы писали:

VE>>>

A>Метро всё равно быстрее их обоих.

VE>>>Сам придумал, сам не знаешь?

A>>Не хами. Метро быстрее — очевидный факт. В большинстве случаев просто в разы.

VE>Я не хамил, я лишь процитировал, что аналогию увёл в сторону не я.

A>>Тебе сколько лет?

VE>Максималист тут не я.

Я не говорил, что ты максималист. Я говорил, что ты отрицаешь очевидные факты про метро.

A>>Я тебе уже сказал. Для сложных задач (не ларек об1Сивать) язык не важен.
A>>Совсем не важен, как авторучка для писателя, нужно чтобы просто была какая-нибудь.

VE>Даже я ручку выбираю не от балды. Писать-то всякая может, но некоторыми удобнее. А уж писатели и подавно.

Ну если тебе нравится эта аналогия, то ты пытаешься утверждать, что писатель не важен,
достаточно дать хорошую ручку любому алкоголику, и он сразу станет Львом Толстым.
А я говорю, что ручка не важна. Чтобы стать Толстым нужно поучаствовать в обороне Севастополя.
Иначе писать будет не о чем.

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

VE>Разумеется. Но если знаю, то мерседес предпочтительней.

Мерседес предпочтительнее, если он бесплатный.
А изучение нового языка (и всех сопутсвующих вещей) не бесплатно.
Оно стоит года (а то и нескольких) жизни.
И лучше это время потратить на что-то другое — например алгоритмы и предметную область.
Да хоть на английский тот же самый.

A>>Я тут уже предлагал простенькую задачку (с сайта Яндекса). Есть список глаголов русского языка.
A>>Сформировать список пар глаголов "делал"-"сделал".
A>>Какие преимущества в этой задаче может дать язык программирования?
A>>В качестве эталона берем С++.

VE>GC, замыкания, АлгТД, лямбды, ФВП, легковесные потоки, иммутабельность: все эти на твой взгляд незначимые плюшки дают возможность писать тот самый алгоритм, а не в очередной раз бороться с языком (в этом плане C++ и правда эталон). Для неспецифических задач (где легковесные потоки, например, позволят на порядок проще написать) разница в простоте написания будет не в разы, но всё же будет заметна.

Я не понял, так ты слил что-ли? Все, что ты перечислил никак не помогает решить названную задачу. Вот то есть совсем.
Спорим, что я с помощью С++ (плюс голова, разумеется) решу эту задачу быстрее чем ты (любыми средствами)?

Хочешь еще задачку с сайта Яндекса?
Есть Террабайт текстов на русском языке.
Нужно найти миллион самых частотных сочетаний из двух слов.