[plt-scheme] Closure Representation

At Sun, 20 May 2007 22:58:45 -0400, "Marco Morazan" wrote:
> Thank you for the answer. I suspected as much as far as indexing the stack.
> My question is related to the creation of closures. When the values are
> obtained from the stack is only the "top" of the stack accessed (i.e. all
> values are local to the funtion being evaluated that will return the
> closure) or do free variables still exist at runtime (i.e. the indexing can
> be to bindings that are not local to the function being evaluated)?
> 
> To illustrate this:
> 
> (define (f x)
>    (define (g y)
>        (.....y......x....)))
> 
> Clearly, y is local and only requires indexing the top of the stack. The
> reference to x is what I am inquiring about. Are the values pushed onto the
> stack for f accessed while g is executed or is g lifted to the global level
> (and x added as a parameter) to make all accessess to the top of the stack
> at runtime?

When the right-hand side of the definition of `g' is evaluated, a
closure is formed (assuming the optimizer doesn't inline all uses of
`g' or convert all free variables of `g' into arguments because it can
see all applications of `g').

Since the closure for `g' is "flat", it includes the value of `x' ---
or the mutable cell for `x' if `x' is ever `set!'ed. When `g' is
applied, the value/cell for `x' is unpacked on the stack, right next to
the argument `y'. In the body of `g', accesses to both `x' and `y' use
an offset into the stack.

Matthew

> On 5/20/07, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> >
> > Bindings are always accessed by offset into a value/box stack. When a
> > closure is applied, its content is unpacked into this stack. When a
> > closure is created, each value/box added to the closure is obtained
> > from the stack by offset. The offsets are always determined at compile
> > time (i.e., local-variable names are all gone by run time).
> >
> > Hope that helps,
> > Matthew
> >
> > At Fri, 18 May 2007 20:31:14 -0400, "Marco Morazan" wrote:
> > > Thank you for your response Matthew. Flat closures need to be
> > "populated"
> > > with the bindings of the free variables. Are local functions
> > lambda-lifted
> > > (or joisted) to simplify this process or is the environment traversed at
> > > runtime to determine the bindings?
> > >
> > > Thanks,
> > >
> > > Marco
> > >
> > >
> > > On 5/18/07, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> > > >
> > > > At Fri, 18 May 2007 13:59:22 -0400, "Marco Morazan" wrote:
> > > > > Can anyone point me to a document or web page that describes how
> > > > closures
> > > > > are represented in PLT Scheme?
> > > >
> > > > What level of detail are you looking for?
> > > >
> > > > For the basic architecture, there's no document specific to PLT
> > Scheme,
> > > > but the implementation is one of the typical points in the spectrum
> > > > described by textbooks. MzScheme's closures are essentially "flat": a
> > > > code pointer is packaged with the values (or boxes, in the case of
> > > > mutable variables) associated with its free variables. For
> > module-level
> > > > bindings, though, there's an extra indirection: one reference in the
> > > > closure record to an array of module bindings (and the array is shared
> > > > for all closures in the same module).
> > > >
> > > > If you want to know the actual byte layout for some reason, see
> > > > `Scheme_Closure' and `Scheme_Native_Closure' in
> > > > "src/mzscheme/src/schpriv.h". Beware that the `vals' array is not
> > > > actually an array of values; it can contain mutable-variable
> > > > indirections and a module-level array, as noted above.
> > > >
> > > > Matthew
> > > >
> > > >
> >