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

From: Thomas Lord <lord>
Date: Thu Mar 15 17:31:49 2007

Mikael Tillenius wrote:
> Thomas Lord wrote:
>> 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. What I meant was that the specification in 5.92 is hard to
> implement efficiently (e.g. string-ref is O(1)) if you want to store
> the strings internally as utf8 or utf16. Some people want to do that.
> Therefore (among other things) the current specification is
> controversial.

Oh, well... my formal comment (submitted last night) would fix that.
The changes it advocates, alas, require more work than is present in the
proposal but hopefully it is enough to spark some interest in the direction.

-t



>
>> Firm up what *you* mean by "reasonable", give that thing a more
>> reasonable name than "reasonable", and refer to that.
> Sorry but I'm vague on purpose here. But to give you some examples: It
> is reasonable if things like string-ref, vector-ref is O(1) in time.
> Its reasonable if a string with n characters use O(n) bytes. It is not
> reasonable for string-ref and vector-ref to take O(n) time. It's not
> reasonable for a string with n characters to use O(n^2) bytes of memory.
>
> Another way to define what I mean by reasonable is to say that every
> Scheme implementation I know about is reasonable.
>
> Ok, were getting off topic here. To sum things up I think is is useful
> to be able to assume certain things about time and memory consumption
> in a programming language. Maybe it does not belong in the language
> specification.
>
> /Mikael
>
>
Received on Thu Mar 15 2007 - 17:41:10 UTC