Tue Sep 8 09:47:46 CEST 2009

Prolog and Pattern Matching

Looks like I missed some important point about Prolog.  In my head
it's simplified to `amb' + constraints in the form of horn clauses.
But then what?  As a guide, let's take [1] and [2].

In [2], chapter 22 talks about `amb' (or `choose').  Relatively
straightforward.  So what is `cut', explained in 22.5?  Essentially,
eliminating part of a search tree.  This is straightforward in
depth-first search, and requires marking of the resume stack.  Then
22.6 talsk about breath-first search, implemented by replacing the
resume stack with a queue.

Chapter 24 talks about prolog as ``rules as a means to construct a
tree of implications, which can then be searched using
non-determinism.''  Or prolog as a combination of pattern matching,
nondetermism and rules.  A rule has the form

  if <body> then <head>.

The basic idea is that if the body matches a fact, its head can be
added to the collection of facts.

When asked for a fact, we can recursively sift through the facts and
heads of rules, essentially picking out rules and finding evidence.
The search ends when there is evidence found, or when all rules and
facts are exhausted.

So, what about binding?  Find all occurences of variables satisfying a
certain property.  It looks like what is necessary to implement this
in Scheme is to map Scheme's binding mechanism to the rule binding.
In the following rule,

   (if (and (tree x) (summer)) then (green x))

which is the binding site, and which is the reference site for `x' ?

It's not obvious, so maybe the answer is it depends on whether this is
interpreted as a constructor or a destructor, or both.  Unification?
Indeed. [1][3].

One thing that confuses me is the 2 directions of information flow: to
see if a parameterized fact is true, one needs to run the rules
backwards, but for every value found, the value propagation runs the
other way.  So it looks like control flow is going in one direction,
while data flow moves the opposite way!

Let's try to organise the control flow first, and see how the data
flow can be incorporated in that solution.  Given a set of rules,
construct functions that are indexed by proposition.

  ;; rule <body> <head>
  (rule (and (tree x) (summer)) (green x))
  (rule #t (summer))
  (rule #t (tree pine))
  (rule #t (green algae))

Suppose `(green x)' nondeterministically binds x.  How does this look
as in expression form?

I'm stuck at expressing binding recursively.  Let's try to make it
more difficult first

  (rule (and (tree x) (brown y)) (browntree x y))


[1] http://mitpress.mit.edu/sicp/full-text/sicp/book/node92.html
[2] http://www.paulgraham.com/onlisptext.html
[3] http://en.wikipedia.org/wiki/Unification