About a year ago I implemented immutable strings in Java. But, I hear you say, immutable strings are part of the standard Java library. Yes, but not like this.
Cedar Mesa work at PARC included a data structure called a Rope (an "industrial strength" String). A Rope is an immutable string structured as a tree. The leaves are "flat strings", simple arrays of characters. The interior nodes are
(1) concat nodes, which represent a rope that is the concatenation of the left and right child ropes; or
(2) substring nodes, which represent a substring of a child rope, indicated by starting offset and length; or
(3) functional nodes, which compute the characters of their contents by executing code. For example, a functional node might represent a rope as a file name, length and offset within that file.
In an object-oriented language, (3) would of course be replaced by "any object that implements the core methods that define ropefullness".
Ropes appeared again in PARC's Portable Common Runtime (under the name "cords", because they were better than strings, but not as tough as ropes), as a sample application for Hans Boehm's garbage collector, and as part of SGI's C++ standard template library. All I did was re-implement Ropes in Java.
Ropes have a number of nice properties.
(1) They are immutable. We have already talked about some of the advantages of this, primarily the fact that immutable strings can be shared freely without the need to protect oneself by making a copy.
(2) Concatenation, Substring, and fetching the i th character can all be implemented in time proportional to the log of the size of the argument. In practice, we delay re-balancing in order to make concatenation take unit time, because concatenation is such an important operation.
(3) Smalltalk style iterators (do:, collect:, etc.) take time proportional to the length of the rope. Loops of the form
for i := 1 to length(str) do { code involving str[i] .... }
might take time n log n (where n is the length of the string), unless we do some careful caching. It is hard to get C and Java programmers to stop writing code like this. Fortunately, in Smalltalk this should not be a problem.
(4) String operations scale to long strings, with good performance.
(5) Strings stored in files and strings available over the network, for example, can be treated in exactly the same way as strings in main memory. Most of the string manipulation functions can be written once in an abstract superclass and reused.
(6) In Java, all strings are Unicode strings, but there is really no need to allocate the same number of bytes for all characters in a String. A long ascii string with a few 2-byte characters in the middle could be represented efficiently as the concatenation of 1-byte per character flat strings and a 2-byte character flat string.
The main advantage of immutablity is that once the programmer is _assured_ that a string is immutable, she is freed from concerns about whether it is necessary to synchronize updates, make copies, update caches, etc. If mutable strings exist, it of frequently necessary to copy them, just to guard against the possibility that they might change in the future.
One possibility would be to have a subclass "InitiallyMutableString" which can be destructively updated, and then "frozen". Once an InitiallyMutableString is frozen, it would become a String (immutable) and the update operations would fail. This could be implemented with becomes: or by setting a bit in the string.
I had been hoping to find time to translate my Java implementation of Ropes into Smalltalk. There are several "gotchas" in Java that prevent them working as one would like. In particular, since String is a class, not an interface, it is in general impossible to replace String by something better, without recompiling the whole world. It is not even possible to subclass String to introduce other variants, because String is a _final_ class. And then there is the problem with numeric indexing loops mentioned above.
In Smalltalk these problems don't arise. I had really looked forward, for example, to using file strings in the directory browser, instead of the current hack of reading only the first 5k of the file.
I have a student working on the Java implementation right now. My hope is to have her run some comparative performance measures on my version (cord.String) and java.lang.String, and see if it makes sense to lobby the Java world for a wholesale replacement. Once these measurements are done, I think that I could offer to do a Smalltalk port. Most of the code is straightforward, with the exception of tree balancing. However, there is some performance tuning that needs to be done on a per-platform basis. For example, concatenating "ab" and "cd" is most efficiently done by copying them into a new four character string, but concatenating a two 1k strings is best done by allocating a concat node. Up to what length should one copy? The answer depends of the relative costs of copying, and allocation, as well as the pattern of usage; it needs to be tuned on each system.
If someone thinks that "Smalltalk Ropes" are the right way forward, and can't wait to get started, I would be happy to provide them with the Java version.
Andrew
References: On the SGI C++ implementation http://www.sgi.com/Technology/STL/Rope.html and http://reality.sgi.com/boehm/ropeimpl.html.
Background and Performance data: Boehm, Atkinson, and Plass, "Ropes: An Alternative to Strings", Software-Practice and Experience 25, 12 (Dec 1995), pp. 1315-1330.