Prolog in Ten Figures

1. TREES

From an abstract point of view, one may say tha t the knowledge of an intelligent being on a g iven sub j ect, is the set of facts that he or she c an gener ate on the subject. Therefore, knowledge can be viewed as a set of facts, spec ified by a set of r ules. Each of these facts can be represented by a dec lar ati ve sentence. In our case we represent a fact by a tree, drawn upside down, as the one shown in Fig 1a. Each l eaf and each node I S label ed wi th an "atom" of informati on : this at om can be a word, a group of words, a number, or a s pecia l character. Onl y the structure of the tree i s r e levant. Therefor e, Figs 1a and 1a ' ar e equi valent. Trees in F1gs 1a, 1b and 1c ar e examples of facts in three different fiel ds : arithmeti c , (st y! isticl permutations, and mea l plann ing . Facts are always trees, but not al l trees are facts: obviously the trees in Fi gs 1d and 1e are not facts in arithmetic, even if tree in Fig 1d is a sub-tree of the fact in Fig 1a.

Trees were purposely chosen as data structures : they are capable of expressing complex informati on and, at the same time, simple enough to be handled a l gebr ai call y , and by a computer.

2. TERMS

Formu l as are used to represent tree patterns . Thes e f ormul as called "terms", consi s t of atoms of information, variables, par~ntheses and commas . Recall that an atom of information is either a group of words, a number, or a special character. In the left column of Fig 2a the s yntac ti c s tructure of a term is defined; this i s a recursive definition where complex terms ar e defined from simpler terms; the simplest terms ar e variables or atoms of Information. Examples of terms can be found in the left part of Figs 2b and 2c.

Je remercie Jacques Cohen de m'avoir aide ~ r~diger cet article en anglais.

Va~iables occu~~ing in te~ms ~ep~esent unknown t~ees . The~efo~e , the tree ex p~essed by a te~m will depend upon the trees assigned to the va~ iables . Such an assignment "X", called a "t~ee-assi gnment" , is just a set of pai ~s " ;< i : =ai ", "ai" being the t~ee assigned to the van able " :q ". The ~ight column of Fig 2a gives the b-ee "a" represented by the term "t" after the appl ication of t~ee-assignment "X" . It is assumed that if "t" contains no variable, an empt y tree-assi gnment can be applied .

Figs 2b and c depict two examples of tree-assignments. xample 2b shows that it is possible to find n the assignment "X" , variables which do not occur in the term, but the contrary is not possible. In e:: ample 2c, the term contains no variable; this means that the corresponding tree does not depend on the assignment . The last example shows a systematic way of coding a finite tree by a term without variables .

3 . CONSTRAINTS

Prolog is a language which "computes " on trees "ai" repres ented by variables ":.: i ". This computation is done by accumul ating constraint s that final trees must satisfy . These constraints limit the values variables can take, that i s th~ tree-assignment of vari ables "x i " by trees "ai"· As shown in Fig 3a , a constraint "C" consists of a set of elementary constraints , each of them to be satisfied. An elementary constraint is either a pair of terms " C sj, ~ j 'l " which will represent equal trees, or a pair of terms "ctk,tk' l" whi ch will repres ent unequal trees. Fig 3a illustrates the general condition under which a tree-assignment "X" satisfies a constraint "C" . "X" is also said to be a solution of "C". Fig 3b shows an example of a constraint "Cl" satisfiable by the tree-assi gnment "XI". In Fig 3c there are three constraints which cannot be satisfied by any tree-assignment.

During the execution of a Prolog program, the basic operation consists of verifying whether a constraint is "satisfiable" or not (by at least one tree-assignment). This is done by "reducing" it, as seen in Fig 3d: the purpose of "reducing" is to simplify the constraint 1n order to make all its solutions explicit. This involves exhibiting variables distinct from each other as left members of equalities. To do so, we use a specific property of trees: the unique decomposition of a tree into immediate subtrees. This property permits us to replace:

Note that if this property would hold for numbers, we would wrongly conclude that the two constraints "{i<+3=2+y} 11 and ··{:-:=2,3=y}" are equivalent~ If we succeed in producing equalities where left members are distinct variables and where there are no inequalities , then the constraint is satisfiable . Its solutions are directly obtained by assigning arbitrary trees to variables not appearing as left members .

If inequalities are left, let "n" be their number.

Another bdsic propert y allows us t o split the initial problem into "n" independent and simpler sub-problems : a constraint of the form 11 Cu{t . 1 ;it . 1 ~ , ··· ~tn;-ttn~}~~ is satisf i ab le if and onl 'y' if each of the constraints "Cuct 1 #t 1 '}", ··. , "Cu{tn#tn'}" is also satisfiable. Again, this is not true in the domain of natural integers "0,1,2, ... ", because it would be possible to show that the constraint ' 1 {:<+y=2, ;< ;i0,:-:;i1,>:#2} 11 has at least one solution since the constraints ''{ :-: +y=l, :-: #0}~~, 1/{>i+y=l,:-:#1} 11 and · ·{;-: +y= l, :-~ ~2 } 11 have at least one' In order to veri f y that the constraint "Cu{ti#ti '}" i s sati s fi abl e (knowing that "C" already 1s l we must check that the constraints 11 [ 11 and "Cu{ti =ti ~}" ar-e not equivalent. If the constraint "Cu{ti=ti' }" 1s not satisfiable, we can even remove the 1nequality "tp<ti' ", as in e:-:ample 3d .

In the same way as we simplify equalities, it is possible to simplify inequalities . This allows us to present any satisfiable const rain t 1n a "reduced form" : this reduced form shows that the constraint is satisfiable by making all its solutions explicit. The general form of a reduced constraint containing inequalities IS beyond the scope of this paper (see Colmerauer 19821.

4. INFINITE TREES

As surprising as it may be, it is also possible to handle infinite trees. Such a tree is shown in Fig 4a: it represents an endless path along the cross-like figure shown 1n Fig 4b. It is possible to present this tree by the diagram with a loop in 4c, obtained by merging all the nodes from which isomorphic subtrees arise, that is, from which equal subtrees arise. If we omit to merge a few nodes, we obtain the different diagrams in 4c' and 4c'' wh1ch still represent the same tree. That Fig 4c is a finite diagram means that the initial tree in 4a contains a finite set of configurations or, more precisely, that the set of its subtrees is finite: this is the definition of a "rational" tr-ee. Of course, all finite trees are rational. Although finite trees can be defined by simple ter-ms without variables, infinite rational trees can only be defined by the constraints they must satisfy . Taking into account successively all sides "1,2, ·.. ,12" of the cross-like figure in 4b, we construct the constraint 4d which is satisfied only in case of the assignment of "x" by the tr-ee in Fig 4a. From the diagram shown in Fig 4c, we can construct a simpler constraint 4d', having the same property.

For the curious reader­ example of a non-rational we provide in Fig 4e an infinite tree. After merging all possible nodes this tree yields the infinite diagr-am in Fig 4e'. Note that it would be necessary to have a constraint, made from an infinity of e lementary constr-aints, to completely descr-ibe this type of tree. ·

5. A PROLOG PROGRAM: LET'S EAT WELL

We now interrupt our­ present an example program computes the and consists of the 5b and 5c. theoretical development to of a F'rolog program. The composition of "light" meals thr-ee parts shown in Figs 5a,

In Fig 5a we describe, by 11 rules, a possible set of meals, r-egardless of their dietetic qualities.

The first rule states that:

• if "a" is an appetizer and,
• if ''m'' is a main course and,
• if "d" is a dessert,

then the triplet "a,m,d" is a meal.

The ne:-:t two rules state that:

• if "m" is a fish, "mu is a main course and,
• if "m" is a meat, "m 11 is a main cour-se.

The remaining eight rules classify a few cour-ses. In Fig 5a', the computer answers two questions based on the knowledge described in Fig 5a. The first question is :

what are the values of "m", that make "m" a main course?

There are s everal possible answers and each answer is given as a reduced constraint on "m". The second question is:

what are the triplets "a ,m,d"

which constitute a mea l ? . .

The corresponding answers are also presented in Fig 5a'.

In Fig 5b we introduce a minimal knowledge of arithmetic of positi ve integers: the addition ":-: +y=z" with "z o:: 10" , denoted by "smal l-sum (:-: , y,zl ". The fact that " >: +y=z" implies "(:-:+1l+y=(z+1)" is used to define the notion "small -sum" from the notion "small -successor", uti lizing two rules. The notion "small-successor" is defined by eight rules so that "small-successor<:-:,yl" corresponds to the equality "y=:-: +1" with "y< 10". Fig 5b' presents the

So... meal <a,m,dl -> appetizer(a) inain (ml dessert(d l ; main(m) - > fish (ml; mainlml - > meat (m); appetizer<radishes) - >; appetizer(patel - ·~ .. ~· ' fish(solel ->; fish(tunal - >; meat(porcl - ·· .. . / ' meat(beef) - >; dessert(cakel - ·· .. . / ' dessertlfruitl - >;

50.: main (m)? {m=sole} {m=tuna} {m=por-c} {m=beef} meal<a,m,dl? {a=radishes, m=sole, d=cake} {a=radishes, m=sole, d=fruit} {a=r ad·i shes, m=tuna, d=cake} {a=radishes, m=tuna, d=fruit} <a=radishes, m=porc, d=cake} <a=radishes, m=porc, d=fruit} {a=radishes, m=beef, d=cake} {a=radishes, m=beef, d=fruit) {a=pate, m=sole, d=cake} {a=pate, m=sole, d=fruit} {a=pate, m=tuna, d=cake} {a=pate, m=tuna, d=fruit} {a=pate, m=porc, d=cake} {a=pate, m=porc, d=fruit} <a=pate, m=beef, d=cake} <a=pate, m=beef, d=fruit}

computer 's answers to a few questions about arithmetic. Observe t hat, according to the f ormul ated questions , the same small Prolog program of Fig 5b also computes the sum, the difference, or decomposes a number in all possible sums of two numbers.

Fig 5c defines a light meal (based on Figs 5a and 5bl by ass igning a cer tain amount of caloric units to each course, and restricting to meals which add up to a number of units smaller than 10 . The main rule of Fig 5c states that :

- if t he triplet "a, m,d" is a meal and, -if the number of units of "a" is ":-:" and, - if the number of units of "m" is "y" and, - if '' >: +y=u .. and "u< l O" and, - if the number of units of "d" is "z" and, - if ":+u=vu and 11 V< l O" ,

then the triplet "a,m,d" is a light meal . In Fig 5c', the computer lists the seven allowed meals'

Sb

little-sum l 1, :-: , yl - > little-successor <:-: ,yl; little-sum(x' , y ,z 'l - > little-successor<x , x' l little-sum<x , y,zl little-successor<z,z'l; little-successor<1,2l - >; little-successor (2 ,3l - >; little-successor <3 ,4l - >; little-successor<4,5l - >; little-successor <5 ,6l little-successor (6, 7 l little-successor (7 ,8l little-successor <B ,9l - ' · / , - >; - "·· · / ' - >;

Sb'

little-sum<4,3, xl? {>:=7} little-sum<4, x,7l? { x=3} little-sum<x,y,5l? {>: =1, y=4} {>:=2 , y=3} {x=3, y=2} {>:=4, y=l}

.Sc light-meal <a,m,dl - .> meal <a, m,dl units<a,>: l units<m,yl little-sum<x,y ,u l uni tsld, z) little-sum<z ,u,vl; unitslbeef,3l - >; units <fruit,ll ->; units <cake,5l ->; units(pate,6) ->; units(porc,7l - >; units<radishes,ll - >; units<sole,2l - >; unitsltuna,4l - >;

S c'

light-meal (a,m,dl ? {a=radishes, m=sole, d=cake} {a=radishes, m=sole, d=fruit } {a=radishes, m=tuna, d=fruit } {a=radishes, m=porc, d=fruit} {a=radishes, m=beef, d=cake} {a=radishes, m=beef, d=fruit } {a=pate, m=sole, d=fruit }

6. FORMAL MEANING OF PROLOG PROGRAMS

Fig 5 informally described a Prolog program. We now formalize its meaning. For most languages, the meaning of a program is given by the succession of elementary operations which the computer is supposed to perform. This is not true of Prolog which, as presented, is a formalism capable of representing knowledge and to express questions about it, independently of any computer . The computer 's simply computes the answers to these questions.

In Fig 6 we derive in two steps the set of facts (a circle) specified by a Prolog program from the original program (a block). This set represents the potential knowledge contained in the program. Each of the facts is a tree, taken from all possible trees. The first step is required since the rules of a Prolog program are, actuall y , pattern of rules, and since it is first necessar y to generate precise rules dealing with trees. The second step can be per~ormed in two ways: either by considering the rules as rewriting rules (definition I>, or by considering them as logical implications (definition II).

Fig 6 also caracterizes the set of facts which yield the answer to a Prolog question. A question is a single term "t" which stating:

what are the facts of the form "t"?

The set of valid answers is the intersection of the set of specified facts with the sub-set of trees, obtained by assigning all conceivable trees to the variables of term "t".

7. THE SEARCH SPACE

Fig 6 illust~ated the double definition of the meaning of a P~olog p~og~am. Althougt both definitions a~e conceptually satisfying, they cannot be di~ectly used to compute the answe~ to a given question.

Howeve~, this computation can be pe~fo~med on the light of definition I by ~ew~iting t~ees patte~ns instead of t~ees, with the use of a finite set of ~ules patte~ns instead of an infinite set of ~ules. A t~ee patte~n is a "te~m-const~aint" pai~, the const~aint limiting the ~ep~esented t~ees; a ~ule patte~n is, in fact, just a P~olog ~ule.

In Fig 7b the question on p~og~am ?a, states: unde~ which const~aints does "meall~adishes,m,dl" ~ep~esent only facts? To compute these const~aints the compute~ inspects the t~ee-shaped sea~ch space of Fig ?d . At each node the~e lS a pai~ "<Ci,Til", "Ci" being a const~aint to be satisfied, and "Ti" being a sequence of te~ms to be e~ased. At the ~oot of the t~ee we have the pai~ "IC~;T;>", whe~e "Co" is empty and the sequence "To" is the term which constitutes the P~olog question. If at a given node the const~aint "Ci" is not satisfiable, this node becomes a dead end. If not, the~e will be as many a~~ows emanating f~om this node, labeled "ICi,Til", to nodes labeled "(Ci+s,Ti+sl"; as the~e a~e ~ules. In this pa~ticula~ example the~e a~e seven a~~ows . The const~aint "Ci+s" is obtained by adding to the const~aint "Ci" the const~aint "{b 0 =a 0 }", whe~e "b 0 " is the fi~st element of sequence "Ti" and "a0 " the left membe~ of the ~ule which one attempts to apply. "Ti+s" is obtained by ~eplacing the fi~st element of "Ti" by the ~ight membe~ of the ~ules which is being applied. Befo~e conside~ing a ~ule, it is impo~tant to ~ename vahables (e.g. by adding p~imesl, so that the ~ule has no va~iables in common with alr-eady e:.:i sti ng var-iables . constr-aints "Ci" which which can be r-educed; in reduced forms just below ar-e satisf iable ar-e this case~ we place them. The answers The those their are subpar- ts of the r- educed constr-aints "Ci ' s " appear-ing in nodes which cannot longer- be e:-: panded, since their ''T i 's" are empty. The four va lid answers are found in Fig 7c .

The best way of expl a ining in detail how a Prolog program r uns on a computer is to idealize this computer by a si mple abstract machi ne. We call our abstract machine "the F'rolog clock" because its basic function is t o keep track of the time . This machine consists of :

1. a cell "i" , containing a non negati ve integer representing the time;
2. 2 . an infinit y of cells · ·c0 ~C 1 ,C 2 ~···'' containing the constraints to be satisfied at times 0,1,2, ... ;
3. 3 . an infinity of cells "T0 ,T1 , T2 , ··. " containing the sequences of terms which, at times 0,1,2, ... , remain to be erased;
4. an infinit y of cells "R0 ,R1 ,R2 , ··· " containing the numbers of the rules which have been chosen at times 0 ,1,2, ...

The rules are numbered "1" to "rma:·: " and the machine has means of acessing them.

The machine ' s operation is depicted by two concentric circles in Fig 8: one of them is swept clockwise as time i ncreases by one unit, the other is swept in the opposite directi on as time decreases by one unit . the time progress1on one- way br idges which other. It is possible to reverse by crossing one of the two link one c ircle to the The execution of a Prolog program consists of answer ing a question represented by a term . All answers to be computed are constraints by which the term represents specified facts. We start with the pair "<C 0 ,T 0 >", "C0 " being empty and the sequence of terms "To" being reduced to the term that constitutes the question. Each turn around the outward circle increases the current constrai nt "Ci" and transforms the sequence "Ti" · Note tha t if the r ule already contains a constraint "B", this constraint is added to the current set of elementary constraints. The process stops as soon as a non-satisfiable constraint is generated, or the sequence "Ti" becomes empty : in these cases, we backtrack to the "past", to tr y other rules . . On the fly, if "Ci" i s satisfiable , an answer is printed .

In fact, the above process corresponds to sweeping the tre~-shaped search space of Fig 7 , from top to bottom and from left to right, the time "i" being the level of the visi ted node.

The two programs in sections 9 additional examples of more programs. and 10 provide intricate Prolog In Moliel"e's play , "Le Boul"geois Gentilhomme", a boul"geois who wants to act as a lol"d <gentilho~me) compliments a noble woman (mal"quisel:

"Beautiful mal"quise, you!" beautiful

eyes make me die of love."

Let us constl"uct all of the compliment's possible val"iations, as the bou!"geois tl"ies to do in the play . The sentence is fil"st decomposed into five pal"ts, which a!"e gi ven in Fig 9a, each pal"t made up fl"om one, Ol" a few unsepa!"able wol"ds. Stal"ting fl"om an initial sequence with these five components we pl"oduce all val"iants by genel"ating al l the pel"mutations of the sequence.

We fil"st have to choose a way of coding a by a tl"ee. Since it is necessal"y to notation fol" the empty sequence, the "3,7,2" is l"epl"esented by the tl"ee in sequence have a sequence Fig 9b.

Also, since each node is labeled with a sing le chal"actel", a dot, !"eadablity is improved by us ing infi }: notation: "u. v" , instead of pl"efi }: notation: ". (u,v)". To ful"thel" simplify, we omit pal"entheses whenevel" left-l"ight association is implied.

To assel"t that sequence "y" is a pel"mutation of sequence"}:" we Wl"ite "pel"mutation( }: , yl" . The fil"st l"ule of Fig 9c states that the sequence of length zel"o, that is the empty sequence, has only one pel"mutation, itself. The second l"ule specifies that, in Ol"del" to pel"mute a non-empty sequence, that is a sequence of length "n+l", we l"emove i ts fil"st element "e" and obtain a sequence "x" of length "n"; we then compute any pel"mutation "y" of this sequence "x" and insel"t the element "e" in any position of this sequence and pl"oduce the desil"ed sequence "z". To insert an element "e" in a sequence "x" and obtain a sequence "y", we intl"oduce the tel"m "insel"tion (e,x , y)" . We eithel"

insert "e'' before ":-: 11 (third rule of Fig 9c) ~ or we insert "e" in the sequence which has its first element removed (fourth rule of Fig 9cl. These four rules of Fig 9c const itute the entire permutation program.

Fig 9d presents the computer's answers to two questions :

and what are all permutations" >: " of the sequence .. 1,2,3"?

what are the values of the variables ··au, "bn, 11 C'' and 11 d" so that "2,4,c,d"

is a permutation of 11 3,a,l,b"?

Finally in Fig 9e, we ask the question producing the 120 stylistic variants that the "bourgeois gentilhomme" might have said'

10. SEND MORE MONEY

The purpose of this example is to c lassical cryptarithmetic puzzle: different digits to the 8 "S,E,N,D,M,O,R, Y", such that "SEND+MORE=MONEY" becomes va lid. To solve a assign 8 letters the sum do so, we introduce in Fig lOa' the four carry-overs "rl", "r2", "r3" and "r4" which can be null and which have to be added to each column of the sum .

The program consists of the three parts shown in Figs lOb, 10c and lOd. In Fig lOd, the table of sums up to 20 i s programmed : any elementary school student knows this table by heart but the machine has to compute it over and over again since it only knows how to add ''1" to a number . We use "plusb: , y ,z l" to mean ":.:+y=z". Each number. is represented by two digits, with a dot between them (we use infix notation as in Fig 91. Fig lOc presents the definition of a sequence without repetition (note that the last rule of Fig lOc contains a non-empty constraint!. In Fig lOb, it is stated that to compute a solution it is necessary to assign distinct values to the letters "S,E,N,D,M,O,R,Y", and that, in each column of the sum, a property called "admissible" , has to be satisf ied between the carry-over, the three letters of the column and the preceding carry-over. Of course, this propert y "admissible" is defined using the property "plus" and the property "plus-one". Si nce the numbers "SEND", "MORE" , and "MONEY" should not begin with the digit 0, an inequality ~onstraint i s added to the first rule of Fig lOb. In Fig lOe, we challenge the computer to provide us with the three mystery numbers .