Integrating Prolog Into the Poplog Environment

ABSTRACT

Although Prolog undoubtedly has its good points, there are some tasks <such as writing a screen editor or network interface controller) for wh i ch it is not the Language of choice. The most natural computational concepts [2] for these tasks are hard to reconcile with Prolog's declarative nature. Just as there is a need for even the most committed Prolog programmer to use "conventional" Languages for some tasks, so too is there a need for "Logic" oriented components in conventional applications programs, such as CAD systems [7] and relational databases [5]. At Sussex, the problems of integrating Logic with procedural programming are being addressed by two projects. One of these [4] involves a distributed ring of processors communicating by message passing. The other project is the POPLOG system, a mixed Language AI programming environment which runs on conventional hardware. This paper describes the way in which we have integrated Prolog into POPLOG.

I THE POPLOG ENVIRONMENT

The POPLOG system . is an AI programming environment dev€Loped at Sussex University [3]. It supports Pr.olog, POP-11, a dialect of POP-2 [1J, and a bas lC LISP. POP LOG currentLy runs on the DEC VAX series of computers under the VMS operating system, but other implementations are in progress.

In POPLOG, the Link between the programming Languages and the underlying machine is the POPLOG virtual machine. The compilers produce POPLOG virtual machine instructions, which are then further trans La ted into the machine code for the host machine. At the Level of host machine code it is possible to Link in programs written i~ Languages such as FORTRAN. Procedures for "planting" instructions for the virtual machine are fully accessible to the user. Thus the Prolog campi Ler is just one of the many possible POPLOG programs that create new pieces of machine code. In particular, it is easy to create procedure closures. For the purposes of this paper, a closure is a structure which contains a pointer to a procedure plus a set of arguments for that procedure. The closure can then be applied as if

it were a normal procedure with no arguments. Some

*Steve Hardy is now at Teknowledge Inc, 525 University Ave, Palo Alto, CA 94301, USA.

INTEGRATING PROLOG INTO THE POPLOG ENVIRONMENT

Chris Mellish and Steve Hardy* Cogni~ive Studies Programme, Un1versity of Sussex, Falmer, BRIGHTON, UK.

"syntactic sugar" has been provided in POP-11 to make it easy to create closures; an express ion such as:

double(% 3 %)

evaluates to a closure which when Later invoked calls the procedure DOUBLE with argument 3.

II BACKTRACKING AND CONTINUATION PASSING

In this section, we i llustrate, us i ng examples written in POP-11, how backtracking programs are implemented in POPLOG using a technique called continuation passing. Although examples are shown in POP-11 for clarity, in practice Prolog programs are compiled directly to

POPLOG virtual machine code.

Continuation passing is a technique in which procedures are given an additional argument, called a continuation. This continuation <which is a procedure closu re) describes whatever computation remains to be performed once the called procedure has finished its comput ation. In conventional programming, the---continuation is represented implicitly by the "return address" and code in the calling procedure. Suppose, for example ~hat we have a proc~dure, caL Led PROG, that has JUSt two steps: call1ng the subprocedure FOO and then the subprocedure BAZ, thus:

define prog 0; fooO; bazO;

enddefine;

We can rewrite this procedure with an

explicit continuation, thus:

define prog(continuation); fooO; bazO; continuation()

enddefine;

This definition presupposes that do not themselves take continuations. then we must arrange for BAZ to CONTINUATION and for FOO to be appropriate closure of BAZ, thus: FOO and BAZ If they do, be passed passed an define prog(continuation); fooCbazC%continuation%)) enddefine;

Thus FOO gets as argument a closure. This closure, when applied, will cause BAZ to be

invoked with CONTINUATION as its argument.

Continuations have proved of great significance in studies on the semantics of programming Languages [6]. This apparently round about way of prog ramming aLso has an enormous practical advantage since procedures have explicit continuations there is no need for them to "return" to their invoker. Conventionally, sub-procedures returning to their invokers means "I have finished - continue with the computation". With explicit continuations we can assign a different meaning to a sub-procedure returning to its invoker, "Sorry- I wasn't able to do what you wanted me to do".

This can be illustrated if we define a new procedure NEWPROG, whose definition is ..!.r:.r doing FOO and ..!....!. that doesn't work then ..!.r:.r doing BAZ, thUs_:_

define newprog(continuation); fooCcontinuation); baz(continuation); enddefine;

If we now invoke NEWPROG (with a continuation) then it first calls FOO (giving it the same continuation as itself). If FOO is succesful then it will invoke the continuation. If not then the caLL of FOO wiLL return to NEWPROG which then tries BAZ. If BAZ too faiLs Cby returning) then NEWPROG itself faiLs by returning to its invoker.

III INTRODUCING UNIFICATION

Consider the following Prolog program: happy(X) :- healthy(X), wise(X). healthy(X) healthy(X) jogs( chris). jogs( jon). jogs(X). eats<X, cabbage).

This says that X is HAPPY if X is HEALTHY and WISE. Someone is HEALTHY if they JOG or EAT CABBAGE; CHRIS and JON both JOG. If these are complete definitions for these predicates, then we can translate them into POP-11 as follows:

define happy(x, continuation); healthy<x, wise(%x, continuation%)) enddefine; define healthy(x, continuation); jogsCx, continuation); eats(x, "cabbage", continuation);

enddefine;

define jogs(x, continuation); unifyCx,"chris",continuation); unify(x,"jon",continuation) enddefine;

UNIFY is a procedure that takes two data structures and a continuation. It attempts to unify (that is, "make equal") the two structures. If it is unsuccessful, UNIFY immediately retl.Jrns to its invoker. If, however, it is successful, then it applies the continuation and when that returns, UNIFY undoes any changes ..!..!. made to "the two structures and then itself returns to itS invoker.

Before we can present a definition of UNIFY, we must consider the representation of Prolog variables. In Prolog, variables start off "uninstantiated" and can be given a value only once (without backtracking); moreover two "uninstantiated" variables when unified are said to "share", so that as soon as one of them obtains a value, the other one automatically obtains the same value.

In POPLOG, a Prolog variable is represented by a single element data structures called a REF. REFs are created by the procedure CONSREF and their components are accessed by the procedure CONT. An uninstantiated Prolog variable is represented by a REF containing the unique word "undef". If a variable is assigned some value, this value is placed into the CONT. If two variables come to "share", we make one point to the other. To find the "real" value of a variable, especially one that is sharing, it is necessary to "dereference" it (Look for the

contents of the "innermost" REF).

Here now is a simple definition of UNIFY

written in POP-11: define unify(x,y,continuation); if x == y then continuation 0 elseif isref<x) and cont(x) "undef" then y -> cont(x); continuation 0; "undef'' -> cont (x) elseif isref(x) and cont(x) /= "undef" then unify(cont(x),y,continuation) elseif isref(y) then unify(y,x,continuation) elseif ispair(x) and ispair(y) then unify(front(x),front(y), unify(%back(x),back(y),continuation%)) end if enddefine;

The procedure first sees if the two given data structures, X and Y, are identical. If so, it immediately applies the CONTINUATION. If the structures aren't identical then UNIFY Looks to see whether X is a REF and if so whether it is uninstantiated (ie. whether its CONT is the word "undef"). If so, UNIFY sets its value to Y Cby assigning to the CONT; assignment works from Left to right in POP-11), does the CONTINUATION and if this returns (ie fails) unbinds the REF by setting the CONT back to "undef". The final case of UNIFY deals with the possibiLity that X and Y may be List pairs. A complete definition of UNIFY must have a case here for each type of datastructure recognised as a Prolog complex term. Note that there is no ELSE part to the IF statement. The default action is simply to return (ie indicate faiLure).

As a more complex example, here is a transLation of the Pro Log MEMBER predicate into POP-11. The Prolog definition is:

member(X,CXIYJ).

member(X,CYIZJ> :- member<X,Z).

When translated into POP-11, it will be necessary to make explicit the unifications which are implicitly done when a Prolog predicate is invoked. It may therefore be easier to understand the POP-11 translation if we rewrite the Prolog definition to make the various unifications explicit:

member (X, Y) member(X,Y) y y CXIMJ.

CLIMJ, member(X,M).

This translates into the following POP-11 procedure:

define member<x, y, continuation>; vars L; consref<"undef") -> L; vars m; consref<"undef") -> m; unify(y, conspair<x,m), continuation); unify(y, conspair(L,m), member(Xx,m,continuation%)) enddefine;

The first two Lines of this definition create new Prolog variables (REFS with contents "undef") L and M. The next Line checks if the value of Y can be unified with a newly created pair whose FRONT is the vaLue of X and whose BACK is the new variable M; if so, UNIFY will perform the continuation. The Last Line of the definition tries unifying Y with a pair whose components are the new variables L and M; if successful, UNIFY will invoke its continuation which, in this case, is a closure of MEMBER itself.

IV CONCLUSIONS

We have presented a simplified version of how Pro log fs implemented in the POPLOG environment. We believe that this system provides a basis for

true mixed-Language AI programming because:

1. The POP-11 and Prolog compilers are just two of potentially many procedures which generate code for the POPLOG virtual machine. This means that the two Languages are compatible at a Low Level, without there being the traditional asymmetry between a Language and its implementation.
2. The continuation passing model provides a semantics for communication between these two Languages which allows for far more than simple "subroutine calling".
3. The control facilities available within POPLOG (not shown here) make it possible to implement a system which is faithful to the theoretica l model, but which is nevertheless efficient.

ACKNOWLEDGEMENTS

We wouLd Like to thank John Gibson, the main implementer of the POPLOG virtual machine and the POP-11 compiLer, for providing us with a powerful programming environment, without which this work would not have been possible. We would also Like to thank Aaron Sloman and Jon Cunningham for many useful discussions.