Alexander Kjeldaas wrote:
> On 3/15/07, Thomas Lord <lord_at_emf.net> 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
Received on Thu Mar 15 2007 - 14:17:37 UTC