Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

PLL: Programming in Logic, in Lisp

Outdated egg!
PLL: Programming in Logic, in Lisp
Loading PLL
Variables
Calling the interpreter
1. Getting multiple answers
Variations of the interpreter
Bugs and missing features
A bibliography

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

As an 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))

Variations of the interpreter

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.

Prolog with any scheme function

This interpreter has no sandbox -- it will recognize and execute any Scheme function when it sees one.

Suppose we want to run this Prolog program, and use a Scheme function "print" in the goal:

a(5).
b(3).
b(5).

Goal:

a(X), b(Y), X=Y, print(X, " " Y).

In our Prolog, we have:

 (prolog+scheme '( ((a 5))
                   ((b 3))
                   ((b 5)))
                '( (a ?x) (b ?y) ((= ?x ?y)) ((print ?x " " ?y))))

5 5
((?y . 5) (?x . 5))

The first line is the effect of the print. The second line is Prolog's answer.

With local variables

 (prolog+local '( ((f ?x ?y)
                   (is ?y (* 2 ?x))
                   ((print 'OK: ?y))))
               '( (f 3 ?a) ))

OK:6
((?a . 6))

With assert and retract

This adds the meta-predicates assert and retract.

 (prolog+meta '(( (f ?x) (asserta (h 1)))
                ( (g ?x) (h ?x)))
              '((f ?w) (g ?z)))

The result will be ((?z . 1))

retract has the opposite effect. The Prolog program we show now is

f(2).
f(3).
g(1) :- retract(f(2)).

And the goal is

g(1), f(X).

In PPL's Schemish-Prolog, this is

 (define prolog-retract '( ((f 2))
                           ((f 3))
                           ((g 1) (retract ((f 2))))
                           ((g 1) (f 3))))

(prolog+meta prolog-retract '((g 1) (f ?x)))

(g 1) causes retract to be evaluated, so the goal succeeds with X=3, and not X=2:

((?x 3))

With cut

This adds the cut operator. For example, in Prolog we could write

a(X) :- b(X), !, c(X).
b(1).
b(2).
c(2).

The goal a(X) fails, because after the interpreter chooses b(1), it cannot backtrack, and c(1) is not true.

In our Prolog, we write:

 (prolog+cut '(( (a ?x) (b ?x) ! (c ?x) )
               ( (b 1) )
               ( (b 2) )
               ( (c 2) ))
             '((a ?x)))

#f

If we remove the cut, then this goal will succeed with X=2.

The cut can be used also in the goal.

Bugs and missing features

There is no way to save and load the database
There is no simple way to get all possible answers (substitutions) for a query in a list.
This manual is too short.

A bibliography

The following is a list of some books related to Prolog programming and implementations of Prolog.

William Clocksin, Chris Mellish. "Programming in Prolog". Springer, 2003. [ a very basic text ]
Michael Covington, Donald Nute, André Vellino "Prolog Programming in Depth". Scott, Foresman and Company, 1988. [ quick introduction to Prolog, followed by some advanced programming techniques and application ]
Leon Sterling, Ehud Shapiro. "The Art of Prolog". MIT Press, 1994. [ solid introduction to Prolog, including the execution model -- strongly recommended for those who want to understand the internals of the interpreter ]
Richard O'Keefe. "The Craft of Prolog". MIT Press, 1990. [ advanced programming techniques ]
Harold Abelson, Gerald Jay Sussman "Structure and Interpretation of Computer Programs". Addison-Wesley, 1996. [ explains and implements in Scheme the AMB operator and a small Prolog interpreter ]
Peter Norvig. "Paradigms of Artificial Intelligence Programming". Morgan Kaufmann, 1992. [ part of the book explains unification and contains another Prolog implementation, in Common Lisp ]
Jacques Chazarain, "Programmer Avec Scheme". International Thomson Publishing France, 1996 (in French). [ a very good book on Scheme. chapters 15-19 focus on Prolog ]
J. A. Campbell. "Implementations of PROLOG". Ellis Horwood, 1984. [ a study of implementation techniques. quite advanced. ]