Pull to refresh

Comments 10

Главное, в моем представлении, это то, что Prolog стремится к наибольшей эффективности для своих задач и готов пожертвовать ради этого чистотой (в смысле побочных эффетов) и «логичностью» (в смысле, что там очень широко используются extra-logical features, такие как cut). miniKanren же наоборот заботится о «логичности» и благодаря этому программы получаются реляционными, то есть их вот так можно запускать в разные стороны. Наверное не будет сильным враньем сказать, что miniKanren сделан специально для парадигмы «программы как отношения» и лучше работает в ней, чем другие логические языки.

Больше деталей есть в стандартном (и очень большом) ответе на этот вопрос от автора языка.
Интересно, как мир переплетается. Примерно в те же года мы делали подобный язык XSG — функционально-логический, с введением свободных переменных и т.п. Правда дальше реализации (пришлю ссылку, правда это еще делалось во времена cvs) и одной публикации (XSG: Fair Language with Built-in Equality — гуглится по названию или могу прислать PDF) дело не прошло — ушли в другие темы. Было бы интересно сравнить наш и Ваш подходы.

Не пробовали на нем запрограммировать какую-нибудь задачу типа «У кого рыба» (http://udel.edu/~os/riddle.html)?
Если что, мы к созданию miniKanren никакого отношения не имеем, мы только пытаемся заставить его работать чуточку лучше. Стоило более явно указать это в тексте.

Я прочитал Вашу статью, cудя и по семантике, и по примерам, XSG действительно сильно похож на базовую версию miniKanren (сильнее, чем тот же prolog). При этом в miniKanren'е не предусмотрены ни ленивость, ни недетерминизм в порядке поиска. У меня правда есть ощущение, что из-за недетерминизма при выборе исполняемого вызова функции (если я правильно понял) это должно работать неэффективно для больших по размеру программ (в miniKanren'е по крайней мере все попытки «попробуем несколько порядков одновременно» приводили к критическому замедлению).

Не пробовали на нем запрограммировать какую-нибудь задачу типа «У кого рыба» (http://udel.edu/~os/riddle.html)?

Да, у нас в лаборатории велась (не мной) работа по использованию miniKanren для всяких логических задачек и «загадка Эйнштейна» была первой из них. Не знаю получилось ли сразу с ней, но чтобы заставить заработать некоторые другие, насколько я знаю, пришлось использовать нетривиальные техники вроде мемоизации и, как раз, суперкомпиляции.
Правильно ли я понимаю, что у Вас это научная работа? Т.е. писать статьи, содержащие обзоры и сравнения с другими решениями, придется? Наш код открыт, написан на Haskell, можно поиграться. Надеюсь, что Haskell за 9-10 лет не слишком изменился…

Есть коллекция примеров, которые, кстати, вполне мотивировали научную деятельность: удовлетворения личного любопытства за государственный счет ;).

Да, если активно использовать «обратные» вычисления, то замедления возможны. Если же писать программу как обычную функциональную, то замедления от размера быть не должно (за исключением далеко не оптимальной реализации). С другой стороны, в ситуациях, когда определение обратной функции «прямолинейно» (как, например, вычитание в унарной системе из сложения), то замедление было небольшим.

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

Да, у нас в лаборатории велась (не мной) работа по использованию miniKanren для всяких логических задачек и «загадка Эйнштейна» была первой из них. Не знаю получилось ли сразу с ней, но чтобы заставить заработать некоторые другие, насколько я знаю, пришлось использовать нетривиальные техники вроде мемоизации и, как раз, суперкомпиляции.

А есть где почитать про результаты?
Правильно ли я понимаю, что у Вас это научная работа? Т.е. писать статьи, содержащие обзоры и сравнения с другими решениями, придется? Наш код открыт, написан на Haskell, можно поиграться. Надеюсь, что Haskell за 9-10 лет не слишком изменился…

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

Есть коллекция примеров, которые, кстати, вполне мотивировали научную деятельность

Это которые тесты в репозитории? Вижу знакомые слова. А в чем состоит Driving task?

А есть где почитать про результаты?

Боюсь, что пока нет. Это вроде как work in progress.
Это которые тесты в репозитории? Вижу знакомые слова.

Да, тесты в файле test.xsg. Там синтаксис не такой, как в статье. В статье более научно-принятый, а в test.xsg — более удобный. Сразу отмечу, что функции имеют и арность, и коарность, но т.к. они заданы, то скобки для правильной и единственной интерпретации выражений не нужны.

А в чем состоит Driving task?

К сожалению, уже не помню в чем был смысл задачи… Формально надо найти все строки, которые удовлетворяют соотношению:
strX++strQ++'B'+c++strP++'A'++strY = strY++strQ++'A'++c++strQ++'B'++strX (где ++ — конкатенация, а c — какой-то символ).

P.S. Недавно вышла пара препринтов про суперкомпиляцию, если интересуетесь.
Очень не хватает отдельно подзаголовка «Мотивация»(зачем это надо, и почему уже имеющиеся языки не годятся).
Мне после беглого ознакомления показалось что это «еще один клон Пролога».
Вообще многие статьи о новом\модном\любимом\убийце_вон_того_языка языке грешат отсутствием внятного пояснения зачем он читателю нужен.
Да, справедливое замечание.
Мотвацией для нашего исследования было исправление неприятной проблемы в существующем (и даже известном в узких кругах) языке. Вопрос о мотивации и применимости самого языка более сложный, и я не настолько сильно в неё верю, чтобы подробно это расписать.
Sign up to leave a comment.