Immutability in C# Part One: Kinds of Immutability

Immutability in C# Part One: Kinds of Immutability

Rate This
  • Comments 54

I said in an earlier post that I believe that immutable objects are the way of the future in C#. I stand by that statement while at the same time noting that it is at this point sufficiently vague as to be practically meaningless! “Immutable” means different things to different people; different kinds of immutability have different pros and cons. I’d like to spend some time over the next few weeks talking about possible directions that C# could go to improve the developer experience when writing programs that use immutable objects, as well as giving some practical examples of the sort of immutable object programming you can do today.

(Again, I want to emphasize that in these sorts of “future feature” posts we are all playfully hypothesizing and brainstorming about ideas for entirely hypothetical future versions of C#. We have not yet shipped C# 3.0 and have not announced that there will ever be any future version of the language. Nothing here should be construed as any kind of promise or announcement; we’re just geeks talking about programming languages, ‘cause that’s what we do.)

So, disclaimers out of the way, what kinds of immutability are there? Lots. Here’s just a few. Note that these categories are not necessarily mutually exclusive!

Realio-trulio immutability:

There’s nothing you can do to the number one that changes it. You cannot paint it purple (‡), make it even or get it angry. It’s the number one, it is eternal, implacable and unchanging. Attempting to do something to it – say, adding three to it – doesn’t change the number one at all. Rather, it produces an entirely different and also immutable number. If you cast it to a double, you don’t change the integer one; rather, you get a brand new double.

Strings, numbers and the null value are all truly immutable.

C# allows you to declare truly immutable named fields with the const keyword. The compiler ensures that the only things that are allowed to go into const fields are truly immutable things – numbers, strings, null. (See the section of the standard on “constant expressions” for details.)

Write-once immutability:

Fields marked as const have to be compile-time constants, which is a bit of a pain if what you want to do is have a field which never changes but nevertheless cannot be computed until runtime. For example, in a later post I’m going to define an immutable stack class which has this code:

    public sealed class Stack<T> : IStack<T>
    {
        private sealed class EmptyStack : IStack<T>
        { /* ... */ }
        private static readonly EmptyStack empty = new EmptyStack();
        public static IStack<T> Empty { get { return empty; } }

I will want to create a singleton empty stack. Clearly it is not a compile-time constant, so I cannot make the field const. But I want to say “once this thing is initialized it is never going to change again.” That’s what the readonly modifier ensures. Basically it’s a “write only once” field. Not exactly immutable, since obviously it changes exactly once, from null to having a value. But pretty darn immutable.

Popsicle immutability:

...is what I whimsically call a slight weakening of write-once immutability. One could imagine an object or a field which remained mutable for a little while during its initialization, and then got “frozen” forever. This kind of immutability is particularly useful for immutable objects which circularly reference each other, or immutable objects which have been serialized to disk and upon deserialization need to be “fluid” until the entire deserialization process is done, at which point all the objects may be frozen.

There is at present no really universal convention for how to declare a freezable object, and there certainly is no support in the compiler for this kind of immutability.

Shallow vs deep immutability:

Consider a write-once field containing an array:

public class C {
    private static readonly int[] ints = new int[] { 1, 2, 3 };
    public static int[] Ints { get { return ints; } }

The value of the field cannot be changed; C.ints = null; would be illegal even from inside the class. This is a sort of “referential” immutability. But there is nothing immutable at all about the array itself! C.Ints[1] = 100; is still perfectly legal from outside the class.

The ints field is “shallowly” immutable. You can rely upon it being immutable to a certain extent, but once you reach a point where there is a reference to a mutable object, all bets are off.

Obviously the opposite of shallow immutability is “deep” immutability; in a deeply immutable object it is immutable all the way down.

If we had immutability in the type system, something like the far stronger kind of “const” in C/C++, then a hypothetical future compiler could verify that an object marked as deeply immutable had only deeply immutable fields.

Objects which are truly madly deeply immutable have a lot of great properties. They are 100% threadsafe, for example, since obviously there will be no conflicts between readers and (non-existant) writers. They are easier to reason about than objects which can change. But their strict requirements may be more than we need, or more than is practical to achieve.

Immutable facades:

Since the contents of an array (though, interestingly enough, not its size) may be changed arbitrarily, it’s a bad idea to expose data that you want to be logically read-only in a public array field. To make this a bit easier, the base class library lets you say

public class C {
    private static readonly intarray = new int[] { 1, 2, 3 };
    public static readonly ReadOnlyCollection<int> ints = new ReadOnlyCollection<int>(intarray);
    public static ReadOnlyCollection<int> Ints { get { return ints; } }

The read-only collection has the interface of a regular collection; it just throws an exception every time a method which would modify the collection is called. However, clearly the underlying collection is still mutable. Code inside C could mutate the array members.

Another down side of this kind of immutability is that the compiler is unable to detect attempts to modify the collection. Attempts to, say, add new members to the collection will fail at runtime, not at compile time.

This sort of immutability is a special case of...

Observational immutability:

Suppose you’ve got an object which has the property that every time you call a method on it, look at a field, etc, you get the same result. From the point of view of the caller such an object would be immutable. However you could imagine that behind the scenes the object was doing lazy initialization, memoizing results of function calls in a hash table, etc. The “guts” of the object might be entirely mutable.

What does it matter? Truly deeply immutable objects never change their internal state at all, and are therefore inherently threadsafe. An object which is mutable behind the scenes might still need to have complicated threading code in order to protect its internal mutable state from corruption should the object be called on two threads “at the same time”.

Summing up:

Holy goodness, this is complicated! And we have just barely touched upon the deeply complex relationship between immutability of objects and “purity” of methods, which opens up huge cans of worms.

So, smart people, what do you think? Are there forms of immutability which I did not touch upon here that you like to take advantage of in your programs? Are there any particular forms of immutability which you would like to see made easier to use in C#?

Next time: let’s get a little more practical. I already implemented an immutable stack in my A* series, but that was pretty special-purpose. We’ll take a look at how one might implement a general-purpose immutable stack today in C# 3.0. We'll then expand that to immutable queues, trees, etc. (And I might even discuss how one could take advantage of typesafe covariance when designing interfaces for immutable data structures, oh frabjous day!)

(‡) A dear old friend of mine from school who happens to be a grapheme-colour synaesthete tells me that of course you cannot paint the number one purple because it is already blue. Silly me!

  • Ok, quick fix and I'll stop.  (assume there are other errors too)

    // new context

    {  

       //new object, value resolves as (double) 5/4 (until methods changed)   <= not (double)1  

  • Ok. so one more...

    I mentioned I'd like it in enum style, but then went on and showed it as a declarative (which I'd still want).

    So here's a supplement:

    Alias MyMetric as increment ( (x) =>x+1 ) {

    One = { (int)1, (double)1, new funkyIntType((int)1), doublelikeOne },

    Two,  //  :== { ((int)1)+1, ((double)1)+1, (new funkyIntType((int)1))+1, (doublelikeOne)+1 },

    OutOfRange= (x)=>(x!=One && x!=Two)

    };

    { // new context

      // hmm, two is not valid anymore, at least for this context

      MyMetric-=Two;

    }

  • Just isn't my day.  Not nominative expression... Vocative expression.

  • Something bothering me about my Dec 18, 1:21PM post.

    Concerning: "OutOfRange= (x)=>(x!=One && x!=Two)"

    x!=Two when Two is undefined in the new context should be an error.

    Throw that out.  It'd be enough if all Aliases support the bool Exists(x) method.  

    Maybe this is turning into an immutable object container...

    I suppose that works too.  

    It's just that when I think immutable objects I immediately think named collections of properties.

    When I think collections of properties I include function pointers and lambda expressions.

    When I think lambda expressions I think algorithms.

    When I think algorithms I think limits, summations, and other equations used in calculus and logic proofs, relational algebra, et al.

    When I think algorithms I also think of abstract, not real until used, collections of objects. (Two does not exist, but One does, Two is the state of One after being added to One, If I reference the name Two, then I need to find a One and add it to a One right then and there.  That does not mean that Two is not an immutable object.)

    So naturally I think of algorithms as parts or wholes of immutable objects.

  • The/an extension of the "popsicle immutability" concept seems interesting to me. Imagine the "mutability status" of an object being subject to a parameter, called "temperature". As you increase the temperature of the object, it becomes more mutable; as the object's temperature decreases, it becomes less mutable. This would form the basis for creating "optimal objects" through a simulated annealing process.

    No, I can't offhand think of any glamourous applications of this concept; it just struck me as interesting.

  • I've been reading Eric Lippert's series on immutable collections (start here with part one ) over on

  • There have been some talks suggesting Microsoft to stop developing C# and simply move on to a...

  • It seems all of the add-on functions suggested for C# come back to a lack of theading support that isn't built in by the programmer.  This is has been true for any language.  It would seem a lot easier to just declare classes that are tread safe ThreadSafe.  

    For classes not marked the complier knows to knows it has to keep thread locked calls and synced copy (if another is created on a second thread).  Probably a big performance hit for existing code, but a lot less crashes.

  • There is a powerful and simple concept in programming that I think is really underused: Immutability

  • For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

  • I've been following this series but still don't know the *why* of wanting Immutability? What would a practicial business implementation be and why would it be beneficial?

  • Read part nine.

  • In SharpDevelop 1.1, the IClass interface had a property that was used in several places in the code

  • Microsoft haven&#39;t committed to anything in C# 4 yet. However, there have been hints about what they&#39;ve

  • I have just been doing some work building a very long (2-10kb) string

    character by charater. The book I referrred to said use stringbuilder

    not strings. The problem with strings is that they are immutable so

    each time I add a chatacter the string gets copied. It is slow, inefficient

    and not what most developers want or need.

    Microsoft gives us immutable strings but also has to give us something

    that performs.

    My view is that Microsoft people need to stop presenting us with

    theoretically good ideas unless they are- simple to use,

    make developing faster, easier to understand and perform well in

    the real world. Immutability- If I need it I want it. If I dont need it

    then I dont want it and would rather not be forced to use it.

Page 3 of 4 (54 items) 1234