Menu
I just attended a Scala-lecture at a summer school. The lecturer got the following question:
- "Is there any way for the compiler to tell if a class is immutable?"
The lecturer responded
- "No, there isn't. It would be very nice if it could."
I was surprised. Isnt't it just to check if the class contains any var-members?
920
An object is mutable if it is not immutable. An object is immutable if it consists, recursively, of only immutable-typed sub-objects. Thus, a tuple of lists is mutable; you cannot replace the elements of the tuple, but you can modify them through the list interface, changing the overall data.
An object whose state cannot change after it has been constructed is called immutable (unchangable). The methods of an immutable object do not modify the state of the object. In Scala, all number types, strings, and tuples are immutable.
Instead of mutating the state, create new state with computed value and return it to the user. In the same way, check for funds and create new state and return it to the user. In functional programming it is very common to create new state instead of trying to mutate the old state.
By contrast, Scala has two types of variables: val creates an immutable variable (like final in Java) var creates a mutable variable.
What is immutable?
Checking to see if the object only contains val fields is an overapproximation of immutability - the object may very well contain vars, but never assign different values in them. Or the segments of the program assigning values to vars may be unreachable.
According to the terminology of Chris Okasaki, there are immutable data structures and functional data structures.
An immutable data structure (or a class) is a data structure which, once constructed in memory, never changes its components and values - an example of this is a Scala tuple.
However, if you define the immutability of an object as the immutability of itself and all the objects reachable through references from the object, then a tuple may not be immutable - it depends on what you later instantiate it with. Sometimes there is not enough information about the program available at compile time to decide if a given data structure is immutable in the sense of containing only vals. And the information is missing due to polymorphism, whether parametric, subtyping or ad-hoc (type classes).
This is the first problem with deciding immutability - lack of static information.
A functional data structure is a data structure on which you can do operations whose outputs depend solely on the inputs for a given state. An example of such a data structure is a search tree which caches the last item looked up by storing it in a mutable field. Even though every lookup will write the last item searched into the mutable field, so that if the item is looked up again the search doesn't have to be repeated, the outputs of the lookup operation for such a data structure always remain the same given that nobody inserts new items into it. Another example of a functional data structure are splay trees.
In a general imperative programming model, to check if an operation is pure, that is - do the outputs depend solely on inputs, is undecidable. Again, one could use a technique such as abstract interpretation to provide a conservative answer, but this is not an exact answer to the question of purity.
This is the second problem with deciding if something having vars is immutable or functional (observably immutable) - undecidability.
132
I think the problem is that you need to ensure that all your vals don’t have any var members either. And this you cannot. Consider
class Base
case class Immutable extends Base { val immutable: Int = 0 }
case class Mutable extends Base { var mutable: Int = _ }
case class Immutable_?(b: Base)
Even though Immutable_?(Immutable) is indeed immutable, Immutable_?(Mutable) is not.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
