[r6rs-discuss] [Formal] Formal semantics should not contain complicating optimizations

From: Thomas Lord <lord>
Date: Thu Mar 15 14:58:11 2007

Mikael Tillenius wrote:
> Thomas Lord wrote:
>>
>> How would you reconcile your category of "reasonable implementation"
>> with all of the complexity-varying, all useful approaches to
>> implementing
>> string-ref that people talk about?
>>
> Isn't this part of why strings is so controversial. Different people
> want to implement them in different ways and at the same time be able
> to access parts of them in a efficient way.


Yes. And, in practice, it is useful to implement them in different
ways and, at the same time, by which metrics we mean "efficient" varies
from situation to situation.


>> Yes, some of that language probably needs cleaned-up, with particular
>> attention
>> to the "must v. should" distinction. My gosh, if we were to get to
>> that point
>> before the end of this year, in my view, it'll probably be evidence
>> that R6 is
>> shaping up nicely.
>>
> It would make it harder to use Scheme as a way to talk about
> algorithms and their efficiency if we cannot do some basic assumptions
> about the underlying Scheme implementation. Of course one could always
> say things like: "On a reasonable implementation this algorithm would
> be O(n)".

Firm up what *you* mean by "reasonable", give that thing a more
reasonable name than "reasonable", and refer to that.


-t
Received on Thu Mar 15 2007 - 15:07:23 UTC