[bitc-dev] Closure Conversion

[Jonathan S. Shapiro]

Swaroop:

I've been thinking about your closure conversion question, and I think
that we have had a small miscommunication.

First, a simple example:

(define f1
  (let ((x 1))
    (lambda () x)))

This needs to be rewritten into something like:

(define f1
  (let ((x 1))
    (make-closure (build-closure x) (lambda (closure) closure^.x))))

where BUILD-CLOSURE is part of the runtime and MAKE-CLOSURE is a closure
constructor. Neither BUILD-CLOSURE nor MAKE-CLOSURE can be expressed
within the language.

Having done this, we now hoist the (lambda ...) to:

(define **hoisted-5109764** (lambda (closure) closure^.x))

and rewrite f1 to:

(define f1
  (let ((x 1))
    (make-closure (build-closure x) **hoisted-5109764**)))

Ignoring optimization, BUILD-CLOSURE is first called to construct the
closure. This results in a reference to a runtime-internal closure type.
Let me imagine that the returned reference has the identity
**closure-234**.  The return value of MAKE-CLOSURE is a reference to
heap-allocated *code*:

  (lambda () (**hoisted-5109764** **closure-234**))

or in the more general case:

  (lambda (args) (**hoisted-5109764** **closure-234** args))

If the lambda does not escape then the closure can be stack-allocated.

Closure conversion certainly should NOT be done blindly -- this
transform should only be done for procedures that require it.

Unfortunately, make-closure is syntax. When the variable that is closed
over is mutable, it is possible to construct cases where the closure
must contain a *reference* to the variable. In general, this can be done
by migrating the closed-over variable to the heap, but we would like to
avoid this for non-escaping closures. So for non-escaping closures, we
want the closure environment to contain an upward stack-ref.

Today, our rule is that stack-refs cannot appear in unions or structs,
so we cannot account for closures within the language.

An alternative would be to allow stack-refs within structs, but only if
the containing struct is itself stack-allocated and immutable. This
seems complex enough that I think we should handle make-closure as a
special case that builds a vector of special, internal refs.

shap