Re: first-class names

["Joe Marshall" <address@hidden>]

----- Original Message ----- 
From: "Dan Sugalski" <dan@sidhe.org>


> At 4:20 PM -0400 8/17/03, mike@newhall.net wrote:
> >  > What do you mean by "all the costs"?  And what do you mean by
> >>  "canonical implementation"?
> >>
> >>  Cheers =8-} Mike Friede
> >
> >>From earlier: "Joe Marshall" <jrm@ccs.neu.edu> 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.
> 
> No, no it doesn't. It does make some things somewhat more difficult, 
> and there are some optimizations it forbids but they're generally the 
> sort of optimizations you can't do anyway in languages that do this 
> sort of thing. (As they normally have user-defined types with 
> behavior the compiler can't normally infer well enough to do anything 
> with)

Let me rephrase that to *static* compiler optimizations.

When I write Scheme code like:
    (let ((x 22))
      (let ((y 3))
        (+ x y)))

In general I expect this to behave *exactly* as if I had written the
literal constant 25.  (there may be some *rare* exceptions, and if it
requires more work from me to make the rare exception, that's ok)

But in the presence of first-class environments, there is the *potential*
for someone to either modify the binding of X or insert a new binding
shadowing `+'.  So the value of the expression is statically indeterminate.

This leaves you with few options for static optimization.  You can't
even rewrite the expression as '(+ 22 3)'  Your compiler will be able
to inline the interpreter, but not much else.

You can either restrict the free use of first-class environments (as they
do with MIT Scheme) or introduce a more complex dynamic
compiler (as they do with Self).  I'm willing to live without pervasive
first-class environments; I rarely use them, and when I do, I'm willing
to annotate the code and take the performance hit.

Remember that the compiler isn't the only tool you might want to run
on the code.  Since the expression above is statically indeterminate
if you allow the user to manipulate the environment structure, you cannot
statically determine the type of the expression either, nor prove that
it terminates, nor prove that it does not cause an error to be raised,
nor prove that it is side-effect free, nor prove that procedure `foo'
is not called, nor prove that it does not capture it's continuation, etc.

That's an awful lot to give up.