A Logic Program Schema and Its Applications

1. INTRODUCTIOif

In reference to recent attempts concerning what is called the fifth generation computer project, the research area of logic programming languages has lately been attracting considerable attention. Since a logic programming language Prolog was initiated by the work of Colmeraure(Colmeraure 1970) and Kowalski(Kowalski 1974), intensive work on Prolog has been done this decade because of its great feasibility as an AI language. Among others, there are a few papers devoting to the theoretical issues on logic programming languages. It was shown by Tärnlund (Tärnlund 1977) that any Turing computable function is computable in bina·y Horn clauses, which ensures the sufficient computational power of Horn logic

programs.

This paper concerns a subclass of Horn logic programs. First we introduce a certain type of a logic program called "recursive-schema", and then define a class of 11 recursive-schema programs" in a recursive manner. A recursive-schema program has very simple structure and property common to many conventional logic programs, and it is explained by the following example.

Suppose one wish to define the concept "ancestor", then he may express it as a binary predicate as follows :

ancestor(X,Y) holds true if and only if

Xis a parent of Y, or there exists Z suchthat

X is a parent of Z and ancestor(Z,Y) holds true.

In a conventional logic formula this is represented, using a "parent" predicate, like

ancestor(X,Y) <- parent(X,Y)

ancestor(X, Y) <- parent(X,Z), ancestor(Z,Y).

Takashi Yokomori

International Institute for Advanced Study of Social Information Science, Fujitsu Limited 140 Miyamoto, Numazu, Shizuoka 410-03 JAPAN

On the other hand, one may also express the concept in a different fashion, that is,

ancestor(X,Y) <- transitive-closure(parent,(X,Y)) where

transitive-closure(P,(X,Y)) <- P(X,Y)

transitive-closure(P,(X,Y)) <- P(X,Z), transitive-closure(P,(Z,Y)).

The introduction of a recursive-schema program is motivated by the latter viewpoint of formulating a concept.

In the next section we introduce a fixed logic program called "recursive-schema" which is a simple generalization of 11 transi tive-closure" mentioned above, and define a class of recursive-schema programs. It is shown that the class of recursive-schema programs has sufficient expressive power in that any recursively enumerable language can be computed by a recursive-schema program. This result gives an alternative simple proof for the Tärnlund's result previously mentioned. Preceding concluding remarks in Section 4, in reference to program transformation and synthesis, some application issues are discussed in Section J,

2. A CLASS OF LOGIC PROGRAMS - RECURSIVE SCHEMAS

It is generally understood that Prolog, a logic programming language, is one of nonprocedural programming languages. Nonprocedural programming has many desirable features, because it can suppress unnecessary details of low-level constructs the procedures bears, and i t enables one to wri te programs in more concise manner (Leavenworth 1975). The simpler a program is, the easier i t is under­ stood, debugged, and modified.

Now, let a predicate "recursive-schema" be defined as follows:

1. recursive-schema(A,B,F,G,X) <- A(X)
2. recursive-schema(A,B,F,G,X) <­

recursive-schema(A,B,F,G,F(X)),B(G(X))

where A,B are predicate names; X=(X 1 , ... ,Xn), Xi: term(1~i~n), F = (f 1 , ... ,fm), G = (g 1 , ... ,gk) are tuples of mappings f. ,g. from the set of terms to the union of the sel Jnd the logical constants (true, false}, and F(X) (f 1 (X), ... , fm(X)), G(X) = (g 1 (X), ... ,gk(X)).

Since we are concerned with logic programs, it should be noted that the secend clause (2) is logically equivalent to

(2 1 ) recursive-schema(A,B,F,G,X) <­

B(G(X)),recursive-schema(A,B,F,G,F(X)).

Hence, in either case we simply refer to it as 11 recursive-schema 11 ·

A class of logic programs denoted by REC is defined in a recursive fashion as follows: (In what follows we identify a predica te wi th i ts program implied. Further, a predicate is sometimes identi­ fied with its predicate name. )

(i) a finite number of predicates called primi­ tive(including true,false,unif) are in REC, (ii)if p is in REC, then not(p) is in REC,

(iii)if p 1 , ··· ,pn are in REC and p <­ p1, ··· ,pn, then p is in REC,

(iv)if p 1 ,p 2 are predicate (names) in REC and p <­ recursive-schema(p1 ,p 2 ,F,G,X), then p is in REC, (v) nothing else is in REC.

A logic program in REC is termed "recursive-schema program".

[Notes]

(1) A predicate unif(X,Y) is the unification predicate. Predicates "true", "false" are logical costants holding true and ·false, respectively. (2) not(p) is the logical negation of p.

(3) The class REC is the smallest class of Horn logic programs constructed from primitive predicates by rules (ii)- (v).

Proparty

Let a predicate 11 or 11 be defined by the follow­ ing two clauses:

or(P,Q) <- P

or(P,Q) <- Q.

One can transform i t into a recursive-schema program as follows :

or(P ,Q)<-recursive-schema(call1 ,call2,F,id,(P,Q)) where call1((P,Q)) <- P, call2((P,Q)) <- Q,

F = (f 1 ,f 2 ), f 1 = f 2 = true, id((P,Q))=(P,Q). Thus, or(P,Q) is in REC, provided that P and Q are in REC. This implies that a program which is defined by a finite set of recursi ve-schema prog­ rams is also a recursive-schema program.

Now, we shall show that the class of recursive­ schema programs has sufficient expressive capabili­ ty, which gives an alternative simple proof for the result that any Turing computable function can be computed in Horn logic programs.(Tärnlund 1977)

It is well known that for a given language L over some finite alphabet T, there exists a Turing machine accepting L if and only if L is a recur­ sively enumerable language. Let L be a recursive­ ly enumerable language over T. We show that there exists a logic prograw. P(X) in REC such that for a given x=a1···am in T, x is in L if and only if P(x) succeeds, where P(x) denotes P( [ a 1 , ··· ,am] ). We assume the reader to be familiar with the rudi­ ments in the formal language theory(e.g.,Salomaa 1973, Harrison 1978).

Lellllla 1.

A recursively enumerable language L can be represented by L = f(L 1 f"\ L 2 ), where L 1 , L 2 are context-free languages, f is a mapping such that for each symbol a, f(a) is a symbol or empty. (See, e.g.,furrison 1978)

Lemma 2.

Let p be a logic program defined by a set of clauses (p(a), p(X) <- p(X 1 ), ··· , p(X) <- p(Xm)}, where a, X,X 1 , ·· ,X!D are n-tuples of terms for some n > 1. Then, p is 1n REC. Proof.

---Let Pi (X) <- recursive-schema(unif1 ,true, Fi, id, X), where unif1(X) <- unif(X,a) and Fi(X)=X., for i=1 , ··· ,m. Obviously, p(X) can be repres.ent~d by (p1 (X), ··· ,pm (X)}. 0

Theorem.

For a given recursively enumerable ianguage L over T, there exists a recursive-schema program P(X) such that P(x) succeeds if and only if x is in L.

Proof.

----By Lemma1,there exist context-free grammars G 1 ,G 2 and f suchthat L = f(L(G 1 )f\L(G 2 )), where L(Gi; denotes the l~guage~enerated by G., and f is a mapping from T to T · We may assu~e that Gi = (V, T', Pi, Si) is in Greibach's normal form, i.e., each rule in P. is ei ther

A -> aB1··· Bm (a inT 1 ,A,B~ in V;15_j_~_m), or A -> a (a in T 1 , A 1.n V),

where V:nonterminal alphabet, T 1 :terminal alphabet.

Construct a logic program cfg-i as follows : cfg-i(X) <- grammar-i(X,[Si]) grammar-i([],[])

for all A -> aB1 · · · B in P., grammar-i([aiXJ,[AifJ) <- 1 grammar-i(X,[B 1 , ··· ,Bm1Yl)

and for all A -> a in P. , gram mar-i( [a I X], [AI Y] ) 1 <- grammar-i(X,Y)

Further, define a predicate homomorphism by : homomorphism([],[])

for all x in T' such that f(x) is non-empty, homomorphism([f(x)IXJ,[xiYJ) <- homomorphism(X,Y)

and for all x in T 1 such that f(x) is empty, homomorphism (X, [x I Y]) <- homomorphism (X, Y). It is easily seen that

(~? x is in L(Gi? if and only ~f cfg-i(x) succeeds, (u) f(y) = x 1f and ony if homomorphism(x,y) succeeds. (In the defini tion of grammar-i above the 2nd argument is used to simulate the left-most derivation for the input in the 1st argument, and when the two become empty at the same moment the predicate succeeds and the input is accepted./

Finally, let a program P(X) be defined as follows :

P(X) <- homomorphism(X,Y), cfg-1(Y), cfg-2(Y). Assurne that P(x) succeeds, then there exists y such that homomorphism(x,y), cfg-1(y) and cfg-2(y) succeed. Hence, we have f(y)=x, y is in L(G ) and L(G2), that is, x is in f(L(G 1 )r"IL(G 2 )) = L. 1 Conversely, it is almost obvious that x is in L implies P(x) succeeds. By the definition of REC and

Lemma 2, we have that P(X) is in REC. o

3. PROGRAM TRANSFORMATION AND SYNTHESIS

One can argue the issues on recursive-schema programs from the view points of program transfor­ mation and synthesis. As we have already seen, the class of recursive-schema programs REC has sufficient expressive capability, and any program in REC can be constructed from a small set of primitive predicates by using some rules.

It would be useful to point out the following facts :

1. any program in REC can be transformed into several assertions and one fixed program, and
2. starting with the fixed program and translating those assertions, one can synthesize a program in REC.

This is illustrated by Figure 1.

When we compare the two databases, it is easily seen that DB2 consisting of one fixed rule ( recursive-schema program) and assertions of facts is much simpler and more effective than DB1 in the following sense. That is, each program in DB2 is demand-driven, so that it is not until when called that it is embodied. Hence, DB2 can save much space.

Another aspect of transformation concerning recursive-schema programs is brought when we pay our attention to the common or similar structure of data domains of programs.

Consider the program "plus" defined in terms of recursive-schema programs plus(X,Y,Z) <- .

recursive-schema(unif1,true,F1,id,(X,Y,Z))

where unif1(X,Y,Z) <- unif(X,O),unif(Y,Z)

F1 = (f 1 ,f 2 ,f 3 ), f 1 ((X,Y,Z)) = pre(X),

id : identity, pre: predicessor Operator .

f 2 ((X,Y,Z)J = Y, f 3 ((X,Y,Z)) = pre(Z).

This representation is quite similar to the one for "append" :

append(X,Y,Z) <­

recursive-schema(unif2,true,F2,id,(X,Y,Z))

where unif2(X,Y,Z) <- unif(X,[]),unif(Y,Z)

F2 = (f~,q,q), q((X,Y,Z)) = cdr(X),

f2((X,Y,Z)f = Y, f_3((X,Y,Z)) = cdr(Z).

Let a mapping T be defined as follows T(cdr) = pre, T(car) = suc, T([]) = 0,

T(X) = X(X: variable), suc: successor operator. Then, we have T(F2) = F1 and T(unif2) = unif1.

Thus, a program "plus" can be obtained from "append" by one-to-one mapping T. This means that any program in REC whose domain is the set of natural numbers can be obtained by using only the transfer mapping T and a few primitives in the "List world". In general, the same thing goes to the recursive-schema programs whose domain world has a one-to-one mapping to the List world.

4- COBCLUDIBG REMARKS

By introducing a specific logic program called "recursive-schema", we have defined the class of 11 recursive-schema programs 11 in a recursive fashion. A recursive-schema program was proposed to capture the common and simple structural property of logic programs, and i t has been shown tha t the class of recursive-schema programs has sufficient computa­ tional power to compute any recursively enumerable language. It should be noted that from the way of constructing the class of recursive-schema programs and the result on computational power just mention­ ed above, one can conclude that any Turing comput­ able logic program can be obtained from a small set of primitive predicates and the "recursive-schema" by applying a few rules.

Further, we have discussed some applica­ tion issues of recursive-schema programs from rather new view-points of program transformation and synthesis. It was demonstrated that a program transforma tion in term s of "recursive-schema" can provide a spacially efficient method for database design, while a program systhesis in our sense can be useful for generating new predicates.

The proposed methods in this paper can be easily implemented in Prolog and incorporated in the phase of database design.

ACKNOWLEDGEMENTS

The author would like to express his gratitude to Dr. Tosio Ki tagawa, the president of IIAS-SIS, Fujitsu Ltd., for warm encouragement and useful suggestion he has been giving through his work.

Also many thanks to Hajime Sawamura for very constructive comment.

HEFERENCES

• [1]Burstall,R.M. and Darlington, "A Transformation System for Developing Recursive Programs", J. of ACM 24:1 (1977) 44-67.
• [2]Colmeraurer,A., 11 Les systemes-Q ou un formalisme pour analyser et synthetiser des phrases sur ordinateur, Internal publication no.43, Depart­ ment d'Informatique, Universite de Montreal, Canada, September, 1970.
• [3]Harrison,M.A., Introduction to Formal Language Theory, Addison-wesley, 1978.
• [4]Kowalski,R., 11 Predicate logic as a programming language," in Proc. IFIP-74, 1974, 569-574.
• [ 5]Leavenworth,B.M., 11 Nonprocedura1Program ming", in Lecture Note in Computer Science 23, Springer, 1975,362-385.
• [6]Salomaa,A., Formal Languages, Academic Press, 1973.
• [7]Sato,T. and Tamaki,H.,"Transformational logic program synthesis", in Proc. of Interna. Conf. on Fifth Generation Computer Systems 1 84,Tokyo, November, 1984, 195-201.
• [ 8] Tärnlund,S.A., "Horn clausecomputabili ty", BIT 17:2 (1977) 215-226.
• [9]Yokomori,T., 11 Using higher-erder inference for knowledge generation", in Proc. of Information System Symposium, at IIAS-SIS, Fujitsu Ltd., November, 1984, 6-13.