Эмуляция пролога возврата в F #

Question

В настоящее время я участвую в проекте по разработке приложения, способного рассмотреть набор узлов и соединений и найти кратчайший путь (распространенная и общеизвестная проблема) между двумя узлами (при разрешенных соединениях).Ну, на самом деле мне не нужно создавать приложение с нуля, а нужно просто «преобразовать» уже существующее приложение Prolog в f #.Я подумал об этом и, наконец, задал себе один вопрос: «Вместо разработки специального решения и реализации новых алгоритмов, специально связанных с этой проблемой, могу ли я создать программу, способную принимать такие факты, как Prolog, и использовать их для выполнения запросов или чего-то еще?Аналогично? "Итак, рассматривая теперь эту новую проблему (преобразование Пролога в F #), мне нужно найти способ создать факты, подобные этим:

myfact1(el1, el2,..., eln).
myfact2(el1, el2,..., elm).
...
myfactk(el1, el2,..., elp).

к чему-то с похожим синтаксисом вроде:

fact factname1: el1 el2 ... eln;
fact factname2: el1 el2 ... elm;
...
fact factnamek: el1 el2 ... elp;

Я знаю, что F # очень хорошо подходит для разбора, поэтому я думаю, что это, вероятно, не будет проблемой.

ОК!Теперь, когда он проанализирован, я должен определить алгоритм, который при синтаксическом анализе кода сохраняет все факты в некотором виде знаний (не более чем в таблице).Чтобы затем создать все необходимые ассоциации.

Например, решение может быть хеш-таблицей, которая учитывает все ассоциации

factname1 -> el1
factname1 -> el2
...
factname1 -> eln
factname2 -> el1
factnale2 -> el2
...
factname2 -> elm
factname3 -> el1
...
...
factnamek -> el1
factnamek -> el2
...
factnamek -> elp

Таким образом, я всегда буду в состоянии решать запросы.Например, рассмотрим следующий факт Пролога

mother(A, B) % This means that A is mother of B
mother(C, D)

В F # я создаю

факт мать: AB;фактическая мать: CD;

Моя хеш-таблица:

mother -> A |B мама -> C |D

Первый столбец - это имя факта, а второй - значение (здесь кортеж).

Если я хочу найти: «кто мать B» -> яискать мать и искать значение, я нахожу B, я смотрю в кортеже и обнаруживаю A!

Ну, это похоже на работу.Но факты легко реализовать.А как насчет правил?Например, правило родителей:

parents(A, B, C) :- mother(A, C), father (B, C)

В F # используется мой синтаксис?Ну, у меня возникла эта идея:

rule parents: A, B, C => mother A C and father B C

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

Answer 1

Там был похожий вопрос об интеграции прологоподобных программ в F # в последнее время.

F # не имеет встроенной поддержки для выполнения поиска, основанного на возврате (например, Prolog). У вас есть два основных варианта:

• Повторно внедрите алгоритм в F #, используя рекурсию и вернув кодировку самостоятельно.
• Реализация интерпретатора Пролога и представление фактов с использованием некоторого дискриминационного объединения.

Чтобы реализовать поиск по кратчайшему пути, я бы, вероятно, просто реализовал алгоритм непосредственно в F # (использование функционального программирования будет весьма удобным, и нет особой причины для использования Prolog).

Если вы хотите внедрить переводчика, вы, вероятно, будете использовать дискриминационный союз, который позволит вам переписать ваш пример с родителями следующим образом:

type Var = Var of string
type Expression = 
  | Binary of string * Expression * Expression
  | Fact of string * Expression list
  | Ref of Var
type Rule =
  | Rule of string * Var list * Expression

/// Simplified syntax for writing And
let And(a, b) = Binary("and", a, b)

let a, b, c = Var("A"), Var("B"), Var("C")
Rule("parents", [a; b; c], 
  And(Fact("mother", [Ref a; Ref c]), Fact("father", [Ref b; Ref c])))

Answer 2

Хорошее место для начала - взглянуть на реализацию алгоритма унификации в стиле Пролога на F #.Хорошие реализации псевдокода или LISP можно найти в ряде общих учебников по искусственному интеллекту или в Интернете.Вы можете работать от этого к возврату и синтаксису.Алгоритм унификации должен быть достаточно простым для реализации на многофункциональном языке, таком как F # (хотя, возможно, немного загадочным).

Answer 3

Когда-то я знал парня, который написал EDSL для Пролога на C ++ . Он продолжает делать то же самое для F #, но никогда не находит время. Кажется, он вспоминает, что основной алгоритм объединения и возврата пролога очень прост (возможно, упражнение в последней главе популярного текста Схемы?) И надеется, что кто-то его ударит, потому что он в отпуске. :)