Тебе для демонстрации осталось вернуть vect1 из ф-ии, которое читает IO и заранее НЕ знает, сколько там элементов.
Попробуешь еще раз? ))
А то, что ты показал, то в Хаскеле сделали через аппликатор (в твоих переменных):
putStrLn $ show $ makeVect size 42
WH>Твоя очередь. Повтори на хаскеле.
Не надоело упираться?
Будь мужчиной, признай, что сел в лужу.
Тут самое смешное, что мне очень хорошо понятно, что именно тебе не понятно.
Ты ставишь знак равенства м/у системой типов Хаскеля и С++.
В то время как даже просто параметрический полиморфизм у них работает по-разному: в С++ происходит инстанс уникального бинарного кода для каждой специализации шаблона (т.е. происходит кодогенерация), а в Хаскель работает т.н. "истинный полиморфизм" (как они сами говорят), когда физически может исполняться один и тот же код для разных типов, заданных классом типов.
Кароч, видя твой незамысловатый ход мыслей, я еще несколько постов назад тебе написал всё, что требуется знать:
И вот у тебя получается новый тип вектора на каждом шаге цикла, т.е. путём абстракции цикла через рекурсию мы получаем уникальный контекст типизации на каждом шаге цикла. Ву а ля.
Как "вернуть" затем такой прочитанный типизированный вектор? — через полиморфный же колбэк, который будет вызван по окончании считывания файла.
В общем, я могу подписываться только под СВОИМИ словами, а не под голосами в твоей голове...
И вот тут: http://www.rsdn.org/forum/philosophy/6712201.1
было показано именно то, что я тебе расписывал на словах.
ЧТД.
Заметь, что пример кода на Хаскеле по ссылке можно легко допилить, чтобы он работал БЕЗ предварительного считывания некоего числа — он может считывать, допустим, некий поток, пока тот считывается и получать длину вектора "по факту". Итого, чудес не бывает. Чтобы повторить такой же трюк на idris тебе придется сделать примерно так же, как в показанном примере на Хаскель.
Опять и снова разгромное ЧТД. ))
Здравствуйте, WolfHound, Вы писали:
V>>Никакой кодогенерацией тут и не может пахнуть, пока речь о С++. V>>Для других каких-то языков еще может быть... V>>Но для С++... )) WH>Гонять N^3 для 22х различных цветовых пространств на шаблонах С++ на компиляторах десятилетней давности... ну-ну.
Здравствуйте, vdimas, Вы писали:
V>Тебе для демонстрации осталось вернуть vect1 из ф-ии, которое читает IO и заранее НЕ знает, сколько там элементов. V>Попробуешь еще раз? ))
Перестань говорить с голосами в своей голове.
Сказано:
Попробуй вернуть этот вектор в функцию main таким образом, чтобы тип сохранился.
Сделано.
V>А то, что ты показал, то в Хаскеле сделали через аппликатор (в твоих переменных): V>
V>putStrLn $ show $ makeVect size 42
V>
В идресе тоже так можно писать. Но это просто другая форма записи.
Главное тут типы. А типы значений vect1 и vect2 ты в хаскеле не повторишь.
WH>>Твоя очередь. Повтори на хаскеле. V>Не надоело упираться? V>Будь мужчиной, признай, что сел в лужу.
Я признаю, что ты трепло конченое.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Сказано: WH>
WH>Попробуй вернуть этот вектор в функцию main таким образом, чтобы тип сохранился.
WH>Сделано.
Мало ли какую задачу ты сам себе решил поставить? ))
Весёлый ты парень. Ты упростил себе задачу — у тебя size известен заранее, что не всегда бывает на практике.
Поэтому, ближе к телу:
Тебе для демонстрации осталось вернуть vect1 из ф-ии, которое читает IO и заранее НЕ знает, сколько там элементов.
Попробуешь и получишь то же самое, что на Хаскеле.
Опять и снова ЧТД, можно расходиться. ))
WH>>>Твоя очередь. Повтори на хаскеле. V>>Не надоело упираться? V>>Будь мужчиной, признай, что сел в лужу. WH>Я признаю, что ты трепло конченое.
Бла-бла-бла, всё слил и ругаешься. Как знакомо. ))
Ты показал некомпетентность. Показал наглухо непонимание параметрического полиморфизма и с чем его едят.
Тут тебе самое время попытаться поймать на некомпетентности кого-нить другого, благо и повод есть: алгоритм Флойда—Уоршелла.
На самом деле основное ты ответил, спасибо. Остальное шелуха.
Ещё я обнаружил тут связанную тему на форуме, где так же затронуты вопросы. Так что здесь заниматься буквоедством и подымать тоже самое ещё раз не нужно. Спасибо за терпение и потраченное время.
Вот это чьё сообщение?
Так что ты получил что хотел.
Теперь повтори этот код на хаскеле.
Ты же тут утверждаешь, что ЗТ в хаскеле есть. Вот и доказывай.
Повтори простейший пример.
V>Весёлый ты парень. Ты упростил себе задачу — у тебя size известен заранее, что не всегда бывает на практике.
1)У меня size заранее не известен. Он читается из консоли.
2)Ты даже упрощённый вариант показать не можешь. Ибо трепло.
V>Бла-бла-бла, всё слил и ругаешься. Как знакомо. ))
Заметь тут с тобой все ругаются. Даже D. Mon послал тебя в весьма грубой форме.
Так что ты подумай может это ты по встречной полосе прёшь.
V>Ту тебе Самое время попытаться поймать на компетентности кого-нить другого, благо и повод есть: алгоритм Флойда—Уоршелла.
Всё что про него нужно знать это то что он имеет кубическую сложность. И для шаблонов С++ это смерть. И об этом я сказал. Да и вообще весь алгоритм это 4 строки.
Адекватный человек бы признал, что сказал глупость. Но ты продолжаешь твердить что всё нормально. С++ переживёт.
Хотя ты конечно можешь доказать, что всё хорошо и реализовать этот алгоритм на С++. Но только чтобы компиляторы 2007ого года это проглотили.
Хотя я думаю, что даже современные подавятся.
Это если забыть про, то что шаблоны сами по себе генерация кода.
И суперпупермегабыстрый GLR я до сих пор жду. Ни LR(0) или что там тебе ещё голоса в голове напоют, а полноценный GLR.
Для него вот эта грамматика не должна являться проблемой:
S = a | S S | S S S;
Трансформировать грамматику нельзя. Должен быть честный разбор, порождающий все деревья разбора.
Это требование необходимое, но не достаточное. Надеюсь разницу понимаешь.
Ну что начнёшь наконец за слова отвечать? Или так и будешь треплом?
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Там в отличии от LL(k) парсеров предсказание ветвления строится динамически. WH>Делается это всё исключительно из-за того, что нельзя в общем случае построить предсказатель перехода статически. А во время исполнения у нас всегда конечное множество префиксов из которого всегда можно сделать ДКА.
...
WH>Ничего общего с Эрли оно не имеет. Ибо Эрли вообще не использует предсказание, а тупо парсит все альтернативы одновременно.
Как бы очевидно ложное утверждение. Из того, что есть отличия нельзя вывести отсутствия общего. Это явная логическая ошибка.
Никто не утверждал, что общее у них построение ДКА.
Общее у них динамическая природа. Наличие очень похожих структур данных (записи Эрли и ATN).
И это делает возможным использование идей из АНТЛР4 в Эрли. Добавляем динамический ДКА к Эрли и получаем алгоритм которому не нужно перебирать все возможные варинты.
WH>Главная проблема с восстановлением — это понять какой текст нужно выкинуть и какой терминал придумать. Как тут поможет предсказатель ветвления не понимаю.
Главная проблема в нашем варианте восстановления заключается в том, что нам нужно сделать слишком большое число переборов. Если ДКА поможет их сократить, это даст приемлемую скорость.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Код на idris.
Это же, если не ошибаюсь, простая эквилибристика, нет? По-моему, на C++ было как раз что-то подобное в примере Jazzer'a.
Если написать так:
main : IO ()
main = do
putStrLn "Hello world"
size1 <- getNat
size2 <- getNat
let vect1 = makeVect size1 "¯\_(ツ)_/¯"let vect2 = makeVect size2 "^_^"
putStrLn (show vect1)
putStrLn (show vect2)
putStrLn (show (zipVect vect1 vect2))
то будет же задница. Придется все равно писать что-то типа "if (size1 = size2)..." По факту size1 и size2 — просто флаги, для которых при компиляции мы можем сказать только одно: либо они равны между собой, либо нет.
В чем принципиальная разница с эмуляцией на C++? Где я ошибаюсь?
Здравствуйте, VladD2, Вы писали:
WH>>Там в отличии от LL(k) парсеров предсказание ветвления строится динамически. WH>>Делается это всё исключительно из-за того, что нельзя в общем случае построить предсказатель перехода статически. А во время исполнения у нас всегда конечное множество префиксов из которого всегда можно сделать ДКА. VD>...
Сказать то что хотел?
WH>>Ничего общего с Эрли оно не имеет. Ибо Эрли вообще не использует предсказание, а тупо парсит все альтернативы одновременно. VD>Как бы очевидно ложное утверждение. Из того, что есть отличия нельзя вывести отсутствия общего. Это явная логическая ошибка.
А ещё они оба алгоритмы. И сортировка пузырьком тоже алгоритм. Значит ANTLR4 похож на сортировку пузырьком.
Короче давай не будем заниматься натягиванием совы на глобус.
VD>Общее у них динамическая природа. Наличие очень похожих структур данных (записи Эрли и ATN).
Ох.
1)ALL это рекурсивный спуск с динамическим построением предсказателя ветвления.
2)Эрли построен на динамическом программировании.
Слово "динамический" в этих случаях означает весьма разные вещи.
VD>И это делает возможным использование идей из АНТЛР4 в Эрли. Добавляем динамический ДКА к Эрли и получаем алгоритм которому не нужно перебирать все возможные варинты.
Не делает. Ибо принципиально разные алгоритмы.
VD>Главная проблема в нашем варианте восстановления заключается в том, что нам нужно сделать слишком большое число переборов. Если ДКА поможет их сократить, это даст приемлемую скорость.
Не поможет. Ибо переборы начинаются, когда мы пытаемся придумать терминалы или удалить текст.
Более того из-за динамической природы автомата предсказания ANTL4 использовать этот автомат для восстановления весьма сомнительное занятие. Ибо он будет каждый раз разным. Те даже если ты придумаешь как это сделать, то восстановление будет работать по-разному сразу после запуска и после часа работы.
Такое невозможно ни протестировать ни отладить.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Я получаю лишь отмазки и уже 3-й раз прошу показать мне то, что ты обещал.
WH>Теперь повтори этот код на хаскеле.
Ты так и не показал своё решение.
Необходимо было "прочесть" из входа некий вектор и вернуть его.
Ты никуда его не возвращаешь, ты оперируешь им исключительно в том же блоке кода, в котором прочел что-то из входа — я вижу чтение из входа прямо в теле main. Для решения задачи все операции чтения должны быть внутри некой ф-ии, которая вызывается из main, внутри себя читает вектор и возвращает его вызывающему коду. Иначе слил.
А попробуешь "завернуть" вектор в некий другой тип-адаптер или вернуть не только вектор, но и любое сопутствующее значение — тоже слил, потому что "завернуть" в некий адаптер можно и в Хаскель опять же на параметрическом полиморфизме. Но ты ж сформулировал вопрос так, чтобы вернуть непосредственно сам вектор, верно? Код в студию. ))
WH>Ты же тут утверждаешь, что ЗТ в хаскеле есть. Вот и доказывай.
Это тебе голоса в голове утверждали.
А я утверждал следующее:
WH>Очевидно, что это профанация, а не ЗТ.
Ну, хаскелисты утверждают, что такими св-вами обладают лишь языки с ЗТ.
Пирс даёт такой же трюк, описанный в Вики:
Решение условно предполагает, что фантомный тип n будет использоваться для моделирования целочисленного параметра вектора на основе аксиом Пеано.
Итого, было сразу же сказано, как и что эмулируется и какой класс задач теперь можно решать — тот класс, который раньше был по зубам языкам с поддержкой ЗТ.
Если бы ты в этом месте включил самый важный орган программиста, то там и спорить дальше было не о чем.
Но ты забыл это сделать. ))
А теперь мне очевидно, что тебе срочно требуется "что-то еще для демонстрации крутости ЗТ", но вот что именно — ты пока СФОРМУЛИРОВАТЬ не в состоянии.
А ты не торопись, подумай.
Как сформулируешь очередную "задачку, с которой справятся только ЗТ", так приходи.
И да. "Доказанную сортировку" на Хаскеле на описанных трюках я тоже уже видел в сети.
Помнится, ты приводил пример такой сортировки и думал, это прям мега-круто и доступно для понимания лишь посвящённым. ))
WH>Повтори простейший пример.
Я не вижу никакого примера. Вижу твои изворачивания.
Просто ты потерял лет 6 (или 8 или сколько там уже?), когда я пытался развить эту тему.
Теперь-то мне понятно — почему. ))
Потому что ты ставил знак равенства м/у статической типизацией в С++ и в Хаскель.
При этом все эти годы ты имел нахальство приписывать своё непонимание мне, ы-ы-ы.
При этом, я делал за весь этот срок несколько попыток поднять тему — но, некие твои личные кач-ва этому мешали и до сих пор мешают, заметь.
Например, показанный тебе пример на Хаскеле ты должен был найти сам на сайте, их разбирали минимум трижды здесь за все эти годы.
Или найти в сети, их тоже полно.
V>>Весёлый ты парень. Ты упростил себе задачу — у тебя size известен заранее, что не всегда бывает на практике. WH>1)У меня size заранее не известен. Он читается из консоли.
Для ф-ии формирования вектора он у тебя прочитан заранее.
WH>2)Ты даже упрощённый вариант показать не можешь. Ибо трепло.
Ибо прикольно быть модером и хамить, верно?
По этой теме уже всё с тобой ясно — ты не в состоянии показать только что тобой же обещанное.
Я уверен, что ты ОЧЕНЬ хорошо понимаешь, что мне нужно.
Я даже это достоверно знаю.
Но показать ты не сможешь.
Поэтому, мне остаётся любоваться твоими психами.
WH>Заметь тут с тобой все ругаются. Даже D. Mon послал тебя в весьма грубой форме.
Почему даже? ))
Он как раз регулярно тут хамит окружающим.
Намного-намного реже тебя, но, таки, регулярно.
И твои "все" — это одни и те же 3.5 человека на весь сайт.
Вы тут регулярно ругаетесь с любыми, кто посмеет вам возражать или ни дай бог, выставит вас неучами. И?
Я здесь при чем, если конкретно ты тут знатно сходил до ветру против ветра, и у тебя в процессе всё время бомбит? ))
У D.Mon точно так же — сначала он долго не въезжает, потом психует. Мы с ним это уже проходили.
Он часто умничает, но понимает далеко не всё.
Работает с oCaml, а что там происходит унутре — не в курсе, как только что выяснилось.
И т.д.
Я такой подход хорошо знаю — нахвататься по верхам и тешить своё ЧСВ за счет окружающих.
Ты ж поглянь что он пишет:
Открою один секрет, о котором большинство программистов не догадываются, и в наших вузах от них тоже скрывают. Есть такая штука, называется теория типов. Она на эти вопросы отвечает очень быстро и однозначно.
Сама по себе такая "широковещательная" формулировка попахивает, знаешь ли.
Но этого мало.
Стоило только чуть ноготком подцепить и выяснилось, что он сам в этой теории изрядно плавает.
Как и ты, который НЕ понимает, что есть "сорта типов". )))
Тебе всё кажется, что это такая простая иерархия, да? Вот прям элементарная? Прям как статическая типизация Хаскеля такая же как в С++? (якобы такая же)? Самое забавное, мне опять и снова хорошо понятно, что именно тебе не понятно.
У тебя же там тоже пукан порвало и я запомнил.
Через несколько лет (я ХЗ сколько тебе потребуется для понимания очередного несложного материала) я тебе напомню твоё нынешнее понимание сортов типов и опять полюбуюсь на твой разорванный пукан.
Ну или есть еще вариант — почему бы тебе не почитать, например HoTT?
Тогда ты быстро обнаружишь, почему я писал о сортах типов то, что писал.
И почему твоя "иерархия" не нужна.
Я ведь именно тебе (единственному из этих 3.5 человек) МНОГОКРАТНО говорил, что конкретно у тебя проблема в том, что ты зачастую и не хочешь знать. Лично мне со стороны даже где-то обидно за незнакомого мне человека — вроде голова твоя соображать умеет (что приятная редкость, прямо скажем), а вроде часто по верхам, кусочно гладко, не систематично и вообще... Жаль, просто жаль... Потому что у других, кто тут регулярно психует, скажем прямо, проблемы совсем другого плана, я бы даже сказал — местами совершенно непреодолимого плана. ))
WH>Так что ты подумай может это ты по встречной полосе прёшь.
Ну, до тех пор пока у меня самого пукан не рвется — я вас потерплю.
Выбор-то невелик.
Вы ж разогнали всех более-менее интересных собеседников с этого сайта в разные годы.
А даже те, которые остались — они же избегают обсуждений, потому что иметь в оппонентах кадра с такими манерами как у тебя — это только заляпаться вот этим неадекватом и негативом.
Я ж грю — пороть вас некому! Балованные.
Из-за банальной слабости психики, из-за вот этого детского недержания, в итоге наносите вред всему проекту.
Кстате, показательно, из-за какого моего сообщения у D.Mon порвался пукан: http://www.rsdn.org/forum/philosophy/6716318.1
Сможешь ли ты выступить беспристрастным судьёй сугубо по технической части спора:
— где я там настолько сурово был не прав?
— что аж взорвался пукан у коллеги?
Причем, мне-то и здесь понятно, что коллеге не понятно (подсказка — в С++ адрес ссылки не доступен, ею нельзя оперировать как значением).
Ну вот у меня праздное любопытство — там пукан порвался, потому что коллега наконец понял (а самые страшные взрывы подобного рода вживую я наблюдал именно в такие моменты), или наборот — не понял ни одной буквы и это его стандартный такой псих, когда он чего-то не понимает?
Как по мне, то забавны оба варианта.
V>>Ту тебе Самое время попытаться поймать на компетентности кого-нить другого, благо и повод есть: алгоритм Флойда—Уоршелла. WH>Всё что про него нужно знать это то что он имеет кубическую сложность. И для шаблонов С++ это смерть. И об этом я сказал. Да и вообще весь алгоритм это 4 строки.
Да дело не в этом...
Можно было так построить компиляцию, чтобы всю шаблонную нагрузку позвать из единственного cpp-файла и не париться.
И в самих шаблонах С++ можно "обрывать" длительные вычисления времени компиляции через некие промежуточные частичные специализации.
Тут вопрос в другом: для кодогенерации тебе в любом случае надо сначала как-то закодировать понятия из предметной области, а затем уже интерпретировать эту кодировку в процессе генерации текста. Так вот, что касается С++ — то как раз вещи из подобной предметной области (отличия в разметке структур и в семантике полей) — это вообще конёк шаблонов С++, тут сложно найти другой такой же заточенный именно под эту задачу тул.
WH>Адекватный человек бы признал, что сказал глупость. Но ты продолжаешь твердить что всё нормально. С++ переживёт.
Адекватный человек вообще не ставит так вопросы, для начала.
Он или поясняет на словах свою т.з., или, если не может пояснить, показывает контрпример.
Не было ни первого ни второго.
А даже если бы и был, то всё-равно вот так вопросы про "глупость" не ставят в техническом обсуждении.
Почему? Потому что часто идёт выбор среди ВАЛИДНЫХ способов решений некоей проблемы.
Т.е. все обсуждение сводится к выбору лучшего варианта решения.
Поэтому, чаще всего никому и не надо признавать никакую свою глупость, максимум что можно признать — что решение другого коллеги лучше.
Но это надо показать, с учётом стоимости решения и стоимости потенциальной поддержки в будущем и т.д. (мы же не первый раз в первый класс).
А ты вот этих базовых вещей технического диалога тоже не догоняешь, что характерно.
Очевидно же, что в коллективе работать тебе противопоказанно.
Потому что будь ты хоть тысячу раз прав в произвольном спорном моменте — у тебя нет никаких шансов свою правоту продемонстрировать. У тебя нет этого навыка. Тем более, что ты непроизвольно часто скатываешься в демагогические приёмы, и любой опытный спорщик тебя размажет даже хотя бы чисто по демагогии — ты же всегда всё переворачиваешь нахрен. ))
И что в итоге?
Ты просто будешь внутри себя знать "я прав" и единственное что мочь — посылать окружающих.
Разве не детсад? ))
WH>Хотя ты конечно можешь доказать, что всё хорошо и реализовать этот алгоритм на С++. Но только чтобы компиляторы 2007ого года это проглотили. WH>Хотя я думаю, что даже современные подавятся.
Я думаю, что ты должен помнить, что начиная с 2005-й студии никаких проблем с шаблонами по стандарту C++03 не было.
Да там уже с 2003-й не было.
Последние проблемы с шаблонами я помню у вот той промежуточной версии — 2002-й студии.
WH>Это если забыть про, то что шаблоны сами по себе генерация кода.
Верно. О чем и речь.
Там вообще все звёзды сошлись:
— ты показывал своё хорошее владение шаблонами С++;
— все 3 стороны спора об этом прекрасно в курсе;
— на шаблонах это всё заняло бы примерно столько же времени, сколько потребовалось бы лишь для того, чтобы закодировать предметную область для кодогенерации (и это еще БЕЗ самой генерации).
И почему ты тогда отрицаешь моё демократическое право признать такое положение вещей забавным?
Это реально было забавно...
Ну, если вообще в технических вопросах случаются забавные вещи — то они именно таковы.
Т.е., явная кодогенерация-то порой нужна, ОК.
Гапертон там приводил за и против.
Ты напирал на за, что, мол, она вообще может стать частью повседневной разработки.
И тут приводишь пример, который невооружённым взглядом смотрится как "мне захотелось поиграть в кодогенерацию".
Ну т.е. "мамой клянусь, кодогенерация нужна... ну вот такой пример пока только!" ))
И зря ты стал пытаться уводить разговор в тонкости сугубо технической области — в этой забавной ситуации она была вовсе не при чем.
Не говоря уже о том, что такой увод являлся грубейшей демагогией и нарушением всех мыслимых норм ведения спора, бо грубый перевод стрелок.
Там надо было просто проехать забавность всей ситуации (в комплексе всех её составляющих) и всё. Т.е. отложить этот спор до того момента, как подвернётся более цепляющий пример.
WH>И суперпупермегабыстрый GLR я до сих пор жду. Ни LR(0) или что там тебе ещё голоса в голове напоют, а полноценный GLR.
Я никому не обещал никакой код, с чего ты взял-то?
Это ж опять демагогические приемы пошли.
Я поделился наблюдаемыми результатами в одном из проектов 7-8-летней давности.
Тогда же и поделился, что наблюдал такие результаты.
И ладно, если бы это был Чайник Рассела, который по условию никто не в состоянии увидеть — я бы еще понял твою попоболь.
Но если весь и-нет завален материалами и исходниками про тот же LR(0) — то какие проблемы-то?
Твой "полноценный GLR" — это распараллеленный LR(0).
Но начать надо с LR(0) или даже забыть про эту тему. Это принципиально.
Потому что ты ж в курсе, что он парсит за O(n)?
Ты говоришь, что там "константа большая".
Но если эта константа и есть в какой-то реализации, то она живет в реализации парсера LR(0).
Поэтому, сорри, но парсер LR(0) — это уровень ноль. Сначала надо пройти его.
Как его пройти — я еще тогда же, когда первый раз зашла на эту тему речь, предложил скормить ему грамматику от лексера и посмотреть на его работу. Т.е. посмотреть на его работу, когда исходные правила (после раскрытия всех скобок) заданы с уровнем вложенности 1.
Это важно.
Потому что в этом месте ты или увидишь для себя что-то полезное или можно будет даже не продолжать.
Здравствуйте, WolfHound, Вы писали:
WH>А ещё они оба алгоритмы. И сортировка пузырьком тоже алгоритм. Значит ANTLR4 похож на сортировку пузырьком. WH>Короче давай не будем заниматься натягиванием совы на глобус.
Вот если бы пузырек был бы алгоритмом сортировки и имел бы что-то общее с Эрли, то можно было бы это обсудить. А пока что сому насилуешь ты.
VD>>Общее у них динамическая природа. Наличие очень похожих структур данных (записи Эрли и ATN). WH>Ох. WH>1)ALL это рекурсивный спуск с динамическим построением предсказателя ветвления.
Нет. ALL(*) имеет записи аналогичные записям Эрли, в которых хранится стек парсинга. Они используются для параллельного разбора правил. Так что тут на лицо соединение рекурсивного спуска с генерализованным алгоритмом вроде Эрли. Сначала АНТЛР пытается парсить не обобщенным методом (прямо как мы), а в случае его облома переходит на обобщенный (опять же как мы).
Если бы они парсили только по ДКА у них никогда бы не получилось O(n4) в худшем случае. Вот что пишет сам автор:
3.1 Predictions sensitive to the call stack Parsers cannot always rely upon lookahead DFA to make correct decisions. To handle all non-left-recursive grammars, ALL(*) prediction must occasionally consider the parser call stack available at the start of prediction (denoted γ0 in Section 5). To illustrate the need for stack-sensitive predictions, consider that predictions made while recognizing a Java method definition might depend on whether the method was defined within an interface or class definition. (Java interface methods
cannot have bodies.) Here is a simplified grammar that exhibits a stack-sensitive decision in nonterminal A:
S → xB | yC
B → Aa
C → Aba
A → b | ε
Without the parser stack, no amount of lookahead can uniquely distinguish between A’s productions. Lookahead ba predicts A → b when B invokes A but predicts A → ε when C invokes A. If prediction ignores the parser call stack, there is a prediction conflict upon ba.
Parsers that ignore the parser call stack for prediction are called Strong LL (SLL) parsers. The recursive-descent parsers
programmers build by hand are in the SLL class. By convention, the literature refers to SLL as LL but we distinguish the
terms since “real” LL is needed to handle all grammars. The above grammar is LL(2) but not SLL(k) for any k, though
duplicating A for each call site renders the grammar SLL(2).
Creating a different lookahead DFA for each possible parser call stack is not feasible since the number of stack permutations
is exponential in the stack depth. Instead, we take advantage of the fact that most decisions are not stack-sensitive and build
lookahead DFA ignoring the parser call stack. If SLL ATN simulation finds a prediction conflict (Section 5.3), it cannot be
sure if the lookahead phrase is ambiguous or stack-sensitive. In this case, adaptivePredict must re-examine the lookahead
using the parser stack γ0. This hybrid or optimized LL mode improves performance by caching stack-insensitive prediction
results in lookahead DFA when possible while retaining full stack-sensitive prediction power. Optimized LL mode applies
on a per-decision basis, but two-stage parsing, described next, can often avoid LL simulation completely. (We henceforth use SLL to indicate stack-insensitive parsing and LL to indicate stack-sensitive.)
ALL(*) is similar to Earley in that both are top-down and operate on a representation of the grammar at parse-time, but Earley is parsing not computing lookahead DFA. In that sense, Earley is not performing grammar analysis. Earley also does not manage an explicit GSS during the parse. Instead, items in Earley states have “parent pointers” that refer to other states that, when threaded together, form a GSS. Earley’s SCANNER operation correspond to ALL(*)’s move function. The PREDICTOR and COMPLETER operations correspond to push and pop operations in ALL(*)’s closure function. An Earley state is the set of all parser configurations reachable at some absolute input depth whereas an ALL(*) DFA state is a set of configurations reachable from a lookahead depth relative to the current decision.
Unlike the completely general algorithms, ALL(*) seeks a single parse of the input, which allows the use of an efficient
LL stack during the parse.
VD>>И это делает возможным использование идей из АНТЛР4 в Эрли. Добавляем динамический ДКА к Эрли и получаем алгоритм которому не нужно перебирать все возможные варинты. WH>Не делает. Ибо принципиально разные алгоритмы.
Ничего принципиально разного нет. Применить построение ДКА в Эрли вполне можно.
VD>>Главная проблема в нашем варианте восстановления заключается в том, что нам нужно сделать слишком большое число переборов. Если ДКА поможет их сократить, это даст приемлемую скорость. WH>Не поможет. Ибо переборы начинаются, когда мы пытаемся придумать терминалы или удалить текст.
Именно тут ДКА и поможет. По крайней мере с удалением так точно. Ведь у нас есть набор исходных токенов. Мы можем тупо искать их в потоке вместо перебора 100500 вариантов.
WH>Более того из-за динамической природы автомата предсказания ANTL4 использовать этот автомат для восстановления весьма сомнительное занятие.
Он использует и это работает довольно сносно.
WH>Ибо он будет каждый раз разным. Те даже если ты придумаешь как это сделать, то восстановление будет работать по-разному сразу после запуска и после часа работы.
С чего бы это? Вообще не понял о чем ты говоришь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Необходимо было "прочесть" из входа некий вектор и вернуть его. V>Ты никуда его не возвращаешь, ты оперируешь им исключительно в том же блоке кода, в котором прочел что-то из входа — я вижу чтение из входа прямо в теле main. Для решения задачи все операции чтения должны быть внутри некой ф-ии, которая вызывается из main, внутри себя читает вектор и возвращает его вызывающему коду. Иначе слил.
1)Это тебе голоса в голове напели.
2)Так ты повторишь этот код на хаскеле или таки опять расписался в том, что трепло?
V>Как сформулируешь очередную "задачку, с которой справятся только ЗТ", так приходи.
Так я уже сформулировал. То, что ты не в состоянии написать код это подтверждает.
WH>>2)Ты даже упрощённый вариант показать не можешь. Ибо трепло. V>Ибо прикольно быть модером и хамить, верно?
Ну так код то будет или как всегда трепло?
V>По этой теме уже всё с тобой ясно — ты не в состоянии показать только что тобой же обещанное.
Ясно что ты не можешь написать десяток строк кода.
Вот и вертишься.
V>Он как раз регулярно тут хамит окружающим. V>Намного-намного реже тебя, но, таки, регулярно.
Окружающим это тебе?
V>Я такой подход хорошо знаю — нахвататься по верхам и тешить своё ЧСВ за счет окружающих.
Это про тебя.
V>Стоило только чуть ноготком подцепить и выяснилось, что он сам в этой теории изрядно плавает.
Да ты её вообще не знаешь.
Путаешь рода типов и классы типов. Да ещё сорта типов придумал.
V>Как и ты, который НЕ понимает, что есть "сорта типов". )))
Только в твоей голове. В теории типов их нет.
V>Я ведь именно тебе (единственному из этих 3.5 человек) МНОГОКРАТНО говорил, что конкретно у тебя проблема в том, что ты зачастую и не хочешь знать. Лично мне со стороны даже где-то обидно за незнакомого мне человека — вроде голова твоя соображать умеет (что приятная редкость, прямо скажем), а вроде часто по верхам, кусочно гладко, не систематично и вообще... Жаль, просто жаль... Потому что у других, кто тут регулярно психует, скажем прямо, проблемы совсем другого плана, я бы даже сказал — местами совершенно непреодолимого плана. ))
Проблемы непреодолимого плана тут только у тебя.
Настолько упёртого невежду я ещё не видел.
V>Вы ж разогнали всех более-менее интересных собеседников с этого сайта в разные годы.
Это таких же безграмотных, как и ты?
V>Там вообще все звёзды сошлись: V>- ты показывал своё хорошее владение шаблонами С++; V>- все 3 стороны спора об этом прекрасно в курсе; V>- на шаблонах это всё заняло бы примерно столько же времени, сколько потребовалось бы лишь для того, чтобы закодировать предметную область для кодогенерации (и это еще БЕЗ самой генерации).
И очень хорошо зная возможности шаблонов я выбрал внешнюю кодогенерация, ибо знал что шаблоны на этой задаче сдохнут.
Ты конечно можешь легко опровергнуть мои слова показав решение на шаблонах.
Но как мы уже выяснили код ты писать не умеешь.
V>И зря ты стал пытаться уводить разговор в тонкости сугубо технической области — в этой забавной ситуации она была вовсе не при чем.
Очень даже причём. Вы же пытались гнать бред про то что там всё можно обобщить. Я показал почему нельзя обобщить.
WH>>И суперпупермегабыстрый GLR я до сих пор жду. Ни LR(0) или что там тебе ещё голоса в голове напоют, а полноценный GLR. V>Я никому не обещал никакой код, с чего ты взял-то?
С того что ты утверждаешь то что противоречит всем работам по GLR.
А значит тебе нужно либо доказать свои слова кодом, либо расписаться в том, что ты трепло.
До сих пор ты только и делаешь что расписываешься в том, что ты трепло.
Причём во всех темах.
V>Но если весь и-нет завален материалами и исходниками про тот же LR(0) — то какие проблемы-то? V>Твой "полноценный GLR" — это распараллеленный LR(0).
Так и по GLR полно материалов. И все они без исключения говорят, что GLR тормозит.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Нет. ALL(*) имеет записи аналогичные записям Эрли, в которых хранится стек парсинга.
А ещё подобные записи есть в GLL, GLR и других алгоритмах которые могут разбирать неоднозначные грамматики.
VD>Ту еже утомил упираться. Я тебе уже приводил слова автора АНТЛР-а, но ты тих их проигнорировал. Я не гордый приведу еще раз:
VD>ALL(*) is similar to Earley in that both are top-down and operate on a representation of the grammar at parse-time,
Ох. Вот на этом сходство заканчиваются. И начинаются различия.
И это очень слабое сходство.
VD>Ничего принципиально разного нет. Применить построение ДКА в Эрли вполне можно.
Зачем? Чтобы O(N^3) превратить в O(N^4)?
WH>>Ибо он будет каждый раз разным. Те даже если ты придумаешь как это сделать, то восстановление будет работать по-разному сразу после запуска и после часа работы. VD>С чего бы это? Вообще не понял о чем ты говоришь.
С того что этот автомат изменяется по мере разбора текстов и кэшируется парсером.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>А ещё подобные записи есть в GLL, GLR и других алгоритмах которые могут разбирать неоднозначные грамматики.
Не, а. Нет. Там есть GSS, т.е. лес стеков. Но вот записей описывающих грамматику там нет, ибо (ц) в них нет нужды. Парсинг ведется автоматами, которые просто "расцепляются". Их состояние хранится в GSS.
WH>Ох. Вот на этом сходство заканчиваются. И начинаются различия.
А это не хреновое такое сходство.
VD>>Ничего принципиально разного нет. Применить построение ДКА в Эрли вполне можно. WH>Зачем? Чтобы O(N^3) превратить в O(N^4)?
Это только на совсем неоднозначной грамматике, к которым грамматики ЯП не относятся.
А у нас с Эрли, при восстановлении, по любому худший случа получается, так что O(n3) у нас в кормане. Если бы не использование базового парсера было бы совсем неприемлемо.
O(n4) у них там получается из-за того, что нет мемоизации в общем случае.
WH>С того что этот автомат изменяется по мере разбора текстов и кэшируется парсером.
И с какого перепуга он будет разным то?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
WH>>Ох. Вот на этом сходство заканчиваются. И начинаются различия. VD>А это не хреновое такое сходство.
Это очень слабое сходство.
Алгоритмы совершенно разные.
Для ALL(*) леворекурсивная грамматика худший случай. Для Эрли лучший.
ALL(*) построен вокруг предсказания ветвления. Эрли никакое предсказание не нужно. Он и так хорошо работает.
У ALL(*) сложности вот с этой грамматикой. Для Эрли тут вообще никаких проблем нет.
S > xB | yC
B > Aa
C > Aba
A > b | ?
VD>А у нас с Эрли, при восстановлении, по любому худший случа получается, так что O(n3) у нас в кормане. Если бы не использование базового парсера было бы совсем неприемлемо.
Он получается из-за того, что все терминалы и нетерминалы внезапно становятся nullable. И грамматика из-за этого становится сильно неоднозначной.
VD>O(n4) у них там получается из-за того, что нет мемоизации в общем случае.
А Эрли он про мемоизацию целиком и полностью. Он работает исключительно благодаря тотальной момоизации.
Собственно, само понятие динамическое программирование это про тотальную мемоизацию.
И ты путаешь это понятие с динамическим построением предсказателя ветвления. Это принципиально разные вещи.
WH>>С того что этот автомат изменяется по мере разбора текстов и кэшируется парсером. VD>И с какого перепуга он будет разным то?
С такого что он строится на основе разбираемых текстов. Это же главная фишка ALL(*).
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Это очень слабое сходство.
Для нас достаточное. Я бы все подумал нельзя ли использовать построение вот такого вот ДКА для того принятия решения при обломе.
Как вариант, вместо ДКА делать динамическую левую факторизацию записей Эрли. По сути — это тоже что ДКА будет.
У нас (с огромной вероятностью) дует один путь в котором будет куда проще делать предсказания. И на скорости это должно сказать очень положительно.
WH>Для ALL(*) леворекурсивная грамматика худший случай. Для Эрли лучший.
Для ALL(*) левая рекурсия вообще неприемлема. Но то рекурсия. А Эрли за свою обобщенность платит тормозами.
WH>ALL(*) построен вокруг предсказания ветвления. Эрли никакое предсказание не нужно. Он и так хорошо работает.
В том то и дело, что не хорошо. Медленно он работает. Очень медленно.
WH>У ALL(*) сложности вот с этой грамматикой. Для Эрли тут вообще никаких проблем нет. WH>
WH>S > xB | yC
WH>B > Aa
WH>C > Aba
WH>A > b | ?
WH>
Нет у ALL(*) с этим проблем. Он переключится на более сложный вариант "stack-sensitive decision" и все.
WH>Он получается из-за того, что все терминалы и нетерминалы внезапно становятся nullable. И грамматика из-за этого становится сильно неоднозначной.
Ну, вот и подумай, что если вместо "скипания" построить ДКА или факторизовать грамматику?
WH>А Эрли он про мемоизацию целиком и полностью. Он работает исключительно благодаря тотальной момоизации.
Это рассуждения как у Вдимоса. Только у лего LR(0), а у тебя мемоизация. Проблема то в том, что даже с мемоизацией получается 100500 бессмысленных переборов. Это проблема генерализации.
WH>И ты путаешь это понятие с динамическим построением предсказателя ветвления. Это принципиально разные вещи.
Я вообще не хочу подобными терминами пользоваться, бо они только все запутывают.
WH>>>С того что этот автомат изменяется по мере разбора текстов и кэшируется парсером. VD>>И с какого перепуга он будет разным то? WH>С такого что он строится на основе разбираемых текстов. Это же главная фишка ALL(*).
Для одного входа все будет одинаковым. Плюс ДКА не более чем кэш. С ним и без него все должно работать одинаково, только с разной скоростью.
Ладно, эта музыка будет вечной. (ц) Надо завязывать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AlexRK, Вы писали:
ARK>то будет же задница. Придется все равно писать что-то типа "if (size1 = size2)..." По факту size1 и size2 — просто флаги, для которых при компиляции мы можем сказать только одно: либо они равны между собой, либо нет.
Вот пример посложнее.
appVect : Vect n a -> Vect m a -> Vect (n + m) a
appVect Nil v2 = v2
appVect (x1 :: v1) v2 = x1 :: appVect v1 v2
main : IO ()
main = do
putStrLn "Hello world"
size1 <- getNat
size2 <- getNat
let vect11 = makeVect size1 size1
let vect21 = makeVect size2 size1
let vect12 = makeVect size1 size2
let vect22 = makeVect size2 size2
putStrLn (show vect11)
putStrLn (show vect21)
putStrLn (show vect12)
putStrLn (show vect22)
putStrLn $ show $ zipVect (appVect vect11 vect22) (appVect vect12 vect21)
Здравствуйте, VladD2, Вы писали:
WH>>Это очень слабое сходство. VD>Для нас достаточное. Я бы все подумал нельзя ли использовать построение вот такого вот ДКА для того принятия решения при обломе.
Вот и подумай.
А я не буду, ибо в принципе не понимаю куда его можно засунуть.
VD>Как вариант, вместо ДКА делать динамическую левую факторизацию записей Эрли. По сути — это тоже что ДКА будет. VD>У нас (с огромной вероятностью) дует один путь в котором будет куда проще делать предсказания. И на скорости это должно сказать очень положительно.
1)Если и скажется, то не сильно. Ибо на практике основные переборы идут там, где левую факторизацию не сделать.
2)Это такая головная боль
WH>>Для ALL(*) леворекурсивная грамматика худший случай. Для Эрли лучший. VD>Для ALL(*) левая рекурсия вообще неприемлема. Но то рекурсия. А Эрли за свою обобщенность платит тормозами.
Тем более. Это говорит о том, что структура алгоритмов совершенно разная.
VD>Нет у ALL(*) с этим проблем. Он переключится на более сложный вариант "stack-sensitive decision" и все.
Это и есть проблемы.
WH>>Он получается из-за того, что все терминалы и нетерминалы внезапно становятся nullable. И грамматика из-за этого становится сильно неоднозначной. VD>Ну, вот и подумай, что если вместо "скипания" построить ДКА или факторизовать грамматику?
Так переборы от этого никуда не денутся.
WH>>А Эрли он про мемоизацию целиком и полностью. Он работает исключительно благодаря тотальной момоизации. VD>Это рассуждения как у Вдимоса. Только у лего LR(0), а у тебя мемоизация. Проблема то в том, что даже с мемоизацией получается 100500 бессмысленных переборов. Это проблема генерализации.
Нет. Это у тебя рассуждения как у Вдимаса. Увидел слово динамический и понесло.
Я тебе уже несколько сообщений пытаюсь объяснить, что в разных контекстах они имеют разный смысл.
И динамическое программирование не имеет ничего общего с динамическим построением предсказателя.
WH>>И ты путаешь это понятие с динамическим построением предсказателя ветвления. Это принципиально разные вещи. VD>Я вообще не хочу подобными терминами пользоваться, бо они только все запутывают.
Это устоявшийся термин, придуманный в 1940 году.
Согласен термин запутывающий. Но та же фигня с семантическим анализом. Но ты за этот запутывающий термин насмерть стоишь
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
