Re: First-class environments

On 4/5/06, Michael Vanier <[email protected]> wrote:
> For instance, are there
> certain important language features or optimizations that first-class
> environments make impossible?

First-class environments essentially make it impossible to reason
about variable values and locations.  Consider this code:

(let ((x 5))
    .....
    (foo x)
     .....)

Without first-class environments, we can know that X will be bound to
5 when we call FOO.  We simply check that there are no intervening
assignments.

In this code:
(let ((x 0))
  (let ((y 1))
    (lambda () (set! x (+ x y)) x)))

We don't know the value of X, but we do know that it is lexically two
frames back and the first variable in the frame.  If we can modify the
environment, we could introduce a new binding of X in the same frame
as the binding of Y.  This would require that the code that refers to
X perform a deep-search on lookup because the binding could be
shadowed at any time by a closer binding.

Full-featured first-class environments are therefore a problem, but
there may be a use for less featureful ones.  If you prohibit
introduction of new bindings, then you can compile the variable
lookup.  If you prohibit side-effects and allow the compiler to
re-arrange the variables, then you can do most of the `normal'
optimizations.  It is hard to write code that uses this feature though
because different compilers may choose to lay out the environment
differently.

--
~jrm