Mutability, aliasing, and the caches you didn't know you had
Many engineers have developed an intuition that mutable state is dangerous and can make programs harder to maintain. Still, it's worth digging into the specifics of why mutability is dangerous so we can think about solutions and trade-offs for each concern.
Now, mutability's dangerous (and useful) for lots of reasons, but today, let's talk about aliasing!
In C programming, that's the concern that one pointer can refer to the same location as another pointer. This possibility frustrates common compiler optimizations.
Logic programming introduced me to the idea that aliasing occurs at a higher level of abstraction, too: programs become harder to reason about whenever the same information is stored in multiple location—even when one variable is storing some derived computation of that information. The problem becomes much worse when that shared information is mutable.
To explore this, consider a typical problem in UI programming:
The timer whose ticks animate the interface should be enabled iff an animating UI element is visible.
Let's say that a UI element is animating iff it has any animations in its animation list. And an element is visible iff its alpha is non-zero. But UI frameworks typically have hierarchies of elements (where the root is a window or screen), so we have to say that an element is visible iff its alpha is non-zero and it's the child of a visible ancestor.
This is tough to achieve. Considering only the animations, we can't simply toggle the timer off when the last animation is removed from an element: what if some other element still has an animation running? The visibility constraint makes the situation even more complex: what if the element's parent's parent is hidden? What if an animating element's parent is moved from a hidden parent to a visible parent?
This problem is difficult to solve because the "timer enabled" bit aliases the information stored in the hierarchy of UI elements, their alpha values, and their animation lists. Any operation which could modify that information implicitly modifies the derivative "timer enabled" bit. But it's too expensive to iterate over every UI element whenever anything changes! You have to be sure to consider only the relevant branches, and you probably want to coalesce this reevaluation to avoid duplicated traversals.
Let me recast this problem a bit in more familiar terms: this is a caching problem! You need to make sure that you invalidate the bits involved in this computation at least as often as necessary, but that you invalidate only as many bits as are necessary. And just like any cache, you want to be somewhat lazy about performing the computations in question.
I'd like to propose that these kinds of implicit caching problems occur all the time, almost whenever you pass mutable data around a typically stateful imperative system. Consider: "The Register button should be enabled when the user enters an email address and a pair of matching passwords." or "The text field displays a formatted string produced by [insert date math] on the submission date."
Typical bugs that result from this problem domain include:
- not reevaluating the mutable data often enough (the register button stays disabled when you paste content into the password field because that's a different code path…)
- reevaluating the mutable data too often (we changed the submission date a hundred times since the last frame, recomputing the formatted date string each time at prohibitive expense, even though the resulting strings were never displayed…)
- degenerative feedback between the cache and the input data (someone might forget that a date<->string formatter/parser is never bijective…)
These issues are old hat in logic programming. But mutability and effect work very differently in those systems, and as far as I'm aware, the crucial question remains of how to interface these logic systems with existing functional and imperative frameworks. I'm hopeful that Joe Osborn's research will help.
Reactive programming seeks to solve this aliasing problem another way. It models this problem with graphs of signals: the dependencies for each computation are made explicit, and observers are notified whenever those dependencies are invalidated. From there, you still need to decide how and when to regenerate the resulting value, and how to conveniently (and dynamically) determine these dependencies in the first place. As with logic programming, interplay with the "host" framework remains a significant problem.
As I consider my own engineering problems in the light of these ideas, I've benefited enormously from the following simple step: for all the variables I declare, I mentally segregate them into ground truth data and data which is derived from ground truth. When I keep that idea in my head, I automatically maintain a more coherent picture of where truth flows from and to, and I handle that flow more carefully.
I hope that being exposed to the issue of aliasing in more specific and systematized terms will help you in your next battle with mutable state! 