Statically decide if a Scala class is immutable_问答_开发者

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开发者_StackOverflow社区 to check if the class contains any var-members?

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.

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.

If you save a mutable object in a val the object itself is still mutable. So you would have to check if each class you use in a val is immutable.

case class Mut(var mut:Int)

val m = Mut(1)
println(m.toString)
m.mut = 3
println(m.toString)

In addition to what others have said, take a look at effect systems and discussion about supporting one in Scala.

It is not quite as easy since you could have vals that are linked to other mutable classes or, even harder to detect, that calls methods in other classes or objects that are mutable.

Also, you could very well have a immutable class that in fact has vars (to be more efficient for example...).

I guess you could have something that checks if a class looks like it is immutable or not though, but it sounds like it could be pretty confusing.

You can have a class, which can be instantiated to an object, and this object can be mutable or immutable.

Example: A class may contain a List[_], which, at runtime, can be a List[Int] or a List[StringBuffer]. So two different objects of a class could be either mutable, or immutable.