Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Invariant Strings

March 11, 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?

Note: Many thanks to Andrei Alexandrescu who educated me on the utility of invariant strings and how invariant references can be treated like values.

 

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video