A System which Automatically Improves Programs

Abstract

We give methods of mechanically converting programs that are easy to understand into more efficient ones, converting recursion equations using high level operations into lower level flowchart programs.

The main transformations involved are (i) recursion removal (ii) eliminating common sub­ expressions and combining loops (iii) replacing pro­ cedure calls by their bodies (iv) introducing assi~nments which overwrite list cells no longer in use tcompile-time garbage collection).

t., Introduction

This paper is an introduction to an automatic program improving system that we have implemented and are developing further.

A programmer is able to present his algorithms to the system in a clear and abstract language. The system converts them to efficient but probably not transparent versions.

For example, here are two versions of one program which reverses lists.

• (i) reverse(xl) = if null(xl) then nil -- else concat(reverse(tl(xl)), -- cons(hd(xl),nil))*
• (ii) reverse(xl) = result:=nil; while not null(xl) ----;iO begin -- temp:=tl(xl); tl(xl):=result; ~:=xl; xl:=temp
• ~

One is clear and abstract, the other more tortuous but efficient. Given the first as a definition, a competent programmer should be able to produce the second. Our system can do this for him.

The system is built around the concept of abstract programming, and we hope to encourage a user to formulate his algorithms in abstract terms appropriate to his problem domain and leave to the system the task of .implementing them efficiently.

Our work was partly inspired by Minsky's 2 homily on form versus content in computer science in which he recommended programming as a good application area for Artificial Intellige~ce work. It was also influenced by Dijkstra's ideas on structured pro­ gramming, differing in that we start from a functional

LISP-like language.

Our investigation took as its starting point a collectian of procedures written by Ambler and Burstall which aimed to provide transparent, but quite efficient operations on finite sets. We used this example to study the transformations which are needed to implement a collection of high level pro­ cedures as efficient code. To enable one to write programs about finite sets some operations on sets, for example, UNION, INTERSECTION, SIDTRACT, NULLSET, NILSET, CONSSET, CHOOSE and MINUS are defined. These

* The operations we use are based on the fOP-2 language, Burstall,Collins and Popplestone · The main fAatures to note are that hd is the ~ISP car tl the

LISP cdr and concat joins two lists tthe LISP append).

J. Darlington and R.M. Burstall

Department of Machine Intelligence University of Edinburgh

basic set operations must be implemented as structured definitions in terms of the array or list primitives available in the programming language. The user of the set system can define and run new functions, such as powerset, using these operations. However, when he looks at his definition~ he notices that he could have produced a much more efficient program by writing a special procedure for powerset directly in terms of the array or list primitives. This is what our sys­ tem attempts to do. A well written program in a LISP-like language expresses its structure as a hier­ archy of functions. Our system eliminates higher level function calls to gain efficiency, flattening this hierarchy. Four distinct improvement processes seemed to be indicated.

1. Recursion removal.
2. Eliminating redundant computation, by merging common subexpressions and combining loops.
3. Replacing procedure calls by their bodies.
4. Causing the program to reuse data cells which are no longer needed, in order to reduce storage allocation and garbage collection at
5. run time.

We have devised algorithms to perform these pro­ cesses on programs and implemented these algorithms as POP-2 programs (section 7 gives an example of their use). These algorithms are applicable to a variety of domains and require only a collection of rules specifying potentially useful equivalences for a particular domain. We have tried our programs on our original example (programs about finite sets), and we can reproduce automatically a lot of the tricks incor­ porated in the original handwritten programs for the

sets domain.

The overall system using processes 1 to 4 takes as input programs in a non-imperative language of recursive definitions and converts them, via inter­ mediate stages, into an imperative language. This imperative language uses while statements as well as recursive definitions and permits assignment to com­ ponents of data structures.

In order to produce efficient programs the system must use properties such as associativity or commutat­ ivity for the operations to be performed.

The principle techniques used are (i) matching, involving functional abstraction to detect the form of a recursive definition, (ii) matching to detect common subexpressions and compound operations involving the occurrence of several functional symbols, using algebraic equivalences, (iii) symbolic running to extract meanings from programs and check that a tentatively constructed sequence of instructions pro­ duces the required result. No elaborate theorem proving techniques are used, and the programs run quite fast, even though we have not ~ked to code them

efficiently.

2.. Recursion Removal

In this stage the system attempts to convert the set of recursion equations to a single iterative pro­ gram in the same operations. During this process particular attention is paid to the semantics of the operationsmlking up the recursion equations. This process is generally applicable; the only input required is the set of recursion equations and a table of rules giving algebraic laws for the operations used.

There has been considerable theoretical invest­ igation into how to translate recursive ~chemas into equivalgnt iterative schemas e,g, Strong , Garland and Luckham , although as far as we know only the BBN LISP compiler makes use of any of these ideas, and this only for simple recursions. These studies apply to translations of a schema which preserves its effect for all interpretations of the primitives. Our pro­ gram uses translations which preserve the effect of a schema only for a class of interpretations in which the primitive~ obey a given set of algebraic laws; we follow Cooper who gave examples of such translations. We are only interested in translations which will improve efficiency. The results for translations of schemas to maintain equivalence under all inter­ pretations seem to be too weak for practical purposes.

The translations that we achieve are of two types

• (i) where the computation sequence of the resulting iterative program is a rearrangement of the computation sequence of the recursive program but con­ tains the same number of steps. In these cases we save time and storage overheads associated with the stacking mechanisms (cf. factorial function below)
• (ii) where the treegrown by the recursive calls contains redundancies because the same values are cal­ culated at separate nodes. Our system may produce an iterative program whose computation sequence is shortr as well as having fewer overheads (cf. the Fibonacci function below),

Our system for recursion removal consists of four parts:

• (i) A set of translation rules. Each rule has (a) a recursive schema over certain primitives (b) an iterative schema over these primitives and (c) a set of equations over the primitives (and possibly some extra restrictions) which, if satisfied, ensure that the iterative schema produces the same result as the recursive one,
• (ii) A matching algorithm. This determines whether a set of equations is an instance of the recursive schema in one of the rules, and if so finds the substitution,
• (iii) A simple equality-based theorem prover, This seeks to prove that a substituticn is legitimate, i.e, that the equations associated with the rule are satisfied,
• (iv) A control program. This first partitions the input equations into the smallest disjoint subsets such that if the equation for f involves a call of g and vice ~ then they are in the same subset. Then, for each subset separately~ it tries to find a translation rule which applies to that subset, using the matching algorithm and the theorem prover, and effects the translation to iterative form if it finds one.

The matching algorithm is a second order one, in that it finds a substitution which takes primitive constants to expressions and also primitive functions to functions gr lambda expressions. It is described in Darlington · It was coded for lucidity, not speed. Consider fo~ example this translation rule

Recursion schema

Iterative schema

J2:1ua tiona

Restriction: x does not occur free in h,

The factorial function defined by the recursion equation

is an instance of this recursive schema, with sub­ stitution a=(x=O), b=1, d=x, e=(x-1), h=mult, This is legitimate since 'mult' satisfies the equation for h in the rule.

The translation is

This translation took 3.5 seconds on an ICL 4130 where the time for a CONS is 400 microseconds, and for HD and TL 50 microseconds. The same system took approx­ imately 0.6 seconds to calculate factorial(30) using the recursive definition and 0,06 seconds using the iterative.

The reverse function defined by the recursion equation

is also an instance of this recursive schema, with substitution a=null(x), b=nil, d=cons(hd(x),nil), e=tl(x), h=)\x1 x2; concat(x2,x1), This is a legit­ imate substitution. Notice the abstracted function that mat~hes with h. The translation is reverse ( x) =

This translation took 52.7 seconds. To reverse a list of length 40 took approximately 1.8 seconds using the recursive definition and ,06 seconds using the iterative,

Another translation rule:-

Recursive schema

Iterative schema

f(x) =

y1 :=b; y2:=b; ~:=b;

while not a do

--begin result:=h(y1,y2); y1:=y2

y2:=~; x: =d1(x)

~

Equation

d2(oC)=d1 ( d1 ~)) ,h(O( , h(p,'~) )=h(jl, h(OC., 'b'))

Restriction: x does not occur free in h or b. This applies to the Fibonacci function

giving the translation

y1:=1; y2:=1; result:=1 while not (n=O V n=1) do begin result:=y1+y2;-y1:=y2; y2:=result; n:=n-1 end

This translation took 48.25 seconds. To calculate Fib(20) took 12.8 seconds using the recursive definition and .125 using the iterative definition.

This section of our system shows the influence of the MIT philosophy 'of embedding knowledge in pro­ grams'. New knowledge, in the form of translation rules can easily be added to the system. We currenay have six schemes, mostly with several translations.

3, · Eliminating Redundant Computation

3,1, Compound operations

After removing as much recursion as possible the flattening is continued by removing procedure calls. This proceeds top down, a layer at a time, rewriting each program into another one. However, we do not proceed by the normal method of first replacing the calls of each procedure by its definition (in-line code introduction) and then optimising. Before replacing procedure calls we manipulate the program to eliminate as much redundant computation as possible and make the program 110re amenable to efficient implementation (see section 4). This we do by examining the semantic contant of the given program, ! t present we are unable to do this for whole programs and we modify them In portions consisting of sequences of testa and assignments within a loop. Consider the following sequence of assignments

S:=union(intersection(T,U),V); W:=union(interaection(T,U),W);

Clearly we can eliminate repeated computation of intersection(T,U), rewriting the sequence as

X:·intersection(T,U); S:=union(X, V); W:=union(x,w);

Suppose now that intersection and union are to be implemented in terms of list processing~he pro­ cedure body for union(X,Y) might be

result:=Y; while !lQ!_ null(X) SQ. begin if !121. member(hd(X), Y) then ~ult:=cons(hd(X),result); X:=tl(X) -- end

By replacing each call of union by this code we would obtain a program which has two loops on X. But this is unnecessary; the two can be combined into a single loop on X which builds up two result lists simultaneously. We could let the system replace each call of union separately and then try to combine the loops, but this would be quite difficult. Instead we let the system do as much manipulation as possible at the higher level, before replacing procedure calls by their bodies. Thus it would first synthesise a compound operation, which we will call doubleUlion, with definition doubleunion(X,Y,Z) = <union(X,Y),union(X,Z)>

It would then rewrite the assignment as

X:=intersection(T,U);

<S,W>:=doubleunion(X,V,W);

The system is able to produce a body of code for doubleunion(X,Y,Z), viz.

reault1:=Y; result2:=Z; while not null(X) do begin if not memb;r(hd(X),Y) --then result1:=cons(hd(X),result1); if not member(hd(X),Z) end· __ , --then result2:=cons(hd(X),result2); X:=tl(X)

and this body will be used to replace the call of doubleunion in the next stage (see section 4).

Notice that if we had started instead with the program

S:=union(intersection(U,T),V); W:=union(W,intersection(T,U));

we could have made the same economies, given the fact that intersection and union are both commutative.

3.2. Origin of compound operations

To be able to spot opportunities for forming com­ pound operations and produce the appropriate code bodies, the system preprocesses the definitions to produce

• (i) A list showing which combinations of higher level operations can be formed into useful compound operations. This is used during the manipulation of the higher level program.
• (ii) A schematic table that enables any synthesised compound operation to be expanded into code which is already in an optimised form. This table is used in the next stage to replace procedure calls by their bodies (see section 4).

This list and table are then used in the trans­ formations of all programs written using these operations. To produce them the program uses a rewrite rule showing how certain combinations of loops can be condensed.

Suppose for example that it is given these definitions:

union(X,Y) <= result:=Y; while not null(X) do begin if not member(hd(X), Y) thm result :~ns (hd (x), result);-- X:=tl(X) --- end subtract(X,Y) <= result:=nil; while not null(X) do berin if not member(hd"(X),Y then reault:=cons(hd(X),result) X:=tl(X) --­

end

All these definitions can be condensed using a rewrite rule

and

rewrites to

end

so that f12(x,y,z) = <f1(x,y),f2(x,z)>

Here x,y,z may each represent several varEbles, not just one, and a,b,f,g,h are arbitrary functions.

The system uses this to preprocess the defini~cns and produces

• (i) a list ((union,subtract,intersection)) showing that all these operations can be combined into compound operations, provided that when they occur in programs the variables they iterate on (in this case the first variable) have the same value,
• and (ii) a table from which code can be produced to realise any synthesised compound operator of this type, namely

3.3. Program manipulation

If we work on assignment sequences directly it is not easy to recognise common subexpressions and to detect opportunities for introducing compound operations. So the system executes the given sequence of assignments symbolically and finds what state transformation it produces, that. is, it com­ putes the final value for each identifier as an expression in terms of the initial values. In the above example, given initial symbolic values s 0 ,T 0 ,u 0 , v 0 and ~O' for variables S,T,U,V and W the final state vector ~s

The search for common subexpressions and compound operations is performed on the 5-tuple of expressions constituting the values of S,T,U,V and·w. This~ate 5-tuple is rewritten, introiucing subsidiary variables in where clauses (in fact the internal representatio~s pointers to list strudures), thus

This new 5-tuple of expressions must now be con­ verted back to assignments.

To summarise, there are three steps (1) convert from assignments to state transformation (2) rewrite the state transformation, and (3) convert back to assignments. We will make a few more remarks about each.

~· From the sequence of commands the trans­ formation induced is extracted by running the sequence on symbolic data. From this state transformation a set of equivalent transformations are produced by applying all the appropriate algebraic equations (commutativity etc.), to a given degree of effort.

Step 2. In each o·f these state transformations the program seeks common subexpressions and compound operations.

The improvements made in this step can be represented as rewriting rules on n-tuples of expressions. They introduce 'where clauses' using new identifiers, to show the sharing. Let E, F and G be meta-variables denoting expressions and v be a meta­ variable denoting a (suitably distinct) identifier. We use E(E 1 , ··· ,E) to denote an expression with sub­ expressions E 1 , ·· ~,En.

The rewriting rule for extracting common sub­ expressions is:-

A quite elaborate matching process is used to determine w§ere these rules are applicable, (Darlington gives details). For each of the variant state transformations produced by using the equations, the system finds all subexpressions occurring in it and matches the Fi against them for each compound f. At this stage only the most promising one, as judged by a rough efficiency estimate is retained. This is rewritten in terms of the compound operations.

• ~. The system converts the rewritten state transformation to a sequence of assignments. It cal­ culates a set of differences between the final expressions for the identifiers and their initial values, an§ then py 0 forms a G.P.S.-like search (Ernst and Newell , Simon ). For example, tryin~ to achieve the transformation <X=consset(X 0 ,Y 0 ),Y=~~ 0 > the system notices three differences between ini~ial and final values. It tries to remove these in all possible sequences until it succeeds. It would first try 'X:=consset(X,Y);·, but Y still differs

from its final value and x 0 is lost. So it tries successively 'Y:=X; Z:=X;', which loses Y too soon, and 'Z:=X; X:=consset(X,Y); Y:=Z'. If necessary it introduces extra identifiers.

• It seems crucial that the manipulation is done on the higher level program, before replacing pro­ cedure calls, for two reasons.
• (a) The higher level programs are often much simpler and easier to understand, since usually a single operation expands into a body of code.
• (b) We are able to make full use of the algebraic laws appropriate to this higher level. For example, once calls to set operations have been replaced by their list processing bodies many possibilities for rearrangement and optimisation will have been lost. Thus union(X,Y)=union(Y,X) but if union is represented by list concatenation, ® , the results X 0 Y and Y @ X are two different lists although they represent the same set. So no list optimiser would commute the arguments however great the gains in efficiency.

4. Replacing Procedure Calls by their Bodies

Here the system replaces calls of basic oper­ ations by their procedure bodies and replaces com­ pound operations by code bodies produced using the compound operator table described earlier.

In our example above the program

X:=intersection(T,U); <S ,W>:= doubleunion(X,V,W);

expands into a list program

result:=nil;

while not null(T)

do begin if member(hd(T),U)

then result:=cons(hd(T),result);

T:=tTITT;___

~;

X:=result; result1:=V; result2:=W;

while not null(X)

do begin if not member(hd(X), V)

then result1:=cons(hd(X),result1);

if not member(hd(X),W)

--t~ result2:=cons(hd(X),result2);

X:=t'i"{'XT;

end;

S:=result1; W:=result2;

At present the system has definitions to provide a choice of two representations for sets: lis~ or bit strings. These involve different sets of com­ pound operations. The user chooses one of the rep­ resentations.

5. Reusing Discarded List Cells

In any program that contains lists as data structures our system isable to take the improvement further. It attempts to transform constructive list programs, which allow assignment only to ident­ ifiers, into destructive ones, which allow assign­ ment to parts of structures, for example 'hd(Y):=X'. In LISP terms it eliminates CONS in favour of REPLACA and REPLACD. Programs written 'destructively' are efficient in store usage, but they are recognised as being difficult to understand or debug since side effects of deaructive assignments are often far from obvious.

The process involved in this transformation follows the same pattern as described in section 3. It is regarded as a rewriting between two levels of language, a 'constructive' list language and a 'destructive' list language. Again the system

--operates by finding the state transformation and re­ interpreting it as efficiently as possible.

The optimisation attempted is to avoid store usage by reusing any list cells that will have been discarded. This process can be thought of as a compile time garbage collection.

The system takes a sequence of assignments and works out the symbolic state transformation they induce. Usually information is available to make the starting state more detailed than before. Thus before X:=tl(X) we know that X should have as value a list of at least one element. To examine store usage we explicitly name list cells and define a starting state in terms of identifiers, I, Atoms, A, list cells, C, and variables, v. Thus a state is a triple of finite functions,

val: I->A V C U V

tl: C->A U C v V

hd: C->'A V C v V

The variables, V, stand for unspecified list cells or atoms (compare the variables x 0 ,Y 0 ,z 0 used previously).

For example before the program

Y:=cons(hd(X), Y); X:=tl(X)

the system creates a symbolic state

and after executing the above program on this symbolic state it would have a final state

The system now performs a 'symbolic garbage collection' on this state description to see if any cells have been disoarded, and attempts to reuse these to avoid the introduction of new cells, In the example it finds that it can use the discarded cell c 1 instead of introducing the new cell c 4 , and it rewrites the final state thus

The system now tries various sequences of assignments (exhaustively but with a G.P.S.-like difference-operator table) to achieve a sequence of instructions to implement the new transformation but avoiding cons's. In our example the sequence pro­ duced is

NEWVAR1:=tl(X); tl(X):=Y; Y:=X; X:=NEWVAR1

Thus the list reverse program

result:=nil; while not null(X) do begin result:=cons(hd(X),result); X:=tl(X); ~;

is automatically converted to a reverse program which uses no new store:-

result:=nil; while not null(X) do begi( NEWVAR1 :=t'ITX); tl X):=~; ~:=X; X:=NEWVAR1; ~;

This translation took 2.125 seconds.

6. Use of the System

One can experiment with the system using simple interactive facilities; a sample dialogue is given below. The user can invoke any of the three processes: recursion removal (Stage 1 above), eliminating redundant computation with code intro­ duction (Stages 2 and 3), and destructive list pro­ cessing (Stage 4), The system can be applied to a new domain of discourse just by giving it new rules and definitions. The table of recursive schemas and iterative equiv­ alents and t he table of iterative compounds are independent of domain; they may of course be extended To apply the system to the finite sets domain, so that it translates recursion equations in basic set oper­ ations (consset, choose, nullset etc.) to destructive list processing programs or to bit string processing programs, we have provided the following,

• (i) Equations about the basic set operations, commutativity etc, (used in Stages 1 and 2)
• (ii) Procedure bodies to implement the basic set operations by list operations (used in Stage 3)
• (ii') as (ii) for bit strings instead of lists.

For the finite set application the system has a few extra tricks built into it as program, We would like to express these by rules or tables.

The idea of symbolic execution of parts of a program has proved fruitful and we would like to explore further applications for it, It ha~ 1 als· been used at Edt~burgh by Burstall and Topor and Boyer and Moore · Our expression optimising techniques seem to go beyond those ~ed in current 14 compile1~ (see for example Sheridan , Rohl and Lin ; Hopgood , page 74 gives further raferences).

7. Example of Use

STARTSYSTEM(); (user commences dialogue) START OF OPTIMISATION.INPUT PROaRAM TO BE OPTIMISED (systems response) union(x,y)= (user inputs program) nullset(x)->y, not nullset(x) ->consset(choose(x), - union(minus(choose(x),x),y)) WHICH OPTIMISATION PROCESS WOULD YOU LIKE PERFORMED REC (user requests recursion removal stage) RESULTING PROaRAM IS result:=y; (system outputs result) while not nullset(x) do begin result: =consaet (choose (x) .m.!!l!) ; xsave:=minus(choose(x),x); y:=y; x:=xsave; end WHICH OPTIMISATION PROCESS WOULD YOU LIKE PERFORMED (user wishes to continue optimising this program) CODEINTRO DO YOU WISH TO IMPLEMENT IN LIS.TS OR BIT STRINGS BIT STRINGS RESULTING PROGRAM IS l:=length(x); n:=1; result:=yj while n<l do begin if x'Ln]=1 then begin reault[nl:=1; x[n]:=O; xsave:=x; end · --' n:=n-1 end WHICH OPTIMISATION PROCESS WOULD YOU LIKE PERFORMED FINISHED (user has finished with this program) DO YOU WISH TO PERFORM ANOTHER OPTIMISATION YES (user continues with another program) INPUT PROGRAM TO BE OPTIMISED doneshuffle:=true; (user inputs sorting while doneshuffle do program) begin doneshuffle:=false; result:=nil; last:=hd(xl); whil~null( tl(xl)) do

begin if last..$,hd(tl(xl)) then begin result:=cons(last,result xl:=tl(xl); last:=h xl end else begin xl:=tl(xl); result:= ---cons(hd(xl), result doneshuffle:=true end· re;llit:=cons(last,result); ~verse(result~ end; result:=xl; WHICH OPTIMISATION PROCESS WOULD YOU LIKE PERFORMED MAKEDEST (stage 4 store overwriting) RESULTING PROGRAM IS doneshuffle:=true; while doneshuffle do begin doneshuffle:=false; result:=nil; last:=hd(xl); whi~ null(tl(xl)) cb begin if last..$,hd( tl(xi}) then begi( -- hd xl) :=last; last:=hd( tl(xl)); newvar1:=tl(xl); tl(xl):=result; result:=xl; xl:=newvar1 --- ~ else begin -- newvar1 :=tl(xl); hd(xl):=hd(tl(xl)); tl(xl):=result; result:=xl; xl:=newvar1; donashuffle:=true; m end result:=cons(laat,result); xl:=reverse(result~ m; result:=xl;

Acknowledgements

We would like to thank our colleagues in the School of Artificial Intelligence for many helpful conversations, Brian Randell for valuable criticism, Eleanor Kerse for speedy and accurate typing, and the Science Research Council for financial support.