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

Re: first-class names



On Tuesday, Aug 19, 2003, at 09:37 US/Eastern, Joe Marshall wrote:

>
> ----- 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.

Or you can introduce the concept of sealing sub-domains of generic 
functions and sealing sub-classes.  Dylan leaves the <number> class 
open but seals certain subclasses like integers and + over integers.  
This allows the compiler to generate optimal code but still permit 
extension of numbers, at an appropriate price.