在 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# 中，我创建

事实母：AB; 事实母亲：CD；

我的哈希表是：

mother ->一个 |乙 妈妈-> 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

最近有关于将类似 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])))

Answer 2

一个好的起点是研究在 F# 中实现 Prolog 风格的统一算法。好的伪代码或 LISP 实现可以在许多通用 AI 教科书或网络上找到。您可以从这里向外延伸到回溯和语法。统一算法应该相当简单地可以用功能丰富的语言（如 F#）来实现（尽管可能有点神秘）。

Answer 3

从前，我认识一个人，他用 C++ 编写了 EDSL for Prolog 。他一直想为 F# 做同样的事情，但一直没有时间。他似乎还记得基本的序言统一&回溯算法非常简单（也许是流行方案文本最后一章中的练习？）并且希望有人能抢先一步，因为他正在度假。 :)