An Environment Model for the Integration of Logic and Functional Programming

1. Introduction

Early attempts ([1],[2]) toward the goal of integrating logic and functiunal programming typically led to the introduction into Lisp of a collection of primitives allowing to return, as a list data object, all, or any number of, the tuples satisfying a given predicate. These proposals actually provide an interface between two different computational models, and therefore have been characterized as embedding one programming language into another. Further works [3] were more theoretic in nature, and dealt with the fundamental issue of providing a unified semantics for languages of both types.

Our own approach is of the embedding kind outlined above. It bears strong similarities with the recent works of both Srivastava and alii [4] and Haynes [5], in the sense that it lead~ to an extension of Scheme (a lexically scoped dialect of Lisp), allowing logic and functional expressions, represented by first class data objects, to be freely mixed, passed as arguments, returned as results, and so on. We thus achieve a functional embedding of logic programming "ithin Scheme. Following Haynes's taxonomy, this embedding can be further described as an environment embedding, in the sense that the embedded and embedding languages share a common environment. It fails h01<ever to be a complete environment embedding, in the sense that it does not allow to access and/or modify control

information.

With regard to these previous works, our

contribution can be described as follows:

• instead of taking care of our extensions by macro expansions, we redefine the semantics of Scheme by modifying the meta-interpreter given in [6]; we are thus led to a new computational model based on two types of environments

This work was done while the author was visiting at the University of California at Santa Cruz.

In the resulting model, the concatenation of two lists can be the result of either a function or a relation application:

• -> APPEND

(APPEND '(A) ' (B C))

• -> (A B C)

(DEFINE APPENDR (CLAUSE (NIL ?X ?X)))

• -> APPENDR

(DEFINE APPENDR (CLAUSE

((CONS ?A ?X) ?Y (CONS ?A ?Z))

(APPENDR ?X ?Y ?Z)))

• -> APPENDR

(APPENDR '(A) '(B C) ?X)

• -> ( (APPENDR (A) (B C) (A B C)))

(APPENDR ?X ?Y '(ABC))

• -> ((APPENDR () (ABC) (ABC))

(APPENDR (A) (B C) (ABC))

(APPENDR (A B) (C) (ABC))

(APPENDR (A B C) () (A B C)))

In the following sections, we first consider a simple subset of Scheme, called Core Scheme. Next, we introduce a variant of Core ScheJo:e which can be used to define and apply relations (cr predicates) rather than functions. By combining these two models, we then obtain a logical extension of Core Scheme, allowing the application of both functions and relations. We conclude by showing how a query language can be fitted into this extension.

2. A .odel for a functional subset of SCHEIIE

Let us consider a simple subset of Scheme, thereafter called Core Scheme, whose expressions have the following syntax:

Following the Lisp terminology, we shall call an identifier an atom, the expression (), the empty list, and all other expressions, non-atomic lists. The semantics of Core Scheme will be defined by a function Eval of two arguments, i.e. an expression and an environment . Thi s interpreter, similar to the metacircular interpreter given in [6], will be given in PASCAL, and rely on the implementation of an abstract data type called S-expression. This implementation will be viewed through a type List, operators NewList, NewAtom, Cons and Append, selectors Car and Cdr, predicates Atom, Eq, Null, and mutator s RplaCa and RplaCd . All of these operators correspond to the usual Li sp functions, except for the constructors NewList and NewAtom which return a empty list and a symbolic atom.

Taking into account the conventions given below for representing expressions, function Eval is :

function Eval(Expr,Env:List):List; begin case TypeOfExpr<Expr) of SelfExpr :Eval :=Expr; VarExpr :Eval :=EvalVar(Expr,Envl ; QuoteExpr :Eval:=Car(Cdr(Exprll; CondExpr :Eval: =EvalCond (Cdr (Expr), Env); De!Expr:Eval:=EvalDef(Car(Cdr<Expr)) , Eval (Car (Cdr (Cdr <Expr))) ,Env), Env i; LaabdaExpr :Eval:=EvalLaabdaCExpr,Env l; CallExpr :Eval :=Apply<Eval (Car (Expr), Env), EvalList <Cdr<Expr) ,Env)) end end;

The expressions recognized by the interpreter are:

2.1 Self-evaluating expressions

Self-evaluating expressions are expressions which evaluate to themselves. In Core Scheme, they are

• the self-evaluating atom NIL and the expression () standing both for the empty list
• the self-evaluating atom T standing for the boolean value true (the boolean value false being represented by the empty list)
• the self evaluating atoms CAR, CDR, CONS, ATOM, EQ and NULL, standing for the corresponding primitive operators (or functions).

2.2 Variables

All atomic expressions which are are treated like variables: the the interpreter is looked up not self evaluating value returned by in the environment supplied as second argument. The pair formed by an atom and its associated va lue being called a binding, a list of bindings def ines a partial environment (called frame in [6]) . Environments are lists of partial environments. It should be noted that environments are not Scheme objects, and are introduced for describing the computational model .

2.3 Quoted expressions

Quoted expressions, prefixed with a quote, are encoded as lists with the atom QUOTE as first element: the value returned is their second element .

2.4 Laabda expressions

They represent functions, and have the general form

(LAMBDA ("arguments") "body")

where "arguments·· is a possibly empty sequence of atoms representing the function formal argument list, and "body" is a sequence of call expressions (see 2 . 7 below) representing its body .

The value returned by the interpreter is a function closure (called a procedure in [6]) , i.e. the association of the expression and its current environment . A closure will be viewed as an instance of an extended abstract data type, called S-Closure, implemented as a non atomic List variant, with additional constructor NewClosure, predicate Closure and selector Environment. It will be represented as

(LAMBDA ("arguments") "body")["environment"]

stressing the fact that the associated environment, accessible through the selector Environment, is not "consed" with the lambda expression.

2.5 Conditional expressions

The general form of conditional expressions is

(COND "easel" ... "casen")

They have their usual Lisp interpretation.

2.6 Define expressions

Define expressions are used to assign a permanent value to an atom . They have the form

(DEFINE "atom" "expression")

with the value of "atom" to be that of "expression".

The value returned by the interpreter is the atom . As a side effect, a new binding is introduced in the head of the current environment.

2.7 Call expressions

They are all interpreted the remaining expressions, and as function applications handled are by function apply . To be legal, their head must be an atom or a lambda expression , and must evaluate to a primitive operator or a function closure. Actual arguments come from a sequential evaluation of their queue . Whereas primitive operators can be applied directly, the expressions contained in the body of function closures are evaluated in sequence, the application receiving the value of the last expression. The environment is taken from the closure and augmented Nith a partial environment build by function BindList, which takes the list of formal arguments from the closure and bind them with the list of actual arguments.

Function Apply can be defined as follows:

!unction Apply<Op,Arq : L1atl : L1at : begin ca .. TypaO!Op(Opl of end: CarOp : Apply:·Car(Car<Argll; CdrOp : Apply : ·Cdr<car<Arqll : ConaOp : Apply : ·Cono(Car(Arql , Car<Cdr<Arql I I: Ato·Op : 1f Ato·<Car<Arql l then Apply : =NewAto·< 'T 'l else Apply: =NewList i EqOp: 1f Eq(Car(Argl ,Car<Cdr<Argl I l then Apply : =NewAto·< 'T ') else Apply : =NewL1·t: NullOp : 1f Null<Car(Argl l than Apply : =NewA to· ( 'T ' I alae Apply : ~NewLiat: ProcOp : Apply :·EvalSequencetCdrtCdrtOp)). end Cons<B1ndL1at<Car<Cdr(Opl I, Arql , EnvtroruaenttOp) l l

3. A logical variant of Core Scba.e: a si~le .adel of logical progr ... ing

Let us now introduce a variant of Core Scheme, allowing to define and evaluate relations (or predicates) rather than functions . Its interpreter, which uses two types of environments, is as follows :

!unction Eval tExpr , FunEnv , LoyEnv : List l: List; begin caae TypeO!ExprtExprl of end: LogVarExpr: Eval : =EvalLogVar ( Expr, LogEnv) ; VarExpr : Eval : =Eval Var t Expr , FunEnv, LogEnv) i QuoteExpr: Eval : =Car (Cdr ( Expr l l : De!Expr :Eval : =EvalDef (Car <Cdr( Expr ll, Eval (Car (Cdr(Cdr (Expr I I I, FunEnv, LogEnv l · FunEnv) i ClauaeExpr : Eval : =EvalClauae ( Expr, }"unEnv. LogEnv): CallExpr :Eval: =SearchCEvalQueryCExpr , FunEnv,LogEnv), EvalCall· CExpr, FunEnv , LogEnvl) end

The expressions recognized by the interpreter are :

3.1 Logical variables

These are all identifiers prefixed ~<ith a question mark . As they can be bound by predicate application, the value returned by the interpreter is looked up in the current logical environment (since clause definitions cannot be block structured , each logical environment is simply a list of bindings, i.e contains just one partial environment) . If no associated value is found, a variable closure is returned, associating the logical variable and the current logical environment . Whenever the associated value is a logical variable, possibly in closure form, it gets evaluated again . Logical variables in closure form are evaluated in their own environment, which overrides the current environment . They are implemented as atom variants, with selector LogEnv accessing the associated logical environment. Note that there is no need, in this particular model , to rename variables having the same name in different clauses, since they are distinguished by the environment they are associated with .

3.2 Fanctional variables

All other atoms are treated as functional variables, and their values looked up in the current functional environment. If no value is found, then the value of the ·logical variable of the same name (i . e . prefixed with a question mark) is returned .

3.3 Quoted expressions

Quoted expressions are defined and treated in the same way aa in Core Scheme . They can be used to represent the equivalent of Prolog terms build with functors (e.g . '(FA) represents F(A) ).

3.4 Clause expressions

They represent logical clauses and have the form

(CLAUSE ("arguments") "body " )

where "arguments" is a possibly empty sequence of terms representing the clause formal argument list, and "body" is a possibly empty sequence of call expressions (see 3 . 6) representing its body. The value returned is a predicate, defined as a list of clause closures , and containing in this case just one c~osure, associating the given expression and the two current environments . As before, closures are implemented as non atomic List variants, with selectors FunEnv and LogEnv accessing the as~ociated functional and logical env ironments .

(CLAUSE (?X ?Z) (FATHER ?X ?Y) (RATHER ?Y ?Z)) will be returned as ((CLAUSE (?X ?Z) (FATHER ?X ?Y)(FATHER ?Y ?Z)) ["environments"})

3.5 Define expressions

Define expressions are represented and treated much in the same way as in Core Scheme, except for the case when the value is a predicate : if the atom already evaluates to a predicate, then these two predicates are appended, a facility for the definition of multiple clause predicates.

3.6 Call expressions

Call expressions are interpreted are all other expressions . They here as predicate applications . To be legal, their head must be an atom or a clause expression, and must evaluate to a predicate or a variable closure. In the first case, the value returned is the list of all instances of the call expression that can be deduced from the predicates defined in the current functional environment. In the second, an empty list is returned. Predicate applications are handled by function Search, which, following most Prolog interpreters , performs a depth-first , left-to-right search for the list of appropriate instances, and uses the unification algorithm without the occur check . The arguments of function Search are:

• a query closure, associating a call expression whose arguments have been evaluated, and two environments
• If variables X and ?X are unbound in their current environment, the call expression

(GDFATHER X 'JIM)

will produce the query closure

(GDFATHER ?X JIM]("anvironlllents")

• a list of calls, each of them formed by the association of a predicate and an argu111ent closure, this closure associating itself an unevaluated list of arguments and a pair of environ111ents.

EKuip1e

The call expression

(GDFATHER X 'JIM) could produce a list of just one call, defined as ((((CLAUSE (?X ?Z) (FATHER ?X ?Y) (FATHER ?Y ?Z)) [ "environments"] (CLAUSE (?X ?Z) (FATHER ?X ?Y) (MOTHER ?Y ?Z)) ["environlllents " )].(X 'JIM)["environments")]]

Function Search is defined as follows:

function SearchCQuery,Calla :LiatJ :Liat; begin it Null (C&llo I then Search:·Cona<ConaCC&r<Query), lnatance(Cdr(QueryJ, LogEnv (Query) ) I , NewLiat J aloe caoa TypeOCOpfC&r<C&r<collol)) or PredOp:Search :·TryEachCQuery, COr(COriC&llo) I, Cdrccor<Callol I, Cdr(COllo)) ; UndefOp :Search:·NewLiat and

end;

Function Search works as follows:

• if there is no calls (i.e the query has been reduced to a fact), then function Search returns a liat containing the query with its arguments instantiated in their associated logical environment
• otherwise, if it is not undefined, the first call is passed to function TryEach, together with a continuation containing the remaining calls.

Function Instance returns a copy of its first argument with all its logical variables evaluated and their associated values instantiated in turn . Function TryEach constructs the list of all deducible instances by trying in turn each of the clause closures contained in the predicate:

function TryEach(Query, Pred ,CallArg , Conl : Liat J: Liat; begin it Null( Pred I then TryEach :=NewLiat elae TryEach : ·Append(TrytQuery,CarCPredJ , CallArg,ContJ, TryEach(Query,Cdr( Pred) ,CallArg, Conti)

end;

Function Try attempts to unify the current call arguments in their associated logical environment, with the candidate clause argument s in a new environment . In case of success, function Search is entered recursively after adding to the continuation the calls from the candidate clause body. All arguments are evaluated before unification:

function Try<Query, Clauae,CallArg , Cont :Liat ) : Liat ; var ClauaeLoqEnv ,TraiJ :Liat ; begin ClauaeLogEnv : ·NewEnv; Trail :·NewList; 1C UniCy(EvalLiatCCOllArg ,FunEnv(COllArg I , LogEnv(CallArgl) , LogEnv ( CallArg) , EvalList(C.rlCdr(Clauae)) ,FunEnv(Clauae), ClauaeLogEnv} . ClauaeLogEnv, Tra11 I then Try : =Search (Query, Append(EvalBody(Cdr !Cdr !Clause) I,, FunEnv (Clause) , · elae Try :=NewLiat; ReataureCTrail} Conti) ClauaeLogEnv),

end;

Function EvalBody returns the list of calls from the candidate clause body.

In the unification process, when a free variable is unified with a term, the environment associated with this variable gets a new binding associating the variable and the term instance in its current logical environment . In order to all01· backtracking (i.e. to be able to restaure logical environments in the state they were before trying a particular candidate clause), a trail is used to keep track of the chronological order of bindings.

1. Log~ca1 Scbe.e: the ~ntegrat~on of Core Scbe.e and ~ta 1og~cal var~ant

Logical Scheme, the integration of Core Sche111e and its logical variant, allows to define and apply functions and predicates. Furthermore, expressions of both kinds can be freely mixed .

Exaaple

For illustration purposes, we shall rely on an extended Core Scheme, where numeric atoms, as well as arithmetic operators, are self-evaluating expressions. The following expressions are then meaningful expressions of Logical Scheme :

(DEFINE AGE [CLAUSE ['JIM 20)))

(DEFINE YOUNG (CLAUSE (?X) (AGE ?X ?Y) (< ?Y 25)))

(DEFINE AND (LAMBDA (P Q) (CLAUSE (?X) [P ?X ?Y) (Q ?X))))

(DEFINE YOUNGFATHER (AND FATHER YOUNG))

While the clause expression assigned to atom YOUNG contains a function application, the body of the lambda expression assigned to atom AND is a clause expression. Finally, atom YOUNGFATHER is defined as a clause expression resulting from a function application whose arguments evaluate to predicates .

The interpreter for Logical Scheme is the union of the two previous interpreters, with its last case element modified as follows:

CallExpr:

case TypeOfCall ( Eval (Car< Expr l , FunEnv, LogEnv J J of FunCall :Eval: =Apply<Eval (Car <Expr), FunEnv, LogEnv), EvalList(Cdr(Expr), FunEnv ,LogEnv), LogEnv); PredCall :Eval :=Search( EvalQuery<Expr, FunEnv ,LogEnv), EvalCalls(Expr,FunEnv , LogEnvl)

end

In order to allow predicate applications within function applications, function Apply has an additional argument . Conversely, in order to allow function applications within predicate applications, function Search has now the following form :

function Search (Query ,Calls :Listl :List: begin if Null(Callsl then Search : =Con& (Cons (Car< Query J , lnstance(Cdr(Query) ,LogEnv<Query))), NewList) else case TypeOfCalltCar(Car(Calls))) of end; FunCall : if Null (Apply (Car (Car ( Call·)) , EvalList(Cdr<Car (Calla l), FunEnv(CdrtCar(Calls))), LogEnv(Cdr(Car(Calls)))), LogEnv<Cdr(Car (Calls))))) then Search: =NewList el!;e Search:=Search<Query,Cdr(Calls)) ~ PredCall :case TypeOfOp<Car(Car(Calls))) of end PredOp : Search : =TryEach( Query, Car<car<C.ll·)), Cdr<Car<Callal), Cdr(Calla)) ; Unde!Op: Search : =NewList end

This new function definition reflects the interpretation given, in a predicate body, to a function application: if this function evaluates to false, the predicate fails; otherwise the predicate evaluation goes on . Furthermore, since clause arguments are evaluated before unification, it follows that arguments of clauses can be function applications (as shown in the introductory example defining the RAPPEND relation), and vice-versa .

5. Query Scbeae: a query language within Scheae

In the previous example, the predicate application

(YOUNGFATHER ?X)

follows the definition of a function AND returning the conjunction of two predicates of respectively two and one arguments. A query language is a facility for applying the disjunction and/or the conjunction, as well as the negation, of any number of predicates of any number of arguments.

Exaaple

In the query language introduced in (6], predicate YOUNGFATHER could be defined by

(RULE (YOUNGFATHER ?X) (AND (FATHER ?X ?Y) (AGE ?X ?Z) ( < ?Z 25)))

while, in Query Scheme, it would be is defined by

(DEFINE YOUNGFATHER (CLAUSE (?X) (AND

(FATHER ?X ?Y) (AGE ?X ?Z) (< ?Z 25))))

In both, this application would also be legal:

(AND (FATHER ?X ?Y) (AGE ?X ?Z) (< ?Z 25))

It must be noted h01·ever that, in [6], the query language is not a part of Scheme . The syntax of Query Scheme being the same as that of Logical Scheme, the new types of expressions are :

5.1 Self-evaluating expressions

In addition to the self-evaluating atoms introduced ~arlier, the self-evaluating atoms AND, OR and NOT stand for the usual operators defined on predicates .

5.2 Negative clause expressions

Negative clause expressions have the form :

(NEGATION ("arguments") "body")

where body is a single call expression. The value returned by the interpreter is a predicate containing a negative clause closure. Negative clauses are used to represent negative call expressions, i.e. expressions prefixed with the NOT operator .

Ex~Q~Ple

The negative call expression

(NOT (YOUNGFATHER 'BILL))

will become the negative clause application ((NEGATION (?X) (YOUNGFATHER ?X]) 'BILL]

5.3 Predicate expressions

Predicate expressions have the following form :

(PREDICATE "clause expr." "clause expr.")

The value returned by the interpreter is a predicate. Predicate expressions are the non-closure representation of multiple clause predicates. They will be used to represent disjunctive calls expressions (see 5 . 4) .

5.4 Call expressions

Call expressions now include conjunctive, disjunctive as well as negative call expressions, i.e. expressions whose head ia equal to the atom AND, OR or NOT, respectively. These particular call expressions are treated as predicate applications whith a list of calls containing:

- for each conjunction, a clause expression - for each disjunction, a predicate expression - for each negation, a negative clause expression. Rxa.ple (AND (FATHER ?X ?Y) (NOT (YOUNG ?X)) (OR (HEALTHY ?X) (YOUNG ?Y)))] will be regarded as equivalent to ((CLAUSE (?X) (FATHER ?X ?Y) ((NEGATION (?X) (YOUNG ?X)) ((PREDICATE (CLAUSE (?X ?Y) (HEALTHY (CLAUSE (?X ?Y) (YOUNG ?X ?Y)) ?X) ?X)) ?Y)))

?X)

While a predicate call reduces to a predicate application, negative clause calls are handled as in most PROLOG implementations, using the closed world assumption: a negative clause succeeds if its calls cannot be satisfied, and fails otherwise . This is reflected in an extension of function TryEach:

function TryEach<Query,Pred,CallArg,Cont :Ptr>:Ptr ; begin if Null ( Pred l then TryEach :=NewList elae caae TypeOfExpr(Car(Pred}) of ClauseExpr:TryEach :=Append(Try(Query,Car<Pred) , CallArg, Cont), TryEach<Query,Cdr(Pred) , CallArg, cont) 1 ; NegExpr:if Null!Try!Quary,C&r!Predl,CallArg,NewLiatll then TryEach : z:AppendCSearch(Query,Cont). end TryEach (Query, Cdr ( Pred l , CllllArg,Cont)) elee TryEach::zTryEachCQuery,Cdr(Pred). CallArg,Cont)

6. Conclusions

The interpretation of expressions involving function and predicate applications, as given above, mirrors the traditional use of both funct ion applications within logic programming languages s uch as Prolog, and predicate applications within 4uery languages. It is by no means the only possible way to evaluate such expressions, but not until a clear denotational semantics is agreed upon will an operational semantics possibly be called correct.

7. References

• (1] Robinson, J.A., and Sibert, E.E., LOGLISP: Motivation, Design and Implementation, in: K. L. Clark and S.-A. Tarnlund (eds), Logic Programming, Academic Press, New York, pp . 299314 (1982) .
• (2] KomorOivski , H.J., QLOG The Programming Environment for PROLOG in LISP, ibidem, pp. 315324 (1982).
• DeGroot, D. and Lindstrom. G. (eds), Logic Programming I Functions, Relations, and Equations, Prentice-Hall, Engle,vood Cliffs,1986
• [41 Srivastava, A. , Oxley, D., and Srivastava, D. , An(other) Integration of Logic and Functional Programming, in: Proceedings of the IEEE Symposium on Logic Programming, Boston , pp . 254260 (1985)
• Haynes, Ch.T., Logic Continuations, in : Proceedings of the Third International Conference on Logic Programming, London (1986)
• (6] Abelson, A. ' and Sussman, G. J . ' with Sussman, J . · Structure and Interpretation of Computer Programs, MIT Press, Cambridge (1985)