parsing - 在F#中模拟Prolog回溯

Question

我目前正参与一个开发应用程序的项目，该应用程序可以考虑一组节点和连接，并找到两个节点(在允许的连接上)之间的最短路径(一个常见且众所周知的问题)。好吧，我实际上不必从零开始构建应用程序，而只需要在f＃中“转换” Prolog预先存在的应用程序即可。
我以为自己对此有些怀疑，最后问自己一个问题:“我可以创建一个程序来接受Prolog之类的事实，并使用它们进行查询或类似的事情，而不是开发特殊目的的解决方案并实现专门针对该问题的新算法。相似的？”。

这样，我将创建一组事实(例如在Prolog中)，然后使用它们进行查询。
因此，现在考虑这个新问题(在F#中转换Prolog)，我需要找到一种创建如下事实的方法:

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

这样，我将始终能够解决查询。
例如，考虑以下Prolog事实

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

在F#中，我创建

事实母亲:A B；
事实母亲:C D；

我的哈希表是:

妈妈-> A |乙
妈妈-> C | d

第一个col为事实名称，第二个为值(此处为元组)。

如果要搜索:“谁是B的母亲”->我搜索母亲，寻找值(value)，我找到B，我在元组中找到A!

好吧，看来可行。
但是事实很容易实现。规则呢？
例如规则 parent :

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

在F#中使用我的语法？好吧，我想到了这个主意:

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

当我的解析器遇到规则时，该怎么办？我想像以前一样在表中创建某种记录，以后可以进行查询，以指定主题并获得其 parent 或指定父亲并获得所有儿子，依此类推...
你会怎么做？

Answer 1

最近有was a similar question关于将类似Prolog的程序集成到F#中。

F#不支持基于回溯执行搜索的任何内置支持(例如Prolog)。您实际上有两个选择:

使用递归和对自己进行回溯编码来在F#中重新实现算法。

实现Prolog解释器并使用某些已区分的并集来表示事实。

为了实现最短路径搜索，我可能只是直接在F#中实现该算法(使用函数式编程将非常方便，并且没有使用Prolog的特殊原因)。

如果您想实现解释器，则可能会使用一个已区分的联合，该联合允许您像这样的 parent 来重写您的示例:

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])))