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

From: Mikael Tillenius <mti>
Date: Thu Mar 15 17:22:47 2007

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.

> 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:25:27 UTC