5.3 Lambda-lifting

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);
}