[bitc-dev] Re: Closure Conversion

Swaroop Sridhar swaroop at cs.jhu.edu
Thu Jul 7 17:29:38 EDT 2005


Jonathan S. Shapiro wrote:
> 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
This is a good idea, and I think we should implement closure conversion 
this way.

I was trying to perform this step as a well-typed AST to AST transform 
(without any run-time code generation). For reasons like:
1) Facilitating full optimization by the C compiler.
2) When time comes for proving properties of the compiler itself,
    AST->AST transformations are easier to reason about.
3) For providing accurate RTTI.
4) At some point, if there is a BitC GC, [1] recommends typed closures
    for tag-free garbage collection.


However, I think we can live with untyped closures. Later versions of 
the compiler may use a different strategy if deemed necessary.

Swaroop.
PS: I think even the Ocaml compiler does not use typed closures

[1] Y. Minamide, G. Morrisett, and R. Harper. Typed closure conversion. 
In Twenty-Third ACM Symposium on Principles of Programming Languages, 
pages 271--283, St. Petersburg, Jan. 1996.


More information about the bitc-dev mailing list