PAPE: An On-Line System for Inferring Procedures from Sets of Their Traces

ABSTRACT

Many learning-by-example problems can be viewed as infering structured non recursive procedures from sets of their traces knowing the basic functions and predicates, used to write them. The on-line system PAPE does this as follows, an example (data + trace) is given. PAPE first checks whether the already learned procedure gives the same trace with the given input data. If not, the trace is trans­ formed into a procedure body (in O(tp) time, where t it is the length of the trace, and, p an integer depending upon the procedure and the basic functions and predicates), and then merges this body with the actual one to get the new procedure body.

0/ INTRODUCTION

Many problems of learning from examples (e.g.: drawing objects on a screen (V 2) , complex actions of an industrial robot, commands of a computer sys­ tem, queries of a database .·· ) can be viewed as infering non-recursive procedures from sets of their traces knowing the functions and the predicates used to write them.

These applications suggest that we can restrict ourselves to non-recursive procedures written in PASCAL- like language in which

• there is no composition of functions in an assignment,and, of a function and a predicate (of a loop, or, of a conditional).
• all constants are introduced by an assignment (x :· constant).
• the sets of identifiers of variables, and, of formal parameters of the procedures are disjoint.
• all procedures to synthesize are supposed structured.

1/ THE SYSTEM PAPE

We describe here a program named PAPE [ V I] , which, like BIERMANN and KRISHNASWAMY'S program

F-Y. VILLEMIN

Departement de Mathematiques et Informatique CNAM, 292 rue Saint-Martin

75141 PARIS CEDEX 03 (FRANCE)

AUIOPROGRAMMER [BiK] , is an on-line system lear­ ning a non-recursive procedure (a structured one for PAPE) from a set of this traces, while SIKLOSSY and SYKES' program SYN [SiS] infers a recursive procedure from a single trace. But, unlike AUIOPRO­ GRAMMER which requires from its programmer symbolic traces (sequences of assignments) and, the predica­ tes for loops and conditionals at the places they are used, PAPE, like SYN, works automatically once the set of traces and the basic functions and pre­

dicates have been given.

An example E for PAPE is a 4-tuples E · (N, D, R, I) where N is the name of the procedure to syn­ thesize, D the input data (actual parameters), R the output data, and, T the trace (a set of pairs

of a variable and its value) free of errors.

All examples are supposed correct.

PAPE is mainly composed of two functions AI and A2.

It works as follows :

An example E is proposed.

-If E is the first one, PAPE creates a proce­ dure-head with identifier N and AI (E) as a body.

-If not, PAPE starts with an execution of a call of N with D as actual parameter. If the trace obtained matches I, then PAPE stops (awaiting for some other example if ·any). Otherwise the partial body AI (E) is compared and merged with the actual body of N by A2.

AI has a worst-case time complexity in O(tp) where t is the length of the trace I, and, p is an integer depending upon the procedure to synthesize, and, the sets of functions, and, of predicates.

In the following the behaviour of PAPE will be

described on an example

Suppose we wish to learn the procedure MULTIPLY which performs the multiplication of two positive integers using F · ( + (addition), pred (predecessor function), /2 (integral division by 2), :t 2 (multiplication by 2)] and P · { · 0, even) respectively as sets of functions, and, of predica­ tes .

We have in mind a procedure of the form Procedure MULTIPLY (MI, M2/N) ; ~Z; X :· Ml; Y :· H2; Z :· 0 while X · 0 do if even X then X ·· X/2 Y :· Y * 2 else X ·· X-1 z :· z + y fi od N:'!'Z

2/ THE SYNTHESIS FUNCTION AI

AI is composed of three functions. Their beha­ viours will be shown on an example :

• E 0 · (MULTIPLY,( 18,4) ,(N·72) ,((X,18)(Y,4)(Z,O) (X,9)(Y,8)(X,8)(Z,8)(X,4)(Y,I6)(X,2)(Y,32)(X,I) (Y,64)(X,O)(Z,72)(N,72))).
• -First All generates a set of symbolic traces together with assertions (conjunctions of true pre­ dicates) : each pair (X.,a.) ofT is replaced by J J the set of all assignments X.:·Fm(X 1 , ··· ,X) when J n F (b 1 , ··· ,b ) · a.,b. being the value of X. before m n J 1 1 (X., a.). J J

If we call Ml and H2 the formal input para­ meters, we get :

AI(E 0 )·(X:-t·ll [even(X)} ·; Y:·H2 {even(X)I\even(Yfr Z:·O {even(X)"even(Y)I\.Z·O}; X:·X/2 {even(Y) ,..z.oj; (Y:·Y+Y,Y:·Y:t2,Y:·pred X) {_even(Y)I\Z·OJ; (X:·X+Z,X:-pred X, X:·Y) {even(X) 1\even(Y)I\Z·O}; (Z:·Z+Y, Z:·Z+X, Z:·Y, Z:·X) {even(X) 1\even(Y)I\even(Z)} ; (Y:·Y+Z, Y:·Y+Y, Y:·Z+Z, Y:·Y:t2, Y:·Z:t2) { even(X) 1\even(Y)/\even(Z}; X:·X/2 {even(X)I\even(Y)I\even(Z)] ;(Y:·Y+Y, Y:·Y*2) {even(X)I\ even(Y) 1\even(Z)} ; (X:·X/2, X:·pred ·x) (even(Y)Aeven(Z)} ;(Y:·Y+Y, Y:·Y:t2) {even(X)I\.even(Z)} ; (X:·X/2,X: ·pred X) { X·O 1\ even(Y)I\even(Z)}; Z:·Z+Y {x·OI\even(Y)I\even(Z)j N:·Z {x·OI\even(Y)I\ even(Z)})

This is a purely combinational process.

• Then A12 yields a single symbolic trace. This done by using :
• a/ The "nice sequence" algorithm (v I J , (A sequence is said "nice" if it has a partltion in which each part has a common initial subpart and the remaining is either empty, or a nice sequence, or a sequence of patterns having at least one occurrence in some other part. This notion captures the syntactical properties of the symbolic traces of an iteration). The assertions being not modified we get :

(X:·MI; Y:·H2; Z:·O; X:·X/2; (Y:·Y+Y,Y:·Y:t2); X:·pred X; Z:·Z+Y; X:·X/2;(Y:·Y+Y,y:·Y:t2);X:·X/2; (Y:·Y+Y, Y:·Y:t2);(X:·pred X, X:·X/2);(Y:·Y+Y,Y:·Y*~; X:·pred X; Z:·Z+Y; N:·Z)

This algorithm does not decide when sequences are equally "nice". Heuristics are used to get a single trace.

• b/ The "regularity" heuristic [v 1] (patterns are choosen to give either the longuest, or, the more repeating subsequences) :X:·X/2 is prefered to X:·pred X since X:·X/2 is always followed by (Y:·Y+Y, Y:·Y:t2), and, X:·pred X by Z:·Z+Y,
• c/ The "insane" heuristic [Sik, V 1] (the most general schema is choosen, e.g. : the one having the more occurrences of variables): Y:·Y+Y is prefered to Y:·Y*2·
• Finally Al3 introduces loops by first cutting Al2 cutting AI2(AI (E)) into the initial, the "nice" and the final sequences, and, retaining only assertion between subparts : ((X:·MI; Y:·H2; Z:·O) {even(X) 1\.even(Y) 1\Z·O); ((X:·X/2; Y:·Y+Y) {even(Y) 1\ Z·O}; (X:·pred X; Z:·Z+Y)) .(even (X)I\even(Y)Aeven(Z)} ((X:·X/2; Y:·Y+Y)) {even (X)I'\even(Y)I\even(Z)} ; ((X:·X/2; Y:·Y+Y)) (even(X)I\even(Y);'\even(Z)} ; ((X:·X/2; Y:·Y+Y) {even(Y) 1\even(Z)} ; (X:·pred X Z:·Z+Y)) {X·O/\.even(Y)I\even(Z)}; (N:·Z) {X·O/\ even(Y)I\even(Z)j ) then, loops are introduced, by using the "pumping lemma" heuristic [Hie, V 1) (an iteration s 0 ; while do S od is infered from occurrences of subsequences of the form s 0 ;s, ... ,S) in two steps starting from the inside, the predica­ te being the largest common predicate included into all the assertion preceding the subparts and into the complement of the assertion following the last occurrence of this subpart : AI (E 0 ) ·(X:·MI ; y:·H2; Z:·O){ even(X) 1\even(Y)I\ Z·O'l ; while , X·O do X:·X/2; Y:·Y+Y;while1 even(X) do X :·pred X; Z:·Z+Y ~ ~ \X·OI\even(Y) 1\even(ZU; N:·Z)

3/ THE MERGING FUNCTION A2

• A2 is composed of three functions, only A21 is fully worked out :
• -First A21 looks to places where AI(E)differs from P, the actual body of N, and, makes a parti­ tion of both AI(E) and P between common and diffe­ rent parts, and, then infers a new body for N. There are three cases :

• a/ They differ on a assertion, or, a predica­ te of a loop, or, of a conditional, A21 replaces it P by their disjunction.
• b/ They differ on a sequence of assertions and instructions, starting by an assertion, A21 repla­ ces this part in P by a conditional with predicate being the difference of the two assertions, and its assertion being the largest common one. Suppose the body Pis : P·(X:·MI; Y:·M2; Z:·O; {even(Y)I\ Z·O]; while 1 X·O do X:·pred X; Z:·Z+Y; while even(X) do X:·X/2; Y:·Y+Y od od { X·OI\even(Y)Aeven(Z)};­ N:·Z)

This body P together with AI(E 0 ), from above,yields: A21(P,AI(E 0 ))·(X:·MI; Y:·M2; Z:·O(even(Y)I\Z·Oj; if even(X) then while, X·O do X:·X/2; Y:·Y+Y; while even(X)do X:-pred x; Z:·Z+Y od od else while X·O do X:·predX; Z:·Z+Y; while even(iC) do X:=x?"r; Y: ·Y+Y od od fi {X·O 1\even("Y')''\even(Z)j T"N: ·Z)

• c/ They differ on a sequence of instructions and assertions, not starting by an assertion : this is a filtering error due to Al2. This is taken care by A22, a backtracking error recovery function (on all examples looked after, we haven't met such an error).
• Then A23 "normalizes" the body of N, by doing a symbolic execution and another program infe­ rence to get a "better looking" body.

4/ CONCLUSIONS

We can prove that the procedure M synthesized by PAPE (with A 23) from a set of examples E 0 ,E 1 , ·· has the following properties :

• For any example E. of the set, the execution of M with the input data 1 D. produces the trace T. of E.. 1 1 1
• Let N be the actual procedure to synthesize, consider any infinite enumeration of the examples of N, E 0 , E 1 , ··· , then there is a finite k such that if M is synthesized from the set E 0 , E 1 , ··· ,~. Then for any i ) k, M executed with D. produces T. of E .· (But it is impossible to determine k). 1 1

So far only parts of PAPE have been implemen­ ted: A II, A 12, A 13 and A 21. Many procedures in arithmetics have being partially synthesized. On the example given here, to get A I(EcJ took 5.7. seconds on an IBM 370/168 in LISP I .5. The full system described here is being implemented in V-LISP on a DEC VAX 11/780.

ACKNOWLEDGEMENT

We thank Ms A. ALMANDIN for the typing.

5/ REFERENCES

• BiK BIERMANN A.W. and KRISHNASWAMY R. :

Constructing programs from example computa­ tions - IEEE Trans. on Software Engineering V SE-2- N· 3 (1976).

Hie MICLET L. inf6rence de grammaires r'guli~res - Th~se de Docteur-Ing,nieur, ENST- PARIS, DEC 1~9

• Sik SIKLOSSY L.

The synthesis of Jrograms from their proper ties and the insane heuristic in Proc. 3rd Texas Conf. on Computing Systems- Austin, Texas, 1975.

Automatic programming synthesis from exam­ ples problems in 4th IJCAI, Tbilissi, URSS,

• SiS SIKLOSSY L. and SYKES D.A. 1975. -
• V I VILLEMIN F-Y

Le systeme PAPE- rapport CRIP-02-CNAM,I981

• v 2 VILLEMIN F-Y :

Le systeme AGE- rapport CRIP-03-CNAM,I981

APPENDIX

The "nice sequence" algorithm, on A II (E 0 ) above, behaves as follows

• it first scans the sequence, ignoring the assertions, looking for the first set of assignmen~ i.e : (Y:·Y+Y, Y:·Y*2, Y:·pred X).

then checks whether a subset of it has repea­ ting occurrences in the sequence, here (Y:·Y+Y, Y:·Y*2). This subset is setted apart. If it has more than one element, it checks whether there is a single repeating subsequence formed with either the preceeding, or the succeeding assignment, or both, and so on, unti 1 nothing repeats, or, .comes up with this single subsequence.

- and then, does the same for the next set.

At the end, only setted apart subsets are retained, and, repeating subsequences are paren­ thesized.