Каковы основные технические различия между Prolog и miniKanren в отношении логического программирования?

Question

Когда я хочу, чтобы прочитать о логическом программировании я всегда спотыкаются два «главных» способов сделать это в наше время:

• miniKanren, minilanguage введен в The Reasoned Schemer и популярных на данный момент из-за core.logic.
• Пролог, первый «большой» язык программирования логики.

Что мне сейчас интересно: Каковы основные технические различия между ними? Являются ли они очень похожими в подходе и реализации, или они используют совершенно разные подходы к логическому программированию? С какими отраслями математики они берутся, и каковы теоретические основы?

Answer 1

Прежде всего, позвольте мне поблагодарить вас за прекрасный значок pw0n1e.

Это сложный вопрос для ответа, во многом потому, что существует так много вариантов как miniKanren, так и Prolog. miniKanren и Prolog - действительно семьи языков, что затрудняет сравнение их возможностей или даже того, как они используются на практике. Из-за этого, пожалуйста, возьмите все, что я собираюсь сказать с осторожностью: если я скажу, что Prolog использует поиск по глубине, имейте в виду, что многие реализации Prolog поддерживают другие стратегии поиска и что альтернативные стратегии поиска также могут быть закодированы в мета -строчный уровень. Тем не менее, miniKanren и Prolog имеют разную философию дизайна и делают разные компромиссы.

Пролог является одним из двух классических языков программирования символического искусственного интеллекта (другим классическим языком является Lisp). Prolog превосходит при внедрении символических основанных на правилах систем, в которых декларативные знания кодируются в логике первого порядка. Язык оптимизирован для выразительности и эффективности для этих типов приложений, иногда за счет логической чистоты. Например, по умолчанию Prolog не использует команду «выполнить проверку» в унификации. С математической/логической точки зрения эта версия объединения неверна. Тем не менее, проверка происшествия является дорогостоящей, и в большинстве случаев отсутствие проверки происходит не проблема. Это очень прагматичное дизайнерское решение, так же как использование Prolog для поиска по глубине и использование разреза (!) для управления обратным трассировкой. Я уверен, что эти решения были абсолютно необходимы при работе на аппаратных средствах 1970-х годов, и сегодня они очень полезны при работе с большими проблемами и при работе с огромными (часто бесконечными!) Пространствами поиска.

Пролог поддерживает множество «экстра-логические» или «не-логические» функции, в том числе вырезать, assert и retract, проекции переменных для арифметики с использованием is, и так далее. Многие из этих функций облегчают выражение сложного потока управления и манипулируют глобальной базой данных Prolog о фактах. Одна очень интересная особенность Prolog заключается в том, что код Prolog сам хранится в глобальной базе данных фактов и может быть запрошен во время выполнения.Это делает тривиальным писать мета-интерпретаторы, которые изменяют поведение кода Пролога под интерпретацией. Например, можно закодировать поиск по ширине в Prolog с помощью мета-интерпретатора, который изменяет порядок поиска. Это чрезвычайно мощный метод, который не известен за пределами мира Prolog. «Искусство Пролога» подробно описывает эту технику.

Огромное усилие ушло на улучшение реализации Prolog, большинство из которых основаны на Warren Abstract Machine (WAM). WAM использует побочную модель, в которой значения деструктивно назначаются логическим переменным, причем эти побочные эффекты отменяются при обратном отслеживании. Многие функции могут быть добавлены в Prolog, расширяя инструкции WAM. Одним из недостатков такого подхода является то, что документы по реализации Prolog могут быть трудночитаемыми без четкого понимания WAM. С другой стороны, у разработчика Prolog есть общая модель для обсуждения проблем реализации. Проводилось много исследований параллельно с Прологом, кульминацией которого стал Андорра Пролог в 1990-х годах. По крайней мере, некоторые из этих идей живут в Ciao Prolog. (Ciao Prolog полна интересных идей, многие из которых выходят далеко за рамки стандарта Prolog.)

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

miniKanren был разработан как минимальный логический язык программирования, с небольшой, легко понятной и легко взломанной реализацией. miniKanren был первоначально встроен в Scheme и был перенесен на десятки других языков-хостов за последнее десятилетие. Самая популярная реализация miniKanren - «core.logic» в Clojure, которая теперь имеет много Prolog-подобных расширений и ряд оптимизаций. Недавно ядро ​​реализации miniKanren было еще более упрощено, в результате чего появилось крошечное «микроядро» под названием «microKanren». Затем miniKanren может быть реализован поверх этого ядра microKanren. Портирование microKanren или miniKanren на новый язык хоста стало стандартным упражнением для программистов, изучающих miniKanren. В результате большинство популярных языков высокого уровня имеют по крайней мере одну реализацию miniKanren или microKanren.

Стандартные реализации miniKanren и microKanren не содержат мутаций или других побочных эффектов, за одним исключением: некоторые версии мини-каранна используют равенство указателя для сравнения логических переменных. Я считаю это «доброкачественным эффектом», хотя многие реализации избегают даже этого эффекта, передавая счетчик через реализацию. Глобальной базы данных фактов также нет. Философия внедрения miniKanren вдохновлена ​​функциональным программированием: следует избегать мутации и эффектов, и все языковые конструкции должны уважать лексическую сферу. Если вы внимательно посмотрите на реализацию, вы можете даже обнаружить пару монадов. Реализация поиска основана на объединении и управлении ленивыми потоками, еще раз без использования мутации. Эти варианты реализации приводят к очень разным компромиссам, чем в Prolog. В Prolog переменный поиск - это постоянное время, но для возврата требуется отменить побочные эффекты. В miniKanren переменный поиск дороже, но обратный поиск является «бесплатным». Фактически, в miniKanren нет возврата, из-за того, как обрабатываются потоки.

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

miniKanren использует проверку наличия для объединения и использует полный поиск перемежения вместо поиска по глубине.Поиск в режиме чередования использует больше памяти, чем поиск по глубине, но может найти ответы в некоторых случаях, в которых поиск по глубине будет расходиться/цикл навсегда. miniKanren поддерживает несколько дополнительных логических операторов --- conda, condu и project, например. conda и condu можно использовать для имитации пролога Пролога, а project можно использовать для получения значения, связанного с логической переменной.

Присутствие conda, condu и project --- и способность легко модифицировать стратегию поиска --- позволяет программистам использовать miniKanren в качестве встроенного Пролог-подобного языка. Это особенно верно для пользователей Clojure's core.logic, который включает в себя многие Prolog-подобные расширения. Это «прагматичное» использование miniKanren, по-видимому, объясняет большую часть использования miniKanren в промышленности. Программисты, которые хотят добавить основанную на знаниях систему рассуждений в существующее приложение, написанное на Clojure или Python или JavaScript, обычно не заинтересованы в переписывании всего своего приложения в Prolog. Внедрение небольшого логического языка программирования в Clojure или Python гораздо более привлекательно. По-видимому, внедренная реализация Prolog будет работать с этой целью. Я подозреваю, что miniKanren стал популярным в качестве встроенного логического языка из-за крошечной и чистой реализации ядра, а также разговоров, сообщений в блогах, учебных пособий и других учебных материалов, появившихся после выхода «The Reasoned Schemer».

В дополнение к использованию miniKanren как прагматичного встроенного логического языка программирования, аналогичного духу Prolog, miniKanren используется для исследований в «реляционном» программировании. То есть при написании программ, которые ведут себя как математические отношения, а не математические функции. Например, в схеме функция append может добавлять два списка, возвращая новый список: вызов функции (append '(a b c) '(d e)) возвращает список (a b c d e). Однако мы можем рассматривать и append как трехпозиционное отношение, а не как функцию с двумя аргументами. Затем вызов (appendo '(a b c) '(d e) Z) связывает логическую переменную Z со списком (a b c d e). Конечно, вещи становятся более интересными, когда мы помещаем логические переменные в другие позиции. Вызов (appendo X '(d e) '(a b c d e)) ассоциирует X с (a b c), тогда как звонок (appendo X Y '(a b c d e)) ассоциирует X и Y с парами списков, которые при добавлении равны (a b c d e). Например, X = (a b) и Y = (c d e) - одна такая пара значений. Мы также можем написать (appendo X Y Z), в котором будет выпущено бесконечное множество тройк списков и Z, так что добавление X к Y дает Z.

Эта реляционная версия append может быть легко выражена в Prolog и действительно показана во многих учебных пособиях Prolog. На практике более сложные программы Prolog, как правило, используют как минимум несколько дополнительных логических функций, таких как разрез, которые препятствуют способности обрабатывать полученную программу как отношение. Напротив, miniKanren явно разработан для поддержки этого стиля реляционного программирования. В более поздних версиях miniKanren есть поддержка решения символических ограничений (symbolo, numbero, absento, ограничения неравномерности, номинальное логическое программирование), чтобы упростить запись нетривиальных программ в качестве отношений. На практике я никогда не использую какие-либо экстра-логические функции miniKanren, и я пишу все свои программы miniKanren в качестве отношений. Наиболее интересными реляционными программами являются реляционные интерпретаторы для подмножества Схемы. У этих переводчиков есть много интересных способностей, таких как создание миллиона программ Scheme, которые оцениваются в списке (I love you), или тривиально генерирующие quines (программы, которые оценивают для себя).

miniKanren делает ряд компромиссов, чтобы включить этот реляционный стиль программирования, который сильно отличается от компромиссов Prolog делает. Со временем miniKanren добавила больше символических ограничений, фактически став символически ориентированным языком программирования Constraint Logic. Во многих случаях эти символические ограничения делают практически невозможным использование дополнительных логических операторов, таких как condu и project. В других случаях эти символические ограничения недостаточны. Лучшая поддержка символических ограничений - одна из активных областей исследований miniKanren, а также более широкий вопрос о том, как писать более крупные и более сложные программы в качестве отношений.

Короче говоря, как мини-Канран, так и Пролог имеют интересные функции, реализации и использования, и я думаю, что стоит изучить идеи с обоих языков. Есть и другие очень интересные языки логического программирования, такие как Mercury, Curry и Gödel, каждый из которых имеет свое собственное логическое программирование.

Я закончу с несколькими miniKanren ресурсов:

Основной сайт miniKanren: http://minikanren.org/

интервью я дал на реляционных программирования и miniKanren, в том числе по сравнению с Прологом: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

Cheers,

--Will

Answer 2

Ориентировочный Ответ:

AFAIK, «Мотивированное Schemer» представило основную логику программирование в схеме-у синтаксиса и функциональный стиль программирования, добавляя в частности постоянных целями «#U» (провал) и «#s "(suceeed) для булевых значений" #t "и" #f ". Он использовал тот же подход к логическому программированию, что и Prolog: Unification и backtracking search. Я посмотрю, есть ли у меня какое-то время, чтобы получить эту книгу с моей полки в выходные. Филиал математики - это ограниченная форма логики первого порядка, в данном случае предложения Хорна и Разделение разрешения. См.: Computational Logic: Memories of the Past and Challenges for the Future от Джона Алана Робинсона и The early years of logic programming Роберта Ковальского для холодного старта.