Re: Vectors as functions

["Joe Marshall" <address@hidden>]

From: "James McCartney" <asynth@io.com>

> On Friday, August 15, 2003, at 12:29 PM, Joe Marshall wrote:
>
> > The biggest problem with first-class environments ala MIT Scheme
> > is the introduction of new bindings at runtime.  If you introduce a
> > new binding, the `lexical address' (frame and offset) of a variable
> > cannot be statically determined and you have to do a deep search
> > every time.  It absolutely destroys any sort of compiler optimization.
>
> Actually it doesn't. In this case your variable lookup becomes the
> exact same problem as method lookup in Self, which has been
> successfully optimized.

Well, I'm overstating the problem, but only a little.  Variable lookup
can be a significant bottleneck if you have to deep search each and
every time you refer to a variable. In Scheme, every LET expression
introduces a new lexical contour, and if you had no guarantee that
the user won't change one arbitrarily, you cannot `flatten' them,
fold `constants', eliminate common subexpressions, etc.

Consider this example:

(define (foo x) (+ x 1))

The compiler can assume that X will be on the stack where the arguments
are passed.

(define (foo x)
  (let ((addend 1))
    (+ x addend)))

If the user were to get a hold of the environment created by the LET
statement, he could introduce a new binding for X that shadows the argument.
So if we wish to allow this sort of manipulation, the compiler cannot
assume that X is in the first argument slot, but rather it has to chain down
the environment and examine each frame to see if a binding of X has
appeared.

Also, since we're allowing this sort of manipulation, we cannot fold the
value of '1' in because the user could change it.

For that matter, the user could shadow '+'.

So the compiled code ends up doing this sort of thing:
    lookup +
    lookup `x'
    lookup `addend'
    apply

rather than the expected:
    push arg 0
    push literal 1
    add

(actually, it could optimize the lookup of addend.  That binding is in the
innermost frame.  So replace  `lookup `addend'' with  `push arg0')