Immutability, Purity, and Referential Transparency

Article
03/01/2007

How often do you write code that just works? It seems to happen so rarely that I find myself suspicious if code does just work. When was the last time that you wrote a non-trivial program that had no compile errors on the first try and then ran fine as well? If it happened recently then congratulations. If it hasn't then join the club. Admittedly, most programmers don't just write a whole program and then submit it to a compiler and a test harness to see if it works. Typically it is built incrementally: a function here, a class there, testing all the time. Code-Compile-Test...rinse and repeat.

I recently read a post where the author describes why Haskell programs just seem to work. It got me thinking about my own experience in Haskell. One of the most interesting things about Haskell is that many programmers don't use a debugger (GHCi does have one). It seems that the impulse to break out the debugger to better understand code occurs far less than in other languages.

Can you imagine working in C# without a debugger? So why is it that many Haskell users seem to get along without a debugger?

A Tale of Two Sorts

Consider writing a function that sorts an IEnumerable<T> using the quicksort algorithm. Here is one possible implementation:

static IEnumerable<T> QuickSort<T>(this IEnumerable<T> sequence) where T : IComparable<T>
{
var array = sequence.ToArray();
QuickSort(array, 0, array.Length - 1);
return array;
}

static void QuickSort<T>(this T[] array, int start, int end) where T : IComparable<T>
{
if (end - start < 1)
return;
var pivot = array[start];
var j = start;
for (var i = start + 1; i <= end; ++i)
{
if (array[i].CompareTo(pivot) < 0)
{
++j;
var temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
array[start] = array[j];
array[j] = pivot;
QuickSort(array, start, j - 1);
QuickSort(array, j + 1, end);
}

Now imagine that ++j was in the wrong place (at the end of the block). The output of sorting

4, 3, 6, 9, 1, 0, 2, 7, 5, 8

would be

4, 4, 4, 4, 4, 9, 6, 7, 7, 8

Clearly this isn't right. So after a quick scan of the code, most programmers would attach a debugger to see what is going on.

The programmer might then step through the code until some state transition ends in a corrupt state. Hopefully the programmer understands the intent of the code so that a fix can be issued to bring the implementation in line with the intent.

Contrast the previous definition of quicksort with the following definition:

static IEnumerable<T> QuickSort<T>(this IEnumerable<T> sequence) where T : IComparable<T>
{
if (!sequence.Any())
return sequence;
var pivot = sequence.First();
var remaining = sequence.Skip(1);
return ((from x in remaining where x.CompareTo(pivot) < 0 select x).QuickSort())
.Concat(pivot)
.Concat((from x in remaining where x.CompareTo(pivot) >= 0 select x).QuickSort());
}

What do you notice that is different besides the number of lines of code?

The first definition creates an array and then does in an place quicksort on the array, destructively updating the contents. It creates several temporary values (i, j) needed to store intermediate results. If a programmer hasn't written the algorithm recently then chances are that the code will contain at least an one off by one error or some other similar error. I've seen too many people do poorly on whiteboards on similar problems (where incidentally there is no debugger, syntax highlighting, or intellisense) to believe that most people would just get it right the first time.

The second definition does not modify any data. Sure it makes assignments but each of these assignments are to a newly introduced variable. These variables are really just aliases for the expressions that are assigned to them because the expressions are side-effect free. Furthermore, the second definition is essentially just a brief description of what the quicksort is rather than a step by step description of how it is accomplished.

At this point, some people will probably be thinking, "But isn't the first approach so much faster than the second approach?"

Maybe, maybe not. Perhaps it doesn't even matter.

I think it is important to use the following principle: Make it correct, make it clear, make it concise, make it fast. In that order.

If I find that the code in question is not performant enough given the user scenarios that we need to support or if the code is overly complex for the sake of eliminating side-effects then I consider adding state. But note that if I wanted to introduce state to our quicksort, I could do it in two different ways: contained within the quicksort function or exposed to the caller of quicksort. This is somewhat analogous to calling either the first function or the second function in the first definition of quicksort. If the state is exposed then quicksort could do an in-place sort on the collection passed to the quicksort function. Alternatively, quicksort could simply return a new collection that is sorted and not update the original collection. This leads to the second principle:

Write side-effect free code. If side-effects are required then confine them to the smallest scope possible.

Most programmers have been following this to some extent for years. We all know that generally it is not a good idea to use global variables. This is basically the extreme of exposing side-effects (the global scope). Unfortunately, many of the programmers who don't use global variables don't realize that the same principles apply to fields, properties, parameters, and variables on a more limited scale: don't mutate them unless you have a good reason.

A Little Story about State

Some time ago, I wrote a post about a way to save the state of an IEnumerator<T>. What I didn't tell is the story behind the post.

I was writing a managed lexer and parser generator. The system is pretty neat and includes things like GLR parsing, automatic inference of the AST types, automatic error recovery, and whole slew of other features. The parser takes an IEnumerable<IToken> in order to decouple the lexer from the parser. However, for many of the features of the parser, it needs a way to save the state the of the underlying token stream and possibly restore it at a later time after more of the stream has been consumed.

Originally, I wrote a MarkableEnumerator<T> which wrapped an IEnumerator<T> and consumed the input. Clients could request a mark which they could then restore at a later point. If they did this then the MarkableEnumerator<T> would continue at the restored point when MoveNext was called again. This little piece of software (about 100 lines of code) caused Cyrus and me lots of trouble. It was super complicated because it was heavily optimized to keep its internal storage as small as possible while preserving requested past state (and possibly restoring it). It used a cyclical buffer and a number of opaque handles. One of the worst problems is that it was a somewhat leaky abstraction since the complexity leaked into the code consuming it.

When the code was first introduced it was reasonably contained but over time its inherent complexity began to pervade the whole parser. Eventually, it was hard to make improvements to the parser without breaking the invariants of the MarkableEnumerator. It was an absolute horror. I remember one night well past midnight, Cyrus and I were talking about how much we hated the thing, but we needed it to provide good performance.

Then it occurred to us that we could replace the whole mess of opaque handles, circular buffers, mark and release code, and MarkableEnumerators within MarkableEnumerators with just a linked list that wrapped the enumerator. If someone wanted to save the state of the enumerator and resume it then all they need to do is keep a reference to the desired node. To all of the clients, it looked just like an immutable linked list. That is it. So much simpler and guess what? It was almost as fast. But even more importantly, because of its simplicity we were able to make even more important code faster. Our development time for new features rocketed again.

There are several lessons from this story, but one of them is perhaps the most important considering our current discussion. Reducing the number and scope of side-effects simplifies the code.

Immutable Binary Trees

Mutation often seems to just cause problems.

Suppose that we want to create a BinaryTree class. One straightforward implementation is

class BinaryTree<T>
{
public T Value { get; set; } // yes, we have autoimplemented
public BinaryTree<T> Parent { get; set; } // properties in case you haven't
public BinaryTree<T> Left { get; set; } // heard
public BinaryTree<T> Right { get; set; }
}

I don't like it very much. Those sets give me an uneasy feeling. Of course it depends on how the objects are used, but suppose that we intend to use the binary tree in a multithreaded environment. If someone changes any of the members of a node there is a chance that some other thread already has a reference to a node in the tree and will then have a tree in an inconsistent state. Yes, we could use a lock to fix the problem but I tend to like a different approach to this problem.

class BinaryTree<T>
{
T value;
BinaryTree<T> left;
BinaryTree<T> right;

public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right)
{
this.value = value;
this.left = left;
this.right = right;
}

public T Value { get { return value; } }
public BinaryTree<T> Left { get { return left; } }
public BinaryTree<T> Right { get { return right; } }
}

This is essentially the same as the first BinaryTree except that it is immutable (no sets and no methods causing mutation). This requires that we have a constructor that takes in the appropriate values. Also, you may have noticed that there is no Parent property. The reason is that if the node is immutable then it is hard to know what the parent is at the time of creation. With an immutable tree, you generally can either create parents before children or children before parents. I prefer the later (despite the biological conundrum posed by this). Note that this doesn't mean that we can't know what the parent of a given node is. Indeed we can, but we need to introduce a new concept before addressing this.

Nodes can really be parented by n nodes. Since any node can be constructed with a given node as either the left or the right child. But given a tree (a root), we can enforce (assuming that we don't want DAGs) that a node has at most one parent. We will call this a BinaryTreeVersion.

class BinaryTreeVersion<T>
{
BinaryTree<T> tree;
Dictionary<BinaryTree<T>, BinaryTree<T>> parentMap;

public BinaryTreeVersion(BinaryTree<T> tree)
{
this.tree = tree;
}

public BinaryTree<T> Tree { get { return tree; } }
public BinaryTree<T> GetParentOf(BinaryTree<T> node)
{
if (parentMap == null)
{
parentMap = new Dictionary<BinaryTree<T>, BinaryTree<T>>();
FillParentMap(tree, null);
}
return parentMap[node];
}

void FillParentMap(BinaryTree<T> tree, BinaryTree<T> parent)
{
if (tree == null)
return;
parentMap.Add(tree, parent);
FillParentMap(tree.Left, tree);
FillParentMap(tree.Right, tree);
}
}

The parent operation is exposed on the BinaryTreeVersion. The parent of a given node is stored in the parentMap which is filled with node-parent pairs. So now we have a tree that is immutable and the ability to access a node's parent.

But we can take it one step further, we can create functions that will modify the tree. Note that we will not actually modify the tree but we will return a new BinaryTreeVersion. The ChangeNodeValues function takes two functions: a function that determines whether to modify the given node's value and a function to compute the node's new value (there are better ways to do this for specific modifications and yes I could have used a visitor).

class BinaryTreeVersion<T>
{

...

public BinaryTreeVersion<T> ChangeNodeValues(Func<BinaryTree<T>, bool> predicate, Func<BinaryTree<T>, T> newValue)
{
return new BinaryTreeVersion<T>(ChangeNodeValue(tree, predicate, newValue));
}

BinaryTree<T> ChangeNodeValue(BinaryTree<T> node, Func<BinaryTree<T>, bool> predicate, Func<BinaryTree<T>, T> newValue)
{
if (node == null)
return null;
var left = ChangeNodeValue(node.Left, predicate, newValue);
var right = ChangeNodeValue(node.Right, predicate, newValue);
var value = predicate(node) ? newValue(node) : node.Value;
if (value.Equals(node.Value) && left == node.Left && right == node.Right)
return node;
return new BinaryTree<T>(value, left, right);
}
}

The neat thing is that since we use immutable trees, we can share subtrees that are not changed. Even so, if another thread has a reference to the first BinaryTreeVersion or a node in the first tree then things will just work because we are mucking around with the data.

The Benefits of Purity

One of the most painful things in software development is integrating two or more things (objects, assemblies, functions, ...) together. Invariably something will go wrong and a programmer that worked on one or the other things in question will protest, "It worked on my machine!" Yes, indeed it probably did and it probably even works by itself but when put together with other things it doesn't play so nice.

One way to increase the reliability of a unit is to eliminate the side-effects. This makes composing and integrating units together much easier and more robust. Since they are side-effect free, they always work the same no matter the environment. This is called referential transparency.

Conversely, things that are side-effect free are also easier to divide. For a good example of this take a look at PLinq which farms out querying work to the available threads. It divides up the work and then integrates the results: map-reduce.

But that is a discussion for another day...

Comments

Anonymous
February 28, 2007
Another great post Wes, where do you find time? I'm really hoping some of the Spec# ideas make it into C# 4, at which point I think the language will essentially be complete (caveat: if STM ever becomes real then maybe we'll get a 'atomic' keyword, or language bindings for message based method invocation). I can see a real need for the constraints and stuff that Spec # offers - esp. when you think about being able to use things like DLINQ with confidence in a compositional manner. That said I also wonder about the comment in Charlie's Orcas Feb/March CTP video about is "C# begining too complicated?" I don't think so yet - but I'd hate to see it decay to the complexity of C++. I think one of the goals for C# is that the majority should be able to grok the entire language.
Anonymous
March 01, 2007
I just read another brilliant blog post of Wes Dyer that emphasizes the importance of simplicity of code. This is one of the paradigms of agile software development and I think this cannot be accentuated too much. It not only helps the author to keep
Anonymous
March 01, 2007
Not that this affects the point you were making in the QuickSort example, but do the implementations of Skip(int) and Concat(IEnumerable<T>) also work without changing state? It seems like at least Skip(int) would have to alter the state of the enumerable it is acting on, but does it instead create a new enumerable from the original one?
Anonymous
March 01, 2007
The comment has been removed
Anonymous
March 01, 2007
Welcome to the twenty-second Community Convergence, the March CTP issue. I'm Charlie Calvert, the C#
Anonymous
March 01, 2007
Welcome to the twenty-second Community Convergence, the March CTP issue. I'm Charlie Calvert, the
Anonymous
March 01, 2007
The comment has been removed
Anonymous
March 01, 2007
Well right now C# is going through it's 'data access evolution' period, and it's doing so in a manner which might well lead into its 'concurrency evolution' period. I'm aware that folks like Sutter are rightly cautious of over selling FP as a magic solution for concurrency. I think he's right about the over selling bit - but I also think the way FP tends to make you think about mutation vs. value and side effects and what not help hugely in expressing and partioning ones logic in a form that takes us a step closer towards Sutter's "sea of available concurrency". If we don't decompose and express with a eye on mutation vs. value then it's going to be very hard for any runtime to infer intent and distribute without us having to explicitly decorate code (in a OpenMP or .NET attribute based manner). So I feel that with LINQ plus some carefully chosen bits of Spec# could position C# 4 or C# 5 as a great platform on which to build software that runs atop of the 16 to 32 hardware threads per socket we can expect by that time. Personally I think once constraints and maybe some language bindings for concurrency are in place then its pretty much "job done" for C#. It would I feel be a huge mistake for it to descend into the murky syntactic depths that C++ has got itself into. The beauty of .NET is the degree to which you can "mix it up". It may well be I feel that C# 5 or 6 would best be realised as a different and complimentary language. Look at the way XAML compliments C#. Or the way you can mix up solutions using F# and C#. Better I feel to have a language which the majority can really grok and feel super comfortable with - that leads to better software in terms of being on time and defect free - which ultimately is better for Windows since its the software that runs on top of Windows that delivers the real value to the end user.
Anonymous
March 02, 2007
A very informative and insightful post as usual, Wes. I'm afraid I have to take exception with these statements about performance, though: >>> At this point, some people will probably be thinking, "But isn't the first approach so much faster than the second approach?" Maybe, maybe not. Perhaps it doesn't even matter. I think it is important to use the following principle: Make it correct, make it clear, make it concise, make it fast. In that order. <<< I agree with you that for many of the problems that we encounter, a developer is better off writing clear, concise code that just works. The re-worked QuickSort method is a great example of that principle. However, the QuickSort example belongs to a class of problems for which such a laissez-faire attitude towards performance is likely to be unacceptable to many people. This class of problems includes these very general sorts of methods where performance is important, you need an algorithm that scales well, and you are unlikely to modify the code much once it's written. If we were going to need the QuickSort method to operate on very large arrays, then you can bet that the difference between an O(n log n) algorithm and (for the sake of argument) an O(n^3) algorithm is going to be important. Furthermore, once it is written and works correctly, you can use QuickSort on just about anything that implements IEnumerable<T> and IComparable<T> without modification, so chances are that you aren't going to need to do much to the method once it is created. So, it would seem that this sort of problem is one for which our priorities are inverted: make it fast, make it clear, make it concise. Now, I'm sure you understand all of this and you were just trying to make a more general point. I happen to agree with that point for the vast majority of problems. Here's what really bothers me about the performance issue, though. How do we tell which is faster, the original implementation of QuickSort or the implementation using LINQ? You seem to be admitting that you don't know. My fear is that we either can't know or that it will be very difficult to determine. I might be willing to trade some performance for code clarity and simplicity, but to do so, I want to have some idea of what the performance is going to be. Heck, the LINQ implementation could be faster, but I'm not willing to roll the dice on this sort of problem, so I'd approach it in the traditional way. Is there a way to get a good approximation of the efficiency of a LINQ algorithm? Sure, you can always profile the application, but I think many of us would like a more generic and rigorous way to analyze their performance. Am I just overlooking something that should be really obvious?
Anonymous
March 02, 2007
The comment has been removed
Anonymous
March 02, 2007
jmlovero: Great comments. Just to be clear, I am pro performance. I was actually getting at two things: first, having clear and concise code lends itself to be in better shape to be improved for performance and second optimizing code is not straightforward. Some optimization choices while improving characteristics in some dimensions actually cause performance to degrade in others. We need to make sure that we understand which scenarios are important and then optimize for those. I understand that you are talking about asymptoptic performance. You are right that we don't want to just throw around O(n^3) algorithms, that would be irresponsible. What I am saying is that the particular code in question may not be important to the overall performance depending upon our performance budget and the customer scenarios that we support. You make a very good point that QuickSort is something that should just be written and stored away in a library and I agree with that. Hopefully there will be at least two implementations: one which modifies the collection in place and another which just returns a new collection. Thank you for having me clear that up. -- Performance is important.
Anonymous
March 02, 2007
I might be missing something but .Concat(pivot) fails because it isn't enumerable. To fix this I wrote this: public static IEnumerable<T> Enumerate<T>(this T t) { yield return t; } And modified the code to this: if (!sequence.Any()) return sequence; var pivot = sequence.First(); var remaining = sequence.Skip(1); return ((from x in remaining where x.CompareTo(pivot) < 0 select x).QuickSort()) .Concat(pivot.Enumerate()) .Concat((from x in remaining where x.CompareTo(pivot) >= 0 select x).QuickSort()); seems to work.
Anonymous
March 03, 2007
Alex: Good point. I had written my own extension method called Concat that looked like this: IEnumerable<T> Concat<T>(this IEnumerable<T> sequence1, params T[] sequence2) { foreach (var item in sequence1) yield return item; foreach (var item in sequence2) yield return item; }
Anonymous
March 04, 2007
i aree that Immutability brings clearity, i would like to c an example from the PLinq implementation where it uses several hardware threads for doing job, that will give some more arguments in my java-oriented consulting company :P i guess the complexity budget is higher than what u think,i even think that adding functional programming features has the opposite effect, because as long as you write side-effects free functions, and Intention revealing interfaces, u are free of complexity. But the overuse of mutability, in not encapsulating state , is the source of the complexity. I went through the implementation of the visitor of expressions, and i have two questions: 1: why in a lambda expression you are not visiting the parameter expressions in the VisitLambdaExpression 2: why u make the class as internal, it would be very helpfull if i could extend it, so that i can replace all the old parameters in my predicate's (LambdaExpression<Predicate>) implementation with the new one resulting from the "And" operator, i would only need to override the VisitParameterExpression to have it done.
Anonymous
March 04, 2007
Wes That makes sense, and is much cleaner than mine. I'm just learning all this stuff, and to that end your blog posts are invaluable. Keep up the good work Alex
Anonymous
March 04, 2007
Great blog post. Keep it coming, Wes. Please push for Spec# ideas to be integrated into C#. IIRC, you can mark methods as [Pure], you can mark reference types as non-null, you can guarantee pre- and post-conditions. Seems to me these things would help us write more correct software.
Anonymous
March 04, 2007
Totally agree. It's not just things like "[Pure]" but being able to constrain parameter values, not least "not null" that I think we have a real need for. Goodness knows how many developers hours get sunk into implementing #region Parameter Validation blocks at the start of every public and protected method. In that C9 video on Language Innovation (http://channel9.msdn.com/Showpost.aspx?postid=273697) with Anders and Herb et al rapping on the motivations behind and directions in language design they certainly seem to hint that some form of formal contraints notation might, possibly, be coming ;-)
Anonymous
March 04, 2007
I vote for Judah's suggeestion! i love spec#!
Anonymous
March 05, 2007
seems a lot like the haskell definition: qsort (x:xs) = qsort [y | y<-xs, y<=x] ++ (x: qsort [y | y<-xs, y>x]) qsort [] = [] What about Monads? Is this haskell feature feasible to implement in C# 3.0?
Anonymous
March 05, 2007
Or maybe a more generic way of putting this is: Can I add interface types to existing classes using extension methods? Like in Haskell I could define: instance Monad {a} where x>>=y = ... return x = ... I could make IList<T> a Monad by implementing: static IList<T> bind(this IList<T> a, Func<T,IList> f); and static IList<T> return<T>(T item); or something like that?
Anonymous
March 05, 2007
I will relay all of the feedback about Spec# features in the next rev of C#. Joost: It is very similar to the haskell definition. Well, I think what you want is something like type classes in haskell. I love them and we are working on some ideas to implement an interface with extension methods (post C# 3.0).
Anonymous
March 05, 2007
FYI I just did a post on this...
Anonymous
March 05, 2007
In my recent Syntactic Sugar presentation I was trying to get to the essence of good code, and come up
Anonymous
March 05, 2007
Sadek:

We don't visit the parameters because they are not part of the body of the lambda.
We wanted to expose it, but we were very short on resources so this feature was cut. We may expose it in a sample.

Anonymous
March 05, 2007
But you do visit arguments, so why to visit arguments and not paramters, anyway thats not a big deal as i can override the methods. I would really like to revisit all the everyday's patterns and think about them in an immutable implementation, maybe it will work for some, i like the new horizon a mixed language like c# offers.
Anonymous
March 05, 2007
The comment has been removed
Anonymous
March 06, 2007
Il sottotitolo di questo blog ora appare come Pensieri eretici nel mondo .NET . Ho deciso di rinominarlo
Anonymous
March 06, 2007
Wes, Would Microsoft consider hosting a FP community site? It seems clear that there's a real interest and hunger in the community for this stuff. The responses to your own posts show that the existing FP community has a considerable body of experience and insight to offer and are now coming out of the woodwork given the tentative steps C# 3 is making in this direction. What I'm suggesting is some central place where we can hang out, with links to your blog, HubFS, Lambda The Ultimate etc, Iron Python. The remit would be FP on .NET. Perhaps a sub-section of Channel 9, but I was really thinking of something like Coding For Fun in terms of having its own identity. Would Microsoft consider putting some resource behind this? Kind regards, tom
Anonymous
March 06, 2007
Tom: I agree :)
Anonymous
March 07, 2007
Joost: You can't do that today, but I'd love to add support for that. Tom: I forwarded your request on to the people who could organize that. Thanks for the suggestion.
Anonymous
March 07, 2007
I was told that it would be fairly difficult to organize such a site; however, I was also told that we'd be happy to host articles and provide links to FP related things on the C# site. You can contact Charlie Calvert if you have something. His blog is at: http://blogs.msdn.com/charlie.
Anonymous
April 11, 2007
I've spent the majority of my career as a Web developer, and I've only recently (with the discovery of

Share via

Immutability, Purity, and Referential Transparency

Comments

Additional resources