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

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

Andy Wingo <wingo@pobox.com> writes:
> Are you certain that it is desirable to transform it into standard
> Scheme code?
>
> The statement that the-environment acts "as if it were the expression,
> (case-lambda ....)" doesn't mean that you have to implement it that
> way.

Yes of course, but nonetheless it was tempting because it would have
made the compiler implementation of `the-environment' and `local-eval'
much simpler.

However, having thought about it some more, I agree that this is the
wrong approach.  It would have worked well with the particular
implementation of closures that we use in the compiler, but I haven't
figured out how to make it work with the evaluator.  Furthermore, I can
imagine more advanced implementations of closures in a native compiler
that would break this approach as well.

>> Indeed, only the macro expander has enough information to generate an
>> optimal list of "reachable lexicals", i.e. lexical variables that are
>> accessible using normal symbols (as opposed to syntax objects) [more
>> on this below].
>
> Are you certain that you want to restrict the set of identifiers?
>
> To me it sounds like an optimization, perhaps premature.

I can certainly believe that it might potentially be useful to capture
the entire environment, in case someone wants to do something clever
using a mixture of syntax-case and `the-environment'.

However, I think that for many (most?) usage scenarios, the expression
passed to `local-eval' will never reference these shadowed or hidden
identifiers, and this could make a noticeable difference in what the
optimizer is able to do.

It's easy to support both modes.  If you feel strongly that the default
(the-environment) should capture everything, I'm probably okay with
that, but I'd like to support the other mode too.

Ideally I'd like to allow the user to specify a precise list of
variables to capture, and perhaps the other two variants should be
implemented in terms of this one.

> What do you think about having a <the-environment> tree-il form have a
> field for the names and a field for the gensyms of captured lexicals?

Yes, I think this is the right approach.  It will need an
<expander-environment> as well, of course.

> We could compile `the-environment' so that at runtime it yields a record
> containing a vector of syntax objects and a vector of corresponding
> variable objects.  (When the compiler boxes a variable, it does so in a
> variable object, as from make-variable.)  Then you don't introduce
> cross-cutting assumptions to the compiler and runtime.

I like the idea of explicitly including vectors of variable objects and
variable names instead of creating a closure.  This decouples the
implementation of `local-eval' from the details of how closures are
represented.

However, I'm not sure about the syntax objects.  What would we use them
for?  The first thing `local-eval' does is to macroexpand the new
expression within the captured <expander-environment>, and henceforth
the compiler will see only gensyms.  So it seems to me that those
gensyms are what we need.

> Maybe what we need is a <lexical-capture> form that evaluates to the
> variable corresponding to a bound lexical.  Then `the-environment' could
> expand out to
>
>    (make-struct/no-tail <lexical-environment>
>                         '(name ...)
>                         (list (capture-lexical name) ...))

This is a very interesting idea.  Note that we'd need to capture the
<expander-environment> as well.  Also, the quoted list of names would
need to be the gensyms created by the expander, not the source names.
(Maybe that's what you meant, but I wasn't sure).

> You would still need support from the expander to get the set of
> currently-bound names, but maybe that is a new primitive that we could
> add.

This is easy enough.  I've already written code for psyntax that
generates a list of lexicals that are reachable using normal symbols.
Creating a list of lexicals reachable by arbitrary syntax objects is
even easier.

> Could we do it all with two new low-level primitives?  And then, could
> we actually put `the-environment', environment accessors, and everything
> else into a module?

This is a very interesting idea.  If we used this approach, we would
also need a third primitive to capture the expander-environment, perhaps
called (the-expander-environment).

This again raises the problem that what to do when (the-environment), or
in this case (the-expander-environment), is found within a macro
definition.  I think I finally have a good answer: do what datum->syntax
does.  Take an extra syntax-object parameter, and use the lexical
context associated with that syntax-object.

(the-expander-environment <for-syntax>) would expand to (quote
<expander-environment>), where <expander-environment> corresponds to the
lexical context of the syntax-object <for-syntax>.

I'm not yet certain, but I think I like the idea of using these
primitives to implement (the-environment).

* * * * *

By the way, two other complications have come to my attention:

First of all, when we compile a file containing (the-environment),
gensym names will be serialized into the .go file as constants.  When
`local-eval' later macroexpands a local expression within an
<expander-environment> that had been serialized from an earlier Guile
session, it needs to ensure that new gensyms do not collide with the
older ones.  An easy solution would be for the local macroexpander (the
one that resumes from a captured <expander-environment>) to first make
sure the gensym counter is larger than any of the gensyms stored in that
environment.

The second complication is that an <expander-environment> captured
within a `let-syntax' form contains the lexically-bound syntax
transformer _procedures_, which are obviously not serializable and
therefore cannot be stored in a .go file.  I guess the simple solution
here would be to document that (the-environment) within `let-syntax',
`letrec-syntax' or equivalent is not fully supported, and currently
cannot be compiled to a .go file.

I'll have to think about whether this limitation could be lifted.  In
theory, it should be possible to serialize syntax-rules macros at least,
though even that might be a pain.  I'm not hopeful that it can be done
for procedural macros in the general case.  However, I don't see this as
a show-stopper in any case.  It's no more serious than the existence of
procedures to the feasibility of `read' and `write'.  We simply document
the limitation.

What do you think?

      Mark