SISP/1: An Interactive System Able to Synthesize Functions from Examples

SISP/1 AN INTERACTIVE SYSTEM ABLE TO SYNTHESIZE FUNCTIONS FROM EXAMPLES

Jean-Pierre JOUANNAUD FRANCE Maitre-Assistant a l'Institut de Programmation Universite Paris VI 4, Place Jussieu 75005 PARIS

Gerard GUIHO FRANCE Maitre de Conference - Laboratoire de Recherche en Informatique Universite Paris Sud 91405 ORSAY

Jean-Pierre TREUIL Chercheur - Laboratoire de Recherche en Informatique Universite Paris Sud 91405 ORSAY

FRANCE

The research presented in this paper is supported by IRIA-CESORI under contract number 76.

ABSTRACT

SISP/1 is an interactive system whose goal is the automatic inference of LISP functions from a finite set of examples {(xi, f(xi))} where xi is a

list belonging to the domain of the function f we want to infer. SISP/1 is able to infer the recur­ sive form of many linear recursive functions and its stop-condition. SISP/1 tries to work with one example only. When it fails, it asks for new ones: using then a method of generating new partial sub­ problems, SISP/1 is able to perfect its generated recursive function until it gets a correct one.

I. INTRODUCTION

In this paper we describe the system SISP/1 whose goal is the automatic inference of LISP func­ tions from a finite set of examples {(x., f(x.))},

~ ~

where x. is a list belonging to the domain of the functiofi f we want to infer.

The problem originates from a more general one: how to build a "Learning-Question-Answering­ System" (L.Q.A.S.) using a functional method to provide an answer to any given question. The me7 thod we propose in SISP/1 is naturally well adap­ ted to the L.Q.A.S. we are developping [6], [7] .

In the field of "Automatic Programming from Examples", an important piece of recent work is THESYS by SUMMERS [5]. The major result of this work, is the following: using a small number of well chosen examples

{(NIL, f (NIL)), ((A), f ((A))) .·. } THESYS is able to infer a recursive expression ~ equivalent to f for every x belonging to the domain of f.

Only a small class of functions can however be obtained by Summers's method; which works by loo­ king for a recurence relation between representati­ ve predicates pi of the given input structure and

for a recurence relation between the map functions mi providing the given outputs from the given in-

puts. Then, using a fixed point theorem, ~ is cons­ tructed.

Although Summers's method is very powerful it has four important drawbacks:

I.- The constructed expression~ is nece.ssarily recursive: for instance the identity function will be infered by ~ (x) = if X = NIL then NIL

else CONS (CAR(x), ~(CDR(x)))

2.- THESYS needs well chosen examples, which in particular must contain the stop condition of the recursive function~. For instance, the construc­ tion of the function REVERSE requires the following set of examples:

{(NIL+ NIL), ((A)+ (A)), ((A B)+ (B A)), ((ABC) + (C B A))}

. 3.- The function to be constructed has to present only one "iterative level". For instance, THESIS fails to construct a correct function corresponding to the example: (P Q R S) + (P P Q P Q R P Q R S). 4.- When THESYS has to solve a difficult problem, it does not try to generate a partial, simpler problem for which it could either find a correct solution or perhaps use a knowledge previously stored in a data base by the system itself. Thus, THESYS cannot be efficiently used in a L.Q.A.S. without important modifications.

The method we propose ·in this paper is very uifferentdn particular, it has the built capacity to use a Professor in interactive mode. It does not lie yet on any theorical groundwork, but allows us to overcome some of the previous drawbacks, al­ though new ones appear:

- recursion is not automatically infered by the synthesis algorithm; for instance, using the exam­ ple ((ABC)+ (ABC)), SISP/1 infers the function ~ : · ~ (x) = x for any x.

- for some "simple" functions, SISP/1 needs only one example (x, f(x)).

In the case where a recursive expression is infered, the stop condition is then found by SISP/1 itself. However the list x must be long enough to be re­ presentative of the function f. For instance, REVERSE is obtained using the only example ((A B C D) + (D C B A)), but is not obtained with ((ABC)+ (C B A)).

- when the function f is "more complicated" SISP/1 fails to construct a correct function with only one example and it then tries to work with two examples. -when the function f is "much more complicated", SISP/1 generates a new partial simpler problem (y, g(y)) where y is defined in terms of x and g(y) is defined in terms of f(x). To solve this new problem, SISP/1 sometimes needs a new example (x', f(x')) which is used to deduce an example (y', g(y')). The interaction is only used in the sense of asking for new examples, when necessary. SISP/1 is thus extensible and has the potentiality to use a self constructed knowledge data base.

Some objections can be raised to our interac­ tive method:

- when a function f needs several examples to be infered, the professor sometimes has to give an appropriate sequence of examples.

- we do not exactly know the class of functions which SISP/1 is able to infer. However, it seems to be much larger than THESYS one. For instance ((P Q R S) + (P P Q P Q R P Q R S)) is infered by SISP/1 using only one example whereas the HALF function ((P Q R STU) + (P Q R)), which is infered by THESYS, requires two examples by SISP/1. In fact, we hope that SISP will be able to infer a larger class of linear recursive functions.

II. GENERAL DESCRIPTION OF THE METHOD

I ·- ~!!!!S!!!!S~

SISP/1 infers functions defined on character strings "ABCD ..· " which will be represented by the list (ABC D ..· ).

SISP/1 synthetizes LISP-functions built with the following basic functions, described here by examples:

LCAR: (A B C D) ~ (A) CDR: (A B C D) ~ (B C D)

LRAC: (A B C D) ~ (D) RDC: (A B C D) ~ (A B C)

CONC: (A B), (CD)~ (ABC D)

CONCT: (A B), (C D), (E F) ~ (A B C D E F)

PREF: (B C), (A B C D) ~ (A) [Prefix of (B C) in (ABC D)]

SUFF: (B C), (A B C D) ~ (D) [Suffix of (B C) in (ABC D)]

and a control structure using COND and NULL.

2.- ~~!i~~-2E_!YE~

A type is a set of lists which can be defined by rules which are summarised as follows [6]: a) the set of known inputs "x" and the set of out­ puts "f(x)" of the function f to be synthetized are types.

b) if X is a type and f a LISP function, then the set of outputs of f restricted to X as input is a type.

1. if Y is a type and g a LISP function then the ·

set X of x such as g(x) E Y is a type.

3.- ~~~~!!!e!!~!!-E!!!!~E!!

Let f be a function to be synthetized and (x, f (x)) an example of "input-output" of this function.

SISP/1 uses a general heuristic to create an expression of the function: a) segmentation of strings x and y = f(x) into

three consecutive segments such that:

CONCT (px, c, sx) ~X_

CONCT (py, c, sy) ~ y

where c denotes the larg-er string common to x and y, px and py denote the prefixs of c in x and y, sx and sy denote the suffixs of c in x and y. b) building of relations between these segments.

• A "Segmentation Pattern" of (x,y), for all x andy, is defined as the network shown in figure 1.

~e can see on this network: - seven nodes representing types respectively as­ sociated to the strings x,y,c.,px,py,sx,sy. - twelve relations between nodes. Each relation consis~of a function and a scheme (I 1 , I 2 , ... , In~ J) ·which indicates the input nodes I 1 , I 2 , ... , In in this order and the output node J. This order is represented on the network by a double arrow.

Note that functions FX, FY, GPX, GPY, GSX, GSY are built by SISP/1 using the basic functions LCAR, CDR, LRAC, RDC, and the composition rule. They are choosen of the less possible -complexity (the smallest number of basic functions).

In some cases, the segmentation pattern is simpler:

• -when one or several strings are empty (NIL), .. the associated nodes are suppressed from the pattern.
• when two strings are equal, the associated

nodes are . joined together. For instance, if x and y are the same, the pattern is reduced to one node; if x and y have no common part, the pattern is reduced to only two nodes.

• 4.- ~Y!!£h~~i~_fE~~-~~~-~!!~E1~ The synthesis consists of three steps: a) SISP/1 generates a network (called a "Segmenta­ tion Structure") by the following process:
• (I) Generate the segmentation pattern of (x,y),The generation gives the two sets of pairs: {(px, py), (c,py), (s'K, py)} {(px,sy),(c,sy),(sx,sy)}
• As long as py and sy are not empty, choose one pair in each set by a heuristic way; for each of these pairs, rename it as (x,y) and go to step 1. b) SISP/1 looks at the segmentation structure for a lattice in which the minimal and final nodes are respectively X andY (that is x andy types). This lattice is stepwise constructed using Algorithm I, defined as follows:

Definitions:

• LAT is the constructed part of the lattice at any step (except in the final step, LAT is not a lattice).
• an incomplete node of LAT is a node such that the relation ending at this node (in LAT) owns some entries which are not connected to X. These nodes are called unsatisfied entries.
• BEG (Z) is the set of nodes in LAT which are less than Z and which are not unsatisfied entries.
• P is a "path" from BEG (U) to V, where U and V are nodes of LAT, if P is an oriented path starting from one node belonging to BEG (U) and ending at V. This path may contain incomplete nodes together with their unsatisfied entries. Example of LAT:

Nodes 6, 7, II are incomplete nodes Nodes 12, 13, 14, IS are unsatisfied entries All others nodes are complete nodes. BEG (9) ={X, I, 2, 7, 8}

Algorithm I:

I. LAT + X 2. Look for a path P between X and Y.

3. Add path P to LAT.

4. If there is no incomplete node in LAT then stop

else select the minimal one and call it N . ~can be demonstrated that Algorithm I 1 generates a set of incomplete nodes which is totaly ordered on LAT).

1. Let Yi be one unsatisfied entry of node Ni 6. Look for a path P between BEG(N.) andY .. Let X. be the origin of P on BEG{N.) and 1 try t6 detect a recursivity betweefi X. and Y. using Algorithm 2. 1 7. G6 to step 3.

It follows from algorithm I that when Algorithm 2 is called, a part of LAT has the following structure:

Sublat

~~e~~es;~!~~o~: ~~::~~~~~!dt~0~:.a lattice, and Yi Algorithm 2:

1. If no path from X. toN. (in sublat) matches a-subpath of P (ifi the ~ense of an identi­ cal sequence of operators) then stop algorithm 2, ---- else let X.+l ~ N.+l be the subpath of P which has Eeen mafcned.

The above structure is changed to:

Sublat

1. If the segmentation structure does not con­ tiin a lattice starting in X. 1 , ending in 1+ N.+l and analogous to sublat then stop algorithm 2 else assume the following re­ cursion:

'P (x)=h[v(<P(u(x))), sublat(x)J

• depending on the order of arguments of h. 3. Find a primitive stop condition of the re­ cursive function <P as follows: match the operators of path P from X. to N. in . 1+1 1+1 the segmentat1on structure, then from X. t to N. ~ and so on, until it fails. 1+ . 1+ . Assume 1 fa1ls rom X. toN .. F1nd a path w from X. toN .. The ~rimitfve stop con­ dition iJ assu~ed to be:

1. Reduce the primitive stop condition as fol­ lows:
2. remove Sublat from LAT.
3. if a relation from Nkto Nk for every k -- . +I , isk <j, cannot be found in the segmentation structure, then set P + (Xi~ Ni) and stop algorithm 2 else let r be the found relation. ----
4. find k, the smaller non negative integer such that wk = rk (w(x)) is not a fixed point of equation:

k

.h [sublat (u (x)), v(r(wk(x))) ] =wk(x)

for every x EX ..

J

d) Set P...,__(x.--4N.)

with <P(x) =~!£ x E uk (Xj) then zk(x)

1

1

/else h [sublat (x), v(<P(u(x))) ]

wh~re zk equat1on: is solution of the following

Remark To reduce the primitive stop condition, the following process is iterated: Suppose the last stop condition is

Using the to calculate <P wing figure: functions u and r, it is possible (x), X EX., as shown on the follo­ J

which means, if the correct answer w(x) is obtained that w(x) is a fixed point of the last equation. It thus follows that there exists a function z such that:

Thus now the stop condition is:

5.- §~gEh~~i~_fE2~-E~2-~~~~El~~

Let us suppose that after a first example, SISP/1 generates a function which fails on a second example. Let the two examples be (x,y) and (x' ,y'). The principle is always to build a structure from the generation of segmentation-patterns; SISP/1 here generates the segmentation patterns associated with the ini~ial pairs (x,x'),(y,y'),(x,y),(x',y') and goes on 1n the same way as in the first method.

SISP/1 then tries to find a three parts split­ ted path from X to Y: -a path from X to X'. -the function <Pitself from X' toY'. -a path from Y' toY.

R~marks: -using th~s technique, SISP/1 looks expli­ C1tely for a recurs1ve form of the function <~'· - when unsatisfied nodes are remaining in the path, SISP/1 generates sub-problems which are to be solved either by algorithm I or again by using one ~ore example when algorithm I fails (3 bis]. ~or 1nstance, let Y 1 be a remaining unsatisfied node 1n the path:

SISP provides the following expression of ~:

where ~ is a sub-problem to be solved by SISP/1 and where w(x) is the function which has been found by algorithm I working on only the example (x',y'). This stop condition can then be reduced as explai­ ned in algorithm 2.

III. PRACTICAL EXAMPLES

I. Let us use our method to find the REVERSE function. The input (A B C D E) is given to SISP/1: it does not know the answer and asks the Professor who returns: (ED C B A). SISP analyses input and output and generates the segmentation structure indicated in figure 3.

SISP looks then for a path from the Ques­ tion Q containing the list (A B C D E) to the answer R containing (E D C B A) and finds the following one:

Looking for the unsatisfied entries, SISP finds r 1 . It looks again for a path from BEG(R) to r 1 , and finds the following one:

SISP now examines both CONC) of the first one (CDR-LCAR-CONC) of the paths. The mapping (LCAR­ matches into the mapping second one. This statement is sufficient to infer a recursive expression~:

SISP has to still find the stop condition. Mat­ ching the three operators CDR, LCAR, CONC with the structure, it remarks that it can apply CDR on type q 3 giving t 5 but cannot apply LCAR on type t 5 . SISP/1 thus knows that the stop condition is to be found in this part of the structure:

SISP/1 tries now to find a new binding of the path from t 5 to the unsatisfied entry of r 3 which happens here to be identical to t 5 . It finds the trivial one and generates the primitive stop condition:

SISP now has to reduce the stop condition, using the following mappings:

Assuming that CDR ((E)) NIL~ RDC((E)) NIL is the first reduced stop condition, SISP cal­ culates now ~(x) for every x belonging to t 5 :

using the new stop condition: ~(E) = CONC [NIL, (E)]= (E) which here gives the correct answer.

The process cannot be performed further, because CDR(CDR((E))) does not exist. The function generated by SISP is thus:

that is the usual REVERSE.

2. The second example we display now needs more material than the first one since two couples (input - output) are necessary. Let HALF be the f unction to synthetize:

- first couple: (A B C D E F G H) ~ (A B C D)

From this first example, SISP/1 constructs the following structure:

The relation ~:Q' ~ R' found here is thus ~(x) = RDDDDC(x).

The professor gives now the following input: (ABC DE F). SISP uses~ to answer (A B), which is false. The professor then gives the correct answer: (ABC DE F)+ (ABC).

SISP then generates the structure displayed on figure 3. Assuming that ~· can be obtained from Q" using the correct function ~ to be synthe­ tized, SISP, as explained before, uses the follo­ wing path from Q' toR':

The problem is now to find a path from BEG (R 1 ) to SR. The simplest one which is found here is:

it follows that ~(x) = CONC [~(RDDC(x)), LCAR(SUFF [~(RDDC(x)), RDDC(x)])J with the trivial stop , condition:

SISP now has to reduce this stop condition using the following mappings:

Assuming that RDDC ((A B C D E F)) = (ABC D)

~ RDC ((A B C D)) = (A B)

SISP computes now ~(x) for every x belonging to Q":

~((ABC DE F)) = CONC [~(RDDC((A BCD E F)),

LCAR(SUFF [~(RDDC((A BCD E F)),

RDDC((A B C DE F))])]

= CONC [~((A B C D)),

LCAR(SUFF [~((A B C D)), (A B C D)]) ]

= CONC [(A B), LCAR(SUFF [(A B),

which is the correct answer.

The primitive stop condition can thus be reduced to:

where RDDC is the solution of the following equation on -z

This process is recursively applied and stops when RDDC ((A B)) = NIL. At this step, we obtain the function HALF defined as follows:

IV. LIMITS AND PROSPECTS OF THE METHOD

I ·- ~!2!1!~£!!

SISP/1 is already able to synthetize most of the functions given in SUMMERS [5] and HEDRICKS [2] in particular it synthetizes the following ones by using algorithm 1:

• (A B C D E) + (E D C B A)
• (A B C D E) + (A X B X C X D X E X)

(A B C D E) + (A A B B C C D D E E)

(A B C D E) + (A A B A B C A B C D A B C D E)

By using two or more examples it synthetizes: ·

(A B C D E F G) 7 . (A A G G B B F F C C E E D D)

• (A B C D E F G H) + (A B C D)

(A B C D E) + (E D C B A E D C B E D C E D E)

(ABC D)+ (DC B A·C B ABA AD C B C B B DCC D)

(A B C D E) + (A B B C C C D D D D E E E E E) (A B C D E F G H) + (D C B A H G F E) (A B)+ (A A A A A A A A)(cube of the entry length) (ABC D)+ (A A A A A A·A A) (half square): such a way is not always easy to use, as we shall see now:

- assume SISP has to synthetize the HALF function using the previous example (A B C D E F G H) + (ABC D). Algorithm I fails and the professor gives as second example:

SISP here generates the following HALF func.tion: ~(x) ·tif x = NIL then NIL

which is mu h simpler than previous HALF function. This simplicity was however found by the professor who gave better examples.

- assume now that SISP has to synthetize a func­ tion using the example

(ABC DE)+ (A B B CCC D D D DEE E E E). Algorithm I fails and the professor gives as second example : (ABC D)-+ (A B B CCC D D D D). SISP generates the following functions:

~(x) ={if x E Q" then R"

else CONC [~(RDC(x)), 1/l(x)J

where 1/l(x) is bound to the following subproblem:

(A B C D E) + (E E E E E)

Algorithm I fails then to provide a correct func­ tion 1/1 and the professor now has to give the two particularly well choosen examples:

(B C D E) + (B C C D D D E E E E)

(B C D) + (B C C D D D)

they allow SISP to generate a new appropriate example in order to synthetize a correct 1/1: 1/l(x) ={if x = NIL then NIL

else CONC [Vi(CDR(x)), LRAC(x)]

the stop condition of~ is then found:

if x = NIL then NIL

the generated function ~ will thus be given by the linear recursive system ~

These two last examples show the main im­ portance of good examples. We hope however that it would be possible to use "bad examples" joined together with a unification process, in order to improve the given "bad examples".

2.- Limits

- with th;-~;~;ption of stop-condition, the func­ tions generated by SISP do not use predicates in their definition . Thus the function:

cannot be synthetized by SISP. This problem is attacked in [6].

- SISP/1 requires a good sequence of example in order to use the second technique. They have to be of decreasing length and consecutive. - SISP/1 only works on atomic lists.

V. CONCLUSION

In summary, the described method consismof constructing a structure from an adequate set of examples {(xi, ,f__{_xi))} and in extracting from the structure a lattice which represents an expression of the function f, SISP is a LISP program working on PDP 10 using VLISP 10 [J ] , Future developments will tend to make SISP able to:

• define and store self contained problems in its memory,
• recognize that a partial problem has already been encountered and solved,
• improve the professor's bad examples in order to be able to solve partial problems which have never before been encountered,
• synthetize n-any functions (the two presented techniques can easily be generalized).

VI. BIBLIOGRAPHY

• [I ] GREUSSAY P., at all: "VLISP 10. Reference manuel". Rapport interne Univ. Vincennes.
• [ 2] HEDRICKS C.L.: "Learning Production System from examples", Artificial Intelligence Jour­ nal n· 7, January 1976.
• [ 3] JOUANNAUD J.P., GUIHO G., TREUIL J.P., COALLAND P.: "SISP, systeme interactif de synthese de programmes a partir d'exemples". Publication de l'Institut de Programmation, Mars 1977.
• [3bis ] JOUANNAUD J.P., GUIHO G.: "Inference of functions with an interactive system" to be published in Machine Intelligence nl 9 edited by D. MITCHIE.
• [4 ] POliL Ir.: "Bi-Directional and Heuristic Search in Path Problems", Thesis, Computer Science Dept. Stanford University, 1969.
• [5 ] SUMMERS P.D.: "Program Construction from examples". Phd. Thesis, December 1975.
• [ 6] TREUIL J.P., JOUANNAUD J.P., GUIHO G.: "Une methode d'apprentissage de concepts, Colloque AFCET: Panaroma de la Nouveaute informatique en France·, Gif s/Yvette, Novembre 1976.
• TREUIL, J.P., JOUANNAUD J.P., GUIHO,G.: "L.Q.A.S., un systeme question-reponses base sur l'apprentissage et la synthese de program­ mes · a partir d'exemples. Publication de l'Institut de Programmation, Mars 1977.