Safer mutation: change the value, change the name
Saturday 16 June 2012 12:33
Many advocates of functional programming suggest that the concept of state, the idea that a value can change and mutate over time, makes reasoning about your program much harder, leading to more bugs. Most languages allow some form of mutability, and can therefore implement both functional and imperative algorithms, even if the preference is strongly towards immutability. In a completely pure functional language, mutability is entirely removed. Since some concepts are arguably easier to understand and implement when using mutable state, this can mean certain problems are harder to solve in a purely functional language. But what if we allowed a limited form of mutability in such a way that we still preserve many of the nicer properties of functional programming, such as referential transparency?
To take a simple example: suppose we want to append an item to the end of a list. In an imperative language, we might write something like this:
list.append("first")so now list has an extra item, meaning that the original value
of list no longer exists. In a functional programming
language, we'd create a new value instead of mutating the original list:
val longerList = list.append("first")We can now use both list and longerList, since
list was not modified during the append. This means we never need
to reason about what state list is in – its value never changes.
The trade-off is that a functional append tends to be more expensive than an
imperative append. If we don't actually want to use list again, then this is
arguably a bad trade-off. What if we could allow the list to be mutated under
the covers, but still be able to present a programming model that appears to
preserve immutability? So, we write the same code:
val longerList = list.append("first")but list is now implemented as a mutable list. The compiler must
now ensure that list is never used after the append operation.
This means the actual implementation is effectively the same as when written
in an imperative style, but we ensure that whenever we change the value of an
object, we also change the name used to access it.
This approach does have some severe limitations. For instance, sharing mutable state between many objects is likely to be impossible. If we allowed mutable state to be shared, then mutating that state inside one object would require marking all objects that hold that state to be unusable. In general, having the compiler keep track of this is likely to be unfeasible.
Yet this sharing of mutable state is arguably the worst form of mutablility. It means that changing something in one part of your system could change something in another far away part of the system. This idea of changing the name whenever we change the value is most useful for mutability in the small, when we just want to implement a particular algorithm efficiently.
However, there still might cases where you'd quite reasonably want to share mutable state between, say, just two objects. The more interesting question is: is it possible to handle this case without requiring the user to write an excessive number of hints to the compiler?
Topics: Language design, Functional programming