Synthesis Of LISP Functions From Examples

Abstract

A system, called GAP, which automatically produces LISP functions from example computations is described. GAP uses a knowledge of LISP progr8.11111ing to inductively infer the LISP funct­ ion 'obviously' intended by a given 1 iopair 1 (i.e. a single input to be presented to the function and the output which must result). The system is written in R>PCORN (a OONNIVER-like extension of R>P2) and represents its knowledge of LISP procedurally.

Acknowledgements

The research reported herein was carried out with the support of the Science Research Council.

I would like to thank Pat Ha,yes, Richard Bernat and, especially, Mike Brady for their constant advice and guidance.

Section One - Introduction

Despite the fact that there are infinitely many functional extensions of the input-output ( 1iopair1 ): (ABC D)=)= ({A) (B) (C) (D)) (1) there is only one function that would be regarded by LISP programmers as the 'obviously 1 intended one, viz: (A B ---- Z) = )= ((A) (B) --- (Z)).

'l:his paper describes a program, called GAP (Generalizing Automatic Programmer), which attempts to model the LISP progr8111!1er to the extent of producing this ±'unction. When presented with iopair (1) GAP produces the LISP

±'unction:

(LAMBDA (X)

(COND ( (ATCM X) NIL)

(T (CONS (LIST (CAR X)) (SELF {CDR X))))))

(The LISP system used by GAP acts as if all LAMBDA expressions were implicitly labelled 1 SELF 1 ).

GAP can be distinguished from those automatic programmers which deduce the wanted program from the given description. These reflect a popular approach to automatic program­ ming and have, theoretically, a nwnber of advan­ tages over GAP. A deductive system can, in principle, produce a correct program - one guar­ anteed to .meet its specification. Furthermore, such a system can, if it contains a complete proof system, produce any program which can be described to it. If the description language used is general sa,y, first order predicate cal­ culus - then the automatic progralllller will be general. Unfortunately, most theorem provers are not very powerful and this limits the size o f program which can be written. This disadvan­ tage can be overcome, to an extent, by allowing the proof system to employ knowledge in the form

SYNTHESIS OF LISP FUNCTIONS FRCM EXAMPLES

Steven Hardy

University of Sussex, Falmer, Brighton, Sussex

of 'control' statements which embody an under­ standing of how to achieve proofs in the domain of program writing. A more important criticism of deductive automatic prograllllling is that the wanted program must be completely specified. This can be as difficult, and as error prone, as actually writing the wanted program. For example, the ±'unction intended by iopair (1) is described in the first order predicate calculus as:

LISTIFY (NIL) = NIL LISTIFY (CONS(X 1 Y)) = CONS (CONS(X,NIL), LISTIFY(Y))

and this is barely simpler than the corresponding LISP ±'unction.

GAP is writ ten in R>PCORN (5) an extension of R>P2 (J) that provides some of the features of CONNIVER (9). The progr~m contains a number of heuristic routines embodying knowledge about various program schelll8.8 for LISP expressions. Whm GAP is presented with an iopair these routines examine it for 1 cues 1 which suggest hypotheses about the form of the wanted expression. If an hypothesis seems particularly promising it is examined in great detail by a deductive LISP system which attempts to verify and complete it.

The cue seeking routines are stored in the R>PCORN data base, making the addition of: new heuristics extremely easy as the remainder or the program need not be altered. It can be seen that the detailed f:low of control will depend on minor vagaries of the data base controlling routines.

The complete program occupies less than J5K words of: core on a PDP-10. It takes two or three seconds of: CPU time to code the e~le given earlier.

In Section Two I explain ho .. GAP works, illustrated by a few simple examples; in Section Three there is a brief: discussion of the LISP system and in conclusion I point out some short­ comings of: the program and describe wa,ys it could be improved.

Section Two - GAP at Work

The LISP expressions that GAP is capable of producing can be described by a nwnber of program schemas · The type of recursive ±'unction to which GAP devotes most attention, called a < LISTFN ) , can be represented as:

(LAMBDA (X)

(COND (<TESTS X> NIL) (T (APPEND < FO~ X > (SELF< PARTOF X > ) <FORM X ) )) ))

This schema is completed by replacing the terms < SOOETHING X) by an expression of the appro­ priate type. ( TESTS X) denotes a Boolean expres­ sion,< FOR-t X> denotes any expression that GAP can write, and < PARTOF X > denotes an expression synth­ esised from the primitive LISP selector functions, CAR and CDR, applied to X.

The various types of expression that GAP can write can be informally described by a 'grammar'. The most general type is 1 FORM 1 ; this denotes an expression where the output is formed from the in"­ put atoms with no reference to the identity of any particular atoms in the input. This type of expr­ ession can be described:

(FORM X) ·· = (BUILD X> ( ( LISTFN >X) ( < TREEFN ).X.) ( (<FLATFN >X) (LIST< FORM X) ---(FORM X) )

The notation used is meant purely as an expl­ anatory device - it 'defines' an abstract, rather than concrete, syntax for the expressions GAP writes.

An expression of type BUILD is synthesised frccn the functions CONS, LIST, APPEND, CAR AND CDR &{!{!lied to X or NIL. For example, (APPEND X (CDR X)) is of type BUILD.

A < LISTFN >is a function with a list as input and output. The function shown in the introduct­ ion is a ( LISTFN) , though optimised for efficiency and appearance.

A ( TREEFN ) takes and returns a tree; the iopair;

((A (B) C) D) =) = ((A A (B B) C C) D D) (which GAP easily handles) would be coded as a <TREEFN).

'!he final possibility for an expression of type FORM is an application o.f a< FLATFN > to a tree to return a list - for eXIIIII.ple :

( (A (B) C) D) && tQ · =) = (A Q B Q C Q D Q )

< LISTFN)s embody an essentially iterative prooess, as they are only singly recursive. <TREEFNS)s and< FLATFN)s call themselves twice.

An expression o.f type BUILD can be described:

(BUILD X) · · (CONS< BUILD X><BUILD X>) · · (LIST< BUILD X>---<BUILD X>) · · = (APPEND<BUILD X>--(BUILD X>) :: (SElECT X> <sEu:cT x > :: = NILI (QUOTE <ATCM> >j< PARTOF x> < PARTOF X > : : = X :: = (CAR< PARTOF X>) :: = (CDR< PARTOF X>)

Once GAP has decided that an iopair is of type BUIUl the expression is found by exhaustive search - though ordered to favour expressions using APPEND.

The expression to replace <TESTS X) in the

expansion of a < LISTFN > can be described : <TESTS X > : : = < FRED X > :: (OR<PRED X> ---<FRED X>) < :mED X > :: (ATOO < PARTOF X> )

The expression actually chosen is completely dete­ rmined by the recursion line of the function - the test is designed to prevent it causing an error. NIL, the 'boundary condition 1 imposed upon the schema is then a reasonable final value for the schema.

Whenever an iopair is coded as a < FLATFN ), it could have been coded as (<'LISTFN > (FLATTEN X)). This would be slightly unnatural and so we include an appropriate combined schema. The only remain­ ing undescribed schema is < TREEFN >:

<TREEFN) :: = (LAMBDA (X) (COND ((NULL X) NIL) (T<TREELINE I>)))) <TREELINE X>:: (APPEND<TREETERM X> (SELF (CDR X))) < TREETERM X> : : (APPEND (SELF(CDR X))<TREETERM X>) (COND(ATOM(CAR X))( BUILD X ) (T(LIST (SELF(CAR X)))))

The schemas described are simplified in that they are presented as if GAP could write only expressions involving one variable, when in fact, arv number can be used ·

How the schemas are used

It would be possible to represent these schemas explicitly within the computer and GAP could write functions by enwnerating possible expressions until one was found which included the g1 ven iopair, and, even though the schemas are not explicitly stored, GAP can effectively do this, using the LISP system described in Section Three. Whilst this method of program writing is appropriate on problems w1 th small search spaces - for example, expressions of type PARTOF - it becomes incredibly slow as the complexity of the problem rises. The cue-seeking routines suggest likely replacements for parts of the FOIM schema (the most general) and so cut the search space. The heuristics used are best explained by following GAP's progress as it writes several functions.

When GAP is presented with an iopair it tries to find an expression which, when evaluated with an allst built up from the inp1ts to the iopair 1 produces the OUtplt of the iopairo ?.'hl.s expres­ Sion is then converted to a function and printed to the user · When g1 ven the io~air : (A B C D) ·> = ((A) {B) (C) (D))} GAP tries to find an expression evaluating to((A) (B) (C) (D)) with the alist ( (X. (A B C D)) ) · Initially all that is known of the expression is that it is o.f type FORM - the most general type. One cue noticed in this case is that the length of the outp1t is an integral number of times the length of an input. (In this case, equal to that of the only input.) This would be the case if the expr­ ession were an application of a < LISTFN ) whe ze the expressions <FORM X> are replaced by (LIST < FO!M X >---<FOIM X>) and where the expression

(PARTOF I) is replaced by (CDR I), Such a<LISTFN> is called a Cllt-loop. <he or the hypotheses sug­ gested by the cue seeking routine isa

(APPEND(LIST( FORM X) ) (SELF(CDR I))(LIST))

other heuristic routines, described later, concur with this hypothesis and it ia selected for det­ ailed exam.ination. ~e expression ia optimised to1

(CONS (FORM I) (SELF(CDR I)))

and GAP tries to make 1

(LAMBDA (I )(CONS< FORM I > (SELF (CDR I))) )I) evaluate to ((A(B)(C)(D)). For this to be so (FORM I) 11111at evaluate to (A). GAP solves this subsidiary problem by a call on the R:>POORN data base - and hence a possible recursive call of GAP i taelf. If the wanted expreaaion is not alrea~ known the iopair1 (A B C D) ·> · (A) ia examined and one routine decides it is of type BUILD. It does this by counting the atoma in the output, getting the list (1 0 0 0) (meaning 'A' occurred once and 1 B 1 , ·c· and 'D' not at all). The routine expects that if the expression being coded calls a recursive function then there should be some pat­ tern in this list. It can't find any and so the expression is coded by the routine responsible for producing exF8aaions or type BUILD I which produoea (LIST (CAR X)),

GAP deduces that the hypothesised recursion line would 'explain' the output if (SELF NIL) eva­ luated to NIL - this suggests that (TESTS I) evaluates to 1 T 1 when I is NIL. However, GAP 1knows 1 that the tenninating condition of many iterative loops -<LISTFN)s embody an essentially iterative process (8) - is such that one more

iteration would have caused an error.

To apply this knowledge GAP finds the 'mini­ IIIWII.t'value of I if the recursion line is not to cause an error. In this case I 11111at be a pair - since both CAR and CDR are applied to it - and so an appropriate TEST is (ATCM I), GAP inserts this into the < LISTFN > schema and checks that (SELF NIL) does actually evaluate to NIL. ~s type of red­ undancy provides a useful consistency check.

Had we given GAP the iopaira

(ABC D) ·) · ((A) (B) (C) (D) (B) (C) (D) (C) (D) (D))

then one of the cues noted would have been that the length of the output is proportional to N*(N+l)/2, where N is the length of an input. This can happen when a CDR-loop function calls another as a sub­ routine. For this iopair, therefore, one of the hypotheses generated is that the first four elem­ ents of the output should be split off ani an exp­ ression evaluating to that segment be found to replace the firet <FORM X> in the< LISTFN> schema. Once this has been done the expreesion is completa:l in a eimilar way to the last example.

A common method of problem solving is find some homomo:rrhictnapping of the problem, wi t.h a emaller search epace, which can be eaeily solved to provide a plan for the eolution of the main problem. This technique has been used by a number of researchers, notable (4,6,2,11 ). GAP applies

this method of problem solution when :p'eaented with an iopair with more than one input. Maey functions or multiple inputs produce their output by interleaving their inputs in soma w~, If 1 therefore 1 GAP finds for each element of the out­ put from which input a they have drawn .a tome 1 it ma,y be able to recognise some pattern in the reau­ lting ·origin list'. Consider the iopair 1

(A B C D) ~ IQ"' · > · (A B Q B C Q C D Q)

Representing the two inputs by I and Y gi vee the origin li at 1

((X) (I) (Y) (I) (I) (Y) (X) (I) (Y))

It ia trivial to recognise the repeated ((I) (.I) (y)) in this list, and this suggests the recursion line hypothesis 1

(APPEND(LIST <FO!IM I> <FORM .I>< FORM Y>) (SELF< PARTOF I>< PARTOF Y > ))

Once this hypothesis has been selected for detailed examination< PARTOF Y >is replaced by Y - the value of Y ia atomic and so neither CAR nor Cim can be applied to it. The validation of this hypothesis is more complicated than the earlier example aa the recursion step for I is not known · ~e LISP system, using a simple matcher, deduces that1 (LIST(FORM .I><FO~ I)<FORM Y>) 111118t evaluate to (A B Q) and can therefore be replaced by1 (LIST (CAR .I) (CAR (CDR I)) Y)

Whilst anti-evaluating (aa this part of the validation process ia called) the recursive call of the h1Potheaiaed function, all that is known or the value of X ia that it ia part or (ABC D). However 1 it ia easily found that (CAR .I) evaluates to B. I can then only be the CDR of (A B C D) and so<PARTOF I):B replaced by (CDR I).

To complete the hypothesis< TESTS I >is replaced by 1

(OR (ATCM I) (ATC:Jof (CDR I)))

and after final optimisation GAP produces the

(COND((OR(ATf'M I) (ATCM(CDR I)))NIL)

function I (LAMBDA (I Y) (T (CONS (CAR I)

(CQNS(CAR (Cllt I))

(CONS Y(SELF (CDR I) Y)))))))

The technique used in the last example - looking for patterns in an origin list - can be extended by regarding multiple occurrences of the eame outputs ae a single occurrence. For example, the modified origin list for the iopair:

(A B C D) && tQ " = > = (A B C D Q B C D Q C D Q D Q) is ((I) (Y) (I) (Y) (X:) (Y) (X) (Y))

The repeated ( (X) (Y)) in thie list suggests splitting of either the first five or the laet two elements of the output and finding an!¥Jpropriate expression and so one of the recursion line hypo­ theses made is :

(APPEND (APPEND X (LIST Y)) (SELF< PARTOF X> Y))

The cues deecribed so far have to generate a number of hypotheses as they camot distinguish whether atoms from the 'front' of the inputs occur at the front or back (or both) of the output . I f we give GAP an iopair with one input, of lengt h four, and an output of length eight then three recursion line hypotheses will be generated by the cue first described in this section. These hypo­ theses can be represented:

(APPEND(LIST<FORM X><FORM X>)(SELF(CDR X))) (APPEND(LIST<FORM X>)(SELF(CDR X))(LIST<FORM X>)) (APPEND (SELF (CDR X) )(LIST<FORM X><. FORM X>))

(However, these hypotheses are not generated simultaneously; not until the most likely altern­ ative (the first) is rejected are the other poss­ ibilities suggested.)

GAP needs a cheap way of rejecting the incor­ rect hypotheses. One way of doing this is to replace the atoms in the output by numbers repres­ enting which element of an input they came from. The 'number list' for the iopair:

(A B C D) =)= (A A B B C C D D)

is (1 1 2 2 3 3 4 4). As the 'average 1 atom in the input.s to the recursive call of the function is higher than the average atom in the original inputs the average for that segment of the output allegedly due to the recursive call of the function should be higher than that for the whole output - if this is not so the hypothesis is rejected. This heuristic will reject the two incorrect hypotheses above.

Additional information can be found by suppo­ sing that the wanted function recurs on the CDR of some input and otherwise refers only to the CAR of that input. If this is so it might be possible to split the output into three segments the outer ones containing no atoms from the CDR of the relevant input, and the inner segment, hopefully due to the recursive call of the function, contain­ ing none from the CAR. Of course, there will usually be several possible splittings, For the iopair : (A B C D) && IQ " =) = (D Q C Q B Q A Q ) the routine embodying this heuristic will suggest:

NIL, (D Q C Q B Q), (A Q) and NIL,(D Q C Q B), (Q A Q))

When used in conjunction with other routines, this heuristic, despite its simple~ndedness, makes a valuable contribution to the selection of the correct hypothesis.

It is clear that we can extend the principle of trying to find which segment of the output of a < LISTFN > is due to its recursive call by guessing which atoms it might contain. Consider the iopair:

(A B C D E F ) =} = (A B B C D D E F F)

If we count the atoms in the output we get the atomcount list (1 2 1 2 1 2) -meaning 'A' occurred once, 1B1 twice and so on. The repeated (1 2) in this list suggests that the segment due to the recursive call might have the atomcount list (0 0 1 2 1 2). GAP uses a simple matcher to find such a segment and gets (C D D E F F). The two outer segments, (A B B) and NIL, suggest replace­ ments for the terms<FORM X) in the<LISTFN) schema and the length of the repeated atomcount segment (1 2) suggests the recursion step to use and so this routine hypothesises the recursion line:

(APPEND(LIST(CAR X)(CAR(CDR X))(CAR(CDR X))) (SELF(CDR(CDR X)))) ~~~--------------- The reader will have noticed that many of the cue-seeking routines appear redundant; several can (and do) suggest the same hypothesis. This redundancy provides the basis of the approach taken to hypothesis generation. Part of GAP, called the 'research director', monitors the hypothesis generation process. If this sees that a hypothesis is particularly popular it interrupts, and tests the promising candidate. Should this be unsuccessful it allows hypothesis generation to continue. Some cue-seeking routines notice failure of their hypotheses and produce fresh alternatives. Should there be no especially popular hypothesis, the research director exhorts the cue-seeking routines to ·try harder·; on receipt of this message the routines release hypotheses previously considered to have too little supporting evidence. This same message causes the recursion lines:

(APPEND <FORM X > (SELF < PARTOF X)) ) (APPEND (SELF< PARTOF X>)<FORM X) )

to be hypothesized so that, if desperate, GAP can search blindly for a solution!

For a system like GAP, which attempts to write functions by associating an iopair with a particular programming construct, it is natural to ask what must be done to include a new construct. The heuristic routines described so far are all concerned with functions of type.( LISTFN >, and I have deliberately omitted references to the routines for functions of type.( FLATFN > and ( TREEFN) · This reflects the historical develop­ ment of the program - routines for these two types were added to the working system with only minor modifications being required.

In one sense, the addition of a new schema is trivial - we need only add a routine to the data base which blindly tries the new schema on all iopairs presented for hypothesis generation.. Such a routine can be added in a matter of minutes - but unless heuristic routines are added to control the use of the new schema GAP will get involved in huge uncontrolled searches (which will, of course, eventually be successful). As an exanple of such a large search, the validation of the hypothesis:

(LAMBDA(X Y) (COND(NULL X) NIL) ( (AT(lot X)< BUILD X Y >)

(T(APPEND(SELF(CAR X))(SELF(CDR X))))))

for the iopair: ((A (B) C) D (E)) && IQ· => = (A Q B Q C Q D Q E Q)

took over a hundred seconds of CPU time; when a heuristic ~~s added to GAP which realised that .( BUILD X Y) could be replaced by (LIST< BUILD X Y) <BUILD X Y .>) the validation time dropped to

under six seconds.

Other routines added to control the new schema recognise the concepts of 1 treeness·, when GAP decides that the input to an iopair is a tree it can ignore the< LISTFN) option for< FOm-1 X) An extension of the 'average' atom heuristic described earlier determines the choice of recursion for these two schemas and finally an extension of the length heuristic replaces the

(BUILD X) in the < FLATFN .> schema by an appropriate (LIST (BUilD X) ---<BUilD X) ) expression.

Section Three - The LISP System

As the reader has seen, the hypotheses made by GAP take the form o.f expression schemas. GAP will usually know to what such an expression is to evaluate but not necessarily the value of the variables it contains (since they mey be the unknown inputs to a recursive call).

To assess the validity of such hypotheses GAP uses a special purpose LISP theorem prover. At it's simplest this takes a LISP expression and it's alleged value and deduces the values of variables contained in the expression. I call this 'anti­ evaluation' to emphasize the contrast with the deduction performed during LISP evaluation.

A LISP interpreter embodies the rules for the evaluation of LISP in a way that allows a tightly controlled deduction. This suggests the possibil­ ity of an 'anti-interpreter' which, when applied to an expression and its value returns possible sets of variable bindings. A LISP function, normally regarded as a program to compute some result from some arguments, could be viewed as an anti-LISP function to compute the arguments from the result!

There are a number of problems with the inversion of computable functions (7). In general there can be any number -perhaps infinite, perhaps zero - of possible inputs that map onto a given outJUt. (Anti-evaluation is a partial relation, not a total function.) If an expression to be anti-evaluated contains conditional expressions the anti-interpreter must search to find which alternatives could have been taken. (The condit­ ional expression in LISP can be thought of as a non-deterministic statement (1) in anti-LISP.) An additional problem is that information about a variable's value is built up gradually during anti­ evaluation - in normal evaluation we know the value completely at all times and can easily represent it by an item on an ALIST.

GAP's anti-interpreter must also cope with incomplete expressions. If it deduces the value of an expression< StNETYPE X) it calls upon GAP to write suitable code; for example if told that (APPEND X ( PAR'IDF X>) evaluates to (A B C D B C D) it deduces that on.: poSsibility is X = (A B C D), ~ PARTOF X)= (CDR X).

Because of its crucial role in validating hypotheses the anti-interpreter should be quick - even at the cost of incompleteness and inconsis­ tency. The search strategy used, and the repres­ entation fo·r variable values are both quite weak. They are, however, adequate for GAP's purposes. (In general, such an approximate 'micro-theory' (10) will be of much greater practical use than a complete theory hundreds of times slower).

Section Four - Conclusions

A major criticism of GAP is that the way it forms and represents hypotheses is almost totally ad-hoc. This has two implications. Firstly, the unskilled user cannot understand the system's reasoning and this makes it impossible for him to contribute to hypothesis formation by supplying any information other than a single iopair - which is, of course, insufficient to describe the major­ ity of LISP functions. If GAP used SOliE widely known language (like LISP or predicate calculus) to represent all facts and hypotheses a much richer interaction with the user would be possible. For example, the system could 'think aloud' with the user interrupting or answering questions as necessary.

The second defect is more fundamental. Most of GAP 1 s knowledge of programming consists of function schema's and associated cue-seeking routines. These cue-seeking routines, it will be recalled, assess which schema should be instant­ iated to realise a particular iopair and suggest likely replacements for the 'slots' of the schema. This knowledge is 'heavily compiled' into ro:R:ORN methods so that to add new heuristics or schemas one must, at least, be able to program in POPCORN. Furthermore since this knowledge is almost totally unstructured, as the number of such frag­ ments of knowledge rises so does the difficulty in avoiding undesirable interactions between heuristics · For example, after adding< TREEFN > s and<FLATFN > s to the system I found that heuristics specific to< LISTFN > s were incorrectly preventing the new schemas being tried on some iopairs.

The significance of this can be seen by considering the current version of GAP's behaviour on iopairs such as:

"C" && ((A W)(B X)(C Y)(D Z) => = "Y" (A C D E) && (B D E F) = > = (A B C D E F) .

It could not produce the familiar ASSOC and UNION functions because these are not instanstiations of known schemas - but there is no way for the user to tell GAP the appropriate schemas, nor, if he could, how to use theml