Можете ли вы сделать логическое программирование в Scala?

Question

Я где-то читал, что Pattern Matching, подобный тому, который поддерживается в Scala функцией соответствия / совпадения, на самом деле был заимствован из языков логики, таких как Prolog.

Можете ли вы использовать Scala для элегантного решения таких проблем, как проблема подключенного графика? например https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html

Answer 1

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

Кроме того, сопоставление с образцом само по себе совершенно не подходит для этого по многим причинам. Рассмотрим, например, сам базовый запрос: path(1, 5, P). При сопоставлении с образцом в Scala 1, 5 и P являются выходами . Вы не можете предоставить вход, который мог бы использоваться для вывода.

С Прологом это похоже на то, что при условии, что 1 и 5 фиксированы, какие возможные значения может принимать P? Вот только как работает сопоставление с образцом.

Редактировать: В Scala 2.10 сопоставление с образцом теперь компилируется в промежуточную операцию, например, для-понимания, а затем перевод по умолчанию дополнительно оптимизируется. Тем не менее, можно определить свой собственный класс для обработки сопоставления с образцом, и я видел, как он использовался для реализации входа в пролог - хотя я не могу найти ссылку, извините.

Answer 2

Языки Haskell и функционального программирования стали прямым источником вдохновения для Scala. Одним из приложений, унаследованных от этих языков, является разработка предметно-ориентированных языков (DSL). В Haskell есть довольно много DSL для логического программирования (Пролог). Должно быть вполне возможно перенести такую ​​библиотеку DSL в Scala, если это еще не произошло.

Answer 3

Я знаю, что опоздал, но в поисках re: kanren я нашел [мертвую ссылку] Также есть это: http://code.google.com/p/scalalogic/

Я просто изучаю эту тему и плохо понимаю ее, но в любом случае ссылки могут быть интересны.

Answer 4

См. http://kanren.sourceforge.net/, чтобы узнать, как функциональное и логическое программирование не так уж далеко друг от друга. Структуры потоков являются ключом к пониманию того, как две парадигмы могут объединиться. «Поднимая» стандартные функции в потоковый / логический формат, они могут демонстрировать поведение решения проблем, очень похожее на Prolog.

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

Answer 5

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

Однако существует относительно новый подход к отображению логических переменных в функциональные конструкции. В конкретном случае язык логики, близкий к прологу, Curry curry переведен на Haskell. Что является очень необычным в этом подходе, так это то, что логические переменные моделируются с ленивостью. Для получения дополнительной информации см. KiCS2: новый компилятор от Curry до Haskell . Может быть, lazy val может быть использован для этой цели.

Answer 6

Styla - довольно полный интерпретатор Пролога, написанный на Scala, полученный из ядра Пролог (см. Fluents: Рефакторинг Пролога для Равномерное отражение и взаимодействие с внешними объектами в CL'2000).

Код с подлинно открытым исходным кодом (лицензия Apache) размещен по адресу:

http://code.google.com/p/styla/

и он разработан с учетом простоты и расширяемости - надеясь было бы полезно людям, экспериментирующим с новыми расширениями Prolog или альтернативные языки логического программирования.

Styla использует несколько вкусностей Scala, недоступных в Java:

• функции высшего порядка, карты, складки, классы дел и т. Д.
• парсер комбинаторов - "DCG бедняков"
• Элегантные неявные преобразования Скалы между списки, массивы, последовательности и т. д.
• целые и десятичные числа Scala произвольной длины (с естественный синтаксис, в отличие от Java)
• Строки Scala "" "..." "" - для регулярных выражений и встраивания Пролог код прямо в классах Scala
• несколько абстракций ввода / вывода, доступных в Scala, которые просматривать такие вещи, как файловые операции как итераторы - естественное совпадение с оригинальными Fluents Пролог ядра на основе Java, из которого был получен Styla

(Текст взят из: http://groups.google.com/group/comp.lang.prolog/browse_thread/thread/4cd835d2c82fce02/505688d4b0be5528)

Answer 7

Scala не является языком логического программирования, но вы действительно можете определить DSL для логического программирования в Scala. Обратите внимание, что Scala заимствует много понятий из функционального программирования - его можно и нужно использовать в функциональном стиле. Функциональное и логическое программирование являются декларативными, но существенно различаются. Вы можете прочитать больше здесь .

Answer 8

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

https://github.com/sonoisa/Prolog-in-Scala/blob/master/PrologInScalaSample.scala

Вышеуказанное указывает на пару тестовых программ. Интерпретатор Prolog написан на Scala таким образом, что предложения Prolog могут быть встроены как объекты Scala, написанные на Scala. Я не совсем понимаю магию, стоящую за этим, вот пример того, как написана функция tak:

tak('X, 'Y, 'Z, 'A) :- (
 'X =< 'Y, CUT, 'Z === 'A)
tak('X, 'Y, 'Z, 'A) :- (
 'X1 is 'X - 1,
 'Y1 is 'Y - 1,
 'Z1 is 'Z - 1,
 tak('X1, 'Y, 'Z, 'A1),
 tak('Y1, 'Z, 'X, 'A2),
 tak('Z1, 'X, 'Y, 'A3),
 tak('A1, 'A2, 'A3, 'A)
)

Я полагаю, что он выполняет возврат через продолжения и имеет свой собственный реализация переменной среды и унификация.

Если вы посмотрите на код, например, unifyTerm, вы увидите, что он активно использует сопоставление с образцом, что ставит Scala в особый позиция для реализации логических движков.

С наилучшими пожеланиями

Answer 9

Вы также можете взглянуть на scampi (решатель программирования ограничений в Scala): https://bitbucket.org/pschaus/scampi/wiki/Home Jacop CP Solver также имеет Scala API.

Answer 10

Сопоставление с образцом как таковое непосредственно не полезно для логического программирования, поскольку не объединяет переменные .