System for conversion of loop functions in continuation-passing style5881291Abstract A compiler and compilation method for processing a source program in a programming language in the Scheme/Lisp family into a representation known as continuation-passing style (CPS) before generating object code, with optimization also being involved in the processing. To simplify the code generator and optimization, and to allow the same code generator to be used for both non-loop as well as for loop functions, novel algorithms are described which find in the standard CPS intermediate tree sets of non-continuation lambda expressions with a common continuation, which can then be converted to optimized CPS code that can be processed by the same code generator as non-loop continuation functions. Claims What is claimed is: Description This invention relates to systems for processing programming language code in the Scheme/Lisp family of programming languages representing loops into continuation functions.
______________________________________
is-a-loop-p (S, C);
for every element L of S
for every reference R to the name of L
if R is used as a call argument rather than as a function then
return false
else if the continuation in the call to R is a lambda node then
if the continuation is not C then
return false
else
continue
else // the continuation in the call to R is a reference to a variable
let V be the variable whose reference is the continuation
in the call to R.
let VL be the lambda node that binds V.
if V = C then
continue
else if VL has is a member of S then
continue
else if VL has a name then
return is-a-loop-p (S plus VL, C)
else
return false
next R
next L
return loop-set
______________________________________
The procedure find-loop-set-and-continuation takes a set S of named NCLEs and determines whether there's a continuation relative to which the named NCLEs can be extended into a loop. If so, the procedure returns the full loop set plus the continuation; otherwise, it returns false.
______________________________________
find-loop-set-and-continuation (S):
for every element L of S
for every reference R to the name of L
if R is used as a call argument rather than as a function then
return false
else if the continuation in the call to R is a lambda node then
let C = the continuation in the Call to R
let S' = is a-loop-p (S, C)
if S' = false then
return false
else
return S' and C
else // the continuation in the call to R is a reference to a variable
let V be the variable whose reference is the continuation
in the call to R.
let VL be the lambda node that binds V.
if VL is a member of loop-set then
continue
else if is-a-loop-p (S, V) then
return is-a-loop-p (S, V) and V
else if VL has a name then
return find-loop-set-and-continuation (loop-set plus VL)
else
return false
next R
next L
return false
______________________________________
Given a loop set S and their common continuation C found in the first part, convert-loop converts all the members of S into continuation lambdas. Exactly one of three conditions must be true of S and C in the found loop set: (a) C is a continuation lambda; (b) C is a continuation variable, and every member of S is within the scope of C; or (c) C is a continuation variable and at least one member of S is outside the scope of C. The second part in pseudocode is as follows with condition or case (a) expressed in the first IF statement, condition or case (b) expressed in the first ELSE statement, and condition or case (c) expressed in the second ELSE statement: convert-loop (S, C):
______________________________________
if C is a continuation lambda then
let V be a new continuation variable.
Insert into the CPS tree a call node which binds V to C,
just above the call node in which C originally
appears. Replace C by a reference to V.
return convert-loop (S, V)
else if C is continuation variable and every member of S is
within the scope of C then
for every element of L of S
Change L to be a continuation lambda
Let V be the continuation variable bound by L
for every reference R to V
replace R by a reference to C
for every reference R to the name of L
delete the continuation in the call to R
else // C is a continuation variable and some member of S is
// outside the scope of C. Because of the definition
// of S and C, every reference to every member of S
// is either within the scope of C or within the
// scope of some member of S. Therefore it's
// possible to move the members of S:
Remove the members of S from the CPS tree, along with the
names.
Just below the lambda node which binds C, introduce a new
binding call which binds all the members
of S to their names.
// Now all the members of S are within the scope of C.
return convert-loop (S, C)
______________________________________
Note that when conditions (a) and (c) are satisfied, convert-loop repeats, until condition (b) is satisfied and the routine is exited. Summarizing, when the non-continuation loop or other functions comprise a set of named NCLEs with the property that every reference to every name of the NCLEs is a call, and those references that are not tail-calls from some member of the set, are called with the identical continuation argument (either a continuation lambda or a continuation variable), determined by executing the procedures is-a-loop-p and find-loop-set-and-continuation of the first part, then one of the three specified conditions must be true: (a) c is a continuation lambda; (b) c is a continuation variable, and all the members of S fall within the scope of c; (c) c is a continuation variable, and at least one member of S falls outside the scope of c. Then, it is straightforward to provide the conversion to the optimized CPS using the convert-loop procedure of the second part. This will be illustrated with the following examples. EXAMPLE 1 Normal conversion of a fragment in the Dylan programming language which is in the Lisp/Scheme family:
______________________________________
(bind-methods ((fact (i ff)
(if (.rarw. i O)
ff
(fact (- i 1) (* i ff)))))
(+ (fact n 1) 3))
______________________________________
to standard CPS yields the following CPS tree:
______________________________________
(letrec ((fact (k i ff)
(if (.rarw. i O)
(lambda () (k ff))
(lambda () (fact k (- i 1) (* i ff))))))
(fact (lambda (v) (+ C v 3)) n 1))
______________________________________
where C is the continuation which would receive the value of the original Dylan expression. Prior art technology would attempt to recognize that fact is a loop, and special code generators would be used to arrange for calls to fact to be implemented with branch instructions, rather than with call instructions. Also, references to k would have to be treated specially, since no actual continuation would be passed. The loop set found by the algorithm first part of the invention when the foregoing CPS tree is inputted consists of just the definition of the variable fact; the distinguished continuation is the lambda expression, (lambda (v) (+C v 3)), which makes this an example of case (a). The loop conversion algorithm of the invention changes the CPS tree to:
______________________________________
(letrec ((fact (k i ff)
(if (.rarw. i 0)
(lambda ( ) (k ff))
(lambda ( ) (fact k (- i 1) (* i ff))))))
((lambda (g) (fact g n 1))
(lambda (v) (+ C v 3))))
______________________________________
which is now handled as case (c), with the variable g being the distinguished continuation. Running the loop conversion algorithm of the invention again moves the binding of fact entirely within the scope of g:
______________________________________
((lambda (g)
(letrec ((fact (k i ff)
(if (.rarw. i O)
(lambda () (k ff))
(lambda () (fact k (- i 1) (* i ff))))))
(fact g n 1)))
(lambda (v) (+ C v 3)))
______________________________________
This version of the CPS tree is now an example of case (b), which can be converted by processing convert-loop again to its final form:
______________________________________
((lambda (g)
(letrec ((fact (i ff)
(if (.rarw. i O)
(lambda () (g ff))
(lambda () (fact (- i i) (* i ff))))))
(fact n 1)))
(lambda (v) (+ C v 3)))
______________________________________
Note that fact is now a continuation, which invokes g directly in order to exit. Code generation is simplified since fact can be treated like any other continuation, without requiring any further special processing. EXAMPLE 2 The Dylan expression:
______________________________________
(+ (if (> x O)
(bind ((f (method (yy) (+ yy x))))
(if (> y O)
(f y)
(f (- y))))
O)
4)
______________________________________
yields the following standard CPS tree:
______________________________________
((lambda (g)
(if (> x O)
(lambda ()
((lambda (f)
(if (> y O)
(lambda () (f g y))
(lambda () (- (lambda (my) (f g my)) y))))
(lambda (k yy) (+ k yy x))))
(lambda () (g O))))
(lambda (v) (+ C v 4)))
______________________________________
Note that although this expression does not contain any loops in the traditional sense, the set consisting of just the definition of f, (lambda (k yy) (+k yy x)), along with the distinguished continuation variable g, satisfies the definition of a "loop set." Note also that every reference to f occurs within the scope of g, making this an example of case (b). The loop conversion algorithm of the invention re-writes this CPS tree to:
______________________________________
((lambda (g)
(if (> x O)
(lambda ()
(lambda (f)
(if > y O)
(lambda () (f y))
(lambda () (- (lambda (my) (f my)) y))))
(lambda (yy) (+ g yy x))))
lambda () (g O))))
(lambda (v) (+ C v 4)))
______________________________________
Note that the value of f, (lambda (yy) (+g yy x)), is now a continuation function, and it includes a direct reference to the distinguished continuation, the variable g. EXAMPLE 3
______________________________________
(bind ((f (method (a) (* a 2))))
(+ (if (< x O)
(f (- X))
(f x))
1))
______________________________________
Normal conversion to standard CPS yields the following CPS tree:
______________________________________
((lambda (f)
((lambda (g)
(if (< x O)
(lambda () (- (lambda (xx) (f g xx)) x))
(lambda () (f g x))))
(lambda (v) (+ C v 1))))
(lambda (k a) (* k a 2)))
______________________________________
Here the loop set is the single value for f, (lambda (k a) (* k a 2)), and the distinguished continuation is the variable g. Note also that (lambda (k a) (* k a 2)) falls outside the scope of the variable g, making this an example of case (c). The loop conversion algorithm of the invention transforms this CPS tree into the following tree:
______________________________________
((lambda (g)
((lambda (f)
(if (< x O)
(lambda () (- (lambda (xx) (f g xx)) x))
(lambda () (f g x))))
(lambda (k a) (* k a 2))))
(lambda (v) (+ C v 1)))
______________________________________
which is an example of case (b). The conversion algorithm then runs again, to produce:
______________________________________
((lambda (g)
((lambda (f)
(if (< x O)
(lambda () (- (lambda (xx) (f xx)) x))
(lambda () (f x))))
(lambda (a) (* g a 2))))
(lambda (v) (+ C v 1)))
______________________________________
Note that f's definition, (lambda (a) (* c a 2)), is now a continuation lambda expression, which invokes the distinguished continuation, g, directly as its exit. Where condition (b) obtains, as will be clear from the foregoing examples, then without difficulty we may replace all references to the continuation arguments of the members of S (other than references in calls to members of S) by references to C, and then we may delete the continuation arguments themselves and convert all the member of S into continuations. (The continuation argument in all calls to all members of S can be removed: they were either recursive calls, or calls with C as the continuation). For case (c), the criteria for selection of S, however, determined by the two procedures is-a-loop-p and find-loop-set-and-continuation, guarantees that all non-recursive references to members of S fall within the scope of C. Therefore, it is possible to "move" on the intermediate node tree the definitions of all the members of S so that they fall within the scope of C, without worrying that doing so will leave a reference to a member of S outside the scope of the newly constructed definition. For case (a) in which C happens to be a clambda node, rather than a continuation variable, we simply introduce a new continuation variable, binding it to the clambda in question, and then handle it as described above. Thus, the procedure to be followed to ensure that code representing loops and other code has been converted to the optimized form of CPS such that the resultant code can be compiled with the same code generator that is used for processing non-loop continuation functions is illustrated in FIGS. 2 and 5. The source code is processed in the usual way, and converted to form the standard CPS tree (block 15 of FIG. 1), and, in accordance with the first part of the algorithm of the invention, procedures find-loop-set-and-continuation 21 and is-a-loop-p 22 are then applied. If the find-loop-set-and-continuation procedure returns a full loop set plus the continuation, indicated by the test block 23, then a loop set is present that can be converted 24 to optimized CPS using the convert-loop procedure of the invention. Otherwise, code is present that is retained in its original CPS form. The resultant CPS code can then be processed by the same code generator to generate object code in a more efficient and effective manner. It will be appreciated that implementing the two parts of the algorithm described above in Scheme or Lisp code will be evident to any programmer of ordinary skill familiar with the language and CPS. It will be further understood that the invention is not limited to the details of the algorithms given, and those skilled in this art following the principles enunciated herein will be able to devise other ways of converting source loop expressions to CPS to produce code that can be processed with the same code generator as non-loop continuation functions in accordance with the invention. It is further noted that Example 1 is of code that represents a true loop, which is the situation which would principally use the invention for the reasons given above. Examples 2 and 3 do not contain loops in the traditional sense. Nevertheless, the standard CPS tree satisfies the definition of a "loop set", and thus subjecting the standard CPS trees to the convert-loop algorithm of the invention will result in an optimized continuation function that can be treated by the code generator in a simpler and more efficacious manner. Although there have been described what are at present considered to be the preferred embodiments of the invention, it will be understood that the invention may be embodied in other specific forms without departing from the essential characteristics thereof. The present embodiments are therefore to be considered in all respects as illustrative, and not restrictive. This scope of the invention is indicated by the appended claims rather than by the foregoing description.
|
Same subclass Same class Consider this |
||||||||||