在F#中模拟Prolog回溯 [英] Emulating Prolog backtracking in F#
问题描述
我目前正在参与一个项目，该项目能够开发能够考虑一组节点和连接并找到两个节点(在允许的连接上)之间的最短路径(一个常见且众所周知的问题)的应用程序.好吧，我实际上不必从零开始构建应用程序，而只需要在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的母亲"->我寻找母亲，寻找价值，我找到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
当我的解析器遇到规则时，该怎么办?我想像以前一样在表中创建某种记录，以后可以进行查询，以指定主题并获得其父母或指定父亲并获得所有儿子，依此类推... 你会怎么做?
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])))
I am currently involved in a project to develop an application able to consider a set of nodes and connections and find the shortest path (a common and well-known issue) between two nodes (on allowed connections). Well I don't really have to build an application from zero, but just need to "convert" a Prolog pre-existing application in f#. I thought I bit about it and finally asked myself one question: "Instead of developing a special purpose solution and implementing new algorithms specifically binded to this problem, can I create a program able to accept facts like Prolog and use them to make queries or something similar?".
By doing so I would create a set of facts (like in Prolog) and then use them to make queries. So, considering now this new issue (converting Prolog in F#) I need to find a way to create facts like these:
myfact1(el1, el2,..., eln).
myfact2(el1, el2,..., elm).
...
myfactk(el1, el2,..., elp).
to something in a similar syntax like:
fact factname1: el1 el2 ... eln;
fact factname2: el1 el2 ... elm;
...
fact factnamek: el1 el2 ... elp;
I know that F# is very well for parsing, so I think that parsing this would probably not be a problem.
OK! Now that it is parsed, I should define an algorithm that, while parsing the code, stores all facts in some sort of knowledge (nothing more than a table). In order to make then all needed associations.
For example a solution might be a hashtable that considers all associations
factname1 -> el1
factname1 -> el2
...
factname1 -> eln
factname2 -> el1
factnale2 -> el2
...
factname2 -> elm
factname3 -> el1
...
...
factnamek -> el1
factnamek -> el2
...
factnamek -> elp
By doing so I will always be able to solve queries. For example consider the following Prolog fact
mother(A, B) % This means that A is mother of B
mother(C, D)
In F# I create
fact mother: A B; fact mother: C D;
My hashtable is:
mother -> A | B mother -> C | D
The first col is the fact name and the second is the value (here a tuple).
If I want to search: "who is the mother of B" --> I search for mother, and look for value, I find B, I look in the tuple and discover A!
Well it seems working. But facts are easy to implement. What about rules? For example rule parents:
parents(A, B, C) :- mother(A, C), father (B, C)
In F# using my syntax? Well I came up with this idea:
rule parents: A, B, C => mother A C and father B C
When my parser encounters a rule, what should it do? I would like to create some sort of record in a table like I did and be able, later, to make queries in order to specify a subject and get its parents or specify a father and get all sons and so on... What would you do?
There was a similar question about integrating Prolog-like programs into F# recently.
F# doesn't have any built-in support for performing search based on backtracking (like Prolog). You have essentially two options:
- Re-implement the algorithm in F# using recursion and encoding backtracking yourself.
- Implementing a Prolog interpreter and representing facts using some discriminated union.
To implement shortest path search, I would probably just implement the algorithm directly in F# (using functional programming will be quite convenient and there is no particular reason for using Prolog).
If you wanted to implement an interpreter, you'd probably use a discriminated union that allows you to rewrite your example with parents like this:
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])))
这篇关于在F#中模拟Prolog回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
