[<<][staapl][>>][..]Tue Sep 8 09:47:46 CEST 2009

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

[Reply][About]

[<<][staapl][>>][..]