Alexander Kjeldaas wrote:
On 3/15/07, Thomas Lord <[EMAIL PROTECTED]> wrote:
Mikael Tillenius wrote:
> Thomas Lord wrote:
>> AndrevanTonder wrote:
>>> I would like to be able to reason about the space behaviour of a
>>> program using the formal semantics.
>>
>> Please, no. That would mean that an implementation which did
>> not exhibit the space behavior you predict that way is not
conforming.
>> It sounds to me like you want a mathematical model of space
>> behavior *of some particular implementations* (and, you'd want
>> a proof that that model is consistent with the formal semantics).
>>
>> The formal semantics should describe, as far as practical, the
>> constraints that apply to all implementations -- but nothing
>> more.
> Please yes! ;-)
>
> If space and time behaviour cannot be entirely ignored in real world
> programming. While it is impossible to describe these in terms of
> seconds and bytes a programmer must be able to know whether an
> algorithm is O(1), O(n) or O(2^n) in terms of both space and time and
> this must be the same on all reasonable implementations.
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?
What if scheme had immutable strings? Henry Baker sais this about
functional strings in "Equal Rights for Functional Objects or, The
More Things Change, The More They Are the Same" (which btw includes
some really good arguments in favor of immutable objects)
http://home.pipeline.com/~hbaker1/ObjectIdentity.html :
"Functional strings can have interesting implementations. A
representation of a string as a tree whose leaves are individual
characters offers O(1) complexity concatenation; while element
indexing is more expensive, it is usually less common than
concatenation."
Alexander
You miss my point. We have overwhelming empirical evidence
that in some situations it is useful for string-ref to be O(1) and
in other situations for it to be O(n). If an implementation is
to be Scheme, is its choice between those to be mandated by the
report?
-t
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
