在 F# 中模拟 Prolog 回溯

我目前正在参与一个项目，开发一个应用程序，该应用程序能够考虑一组节点和连接，并找到两个节点（在允许的连接上）之间的最短路径（一个常见且众所周知的问题）。好吧，我实际上不必从零开始构建应用程序，而只需要“转换”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

第一个列是事实名称，第二个列是值（这里是一个元组）。

如果我想搜索：“谁是 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

当我的解析器遇到规则时，它应该做什么？我想像我一样在表中创建某种记录，并且稍后能够进行查询以指定主题并获取其父母或指定父亲并获取所有儿子等等...... 你会怎么办？

There 是一个类似的问题 https://stackoverflow.com/questions/4299948/f-and-fuzzy-logic/4300010#4300010最近关于将类似 Prolog 的程序集成到 F# 中。

F# 没有任何内置支持执行基于回溯的搜索（如 Prolog）。您基本上有两个选择：

• 自己使用递归和编码回溯在 F# 中重新实现该算法。
• 实现 Prolog 解释器并使用一些可区分的联合来表示事实。

为了实现最短路径搜索，我可能会直接在 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])))