|
Allegro CL version 6.2 Added after initial 6.2 release |
This is an early release of Allegro Prolog. It is distributed as a patch for Allegro CL 6.2 and Allegro CL 7.0.beta. Downloading the patch creates a file sys:;code;prolog.fasl which is most-easily loaded by executing (require :prolog). Symbols in the prolog module are in the prolog package. It is convenient to (use-package :prolog). (Due to name conflicts of exported symbols, a package may not use both the prolog package and the common-graphics package without shadowing conflicting symbols appropriately.)
While Allegro Prolog exploits some new optimizations available in 7.0 and will run slightly faster than in 6.2, Allegro Prolog is fully supported on both releases.
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 with a single Lisp function combining 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.
Prolog operates by attempting to unify a clause and if successful calling a continuation. Prolog continuations always have dynamic extent. The implementation exploits this to make Prolog code operate with essentially zero consing. (However, non-dynamic-extent consing is necessary for the bagof/2, setof/2, lisp/2, lisp/1, and lispp/1 functors.)
All public symbols are exported from the prolog package. The definitions mostly follow Norvig. Lisp sexpr syntax is used rather than Edinburgh syntax, although support for Edinburgh input may be provided in the future. Prolog variables are Lisp symbols that begin with the `?' character. The anonymous variable is the symbol `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.
Allegro Prolog does not attempt to be ISO compliant, 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, particularly if there is motivation to extend Allegro Prolog into 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.
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.
=/2 ==/2 abolish/2 and append/3 assert/1 asserta/1 assertz/1 atom/1 bagof/3 call/1 consult/1 fail/0 first/1 ground/1 if/2 if/3 is/2 last/1 length/1 listing/1 member/2 memberp/2 (member without backtracking) not/1 numberp/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 (!).
| 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 . ?rest))) (<- (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 pathname |
This function calls cl:load on its 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 pathname or a list of pathnames. |
leash functor/arity* |
Analogous to Lisp trace, causes printing to *trace-output* 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 clashes with the standard cl:trace macro. |
leash-1 functor/arity |
Functional version of the above. |
unleash functor/arity* |
Analogous to Lisp untrace. |
unleash-1 functor/arity |
Functional version of the above |
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.
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 |
The single argument case is treated as above, executing the Lisp form for side effect only. The clause always succeeds (if all variables are bound) and no result is returned to Prolog. |
lispp form |
A convenience functor similar to lisp but runs as a predicate and fails if execution of the form returns nil. (lispp form) is equavalent to (lisp t (and form t)) |
| Lisp Operator | Description |
|---|---|
fail |
Lisp code running inside a call to the Prolog lisp functor can call this Lisp function to cause the lisp 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 (likes ?person ?x)
(human ?x)
(lisp (pushnew ?x friends)))
friends))
The above example works assuming the ?x are Lisp symbols, 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, is is consed on the stack. It must be copied to pass it back to Lisp or otherwise preserve it outside the dynamic contour where it is created. As an example see the function zebra-benchmark in the zebra example below. Note that the top-level lists 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. |
| 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-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 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. |
[This section is preliminary.]
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 rememberd 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 . ?rest))) (<- (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 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 more of the individuals had idiosyncratic affinities. The factual data would better be represented in tabular form, usually called a recorded database in Prolog, managed by functors such as recorda. Prolog stores recorded facts in an equal hashtable.
[Note that details of the following functors differ in some ways from those of other Prolog implementations. The API may change in the future.] The predicates assert/1, asserta/1, asserta/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.
| 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)) ... |
assertz 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 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.
| 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 iterates over items in the set of data and returns. These predicates 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. |
Prolog programs that walk a lattice of linked objects present little problem because they can simply use the lisp operator to follow links. The object links automatically structure how the data is organized. Here is a more extended example showing both traversal of a tree with generator and references to Lisp objects and predicates using lisp.
(<-- (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 implenment 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 to Allegro Prolog.
Allegro Prolog is a new product and rough edges can be expected while experience is gained supporting large programs. Smooth integration into the Allegro program development and debugging environment needs more attention.
These are some known issues: The interface to and capabilities of prolog:leash need improvement and extension better to support debugging. A mechanism such as the Allegro CL :inside trace option would be especially useful. Also, immediately recursive invocation of a functor will not be intercepted by leash. (The issue is essentialy 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. The system tries to copy stack-consed data structure when it might be returned outside its dynamic extent, e.g. by bagof/3. There may exist other situations where the application program may see unexpected stack-consed data. There are irregularities when a and, or, of not term is passed to call/1. This is a bug that will be fixed. recorded and retract/1 are not yet consistently implemented, nor is there support for the Reference arguments to predicates like assert/2. These will be fixed soon.
Franz Inc is interested in bugs and the experience of programmers using this early release. Contact support@franz.com.
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) and questions whose answers can be deduced. First 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-real-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-real-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