Re: summary: lilypond, lambda, and local-eval

[Mark H Weaver <mhw@netris.org>]

Hello all,

Although it has not yet been decided whether `local-eval' will be
accepted into Guile 2, I've decided to proceed with a proper
implementation that is fully integrated into the compiler.

I hope to demonstrate that this feature can be implemented easily
without creating any significant maintenance burden.

Here's an outline of my plan:


How to compile (the-environment)
================================

Most passes of the compiler will pretend that (the-environment) is
replaced by tree-il code corresponding to the following standard scheme
code:

  (make-lexical-environment  ;; a normal procedure (constructor)
    (case-lambda  ;; general dispatcher to access or mutate any lexical
      (() #f)
      ((name-XXX)            ;; name-XXX is a gensym
       (case name-XXX
         ((<var>) <var>)     ;; one clause for each lexical
         ...))
      ((name-XXX value-XXX)  ;; name-XXX and value-XXX are gensyms
       (case name-XXX
         ((<var>) (set! <var> value-XXX)) ;; one clause for each lexical
         ...)))
    (quote <compiler-environment>)  ;; simple list structure
    (quote <expander-environment>)  ;; simple list structure
    <module>)  ;; XXX not sure how best to represent this

The <expander-environment> is extracted from the tree-il node
corresponding to (the-environment), created by the macro expander.
I've already implemented this part in my previous patch.

The <compiler-environment> would include a list of lexical variable
names (<var> ...), which must exactly correspond to the closure slots of
the `case-lambda', in order to implement `local-eval'.  We _might_ also
need to include some information about how those variables are stored,
e.g. a flag telling whether they are boxed.  (Usually they will all be
boxed, but

Note that general-purpose dispatcher will not actually be used by
`local-eval'.  Its purpose is primarily to force all of the visible
lexicals to be boxed and included within the closure.  They are also
there to make any fancy optimizers do the right thing.

KEY POINT: Since the general-purpose dispatcher would be sufficient to
implement `local-eval' in standard scheme, it communicates exactly the
right facts to the code analyzers, no matter how clever they are, and it
does so without the analyzers having to know anything about these new
primitives!


How to implement `local-eval'
=============================

When `local-eval' is called on a lexical environment that was created by
compiled code, it will do the following:

* Macroexpand the local expression within <expander-environment>.

* Compile the expanded expression within <compiler-environment>.
  (I'll explain how to do this below)

* Make a copy of the closure from the lexical environment object, but
  replace its code (the dispatcher) with the newly compiled code.

* Call the newly created closure.

So, the trick is to make sure that the newly compiled code accesses the
closure variables in exactly the same way as the general-purpose
dispatcher.

I haven't yet dug deeply enough into the compiler internals to know the
best way to do this.  Ideally I would create a new procedure to handle
this simply and robustly, making use of <compiler-environment>.

For now, I will describe a method that I suspect would do the right
thing without any new compiler interfaces, though not as efficiently or
robustly: Simply compile the same general-purpose dispatcher as before,
except replace the #f (from the first case-lambda clause) with the
expanded local expression:

  (lambda (<var> ...)  ;; list of lexicals from <compiler-environment>
    (case-lambda
      (() <expanded local expression>)
      ((name-XXX)            ;; name-XXX is a gensym
       (case name-XXX
         ((<var>) <var>)     ;; one clause for each lexical
         ...))
      ((name-XXX value-XXX)  ;; name-XXX and value-XXX are gensyms
       (case name-XXX
         ((<var>) (set! <var> value-XXX)) ;; one clause for each lexical
         ...))))

and then extract the code from the inner `case-lambda'.  As described
above, this code would replace the code portion of the captured closure.

NOTE: This assumes that case-lambda creates only one closure for all
cases.  I confess that I haven't yet verified this suspicion.  If this
is not true, one could replace the case-lambda with the equivalent using
standard scheme.


Again, I don't expect to actually use this hack.  I expect to simply
introduce a new internal compiler interface that essentially does the
same thing, but in a less fragile way.

However, I hope that these draft notes will give confidence that it is
possible to implement `the-environment' and `local-eval' without adding
any additional complexity to the compiler.  No changes should be needed
to the analysis or optimization passes, aside from adding some clauses
to `record-case' for `the-environment' tree-il nodes, and a new
procedure or two to handle `local-eval'.

I intend to implement this soon.  Comments and suggestions solicited.

     Best,
      Mark