Immutability and shared references - how to reconcile?

Question

Consider this simplified application domain:

• Criminal Investigative database
• Person is anyone involved in an investigation
• Report is a bit of info that is part of an investigation
• A Report references a primary Person (the subject of an investigation)
• A Report has accomplices who are secondarily related (and could certainly be primary in other investigations or reports
• These classes have ids that are used to store them in a database, since their info can change over time (e.g. we might find new aliases for a person, or add persons of interest to a report)

If these are stored in some sort of database and I wish to use immutable objects, there seems to be an issue regarding state and referencing.

Supposing that I change some meta-data about a Person. Since my Person objects immutable, I might have some code like:

class Person(
    val id:UUID,
    val aliases:List[String],
    val reports:List[Report]) {

  def addAlias(name:String) = new Person(id,name :: aliases,reports)
}

So that my Person with a new alias becomes a new object, also immutable. If a Report refers to that person, but the alias was changed elsewhere in the system, my Report now refers to the "old" person, i.e. the person without the new alias.

Similarly, I might have:

class Report(val id:UUID, val content:String) {
  /** Adding more info to our report */
  def updateContent(newContent:String) = new Report(id,newContent)
}

Since these objects don't know who refers to them, it's not clear to me how to let all the "referrers" know that there is a new object available representing the most recent state.

This could be done by having all objects "refresh" from a central data store and all operations that create new, updated, objects store to the central data store, but this feels like a cheesy reimplementation of the underlying language's referencing. i.e. it would be more clear to just make these "secondary storable objects" mutable. So, if I add an alias to a Person, all referrers see the new value without doing anything.

How is this dealt with when we want to avoid mutability, or is this a case where immutability is not helpful?

Answer 1

If X refers to Y, both are immutable, and Y changes (i.e. you replace it with an updated copy), then you have no choice but to replace X also (because it has changed, since the new X points to the new Y, not the old one).

This rapidly becomes a headache to maintain in highly interconnected data structures. You have three general approaches.

• Forget immutability in general. Make the links mutable. Fix them as needed. Be sure you really do fix them, or you might get a memory leak (X refers to old Y, which refers to old X, which refers to older Y, etc.).
• Don't store direct links, but rather ID codes that you can look up (e.g. a key into a hash map). You then need to handle the lookup failure case, but otherwise things are pretty robust. This is a little slower than the direct link, of course.
• Change the entire world. If something is changed, everything that links to it must also be changed (and performing this operation simultaneously across a complex data set is tricky, but theoretically possible, or at least the mutable aspects of it can be hidden e.g. with lots of lazy vals).

Which is preferable depends on your rate of lookups and updates, I expect.

Answer 2

I think you are trying to square the circle. Person is immutable, the list of Reports on a Person is part of the Person, and the list of Reports can change.

Would it be possible for an immutable Person have a reference to a mutable PersonRecord that keeps things like Reports and Aliases?

Answer 3

I suggest you to read how they people deal with the problem in clojure and Akka. Read about Software transactional memory. And some of my thoughts...

The immutability exists not for the sake of itself. Immutability is abstraction. It does not "exist" in nature. World is mutable, world is permanently changing. So it's quite natural for data structures to be mutable - they describe the state of the real or simulated object at a given moment in time. And it looks like OOP rulez here. At conceptual level the problem with this attitude is that object in RAM != real object - the data can be inaccurate, it comes with delay etc

So in case of most trivial requirements you can go with everything mutable - persons, reports etc Practical problems will arise when:

1. data structures are modified from concurrent threads
2. users provide conficting changes for the same objects
3. a user provide an invalid data and it should be rolled back

With naive mutable model you will quickly end up with inconsistent data and crushing system. Mutability is error prone, immutability is impossible. What you need is transactional view of the world. Within transaction program sees immutable world. And STM manages changes to be applied in consistent and thread-safe way.