You are looking at historical revision 33201 of this page. It may differ significantly from its current revision.
PLL is a set of implementations of Prolog in Scheme. It is not supposed to be efficient, but rather as a simple way to teach the fundamentals of Logic Programming and the internal working of a Prolog interpreter (conceptually only -- a real implementation would be radically different). This interpreter is based on a simple implementation of the AMB operator.
PLL is very small (less than 500 lines of code, including different versions of the interpreter).
Each variant is built on top of the other.
- Pure prolog: no variables, no assertions, only plain Prolog and SLD-resolution.
- Prolog w/built-ins: with an extensible set of built-in predicates. Only the built-ins within a list are allowed.
- Prolog w/Scheme functions: call any Scheme function from Prolog.
- Prolog w/local vars: this version has support for "IS" and local Prolog variables.
- Prolog w/meta-predicates: this version has support for "assert" and "retract".
- Prolog w/cut: this version supports cuts.
One last implementation is missing, that would allow for writing and reading the database (so it would be possible to store and retrieve programs). This is very simple to implement and planned for the near future.
Loading PLL
Just
(use (pll))
VARIABLES
Traditionally, Prolog systems treat symbols beginning with uppercase letters as variables: X, Y, Variable are variables, while x, y, constant are constants.
Lisp-based Prologs usually do this differently: the variables are the symbols that begin with a question mark: ?x, ?y, ?variable, etc. We do the same in this implementation.
CALLING THE INTERPRETER
Our Prolog use the following syntax:
(pure-prolog PROGRAM GOAL)
The program is a list of assertions. The program
p(x).
p(Z) :- q, r(Z).
is written as a list of assertions. Each assertion is a list where the head represents the left side (the consequent), and the tail is a list of the goals to be met in order to prove the consequent. For example,
'(( (p x) ))
( (p ?z) q (r ?z)))
The GOAL is a list of goals:
p(1), q(X).
is written as
'((p 1) (q ?x))
EXAMPLE: Suppose we want to enter the following program:
f(0). f(Z) :- g(Z). h(3). h(4). p(Z,Y,S) :- f(Z),g(Y),h(S) g(10).
And ask the question
p(10,D,A), q(A).
We can do this:
(define facts '(( (f 0) )
( (f ?z) (g ?z) )
( (h 3) )
( (h 4) )
( (q 4) )
( (p ?z ?y ?s) (f ?z) (g ?y) (h ?s) )
( (g 10) )))
(define goals '((p 10 ?d ?a) (q ?a)))
And call
(pure-prolog facts goals)
Or, directly enter the facts and goal (as we do in the examples that are included in prolog-examples.scm):
(pure-prolog '(( (f 0) )
( (f ?z) (g ?z))
( (h 3) )
( (h 4) )
( (q 4) )
( (p ?z ?y ?s) (f ?z) (g ?y) (h ?s))
( (g 10) ))
'((p 10 ?d ?a) (q ?a)))
The result will be a list of substitutions that satisfy the goal:
((?a . 4) (?d . 10))
GETTING MULTIPLE ANSWERS
This can be done with the `amb+` operator.
(pure-prolog '(((f 1))
((f 2)))
'((f ?x)))
((?x 1))
If we call `(amb+)`, then we get another solution:
((?x 2))
DIFFERENT INTERPRETERS
The different interpreters included are:
- pure prolog (prolog only) - prolog+built-ins (with built-in predicates with side-effect) - prolog+scheme (with an FFI to Scheme, but NO built-ins) - prolog+local (with "IS" and local vars; on top of prolog+scheme) - prolog+meta (with assert and retract; on top of prolog+local) - prolog+cut (with cut (!); on top of prolog+meta)
So the features are added one on top of the other, except for the built-ins feature, which is not included in the later interpreters.
In the source code, there is one initial implementation (pure-prolog) with short comments explaining how it works. Each interpreter after that one has comments only on the modified parts.
Pure Prolog
This is the most basic of all. You can only statet facts as we described above, nothing else. Call it as
(pure-prolog facts goals)
For example, we define a graph by declaring its edges, then define a reach/2 predicate.
edge(a,b). edge(a,c). edge(c,b). edge(c,d). edge(d,e). reach(A,B) :- edge(A,B). reach(A,B) :- edge(A,X), reach(X,B).
We could then as "reach(b,e)" and find that b doesn't reach e.
In PLL:
(define graph '( ((edge a b))
((edge a c))
((edge c b))
((edge c d))
((edge d e))
((reach ?a ?b) (edge ?a ?b))
((reach ?a ?b) (edge ?a ?x)
(reach ?x ?b))))
(pure-prolog graph '( (reach b e) )) #f
- Prolog with built-in "procedures"
This adds some predicates with side-effects.
Define a list of Scheme functions that you want to be accessible from Prolog:
(define write-it
(lambda (args sub)
(cond ((not (null? args))
(if (matching-symbol? (car args))
(display (assoc (car args) sub))
(display (car args)))
(write-it (cdr args) sub))
(else #t))))
Here "sub" is the current substitution, where Prolog will find the values of variables.
(define built-ins `((write . ,write-it)))
So (write a b c ...) will be translated to
(write-it (a b c ...) sub)
Then, whenever one of these predicates show up in the goal, Prolog will execute them:
father(john,johnny). father(old-john,john). grandpa(A,B) :- father(A,X), father(X,B).
Our goal is
grandpa(old-john,Who), write("grandson is: "), write(Who).
In our Prolog, this is expressed as follows:
(prolog+built-ins '( ((father john johnny))
((father old-john john))
((grandpa ?a ?b) (father ?a ?x) (father ?x ?b)) )
'( (grandpa old-john ?who) (write "Grandson is: " ?who) ))
Grandson is: johnny (((?who . johnny)) ())
The first line was the effect of having a (write ...) in the goal. The second is the answer.