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
Received on Thu Mar 15 2007 - 13:57:03 UTC