PROLOG FOR XLISP
                               by
                M. Nilsson, P. Schachte, and R. Denney


XLPROLOG is a PROLOG written in XLISP.  It is currently pretty slow. The
problem is  mostly in  prolog/resetbindings.  Austin Code Works will pay
$25 to the first suggestion for  an extension  to Xlisp that  halves the  
speed of XLPROLOG.

This file is not meant to be an introduction to PROLOG.  PROGRAMMING  IN
PROLOG  by  Clocksin and Mellish is a good introductory text.  This file
is meant to be a reference aid to the features  available  in  XLPROLOG.

The .EXE file on the Xlisp distribution diskette has been build with the
DeSmet  C  compiler.  Due to  the  non-standard  way the DeSmet  runtime 
library  handles  setjmp and  longjmp, we have included a custom version
of setjmp and longjmp.

1  SYNTAX

As a LISP PROLOG the syntax is a bit different  from  "regular"  PROLOG.
The regular PROLOG clause:

   above(X,Z) :- on(X,Y),on(Y,Z).

is written like this in XLPROLOG:

   ((above ?x ?y)(on ?x ?y)(on ?y ?y))

Notice that variables in regular PROLOG begin  with  uppercase  letters,
while  variables  in XLPROLOG begin with a ?.  All XLPROLOG code must be
in lowercase.  In examples in  this  file,  system  output  will  be  in
uppercase to distinguish it from user input.

Facts in regular prolog look like:

   on(block1,block2).

and in XLPROLOG like:

   ((on block1 block2))

Notice that facts are like rules with no bodies.


2  RUNNING XLPROLOG

You will need files XLISP.EXE (version 1.4) and XLPROLOG.LSP.   XLPROLOG
is run by:

   C>run xlisp
   >(load "xlprolog.lsp")


3  MAKING ASSERTIONS

To assert a rule do:

   >(assert '((loves ?x ?y)(man ?x)(woman ?y)))

which says:  all mem love all women.

To assert facts do:

   >(assert '((man john)))
   >(assert '((woman mary)))

which says that john is a man and mary is a woman.

Facts and rules can be asserted interactively by doing:

   >(assert nil)
   ASSERT>((above ?x ?z)(on ?x ?y)(on ?y ?z))
   ASSERTED.
   ASSERT>((on block1 block2))
   ASSERTED.
   ASSERT>((on block2 block3))
   ASSERTED.
   ASSERT>ok
   COMPLETED.
   >

Uppercase is print from the system.  Notice that the expressions are NOT
quoted.  The user terminates the session with "ok" or "OK".  The user is
left at XLISP prompt level after COMPLETED is printed.

There is not currently a facility for  modifying  rules/facts  that  are
asserted,  but  maybe  this  will  help  until an editor is implemented.
Rules/facts are stored on the property list 'assertion of the  predicate
of the rule/fact.  For example:

   (get 'man 'assertions)

returns the list of rules/facts about "man".  To clear out  the  set  of
assertions about "man" one could do:

   (setf (get 'man 'assertions) nil)

"setf" is the XLISP function for  doing  property  list  actions,  among
other things.


4  PURSUING GOALS

Computation in PROLOG is done by pursuing goals.  The only goal pursuing
mechanism  currently implemented in XLPROLOG is the XLISP function "all"
which has the form:

   (all '<template> '( <goal> [ <goal> ...  ] ))

Expression in []s are optional.  The template  and  list  of  goals  are
quoted.  Template has a form like:

   '(block ?x is on top of block ?y)

The template describes the format that answers are to presented  in.   A
goal has a form like:

   (on ?x ?y)

which is either the head of some rule or the head of some fact.

The function "all" treats variables as being universally quantified  and
returns  a list of templates with all the possible instantiations of the
variables.  So, for example, if we gave the following goal to our  video
dating service XLPROLOG program:

   >(all '(match ?x with ?y) '((loves ?x ?y)))

we might expect to get back a list like:

   ((match john with mary)(match john with paula) ...  ))

This example could be interpreted as saying:  find all values of ?x  and
?y  such that ?x loves ?y, and present me with a list whose elements are
formatted like "match ?x with ?y".

As an example of pursuing multiple goals we might say:

   (all '?x '((man ?x)(single ?x)))

which would return a list of all single men.  If the template  has  only
one variable, it need not be in a enclosed in parens.  The template need
to include variables at all, for example:

   (all 't '((man bob)))

will return 't if bob is a man, and nil otherwise.


5  LOADING XLPROLOG RULES AND FACTS FROM A FILE

Assume you had a file, DATABASE.LSP, with contents:

   (assert '((corporation texas-instruments)))
   (assert '((headquarters texas-instruments dallas)))
   (assert '((city-in-texas dallas)))
   (assert '((texas-corporation ?x)(corporation ?x)
                            (headquarters ?x ?city)
                            (city-in-texas ?city)))

This set of facts and rule can be loaded from XLISP by doing:

   >(load "database")


6  BUILT-IN PREDICATES AND FUNCTIONS

6.1  The Cut Primitive

Refer to a PROLOG text for a thorough description of the Cut  primitive.
Syntactically, Cut appears in an XLPROLOG rule as a goal whose predicate
is !  with no arguments.  For example:

   ((loves ?x ?y)(man ?x)(!)(woman ?y)))

Very briefly, the effect of Cut is to freeze bindings  of  variables  as
they  are  at  the  time Cut is encountered.  This prevents backtracking
back past the Cut symbol.  In the above example, one value for ?x  would
be  found  for  (man  ?x), then all possible values for ?y in (woman ?y)
would be used with that one value.  In this example:

   ((loves ?x ?y)(man ?x)(woman ?y)(!)))

only one value for both ?x and ?y would be sought.

6.2  CALL

"call" is similar to LISP's EVAL.  It takes as its sole argument a  goal
or  a  variable  that  is  bound  to a goal, and pursues that goal.  For
example, if ?x where bound to:

   (loves ?man ?woman)

then we could pursue that goal by doing:

   (call ?x)

6.3  FAIL

The goal:

   (fail)

always fails.

6.4  NOT

"not" takes as its sole argument a goal, like:

   (not (man susie))

and succeeds only if the goal (man susie) fails.  As interesting example
of the use of "call", "!", and "fail", "not" can be defined like:

   ((not ?x)(call ?x)(!)(fail))
   ((not ?x))