PLANLOG: A Language Framework for the Integration of Procedural and Logical Programming

1. BACKGROUND MOTIVATION

Although we are fully aware of the conceptual advan­ tages of functional and logical programming, and the pro­ found Insight Into the non-procedural nature of many appli­ cations of computing obtained this way, In this paper a case shall be made for the procedural, where It goes together with naturalneu and conceptual simplicity.

1.1. PROCEDURAL CONTAMINATION

Actual logical and functional languages, as are the various dialects of LISP and PROLOG, are apparently pro­ cedurally contaminated, as Is already evidenced by notions as pure LISP or pure PROLOG.

Examples of procedurallty would be the predicates "auert" and "retract" In PROLOG, which add or delete knowledge. Another example Is the following PROLOG clause which Is a primitive user Interface around a lotrlc program for the concatenation of two lists.

Head :- wrl te(pro mpt),read(U, V),append(U, V ,R), wrl te(R)

Here the order of execution of the literals seems to be more Important than their truth values.

1.2. PLANNING AND THE NATURALrrY OF THE PRo­ CEDURAL STYLE

In spite of the high esteem which we share for logical and functional programming, we are nevertheless con­ vinced, that the existence and use of procedural features are primarily due not to bad habits of language designers and programmers, but to the nature of the world we live In, and the tasks we want to perform.

The main reason for these procedural features lies In the fact that the conceptual basis of logic programming Is deduction from a single fixed theory, while many aPPlica­ tions must deal with deduction from varying or alternative theories (see [BOW 82], p. 153) Of course, through the Introduction of a (time) parameter Into the theory, many problems of this kind disappear Immediately, but another one shows up : the frame problem.

Natural formulations of many problems In Artificial Intelligence Involve noncommutatlve systems ([NIL 82]). The plan generation systems used for robot problem solv­ Ing are standard examples. Furthermore, the use of plans and plan generation techniques In automatic programming should be mentioned In our context (see [WAL 77], [RIC 81]).

2. THE BASIC IDEA : HORN CLAUSE REASONING AS PLAN GENERATION

A p088iblllty to reconcile logical and procedural pro­ gramming showed up when we noticed that linear proofs (see [BIB 86]), though Invented for the description and generation of plans (or procedural programs), also allow the simulation of ordinary Horn clause reasoning.

We will view a theorem prover as a kind of robot whose job might be called theorem construction. In every proof a plan for Its construction, Is trivially contained. Consequently, the activity of a Horn clause Interpreter, I.e. finding a proof of the goal clause, can be understood as plan generation.

2.1. LINEAR PROOFS FOR PLAN GENERATION

As we shall see, the above given view of a Horn clause Interpreter can easily be modelled in the frame­ work for plan generation, proposed In [BIB 86]. As several others, this approach equates plan generation to proving that a certain goal situation can be deduced from knowledge consisting of an initial situation and the rules describing the actions. To the extent we need it for the definition of PLANLOG, this approach can be outlined as follows:

We describe rules as predicate logic formulae of the form: ALL X,<varlist> EXIST X'

Sit(X') & Bl & ··· & Bm <--- Al & ··· & An & Sit(X)

where Al, ··· ,An,Bl, ··· ,Bm are (not necessarily different) literals and <varlist> is the set of their variables. Such a rule describes an action, saying intuitively, that in every situation X such that Al, ··· ,An are fulfilled, then exists a situation X' such that Bl, ··· ,Bm are valid.

The initial situation will be specified by a set of literals, among them a distinguished literal Sit(init). A goal clause Is of the form

EXIST Z <varlist> Gl & ··· & Gn & Slt(Z).

and means that we ask whether there exists a situation Z In which Gl, ··· ,Gn are true. ( <varlist> Is the set of vari­ ables occurring In Gl, ··· ,Gn .)

Plan generation now means to derive the goal clause from the Initial situation and the rules. The plan Is finally given as the value of the variable Z, which is a term built out of the Skolem functions for the existential variables in the rules. Of course, we cannot expect every proof to yield a correct plan. Therefore, we imposed the restric­ tion that every occurrence of a literal may at most be used once In a proof. Proofs of that kind were called linear In [BIB 86] and it Is claimed that this kind of linear­ ity Is the necessary restriction which must be imposed on proofs in order to represent plans.

The appeal of this conception of a plan generation system lies In Its propinquity to ordinary theorem proving as well as the promise of a new way to master the frame p.roblem without introducing frame axioms.

2.2. LINEAR PROOFS AND HORN CLAUSE REASONING

Horn clause reasoning can be done with this plan gen­ eration method If we transform Horn clauses with non­ empty tall Into rules, e.g. the Horn clause (In PROLOG notation) H :- Al, ··· ,An. (n>O) yields the rule

ALL X,<varlist> EXIST X' :

Sit(X') & Al & ··· & An & H <--- Al & ··· & An & Sit(X)

Here, <varlist> refers to the set of variables occur­ ring In the original clause, and the variables X and X' must be distinct from them. Every instance of such a rule reflects the performing of an action which derives an Instance of the clause's head from Instances of Its tall literals.

Example : Given a logic program for appending two lists:

append([XIA],B,[XIC]) :- append(A,B,C). append([ ],L,L).

The first of the two clauses is transformed to

All S,X,A,B,C Exist S' : Slt(S') & append([XIA],B,[XIC]) & append(A,B,C) <--- append(A,B,C) & Sit(S)

To the set of facts, I.e. append([ ],L,L), the literal Sit(lnit) denoting the Initial situation, is added.

A goal, e.g. ?- append([a,b],[c,d],R), would be transformed to · Exist Z,R : append([a,b],[c,d],R) & Sit(Z)

With the Connection Method (see [BIB 82]) we obtain the following proof:

During this proof the variables are substituted and the value of the variable Z can be interpreted as a plan to derive append([a,b],[c,d],R) from the given facts and rules: It tells In which order the rules must be selected and how they must be instantiated. As in PROLOG, the variable R Is finally bound to the concatenated list [a,b,c,d].

3. TOWARDS WORKING WITH PLANLOG

If we Implement PLANLOG based on a mechanism which generates linear proofs through backward chaining, we can do ordinary Horn clause reasoning and on the other hand are able to do plan generation.

But up to now we still live in a purely logically given world, where non-logical objects like files, a data base or a terminal are not admitted to exist. (For reasons of effi­ ciency we must exclude working with logical descriptions of such objects, where it would be possible.)

Links to an extenal world are created by allowing some of the predicates of our language to be built-ins. This means, that some relations are not represented logi­ cally, I.e. by means of facts or derivable by rules, but coded In the Interpreter ltsself. For Instance, reading from the terminal would be Implemented by a predicate which retrieves some text from the terminal and makes it the value of one of Its variables.

Using such built-in literals In our rules has .the severe consequence, that we have to distinguish between the generation of a plan and Its execution. In a completely logically given world a plan's existence already Implicitly represented the situation of the world after Its Imagined execution. It was given by the set of unconnected literals both In the Initial situation and the left sides of the used rules. But If the rules contain built-In predicates, which reflect and cause modifications of an external world, then the generated plans must be executed to realize these modifications.

There Is a further difference between logical and procedural programs: One of the characteristics of logic programs Is the emphasis on 'what' shall be computed, while trying to care as little as possible about the 'how'. Since with many procedural programs the way they

'behave' is more Important than the result they finally compute, we even believe that with many 'typical' pro­ cedural tasks the 'what' reduces to a side aspect of the 'how'. Consequently, to generate a procedural program from a goal may be rather difficult, just because this goal may be extremely difficult to formalize. Therefore, a major role will be played by the execution of prefabri­ cated plans. On the other hand, the completely prefabri­ cated plan is hardly feasible, because it will often depend on information which is only available at run-time. For Instance, the exact form of a plan to append two lists depends on the length of the lists, which will be communi­ cated to the program at run-time.

For this reason, we have to intermingle plan genera­ tion and execution. If a partial plan Is sufficiently worked out, i.e. the first actions are determined, then they will be executed and based on the information thus acquired the plan generation process is resumed. Let us illustrate the Issues just discussed by considering how a primitive user interface to the logic program for appending two lists can be treated In PLANLOG.

acc(prompt) =====-------

The plan must be read top-down. We assume a prompt symbol already to be stored In a special register called ace. The built-in write predicate in the first rule writes It on the terminal. The built-in read predicate In the next rule reads two lists and stores them in two regis­ ters reg1 and reg2. The third rule calls the append pro­ gram. Since the Input values for this predicate are now known, a subplan can be generated which computes R. The last rule writes R on the screen.

4. THE PROMISE OF PLANWG.

Viewing PLANLOG as a procedural language, It Is distinguished by the following remarkable features:

PLANLOG can be termed a "declarative procedural language". This goes without saying for the logical part, for which declaratlvlty is characteristic, but due to the specification of the procedural entitles, i.e. the actions, In form of logical lmpllcatlons, we obtain 'declarative pro­ cedures'.

PLANLOG can be termed a "predicative procedural language". The data structure it works on are relations and formulas: It might be seen as a high level database language.

PLANLOG can be termed an "open procedural language". Adding a new procedural rule is as easy as defining a new function in LISP, but in contrast to a tradi­ tional procedural language, we have extended the language by a new statement and not just written another procedure.

PLANLOG can be termed a "knowledge-based pro­ cedural language". Since declarative knowledge, i.e. logi­ cal Implications, are transformed Into rules, we finally obtain a procedural language, the statements of which reflect chunks of knowledge.

PLANLOG is a means to overcome the procedural contamination of PROLOG. This is not o~y of theoretical interest: The more we create systems which process or extend logic programs, e.g. program transformation and synthesis systems, incorporation of function handling, ··· , the easier are these enterprises if our programs are writ­ ten in pure logic.

PLANLOG might give a new impetus to program syn­ thesis. Having PLANLOG as a target language might force the synthesized programs to become more procedural and, consequently, more efficient.

Due to the representation of plans as (partial) proofs, potential parallelism in plans should be uncovered by analysis of the connection structure and thus facilitated the parallel execution.

Due to the availability of several programming styles as pure Horn clause reasoning, plan generation from goals and traditional procedural programming in the same language, the programmer is obliged to decide explicitly, which style he wants to adopt and for which task.

ACKNOWLEDGEMENTS

Besides our Munich AI group, I owe very special thanks to Ricardo Caferra, Reinhard Enders, Ulrich Fur­ bach, Paul Jacquet and Philippe Schnoebelen for their patient sympathy with my dizzy explanations in the days when PLANLOG began to loom. Wolfgang Blbel, Christoph Kreitz and Reinhold Letz provided a lot of comments on the present as well as on earlier draft versions.