Emulating Prolog backtracking in F#

Question

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?

Answer 1

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

Answer 2

One good place to start is to look at implementing a Prolog-style unification algorithm in F#. Good pseudo-code or LISP implementations can be found in a number of general A.I. textbooks or on the web. You can work outwards from that to the backtracking and syntax. A unification algorithm should be fairly straightforward to implement in a feature-rich language like F# (though perhaps a bit arcane).

Answer 3

Once upon a time, I knew a guy who wrote an EDSL for Prolog in C++. He keeps meaning to do the same thing for F#, but never quite finds the time. He seems to recall the basic prolog unification & backtracking algorithm is very straightforward (an exercise in a late chapter of a popular Scheme text, perhaps?) and hopes someone will beat him to the punch, since he's on vacation. :)