Inferring LISP Programs From Examples

ABSTRACT

A program is desmbed which infers certain recursive LISP programs from smgle example input.output pairs. Synthesized programs may recur in more than one argument, and may involve the synthesis of auxilliary functions. An actual user session with the program, called EXAMPLE, is presented, and the operation of the program and its important heuristics are outlined.

ACKNOWLEDGEMENTS

The authors wish to thank Richard Waldinger and Doug Lenat for the fruits of several valuable discussions held early in the course of this work. We are also grateful for the editorial assistance of A vra Cohn, which made possible the preparation of this draft. This research was supported in part by the Advanced Research Projects Agency under contract DA HC 15-73-C-0435 and in part by the State of California through a California State Graduate Fellowship.

SECTION I - INTRODUCTION

A common aspect of many definitions of automatic programming is the goal of facilitating program specification. In this paper, we consider the specification of programs by examples. To describe a particular program by example, the user supplies only a sample input and output. The computer then infers a plausible candidate program.

The inductive inference of programs from input-output examples has also been explored by Licklider [1973) and Hardy [1974). More generally, this inference task is related to the problems of program inference from traces [Biermann. 1973) and grammatical inference [Feldman, Cips. Horning and Reder, 1969; Horning, 1969; Biermann and Feldman, 1972; Blum and Blum, 1973).

This paper describes a program. called EXAMPLE, that infers recursive LISP functions from single input-output pairs. Given the input-output specification

for instance, EXAMPLE writes the "reverse-and-double" function

f(x) ·- if 11ull(x) then nil tbe

append(f(cd r(x ),

list(car(x ),car(x))) .

INFERRING LISP PROGRAMS FROM EXAMPLES

David E. Shaw William R. Swartout C. Cordell Green

Artificial lntellirence Laboratory Department of Computer Science Stanford University Stanford, California

EXAMPLE is able to infer a class of functions . which perform certain list-to-list transformations. In particular, each recursive function in this class steps through the input list from left to right, producing part of the output at each step. Consider, for example, the pair

The output is produced in three steps. A recursive subfunction produces the subhsts I, 2. and 3 in successive steps and the main function appends them together.

Let us briefly outline the way this function is synthesized. First, EXAMPLE determines which part of the output is produced in the first step of recursion. In the above example, sublist I is produced in the the first step. It is assumed that this sublist is produced by a subfunction. EXAMPLE thus attempts to synthesize the subfunctlon, generating a new input-output specification which describes this subgoal. The arguments A and (B C D) are chosen as input. The subfunction specified by

may now be synthesized by calling the EXAMPLE program recursively. Returning to the synthesis of the main function, we find three remaming steps: I) The recumve call of the main function is formed, 2) the resulting code is embedded in either a CONS or APPEND expression so as to properly conjoin the output from each recursive step, and 3) termmaung conditions are selected.

We will say that an output has been realized when a function has been synthesized which satisfies the given input-output specification. Unfortunately, not all syntheses which simply realize the output will be found acceptable to the user. To see why. we cons1der a trivial synthesis scheme wh1ch can realize any output by breaking the input arguments down into their consititueht atoms and recombining these atoms mechanically to form the desirt>d output.

Using this schemt>, the function specified by

(A B C D) .... ((A R) (A C) (A D) (B C) (B D) (C D)) may be synthesized trivially as

(LAMBDA (ARCI)

(LIST (LIST (CAR ARC I) (CAR (CDR ARC I)) (LIST (CAR ARC I) (CAR (CDR {CDR ARC I)))) {LIST {CAR ARC I) {CAR {CDR (CDR (CDR ARCI))))) (LIST (CAR (CDR ARC I)) (CAR (CDR (CDR ARC I)))) (LIST (CAR (CDR ARC I)) (CAR (CDR (CDR (CDR ARC I))))) (LIST (CAR (CDR (CDR ARC I))) (CAR (CDR (CDR (CDR ARC I] .

The user probably intended, though, to specify a function which finds all combinations of two elements from an input list of any length. The above synthesis is implausible since it performs this function only for lists of four elements. As we will see, EXAMPLE formulates subgoals in a manner which guards against implausible synthesis of this sort.

A discussion of the types of synthesis tasks for which example specification is appropriate, of the problems associated with specification by example, and of the relationship between this and other methods of program specification appears in Green, et al.[ 197-t). .

SECTION 2 ·AN ACTUAL SESSION

Let us now examine an actual session in which the EXAMPLE program synthesizes several user-specified LISP functions. Material typed by the user appears in lower case and is preceded by an asterisk (·:·). Responses by EXAMPLE are in upper case, while our comments appear in italics. The session begins when the user types "ex ample()" to initiate the specification process.

· · · · ·

·:·ex ample()

WHAT SHALL I CALL THE TOP-LEVEL FUNCTION? ·:·comb2

OK. NOW TYPE IN AN EXAMPLE ARCUME;NT LIST.

·:·{(a b c d))

AND WHAT WOULD BE THE VALUE OF COMB2 WITH THIS ARGUMENT LIST?

·:·(a b a c a d b c b d c d)

OK, I'LL TRY.

DOES COM B2((B C D)) · (B C B 0 CD)?

The Junction of this query will be discussed in section ).

I HAVE DEFINED COMB2 AS FOLLOWS:

(COMB2

[LAM BOA (ARC I)

(COND

\(NULL ARC I)

NIL)

(T (APPEND (COMB2.AUXI (CAR ARCI)

·:·ex ample()

WHAT SHALL I CALL THE TOP-LEVEL FUNCTION?

OK. NOW TYPE IN AN EXAMPLE ARGUMENT LIST.

·:·{(a b cXd e f))

AND WHAT WOULD BE THE VALUE OF MIX WITH THIS ARGUMENT LIST?

·:·(f c c e b b d a a)

OK, I'LL TRY.

DOES MIX((B CXD E F)) · (FCC EBB D)?

DOES MIX((B CXE F))· (FCC E B)?

DOES MIX((B C)(E F)) · {FCC E B B)?

·:·yes

(CDR ARCI))

(COMB2 (CDR ARC I))

{COM B2.A UX I

[LAMBDA (ARC2 ARC3)

(COND

((NULL ARC3)

NIL)

(T (CONS (LIST ARC2 (CAR ARC3))

(COMB2.AUX I ARC2 (CDR ARC3))

T ht user may non1 test COM 82. ·:·comb2((a b c))

(ABA C B C)

·:·example()

WHAT SHALL I CALL THE TOP-LEVEL FUNCTION? ·)pairreverse

OK. NOW TYPE IN AN EXAMPLE ARGUMENT LIST. ·:·{(a b c d e f))

AND WHAT WOULD BE THE VALUE OF PAIRREVERSE WITH THIS ARGUMENT LIST?

·:{b ad c f e)

OK, I'LL TRY.

DOES PAIRREVERSE((C D E F)) · (DC FE)?

''yes

I HAVE DEFINED PAIRREVERSE AS FOLLOWS:

{PAIRREVERSE

{LAMBDA (ARCI)

(COND

((NULL ARC I) NIL)

((NULL (CDR ARC I)) NIL)

(T (APPEND (LIST (CAR (CDR ARC I))

(CAR ARC I))

(PAIRREVERSE{CDR {CDR ARC I])

DOES THIS LOOK RIGHT?

(MIX

[LAMBDA (ARCI ARC2)

(COND

((NULL ARC I)

NIL)

((NULL ARC2) NIL)

(T (APPEND (MIX (CDR ARCI)

(CDR ARC2)) (LIST (CAR ARC2) (CAR ARC I)

(CAR ARCID

*mix((a b c dXe f g h))

(H D D C C C F B B E A A)

· ·· · · ·

A number of other input-output pairs are included In the appendix, along with the corresponding programs synthesized by EXAMPLE. It should be noted that EXAMPLE can not synthesize functions involving counting operations or numerical comparisons (a function that sorts a list of integers by value, for example). Further, all termination checks are null tests which can return only the value NIL. Thus, for example, the function which returns the last element of a list,

(A BCD)..., D

can not be synthesized, since an equality test and the ability to return a non-NIL atom would be required. A function which finds the first half of a list, which might be specified by

also falls outside the class of functions synthesized by example.

We have tried only to convey a feeling for some of the programs still beyond the reach of EXAMPLE. A more precise characterization of the class of functions attacked by the current program is found in sections i .2 and i .3.

SECTION 3- HOW IT WORKS: AN OVERVIEW

The program first determines whether a simple nonrecursivt realization of the target output is possible. The programming construl!ts available for nonrecursive synthesis will be described In section i . l.

If the output can not be realized using available nonrecursive constructs, a synthesis involving recursive constructs is attempted. The recursive LISP functions synthesized by EXAMPLE produce some part of the output during the original top-level evaluation and the remainder during subsequent recursive calls. Considering the specification

for example, we see that the initial value segment

Is produced during the first recursive step. while the remainder of the output, is produced by wb~equent rP.cursive calls. We will refer to the initially produced output segment as the htad of the output. The remaining segment w1ll be called the rtcurrate.

After the dividing point between head and recurrate is found, EXAMPLE attempts to synthesize the code that produces the head in the same way it attempted the original (user-specified) goal. This ~ubgoal is again specified with an input-output pair, with the head appearing as the output:

(We ignore for now the question of specifying the input part of the head realization subgoal.)

In order to distinguish the head from the recurrate, EXAMPLE divides the output into equal-length groups of adjacent ·elements. By way of illustration, we consider a simple variant of COMB2:

EXAMPLE dtvides the output into groups of two elements, as indtcated above.

Successive groups are then compared using a template-matching procedure. Th1s procedure searches for the first major group which is substantially different in some way from its predecessors, conjecturing a head-recurrate separation just before this change. Comparing successive groups, EXAMPLE discovers a major change after the third group, and postulates the following separation:

Head -- (A B A C A D ...

Recurrate -- ... B C B D C D)

In the case of some input-output pairs, the serial comparison procedure must in fact proceed bacluvard through the output list structure. Simple heuristics are used to select a scanning direction for the output. This direction determination is used in several later stages of synthesis. The procedures for grouping, matching, and deteimin111g scanning direction are discussed in section i .3.

EXAMPLE is now able to reduce the synthesis task to several simpler subgoals. The head and recurrate must each be realized, and the resulting blocks of code combined in an appropriate way, along with code for terminating conditions. In order to specify the head-realization subgoal in input-output form, a: new set of input arguments must be formulated. Arguments used in specifying the subtask must again be carefully chosen to avoid the possibility of implausible synthesis. Still, some of the arguments which form the input of the parent goal may be broken down in specifying input for the subgoal. For example, the initial goal of realizing

(A B A C A D B C B D C D) from (A B C D)

spawns the subgoal of realizing

(A B A C A D) from the two arguments

A and (BCD).

The heuristiCS used to break down parent input arguments are discussed in sec;tion ·l.i.

Once n'ew arguments have been generated, EXAMPLE attacks the head-realization subtask exactly as it did the original problem. If head realization itself requires a recursive synthesis, of course, a separate auxilli~ry iunction must be synthesized. In this case, a call to the aux illiary function (with appropriate arguments) appears as the head realization code.

The problems of recurrate realization are different. EXAMPLE synthesizes only recursive calls whose arguments are the tails (CDR, CDDR, etc.) of the original lambda-variables. The number of CDRs within which the original arguments are embedded is postulated usmg certain clues involving the propagation of ~rgument elements to the recurrate.

If the head and recurrate are successfully realized, they are conjoined using either CONS or APPEND. If the original output was interpreted in the forward direction, the head realization appears as the first argument of the joining function, while in the case of backward scanning, the recurrate realization appears first . The resulting body of code is embedded in a CONDitional statement, following a set of termination checks. Each termination form involves a null-check on some tail of a current argument, with the value NIL returned if the result is positive.

SECTION i - HOW IT WORKS: THE WHOLE STORY

i . l NONRECURSIVE SYNTHESIS

In the current version of EXAMPLE, nonrecurslve synthesis is allowed only if the output can be realized simply from the current input arguments without decomposing those arguments. No constructs which break . down the. arguments (such as CAR or CDR, for example) are considered at this stage. The effect of this limitation is to prevent the synthesis of an implausible function, which might be generated by br~aking down each argument into its primitive components and combining them mechanically to realize the output.

At prt>sent, EXAMPLE allows nonrecursive synthesis only if the output can be realized with a composition of the functions CONS and LIST over the input arguments. More precisely, the class of functions which may be synthesized without recursion is the union of

1. The identity function over the input arguments themselves
2. A II functions of the form (CONS ·:· ·:·) and (LIST ·:· ·:· ), where ·:· represents a function which may be synthesized nonrecursively.

Thus, if the argumt'nts were A and (B C), eitht'r (A B C) or (A (B C) A) could be realized nonrecursively, but realization of (B A C) would be not be possible.

Because of these restrictions on nonrecursive synthesis, most user­ specified functions of interest are not synthesized at this stage. As we will see, the 1mport~nt function of nonrecursive synthesis is the realization of very simple EXAMPLE-specified subgoals.

i.2 THE RECURSIVE FUNCTIONS

The recursive functions syntht'med by EXAMPLE have the form indicated in the followmg schema:

(function-name [LAM BOA argument-list (COND ((NULL argta1l) NIL) ((NULL argtail) NIL) (T (join-function head-realizing-code ! (possibly (function-name recursive-args)) t reversed)

Here, each "argtail" represents some composition of the function CDR oyer some input argument. "Join-function" may be either CONS or APPEND. The "head-realizing-code" is either some nonrecursively synthesized el\pression or a call to an auxilliary function "function-name.A UX I" with appropriate arguments. The form of the recursive argument list will be discussed later. Finally, we note that the order of the "head realizing-code" and the recursive call may be interchanged.

i.3 SEGMENTING INTO HEAD AND RECURRATE

Recursive realization requires correct identification of the head and recurrate of the output. We recall that a template-matching procedure is used to locate the first maJOr change in successive groups of elements. In the present version of EXAMPLE, each group initially consists of a single t>lement. If such a grouping does not allow head-recurrate separation in the template-matchin' stage, the size of the groups is increased.

We now examine the template-matching procedure in detail. EXAMPLE forms a template by comparing the first two groups appt>aring in the output. Consider COMB2:

(A BCD) .... (A B A CAD B C B DC D).

In this case, the two-elemt>nt groups (A B) and (A C) are compart>d to form a tt>mplatl' (A x), where x stands for the differing elements which appear in the two instances. {The first head-recurrate segmentation postulated by EXAMPLE is in fact an inaccurate guess based on thl' use of single-element groups; the correct segmentation discussed here is found upon subsequent scanning with two-elt>ment groups.)

In gt>neral, all atoms appearing in corresponding positions are compared for equality. If the two atoms are the same, that atom appears in the template. Otherwise, a unique variable x, representing the unequal atoms, appt>ars. A description of the relationship between the two differing atoms is associated with x. Thus, thl' COM 82 template indicates that C, the second instance of x in the output, is the immediate successor in the input list of B, the first mstance. A template for the function

(A B C D E F) -+ {A C E),

analyzed with a group size of one, is comprised of a single variable and the associated information that the second instance of this vanable is the doublt>-successor of the first.

The template is then used to predict the third group of elements, assuming the same relationship between the second and third groups as was observed between the first and second. To predict the third group appearing in COM 82, for example, the successor of C is instantiated for the template variable x. The resulting instantiated template, (A D), in fact agrees with the third group appearing in the output. This template, though, does not correctly predict the fourth group from the third. EXAMPLE thus correctly divides the head from the recurrate after the third group. For some function specifications, no major change is detected usmg these heumtics. In this case, the first group of elements is taken to be the head, and the remaining groups the recurrate. The two initial (one-element) groups of

F, (A B C D) .. ((F AXF BXF CXF D)),

for example, yield the template (F x), which allows prediction of all groups. Separation after (F A) is thus assumed. While the head-recurrate separation methods employed by EXAMPLE work reasonably well, it must be emphasized that tney are not universal1y effective. A larger class of functions might be synthesized using better heuristics for this critical decision.

It was noted in seCtion 3 that the output must sometimes be scanned back ward (from right to left) in order to effect the proper head-recurrate separation. EXAMPLE chooses a scanning direction by noting whether elements from the front of the input Jist propagate toward the front or the back of the output. If they tend to appear in the end of the output, EXAMPLE assumes that the heat! will be found at the end of the output list. In this case, a reverse scanning direction is used to distinguish the head and recurrate. In section '1.6, we wi11 see other effects of the decision to scan backward.

i .i SUBGOAL: REALIZING THE HEAD

Let us review the work EXAMPLE has done so far. A scanning direction has been chosen heuristically and noted for later reference. AdJacent groups of elements have been scanned in the chosen direction and compared using a template-matching procedure. By locating the site of the first major change, that part of the output generated during the first step of recursion (the head) has been distinguished from the part produced during all successive recursive calls (the recurrate). If no major change was apparent, a default separation point has been assumed. Finally, those atoms appearing only in the head have been distinguished.

EXAMPLE must now attempt to synthesize code which will generate the head when evaluated with the arguments of the top­ level function· call. We implicitly assume that evaluations of this same code during all subsequent recursive calls will produce the recurrate. As mentioned before, the head realization subgoal is specified with an input-output pair, JUSt as the user specified the original task . The target output, of course, is the head itself. Selection of an appropriate input argument list for the head realization subgoal IS less trivial.

In certain cases, the original input list is a reasonable choice of

input for the subgoal. For example, consider the following input­ output pair:

(A B C D) .. (A B C D B C D C D D),

Here the head is exact ly the same as the original input argument: (A B C D). A trivial nonrecumve realization of the head thus results when

(A B C D) -. (A B C D)

is specified as the subgoal. For a first attempt at head realization, EXAMPLE always tries this first method, in which the input for the subgoal is the same as the original input. For some problems, though, the original arguments must be broken down in some manner in order to realize the head. In this case, EXAMPLE fails to accomplish the first subgoal, and creates a new subgoal whose input arguments are subparts of the original arguments. To i11ustrate, the first subgoal generated in trying to realize the head of COM B2 is to synthesize a subfunction satisfying the input-output relation

(A B C D) __, (A B A C A D)

This output, however, can not be realized from the input (A B C D). EXAMPLE thus generates the new subgoal

A, (BCD)__, (A B A CAD)

whtch will eventually result in the successful synthesis of a two­ argument auxilliary function.

EXAMPLE generates this new subgoal by decomposing the original input , (A B C D), according to a simple heuristic. First, we note that certain atoms from the input list may appear in the head but not in the recurrate. These atoms, called Mad distingu.ishers, appear as arguments for the head realization subgoal. Here A is a head distinguisher, since it appears in the head, (A B A C A D), but not inthe recurrate, (B C B DC D); A is thus chosen as an argument. Second, the remainder of the original argument after removing the head distmguisher is included unless none of its atoms are found m the head. We. remark in passmg that if EXAMPLE broke down the onginal argument completely into its constituent atoms, head realizat ion would alwap succeed (nonrecursively). A complete decomposit ion of this sort , though , is in general dangerous, admitt ing the possibility of implausible synthesis. This danger is the motivation for selective input decomposition.

Before continumg our discussion of the synthesis of the main function COM B2, Jet us summarize the synthesis of its subfunction. The original goal of synthesizing a function specified by

(A B C D) .... (A B A C A D B C B D C D) spawns the head realization subgoal

A, (BCD) .... (A B A C A D)

Template matchmg with smgle-element groups separates the head of thiS subgoal output, (A B), from the recurrate, (A C A D). EXAMPLE th('n decomposes the argument (BCD) into Band (C D), discarcltn[: (C D), whose atoms fail to appear in the head.

The resultmg subgoal is

A, B _,(A B).

The list (A B) is ~asily synthesized nonrecursively from A and B.

i .5 REALIZING THE RECURRATE

As we have indicated in section i . l, all recursive calls synthesized by EXAMPLE to realize the recurrate are of the form

(function-name var I var2 ... varn)

where each vari is either the ith lambda variable or a tail of (some composition of CDR over) the ith lambda variable. The recursive call of the ALTERNATE function,

(A B C D E F) -+ (A C E),

for example, is

(ALTERNATE (CDR (CDR ARGI))),

while the func taon FOO described by

F, (A B C D) .... ((F AXF BXF CXF D)) employs the recursive call

(FOO A RG I (CDR ARG2)).

EXAMPLE must thus determine the number of CDRs within which each recursive argument should be embedded. This number is assumed equal to the number of atoms from the beginning of that argument which fail to appear in the recurrate. Unfortunately, this method fails for many input-output pairs in which the atoms of the input do not all propagate to the output. Certain weak heuristics are used to allow synthesis of some such functions, but the problem is not entirely solved.

Once the recursive call has been synthesized, EXAMPLE can check Its decisaon about head-recurrate segmentation by querying the user. In the case of the above function FOO, for example, the user is asked if the proposed recursive call in fact realizes the recurrate:

"DOES FOO[F, (BCD))· ((F BXF CXF D))?"

(The us.er-spccif ied identifiers are substituted for the formal variables used in the actual recursive call). A negative response is taken as evidence of faulty segmentation of head and recurrate, often leading to a revised conjecture regarding scanning group si ze.

i.6 CONJOINING THE HEAD AND RECURRATE

Now that the head and recur rate have been realized, EXAMPLE conjoins the two resulting pteces of code usmg either CONS or APPEND. If the output was analyzed using a forward scanning direction, the lw~d realizing code appears as the first argument of the JOmtng; functaon, smce the head must have been found at the beginning of the output. If reverse scanning was used, the head must be at th P. end of the output, and the head realization appears as the Sf'cond argumen t.

Several fa ctors are con s ad~red in deciding whether CONS or APPEND should be used for conJunctaon. In the case of backward ~cannang, APPEND is always chosen. The JOining function will also be APPEND whenever the head cont ains more than one element. In accordance with usual human programming practice, however, CONS is used in. the case of a single-element head found by forward scanning. EXAMPLE adjusts the outermost list structure of the head to allow the use of the appropriate joinang function .

i .7 SYNTHESIZING TERMINATING CONDITIONS

We saw in section i . l that all terminating conditions synthesized by EXAMPLE test a tail of some arg·ument, returning NIL if a NULL tail is encountered. The number of CDRs involved in each tail depends on the number of CDRs used in the recursive call on that argument. Thus COMB2, which is synthesized using CDR recurston, embodies the single null check

if NULL (ARC) then NIL

but the function specified by

(A B C D E F) -+ (A C E) requires the deeper termination check

if NULL (CDR (ARC)) then NIL since its recursive argument is

CDR (CDR (ARC)).

It must be acknowledged that this heuristic yields incorrect terminating conditions for some functions which are o:herwise within the target class of EXAMPLE.

The resulting block of code is embedded in a function definition call with the user specified name and list of lambda variables. The resulting function is then defined for system use and evaluated with the user-specified input list. If this evaluation in fact yields the user-specified output, the function is presented to the user for verification and further user testing.

SECTION 5 - CONCLUSION

The EXAMPLE program was written in INTERLISP by David Shaw and was revised by William Swartout. A number of EXAMPLE sessions have been observed during the past year, but no formal study has yet been conducted of the programs users actually specify or of the way in which such programs are specified. It seems to us that such further study of actual program specification would be valuable at this point.

The exact role anput-output examples will play in facilitating program specification is not yet clear. We believe, however, that the capacity for specification by examples may be a useful component of future automatiC programming systems.

We conclude with several other LISP functions synthesized by the EXAMPLE program. The shorthand notation

<function name> : <input list> -+ <output> wall represent the user specification of a function <function name> which returns the value <output> when evaluated with the arguments on <input list>.

REVDBL : ((A B C D)) ... (D DCC B B A A)

(REVDBL

[LAMBDA (A RG I)

(COND

((NULL ARC I) NIL)

(T (APPEND (REVDBL (CDR ARGI))

(LIST (CAR ARGI)(CAR ARGI])

REVERSE : ((A BCD)) ... (DC B A)

(REVERSE

[LAM BOA (A RG I)

(COND

((NULL ARC I) NIL)

(T (APPEND (REVERSE (CDR ARC I))

(LIST (CAR ARC I))

DOUBLE : ((A B C)) ... (A A B B C C)

(DOUBLE

[LAMBDA (ARGI)

(COND

((NULL ARC I) NIL)

(T (APPEND (LIST (CAR ARC I)

(CAR ARGI))

(DOUBLE (CDR ARC I])

LISTTHRU : ((A BCD)) ... ((A) (B) (C) (D))

(LISTTHRU

[LAMBDA (ARGI)

(COND

((NULL ARC I) NIL)

(T (CONS (LIST (CAR ARC I))

(LISTTHRU (CDR ARC I))

LISTOFCOMBS : ((A BCD))

... ((A B) (A C) (A D) (B C) (B D) (C D))

(LISTOFCOMBS

[LAM BOA (ARC I)

(COND

((NULL A RG I) NIL)

((NULL (CDR A RG I)) NIL)

(T (APPEND (LISTOFCOMBS.A UX I

(CAR ARC I) (CDR ARC I)) (LISTOFCOMBS (CDR ARC I))

(LIS TO FCO M BS.A U X I

(LAMBDA (ARG2 ARG3)

(COND

((NULL ARG3) NIL) ((T (CONS (LIST ARG2 (CAR ARG3)) (LISTOFCOM BS.A UX I

ARG2 (CDR ARG3))

TELESCOPE : ((A B C D)) ... (A BCD BCD CD D)

(TELESCOPE

(LAMBDA (ARGI)

(COND

((NULL ARC I) NIL)

(T (APPEND ARC I

(TELESCOPE (CDR ARC I))

PAIR2 : ((A B C) (D E F)) ... ((A D) (B E) (C F))

(PAIR2

(LAMBDA (ARGI ARG2)

(COND

((NULL A RG I) NIL)

((NULL ARG2) NIL)

(T (CONS (LIST (CAR ARC I)

(CAR ARG2))

(PAIR2 (CDR ARC I)

(CDR ARG2))

ALTERNATE: ((ABC DE F)) ... (ACE)

(LAMBDA (ARGI)

(ALTERNATE (COND

((NULL ARC I) NIL)

((NULL (CDR ARC I)) NIL)

(T (CONS (CAR ARC I)

(ALTERNATE (CDR (CDR ARC I))

PAIR I : (FN (A BCD)) ... ((FN A) (FN B) (FN C) (FN D))

(PAIR I

(LAMBDA (ARGI ARG2)

(COND

((NULL ARG2) NIL)

(T (CONS (LIST ARC I (CAR ARG2))

(PAIR I ARC I (CDR ARG2])

SHUFFLE : ((A B C) (D E F)) ... (A D B E C F)

(SHUFFLE

(LAMBDA (ARGI ARG2)

(COND

((NULL ARC I) NIL)

((NULL ARG2) NIL)

(T (APPEND (LIST (CAR ARC I)

(CAR ARG2))

(SHUFFLE (CDR ARC I)

(CDR ARG2))

FOO : ((A B C) (D E)) ... (A D B D C D A E B E C E)

(FOO

(LAMBDA (ARGI ARG2)

(COND

((NULL ARG2) NIL)

(T (APPEND (FOO.AUXI ARGI

(CAR ARG2))

(FOO ARC I (CDR ARG2))

(FOO.AUX I

(LAMBDA (A RG3 A RGi)

(COND

((NULL ARG3) NIL)

(T APPEND (LIST (CAR ARG3) ARGi)

(FOO.AUX I (CDR ARG3) ARGi])

(CROSSPROD

(LAMBDA (ARCI ARC2) (COND

((NULL ARC I) NIL)

(T (APPEND (CROSSPROD.AUXI

(CAR ARCI)ARC2) (CROSSPROD (CDR ARC I) ARC2])

(CROSSPROD.AUX I (LAMBDA (ARC3 ARCi) (COND

((NULL ARC·f) NIL)

(T (CONS (LIST ARC3 (CAR ARC·f))

(CROSSPROD.AUX I ARC3 (CDR ARCi))

REVTELESCOPE · ((A BCD)) ~ (D C B A D C B D C D)

((NULL ARC I) NIL))

(REVTELESCOPE (LAMBDA (ARC I) (CC>ND (T (APPEND

(REVTELESCOPE.AUXI ARCI) (REVTELESCOPE (CDR ARC I))

(REVTELESCOPE.A UX I (LAMP.DA (ARC2) (COND

((NULL A RC2) NIL) (T (APPEND (REVTELESCOPE.AUXI (CDR ARCI)) (LIST (CAR ARC I])