Можете ли вы сделать логическое программирование в Scala?
Я где-то читал, что Pattern Matching, подобный тому, который поддерживается в Scala функцией совпадения / регистра, на самом деле был заимствован из языков логики, таких как Prolog.
Можете ли вы использовать Scala для элегантного решения таких проблем, как проблема подключенного графика? например, https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html
10 ответов
Нет, вы не можете сделать это, если вы не создадите логический движок, который побеждает всю цель.
Более того, сопоставление с образцом само по себе совершенно не подходит для этого по многим причинам. Рассмотрим, например, сам базовый запрос: path(1, 5, P), При сопоставлении с образцом в Scala 1, 5 и P являются выходными данными. Вы не можете предоставить вход, который мог бы использоваться, чтобы произвести вывод.
С Прологом это похоже на то, что при условии, что 1 и 5 фиксированы, какие возможные значения может принимать P? Вот только сейчас, как работает сопоставление с образцом.
Редактирование: В Scala 2.10 сопоставление с образцом теперь компилируется в промежуточную операцию, например, для-понимания, а затем перевод по умолчанию дополнительно оптимизируется. Тем не менее, можно определить свой собственный класс для обработки сопоставления с образцом, и я видел, как он использовался для реализации входа в пролог - хотя я не могу найти ссылку, извините.
Смотрите http://kanren.sourceforge.net/ для подробностей о том, как функциональное и логическое программирование не так уж далеко друг от друга. Структуры потока являются ключом к пониманию того, как две парадигмы могут объединиться. "Поднимая" стандартные функции в потоковый / логический формат, они могут демонстрировать поведение решения проблем, которое во многом похоже на Prolog.
Вы также должны посмотреть на комбинаторы парсеров. При наличии правильных комбинаторов возможны эффективные прологоподобные решения.
Языки Haskell и Functional Programming были прямым источником вдохновения для Scala. Одним из приложений, унаследованных от этих языков, является разработка предметно-ориентированных языков (DSL). В Haskell довольно много DSL для логического программирования (Пролог). Должно быть вполне возможно перенести такую библиотеку DSL в Scala, если это еще не произошло.
Я знаю, что опоздал, но в поисках: kanren я нашел эту [мертвую ссылку] Также есть это: http://code.google.com/p/scalalogic/
Я просто изучаю эту тему и очень слабо понимаю ее, но в любом случае ссылки могут представлять интерес.
Традиционный ответ на ваш вопрос должен показать, что логические переменные не могут быть напрямую смоделированы в языке, который предполагает, что все является значением.
Однако существует относительно новый подход к отображению логических переменных в функциональных конструкциях. В конкретном случае язык, близкий к прологическому логике карри, карри переводится на Haskell. В этом подходе очень необычно то, что логические переменные моделируются с ленивостью. Для получения дополнительной информации см. KiCS2: новый компилятор от Curry до Haskell. Может быть lazy val может быть использован для этой цели.
Styla - довольно полный интерпретатор Пролога, написанный на Scala, основанный на Kernel Prolog (см. Fluents: Рефакторинг Пролога для равномерного отражения и взаимодействия с внешними объектами в CL'2000).
Подлинно открытый исходный код (лицензия Apache) размещен по адресу:
http://code.google.com/p/styla/
и он разработан с учетом простоты и расширяемости - надеясь, что он будет полезен для людей, экспериментирующих с новыми расширениями Prolog или альтернативными языками логического программирования.
Styla использует несколько вкусностей Scala, недоступных в Java:
- функции высшего порядка, карты, складки, классы дел и т. д.
- комбинаторные парсеры - "DCG бедняка"
- Элегантные неявные преобразования Scala между списками, массивами, последовательностями и т. Д.
- Произвольные целые и десятичные числа Scala (с естественным синтаксисом, в отличие от Java)
- Строки Scala """...""" - для регулярных выражений и для встраивания кода Prolog непосредственно в классы Scala
- несколько доступных в Scala абстракций ввода-вывода, которые рассматривают такие вещи, как файловые операции, в качестве итераторов - естественное совпадение с исходными Fluents из основанного на Java Пролога ядра, из которого был получен Styla
(Текст взят из: http://groups.google.com/group/comp.lang.prolog/browse_thread/thread/4cd835d2c82fce02/505688d4b0be5528)
Scala не является языком логического программирования, но вы действительно можете определить DSL для логического программирования в Scala. Обратите внимание, что Scala заимствует много понятий из функционального программирования - его можно и нужно использовать в функциональном стиле. Функциональное и логическое программирование являются декларативными, но существенно различаются. Вы можете прочитать больше здесь.
Только что нашел хорошую реализацию Пролога в 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 в особое положение для реализации логических движков.
С уважением
Сопоставление с образцом как таковое непосредственно не полезно для логического программирования, так как оно не объединяет переменные.
Вы также можете взглянуть на scampi (средство программирования ограничений в Scala): https://bitbucket.org/pschaus/scampi/wiki/Home Jacop CP Solver также имеет Scala API.
Я нашел этот http://yieldprolog.sourceforge.net/ как источник для методов реализации, подобных Prolog, а не недокументированный исходный код или загадочные библиотеки.
Но я интересуюсь Scala всего несколько дней назад, поэтому задал тот же вопрос на users.scala: https://users.scala-lang.org/t/yield-prolog-unification-and-coroutines-in-scala/4433
На языке, обеспечивающем объединяющий возврат, должна быть доступна функция генератора, которая может возвращать и сохранять вычисления в середине выполнения функции. Тот же эффект может быть достигнут при использовании сопрограмм или зеленых нитей, которые производят частичные решения в цепочке возврата.