[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Vectors as functions

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

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'

rather than the expected:
    push arg 0
    push literal 1

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