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

From: Shiro Kawai <shiro>
Date: Thu Mar 15 22:55:57 2007

From: John Cowan <cowan_at_ccil.org>
Subject: Re: [r6rs-discuss] [Formal] Formal semantics should not contain complicating optimizations
Date: Thu, 15 Mar 2007 22:32:51 -0400

> Thomas Lord scripsit:
>
> > 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?
>
> No, it is not to be mandated by the report, and it isn't.
>
> BTW, it occurred to me that a representation-switching implementation
> of strings can switch representations atomically provided the
> pointer to the code units (8-bit, 16-bit, or 32-bit) contains
> some tag bits indicating which one it is. When a string mutator
> detects that it needs to convert the representation, it builds up
> a new representation in freshly allocated memory, constructs the
> specially tagged pointer to it, and atomically swaps in the new
> pointer for the old. No locks.

That's similar to what Gauche does for its utf-8 string. A
Scheme string is merely a type tag and a pointer to a "string body".
Mutation causes allocation of a "string body" and swapping the
pointer atomically.

--shiro
Received on Thu Mar 15 2007 - 22:55:43 UTC