Immutability Part 2

wherein we make a compiler do the work

Russ Bishop

March 23, 2014

The very first question any programmer has when they hear about immutable data structures is "how the hell can that possibly work when I can't change my data?"

The answer is rather simple, at least in an object-oriented language like C#. Instead of setting properties and fields, you call a method that returns a new object containing the original values plus your changes.

var original = FancyTown.Create(id: 0, isFancy: true);
var mutated = original.With(id: 5, description: "fancy");

Because the mutated object is a copy, we didn't introduce any threading issues. As far as the rest of the universe is concerned, nothing happened. As a result, and this is a key concept of immutability:

We decide if, when, and where to publish our changes, and can do so in an atomic way. No one can observe a half-mutated object. No object needs to allow the setting of invalid combinations of values. Both our mutation and the publishing of that mutation are atomic operations.

By constructing an appropriate object graph and making nested changes, it becomes trivial to publish any arbitrarily large set of changes to the rest of the universe as a single Interlocked.CompareExchange operation, without requiring the rest of the universe stop and wait on a lock while we work.

Builders

There's an optimization we might want to implement, and that's to have mutable builder versions of our classes. For a really simple object it might not matter, but when you have a fairly complex object hierarchy, builders buy you several things:

With a builder, you don't have to make your mutations inside-out, from the inner-most object to be mutated all the way out.
It is easier to avoid multiple mutations in a row. Yes, the garbage collector helps a lot here, but we don't want to be completely inefficient if we can help it.
The builder can defer converting the objects deeper in the hierarchy to builders until they are needed, allowing us to cleanly skip most of the work.

With Methods

Sometimes we don't need to do a bunch of mutations, we just want to change one property. Sure, we can use the With() syntax and named parameters, but there's a cleaner bit of syntax sugar:

var mutated = obj.WithDescription("new description");

We can also provide handy methods for mutating collections contained within an object in a similar way:

var mutated = obj.AddItems(item1, item2).RemoveItem(item3);

The Problem

The big problem is that creating all this by hand sucks. Hard. If we want to include optimizations, like making properties use a readonly backing field so they are trivially inlined, it only increases the workload. Want to have some defaults so a new object has empty collections instead of null? Want all your immutables to have builders? Even more work.

Fortunately, there is a better way: Immutable Object Graph.

Many people don't realize that the same T4 text templating engine that drives internal Visual Studio features and ASP.Net Web Forms is also available to generate code for you. IOG makes use of this to take a really simple class definition with simple fields and produces a full immutable class, complete with a builder, read-only backing fields, mutation methods, etc.

class Fruit {
    string color;
    int skinThickness;
}

Generates this output:

public partial class Fruit {
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private static readonly Fruit DefaultInstance = GetDefaultTemplate();

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private readonly System.String color;

    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private readonly System.Int32 skinThickness;

    /// <summary>Initializes a new instance of the Fruit class.</summary>
    private Fruit()
    {
    }

    /// <summary>Initializes a new instance of the Fruit class.</summary>
    private Fruit(System.String color, System.Int32 skinThickness)
    {
        this.color = color;
        this.skinThickness = skinThickness;
        this.Validate();
    }

    public static Fruit Create(
        ImmutableObjectGraph.Optional<System.String> color = default(ImmutableObjectGraph.Optional<System.String>), 
        ImmutableObjectGraph.Optional<System.Int32> skinThickness = default(ImmutableObjectGraph.Optional<System.Int32>)) {
        return DefaultInstance.With(
            color.IsDefined ? color : ImmutableObjectGraph.Optional.For(DefaultInstance.color), 
            skinThickness.IsDefined ? skinThickness : ImmutableObjectGraph.Optional.For(DefaultInstance.skinThickness));
    }

    public System.String Color {
        get { return this.color; }
    }

    public Fruit WithColor(System.String value) {
        if (value == this.Color) {
            return this;
        }

        return new Fruit(value, this.SkinThickness);
    }

    public System.Int32 SkinThickness {
        get { return this.skinThickness; }
    }

    public Fruit WithSkinThickness(System.Int32 value) {
        if (value == this.SkinThickness) {
            return this;
        }

        return new Fruit(this.Color, value);
    }

    /// <summary>Returns a new instance of this object with any number of properties changed.</summary>
    public Fruit With(
        ImmutableObjectGraph.Optional<System.String> color = default(ImmutableObjectGraph.Optional<System.String>), 
        ImmutableObjectGraph.Optional<System.Int32> skinThickness = default(ImmutableObjectGraph.Optional<System.Int32>)) {
        if (
            (color.IsDefined && color.Value != this.Color) || 
            (skinThickness.IsDefined && skinThickness.Value != this.SkinThickness)) {
            return new Fruit(
                color.IsDefined ? color.Value : this.Color,
                skinThickness.IsDefined ? skinThickness.Value : this.SkinThickness);
        } else {
            return this;
        }
    }

    public Builder ToBuilder() {
        return new Builder(this);
    }

    /// <summary>Normalizes and/or validates all properties on this object.</summary>
    /// <exception type="ArgumentException">Thrown if any properties have disallowed values.</exception>
    partial void Validate();

    /// <summary>Provides defaults for fields.</summary>
    /// <param name="template">The struct to set default values on.</param>
    static partial void CreateDefaultTemplate(ref Template template);

    /// <summary>Returns a newly instantiated Fruit whose fields are initialized with default values.</summary>
    private static Fruit GetDefaultTemplate() {
        var template = new Template();
        CreateDefaultTemplate(ref template);
        return new Fruit(
            template.Color, 
            template.SkinThickness);
    }

    public partial class Builder {
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        private Fruit immutable;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        private System.String color;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        private System.Int32 skinThickness;

        internal Builder(Fruit immutable) {
            this.immutable = immutable;

            this.color = immutable.Color;
            this.skinThickness = immutable.SkinThickness;
        }

        public System.String Color {
            get {
                return this.color;
            }

            set {
                this.color = value;
            }
        }

        public System.Int32 SkinThickness {
            get {
                return this.skinThickness;
            }

            set {
                this.skinThickness = value;
            }
        }

        public Fruit ToImmutable() {
            return this.immutable = this.immutable.With(
                ImmutableObjectGraph.Optional.For(this.color),
                ImmutableObjectGraph.Optional.For(this.skinThickness));
        }
    }

    /// <summary>A struct with all the same fields as the containing type for use in describing default values for new instances of the class.</summary>
    private struct Template {
        internal System.String Color { get; set; }

        internal System.Int32 SkinThickness { get; set; }
    }
}

Now that's developing software.

Visual Studio will automatically update the generated file anytime the template is updated, so keeping things in sync is really easy. A couple of things to note:

Name the include files to .t4 so Visual Studio doesn't attempt to process them.
You can't reference types in the same assembly, so you may need to move some classes to a common or utilities assembly. This is because the template engine is actually turning the template into a C# class and executing it behind the scenes. The literal text becomes Write() calls, while the code inside the brackets gets added to your class definition and executed.
Build whatever object graph you like, including using abstract base classes.
If you update the template include files, there's a handy menu option Build, Transform all T4 Templates that will re-process all the templates in your project
The generated classes are all partial classes, so put any custom logic in a separate file. The builder is a partial private class too; Visual Studio won't show you intellisense for it, but you can extend the builder the same way you extend the class itself.

I have my own modified version of the template that can carry attributes forward from the prototype definition into the generated classes. It also adds convenience methods for working with Dictionaries. I don't know if I'll be able to open-source it or not, but I'm working on that.

Conclusion

Go forth and template. Don't write immutable classes by hand like a fool; let the compiler do the work.

Part 1: Russell's Rules For Highly Concurrent Software
Part 3: ContextLocal
Part 4: On Rediscovering the Classic Coordinated Transaction Problem
Part 5: Interlocked.CompareExchange