Invariant Strings
written by Walter Bright
Mar 3, 2008
The language you’re used to programming in very definitely shapes the way you think about solving programming problems. For example, I’ve been programming in C and C successors for 25 years. A deep rut in my brain is the idea that a string is pointer to an array of characters. In other words, it’s a reference type. I always think of it as having two parts, the reference and the referred to data, which can be manipulated separately. The referred to data must also be memory managed, which is always at the back of my mind when manipulating strings.
This makes strings inherently harder to work with than, say, a simple integer value.
But not all languages are like this. For all their faults, BASIC, Javascript and many other languages handle strings in a seductively easy manner. They can be copied and passed about just like integer values. They behave not like reference types, but like value types. I wanted that for the D programming language, but how does one go from two part reference types to a value type? It’s not like one could stuff an arbitrary number of characters into a fixed size value.
The first requirement is fairly obvious. Strings need automatic memory management, done with either reference counting or garbage collection. That takes care of copying them about. But there’s another, more subtle requirement. When a value is copied:
int a; int b = 5; a = b; b = 6;
we intuitively expect the last assignment to b to not affect the value in a. Unless we actually do something with a, its value should not change out from under us. What’s needed are invariant strings. Invariant strings (also called immutable strings) are reference types where the reference can be rebound, but the string data itself can never change. Thus:
string a; string b = "hello"; a = b; b = "world";
and a still is "hello". This is done without any copying or changing of the actual strings, just the references are manipulated. Since references are just pointers, it’s as efficient as copying integer values around.
But, a C programmer would ask (and being an old C programmer I asked this a lot), most of my string uses require changing the underlying string data. How can I do this with invariant strings?
To my great surprise, I discovered that although most of my programs heavily manipulate strings, they rarely need to actually change the underlying string data. Most of the manipulations involved moving references around, slicing, and concatenating. This can all be done with invariant strings. The handful of remaining cases are isolated and easily handled by using a mutable character array, doing the manipulations, and then converting it into an invariant string. Invariantness coupled with automatic memory management means reference types can be treated as if they were value types.
And so, my thinking about strings has changed. I now program them just like they were value types. In D it’s every bit as easy to program with strings as it is in BASIC or Javascript. It’s quicker to write the code, the result is easier to understand, and there are a lot fewer bugs. It’s even just as fast. What’s not to like?