Today’s post is a slightly random collection of stories and observations, all tied together under the common theme of “state” in programming. I feel that just in the last year or so, I’ve come to understand this better as an abstract concept in its own right. I feel that it’s helped me to connect a variety of different things from my experience – things I already knew, but hadn’t related to one another.
Anyhow, enough abstract twaddle.
State causes problems. It causes problems because it’s not visible in your source code. When you inspect a piece of code, you want to be able to see exactly what it does. The more your code has hidden or unclear dependencies on external state, the more you’re missing part of the picture, and the less reliably you can reason about what the code does. In the worst case, you have to perform some kind of global reasoning about the behaviour of your application – which can be more or less impossible to do in a watertight way.
At the same time, state is a fact of life. Your computer is stateful. The world is stateful. The game worlds we simulate are stateful. If your software doesn’t alter the state of something, it has no effect on the world, and might as well not exist. We give a CPU a list of instructions to go and interact with the computer’s state, and most languages don’t hide this from us at all. Why should they, when imperative programming is such a natural beginner’s metaphor? We naturally grasp the analogy of giving a person instructions to go and interact with the world (of course, the statefulness of the world is what makes giving precise instructions so brittle – even to a person who can apply some intelligence and initiative to deal with edge cases!)
Leaving const behind
One of the triggers that set me on the path of thinking about state was moving from C++ to C# for most everyday programming. I don’t think I was alone in thinking, “how can you write good software without const?” Check out how angry people get about this!!
At first I thought I was just upset at missing a language feature. It took some time to realise why missing this particular feature was so upsetting, when others (multiple inheritance, most features of templates, deterministic destruction) weren’t. I now believe that it’s because dealing with state is completely unavoidable, and tricky to do well – and ‘const’ is one of the main tools for dealing with the problems of state in C++. In other words, it becomes a truly essential tool in the C++ programmer’s chest (whereas advanced features of templates, while powerful, are non-essential). Const member functions promise not to change the state of their object, and const references restrict you to call only these functions. Careful use of const allows you to put a great deal of automatic checking around how you deal with state, letting the compiler do the grunt work. I now think that my level of upset was simply an indication of how much problems of state mattered to me.
While I still think ‘const’ is a great tool, C++ programmers never seem to talk much about entirely immutable data structures. I must have read more or less all the classic books on C++, and I can’t think of any references to the topic. I guess it’s partly because you have const, and partly because immutable data structures naturally work better with garbage collection. It was only when moving to C#, wondering how to cope without const, that I discovered and understood immutability. I guess it’s one thing I missed out on by doing maths instead of CS at university, although I wonder how many CS students really grasp the significance of immutability in a functional programming course. I think it’s one of those things you learn so much better when you’ve suffered first-hand from the problems it solves.
Immutable objects give you all the benefits of const correctness: you can hand them out to people and be sure they won’t change them. But they’re even better: when you receive a const reference in C++, sure, you can’t change it, but someone else could still pull the rug from under your feet. So they vastly simplify the reasoning involved when you look at a piece of source code. They even simplify reasoning about how local variables work within a function.
One of the more startling illustrations I’ve seen of how immutability can simplify your code is the red-black tree. When you write a stateful RB-tree, the tree balancing routine is rather fiddly. Here’s one part of the insertion routine for a red-black tree, from CLR:
RB-INSERT(T, x) 1 TREE-INSERT(T, x) 2 color[x] ← RED 3 while x != root[T] and color[p[x]] = RED 4 do if p[x] = left[p[p[x]]] 5 then y ← right[p[p[x]]] 6 if color[y] = RED 7 then color[p[x]] ← BLACK 8 color[y] ← BLACK 9 color[p[p[x]]] ← RED 10 x ← p[p[x]] 11 else if x = right[p[x]] 12 then x ← p[x] 13 LEFT-ROTATE(T, x) 14 color[p[x]] ← BLACK 15 color[p[p[x]]] ← RED 16 RIGHT-ROTATE(T, p[x]) 17 else (same as then clause with 'right' and 'left' exchanged) 18 color[root[T]] ← BLACK
This is actually only about a third of the total code: the “else” clause on line 17 doubles this function, and then there are the two rotation methods that aren’t listed here. If they hadn’t used a sentinel node, it would be even worse.
In contrast, here’s the complete insertion code for an immutable red-black tree in ML:
fun balance( (B, T(R, T(R, a, x, b), y, c), z, d) | (B, T(R, a, x, T(R, b, y, c)), z, d) | (B, a, x, T(R, T(R, b, y, c), z, d)) | (B, a, x, T(R, b, y, T(R, c, z, d))))= T(R, T(B,a,x,b), y, T(B,c,z,d)) | balance body = T body fun insert(x, s) = let fun ins E = T(R, E, x, E) | ins (s as T(colour, a, y, b)) = if Element.lt(x, y) then balance(colour, ins a, y, b) else if Element.lt(y, x) then balance(colour, a, y, ins b) else s val T(_, a, y, b) = ins s in T(B, a, y, b) end end
If you don’t know ML, it might look a bit alien, but you can see that it’s incredibly short, and highly symmetric: even without understanding it, there’s an elegance to it (and if you do know ML, you can see more or less at a glance that it’s correct). Now part of its elegance (particularly its extreme compactness) is down to ML’s awesome pattern matching. But the simplicity of verifying its correctness is substantially down to the lack of mutability, which eliminates a whole class of bugs from consideration. If we’re being completely honest, of course I’ve chosen an example that happens to work well in immutable form. Some data structures just don’t work at all, or don’t work well, in this form. But I still find this eye-opening🙂
If you enjoyed that, this book is fascinating.
Being a chump
What’s wrong with this pseudocode? It’s something I’m sorry to say I actually wrote not so long ago:
This was within an event handler on a calendar widget, updating the current date used by the rest of the page, based on the newly selected date in the calendar.
Here’s a gratuitous picture so that you can think about it for a second.
The answer, of course, is that those “Set” methods do more work than a straightforward setter, in order to prevent you from creating invalid dates. Suppose the current date is initially 31st October. Now suppose the user clicks on the day after, 1st November. First we set the month to November: uh-oh, there’s no such thing as 31st November, so the date object helpfully wraps around to become 1st December. Now we set the day to 1, and we’re left with 1st December – a whole month out.
How about this instead:
363 currentDate = new Date(newYear, newMonth, newDay);
On top of being correct, that’s clearer and more succinct. I actually laughed out loud when I found that bug, and then had to explain it to Andrew next to me, whose immediate response was “Ha! That’ll teach you a lesson for using mutable state!” Although it’s not the best code sample, I love the fact that Andrew made the words “immutable” and “state” part of standard vocabulary for our technical discussions, to the point where we could laugh about them.
Why beginner graphics programming frustrates me
Once these concepts around state clicked for me, other things started to make sense: most noticeably, why I’ve never enjoyed using DirectX that much. I’m one of those programmers that’s never really gotten into graphics programming, but tends to dabble with a few of the samples when a new version of DX comes out. The classic frustration is that you have a sample which appears to render three things, let’s say sky, objects, and text overlay – and you have another sample that renders some lovely particle effects – but when you try to mix them by pasting snippets in, stuff goes wrong. Everything’s subtly dependent on what came before, and needs to be exactly in the order given. You insert some new particle effects, and the text display goes bonkers. You delete the sky rendering, and objects disappear. And so on. It’s not that bad, but still … annoying.
It partly explains why the source code for student graphics demos is usually horrible: some poor kid has copied and pasted, randomly changed things and moved stuff up and down until it seems to work, and then it becomes magic voodoo code that they daren’t touch.
It’s a classic leaky abstraction. Graphics is one of those interfaces to the outside world, so it’s pretty stateful to start with. The graphics hardware itself has a whole load of state. DirectX (and OpenGL) is just a monstrous state machine wrapping it. While all I/O has this problem, the graphics API is just so much bigger and richer than most of the other I/O APIs, that the problems seem much worse.
Most games create further abstractions on top that take state seriously (primarily to minimise state changes for performance), and often simplify these problems. And I’m sure it’s just the way the graphics hardware abstraction layer needs to be, so it’d be silly to complain. It’s more just that I now understand why it can be frustrating.
Multi-threading is another area where state causes headaches. Essentially, the only reason multi-threading is hard is that sharing state is hard. Now that our machines will only go faster by adding more cores, it seems we’re being forced to embrace multi-threading where we’ve maybe shied away from it before. In turn, we’re being forced to understand the problems state causes in ways we haven’t before. I think this is one of the reasons for a recent rise in interest in immutable data structures and functional programming.
What about globals?
Global state is the worst kind, because global state is the hardest to reason about. If a piece of code depends on global state, then by definition, you depend on something that could be changed by any other part of the software. You have to understand and reason about your entire codebase, in order to understand one little bit of code. This is not good.
The solution is to minimise those dependencies, and advertise the unavoidable ones as constructor arguments and function parameters. That tightens the scope of your reasoning, and helps your caller: they now have some idea what factors might influence your code’s behaviour. But it’s not always simple …
I think I’ll leave that for next time as a topic in its own right🙂