% Trademark.

\def\DECsystemX{DECsystem-10$^{tm}$}

% Customize xitem.

\def\mykindex{\smallbreak \parsearg\mykindexx}
\def\mykindexx #1{\dosubind {kw}{#1}{for {\bf \lastfunction}}}

% Handy macros for DEC-10 Prolog built-ins.

\def\Bgg{$\gg$}
\def\Bll{$\ll$}

% \defpredicate.

\def\defpredicateheader #1#2{\doind {pr}{#1}% Make entry in predicate index
\gdef\lastfunction{#1}%
\dosetq {#1-pred}{page}%
\begingroup\defname {#1}{Predicate}%
\defunargs {#2}\endgroup %
}

\def\defpredicate{%
\defparsebody\Edefpredicate\defpredicatex\defpredicateheader}
\def\defpredicatex #1 {\errmessage{@defpredicatex in invalid context}}

% \defineoption.

\def\defineoptionheader #1#2{\dosubind {kw}{#1}{for {\bf define-predicate}}
\gdef\lastfunction{#1}%
\dosetq {#1-defpredopt}{page}%
\begingroup\defname {#1}{Define-Predicate Option}%
\defunargs {#2}\endgroup %
}

\def\defineoption{%
\defparsebody\Edefineoption\defineoptionx\defineoptionheader}
\def\defineoptionx #1 {\errmessage{@defineoptionx in invalid context}}

% \deftoplevel.

\def\windex {\woindex}
\def\deftoplevelheader #1#2{\doind {wo}{#1}% Make entry in world index
\gdef\lastfunction{#1}%
\dosetq {#1-toplevel}{page}%
\begingroup\defname {#1}{Top Level}%
\defunargs {#2}\endgroup %
}

\def\deftoplevel{%
\defparsebody\Edeftoplevel\deftoplevelx\deftoplevelheader}
\def\deftoplevelx #1 {\errmessage{@deftoplevelx in invalid context}}

\input patbo

@c Customize the fonts to 12pt for readability.

@tex
\global\font\twelverm=amr10 scaled \magstep 1 % 12pt
\global\font\twelveit=amti10 scaled \magstep 1 % 12pt
\global\font\twelvesl=amsl10 scaled \magstep 1 % 12pt
\global\font\twelvett=amtt10 scaled \magstep 1 % 12pt
\global\def\textfonts{\let\rm=\twelverm
		      \let\it=\twelveit
		      \let\sl=\twelvesl
		      \let\sc=\tensc		       % we don't have 12pt
		      \let\vf=\sl
		      \let\defbf=\twelvebf	       % in BOTEX
		      \let\bf=\defbf
		      \let\deftt=\twelvett
		      \let\tt=\deftt
		      \let\defsf=\twelvesf	       % in BOTEX
		      \let\sf=\defsf
		      \DEFsf
		      \baselineskip 14.4pt}

% UPMAIL Front page.
\textfonts
\rm

\line{\hfill\bf Upmail Technical Report no. 24}

\vfill

\centerline{\chaprm LM-Prolog User Manual}
\vskip 2mm
\centerline{\bf Version 9.1: \datestamp}

\vfill

\centerline{\it Mats Carlsson and Kenneth M. Kahn}

\vfill

\centerline{UPMAIL}
\centerline{Uppsala Programming Methodology and Artificial Intelligence Laboratory}
\centerline{Department of Computing Science, Uppsala University}
\centerline{P.O. Box 2059}
\centerline{S-750 02 Uppsala Sweden}
\centerline{Domestic (018) 155400}
\centerline{International +46 18 111925}
\centerline{Telex 76024 univups s}

\vfill

The authors wish to thank the National Swedish Board for
Technical Development (STU) and Uppsala Programming Methodology and Artificial
Intelligence Laboratory (UPMAIL), Uppsala University for their support during 
the building of prototypes of LM-Prolog.
\eject

@end tex

@textfonts 
@rm

@defindex cp
@defindex fn
@defindex kw
@defindex wo
@defindex pr

@settitle LM-Prolog User Manual
@setx titlecomment Version 9.1: @datestamp
@setx lmipart 24-???????-????
@hsize=6.5in
@parindent=0.4in
@itemindent=0.4in
@lispnarrowing=0.4in
@titlepage
@copyrightpage

This manual was written by Mats Carlsson and Kenneth M. Kahn,
at Uppsala Programming Methodology and Artificial Intelligence Laboratory,
Department of Computing Science, Uppsala University.

The authors wish to thank the National Swedish Board for
Technical Development (STU) and Uppsala Programming Methodology and Artificial
Intelligence Laboratory (UPMAIL), Uppsala University for their support during 
the building of prototypes of LM-Prolog.

\DECsystemX is a trademark of Digital Equipment Corp.
@end copyrightpage
@headings on

@chapter Introduction to the System
LM-Prolog is an implementation of Prolog [Kowalski 1974]
on Lisp Machines [Greenblatt 1974].
Prolog is a programming language based upon a subset of first-order logic that
can be computed with effectively.
The language is used primarily for symbolic computation and database
applications.
It was originally implemented at the University of Marseille [Roussel 1975] 
and the most
widely used implementation on DEC 10/20 was developed at the University of
Edinburgh [Warren 1977].

MIT Lisp Machines and their descendants provide a very rich and powerful
environment for developing and running Lisp programs.
They are personal work stations with large address spaces, large amounts of
memory and disk storage, high resolution graphics, and
high-speed network interfaces.
The amount and quality of the software engineering behind the machines greatly
exceeds that of any Prolog implementation.
The idea behind LM-Prolog is to provide the environment and features of the
Lisp Machine to Prolog users.

The @b[pure] part of Prolog is a Horn-clause theorem prover.
A Horn clause is a universally quantified logical implication.
The consequent part of a Horn clause is constrained to be an atomic formula; 
the antecedent is a conjunction of atomic formulas. 
Pure Prolog is
not sufficient for a practical programming language however and several
primitive predicates need to be defined.
LM-Prolog differs from other Prolog implementations in providing a much richer
and more complete set of primitive predicates.
These @b[evaluable predicates] perform i/o, efficient arithmetic, database
updating, control, and interfacing to the underlying Lisp system.
@cindex evaluable predicate
@cindex predicate, evaluable

LM-Prolog consists of an interpreter and a compiler to Lisp.
Both are written in ZetaLisp.
The compiled code and the interpreter
communicate with each other automatically.
LM-Prolog features arbitrary arity of predicates,
optional occur check,
handling of cyclic structures, multiple databases, user-controllable
database indexing, efficient conditionals, lazy collections, 
error signalling and recovery, user extensibility,
the ability to re-enter Prolog recursively,
turtle graphics, several debugging aids, and various interfaces to Lisp
and the Zwei editor.
The ZetaLisp data types such as arbitrarily long integers, rational
and complex numbers, strings, i/o streams, flavors, etc. 
are all easily accessible from LM-Prolog.
LM-Prolog also consists of experimental
facilities such as constraints
and parallel processing via eager bags and sets.

Compiled LM-Prolog programs are typically much faster. Compiler optimizations
include detection of determinacy,  micro-coded unification and
runtime support, tail recursion elimination,
optional open compilation, and a fast interface to Lisp.
For systems without micro-code support unification is open compiled.
Any predicate can be compiled.

The following chapter is a brief introduction to Horn-clause programming
and contains many examples.
Chapter 3 describes predicates for list processing,
predicates for calling Lisp and Lisp functions for calling LM-Prolog,
predicates of general utility, arithmetical predicates, 
input-output predicates, and control primitives.
Chapter 4 is about how one adds and compiles definitions, while Chapter 5
describes predicates for retrieving and changing definitions.
Chapter 6 describes how users can customize the system.
Chapter 7 deals with the debugging and tracing facilities.
Chapter 8 describes various experimental extensions to LM-Prolog that are
subject to further development.
Various ways of interacting with the top-level of LM-Prolog are presented in
Chapter 9.
Chapter 10 describes a compatibility package with Dec 10/20 Prolog and its
near copies.
Chapter 11 discusses briefly how a sophisticated user can extend or modify the
system in Lisp.
Chapter 12 discusses some performance considerations.
Appendix A gives examples of translations from Dec 10/20 Prolog to LM-Prolog.
Appendix B discusses the output of the compiler.
Appendix C summarizes the terminal keys with a special meaning to LM-Prolog.
Appendix D contains references.

@chapter Introduction to Pure Prolog
@section Syntax, Terminology, and Packages
A pure Prolog program is a collection of statements in a subset of 
first-order logic.
The programs are executed by a theorem prover which performs a restricted
form of resolution, see [Robinson 1965] and [Lloyd 1984].
One can compute very efficiently with the subset of logic restricted to 
@b[Horn clauses].
A @b[pure] LM-Prolog predicate is defined by a list of Horn clauses.
Each clause is a list of @b[predications].
A predication is the @b[cons] of a @b[predicator] and arguments.
A predicator can be any symbol.
Arguments can be any term (i.e. either an atom, a variable, or a cons of
two terms).
@cindex Horn clause
@cindex predication
@cindex predicator

Logically, a clause is an implication where the first element is the consequent
and the antecedent is the conjunction of the rest of the elements.
If the rest is empty, the clause simply means that its first element is true.
All variables are universally quantified so they need not be explicitly
quantified.
They are distinguished from symbolic constants by beginning with a 
single `?'.
(Symbolic constants beginning with a `?' are entered and printed with an
extra `?' in front.)
For example, the logical formula
@tex
$$\forall gc \forall gp \forall p:\ \mathop{\rm grandparent}(gp,gc) \leftarrow \mathop{\rm parent}(gp,p) \land \mathop{\rm parent}(p, gc)$$
@end tex
is written in LM-Prolog as @*
@sp 1
@center @l[((grandparent ?gp ?gc) (parent ?gp ?p) (parent ?p ?gc))]
@sp 1

@cindex argument list
Technically speaking, all LM-Prolog predicates and predications
have exactly one argument, the @b[argument list]. 
This interpretation is
needed to account for LM-Prolog's variable arity, discussed below.
The above LM-Prolog clause really represents the logical formula
@tex
$$\forall gc \forall gp \forall p:\ \mathop{\rm grandparent}(gp.gc.\mathop{\rm nil}) \leftarrow \mathop{\rm parent}(gp.p.\mathop{\rm nil}) \land \mathop{\rm parent}(p.gc.\mathop{\rm nil})$$
@end tex

For all practical purposes, however, LM-Prolog predicates should be
viewed as taking a list of arguments.

@cindex anonymous variable
@cindex variable, anonymous
@cindex occurrence
A single @l[?] is LM-Prolog's syntax for an @b[anonymous variable].  
An anonymous variable is a variable that is defined to @b[occur only once]
in a given clause.
For example, @l[((foo ? ?X ?))] should be interpreted as
@tex
$$\forall u \forall x \forall u^{\prime}: \mathop{\rm foo}(u,x,u^{\prime})$$
@end tex

Anonymous variables differ from other variables only in that their bindings
are not displayed in answer to a top-level query.
Additionally the system produces warnings if a non-anonymous
variable occurs only once in a clause.
(This catches many typing mistakes of variable names.
Variable names beginning with @l[?ignore] may occur once without receiving a
warning.)

The primary means of defining predicates is using @l[define-predicate]
which collects together clauses pertaining to the same @b[predicator] and 
provides a place to select options as described in detail in @ref[defpred].
@cindex predicator

The syntax of LM-Prolog follows Lisp closely in spirit and in details.
This makes it possible to use all the system software of the Lisp Machine,
such as the Zwei editor, without extra effort.
As with Lisp, the syntax of the language @b[per se] is kept simple and other
notations are developed separately as front-ends.

@cindex packages
LM-Prolog defines three packages: @l[pglobal:], @l[prolog:],
and @l[puser:], where the two latter are subpackages of @l[pglobal:].
The main parts of LM-Prolog are in the @l[prolog:] package.
Programs written @b[in] LM-Prolog should normally be in the @l[puser:]
package.
Those builtin predicates and functions that are documented herein without
a package prefix are available from the @l[puser:] package.

The part of LM-Prolog corresponding to Horn clauses is very powerful.
Several examples of its use follow.

@section Examples
@subsection Grandparent Example
The following is the part of a family tree program in LM-Prolog which defines
@l[grandparent], @l[parent], @l[father], and @l[mother].
The first two definitions are complete; the next two may be extended as more
father- or mother-child relationships are encountered.

@lisp
(define-predicate grandparent
  ((grandparent ?grandparent ?grandchild) @ii[;if]
   (parent ?parent ?grandchild) @ii[;and]
   (parent ?grandparent ?parent)))

(define-predicate parent
  ((parent ?parent ?child) @ii[;if]
   (father ?parent ?child)) 
  ((parent ?parent ?child) @ii[;if]
   (mother ?parent ?child)))

(define-predicate father (:options (:type :dynamic))
  ((father Gustaf-Adolf Carl-Gustaf))
  ((father Carl-Gustaf Victoria))
  ((father Carl-Gustaf Carl-Philip))
  ((father Carl-Gustaf Madeleine)))

(define-predicate mother (:options (:type :dynamic))
  ((mother Sibylla Carl-Gustaf))
  ((mother Silvia Victoria))
  ((mother Silvia Carl-Philip))
  ((mother Silvia Madeleine))
@end lisp

@cindex packages
@l[(:options (:type :dynamic))] informs LM-Prolog that programs are
allowed to update the @l[father] and @l[mother] predicates.
The `:' is to indicate that the symbols belong to the Lisp Machine's 
@b[keyword] package of symbols.
By default, predicates are not changeable.
@l[Define-predicate] is both a Lisp macro
and a LM-Prolog predicate so it can be
entered at top-level to either system or included in Lisp files.

The predicate @l[grandparent] can be used as illustrated in the following
sample dialog with the system.
@setq king section-page

@format
@tt
(grandparent Sibylla Carl-Philip) @ii[;Is Sibylla a grandparent of Carl-Philip?]
OK @ii[;The system replies in the affirmative]
(grandparent Gustaf-Adolf ?who) @ii[;Who is a grandchild of Gustaf-Adolf?]
OK @ii[;one answer is Victoria]
?WHO = VICTORIA
OK @ii[;more answers are obtained by hitting @handdown.]
?WHO = CARL-PHILIP
(grandparent ?who Madeleine) @ii[;Who is a grandparent of Madeleine?]
OK
?WHO = GUSTAF-ADOLF
(grandparent ?gp ?gc) @ii[;Who is a grandparent of whom?]
OK
?GP = GUSTAF-ADOLF
?GC = VICTORIA
...
@end format


More details about the top-level of LM-Prolog can be found in 
@ref[toplevel].

@subsection List Processing Example
A classic Prolog program is one defining the relationship of two lists which
concatenate to a third. In LM-Prolog, 
it is generalized to the concatenation of any number of lists.
@l[Append] holds when its first argument is the concatenation of the 
rest of its arguments. It could be defined as follows.

@setq append section-page
@lisp
(define-predicate append
  ((append ()))) @ii[;zero lists concatenate to the empty list]
  ((append ?total () . ?back) @ii[;an empty list can be simplified away]
   (append ?total . ?back))
  ((append (?first . ?rest-of-total) (?first . ?rest-of-front) . ?back)
   @ii[;a non-empty list contributes one element to the concatenation]
   (append ?rest-of-total ?rest-of-front . ?back)))
@end lisp

@cindex arity, arbitrary
@cindex arbitrary arity
In order to fully exploit the @b[arbitrary arity] of LM-Prolog predicates,
the convention is that a function is represented by a predicate whose
first argument is the value of the function application and whose
other arguments correspond to the arguments of the function.
This is unfortunately the opposite of the
convention in other Prolog implementations.
LM-Prolog's convention facilitates using predicates
representing functions of an arbitrary number of arguments.
Essentially any associative function (e.g. plus, times, intersection,
union, concatenation) is well-suited for having an arbitrary number of
arguments.
This provides the same power as APL's reduction operator `/'
[Iverson 1962]
by enabling one to reduce a list by ``applying'' a predicate to it.
The call @l[(append ?list . ?list-of-lists)], for
example, will bind @l[?list] to a list of the elements of each of
the @l[?list-of-lists].
The only restriction on variable
arity is that compiled calls (predications) may not end with a
``dotted pair'' that ends with an unbound variable.

Arbitrary arity is not only very convenient for the user but it often
decreases the need to be concerned with run-time efficiency.
Consider the situation where one wants to concatenate three lists.
An experienced Prolog programmer, especially one thinking ``declaratively'',
might code this as 
@l[(and (append ?ab ?a ?b) (append ?abc ?ab ?c))]
while the logically equivalent coding
@l[(and (append ?bc ?b ?c) (append ?abc ?a ?bc))]
performs proportional to the length of @l[?a] fewer operations.
@l[Append] is declaratively associative, 
but it is not associative with respect to computational complexity.
The cognitive burden of thinking about such issues is 
alleviated by building the
``correct'' coding into the implementation of an arbitrary arity @l[append].

What is fascinating about Prolog, is that a simple definition of concatenation
as given above can be used in so many different ways.
For efficiency or clarity some of the uses that follow should be 
specialized and named [Kahn and Carlsson 1984].

@description
@item @l[(append ?list ?x ?difference)]
subtracts the list @l[?x] from the beginning of @l[?list] to obtain 
@l[?difference].

@item @l[(append ?list ?difference ?x)]
subtracts the list @l[?x] from the end of @l[?list] to obtain @l[?difference].

@item @l[(append ?list ?x ?y)]
generates pairs of lists @l[?x] @l[?y] which append to @l[?list].

@item @l[(append ?list ? (?term) ?)]
decides whether @l[?term] is a member of @l[?list].

@item @l[(append ?list ? (?x) ?)]
generates elements of @l[?list] called @l[?x].

@item @l[(append ?list ? (?x))]
finds @l[?x] which is the last element of @l[?list].

@item @l[(append ?list ? (?term-1 ?term-2) ?)]
asks if @l[?term-1] and @l[?term-2] are successive elements of @l[?list].

@item @l[(append ?a-list ? ((?key ?value)) ?)]
asks if @l[?value] is associated with @l[?key] in @l[?a-list].

@item @l[(append ?list ? ?sub ?)]
asks if @l[?sub] is a sub-list of @l[?list].

@item @l[(append ?list ? (?term) ? (?term) ?)]
asks if @l[?term] occurs twice in @l[?list].

@item @l[(and (append ?list ?before (?term) ?after) (append ?remaining ?before ?after))]
removes @l[?term] from @l[?list] to obtain @l[?remaining].

@item @l[(append ?list ?a ?b)]
where @l[?list], @l[?a], and @l[?b] are
bound will answer the question of whether @l[?a] and @l[?b] append to 
@l[?list].
It will answer the question efficiently without any consing or searching.

And so on.
@end description

@subsection Peano Arithmetic Examples
@setq peano section-page

Another classic example of logic programming is the Peano definition of
arithmetic in terms of successor.
In the following example, the constructor @l[1+] represents the successor
function.
The predicate @l[plus] is a relation which holds when its first argument is
the sum of its other arguments.
The predicate @l[times] is a relation which holds when its first argument is
the product of its other arguments.
The predicate @l[factorial] is a relation which holds when its 
first argument is the factorial of its second.

@lisp
(define-predicate plus
  @ii[;Zero is the sum of zero numbers]
  ((plus 0)) 
  @ii[;A zero term is simplified away]
  ((plus ?sum 0 . ?addends) 
   (plus ?sum . ?addends)) 
  @ii[;A nonzero term contributes to the sum]
  ((plus (1+ ?sum) (1+ ?x) . ?addends)
   (plus ?sum ?x . ?addends)))
@end lisp

@lisp
(define-predicate times
  @ii[;One is the product of zero numbers]
  ((times (1+ 0))) 
  @ii[;A zero factor makes a zero product]
  ((times 0 0 . ?)) 
  @ii[;(1+x)*y is (x*y)+y]
  ((times ?product (1+ ?x-1) . ?multiplicands) 
   (times ?product-m . ?multiplicands)
   (times ?product-y ?x-1 ?product-m)
   (plus ?product ?product-y ?product-m)))
@end lisp

@lisp
(define-predicate factorial
  @ii[;1 is the factorial of 0]
  ((factorial (1+ 0) 0)) 
  @ii[;the factorial of n is n times the factorial of n-1]
  ((factorial ?factorial (1+ ?n-1))    
   (factorial ?factorial-of-n-1 ?n-1) 
   (times ?factorial (1+ ?n-1) ?factorial-of-n-1)))
@end lisp

@l[Factorial] can be used to compute factorials, e.g. 
@l[(factorial ?f (1+ (1+ (1+ 0))))], compute inverse factorials
(if they exist, otherwise it will not terminate), e.g.
@l[(factorial (1+ (1+ (1+ (1+ (1+ (1+ 0)))))) ?n)],
or generate pairs of integers
such that one is the factorial of the other, @l[(factorial ?f ?n)]. 
It can even answer the question ``are there any factorials greater than four'',
i.e. @l[(factorial (1+ (1+ (1+ (1+ ?x)))) ?n)].

@subsection Database Query Example
@setq dbquery section-page
[Warren 1977] contains a data base query example.
It contains
facts about areas and populations of some countries, and a rule for computing
the density of a country.
In this example, the primitive predicates 
@l[product], @l[quotient], < and >,
to be described later, are used.
These are used for arithmetic and could be replaced by less efficient
predicates written directly in pure Prolog.

@lisp
(define-predicate density
  @ii[;Density in 1000 people per square mile.]
  ((density ?density ?country)
   (population ?population ?country)
   (area ?area ?country)
   (quotient ?density ?population ?area)))
@end lisp

@lisp
(define-predicate population
  @ii[;Population in millions.]
  ((population 825.0 china))
  ((population 586.3 india))
  ((population 252.1 ussr))
  ((population 211.9 usa))
  ((population 127.6 indonesia))
  @ii[;and so on...]
  )
@end lisp

@lisp
(define-predicate area
  @ii[;Area in 1000 square miles.]
  ((area 3380 china))
  ((area 1139 india))
  ((area 8708 ussr))
  ((area 3609 usa))
  ((area 570 indonesia))
  @ii[;and so on...]
  )
@end lisp

It could be used for answering queries like

@description
@item @t[(density ?density USA)]
What is the density of the USA?

@item @t[(and (population ?pop ?country) ( ?pop 500))]
What countries have half a billion people or more?

@end description

The following predicate finds pairs of countries whose densities are
within 5% of each other.

@lisp
(define-predicate similar-density
  ((similar-density (?country-1 ?country-2))
   (density ?density-1 ?country-1)
   (density ?density-2 ?country-2)
   ( ?country-1 ?country-2)
   (product ?density-2-more 1.05 ?density-2)
   ( ?density-2 ?density-1 ?density-2-more)))
@end lisp

@section The Execution of Pure Prolog
When the user types in a predication to Prolog, Prolog tries to @b[prove]
the predication using its database.  (Formally, it tries to refute the
predication's negation.)
The predication becomes the @b[goal].
@cindex goal

Prolog achieves a goal by searching its database of Horn clauses for ones
whose consequent unifies with the goal, i.e. whose head matches the goal.
The body of the first of these clauses then becomes a new, conjunctive
goal and is achieved recursively.
If this fails, backtracking to the next matching clause occurs.
If the predicate of a goal is built-in then the program associated with that
predicate takes over.
One can depend upon the fact that Prolog will go through the clauses in the
order in which they are defined in the database (by default in LM-Prolog
that is the order of the clauses inside the @l[define-predicate]).
The order in which the elements of the body of a clause will be considered is
the same as they appear within the clause.
For a more detailed discussion of the underlying deduction mechanism of Prolog
see [Kowalski 1974] and [Lloyd 1984].

Prolog programs are sometimes said to have both a @b[declarative] and a
@b[procedural] reading.
Consider the clause defining @l[grandparent] in terms of @l[parent]:
@cindex declarative reading
@cindex reading, declarative
@cindex procedural reading
@cindex reading, procedural

@lisp
((grandparent ?grandparent ?grandchild)
 (parent ?parent ?grandchild)
 (parent ?grandparent ?parent))
@end lisp

This clause can be read declaratively as
``for all @l[grandparent] and @l[grandchild]
the relation @l[grandparent] holds between them if there exists a
@l[parent] such that the relation @l[parent] holds between it and
@l[grandchild] and the relation @l[parent] holds between the
@l[grandparent] and it''.
The clause can be read procedurally as
``if your goal is to determine if the @l[grandparent] relation holds between
@l[grandparent] and @l[grandchild] then replace the goal by two new
goals: determine the relation @l[parent]
between @l[parent] and @l[grandchild] and determine the relation
@l[parent] between @l[grandparent] and @l[parent]''.

@chapter The Predicates
This chapter contains most of the pre-defined predicates of LM-Prolog.
Some of these are written completely in LM-Prolog and are provided because
of their general usefulness.
Others interface to Lisp to provide efficient arithmetic, i/o, and the
like.
The control predicates extend the language beyond the left-to-right
depth-first control regime of Pure Prolog.

The convention for describing the arguments of predicates follows closely
the Lisp Machine convention.
The keyword @l[&rest] indicates that the following variable represent
the rest of the caller's argument list.
The keyword @l[&optional] indicates that the arguments that follow need
not be given.
If any of the arguments that follow @l[&optional] are a list of two elements
then the first element is the variable name and the second describes the
default value.
Additionally, if a variable name begins with `+' then it must be
a term or a bound
variable, if it begins with `-' then it must be unbound, otherwise
it can be either.
@section List Processing Predicates
@defpredicate append ?appended &rest +parts
This predicate is discussed in @ref[append]. @i[?Appended] is the result of
appending the elements of @i[?parts].
@end defpredicate

@defpredicate reverse ?reversed ?list
This predicate holds for lists such that @i[?reversed] 
is @i[?list] reversed.  It happens to be written to run more efficiently
if @i[?list] is the ``input'' and @i[?reversed] is the ``output''
argument.
@end defpredicate

@defpredicate length ?length ?list
This predicate is true when @i[?list] is a @i[?length] long list.
@end defpredicate
@nopara
The predication @l[(length ?n (a b c))] will succeed and bind @l[?n] to
3.
The predication @l[(length 3 ?l)] will succeed and bind @l[?l] to
@l[(?-1 ?-2 ?-3)].
It could be defined as

@lisp
(define-predicate length
  ((length 0 ()))
  ((length ?n (? . ?rest))
   (length ?n-1 ?rest)
   (sum ?n ?n-1 1)))
@end lisp

@defpredicate nth ?nth ?n ?list
This predicate says that @i[?nth] is the @i[?n]th element of
@i[?list].  Zero indexing is used.
@end defpredicate
@nopara
It can be used backwards to find the position of something in a list.
For example, the predication @l[(nth i ?position (m i s s i s s i p p i))]
will first bind @l[?position] to 1, then 4 then 7 then 10.

@defpredicate member ?x ?list
This predicate is true if @i[?x] is a member of the list @i[?list].
@end defpredicate

@defpredicate delete ?left ?out +list
This predicate is true if @i[?left] is @i[+list] with @i[?out] spliced 
out.
@end defpredicate

@defpredicate remove ?left ?out +list
@setq remove section-page
This predicate is true if @i[?left] is those elements of @i[+list] 
which do not match @i[?out].
@end defpredicate

@defpredicate intersection ?intersection &rest +lists
This predicate holds when @i[?intersection] is the intersection of
the @i[+lists].
@end defpredicate
@nopara
It could be defined as

@lisp
(define-predicate intersection
  @ii[;The intersection of no lists is the empty list.]
  ((intersection ()))
  @ii[;The intersection of an empty list and others is the empty list.]
  ((intersection () () . ?))
  @ii[;The intersection of a non-empty list L and some lists Ls,]
  ((intersection ?intersection (?first . ?rest) . ?lists)
   (cases (@ii[;where the first element of L is a member of Ls,]
           (member-of-each ?first . ?lists)           
           (intersection ?rest-intersection ?rest . ?lists)
           @ii[;includes that element,]
           (= ?intersection (?first . ?rest-intersection)))
          (@ii[;otherwise the element is not included.]
           (intersection ?intersection ?rest . ?lists)))))

(define-predicate member-of-each
  ((member-of-each ?))
  ((member-of-each ?x ?first . ?rest)
   (member ?x ?first)
   (member-of-each ?x . ?rest)))
@end lisp

@l[Cases] is an efficient conditional construct, described in @ref[cases].

@defpredicate union ?union &rest +lists
This predicate holds when @i[?union] is the union of
the @i[+lists].
@end defpredicate

@defpredicate sort ?sorted-list +unsorted-list +predicator
@l[Sort] holds if @i[?sorted-list] is a permutation of 
@i[+unsorted-list] such that @i[+predicator] holds between adjacent
elements of @i[?sorted-list].
@end defpredicate
@nopara
@i[+predicator] should correspond to a binary predicate defining a
total order over the elements of the list. @l[standard-order],
discussed in @ref[stord], is a suitable predicate.

@defpredicate substitute ?substituted ?old ?new ?term &optional (+predicate identical)
@i[?substituted] is same as @i[?term] except that all occurrences of
a term @l[x] for which @l[(+predicate x ?old)] holds inside 
are replaced by @i[?new].
@end defpredicate

For example, the predication @l[(substitute ?new-alist (apple ?old-color)
(apple brown) ?alist =)] will replace the old a-list entry of @l[apple] with
one associating it with @l[brown] and find the old entry's association at
the same time.
@l[Substitute] could be defined as follows.

@lisp
(define-predicate substitute
  ((substitute ?substituted ?old ?new ?form ?test-predicate)
   (cases ((?test-predicate ?form ?old) (= ?substituted ?new))
          ((and (not-variable ?form) (= ?form (?first . ?rest)))
           (substitute ?first-substituted ?old ?new ?first)
           (substitute ?rest-substituted ?old ?new ?rest)
           (= ?substituted (?first-substituted . ?rest-substituted)))
          ((= ?form ?substituted))))
  ((substitute ?substituted ?old ?new ?form)
   (substitute ?substituted ?old ?new ?form identical)))
@end lisp

@section Utility Predicates
@defpredicate same &rest +terms
This succeeds only if all the @i[+terms] unify.
@end defpredicate
@nopara
It could be defined as follows

@lisp
(define-predicate same
  ((same ?x ?x . ?more)
   (same ?x . ?more))
  ((same ?)))
  ((same)))
@end lisp

@defpredicate = ?x ?y
@i[?x] and @i[?y] are unified.
This is equivalent to, but faster than, @l[(same ?x ?y)].
@end defpredicate

@defpredicate identical &rest +terms
@setq id section-page
This tests that all @i[+terms] are @b[currently] identical.
@end defpredicate
@nopara
Another way of
expressing it is that the most general unifier for @i[+terms]
is the identity substitution.
This will terminate even if some of the @i[+terms]
are cyclic list structures, provided the @l[circularity-mode] is
@l[:handle].
Cyclic structures are discussed in more detail in @ref[circ].

@defpredicate not-identical ?x ?y
This tests that @i[?x] and @i[?y] are not currently identical.
@end defpredicate


@defpredicate atomic ?x
Tests that @i[?x] is not currently a list.
@end defpredicate

@defpredicate symbol ?x
Tests that @i[?x] is currently a symbol.
@end defpredicate

@defpredicate number ?x
Tests that @i[?x] is currently a number, e.g. a fixnum, a bignum, a flonum,
a rational or complex number, etc.
@end defpredicate


@defpredicate variable ?term
This is true only if @i[?term] is currently unbound.
@end defpredicate


@defpredicate not-variable ?term
This is true only if @i[?term] is currently bound.
Note that it may be bound to a list containing variables.
@end defpredicate


@defpredicate variables ?variables ?term
This is true only if @i[?variables]
is a list of the currently unbound variables in @i[?term].
There are no duplicates in @i[?variables]
and the order of its elements is implementation-dependent.
@end defpredicate

@defpredicate ground ?term
This is true only if @i[?term] is currently variable-free.
It is equivalent to @l[(variables () ?term)].
@end defpredicate


@defpredicate finite ?term
This is true only if there are no cycles inside of @i[?term].
@end defpredicate
@nopara
See the description of @l[circularity-mode] in @ref[circ].

@defpredicate infinite ?term
This is true only if there are cycles inside of @i[?term].
@end defpredicate

See the description of @l[circularity-mode] in @ref[circ].

@defpredicate generate-name ?new-name +old-name
This generates a unique interned symbol whose print name begins with
@i[+old-name].
@i[+old-name] can be any kind of term.
@end defpredicate


@defpredicate generate-symbol ?new-name +old-name
This generates a unique un-interned symbol whose print name begins with
@i[+old-name].
@i[+old-name] can be any kind of term.
@end defpredicate


@section Interface to Lisp
@subsection Calling Lisp from LM-Prolog
This section describes ways of calling Lisp functions from Prolog, how to
pass Prolog arguments to Lisp, and how to pass values of Lisp functions 
back to Prolog.  This involves the issue of how Prolog terms are represented
and stored internally.

@cindex datatype
@cindex locative
@setq dtp section-page
The Lisp interface handles any Lisp Machine datatypes @b[except locatives].
Locatives are considered to be variables by both the interpreter and
compiled Prolog code.
Unbound variables are translated to symbols beginning with `?' before
passing them to Lisp. Lisp cannot pass back Prolog variables ---
symbols beginning with `?' will become Prolog symbols.

@defpredicate lisp-command +statement &optional +mode
@i[+statement] is instantiated and evaluated.
This always succeeds.
@i[+Mode] is described in @ref[dvm] in the description of
@l[delayed-value-mode].
The @i[+mode] argument can be neglected if the @i[+statement] does not
store away anything it receives from Prolog.
If it does store anything then the @i[+mode] should be @l[:copy].
@end defpredicate
@nopara
An example using @l[lisp-command] follows.

@lisp
(define-predicate clear-window
 ((clear-window ?window) 
  (lisp-command (send '?window ':clear-screen))))
@end lisp

Note the convention of quoting Prolog variables before passing them to Lisp:
this is because the Lisp expression is instantiated before it is evaluated.
Instantiation should be viewed as just substituting variables for their 
bindings. The quote is needed in e.g. @l[(symbolp '?x)] to protect 
@i[?x]'s @b[value] from being evaluated.
The compiler arranges so that as much as possible of Lisp expressions like
this are compiled.

@defpredicate lisp-predicate +form &optional +mode
@i[+form] is instantiated and evaluated.
@i[+Mode] is described above.
@end defpredicate
@nopara
This succeeds only if the result of the evaluation is non-@l[nil].
One can define a predicate @l[alphaless]
which is true if its arguments are both
symbols and the first argument is alphabetically before the second as follows:


@lisp
(define-predicate alphaless
  ((alphaless ?x ?y)
   (symbol ?x)
   (symbol ?y)
   (lisp-predicate (alphalessp '?x '?y))))
@end lisp

@setq lispi section-page
@defpredicate lisp-value ?value +form &optional +mode
@i[+form] is instantiated and evaluated and the result is unified with
@i[?value]. @i[+Mode] is described above.
@end defpredicate
@nopara
The predicate @l[product] of any number of arguments can be defined as:

@lisp
(define-predicate product
  ((product ?product . ?arguments)
   (lisp-value ?product (apply 'times '?arguments))))
@end lisp

@l[Lisp-value] can return any kind of Lisp object except for locatives as
they are used internally by the system to represent variables.
Everything passed back except conses will be treated as
atoms. Two Lisp atoms unify only if they are @l[equal] in Lisp's
sense.  Note that the result is not parsed so that symbols beginning with
`?' are treated as ordinary symbols.


@defpredicate lisp-type ?type ?term
This unifies @i[?type] with the Lisp type of @i[?term], or fails if
@i[?term] is a variable.
@end defpredicate
@nopara
It could be defined as follows:

@lisp
(define-predicate lisp-type
  ((lisp-type ?type ?term)
   (not-variable ?term)
   (lisp-value ?type (typep '?term))))
@end lisp


If one wishes to write new primitive predicates in Lisp that cannot be written
using the above, see @ref[exten].
@subsection Calling LM-Prolog from Lisp
The following functions are provided for calling LM-Prolog from Lisp.

@defun prolog:make-query predication &optional &key (lisp-term predication)
This function returns an instance of the flavor @l[prolog:query] which when
sent the message @l[:next-answer] will attempt to prove the
@i[predication].
If successful it will multiple value return 
an instantiation of @i[lisp-term] and @l[t].
If it fails it returns @l[nil].
@end defun
@nopara
Sending the instance another @l[:next-answer] will cause it to look for the
next proof of @i[predication].
The message @l[:flush] should be sent to a query instance so that it can
free up resources that it is holding on to.
The @l[prolog:make-query] takes several more optional
keyword arguments but they are not normally needed.


@defun prolog:query-once predication &optional &key (lisp-term predication)
@setq qonce section-page
This function essentially creates a query and sends it the message
@l[:next-answer] and returns the results as described above.
It also sends a @l[:flush] message.
@end defun

@section Arithmetical Predicates
An experimental version of smart arithmetic exists and is described in
@ref[smart].
The following is a simpler, more efficient, implementation which 
severely restricts which arguments can be variables.
Much is missing (trigonometric functions, exponentiation, etc.) 
because it is so
straight-forward to use @l[lisp-value] as in the definition of @l[sum]
below. 
The following predicates require that all but the first argument be numbers.

@defpredicate sum ?sum &rest +numbers
This unifies @i[?sum] with the sum of the @i[+numbers].
@end defpredicate
@nopara
It could be defined as

@lisp
(define-predicate sum
  ((sum ?sum . ?numbers)
   (lisp-value ?sum (apply 'plus '?numbers))))
@end lisp

@defpredicate product ?product &rest +numbers
This unifies @i[?product] with the product of the @i[+numbers].
@end defpredicate


@defpredicate difference ?difference +number +decrement
This unifies @i[?difference] with the @i[+number] minus @i[+decrement].
@end defpredicate

@defpredicate quotient ?quotient +dividend +divisor
This unifies @i[?quotient] with @i[+dividend] divided by @i[+divisor].
@end defpredicate


The following four predicates require that all arguments be numbers.

@defpredicate < &rest +numbers
The list of @i[+numbers] must be in strictly 
ascending order for this to succeed.
@end defpredicate


@defpredicate > &rest +numbers
The list of @i[+numbers] must be in strictly 
descending order for this to succeed.
@end defpredicate

@defpredicate  &rest +numbers
The list of @i[+numbers] must be in ascending order for this to succeed.
@end defpredicate

@defpredicate  &rest +numbers
The list of @i[+numbers] must be in descending order for this to succeed.
@end defpredicate

The above four predicates hold even if given zero arguments, as
opposed to the corresponding Lisp functions.

@section Input-Output Predicates
@setq io section-page
The optional arguments of these predicates are described in 
the ZetaLisp manual [Moon @i[et al.@/] 1983].

@defpredicate read ?term &optional +stream +eof-option
@i[?Term] is unified with the expression returned by the Lisp function
@l[read] applied to @i[+arguments].
@end defpredicate

@cindex global name
@cindex name, global
@defpredicate global-read ?term &optional +stream +eof-option
This differs from @l[read] only in its handling of variables in the term
read.
For top-level interactions, LM-Prolog supports global names for variables.
The idea is that two global variables are the same if they have the same name.
This is @b[not] a language extension since it applies only to the reader.
@end defpredicate
@nopara
For example, @l[(and (global-read 1) (global-read 2))] will fail if the
terms read are both @l[?x] while @l[(and (read 1) (read 2))] will succeed
under the same circumstances. See @ref[handup] for more about global names.

@defpredicate format ?stream +format-control-string &rest +format-arguments
This provides an interface to ZetaLisp's @l[format] function.
Any special terms inside of the @i[+format-arguments]
obey the current @l[delayed-value-mode].
@end defpredicate

@defpredicate y-or-n +format-control-string &rest +format-arguments
This predicate applies the Lisp function @l[format] to the given arguments,
and asks the user to confirm by typing a single character. The characters which
mean success are @t[Y], @t[T], @spacekey, and @handup.
The characters which mean failure are @t[N], @rubout, 
and @handdown.
@end defpredicate


@defpredicate print +term &optional stream
This predicate always succeeds and applies the pretty printer 
to the given arguments. Special terms such as lazy collections
inside of @i[+term] are run before printing.
@end defpredicate


@defpredicate tyi ?ascii-code &optional +stream +eof-option
This unifies @i[?ascii-code] with the code of the next character read,
as returned by the Lisp function @l[tyi].
@end defpredicate

@defpredicate tyo +ascii-code &optional +stream
This prints the character with the @i[+ascii-code] by calling the
Lisp function @l[tyo].
@end defpredicate

@defpredicate open-file ?stream +file-name &rest +options
This predicate opens the file named @i[+file-name] as a stream and unifies
it with @i[?stream].
@end defpredicate
@nopara
A very common option is @l[:direction] to indicate whether the file
is being opened for @l[:output] or @l[:input] (the default).
Refer to the ZetaLisp manual for a complete description of the function
@l[open].
It is guaranteed that the stream is closed upon
backtracking or abnormal return.
It could be defined as

@lisp
(define-predicate open-file
  ((open-file ?stream . ?arguments)
   (lisp-value ?stream (apply 'open '?arguments))
   (unwind-protect (true) (lisp-command (close '?stream)))))
@end lisp

@defpredicate load +file-name &rest +options
This predicate always succeeds.
It loads a file by calling the Lisp function @l[load].
@end defpredicate

@defpredicate compile-file +file-name &rest +options
This compiles the @i[+file-name] using the Lisp primitive 
@l[qc-file] or @l[compile-file].
@end defpredicate

@defpredicate compile ?predicator &optional ?world ?universe
This ensures that a particular predicate is compiled.
The arguments are as for @l[predicator].
@end defpredicate


@section Control Primitives

@defpredicate true
@end defpredicate
@defpredicate comment &rest +ignore
These predicates succeed.
@end defpredicate
@nopara
@l[Comment] could be defined as

@lisp
(define-predicate comment
  ((comment . ?)))
@end lisp

@defpredicate false
@end defpredicate
@defpredicate fail
These predicates fail.
@end defpredicate
@nopara
@l[False] could be defined by @l[(define-predicate false)].
Unlike some other Prolog implementations, undefined predicates, by default,
signal errors rather than failing, so it is necessary to define @l[false] as
a predicate with no clauses.

@defpredicate and &rest +predications
The conjunction of the elements of
@i[+predications] is satisfied in the order presented.
@end defpredicate
@nopara
@l[(And)] is true.  It could be defined as

@lisp
(define-predicate and
  ((and))
  ((and ?predication . ?more-predications)
   ?predication
   (and . ?more-predications)))
@end lisp

@cindex meta-level predicate
@cindex predicate, meta-level
@l[And] is a @b[meta-level] predicate i.e. its arguments are predications,
rather than terms.  Please note that the syntax for predications allows 
variables anywhere in it.  In the example above, the second clause has two
predications. The first one is just a variable, this means that whatever
predication that variable is bound to at run time will be tried. The
second one is a recursive call to @l[and] with an argument list with
one element less.

@defpredicate or &rest +predications
The @i[+predications] are tried in the order presented.
@end defpredicate
@nopara
@l[(Or)] does not succeed.  It could be defined as

@lisp
(define-predicate or
  ((or ?predication . ?) ?predication)
  ((or ? . ?more-predications) (or . ?more-predications)))
@end lisp

@defpredicate bag-of ?bag ?term &rest +predications
@cindex deterministic predicate
@cindex predicate, deterministic
This predicate is @b[deterministic] which means that it
can generate at most one proof for a given predication.
It  unifies @i[?bag] with the list created by
instantiating @i[?term] in every proof of the conjunction of the elements of
@i[+predications].
@end defpredicate
@nopara
The order of the elements of the bag is the same as they are found.
Unlike Dec 10/20 Prolog, the bag produced by @l[bag-of] can be empty if
the system cannot prove the @i[+predications].
For example, the call @l[(bag-of ?b (?x ?y) (append (a b) ?x ?y))]
will bind @l[?b] to @l[((() (a b)) ((a) (b)) ((a b) ()))] which is 
the list of pairs of lists which append to form @l[(a b)].
A common way to execute a predication until it fails is as @l[(bag-of ? ?
@i(predication))].
This compiles well and is clearer than @l[(or (and @i(predication) (false))
(true))].

@defpredicate lazy-bag-of ?bag ?term &rest +predications
This differs from the previous predicate only in the manner in which the bag is
computed. 
The bag is computed only as needed or ``looked at''.
A @l[lazy-bag-of] predication succeeds immediately and @i[?bag] is bound
to a @b[lazy value], 
i.e. data structure which computes its elements when necessary to decide a
unification.
@end defpredicate
@nopara
@cindex lazy value
@cindex value, lazy
It is the unification of a delayed value and a non-variable term that causes
the delayed value to compute its value.
Lazy bags when being unified with non-variable term become either @l[()] or
a cons of a term and a new delayed value.
For example, the list of all factorials
can be described by
@l[(lazy-bag-of ?all-factorials ?factorial (factorial ?factorial ?))].
@l[?All-factorials] behaves indistinguishably from the list of all primes
numbers. 
For example, the predication @l[(member 24 ?all-factorials)] will cause the
first five factorials to be computed before it succeeds.

A classic co-routining problem is the Same Fringe Problem.
Given two trees represented as list structures,
we wish to determine whether they have the same leaves. 
We consider n-ary trees where the branches of a tree are represented
by the elements of a list.
We solve this by constructing for each tree a lazy bag of its leaves and
then unifying the collections.

The entire LM-Prolog program follows: 

@lisp
(define-predicate same-fringe
  ((same-fringe ?tree-1 ?tree-2 ?lazy-or-eager) @ii[;if]
   (lazy-bag-of ?fringe ?leaf (has-leaf ?leaf ?tree-1)) @ii[;and]
   (lazy-bag-of ?fringe ?leaf (has-leaf ?leaf ?tree-2))))

(define-predicate has-leaf
  ((has-leaf ?first (?first . ?)) @ii[;if]
   (atomic ?first))
  ((has-leaf ?leaf (?first . ?)) @ii[;if]
   (not-atomic ?first) @ii[;and]
   (has-leaf ?leaf ?first))
  ((has-leaf ?leaf (? . ?rest)) @ii[;if]
   (has-leaf ?leaf ?rest)))
@end lisp

In the lazy bag computation, in contrast to the normal
sequential computation,
as soon as a difference is detected 
the predicate @l[same-fringe] will fail and unnecessary
computation involving the rest of the two trees will have been avoided.
This program depends upon the fact that the bag contains duplicates and the
order of its elements are those produced by a depth-first search.

Another use of lazy bags is for implementing input streams.
Consider the following program for creating a list containing all the
characters in a file.

@lisp
(define-predicate file-characters
  ((file-characters ?stream ?file-name)
   (open-file ?lisp-stream ?file-name)
   (lazy-bag-of ?stream
                ?character
                (tyi-until-eof ?character ?lisp-stream))))
@end lisp

@lisp
(define-predicate tyi-until-eof
  ((tyi-until-eof ?character ?stream)
   (tyi ?char ?stream -1) @ii[;binds @t(?char) to @t(-1) if end of file.]
   ( ?char 0)
   (or (= ?char ?character) (tyi-until-eof ?character ?stream))))
@end lisp

An experimental parallel processing package described in @ref[exper] provides
versions of @l[bag-of] and @l[set-of]
that compute their elements in independent parallel processes.
For a detailed discussion of lazy and eager collections see [Kahn 1983a].

@defpredicate set-of ?set ?term &rest +predications
This differs from @l[bag-of]
only in that duplicates in @i[?set] are removed.
Two elements are considered duplicates if the relation @l[identical] 
(@ref[id]) holds between them.
@end defpredicate
@nopara
For example, the intersection of the elements of two lists can be computed by 
@l[(set-of ?intersection ?x (member ?x ?list-1) (member ?x ?list-2))].

@defpredicate lazy-set-of ?set ?term &rest +predications
This is the ``lazy'' version of @l[set-of].
It differs from @l[lazy-bag-of] in that duplicates are eliminated.
@end defpredicate

@defpredicate prove-once &rest +predications
This succeeds if there is at least one proof of the conjunction of the
@i[+predications].
Only the first proof found will be used.
@end defpredicate
@nopara
It could be defined as:

@lisp
(define-predicate prove-once
  ((prove-once . ?predications)
   (lazy-bag-of (?predications . ?) ?predications . ?predications)))
@end lisp

@cindex instantiation
The execution of the @l[lazy-bag-of] predication above attempts to satisfy
the conjunction of @i[+predications] and if successful it @b[instantiates]
the @i[+predications] and unifies the result with the original
@i[+predications]. To instantiate a term means essentially to copy it,
in particular to copy all variable bindings in it.  The purpose of
instantiation is to protect a term from having the variables in it
becoming unbound when Prolog backtracks.
This moves out the bindings created within the collection process.

@defpredicate cannot-prove &rest +predications
This is true only if the conjunction
of the elements of @i[+predications] cannot be achieved.
No bindings are created.
@end defpredicate


@defpredicate can-prove &rest +predications
This is the same as @l[prove-once] except that no bindings are made.
When one is interested only in the truth value of a predication or conjunction 
of predications then this predicate prevents the system from upon backtracking 
looking for other proofs of the predications.
@end defpredicate
@nopara
It could be defined as

@lisp
(define-predicate can-prove
  ((can-prove . ?predications)
   (lazy-bag-of (? . ?) ? . ?predications)))
@end lisp

or alternatively as

@lisp
(define-predicate can-prove
  ((can-prove . ?predications)
   (cannot-prove (cannot-prove . ?predications))))
@end lisp

@defpredicate cases &rest +alternatives
@setq cases section-page
This is equivalent to the conjunction of the elements of the first alternative
whose first element is provable.
If there is no such clause it is false.
The alternatives are considered mutually exclusive.
@end defpredicate
@nopara
For example, the predicate @l[maximum] could be defined using @l[cases]
as:

@lisp
(define-predicate maximum
  ((maximum ?max ?x ?y)
   (cases ((> ?x ?y) (= ?max ?x))
          ((= ?max ?y)))))
@end lisp


The call to @l[cases] above can be viewed as short-hand for

@lisp
(or (and (> ?x ?y) (= ?max ?x))
    (and (cannot-prove (> ?x ?y)) (= ?max ?y)))
@end lisp

The important difference is that @l[cases] avoids the re-computation of the
predication @l[(> ?x ?y)].
@l[Cases] is due to IC-Prolog [Clark and McCabe 1982a].

@defpredicate if +test +then &optional +else
@l[If] is syntactic variant of @l[Cases].
@l[Maximum] could be defined using @l[if] as

@lisp
(define-predicate maximum
  ((maximum ?max ?x ?y)
   (if (> ?x ?y) (= ?max ?x) (= ?max ?y))))
@end lisp

@l[If] could be defined as
@lisp
(define-predicate if
  ((if ?test ?then ?else) (cases (?test ?then) (?else)))
  ((if ?test ?then) (cases (?test ?then) ((true)))))
@end lisp
@end defpredicate

@defpredicate either &rest +predications
This works like @l[(cases (+predication@-(1)) (+predication@-(2)) ... (+predication@-(n)))].
@end defpredicate

@defpredicate rules ?term &rest +rules
Each rule is of the form @l[(?term-n . ?conditions-n)].
@l[Rules] succeeds with
the first rule for which @i[?term-i] unifies with @i[?term] and the
conjunction of @i[conditions-i] are satisfiable.
It fails if there is no such rule.
@end defpredicate
@nopara
@l[Maximum] could be defined using @l[rules] as

@lisp
(define-predicate maximum
  ((maximum ?max ?x ?y)
   (rules ?max
          (?x (> ?x ?y))
          (?y))))
@end lisp


@l[Rules] could be defined as

@lisp
(define-predicate rules
  ((rules ?term (?term-1 . ?conditions-1) . ?more-clauses)
   (either (and (= ?term ?term-1) . ?conditions-1)
           (rules ?term . ?more-clauses))))
@end lisp

Note that if @l[either] were replaced by @l[or] this would correspond to
the resolution of the @i[?term] against the clauses.

@defpredicate unwind-protect +predication &rest +undo-predications
This is logically equivalent to @*
@l[(or +predication (and (and . +undo-predications) (false)))]@*
The system guarantees however that the @i[+undo-predications]
will be attempted even in the case of
abnormal return due to the use of @l[cut],
lazy collections, or the user hitting @abort.
@end defpredicate
@nopara
The @i[+undo-predications] usually undo some side-effect done by the @i[+predication].
For example, the predicate @l[assume] which
adds a clause to the database and
retracts it upon backtracking could be defined as:

@lisp
(define-predicate assume
  ((assume ?clause)
   (generate-symbol ?clause-name clause)
   (unwind-protect (assert (?clause-name . ?clause))
                   (retract (?clause-name . ?clause)))))
@end lisp

The optional naming of clauses is described in @ref[clname].

@defpredicate map +predicator &rest +list-of-lists
This applies the @i[+predicator] to successive elements in each of the
@i[+list-of-lists].
@end defpredicate
@nopara
This predicate is due to Prolog/KR [Nakashima 1982].
Some examples follow:

@lisp
(map sum ?x (1 2 3) (9 12 15) (-2 -1 0)) @ii[;binds @t(?x) to @t"(8 13 18)"]

(map first (?a foo ?c) ((bar zap) (foo silly) ?d))
@exdent 1600 binds ?a to bar and ?d to (?c . ?)
@exdent 1600 where (define-predicate first ((first ?x (?x . ?))))

(map > (6 7 8) (1 2 99)) @ii[;fails since 8 is not greater than 99]
@end lisp

@prindex first
@prindex second
@prindex third
@prindex fourth
@prindex rest

The predicates @l[first], @l[second], @l[third], @l[fourth],
and @l[rest] select the corresponding element or elements of a list.
They have been found useful only when using @l[map].

@defpredicate cut
This is provided mainly for compatibility with other Prolog systems.
It succeeds.  As a side-effect, it removes all backtracking alternatives
introduced from the invocation of the predicate in which it occurs.
In other words, if a @l[cut] is encountered in a clause then
upon backtracking the goal which invoked the clause will fail even if there are
more possibilities within the clause or if there are more clauses to consider.

The scope of a @l[cut] is lexical.
@cindex scope
@end defpredicate
@nopara
Note that this interpretation of @l[cut] makes its behavior very peculiar if
it occurs inside of a collection (@l[bag-of], @l[set-of], etc.) and such
uses should be avoided.

@l[Cases] and @l[lazy-bag-of] can do all that @l[cut]
can in a much clearer and more structured way.
The most common use of @l[cut] is to declare that only some solutions are of
interest.
(See the description of @l[prove-once] above.)

Compare the standard definition of @l[cannot-prove]
(called @l[not] or @l[\+] in other Prolog implementations) using
@l[cut]

@lisp
(define-predicate cannot-prove
  ((cannot-prove . ?predications) (and . ?predications) (cut) (fail))
  ((cannot-prove . ?)))
@end lisp

and the definition using @l[lazy-bag-of]

@lisp
(define-predicate cannot-prove
  ((cannot-prove . ?predications) (lazy-bag-of () ? . ?predications)))
@end lisp

These two implementations of @l[cannot-prove] compile to equivalent code.

One common use of @l[cut] is to avoid re-computing predicates.
Consider the following definition of @l[Maximum] using no control
primitives.

@lisp
(define-predicate maximum
  ((maximum ?x ?x ?y) (> ?x ?y))
  ((maximum ?y ?x ?y) ( ?x ?y)))
@end lisp

It is common practice to use a @l[cut]
to avoid computing @l[( ?x ?y)] as follows.

@lisp
(define-predicate maximum
  ((maximum ?x ?x ?y) (> ?x ?y) (cut))
  ((maximum ?y ?x ?y)))
@end lisp

Compare this definition to those using @l[cases] and @l[rules] presented
earlier.

@chapter Definition of Predicates
@setq defpred section-page
@section Introduction

@cindex world
@cindex universe
A predicate in LM-Prolog is a list of clauses.
A @b[world] is a collection of predicates.
The current database is described by the @b[universe]
which is a list of worlds.
To find a predicate's definition, LM-Prolog behaves as if it were 
searching linearly down the list of worlds in the current universe.
(It actually searches a data structure on the property list of the
predicator.)

@cindex memoization
Associated with every definition are instructions as what to do if there are
other definitions in later worlds.
By default they are ignored.
This whole process of finding the definition of a predicate is @b[memoized]
so that the associated overhead is paid only the first time a predicate is
referred to in a new universe.

Worlds can be used in a static fashion to achieve modularity.
Modularity can also be achieved using the ZetaLisp
package facility.
The universe can also be changed during a session.
A large system, for example, can have two or more versions
of some module.
Perhaps one keeps expensive records for later use in
providing explanations, another runs substantially faster, and a
third is an experimental version under development.
It becomes very simple to switch between these modules if
each one has its predicates defined in different worlds.
The universe can also be changed dynamically during the program execution.
While this ability can be abused by users, it can be 
a powerful programming technique.
The trace package (@ref[trace]), for example, keeps the traced versions of
predicates in one world and leaves the original definitions
untouched.
When trace is enabled the world with traced predicates is the first in the
universe and essentially masks the originals.
The stepper often ``binds'' the universe to include or exclude the traced
predicates to ``crawl'' and ``leap'' respectively.

@defpredicate define-predicate +predicator (:options . +option-alist) &rest +list-of-clauses
@end defpredicate
@defpredicate define-predicate +predicator &rest +list-of-clauses
The principle means of creating and modifying predicates is through the use of
the predicate @l[define-predicate].
Each clause in @i[+list-of-clauses] must have a head whose first
element is @i[+predicator].
They are added to the database in the same order in which they appear in the
@i[+list-of-clauses].
The @i[+option-list] is a list of options,
where each option is a list beginning with an option name.
All options and values are in the @l[keyword:] package.
(Remember to put `:' in front of all options.) 

@l[Define-predicate] can be used as a Lisp macro as well as a Prolog predicate.
Consequently files containing predicate definitions can be loaded, compiled,
etc. just as ordinary Lisp files.
If seen in the context of the Lisp compiler, a predicate definition is first
compiled to Lisp by LM-Prolog's compiler. Later, when the result of the
compilation is loaded, the predicate definition is added to the database
as a compiled predicate.
If executed as a Prolog predicate or as a Lisp form,
the predicate definition is added to the database
as an interpreted predicate.
@end defpredicate

@section Define-Predicate Options
The processing of each definition is affected by the @l[define-predicate]
options currently in effect.
These come from three sources, listed in increasing order
of precedence.

@enumerate
@item The default options, documented below.

@item Any options that you have included in the File Attribute List. 
The word @l[options] is known to the system as a file attribute and can be
included in the ``-*-'' line of source files. Its value should be an alist
of some of the possibilities listed below. File attributes are explained
in the ZetaLisp manual.
@cindex file attribute

@item The @l[:options] part of the definition.
@end enumerate

@defineoption :type +type
The possible values of @i[+type] are @l[:static] and @l[:dynamic].

@l[:Static] is the default and declares that no clauses may be added or removed
from this definition.
A type of @l[:dynamic] means that the predicate is not 
protected against change.
@end defineoption
@nopara
The compiler fully supports dynamic
predicates as well as static ones.
However, optimizations that would not
be feasible for dynamic predicates are performed on static ones.

@defineoption :world +world
@i[+world] should be a symbol and is used to name a collection of predicates,
to which the predicate being defined is added.
@end defineoption
@nopara
@woindex :user
@woindex :system
The default world is called @l[:user].
Most system predicates belong to the world @l[:system].

@defineoption :if-another-definition +action
This option allows one to control what happens if a predicate is defined in
more than one world in the current universe. The value of this option should be
either @l[:before], @l[:after], or @l[:ignore].
At run time, the other definition
will be tried before the current one, after the current one, or not at all, 
respectively.
@l[:Ignore] is the default.
@end defineoption
@nopara
This facility can be used to, for example, ``cache'' the results of
computations.
(The logic programming community sometimes calls this ``adding lemmas''.)
The following predicate will cache its argument in the world called @l[:cache]
which is earlier in the universe than the original predicate and its
traced version.
It uses the trace facility described in @ref[trace].

@lisp
(define-predicate cache-predicate
 ((cache-predicate ?predicator)
  (define-predicate ?predicator
    (:options (:type :dynamic)
              (:world :cache)
	      (:if-another-definition :try-after)))
  (trace ?predicator
         (:print-if) @ii[;don't print anything when called.]
         (:after cache-predication))))
@end lisp

@lisp
(define-predicate cache-predication
  ((cache-predication ?predication)
   (assert (?predication) :cache)))
@end lisp

The predication @l[(cache-predicate fibonacci)], for example,
would cause the predicate
@l[fibonacci] to be cached in the world called @l[:cache].

@defineoption :if-old-definition +keep-or-flush
If there already is a predicate of the same name in the same world then
if @i[+keep-or-flush] is @l[:keep] the new clauses are added to the old
predicate, otherwise if it is @l[:flush] then the new definition replaces 
the old one. The default is @l[:flush].
@end defineoption
@nopara
@setq clname section-page
Optionally a clause can have a name which is a symbol in the first position.
The name is very useful in updating and maintaining the database of clauses.
The name is unique within a definition.
The recommended way to have a predicates definition spread out between
different files (or parts of the same file) is by using named clauses and the
@l[(:if-old-definition :keep)] option.
This way the file can be re-loaded.
If one of the clauses is edited, then the new version will replace the old.
For example, an predicate called @l[equivalent] which decides if its
arguments are equivalent may be have its definition spread out so that those
clauses dealing with arithmetic are in one file, those with geometric figures
another and so on.
A typical clause could be described as

@lisp
(define-predicate equivalent
  (:options (:if-old-definition :keep))
  (zero-is-plus-identity
    (equivalent (plus ?zero ?x-1) ?x-2)
    (equivalent ?zero 0)
    (equivalent ?x-1 ?x-2))
  (plus-is-commutative
    (equivalent (plus ?x-1 ?y-1) (plus ?y-2 ?x-2))
    (equivalent ?x-1 ?x-2)
    (equivalent ?y-1 ?y-2)))
@end lisp

@defineoption :place-clauses +where
This option can be used together with @l[(:if-old-definition :keep)].
It controls exactly where the new clauses go.  The value @l[:before]
means before previous ones, @l[:after] means after previous ones, and
@l[:anywhere], which is the default, lets LM-Prolog decide.
@end defineoption

@defineoption :indexing-patterns &rest +patterns
@setq indpat section-page
This option allows for indexed database search when predications of the
current definition are to be satisfied.  @i[+Patterns] is a list
of search patterns that can be used by the theorem prover.
@end defineoption
@nopara
As an example consider a predicate @l[area] used as a database of areas
of countries.  It could have an indexing-pattern @l[(area +area -)]
meaning that the first argument may be used as a search key @b[if
bound].  It could have another indexing pattern @l[(area - +country)]
which could be used if the second argument happens to be bound.
In general, an indexing pattern specifies a particular component of
the predication to be satisfied.  If the component is bound,
it is used as a hash key for the predicate.  There may still be several
clauses whose heads match the predication. 
In an indexing pattern there should be exactly one component beginning with
a `+' to specify what the key is.

For example, the following definition of @l[father] creates indexes 
such that the system can find the clauses for a given father or son in constant
time.

@lisp
(define-predicate father
  (:options (:type :dynamic)
            (:indexing-patterns (father +father -son)
                                (father -father +son))))
@end lisp

The cost of finding an indexed clause is independent of the number of clauses
in the definition.
For the interpreter, indexing is worthwhile if there are about 50 
clauses, for compiled predicates it depends on the type of predicate.
For static predicates the cost is like searching about 120 
clauses, for dynamic predicates it's like searching 25 clauses or so.
These numbers are largely due to the fact that unification is in micro-code.

@defineoption :deterministic +when
This option is used to declare to the system that certain optimizations are
possible since the predications of the predicate being defined have at most one
solution.
@end defineoption
@nopara
Both the interpreter and compiled code perform significant optimizations if 
the option @l[(:deterministic :always)] is provided.
The compiler can often determine on its own that a predicate is deterministic,
especially if the @l[:argument-list] option described below is provided.
This can be used as an alternative to @l[cut] when one is interested in only
the first solution found for all calls to the predicate.

@defineoption :compile-method &rest +method
This option affects the compilation of calls to the predicate being defined. 
It can take one of the following forms.

@description
@item @l[(:compile-method :closed)]
@kindex :closed
This is the default and means that in the sequel, any calls to
the predicate being defined shall be compiled in the normal way i.e. as a
sort of function call to the ``entrypoint'' function of the predicate.
@cindex closed compilation
@cindex compilation, closed

@item @l[(:compile-method :open)]
@kindex :open
This works like a generalization of the @l[defsubst] feature in Lisp.
After a definition with this option has been encountered by the compiler, 
any predications of the predicate being defined are @b[opened]; 
i.e. they are replaced by the 
result of resolving the predication with the definition of the predicate.
@cindex open compilation
@cindex compilation, open

@item @l[(:compile-method :intrinsic @i(function-name))]
@kindex :intrinsic
This is a handle for having the compiler generate hand-tailored code.
It is discussed in @ref[exten].
@cindex intrinsic compilation
@cindex compilation, intrinsic

@end description
@end defineoption
@nopara
Semantically, there is no difference between open and closed compilation.
The unification of actual and formal argument lists
is partially evaluated at compile time to win efficiency.
However, in order for the compiler to compile calls open, the
definition of a predicate to be open coded must precede its use.
If it does not, an ordinary closed call will be generated, and the code
will still run although somewhat slower.
This compile-method suffers from the same problem as Lisp's @l[defmacro],
@l[defsubst] and the like, namely if you change a definition
whose compile-method is open, any definitions using it have to be re-compiled
too.
There is an obvious space-time trade-off that has to be considered:
if a definition to be open-coded is large, each use of it will compile
to rather lengthy code.

Open compilation is useful if you want to define meta-level predicates, 
that is to say,
predicates that take arguments that are being used as predications.  Those
predications would not be compiled as such in closed compilation.
Another useful case for open compilation is when a predicate is used
merely as an alias for another one, perhaps with a different order of
arguments.

@l[true], @l[false], @l[=], @l[sum] and @l[cannot-prove] 
compile open, for instance. Of course, @l[:compile-method :open] must not 
be used in a recursive predicate, or else
the compiler will go on opening predications forever.

@defineoption :argument-list +pattern
It is good practice to declare the argument list, and to give
the arguments mnemonic names. This option
is used for self-documentation of the predicate.
@end defineoption
@nopara
The @csh[A] command in
both the editor and the rubout handler will show the @i[+pattern]
as does the predicate @l[documentation].

This option also affects the compilation of the pattern-matching part
(unification) of the predicate being compiled.  It is used to give the
compiler partial knowledge about possible argument lists. This knowledge is
used to reduce the time consumed by the unification, and the size
of the code for it. More importantly, `+'s help detect mutually exclusive
clauses within a predicate which in turn helps detect that a 
predicate is deterministic.
Deterministic predicates can be compiled to run significantly faster than
non-deterministic predicates.

An argument list is a list of symbols and lists.
A symbol beginning with `+' indicates that the corresponding element must be
bound, a symbol beginning with `-' indicates that it must be unbound, and
other symbols allow anything in the corresponding position.
For `+' and `-', the corresponding element must not be
a special term (see @ref[dvm]).
The key words @l[&rest] and @l[&optional] are also allowed.
They indicate that what follows corresponds to the rest of the arguments.
A list in an argument list (except after @l[&optional]) means that the
corresponding argument must be a list satisfying the constraints described
within the list. A list following @l[&optional] may be 
provided for documentation purposes.

Examples:

@description
@item @l[(+x +y -z)]
means that there are three arguments, the first two are
bound and the third one is unbound.

@item @l[((x +y) +z &rest +)]
means that there are at least two arguments, the first one
being a list of anything and a non-variable element.

@item @l[(&rest anything)]
is the default and means that any argument list is handled.
@end description

If you define a @l[:static] predicate without declaring its argument list,
the compiler will look at the heads of the clauses and compute
a suitable argument list.  This is because Prolog code compiles to Lisp
functions with corresponding argument lists.
@l[(&rest anything)] would become just a Lisp rest argument, with
a fairly expensive unification of it and the heads of the clauses.

If you lie when you use this @l[define-predicate] option,
then calls not satisfying the argument list will either fail or
signal an error.

@defineoption :lisp-macro-name +macro-name
This defines a Lisp macro named @i[+macro-name] which executes
the predication
corresponding to the predicator being defined and the macros arguments.
The call expands to a call to @l[prolog:query-once] (@ref[qonce])
so it does not backtrack.
@end defineoption
@nopara
This is primarily useful for including predications in files that either change
the database or customize the system.
If the predicate @l[assert], for example, had the option
@l[(:lisp-macro-name assert)] 
then @l[assert] could be used at top level in
files and to Lisp.

@defineoption :documentation +documentation-string
It is good practice to include a brief documentation of predicates.
This option is used for self-documentation of the predicate.
@end defineoption
@nopara
The @i[+documentation-string] is accessed by the @csh[D] command in 
both the editor and the rubout handler.
It can also be retrieved by a program as 
@l[(option (:documentation ?d) ?predicator)].
The @b[predicate] @l[documentation] uses this.

@chapter Database Predicates

@defpredicate assert +clause &optional +world
@l[Assert] can only be performed upon predicates of type @l[:dynamic].
It adds a clause to @i[+world].
@i[+World] defaults to the current defining world.
@end defpredicate
@nopara
This could be defined as follows

@lisp
(define-predicate assert
  ((assert ?clause)
   (option (:world ?default-world))
   (assert ?clause ?default-world))
  ((assert ?clause ?world)
   (prolog:clause-predicator ?predicator ?clause)
   (define-predicate ?predicator
     (:options (:world ?world)
               (:type :dynamic)
               (:if-old-definition :keep)
     ?clause)))
@end lisp

@l[Prolog:clause-predicator] is a system internal
predicate that gets the predicator of the head of a clause whether named or
not.

@defpredicate assume +clause &optional +world
This is just like @l[assert] but in addition it is guaranteed that 
@i[+clause] is deleted upon backtracking or abnormal return.
@i[+World] defaults to the current defining world.
@end defpredicate
@nopara
See the description of @l[unwind-protect] earlier.

@l[Assume] is typically used for asserting lemmas that are only relevant
to a few predicates of a program.
The alternative would be to pass around those
results as arguments everywhere. 
This is both awkward and exploring the data structure representing new lemmas
is typically much slower than using LM-Prolog's clause indexing.
Of course, the cost of asserting and retracting @i[+clause] must
be taken into account.
These considerations are discussed in @ref[retract].

@l[Assume] is for example used in the trace package (@ref[trace]) to keep
track of indentation levels. The current indentation level is stored in the
predicate @l[*indentation*] which is updated as follows when a predicate
is entered.

@lisp
(define-predicate indentation
  ((indentation ?indentation)
   (prove-once (*indentation* ?indentation))
   (sum ?next-indentation ?indentation 1)
   (assume ((*indentation* ?next-indentation)))))
@end lisp

When a predicate succeeds, the indentation level is decremented by

@lisp
(define-predicate decrement-indentation
  ((decrement-indentation)
   (prove-once (*indentation* ?next-indentation))
   (difference ?indentation ?next-indentation 1)
   (assume ((*indentation* ?indentation)))))
@end lisp

Upon backtracking, it is guaranteed by the @l[assume] mechanism that
the indentation levels are restored.

@defpredicate retract +clause &optional +world
This predicate deletes any clause matching @i[+clause] in @i[+world].
@i[+World] defaults to the current defining world.
It backtracks, trying each time to delete another clause.
@end defpredicate

@defpredicate retract-all +predicator &optional +world
This predicate deletes all clauses of a given predicate in @i[+world].
@i[+World] defaults to the current defining world.
It always succeeds.
@end defpredicate
@nopara
Note that the definition of the predicate is not destroyed.
The tables associated with indexing patterns for example are cleared but are
still available for indexing new clauses.

@defpredicate remove-definition +predicator +world
This predicate does everything that @l[retract-all] does, in addition
it deletes the (now empty) definition itself. This operation is
necessary if a predicate was mistakenly defined either with the wrong
name or in the wrong world, to undo the definition. An empty definition
could mask a definition of the same predicator in a different world.
@end defpredicate

@defpredicate all-worlds ?worlds
@i[?Worlds] are all worlds ever created.
@end defpredicate

@defpredicate universe ?worlds
@i[?Worlds] is the current universe, i.e. the list of current worlds.
@end defpredicate

@defpredicate add-world +world
@i[+World] is removed from the universe if it's already there. It is then 
added to the front of the universe.
@end defpredicate

@defpredicate remove-world +world
@i[+World] is deleted from the current universe.
@end defpredicate

@defpredicate save-world +world +file-name
All definitions in @i[+world] are written onto @i[+file-name].
@end defpredicate
@nopara
This could be defined by

@lisp
(define-predicate save-world
  ((save-world ?world ?file-name)
   (bag-of ? ?
     (open-file ?stream ?file-name :out)
     (format ?stream ";; -*- Mode: Lisp; -*-~%")
     (definition ?definition ? ?world)
     (print ?definition ?stream))))
@end lisp

@defpredicate destroy-world ?world
This runs @l[remove-definition] on every predicate defined in @i[?world]
and then deletes any reference to @i[?world].
@end defpredicate
@nopara
This should be done if one wishes the garbage collector
to reclaim the space used by a world.

@defpredicate with-world +world &rest +predications
@i[+Predications] are satisfied with @i[+world] temporarily added
to the current universe.
If @i[+predications] calls any predicate that changes the universe the
change will only have the scope of the @l[with-world].
@cindex scope
@end defpredicate
@nopara
This could have been implemented as follows

@lisp
(define-predicate with-world
  ((with-world ?new-world . ?predications)
   (universe ?current-worlds)
   (with (universe (?new-world . ?current-worlds)) . ?predications)))
@end lisp

@l[With] is described in @ref[with].

@defpredicate without-world +world &rest +predications
@i[+Predications] are satisfied with @i[+world] temporarily removed
from the current universe.
@end defpredicate
@nopara
@defpredicate call +predication &optional +world
@l[Call] of one argument is provided for compatibility with other Prologs
and because some people prefer it over the default implicit call of a variable.
@l[Call] is implicit for any predication.
For example, @l[(print 1)], @l[(call (print 1))],
@l[(and (= ?g (print 1)) (call ?g))], @l[(and (= ?g (print 1)) ?g)],
and @l[(and (= ?p print) (?p 1))] are all equivalent.

@l[Call] of two arguments allows one to specify explicitly which world the
definition of the predicator of the @i[+predication] should be found.
@end defpredicate
@nopara
The implementation of @l[trace], for example, uses this.
It creates a version of a traced predicate in a special world called
@l[prolog:traced-predicates] which is in the beginning of the universe.
Inside the new predicate it needs to call the original predicate and does so
using @l[call] of two arguments.
@windex prolog:traced-predicates

@defpredicate predicator ?predicator &optional ?world ?universe
This predicate succeeds if @i[?predicator] is a predicator in @i[?world]
in @i[?universe]. @i[?Universe] defaults to the current universe, and
@i[?world] is a member of @i[?universe].
@end defpredicate

@defpredicate defined-in-world ?world ?predicator
@i[?World] is unified with a world where @i[?predicator] is
defined.
It could be defined as

@lisp
(define-predicate defined-in-world
  ((defined-in-world ?world ?predicator)
   (all-worlds ?worlds)
   (predicator ?predicator ?world ?worlds)))
@end lisp
@end defpredicate

@defpredicate apropos ?predicator +substring &optional ?world ?universe
This predicate is like @l[predicator] with the additional constraint
that @i[?predicator] must contain @i[+substring] in its print name.
@end defpredicate

@defpredicate definition ?definition ?predicator &optional ?world ?universe
This predicate is like @l[predicator] with @i[?definition] being unified
with each definition found.
The @i[?definition]'s option list is the merger of those given when defined
and the defaults at the time of creation.
@end defpredicate

@defpredicate print-definition ?predicator &optional ?world ?universe
This predicate prints out appropriate definition. Only those options
that differ from the current set of defaults are printed.
This backtracks if the definition is under specified.
@end defpredicate
@nopara
For example, @l[(bag-of ? ? (print-definition ?))] will print out all
definitions.

@defpredicate documentation ?predicator &optional ?world ?universe
This predicate prints out the @l[:argument-list] and @l[:documentation]
options in an easy to read format.
@end defpredicate
@nopara
For example, the predication @*
@l[(bag-of ? ? (apropos ?predicator ``world'' ?w) (documentation ?predicator ?w))]@*
will print out the documentation of all predicates whose name contains the
string @l[``world''].

@defpredicate clause ?clause &optional ?world ?universe
This predicate is reminiscent of @l[predicator] but unifies @i[?clause]
with clauses found.
@end defpredicate
@nopara
For example, the predication

@lisp
(and (clause (?head . ?body))
     (member (print . ?arguments) ?body))
@end lisp

will find all clauses that contain a top-level @l[print] predication.
@defpredicate prolog:clauses ?clauses +predication
This unifies @i[?clauses] with those clauses that the system considers
possibly appropriate for the @i[+predication].
It does not unify the @i[+predication] with the heads of the @i[?clauses]
but it does use any indexing patterns provided (see @ref[indpat]).
Except for the indexing patterns it could be defined as

@lisp
(define-predicate clauses
  ((clauses ?clauses (?predicator . ?))
   (definition (define-predicate ?predicator ? . ?clauses)
               ?predicator)))
@end lisp
@end defpredicate

@chapter System Customization
This chapter contains primitives for inspecting and changing the various modes
and global parameters of the system.

@defpredicate option (?option-name . ?values) &optional ?predicator ?world ?universe
If called without any ``optional'' arguments 
this unifies @i[?values]
with the default value for @l[define-predicate] option
@i[?option-name].
@end defpredicate
@nopara
For example, @l[(option (:world ?w))] will bind @l[?w]
to the default world for new definitions.
If the @i[?predicator] is given then the @i[?values]
for that predicator are given.
One can further specify the @i[?predicator]'s @i[?world] or
@i[?universe].

@setq circ section-page
@defpredicate circularity-mode ?mode
@i[?Mode] is unified with the current circularity mode, which is either
@l[:ignore], @l[:handle], or @l[:prevent].
The issue this addresses is that unification is defined to prevent cyclic
bindings such as @l[(= ?x (f ?x))].
This is normally prevented by an ``occur check'' which most Prolog
implementations neglect to make in the interests of efficiency.
LM-Prolog users decide whether they want the occur check or not.
In addition, if the occur check is ignored then the system can handle
cyclic structures.
If the circularity-mode is @l[:handle] then the system will be able to unify,
print, and instantiate cyclic structures.
@end defpredicate
@nopara
The default circularity mode is @l[:ignore].
The circularity mode can be altered by @l[make-true] and @l[with]
described below.
A discussion of this issue can be found in [Colmerauer 1982a] and
[Hansson @i[et al.@/] 1982] among others.

@setq dvm section-page
@defpredicate delayed-value-mode ?mode
This predicate inspects the default mode of interfacing Prolog and Lisp.
This unifies @i[?mode] with the default action taken when Prolog calls
Lisp. The value can be @l[:copy], @l[:invoke], @l[:query], 
or @l[:dont-invoke]. It is @l[:query] initially.
The predicate @l[make-true] and @l[with] described below can be used to
alter the @i[?mode].
@end defpredicate
@nopara
The rationale for having different modes here has to do with semantics of
lazy computations, storage allocation, and efficiency.

@cindex areas
In order to be able to reclaim working space, Prolog allocates most of its
objects in a temporary area, which is reset at the top level.
(An @b[area] is a Lisp Machine construct that gives users some control over
where objects are constructed.)
Care must be taken so that one does not pass
an argument pointing into this area
to a Lisp function that stores such pointers permanently.

LM-Prolog's data structures were introduced in @ref[dtp].
The implementation also introduces certain datatypes for Prolog variables, for
@b[lazy collections]
(see @l[lazy-bag-of] and @l[lazy-set-of]), 
@b[eager collections] 
(see @l[prolog:eager-bag-of] and @l[prolog:eager-set-of]), 
and @b[constrained variables] (see @l[prolog:constrain] and @l[prolog:freeze]).
Lazy and eager collections and constraints are collectively called
@b[special terms].
@cindex lazy collection
@cindex collection, lazy
@cindex eager collection
@cindex collecation, eager
@cindex constrained variable
@cindex variable, constrained
@cindex special term
@cindex term, special

Terms are often perfectly good Lisp objects and are always so
if they are ground (i.e. contain no unbound variables).
Therefore, it is wasteful to call a conversion
routine before passing a ground term from Prolog to a Lisp function.
If the user knows that a certain call to Lisp will only involve
ground arguments, (s)he may specify the control argument @l[:dont-invoke]
(see below) to achieve minimum overhead.
Bound variables inside structures need not require any conversion
since Lisp will follow @b[invisible pointers] to their bindings.
Unbound variables will be passed as symbols, if the control argument
is @l[:copy].
Special terms should not be passed to Lisp as @l[:dont-invoke].

The usual way to call to Lisp from Prolog is with @l[lisp-command], 
@l[lisp-predicate], or @l[lisp-value], documented in @ref[lispi].
They all take an optional extra argument enabling the user to
specify just how careful a conversion is needed for the particular case.
The value of this control argument can be

@description
@kitem :copy
All special terms are invoked, and
the Lisp form is to be copied into @l[working-storage-area]
before evaluation. This could be needed in @l[lisp-command]
if the function called stores its argument somewhere as a side-effect.

@kitem :invoke
Special terms are invoked, but the result
may still point into Prolog's temporary area.
This is often used for printing.

@kitem :query
Each special term encountered
asks the user whether to invoke it or not.  This mode of interfacing
is used e.g. in the Prolog top levels --- they display answers to user queries,
but if the answers contain lazy collections, the user is queried about
how they should be handled.

@kitem :dont-invoke
Lazy collections are not run, eager collections are not waited for,
and constraints are not run.
Arguments are passed directly to Lisp functions without conversion.
In particular, uninstantiated variables will be passed as locatives.
This mode is safe to use if the arguments are known to be ground,
do not contain collections or constraints, and will not be stored anywhere.

@end description

@defpredicate protected-worlds ?worlds
@cindex protected world
@cindex world, protected
This unifies @i[?worlds] with the list of worlds with are @b[protected].
If a predicate is defined which would mask the definition of a predicate in
a protected world, then the user is queried first.
The default value is @l[(:system)] so that a user is queried before
re-defining a system primitive.
@end defpredicate

@defpredicate make-true &rest +predications
This predicate is really an operator upon predications.
Rather than having predicates for changing the @l[circularity-mode],
the @l[option], the current @l[universe], 
the handling of @l[interrupts],
the @l[protected-worlds], and the @l[delayed-value-mode], 
the predicate @l[make-true] is used.
The predication @l[(circularity-mode :handle)], for example, asks ``is the
circularity mode @l[:handle]''.
The predication @l[(make-true (circularity-mode :handle))] always
succeeds and @b[sets] the mode to @l[:handle].
@l[Make-true] also works for @l[lisp-value] if its second argument is a
symbol. 
@end defpredicate
@nopara
For example, the predication @l[(make-true (lisp-value 8 ibase))]
changes the input base to octal.
If the predicator of the @i[+predication] is a dynamic predicate then the
@i[+predication] is asserted.
@l[Make-true] simply succeeds if its @i[+predication] is true to begin
with. 

@defpredicate with +temporarily-true-predication &rest +predications
@setq with section-page
This is an operator which builds upon the @l[make-true] operator.
The conjunction of the @i[+predications] is achieved with the
@i[+temporarily-true-predication] ``made true'' only for the scope of the
@l[with].
@i[+temporarily-true-predication] can be any predication that
@l[make-true] accepts.
@cindex scope
@end defpredicate
@nopara
For example, the trace facility has a problem when printing delayed values.
The default behavior of querying the user would be very annoying.
Clearly the delayed collections should not be run simply because trace happens
to run across it.
A solution is for trace to say @*
@l[(with (delayed-value-mode :dont-invoke) (format ...))] @*
This is equivalent to

@lisp
(and (delayed-value-mode ?current-value)
     (unwind-protect (make-true (delayed-value-mode :dont-invoke))
                     (make-true (delayed-value-mode ?current-value)))
     (format ...)
     (unwind-protect (make-true (delayed-value-mode ?current-value))
                     (make-true (delayed-value-mode :dont-invoke))))
@end lisp

@chapter Debugging Facilities
@setq debug section-page
@section Trace Facility
@setq trace section-page
LM-Prolog has a Lisp-like trace facility.  Any predicate, interpreted or
compiled, can be traced.  Tracing compiled predicates doesn't always
work, however, since some predicates compile in-line, and because 
tail-recursive predicates compile to iterative code.  

LM-Prolog also has a facility for single-stepping the execution of Prolog 
programs, pausing at calls to all predicates except calls from
certain compiled predicates to certain compiled predicates.

The execution of
Prolog programs is in general more complex than that of Lisp because of
the non-deterministic nature of the language.  We introduce therefore the
following terminology.

@cindex port
An invocation of a predication is said to have four @b[ports]. When first
invoked, the @i[trying] port is entered. When a solution is found we exit
through the @i[succeeding] port. Upon backtracking we re-enter through the 
@i[re-trying] port. 
Eventually we fail, leaving through the @i[failing] port.

The ``ports'' terminology is due to Lawrence Byrd [Byrd 1980].

@defpredicate step +predication
The execution of @i[+predication] is single-stepped.
The following step commands are available at every @i[trying] port:

@description
@item C @r[or] @return
continue stepping (CREEP),

@item L @r[or] @linefeed
prove the current goal without stepping (LEAP),

@item S @r[or] @altmode
prove the current goal without stepping or tracing (SKIP),

@item F
cause the current goal to be FALSE,

@item T
cause the current goal to be TRUE,

@item A
give the ANSWER, you will be prompted for a term to unify with
the current goal,

@item B or @breakkey
get a Prolog/Lisp Listener breakpoint.

@end description
@end defpredicate

@defpredicate trace +name-or-names &rest +options
@i[+name-or-names] is either a single predicator or a list of predicators
to be traced.

@i[+options] is zero or more of the following.

@description
@item @l[(:print-if &rest +port-names)]
@mykindex :print-if
the default is all four ports 
(@l[:trying], @l[:succeeding], @l[:re-trying], and @l[:failing]). The predicate
@l[prolog:trace-print-doit] actually prints the traced predication,
and may be redefined by the user.

@item @l[(:when @r(&rest) +patterns)]
@mykindex :when
the tracing/stepping applies only if the predication unifies with at least 
one of the @i[+patterns].

@item @l[:step]
@mykindex :step
enter step mode when the predicate is entered.

@item @l[(:before +predicator)]
@mykindex :before
@i[+predicator] is called on the predication upon entry.

@item @l[(:after +predicator)]
@mykindex :after
@i[+predicator] is called on the predication after entry.

@item @l[(:world +world)]
@mykindex :world
by default traced predicates are added to a world called 
@l[prolog:traced-predicates]. This option allows one to control 
where they will be put.
@windex prolog:traced-predicates
@end description
@end defpredicate

@defpredicate untrace &optional ?predicator
@end defpredicate
@defpredicate untrace-query
The first form untraces one predicator, backtracking if @i[?predicator]
is unbound. If @i[?predicator] is omitted, all predicates are untraced. 
@l[Untrace-query] is selective
i.e. it asks you for each traced predicate whether to untrace it.
@end defpredicate

@defpredicate who-state +label
This predicate sets the ``who-state'' at the bottom of the Lisp machine console
to @i[+label].  Upon backtracking or abnormal return, the original value
is restored.
@end defpredicate

@section Error Handler
It is possible to fall into the Lisp error handler from Prolog.  For
instance, calling undefined predicators causes a Lisp error, unlike some
other Prologs.  
Currently errors can be inspected, given handlers, or corrected interactively
only from Lisp.
A Prolog interface to these facilities is in progress and will be documented
here later.
Currently, the following predicate is provided. See also @l[unwind-protect].

@defpredicate prolog:condition-protect +condition-name +goal &rest +undo-goals
This is logically equivalent to @i[+goal].
If during its execution a @i[condition] named @i[+condition-name] is 
signalled, @i[+goal] is aborted and @i[+undo-goals] are executed instead.
@end defpredicate

@chapter Experimental Facilities
@setq exper section-page
@cindex constrained variable
@cindex variable, constrained
@cindex constraint
LM-Prolog contains facilities which, while still under development
and subject to change, provide an
adventurous user with some powerful extensions to the system.
Until these facilities settle down, the names of the predicates 
in these extensions are in the @l[prolog:] package.
One of the major extensions is the ability to freeze goals so that they are
postponed until more is known.
This facility is good for @b[constraining] variables to satisfy certain
predicates.
Another major extension consists of versions of
@l[set-of] and @l[bag-of] that
compute in independent parallel processes.
Lately, parallel execution schemes for Prolog has attracted great
research interest. Among others, members of the Japanese Fifth Generation
Computers project are investigating this, see e.g. 
[Furukawa @i[et al.@/] 1982].

Also included in this chapter is a brief description of the ``demo'' facility
which can be used to load and run various applications and extensions.

@section Constraints and Freezing Goals
@setq freeze section-page
The standard execution model of Prolog is to always execute predications
in the order as they appear in the program.
As a complement to this, LM-Prolog has the ability to selectively delay
the execution of a predication until enough variables in it are bound.
The facility is defined in the file @l[LMP: EXPERIMENTAL; FREEZE] and is
due to Prolog II [Colmerauer 1982b].
The facility has lots of applications in logic programming, e.g.
to implement sound versions of inequality and negation.
It is used in several of the demo programs (@ref[demfac]) to
implement IO streams, to write ``generate and test'' problems in
a clear yet efficient way, to solve equations, and to compute
with infinite lists.

@defpredicate prolog:constrain ?variable +predication
If @i[?variable] is bound then @i[+predication] is executed.
Otherwise @i[?variable] is constrained to satisfy @i[+predication].
If @i[?variable] is subsequently bound when unifying a predication
with the head of a clause then the @i[+predication]
is executed as if it were the first element of the body of that clause.
Currently, the system behaves as if all constraints were deterministic.
@end defpredicate
@nopara
For example, we can constrain a variable to be greater than 7 with
@l[(prolog:constrain ?x (> ?x 7))].
This constrained variable can be used anywhere.
For example, to remove all negative numbers from a list we can use
@l[remove] (@ref[remove]) as follows.

@lisp
(and (prolog:constrain ?x (< ?x 0))
     (remove ?only-positive ?x ?list))
@end lisp

Another rather different use is to connect a list to a physical output
stream such that elements are printed as they become instantiated.
@setq stream section-page

@lisp
(define-predicate output-stream
  ((output-stream () ?)
   (output-stream (?elt . ?rest) ?lisp-stream)
   (lisp-command (send '?lisp-stream ':tyo '?elt))
   (prolog:constrain ?rest (output-stream ?rest ?lisp-stream))))
@end lisp

Yet another use is to compute an infinite list of the Fibonacci numbers 
in a demand-driven fashion:

@lisp
(define-predicate fib
  ((fib (1 1 . ?rest))
   (prolog:constrain ?rest (fib 1 1 ?rest)))
  ((fib ?i ?j (?k . ?rest))
   (sum ?k ?i ?j)
   (prolog:constrain ?rest (fib ?j ?k ?rest))))
@end lisp

The predication @l[(fib ?r)] will instantiate @l[?r] to an infinite
list whose elements are computed as they are needed.


@defpredicate prolog:freeze ?predication &optional (+unbounds 0)
This predicate postpones the execution of @i[+predication] until
at most @i[+unbounds] distinct variables in it are still unbound.
@end defpredicate

@defpredicate not ?predication
Sound negation.
This is equivalent to @l[(cannot-prove @i(?predication))]
but postpones the execution until @i[?predication] is ground.
@end defpredicate

@defpredicate  ?x ?y
Sound inequality.
This is true if @i[?x] and @i[?y] are terms that do not unify.
This is false if @i[?x] and @i[?y] unify without binding any variables.
Otherwise, it delays.
@end defpredicate

@defpredicate prolog:combine-constraints -union +predications-1 +predications-2
This predicate is called when two constrained variables are unified,
or when a constrained variable is incrementally constrained.
It may compute one of the following values for @i[-union]:
@l[:fail], @l[:invoke], or a list.
If it fails, the combined constraint is
the union of @i[+predications-1] and @i[+predications-2].
If it computes @i[-union] as a list, 
@i[-union] is considered to be
the new constraints for the two variables involved.
If it computes @i[-union] as @l[:fail],
the unification that caused the invocation of @l[prolog:combine-constraints]
fails.
If it computes @i[-union] as @l[:invoke],
the new constraints are not added incrementally but run immediately.
@end defpredicate
@nopara
For example, the following clause simplifies two constraints using >.

@lisp
(define-predicate prolog:combine-constraints
  (:options (:if-old-definition :keep))
  (simplification-of-two-greater-thans @ii[;the clause name]
   (prolog:combine-constraints ((> ?x ?bigger))
                               ((> ?x ?smaller))
			       ((> ?x ?bigger)))
   ( ?bigger ?smaller)))
@end lisp

The following clause causes the unification of two incompatible constraints to
fail. 

@lisp
(define-predicate prolog:combine-constraints
  (:options (:if-old-definition :keep))
  (incompatible-greater-and-less-thans
   (prolog:combine-constraints :fail
                               ((< ?x ?smaller))
			       ((> ?x ?bigger)))
   ( ?bigger ?smaller)))
@end lisp

@setq smart section-page
An example of a problem in Prolog which @l[prolog:freeze] solves is that
arithmetic primitives are not general.
LM-Prolog's @l[sum] for example requires that all but its first argument
(the sum itself) be numbers.
This is because it essentially passes the problem along to Lisp's @l[plus]
which requires that its arguments be numbers.
Using @l[prolog:freeze] we can implement a predicate that if too many 
arguments are unknown simply constrains the variables in those arguments.
The following predicate computes the sum relation for any number of arguments
any of which may be unbound.

@lisp
(define-predicate +
  ((+ . ?args)
   (append ?goal (+) ?args ()) @ii[;Copy out the &rest argument.]
   (prolog:freeze (solve ?goal) 1))) @ii[;Freeze until zero or one unknown.]
@end lisp

@lisp
(define-predicate solve
  ((solve (+ ?sum . ?addends))
   @ii[;split @i(?addends) into numbers and occurrences of @i(X)]
   (vars-and-nonvars ?vars ?nonvars ?addends) 
   (cases ((= () ?vars) @ii[;simply compute @i(?sum) if no variables]
           (lisp-value ?sum (apply '+ '?nonvars)))
          ((not-variable ?sum) @ii[;compute @i(X) if @i(?sum) is known]
           (= ?vars (?var . ?)) 
           (length ?length ?vars)
           (lisp-value ?var
                       (// (- '?sum (float (apply '+ '?nonvars)))
		           ?length)))
          ((variable ?sum) @ii[;Here  @i(X = n*X+Y)]
           (lisp-value 0 (apply '+ '?nonvars)) @ii[;@i(Y) must be 0]
           (rules (?sum)
                  (?vars)
                  ((0))) @ii[;@i(X=0) if @i(n>1)]
           ))))
@end lisp

@section Eager Collections
This experimental facility is for doing parallel processing and
is described in detail in [Kahn 1983a] and is defined in the file
@l[LMP: EXPERIMENTAL; EAGER].

@defpredicate prolog:eager-bag-of ?bag ?term &rest +predications
@setq eager section-page
@cindex eager value
@cindex value, eager
This predicate is logically the same as @l[bag-of] and @l[lazy-bag-of].
Operationally it creates a separate Lisp Machine process to compute the
elements of the @i[?bag].
Unification is extended so that if a non-variable term is unified with
an @b[eager value] the unification waits for it to complete.
Eager bags are eager values that either become @l[()] or a cons of an
instantiation of @i[?term] and a new eager value.
@end defpredicate
@nopara
The @l[same-fringe] predicate, for example, defined under the
description of @l[lazy-bag-of] could be modified to explore the two
trees in parallel by replacing @l[lazy-bag-of] with @l[prolog:eager-bag-of].
As soon as a difference is detected the processes will automatically
be terminated.

Eager values were inspired by the ``futures'' of Act 1 [Lieberman 1981].

@defpredicate prolog:eager-set-of ?bag ?term &rest +predications
This is the same as @l[prolog:eager-bag-of] described above except 
duplicates are eliminated from @i[?bag].
@end defpredicate

@defpredicate prolog:faster ?term-1 ?term-2
If @i[?term-1] is anything other than an eager value this predicate
succeeds.
If it is an eager value and @i[?term-2] is not then it fails.
If both are eager it waits for one of them to become a non-eager value.
@end defpredicate
@nopara
Using @l[faster] and @l[lazy-bag-of] one can define a parallel version of
@l[or] as follows.

@lisp
(define-predicate parallel-or
  ((parallel-or ?goal-1) ?goal-1)
  ((parallel-or ?goal-1 ?goal-2)
   (eager-bag-of ?bag-1 ?goal-1 ?goal-1)
   (eager-bag-of ?bag-2 ?goal-2 ?goal-2)
   (cases ((faster ?bag-1 ?bag-2)
           (alternate ?goal-1 ?bag-1 ?goal-2 ?bag-2))
          ((alternate ?goal-2 ?bag-2 ?goal-1 ?bag-1))))
  ((parallel-or ?goal-1 ?goal-2 ?goal-3 . ?more-goals)
   (parallel-or (parallel-or ?goal-1 ?goal-2)
                (parallel-or ?goal-3 . ?more-goals))))
@end lisp

@lisp
(define-predicate alternate 
  ((alternate ?goal-1 (?goal-1-instantiated . ?bag-left-1)
              ?goal-2 ?bag-2)
   (or (= ?goal-1 ?goal-1-instantiated)
       (cases ((faster ?bag-2 ?bag-left-1)
               (alternate ?goal-2 ?bag-2 ?goal-1 ?bag-left-1))
              ((alternate ?goal-1 ?bag-left-1 ?goal-2 ?bag-2)))))
  ((alternate ? () ?goal-2 ?bag-2)
   (member ?goal-2 ?bag-2)))
@end lisp

@defpredicate interrupts ?on-or-off
If interrupts are allowed then @i[?on-or-off] is @l[:on] otherwise its
@l[:off].
@l[Make-true] and @l[with] work with this so that if one wants a goal to
be executed as an atomic unit then this can be expressed as
@l[(with (interrupts :off) ...)].
@end defpredicate

@section Mutable Arrays
@subsection Introduction
LM-Prolog provides a completely logical interface to the arrays of ZetaLisp,
defined in the file @l[LMP: EXPERIMENTAL; ARRAY].
A mutable array is, just like a ZetaLisp array,
a (possibly very large) data structure with direct access to its elements.
However, mutable arrays are logical objects and so are not amenable to
destructive updates. LM-Prolog instead provides updating predicates which
are not destructive, but creates a new virtual array while
keeping the old.  As much storage as possible is shared between the old and
the new virtual array, in particular they both point to the same ZetaLisp
array which normally reflects the new virtual array.
The old virtual array normally keeps a record of the difference between it
and the new virtual array.

The implementation is optimized so that in the best case array references and
updates are nearly as efficient as using them directly in ZetaLisp.
More details on mutable arrays can be found in [Eriksson and Rayner 1984].

@subsection Array Predicates
@defpredicate prolog:is ?array ?array-description
This is true if @i[?array] satisfies the @i[?array-description].
Can be used to create arrays or to determine their properties.
An array description is a cons of @l[:array] and a list of keywords
paired with their values as follows:

@description
@item @l[(:dimensions . @i(list--of--integers))]
@mykindex :dimensions
Obligatory list of dimensions (ZetaLisp supports up to 7 dimensions).

@item @l[(:type @i(type))]
@mykindex :type
Possible types are
@l[:normal, :1-bit, :2-bit, :4-bit, :8-bit, :16-bit, :string]
and @l[:fat-string].
Default is @l[:normal].
The other types are more efficient if the vast majority of values fit the
description.

@item @l[(:initial-value @i(value))]
@mykindex :initial-value
If an initial value is not given then each element becomes an independent
logical variable.
If the array is not @l[:normal] then the default initial value is 0.

@item @l[(:usage . @i(list--of--declarations))]
@mykindex :usage
The @i[list--of--declarations] may contain the flags 
@l[:deterministic], @l[:recent-only], and @l[:check].  
Or it may contain only the flag @l[:lisp-like].

@end description

@description
@kitem :deterministic
declares that old versions of the array
will never be backtracked to i.e. will never be used by alternative
computations,

@kitem :recent-only
declares that old versions of arrays are never 
referenced in the current computation,

@kitem :check
tells the system to signal an error if either of the above 
declarations are violated,

@kitem :lisp-like
means that the array will be used 
@l[:deterministic], @l[:recent-only],
and that indices are always ground and if the @l[:type] is not 
@l[:normal] that all the values will fit.

@end description

These @l[:usage] declarations can significantly improve the efficiency of 
programs using arrays.
@end defpredicate
@nopara
For example, the predication

@lisp
(is ?a (:array (:dimensions 10) (:initial-value 0)
               (:usage :recent-only :deterministic)))
@end lisp

unifies @l[?a] with a one-dimensional array 10 long, initialized to
0. It will be updated destructively, since old versions of it
are not going to be referenced neither by any subcomputations 
(@l[:recent-only]) nor by alternative computations (@l[:deterministic]).

@defpredicate prolog:array-element ?value +array &rest ?indices
The element of @i[+array] described by @i[?indices] is unified with
@i[?value].
If @i[?indices] contain variables then the predicate will search for
elements who unify with @i[?value].
This fails if the @i[?indices] are out of the range of the
@l[:dimensions] of the @i[?array].
@end defpredicate
@nopara
For example, the predication @l[(array-element 7 ?a 6)]
unifies the 6th element of @l[?a] with 7.

@defpredicate prolog:array-difference +old-array ?new-array (?new-value . ?indices)
This unifies @i[?new-array] with a new virtual array
which differs from @i[+old-array]
in that the element indicated by @i[?indices] is replaced by
@i[?new-value].

@end defpredicate
@nopara
For example, the predication @l[(array-difference ?a ?a-1 (not-x 6))]
creates a new virtual array @l[?a-1] which is equal to @l[?a] except
for its 6th element which has been changed to @l[not-x].

@defpredicate prolog:array-difference-old-real +old-array ?new-array (?new-value . ?indices)
This is equivalent to @l[array-difference]
but is more efficient if one expects to use @i[+old-array] more often than
@i[?new-array]. Otherwise use @l[array-difference].
@end defpredicate

@subsection Unification
Two mutable arrays unify if and only if they have the same @l[:type]
and the same @l[:dimensions] and their elements unify pairwise.

@section The Demo Facility
@setq demfac section-page
@defpredicate demos
The predication @l[(demos)] will put up a menu of several self-documenting
demos. 

@end defpredicate
@nopara
Currently, the list includes

@description
@item Peano arithmetic.
@cindex Peano arithmetic,
Predicates are defined for doing addition, 
multiplication, factorial, and the like of natural numbers.
Some of these predicates are presented in @ref[peano].

@item Ask about.
@cindex Ask about.
A predicate called @l[ask-about] is loaded which when 
applied to
a predicator defines that predicator so that it queries the user when it is
called unless the user has already answered the query.

@item Backtracking Turtle.
@cindex Backtracking Turtle.
A Logo-like turtle [Lieberman 1980]
is interfaced so that it reacts to a stream of commands
such as @l[(:forward 100.)], @l[(:right 90)], etc.
The commands are executed as elements of the stream become instantiated
and upon backtracking undo whatever graphics they performed.
This facility builds upon constraints (see @ref[stream], where a
stream programming example appears).

@item Grammar Kit.
@cindex Grammar Kit.
A facility for defining definite clause grammars 
[Pereira and Warren 1980]
and a small sample grammar.  This uses the ``ask about'' and
``backtracking turtle'' features.  It optionally provides a backtracking
graphical trace of its execution.  This kit is described in detail in
@ref[gram] and in [Kahn 1983b].

@item Alternative Top Levels.
@cindex Alternative Top Levels.
These alternative Prolog top levels are described in @ref[toplevel].

@item Eager Collections and some examples.
@cindex Eager Collections.
These parallel processing versions of 
@l[bag-of] and @l[set-of] are described in @ref[eager].

@item Constraints and some examples.
@cindex Constraints.
This control extension of Prolog is described 
in @ref[freeze].

@item Prime Numbers.
@cindex Prime Numbers.
A list of all prime numbers is generated with either
lazy or eager bags.  The sieve of Eratosthenes is modeled by infinite
bags and infinite operations on those bags.

@item Eight Queens.
@cindex Eight Queens.
A program to solve the puzzle of how one can place 8 queens on 
a chess board so that none can capture another. The solution uses constraints.
It optionally displays its states while running, using a similar stream-based
technique as in the Backtracking Turtle.

@item Knights Tour.
@cindex Knights Tour.
A program to solve the puzzle of how a knight can traverse a
chess board so that each square is visited exactly once.  It backtracks to
find more solutions and displays its states.

@item Cryptarithmetics.
@cindex Cryptarithmetics.
A program to solve the SEND + MORE = MONEY puzzle
where each letter stands for a unique digit.  It is written in terms of
constraints and optionally displays its states while running.

@item Concurrent Prolog with Bagel Simulator.
@cindex Concurrent Prolog.
@cindex Bagel Simulator.
An interpreter for the language
Concurrent Prolog [Shapiro 1983a, 1983b] is defined and several
example programs are run.
The allocation of processes on a virtual doubly twisted torus (a ``bagel'')
is displayed.

@item Benchmarks.
@cindex Benchmarks.
This runs LM-Prolog on a series of published benchmarks and
prints out the cpu and paging times involved.

@end description

@chapter Top Levels
@setq toplevel section-page

@section Editing
Normally, definitions of predicates are typed into Zwei buffers.
The normal mode for the buffers is @l[Lisp].
Predicate definitions can be intermixed with @l[defun]s, @l[defprop]s, 
or any other Lisp forms that you want to have in the same file.  
Prolog predications can be included if the predicator uses the
@l[:lisp-macro-name] @l[define-predicate] option.
Definitions can be compiled or evaluated in Zwei, 
@l[qc-file]d, @l[compile-file]d, or @l[load]ed, just as Lisp code.
The commands @meta[.] (edit definition),
@csh[A] (display argument list), and @csh[D] (show documentation) 
work for Prolog predicates as well as Lisp objects.
The @romanii button makes Zwei ``prefer'' Prolog.  The @romani button
makes it ``prefer'' Lisp.

@section The ``Normal'' Top Level
The ``Lisp listeners'' of the Lisp Machine have been modified to be
``Prolog/Lisp Listeners''.
The keys @romani, @romanii, and @romaniii are used to indicate
which system one wishes to converse with.
(For keyboards without Roman numerals these are changed as described in
Appendix III.)
When talking to LM-Prolog one simply types in a predication.
The system will respond either with ``No answer'' or ``OK'' followed by the
bindings of any of the variables of the predications.
The bindings of anonymous variables are not shown.
See the sample interaction in @ref[king].

In a Prolog/Lisp Listener the following keys have special meaning.

@description
@item @romani
makes the window expect Lisp forms to evaluate.
This also changes the window's label if necessary.

@item @romanii
makes the window expect LM-Prolog queries to answer.
This also changes the window's label if necessary.

@item @romaniii
switches between @romani and @romanii modes
and changes the window's label.

@item @handdown
``rejects'' the latest answer from LM-Prolog,
i.e. tries to find another one.
It either prints ``No more answers'' or ``OK'' and the bindings.

@item @handup
@setq handup section-page
``accepts'' the latest answer,
i.e. enters a recursive prolog with top-level
variable bindings intact.

@item @ctrl[@handdown]
``rejects'' the last prolog entered recursively by @handup.

@item @help
is extended in the rubout handler to print out the above in
addition to its normal print out.

@end description

These extensions also apply to Lisp breaks but not to the debugger's listener.

@section Alternative Top Levels
Unlike Lisp for which there is wide-spread agreement that the top level should
be a ``read-eval-print'' loop there is less agreement about Prolog top levels.
The default LM-Prolog top level checks first if the predicate
@l[top-level-predication] is defined and if so passes the problem on to it.
This predicate should then interpret the query and print out results.
If the query is non-deterministic then upon rejection (via @handdown)
it will be re-entered.
Several such top levels are pre-defined in LM-Prolog and to use them one just
adds the world they live in to the universe (using @l[add-world]).
They can also be selected using the @l[demos] predicate.

@deftoplevel :unique-answers-top-level
This top level differs only in that the same set of bindings is never printed
more than once even if there are redundant ways of achieving it.
@end deftoplevel
@nopara
For example, the predication
@l[(member ?x (a a b))] will display 
the binding @t[?X = A] and if that is rejected it will display @t[?X = B].

This top level could be implemented as follows.

@lisp
(define-predicate :top-level-predication
 (:options (:world :unique-answers-top-level))
 ((:top-level-predication ?predication)
   (variables ?variables ?predication)
   (variable-names ?variable-names ?predication)
   (lazy-set-of ?answers ?variables ?predication)
   (or (= ?answers (? . ?)) (and (format t "~&No answer") (false)))
   (or (and ?predication
            (format t "~&OK")
            (member ?variables ?answers)
            (print-bindings ?variable-names ?variables))
       (and (format t "~&No more answers") (false)))))
@end lisp

@deftoplevel :lazy-set-top-level
This top level expects a query of the form @l[(?term . ?predications)] and
it prints out all the unique instantiations of @l[?term] for the proofs of
the conjunction of the @l[?predications].
@end deftoplevel
@nopara
For example, the query @l[(?l . (factorial ?l ?))] means
``what is the set of all @l[?l] such that @l[?l] is a factorial?'' 
and the answer will continue to be
printed until one hits @ctrl[@abort].

@deftoplevel :compute-ahead-top-level
This top level depends upon the experimental parallelism facilities described
in @ref[eager].
The idea is that in response to a top-level query the system creates an
independent process to compute all the solutions.
As soon as one solution is ready it is displayed and while the user inspects
the results more solutions are being sought.
If a new query is given then the old process is killed.
@end deftoplevel

@deftoplevel :parallel-prolog-top-level
This top level is very experimental and uses the experimental parallelism
facilities described in @ref[eager].
The query is solved by exploring all alternatives in parallel and by creating
separate processes for each predication in a conjunction.
@end deftoplevel
@nopara
This is useful for experimentation with parallelism but there has been little
attempt to bring this facility up to ``production'' standards.

@chapter Dec-10 Prolog Compatibility Package
@section Introduction

This chapter describes a translation package from @DECsystemX Prolog
[Pereira @i[et al.@/] 1979] and its near copies to LM-Prolog. 
This is provided for people who have Prolog programs on some
machine and want to move them to a Lisp Machine.

The main part of the package consists of a translator program that accepts 
@DECsystemX Prolog
files as input and produces files in LM-Prolog format.  The translator
does the obvious syntactic translations, and as many semantic translations
as it can, mainly changing names of predicates.  A minor part of the package
consists of some predicates provided for compatibility.

To get around the problem of parsing @DECsystemX Prolog, the translator program
is itself written in @DECsystemX Prolog.  
``:-op'' declarations are handled. 
Variable names are kept (prefixed by ?'s) if the files are in ``LC'' mode.
``:-mode'' declarations are handled by becoming @l[:argument-list]s.
Other declarations are ignored, and comments are unfortunately lost.

The package is distributed as the logical directory @l[LMP: COMPATIBILITY;].
It is intended for
running under TOPS-20 but it should be easy to adapt it for other systems.
Further documentation can be found in files on that subdirectory.

@section Semantic Translations

Due to the differing sets of available datatypes in LM-Prolog and @DECsystemX 
Prolog, all translations cannot be guaranteed to be done correctly. For
instance, @DECsystemX Prolog does not have symbols nor strings.
(A Prolog symbol is indistinguishable from a predication of no arguments.
A string is represented as a list of character codes.)

LM-Prolog does not make a distinction between lists and constructions or
function applications. For example, @l[(f a)] in LM-Prolog corresponds
to both @l[f(a)] and @l([f,a]) in @DECsystemX Prolog.
The `=..' predicate is equivalent to `=' in LM-Prolog.  The translator
issues warnings for translations that are not straight forward.
It also attempts to detect what are terms and what are
predications. The translations listed in Appendix B are performed
on predications.

@section Compatibility Predicates
The predicates documented herein are defined in
@l[LMP: COMPATIBILITY; COMPATIBILITY]. 

@defpredicate quantified-bag-of ?bag +quantified ?term &rest +predications
@i[+Quantified] should be a list of variables that are instantiated to some 
values such that @i[+predications] hold, and @i[?bag] is the bag of all
instantiations of @i[?term] such that @i[+predications] still hold.
I.e. this predicate can backtrack to find new values of @i[+quantified]
and @i[?bag].  All values of @i[?bag] are non-empty lists.

@end defpredicate
@nopara
Consider for example the database

@lisp
(define-predicate likes
  ((likes dick beer))
  ((likes harry beer))
  ((likes tom beer))
  ((likes bill cider))
  ((likes jan cider))
  ((likes tom cider)))
@end lisp

@nopara and the conversation

@lisp
(quantified-bag-of ?bag (?beverage) ?who (likes ?who ?beverage))
OK @ii[;LM-Prolog replies in the affirmative]
?BAG = (DICK HARRY TOM)
?BEVERAGE = BEER
OK @ii[;@handdown to get the next possibility]
?BAG = (BILL JAN TOM)
?BEVERAGE = CIDER
@sp 1
(quantified-bag-of ?bag () ?who (likes ?who ?beverage))
OK
?BAG = (DICK HARRY TOM BILL JAN TOM)
@end lisp

@defpredicate quantified-set-of ?set +quantified ?term &rest +predications
This is just as the previous one but copies are suppressed in @i[?set] and
@i[?set] is in the standard order as defined below.
@end defpredicate

@defpredicate repeat &optional +n
@l[Repeat] succeeds @i[+n] times. If @i[+n] isn't given, it succeeds
forever.
@end defpredicate
@nopara
It could be defined by

@lisp
(define-predicate repeat
  ((repeat) (or (true) (repeat)))
  ((repeat ?n) ( ?n 0) (sum ?n-1 ?n -1) (or (true) (repeat ?n-1))))
@end lisp

@defpredicate exploden ?integers ?symbol
This predicate is true if the list @i[?integers] contains the ASCII
codes for the characters in the print name of @i[?symbol].
At least one of its arguments should be bound.
@end defpredicate
@nopara
This is equivalent to @DECsystemX Prolog's @l[name] predicate.

@defpredicate asserta +clause
@end defpredicate
@defpredicate assertz +clause
These predicates are like @l[assert] with the additional control that
the asserted clause is stored first or last, respectively, in its
definition.
@end defpredicate

@subsection Comparison of Terms
LM-Prolog has a standard total ordering of terms, which is defined as follows:
First come variables, ordered ``oldest first''. Then come other terms,
ordered first alphabetically by datatype name defined by @l[lisp-type].
Within datatypes, the following rules apply:
Conses are ordered by their two arguments.
Numbers are ordered by standard arithmetic relations.
Strings and symbols are ordered alphabetically by their printnames.

@defpredicate standard-order ?term1 ?term2
@setq stord section-page
This holds if @i[?term1] is not after @i[?term2] in the standard order.
@end defpredicate

@defpredicate compare ?op ?term1 ?term2
This succeeds if the result of comparing @i[?term1] with @i[?term2]
is @i[?op], where @i[?op] is:@*
@sp 1
=, if @l[(identical @i(?term1) @i(?term2))] holds,@*
<, if @i[?term1] is before @i[?term2] in the standard order,@*
>, if @i[?term1] is after @i[?term2] in the standard order.
@end defpredicate

@subsection Grammar Rules
@setq gram section-page
There has been much work within the Prolog community on devising grammars that
translate straight-forwardly into Prolog programs (Pereira and Warren, 1980).
The LM-Prolog file for defining definite clause grammars has the logical
pathname @l[LMP: LIBRARY; GRAMMAR].
It can also be loaded by executing @l[(demos)] and mousing
@mouseditem[Grammar Kit].
The grammar kit contains a predicate called  which transforms its
arguments into an ordinary Prolog clause and adds it to the database:

@defpredicate  non-terminal &rest constituents
This asserts the grammar rule that the predication @i(non-terminal)
may be built up from the @i(constituents).
Behind the scenes, LM-Prolog adds four implicit arguments to the 
@i(non-terminal), as explained below,  and adds the transformed rule
as a clause.
The way each @i(constituent) is treated depends on its syntax:
@description
@item[(call @i(predication))]
is simply transformed into just @i(predication),

@item[(is-word @i(word) @i(category))]
is transformed into a test that the next terminal symbol is of
the correct @i(category),

@item[(terminal @i(word))]
is transformed into a test that the next terminal symbol is @i(word),

@item[@i(nonterminal)]
Anything else is transformed into a call to a grammar relation.
@end description
@end defpredicate

Consider the following definitions of
the rule that a verb phrase can consist of a verb followed by a
noun phrase, first with, then without, .

@lisp
(--> (verb-phrase (vp ?verb ?np))
     (verb ?verb)
     (noun-phrase ?np))
@end lisp

In @DECsystemX Prolog, the above rule would,
modulo Prolog syntax and placement of arguments,
translate into a clause
extending the @l[verb-phrase] predicate which is a relation between
a tree structure and a part of a list of words:

@lisp
(assert ((verb-phrase ?words0 ?words (vp ?v ?np))
         (verb ?words0 ?words1 ?v)
         (noun-phrase ?words1 ?words ?np)))
@end lisp

Our grammar predicates are actually relations between
tree structures, parts of a list of words,
and parts of lists of graphics commands.
The graphics commands can be fed into the Backtracking Turtle program.
Our  predicate translates the above rule into the following:

@lisp
(assert
 ((verb-phrase ?words0 ?words
               ((:here ?x ?y ?) (:place-turtle ?x ?y 240.0) . ?coms0) ?coms
               (vp ?v ?np))
  (display-constituent ?coms0 ?coms1 verb)
  (verb ?words0 ?words1
        ?coms1 ((:place-turtle ?x ?y 120.0) . ?coms2)
        ?v)
  (display-constituent ?coms2 ?coms3 verb)
  (noun-phrase ?words1 ?words ?coms3 ?coms ?np)))
@end lisp

@nopara
where the predicate @l[display-constituent] is responsible for generating
graphics commands for displaying a constituent.

@chapter User Extensibility of the System
@setq exten section-page
The predicate @l[lisp-value] is nearly always adequate for user extensions
to the system.
Such extensions require only a knowledge of ZetaLisp.
Occasionally a control extension is desired.

@cindex intrinsic compilation
@cindex compilation, intrinsic
The supported way of extending the compiler is by using @b[intrinsic] compile
methods.  Whenever the compiler encounters predications for a predicate with
an intrinsic compile method, it will simply call 
the corresponding function whose responsibility it is to emit suitable code.

It should accept the following arguments:

@description
@item @i[cont1]
will contain compiled code for the remainder of the conjunction
in which the current predication occurs,

@item @i[cont2]
is only needed for the implementation of @l[cut].

the rest of the arguments should be the arguments of the predicate itself.
At compile time, these are terms which look just like the Lisp form
of the source representation except for variables which are represented
by locatives.

@end description

The intrinsic function should return two values: 
@enumerate
@item @i[cont1] augmented with code for the predication being compiled.
If the predicate corresponding to the intrinsic function
is deterministic, you could return @l[`(and ,code-for-this ,@i(cont1))].
If the predicate is to be non-deterministic, you will need a deeper 
understanding of the implementation. Loosely speaking, @i[cont1] will
have to be transformed to a continuation to be passed to the code for the
predication being compiled by the intrinsic function.

@item Just return @i[cont2]. There is only one intrinsic function that breaks
this convention: the one for @l[cut].
@end enumerate

@l[Lisp-predicate], @l[and], and @l[or] have 
intrinsic compile-methods, for instance.
@l[Define-predicate] takes special action for definitions with
intrinsic compile-methods, so that calls from within the same file will be
compiled correctly both with editor commands and with @l[compile] or
@l[qc-file].

For an example of a non-deterministic predicate with an intrinsic compile
method, consult the source code for @l[cases].
@l[Lisp-value] is an example of a deterministic predicate with an intrinsic
compile method. Its definition follows.

@lisp
(define-predicate lisp-value
  (:options (:compile-method :intrinsic compile-lisp-value)
            (:deterministic :always))
  @ii[;The clauses are needed so that @l(lisp-value) can be called directly]
  ((lisp-value ?value ?form) (lisp-value ?value ?form))
  ((lisp-value ?value ?form ?mode) (lisp-value ?value ?form ?mode)))
@end lisp

@lisp
(defun compile-lisp-value (cont1 cont2 value form &optional mode)
  (values `(and (%unify-term-with-term ,(constructor value t)
                                       ,(compile-lisp-form form mode))
                ,cont1)
          cont2))
@end lisp

The system is designed to allow modular definitions of new data types
as Lisp Machine flavors.
This requires however, a good understanding of the implementation.
Illustrative examples can be found in the implementation of constraints
(see the file @l[LMP: EXPERIMENTAL; FREEZE]) and eager values
(see the file @l[LMP: EXPERIMENTAL; EAGER]).

@chapter Performance Considerations
@section LIPS Speed

@cindex benchmarks
@cindex LIPS speed
The file @l[LMP: LIBRARY; BENCHMARKS] contains some benchmark programs
that were published in [Warren 1977].  The programs are @l[reverse-30], a
naive @i[O(n@+(2))] reverse of a list 30 long; @l[qsort-50], 
a quicksort of a list 50 long; 
four differentiations; a palindrome of a list 25 long;
and a database query similar to the one described in @ref[dbquery].
The table below shows the timings in milliseconds
for compiled (LM-C) and interpreted (LM-I) predicates on a CADR or LM-2,
and for DECsystem-10 Prolog on a KI10 (10-C and 10-I).
The LM-Prolog times are followed in parentheses by the timings without
micro-code support.
Note that the hardware
of a KI10 is much faster than that of a CADR.

The first benchmark involves 498 inferences,
suggesting a LIPS rate of around 12000 for compiled code and
2000 for interpreted. 

@settabs 5 @columns
@sp 1
@<@\@hfill LM-C@\@hfill LM-I@\@hfill 10-C@\@hfill 10-I@\@cr
@sp 1
@<reverse-30@\@hfill 43(134)@\@hfill 250(1170)@\@hfill 53.7@\@hfill 1160@\@cr
@<qsort-50@\@hfill 56(197)@\@hfill 644(2380)@\@hfill 75.0@\@hfill 1344@\@cr
@<d-times-10@\@hfill 7(16)@\@hfill 36(110)@\@hfill 3.0@\@hfill 76.2@\@cr
@<d-divide-10@\@hfill 8(18)@\@hfill 38(126)@\@hfill 2.9@\@hfill 84.4@\@cr
@<d-log-10@\@hfill 5(12)@\@hfill 21(77)@\@hfill 1.9@\@hfill 49.2@\@cr
@<d-op-10@\@hfill 5(12)@\@hfill 26(83)@\@hfill 2.2@\@hfill 63.7@\@cr
@<palin-25@\@hfill 37(167)@\@hfill 294(1250)@\@hfill 40.2@\@hfill 602@\@cr
@<query@\@hfill 404(1746)@\@hfill 1780(5858)@\@hfill 185.0@\@hfill 8888@\@cr

@section Costs of Various Features

In building large systems in LM-Prolog a user should be aware of what
various features cost so that they can be used in a rational way.
The following is a list of features and their costs.

@description
@item Assert.
Adding clauses to the interpretive definition of a predicate
takes about .02 seconds per clause depending on the complexity of the clauses.
Adding clauses to compiled definitions is the same, however, the real
cost of the assert is the first time the clause is used.
It is then that it is translated into Lisp and compiled into machine language.

@item Retract.
@setq retract section-page
Little effort has been put in to making clause retraction happen quickly.
A simple retraction takes about .01 seconds.

@item Occur check and circularity handling.
Putting on the occur check will typically slow down
interpretive LM-Prolog by about 30%   and compiled code by about 65%.
A circularity mode of @l[:handle] slows down the interpreter and compiled
code by 1% to 2%.

@item Lazy collections.
The cost of using lazy bags and sets depends very much on how they are used and
the size of the terms involved.
If the first argument is given, then several optimizations are performed.
For example, the predication @l[(cannot-prove ?predication)]
compiles equally
well if it is defined as @l[(lazy-bag-of () ? ?predication)]
or it is defined in terms of @l[cut].
In general, however, a lazy collection requires its own @b[trail] for
@cindex trail
backtracking.
In some cases it will need to run in its own @b[stack group].
@cindex stack group
All but the first argument may need to be copied.

@item Multiple worlds.
The system caches its search for the definition of a predicator in a universe.
If the universe is not changed then the overhead is minimal.
The cost of frequently changing the universe depends upon how many worlds are
in the universe and how often predicate definitions can be found in the first
few worlds.

@item Open compilation of predicates.
The speedup gained by open compilation is important if the open-coded
predicate is a meta-level predicate. Its arguments are then predications,
and with closed compilation, the compiler would compile them as terms
which is almost equivalent to letting them be interpreted at run time.
@cindex object-level predicate
@cindex predicate, object level
If the open-coded predicate is an ordinary @b[object-level] predicate,
the gain in speed corresponds to a couple of function calls and is
usually of minor importance, unless it is very heavily used.  One case 
where open-coding can be worthwhile
is when the predicate is an alias for another predicate, e.g. with a different
order of its arguments.
Open coding can of course lead to increases in the size of the compiled code.

@item Garbage Collection.
The system does all its temporary consing in temporary areas which it resets
when it is sure that nothing can point inside them.
(See the description of @l[delayed-value-mode] in @ref[dvm].)
Definitions are kept in their own area which is the value of the Lisp variable 
@l[prolog:*structure-area*].
If a program retracts or
re-defines many clauses then the Lisp Machine's garbage collector should be
enabled to re-claim that storage.

@item Non determinacy.
Prolog's inherent non-determinacy occasionally causes the stack to grow very
large.  In most Prolog programs, however, the non-determinacy is just
artificial and the program is really deterministic.
If this is the case, then the problem of stack growth is easily cured by
declaring predicates deterministic and/or using @l[cut].
Declaring a predicate @i[P] deterministic ensures that the stack depth at
@i[P]'s call ``port'' equals the stack depth at @i[P]'s exit ``port''.
This is not the case for general predicates.
The compiler and the interpreter both capitalize on such declarations.
Using @l[cut] immediately before tail-recursive calls in @i[P] ensures that 
the stack does not grow at all when @i[P] recurses. Note that @l[cut]
has no declarative semantics, but can be used (with care) for cutting out 
unwanted deduction paths and for preventing excessive stack growth.

@end description

@section Time And Meter Predicates

@defpredicate time-and-print +predication
This satisfies @i[+predication] and prints out timing information 
when a proof is found.
It  backtracks to find the next proof of @i[+predication], and finally to print
out timings of its eventual failure. 
@end defpredicate
@nopara
E.g. if @i[+predication] succeeds @i[n] times,
@l[time-and-print] succeeds @i[n+1] times.

@defpredicate time (?cpu ?disk) +predication
This predicate unifies @i[?cpu] and @i[?disk] with the cpu and disk
time consumption for finding a proof of @i[+predication].  It backtracks in the
same way as @l[time-and-print].  @i[?Cpu] and @i[?disk] will not
contain accumulated values but just the time to find the first proof, the
next proof, or to ultimately fail.
@end defpredicate
@nopara
Occasionally, @i[?cpu] will be a negative number.  This is because the 
accuracy of metering disk time consumption is rather poor and influences the
computation of cpu time consumption. It may also happen that the machine's
microsecond clock wraps around.

@defpredicate meter +predication
This predicate satisfies @i[+predication] with metering switched on.
A meter
analysis is written into Zwei buffer @l[Meter Information].  Again, this
predicate backtracks to meter the next solution or ultimate failure.
@end defpredicate
@nopara
The Lisp Machine's metering facility seems somewhat fragile.
It is recommended that one meter only computations that take a second or less.

@include MANUAL-TRANSLATIONS
@include MANUAL-COMPILATIONS
@include MANUAL-KEYBOARD
@include MANUAL-REFERENCES

@unnumbered Concept Index
@printindex cp
@unnumbered Function Index
@printindex fn
@unnumbered Keyword Index
@printindex kw
@unnumbered World Index
@printindex wo
@unnumbered Predicate Index
@printindex pr

@contents
@bye