ToC DocOverview CGDoc RelNotes Index PermutedIndex
Allegro CL version 8.1
Unrevised from 8.0 to 8.1

Allegro Prolog

Release 0.98b

Release 0.98b of Allegro Prolog continues a sequence of minor bugfix releases from 0.98, but 0.98 and its accompanying documentation have significant changes and enhancements from earlier releases.

The prolog module can be loaded with (require :prolog). Symbols are exported from the prolog package. If you intend to use Prolog interactively you will probably find it convenient to execute (use-package :prolog) also.

It happens that both the prolog and cg packages export a symbol named == which will signal a package conflict if there is an attempt to use both packages. This will happen, for instance, if you try to use the prolog package in the cg-user package without first shadowing one or the other symbol. Usually you want == to refer to prolog:==. You will get that if you load the prolog module and evaluate (shadowing-import '(prolog:==)) and then (use-package :prolog).

User Documentation

This document is not intended as an introduction to programming in Prolog. It assumes some programming knowledge of both Prolog and Common Lisp.

Allegro Prolog is an implementation of Prolog in Common Lisp. It is based on the implementation developed by Peter Norvig in Paradigms of Artificial Intelligence Programming. The code has been further optimized and useful extensions provided, making an industrial-strength Prolog programming environment with a flexible calling interface in both directions between Common Lisp and Prolog.

Prolog functors are translated to compiled Common Lisp functions. A single Lisp function combines all rules for each distinct functor/arity. Special treatment is given for facts, that is, rules with no variables in the head and no clauses in the body. The Lisp function automatically captures these as data instead of code. This allows reasonably large collections of data to be specified as regular Prolog rules. Larger, highly-scalable data sets can be implemented by extensions outlined below.

Allegro Prolog does not intend to be an ISO-compliant Prolog, nor does it implement the entire Prolog language. Its purpose is to provide Prolog logic programming as an integrated extension to Common Lisp for use in Lisp programs, not as a separate language. Many standard Prolog arithmetic, predicate operators, and I/O operators are not implemented, as they are a subset of the standard Common Lisp operators available using lisp/2. There is also no support for operator syntax (e.g. infix notation), as input notation is subsumed by sexpr syntax. These choices may be reconsidered in the future if there is reason to if there is motivation to make Allegro Prolog a self-standing Prolog implementation. What is provided is the basic Prolog engine for logic programming.

Prolog source files may be loaded either compiled or interpreted, as Prolog functors are automatically compiled upon first use. But since Allegro Prolog programs will typically contain both Lisp and Prolog code intermixed, it is generally a good idea to compile the files so that the Lisp code is compiled.

All public symbols are exported from the prolog package. The definitions mostly follow Norvig. Lisp S-expression syntax is used rather than Edinburgh syntax, although support for Edinburgh input may be provided in the future. Prolog variables are Lisp symbols that have names that begin with the `?' character. The anonymous variable is the symbol `?' (that is, `prolog:?'). Some symbols exported from the prolog package are eq to symbols exported from the common-lisp package, but there is never any ambiguity between use of a Prolog name and a Lisp name. There is no implementation of the Prolog module system. Programmers should be aware that there is a danger of collision with inherited symbols. For example, the symbol cl:list is not defined by Prolog but would typically be inherited from the common-lisp package by an application package. An attempt to make a Lisp function definition on cl:list would be prevented by package locking, but definition as a Prolog functor is not protected. If multiple application packages attempt to make such definitions, they would collide on the inherited symbol.

Allegro Prolog has no known dependencies on 8-bit vs. 16-bit character images or on ANSI vs. Modern mode images.

Built-in Prolog Functors

The following Prolog functors are predefined in Allegro Prolog and generally implement the standard Prolog functionality. The set of defined functors may be extended in the future. A few functors in this implementation accept varying arity and are indicated with a *, as in or/*.

=/2   ==/2   abolish/2   and/*   append/3   arg/3   assert/1   asserta/1   assertz/1   atom/1   atomic/1   bagof/3   call/1   consult/1   copy-term/2   erase/1   fail/0   first/1   functor/3   ground/1   if/2   if/3   is/2   last/1   leash/1   length/1   listing/1   member/2   memberp/2 (member without backtracking)   not/1   number/1   or/*   princ/1   read/1   recorda/1   recordz/1   recorded/2   repeat/0   rest/1   retract/1   rev/2   setof/3   true/0   var/1   write/1  

! is the Prolog cut. It may written as an atom ! as well as the 1-element list (!). The Prolog atom predicate is equivalent to Lisp's symbolp. The Prolog atomic predicate is equivalent to Lisp's atom, true for any object that is not a cons.

The Prolog Top Level

Allegro Prolog does not provide a top level listener loop other than the regular lisp listener. Prolog computation may be invoked programmatically from Lisp using the prolog macro described below, or interactively by executing the ?- macro. Here is a simple example interactive session using ?-.

cl-user(2): (require :prolog)
nil
cl-user(3): (use-package :prolog)
t
cl-user(4): (?- (append ?x ?y (1 2 3)))
?x = ()
?y = (1 2 3) <ENTER>
?x = (1)
?y = (2 3) <ENTER>
?x = (1 2)
?y = (3) <ENTER>
?x = (1 2 3)
?y = () <ENTER>
No.
cl-user(5): 

The ?- macro operates similarly to the top-level loop in interactive Prologs. A ?- expression takes zero or more subforms which are clauses and tries to solve them. When a solution is found, it prints the values of all variables in the expression then reads a character from *standard-input*. (If there are no variables it prints "Yes."). If the character is either newline (usually enter on a keyboard) or semicolon, Prolog backtracks and attempts to find another solution. If the character is a period, Prolog prints "No." and returns.

Defined Lisp Operators

Lisp Operator Description
<- clause*
Assert a fact or rule. A macro.
<-- clause*
As above, but first retracts all rules for the functor with the same arity. This is similar to the action taken for <- the first time a functor/arity is seen within a consult, but <-- is especially useful interactively. By retracting previous clauses it allows predicates to be changed and files to be loaded more than once. A useful convention (in a file that might be loaded rather than consulted) is to use <-- in the first rule for a particular function/arity. An example of typical usage would be:
  (<-- (member ?item (?item . ?)))
  (<-  (member ?item (? . ?rest)) (member ?item ?rest))
?- clause*
Interactively try to prove the concatenation of clauses, printing unified variables and then backtracking after each success. A macro.
consult &rest filename*
This function calls cl:load on its filename or pathname argument, with the additional functionality that the first time <- is executed for a given predicate/arity, that predicate/arity is cleared before the new definition is established. consult/1 is also available as a prolog functor, accepting a single filename or a list of filenames.
leash {functor arity}*
A macro analogous to Lisp trace which causes printing at each of the four ports to the functor: call, exit, redo, and fail. This predicate is often called trace in other Prologs, but that name clashes with the standard cl:trace macro.

Leash output is printed to *trace-output*.

If leash is called with no arguments it returns a list of the currently-leashed functor/aritys currently being leashed.

When a functor/arity is leashed (or unleashed) it is automatically recompiled without (or with) tail-call optimization to make leash output conform to Prolog WAM model even for tail-recursive functors. The programmer does not normally need to be concerned with this.

Some built in functors such as if, not, or, and and are normally rewritten by inline macro transformers so will usually not appear in leash output if leashed.

Here is an example of leash. rev-member is like member but returns results starting from the tail of the list:

cl-user(2): (require :prolog)
t
cl-user(3): (use-package :prolog)
t
cl-user(4): (<-- (rev-member ?item (? . ?rest)) (rev-member ?item ?rest)) rev-member cl-user(5): (<- (rev-member ?item (?item . ?))) rev-member cl-user(6): (leash rev-member 2) t cl-user(7): (?- (rev-member ?animal (dog cat fish))) [1] Entering rev-member/2 {Unbound 1000fe7cb1} (dog cat fish) [2] Entering rev-member/2 {Unbound 1000fe7cb1} (cat fish) [3] Entering rev-member/2 {Unbound 1000fe7cb1} (fish) [4] Entering rev-member/2 {Unbound 1000fe7cb1} () [4] Failed rev-member/2 [3] Succeeded rev-member/2 fish (fish) [2] Succeeded rev-member/2 fish (cat fish) [1] Succeeded rev-member/2 fish (dog cat fish) ?animal="fish" <ENTER>
[1] Backtracking into rev-member/2
 [2] Backtracking into rev-member/2
  [3] Backtracking into rev-member/2
  [3] Failed rev-member/2
 [2] Succeeded rev-member/2 cat (cat fish)
[1] Succeeded rev-member/2 cat (dog cat fish)
?animal = cat <ENTER>
[1] Backtracking into rev-member/2
 [2] Backtracking into rev-member/2
 [2] Failed rev-member/2
[1] Succeeded rev-member/2 dog (dog cat fish)
?animal = dog <ENTER>
[1] Backtracking into rev-member/2
[1] Failed rev-member/2
No.
cl-user(8): 
leash-1 functor arity
Functional version of the above.
unleash {functor arity}*
Analogous to Lisp untrace. If called with no arguments, every currently-leashed functor/arity is unleashed.
unleash-1 functor arity
Functional version of the above
*leash-limit*
If variable this is an integer, the debugger will be entered if leash output exceeds the specified depth. This is intended as a convenience when debugging deep recursion. Initially nil.
*prolog-leash-indent-wrap*
Leash output indents one space for each level of leashed functor. If leashing is deeply recursive this indentation may make the leash output unreadable, so the indentation is taken modulo the value of this variable. It must be a nonnegative integer, but may be set large. Initially 20.
prolog-compile-symbols functor*
This may be called after new rules are asserted before making Prolog queries. Called with no arguments, it compiles all functors needing (re)compilation. Otherwise, a functor/arity will be compiled automatically the first time it is called.

Whether a rule is established by <- or assert/2, a Lisp form inside a prolog rule executed by the lisp/2 and similar functors may not refer to the Lisp lexical environment outside the rule definition. This restriction is necessary because the code for the Prolog functor is not compiled until later, after all functor/arity clauses have been combined to form its function body.

The Programming Interface between Prolog and Common Lisp

In addition to the interactive query and assertion macros (e.g. ?-> and <-) there are several operators to call in either direction between Prolog code and Lisp code.

Prolog Functor Description
lisp arg form
Execute a Lisp form from Prolog. The Lisp form is compiled (at the same time the Prolog predicate is compiled) and may refer to variables in the surrounding dynamic Lisp environment. Lexical references cannot go beyond the rule boundary. Prolog variables may be referenced, but only in evaluated positions (i.e. not inside constants). Prolog variables are dereferenced as necessary into non-dynamic-extent copies. The clause fails and no Lisp code is executed if any Prolog variables in the form are unbound. The result of executing the Lisp form second argument is unified with the first argument.
lisp form
As above, but the Lisp form is executed for side effect only. Any value returned by the form is ignored.
lisp* arg form
lisp* form
As above, but unbound Prolog variables do not cause the clause to fail. If the Prolog variables referenced within the Lisp form are guaranteed to be bound, this functor is more efficient than the otherwise-equivalent lisp functor because it does not need to set up code to handle the unbound-variable failure case. It is often the case in numeric calculation that the variables are certain to be bound. In such situations it is faster to execute (lisp* ?x (1+ ?x)) than (lisp ?x (1+ ?x)).
lispp form
A convenience functor similar to lisp but runs as a predicate and fails if execution of the form returns nil. The familiar Prolog numeric predicates can be obtained this way:
  (lispp (>= ?x 5))
lispp* form
As above, except that unbound Prolog variables do not cause the rule to fail. lispp* is more efficient than lispp if all referenced Prolog variables are bound.
lisp! arg form
lisp! form
lisp*! arg form
lisp*! form
lispp! form
lispp*! form
Similar to the above functors, with the provision that any dynamic-extent data bound to Prolog variables in the form are consed in the heap before being passed to Lisp. See the section below on Prolog and Dynamic Extent.
is arg form
This is an exact equivalent for the 2-argument lisp functor above. is is the traditional name for this functor. The lisp and is in this implementation are slightly more powerful than the Prolog is since they are capable of unifying (even destructuring) an arbitrary returned value returned by the Lisp form, while the Prolog functor is intended only for numerical calculations.
  cl-user: (?- (is (?div ?rem) (multiple-value-list (truncate 11 3)))) 
  ?div = 3 
  ?rem = 2 
  No.
Lisp Operator Description
fail
Lisp code running inside a call to one of the the Prolog lisp functors can call this Lisp function to cause the clause to fail immediately.
prolog clause*
A Lisp macro that invokes Prolog programmatically to solve the conjunction of the clauses. The surrounding Lisp environment (lexical as well as dynamic) can be accessed using the lisp functor. This example refers to the likes data in an example in a later section of this document:
  (defun human-friends-of (person)
    (let ((friends nil))
      (prolog (lisp ?person person)
              (likes ?person ?x)
	      (human ?x)
	      (lisp (pushnew ?x friends)))
      friends))

The expansion of the prolog macro wraps a block named prolog around the body so Lisp forms inside the body can easily return a value:

  (defun human-friend-of (person)
    (prolog (lisp ?person person)
            (likes ?person ?x)
	    (human ?x)
	    (lisp (return-from prolog ?x))))

Unless there is some nonlocal exit, execution of the prolog macro silently finds all solutions to the clauses.

Prolog and Dynamic Extent

Computation in Prolog works by attempting to satisfy a clause and, if successful, calling a continuation function. If that continuation fails control may return to any previous choice point, undoing any intervening unifications, and trying a different solution choice. Prolog unification data and continuation functions always have dynamic extent. The implementation exploits this by allocating Prolog variables themselves, cons structure created by unification, and continuation closure functions on the stack, that is, with dynamic extent. This allows Prolog code to operate with essentially zero consing and with a resulting improvement in speed.

There are, however, certain functors that typically cons data with indefinite extent. Solutions collected by the bagof/3 and setof/3 functors are automatically heap consed, as are any rules stored by the assert, asserta, assertz, recorda, and recordz functors.

The family of lisp functors are special cases. When a call to the lisp functor is performed, the values of any Prolog variables referenced in the Lisp form are communicated efficiently to the Lisp code using symbol macros. But those variables may contain nested unification with other Prolog variables, and the structure created by unification may have been consed with dynamic extent. This is not normally a concern since the Lisp code is of course running within the dynamic extent of the surrounding Prolog code, but it would become an issue if the Lisp code stored the data somewhere with indefinite extent.

Dynamic extent is only a concern for cons structures. Numeric data is generally not stack consed.

Some examples will make this clear. Consider the following code:

(defun ancestors-of (person)
  (let ((ancestors nil))
    (prolog (lisp ?person person)
            (ancestor ?x person)
            (lisp (push ?x ancestors)))
    ancestors))

If the data returned by the ancestor predicate are atoms (e.g. symbols) there is no problem since they cannot be stack consed. Similarly, there is no problem with numbers and numeric calculation since the implementation generally does not stack cons numbers. But suppose Prolog data passed to Lisp code was created by unification:

(defun grandfather-pairs ()
  (let ((pairs nil))
    (prolog (grandfather ?gramp ?child)
            (lisp (push (?gramp ?child) pairs)))
    pairs))

are atoms, but it would not work if the objects being passed back were conses created by Prolog unification. But structure created by Prolog unification has only dynamic extent -- that is, it may be consed on the stack. Stack-consed data must be copied to the heap if it is passed outward to Lisp or otherwise preserved outside the dynamic contour where it is created. As an example see the function zebra-benchmark in the zebra example file.

A top-level list created by bagof and setof are automatically given indefinite extent, as is any substructure created by unification and collected on these lists. Therefore the programmer should not have to worry about dynamic extent when using these predicates.

Tail Call Elimination

The ISO standard for Prolog apparently does not require tail-call elimination. However, most implementations provide it to some degree. It is certainly a valuable feature. Allegro Prolog functors usually do not perform tail-call elimination. The Prolog compiler tries to stack cons Prolog variables, data structure, and continuations. Stack allocation of these data enhances performance, but stack-consed data generally prohibits tail-call elimination.

Since tail-call elimination can be important for particular functors in certain styles of coding, a crude control over stack consing has been implemented at the level of an individual functor/arity. This facility is experimental and is likely to change in future releases.

The first clause of any rule may be a cl:declare which makes declarations about the functor. Declarations may appear in any rule for a given functor/arity -- declarations in later rules (according to the ordering maintained by assert and friends) override earlier declarations.

The only declarations currently supported are :tail-calls and :no-tail-calls. The latter is the default.

  (<-- (my-member ?item (?item . ?)) (declare :tail-calls)) (<- (my-member ?item (? . ?rest)) (my-member ?item ?rest))
The (declare :tail-calls) could have been included in either or both of the two rules.

The built in member/2 and length/2 functors are written in a way that consumes neither Prolog nor Lisp stack, but if they had not, the version of my-member shown above implements heap-consing by the functor and allows tail recursion on the Lisp stack. The functor still requires Prolog stack for the unifications performed on the ?rest Prolog variable, but this is small (one word per unified variable) compared to the consumption of Lisp stack that recursion would require.

Tail call elimination is subject to the normal constraints imposed by the Lisp compiler. These are platform dependent.The presence in a functor/arity of calls to the lisp, lispp or lisp! functors will sometimes prevent tail call elimination. Where possible, use lisp*, lispp* and lisp*! instead.

The Prolog Stack

Lisp Name Description
prolog-stack-overflow Prolog maintains a stack of unifications as it tries to satisfy clauses recursively. This stack is separate from the regular Lisp execution stack. The initial stack length is determined by the implementation, but the stack will double in length when the current length is exceeded. This Lisp condition is signalled with cerror when automatic doubling will exceed the limit contained in the variable *prolog-stack-limit*. Continuing (e.g. with the standard Lisp continue function) will continue Prolog computation with the stack length doubled.

The only superclass of this condition is cl:condition itself. In particular, it is not a subclass of error so extraneous error handlers don't try to handle it.

prolog-stack-overflow-length This reader on the above condition returns the current stack length.
*prolog-stack-limit* A special variable containing a positive integer that specifies the size above which a prolog-stack-overflow-length will be signalled. The initial value is 4096.

I/O Functors

The set of built-in Prolog I/O functors is intentionally limited because most input and output would naturally be done by Lisp code. A few functors are provided for convenience.

Lisp Name Description
read value [stream [stream [stream] ] ]
The value argument is unified with a single datum read from *standard-input*. This is just a simple wrapper for the Lisp read function. The input syntax is Lisp syntax, not Edinburgh.

The functors read/2, read/3, and read/4 are also defined, providing the stream, eof-error, and eof-value optional arguments to read. If supplied, the values of these arguments must be grounded.

write value [stream]
The value argument is written to *standard-output*. This is just a simple wrapper for the Lisp write function. The output syntax is Lisp syntax, not Edinburgh.

The functor write/2 is also defined, providing the stream, write. If supplied, the value must be grounded.

princ value [stream]
Like write but uses the Lisp princ function.
nl [stream]
A wrapper for the Lisp terpri function.

Unification with standard-objects.

Prolog Functor Description
slot= inst slot-name slot-value
This Prolog functor unifies the value of a slot of a standard instance. The instance and slot-name arguments must be bound, otherwise the predicate silently fails. The slot-value argument is unified against the content of the slot. A Lisp error is signalled if the slot does not exist or is not bound. The implementation is:
  (<-- (slot= ?instance ?slot-name ?slot-value)
       (lisp ?slot-value
             (slot-value ?instance ?slot-name)))

When it is only necessary to read a slot, this functor is faster than the two that follow.

slot=* inst slot-name slot-value
Like lisp* except that this functor fails silently if the slot does not exist or is unbound.
slot-value inst slot-name slot-value
As above, this Prolog functor unifies the value of a slot in a standard instance. However, if the slot is unbound it is bound dynamically as if by letf to the value of slot-value, and the clause succeeds. (If slot-value is unbound or contains any unbound Prolog variables, the clause fails.) The slot is again made unbound when execution returns out of the continuation (by backtracking, or by Lisp nonlocal exit). While the slot is bound it is visible to other threads. Example:
  cl-user(38): (defparameter *inst* (make-instance 'foo))
  *inst*
  cl-user(39): (?- (lisp ?i *inst*)
                   (slot-value ?i a ?sv))
  No.
  cl-user(40): (?- (lisp ?i *inst*)
                   (slot-value ?i a 123)
                   (slot-value ?i a ?sv))
  ?i = #<foo>
  ?sv = 123
  No.
  cl-user(41): (?- (lisp ?i *inst*)
                   (slot-value ?i a ?sv))
  No.
slot-value! inst slot-name slot-value
As above, except that if the slot is set it is not made unbound when execution backtracks. The side effect of setting the slot persists. Example:
  cl-user(42): (defparameter *inst* (make-instance 'foo))
  *inst*
  cl-user(43): (?- (lisp ?i *inst*)
                   (slot-value! ?i a ?sv))
  No.
  cl-user(44): (?- (lisp ?i *inst*)
                   (slot-value! ?i a 123)
                   (slot-value! ?i a ?sv))
  ?i = #<foo>
  ?sv = 123
  No.
  cl-user(45): (?- (lisp ?i *inst*)
                   (slot-value! ?i a ?sv))
  ?i = #<foo>
  ?sv = 123
  No.

The Prolog `Database' and Generators.

In its simplest model, Prolog needs only to remember rules. (A fact is simply a rule with no trailing clauses and no variables in its head.) All rules for a particular functor/arity are remembered in the order they were asserted and the Prolog implementation somehow references these when that functor/arity is invoked. Under this simple model, there is no firm distinction between that portion of a system which the programmer considers program, that part which he considers internal data and tables, and (sometimes) that part which he would consider external data.

But the scaling requirements and operating characteristics of Prolog data sets vary over enormous ranges. Many standard functors have only one or two rules:

  (<-- (first ?x (?x . ?)))

  (<-- (member ?item (?item . ?)))
  (<-  (member ?item (? . ?rest)) (member ?item ?rest))

Functors like these are naturally represented as compiled code, or may even be inlined. Rules which are conceptually implemented by compiled program code are managed by the Prolog assert/abolish mechanism.

Now consider a different example (from Norvig) where a functor is defined partly by algorithm (nontrivial rules) and partly by data (facts):

  (<-- (likes Kim Robin))
  (<-  (likes Sandy Lee))
  (<-  (likes Sandy Kim))
  (<-  (likes Robin cats))
  (<-  (likes Sandy ?x) (likes ?x cats))
  (<-  (likes Kim ?x) (likes ?x Lee) (likes ?x Kim))
  (<-  (likes ?x ?x))

The likes/2 predicate has seven rules, four of which are facts. Despite the combination of programmatic rules and facts, this combined data is still small enough to be represented directly by the code implementing the functor/arity predicate. (This is true especially for Allegro Prolog since compiled functors capture facts as constant data, rather that expanding them into volumous Lisp code.) However, this representation would become unwieldy if the number of individuals represented in the data were a few orders of magnitude larger, and especially if more of the individuals had idiosyncratic affinities. The factual data would better be represented in tabular form, usually called recorded databases in Prolog. These are managed by functors such as recorda. Prolog stores recorded facts in an equal-key hashtable.

Note that details of the following functors differ in some ways from those of other Prolog implementations, and the API may change in the future. The predicates assert/1, asserta/1, assertz/1 and abolish/2 pertain to the compiled predicate database. The predicates recorda/2, recordz/2, retract/1, and retractall/1 pertain to the hashtable database of facts. The hashtable database is not automatically referenced by compiled functors; it is consulted only by the recorded/2 predicate.

There is a separate interface to the AllegroCache object database described below.

Prolog Functor Description
assertz rule
Asserts a single rule into the database. The new rule is placed after all existing rules for that functor/arity.

Note that assert/1 takes a single list of clauses, therefore one would write

... (assert ((likes ?name Lisp))) ...

and not

... (assert (likes ?name Lisp)) ...
assert rule
Same as assertz.
asserta rule
Like assertz except the new rule is placed before all existing rules..
abolish functor arity
All rules for the functor/arity are removed.

A typical Prolog application will reason over sets of data. In small programming examples, the data is simply included as `facts' that are part of the program source itself. Reading facts from an external source and asserting them into the program is not much different. While a clever Prolog implementation can optimize collections of facts, this approach cannot scale indefinitely. First, it requires the facts be captured as data belonging to the function. Second, efficient reasoning over large data sets requires knowledge about how the data will be accessed. Often this is really an indexing problem, and the application programmer must guide the system by describing (or implementing) how the data is indexed. It is no coincidence that this concern is similar to database implementation.

A Prolog functor/arity is compiled automatically the first time it is called. Any assert or retract to that functor/arity automatically invalidates the compiled function such that it will be recompiled the next time it is called. While the Allegro compiler is reasonably fast, performance may be poor if dynamic fact/rule management is performed using assert and retract with high bandwidth, interspersed with calls to the functor/arity. In such applications it would be better to use the recorded interface or some other custom fact maintenance code, perhaps using generator.

Prolog Functor Description
recordz rule
Asserts a single new rule into the recorded database, keyed on the key which is the head of the rule. Only the functor and arity are considered in matching the key. The new rule is placed after all existing rules for that key. See the example below under generator.
recorda rule
Same as recordz except that the new rule is placed before all current rules for key.
recorded key rule
Finds the list of rules matching key in the recorded database and unifies rule successively to each rule. Only the functor and arity are considered in matching the key.
retract key
All rules for the key are removed from the recorded database. Succeeds only if something is deleted.

A common idiom for solving the data set issue is to construct a Lisp closure that iteratively generates the data items to be returned. The following functors support this use.

Prolog Functor Description
generator item generator
The generator argument should be a Lisp closure that returns an item each time it is called. When there are no more items, it should return nil. This protocol cannot be used with generators that may return nil; see generator* below. The item argument is unified with the returned item.

Example:

  ;; This asserts facts into the record database all the package
  ;; inheritances in the running Lisp. 
  cl-user(40): (?- (lisp ?gen (let ((packages (list-all-packages)))
                                (lambda () (pop packages))))
                   (generator ?package ?gen)
                   (lisp ?used-list (package-use-list ?package))
                   (member ?used ?used-list)
                   (recordz (use ?package ?used))
                   (fail))
  No.
  ;; This queries which packages are used by the current package.
  cl-user(41): (?- (lisp ?package *package*)
                   (recorded (use ?package ?) (? ? ?used)))
  ?package = #<The common-lisp-user package>
  ?t = #<The prolog package>
  ?package = #<The common-lisp-user package>
  ?t = #<The common-lisp package>
  ?package = #<The common-lisp-user package>
  ?t = #<The excl package>
  No.
generator* item generator
Similar to generator but suitable when generated items may include nil. The generator should return two values: the item, and a boolean indicating that an item was returned. When there are no more items the second value should be nil.
generating item lisp-generator
This is a convenience shortcut for typical use of the generator functor. The second argument is a lisp form that returns the generator closure. The values it generates are unified against the first argument. The example above could be written more conveniently this way:
  cl-user(40): (?- (generating ?package (let ((packages (list-all-packages)))
                                          (lambda () (pop packages))))
                   (lisp ?used-list (package-use-list ?package))
                   (member ?used ?used-list)
                   (recordz (use ?package ?used))
                   (fail))
  No.
generating* item lisp-generator
As above for generator*.

A Prolog program that walks a lattice of linked objects is naturally implemented using the lisp operator to follow links using standard Lisp accessors.

  (<-- (class-subclass-gen ?gen ?class)
       (lisp ?gen
             (let ((class-stack (list
                                 (if (symbolp ?class)
                                     (find-class ?class)
                                   ?class))))
               (lambda ()
                 (let ((class (pop class-stack)))
                   (when class
                     (loop for subclass in (clos:class-direct-subclasses class)
                            do (push subclass class-stack))
                     class))))))

  (<-- (has-initarg-p ?class ?slot-name ?initarg)
       (lisp t (typep ?class 'standard-class))
       (lisp ?dslotds (clos:class-direct-slots ?class))
       (member ?dslotd ?dslotds)
       (lisp ?initargs (clos:slot-definition-initargs ?dslotd))
       (member ?initarg ?initargs)
       (lisp ?slot-name (clos:slot-definition-name ?dslotd)))

  (<-- (class-initarg ?root-class ?class ?slot-name ?initarg)
       (class-subclass-gen ?gen ?root-class)
       (generator ?class ?gen)
       (has-initarg-p ?class ?slot-name ?initarg))

  ;; This query will unify to each standard-class and slot that has a
  ;; :documentation initialization argument.
  ;;   (?- (class-initarg t ?class ?slot :documentation))

But querying large collections of relational data may require the programmer to inform the system how the data should be stored and indexed. Allegro Prolog has under development some general mechanisms for indexing data sets, or else an application programmer may implement his own custom mechanisms. For example, the application programmer might back end the Prolog program with a full relational or object database. These possibilities are under active exploration as extensions.

The Interface to AllegroCache

Prolog code can reason directly over data stored in an AllegroCache database. The interface is contained in the pcache module which can be loaded with (require :pcache). The module is currently distributed as part of the AllegroCache distribution.

The interface consists of the single prolog:db functor. This functor has variable arity.

Prolog Functor Description
db class ?instance { slot-name slot-value }*
The db functor should only be executed in a dynamic (Lisp) environment in which the *allegrocache* variable is bound to an open AllegroCache database. The class argument must be grounded and have the value of a persistent-metaclasss class or the name of such a class. ?instance is a variable that will be unified with a succession of instances of that class. If there are no additional arguments, the clause succeeds once for each instance of that class in the database.

If there are additional arguments, they are pairs of slot-names and slot-values. Each slot-name must be grounded and be a symbol naming a slot. If ungrounded, the functor silently fails. The value of that slot is unified against the slot-value which may be grounded or not.

If the first slot is indexed and the first value is fully grounded, retrieval uses AllegroCache's indexing and is fast. Otherwise retrieval may need to iterate over all instances of the class. Improvements in this simple indexing strategy may be explored in future releases.

This is an example of a Roman numeral database that can do arithmetic by database lookup. The objects in the database store Roman numeral and English representations. The example retrieves the integer and English representation of numbers that are half the value of perfect squares that are multiples of 100.

(defclass roman ()
  ((int     :accessor int     :index :any-unique :initarg :int)
   (roman   :accessor roman   :index :any-unique :initarg :roman)
   (english :accessor english :index :any-unique :initarg :english)
   (0mod100 :accessor 0mod100 :index :any        :initarg :0mod100)
   (square  :accessor square  :initarg :square))
  (:metaclass db.allegrocache:persistent-class))

(defun test-populate ()
  (with-file-database ("roman.db" :if-exists :supersede :if-does-not-exist :create)
    (loop for i from 1 to 500
        do (make-instance 'roman
             :int i
             :roman   (intern (format nil "~@r" i) (load-time-value (find-package :keyword)))
             :english (mapcar (lambda (string)
                                (intern string
                                        (load-time-value (find-package :keyword))))
                              (split-re "[ -]" (format nil "~r" i)))
             :0mod100 (zerop (mod i 100))
             :square (* i i)))))

(defmacro with-file-database ((name
                               &key (if-exists nil if-exists-p)
                                    (if-does-not-exist nil if-does-not-exist-p)
                                    read-only)
                              &body body)
  `(let ((db.allegrocache:*allegrocache* nil))
     (unwind-protect
         (multiple-value-prog1
             (progn
               (db.allegrocache:open-file-database
                ,name
                ,@(and if-exists-p
                       `(:if-exists ,if-exists))
                ,@(and if-does-not-exist-p
                       `(:if-does-not-exist ,if-does-not-exist)))
               ,@body)
           (unless ,read-only
             (db.allegrocache:commit)))
       (when db.allegrocache:*allegrocache*
         (db.allegrocache:close-database db.allegrocache:*allegrocache*)))))

cl-user(15): (test-populate)
nil
cl-user(16): (with-file-database ("roman.db")
               (?- (bagof (?half ?english)
                          (and
                           (db roman ?r 0mod100 t int ?int english ?english square ?square)
                           (lisp ?half (truncate ?int 2))
                           (db roman ?r2 int ?half english ?english-half))
                          ?bag)))
?r = 
?english = 
?square = 
?int = 
?r2 = 
?half = 
?english-half = 
?bag = ((100 (two hundred)) (150 (three hundred)) (200 (four hundred)) (250 (five hundred))
        (50 (one hundred)))
No.

Known Issues.

Allegro Prolog is a new product and rough edges can be expected while experience is gained supporting large programs. More attention is needed on smooth integration into the Allegro program development and debugging environment. These are some other known issues:

The interface to and capabilities of leash deserve extension better to support debugging. A mechanism such as the Allegro CL :inside trace option would be especially useful, as would the ability to select individually which of a functor's four WAM ports to leash. In some cases immediately recursive invocation of a functor will not be intercepted by leash. (The issue is essentially the same as tracing lisp self calls.)

It might be worthwhile to make public the Prolog compiler-macro interface if it allows better optimization of user code. However, the API and conventions for a compiler macro are complex and need review and some convenience macros before the machinery can be exported.

A more powerful solution to the tail-jump elimination problem is pending.

Performance could be improved in some kinds of programs by a capability to control indexing of rule terms. This is available as the index/1 in some Prolog implementations.

Definition of Prolog functors should be integrated into the Allegro CL source file recording machinery. This would provide warnings about multiple definitions, particularly in definitions on inherited symbols.

An etags extension for <- and <-- would be helpful.

Franz Inc is interested in bugs and the experience of programmers using Allegro Prolog. Contact support@franz.com.

Example: the zebra problem

Here is the Lisp code and the Prolog code for the zebra problem, a well known example of a puzzle with a set of facts about the attributes of people who live in adjacent houses. First here is the Lisp code:

;;;========== zebra.cl
;;;; -*- Mode: common-lisp; Syntax: Common-Lisp -*-
(in-package :user)
(eval-when (compile load eval)
  (use-package :prolog))
(eval-when (compile) (setf excl:*load-xref-info* nil))
(<-- (nextto ?x ?y ?list) (iright ?x ?y ?list))
(<-  (nextto ?x ?y ?list) (iright ?y ?x ?list))
(<-- (iright ?left ?right (?left ?right . ?rest)))
(<-  (iright ?left ?right (?x . ?rest))
     (iright ?left ?right ?rest))
(<-- (zebra ?h ?w ?z)
     ;; Each house is of the form:
     ;; (house nationality pet cigarette drink house-color)
     (= ?h ((house norwegian ? ? ? ?)   ;1,10
            ?
            (house ? ? ? milk ?) ? ?))  ; 9
     (member (house englishman ? ? ? red) ?h) ; 2
     (member (house spaniard dog ? ? ?) ?h) ; 3
     (member (house ? ? ? coffee green) ?h) ; 4
     (member (house ukrainian ? ? tea ?) ?h) ; 5
     (iright (house ? ? ? ? ivory)      ; 6
             (house ? ? ? ? green) ?h)
     (member (house ? snails winston ? ?) ?h) ; 7
     (member (house ? ? kools ? yellow) ?h) ; 8
     (nextto (house ? ? chesterfield ? ?) ;11
             (house ? fox ? ? ?) ?h)
     (nextto (house ? ? kools ? ?)      ;12
             (house ? horse ? ? ?) ?h)
     (member (house ? ? luckystrike oj ?) ?h) ;13
     (member (house japanese ? parliaments ? ?) ?h) ;14
     (nextto (house norwegian ? ? ? ?)  ;15
             (house ? ? ? ? blue) ?h)
     (member (house ?w ? ? water ?) ?h) ;Q1
     (member (house ?z zebra ? ? ?) ?h) ;Q2
     )
;; This runs the query:
(?- (zebra ?houses ?water-drinker ?zebra-owner))
;; These are benchmarking and profiling functions.  
;; It is believed that solving zebra a
;; single time requires 12825 inferences.
(defun zebra-benchmark (&optional (n 1000))
  (declare (optimize (speed 3) (safety 0)))
  (let (rt0 rt1)
    (time (loop initially (setf rt0 (get-internal-run-time))
              repeat n do (prolog (zebra ?houses ?water-drinker ?zebra-owner)
                                  !     ; Stop once answer is found.  
                                        ; This appears to be
                                        ; what other implementations do, 
                                        ; e.g. time/1 in
                                        ; SWI Prolog.
                                  )
              finally (setf rt1 (get-internal-run-time))))
    (let (zebra-owner water-drinker houses)
      (prolog (zebra ?houses ?water-drinker ?zebra-owner)
              ;; Nearly any cons structure created by Prolog 
              ;; unification will be consed with
              ;; dynamic extent.  It isn't safe to return such 
              ;; structure outside the contour
              ;; that created it.  Prolog doesn't need to worry, 
              ;; since unification always
              ;; has dynamic extent, but arbitrary Lisp 
              ;; code needs to be careful.  The first
              ;; two values this function will return are 
              ;; symbols, but the third is a cons
              ;; tree created by Prolog unification.  In order 
              ;; to return it, the tree needs
              ;; to be copied with indefinite extent.
              (lisp (setf zebra-owner ?zebra-owner
                          water-drinker ?water-drinker
                          houses (copy-tree ?houses)))
              !)
      (values (/ (* n 12825) (/ (- rt1 rt0) 1000.0)) ; real time 
                                                     ; is milliseconds
              zebra-owner water-drinker houses))))
;;;  zebra.cl end

Here is Prolog code:

========== zebra.pl
/* -*- Mode: prolog -*-
 *
 * This file for benchmarking against SWI Prolog.
 */
nextto(X, Y, List) :- iright(X, Y, List).
nextto(X, Y, List) :- iright(Y, X, List).
iright(Left, Right, [Left, Right | _]).
iright(Left, Right, [_ | Rest]) :- iright(Left, Right, Rest).
zebra(H, W, Z) :-
    H = [house(norwegian, _, _, _, _), _, house(_, _, _, milk, _), _, _],
     member(house(englishman, _, _, _, red), H),
     member(house(spaniard, dog, _, _, _), H),
     member(house(_, _, _, coffee, green), H),
     member(house(ukrainian, _,  _, tea, _), H),
     iright(house(_, _, _, _, ivory), house(_, _, _, _, green), H),
     member(house(_, snails, winston, _, _), H),
     member(house(_, _, kools, _, yellow), H),
     nextto(house(_, _, chesterfield, _, _), house(_, fox, _, _, _), H),
     nextto(house(_, _, kools, _, _), house(_, horse, _, _, _), H),
     member(house(_, _, luckystrike, oj, _), H),
     member(house(japanese, _, parliaments, _, _), H),
     nextto(house(norwegian, _, _, _, _), house(_, _, _, _, blue), H),
     member(house(W, _, _, water, _), H),
     member(house(Z, zebra, _, _, _), H).
/* This runs the query a single time:
 *  ?- zebra(Houses, WaterDrinker, ZebraOwner).
 */
zebra1(Houses, WaterDrinker, ZebraOwner) :-
        zebra(Houses, WaterDrinker, ZebraOwner), !.
benchmark1 :-
        flag(benchmark,_,0),
        repeat,
        zebra1(Houses, WaterDrinker, ZebraOwner),
        flag(benchmark,N,N+1),
        N = 1000,
        !.
benchmark :- time(benchmark1).
========== end

Copyright (c) 2004,2005 Franz Inc, Oakland, CA - All Rights Reserved.