Next: Statement-lifting, Previous: Building Closures, Up: Principles of Compilation [Contents][Index]

When this pass starts, all the real (nonliftable) closures have been translated to closure-creating code. The remaining lambda-terms are all liftable.

Lambda-lifting is performed. That is, all procedures defined inside
some other procedure (eg. in `letrec`) and unnamed lambda-terms are
made top-level procedure definitions. Any N variables not bound in such
procedures which were bound in the surrounding procedure are given as
extra N first parameters of the procedure, and whenever the procedure is
called, the values of these variables are given as extra N first
arguments.

For example:

(define foo (lambda (x y) (letrec ((bar (lambda (u) (+ u x)))) (bar y) )))

is converted to

(define foo (lambda (x y) (foo-fn1 x y) )) (define foo-fn1 (lambda (x u) (+ u x) ))

The case of mutually recursive definitions in `letrec` needs special
treatment – all free variables in mutually recursive funs have, in
general, to be passed to each of those funs. For example, in

(define (foo x y z i) (letrec ((f1 (lambda (u) (if x (+ (f2 u) 1)))) (f2 (lambda (v) (if (zero? v) 1 (f1 z)))) ) (f2 i) ))

the procedure f1 contains a free variable x and the procedure f2 contains a free variable z. Lambda-lifted f1 and f2 must each get both of these variables:

(define (foo x y z i) (foo-fn2 x z i) ) (define foo-fn1 (lambda (x z u) (if x (+ (foo-fn2 x z u) 1))) ) (define foo-fn2 (lambda (x z v) (if (zero? v) 1 (foo-fn1 x z z))) )

Recall that hobbit has already done dependency analysis and has
split the original `letrec` into smaller chunks according to this
analysis: see pass 1.

Whenever the value of some free variable is modified by `set!` in
the procedure, this variable is passed by reference instead.
This is not directly possible in scheme, but it is possible in C.

(define foo (lambda (x y z) (letrec ((bar (lambda (u) (set! z (+ u x z))))) (bar y) z)))

is converted to incorrect scheme:

(define foo (lambda (x y z) (foo-fn1 x (**c-adr** z) y) z)) (define foo-fn1 (lambda (x (**c-adr** z) u) (set! (**c-fetch** z) (+ u x (**c-fetch** z))) ))

The last two will finally be compiled into correct C as:

SCM foo(x, y, z) SCM x, y, z; { foo_fn1(x, &z, y); return z; } SCM foo_fn1(x, z, u) SCM x, u; SCM *z; { return (*z = (u + x) + *z); }