Immutability: state, identity, and history

Lesson 02 gave you the syntax — val for a binding that cannot be reassigned, case class for a data record, and .copy to produce a changed version. Now we cash that syntax out into a principle. This is the first of the three pillars (03 immutable data, 04 pure functions, 05 functions as values). The one new idea: when a value can never change in place, an entire category of bug — the one where two parts of your program edit the same object behind each other's backs — simply cannot occur. We will see that bug happen, see immutability make it impossible, and end by naming the cost worry that Lesson 12 will resolve.

1 · The aliasing bug, concretely

An alias is a second name for the same object. With mutable data, aliases are a trap: change the object through one name and every other name sees the change, often far from where you were looking. Here is a mutable cart built on scala.collection.mutable.ListBuffer, plus an innocent-looking helper.

import scala.collection.mutable.ListBuffer

// a helper that "just looks at" the cart to compute a preview total
def previewWithFreebie(cart: ListBuffer[String]): Int = {
  cart += "free-gift"        // BUG: mutates the caller's cart in place
  cart.size
}

val myCart = ListBuffer("book", "pen")
val alsoMyCart = myCart      // NOT a copy — a second name for the SAME buffer

val n = previewWithFreebie(myCart)   // n == 3
println(myCart)       // ListBuffer(book, pen, free-gift)  -- changed!
println(alsoMyCart)   // ListBuffer(book, pen, free-gift)  -- ALSO changed!

Three names — the parameter cart, the binding myCart, and the alias alsoMyCart — all point at one buffer. The helper was only supposed to preview a total, but its += edited that one shared buffer, so the free gift now appears everywhere. The damage shows up at println(alsoMyCart), a line that never called the helper. That is action-at-a-distance: cause and effect are in different parts of the code, and to predict any line you must know the entire history of who-touched-what.

Now the same shape with an immutable List and a case class. The helper cannot reach back and edit the caller's data, because there is no operation that edits a List at all.

case class Cart(items: List[String])

def previewWithFreebie(cart: Cart): Int =
  cart.copy(items = cart.items :+ "free-gift").items.size   // builds a NEW Cart

val myCart    = Cart(List("book", "pen"))
val alsoMyCart = myCart                 // a second name — but for an unchangeable value

val n = previewWithFreebie(myCart)      // n == 3, computed from a fresh Cart
println(myCart.items)       // List(book, pen)  -- untouched
println(alsoMyCart.items)   // List(book, pen)  -- untouched

The helper still computes 3, but it does so by building a brand-new Cart and asking its size. The original myCart is exactly what it always was. Aliasing is now harmless: alsoMyCart is a second name for a value that nobody can change, so it does not matter how many names point at it. The bug is not "less likely" — it is unrepresentable, because the language offers no way to mutate the shared thing.

2 · Value versus identity

Two questions get conflated when data is mutable, and pulling them apart is the heart of this lesson:

Identity only earns its keep when things mutate. If object #A can change, then "is this the same object as the one I stored?" is a real, load-bearing question — because if it is, a change here will be seen there. But when values are immutable, identity becomes irrelevant: two values that are equal now will be equal forever, so there is never a reason to care whether you hold "the same object" or "an equal copy." They are interchangeable in every situation.

val a = List(1, 2, 3)
val b = List(1, 2, 3)
a == b   // true  -- same VALUE
a eq b   // (likely) false -- different objects, i.e. different IDENTITY
// Because neither can ever change, the eq answer never matters to your logic.

This is why immutability quietly makes three things safe at once. Equality behaves: a value's contents define it, and they never drift, so == is a stable fact rather than a snapshot. Caching / memoization is safe: if you stored a result keyed by an immutable input, that key cannot mutate underneath you and corrupt the cache. Sharing is safe: handing the same value to ten callers can never let one caller's later "change" leak to the others, because there is no later change. With mutable data, every one of these requires defensive copies and careful reasoning about identity; immutability deletes the question.

3 · Copy-on-write, and history for free

"Never changes in place" does not mean "never updates." It means an update is a function: take the old value, return a new value that differs in the intended way, and leave the old one standing. This is copy-on-write. You already met the operators in Lesson 02; here is what they return.

case class Account(owner: String, balance: Int)

val before  = Account("ada", 100)
val after   = before.copy(balance = 150)   // a NEW Account; `before` is unchanged

before.balance   // 100   -- still valid, still true
after.balance    // 150

val xs  = List(2, 3)
val ys  = 1 :: xs        // prepend -> List(1, 2, 3); xs is still List(2, 3)
val zs  = xs :+ 4        // append  -> List(2, 3, 4); xs is still List(2, 3)
xs       // List(2, 3)   -- every "update" left the original intact

Notice the payoff hiding in plain sight: after these updates you still hold before and xs — the prior states — and they are still completely valid values. That is a history, and you got it for free. Undo is "use the old reference you still have." Time-travel debugging, audit logs, and "compare the state before and after" all become trivial, because the old value was never destroyed to make the new one. With mutable data you would have had to deliberately snapshot a copy beforehand and hope you copied deeply enough; with immutable data the old value is simply still there.

4 · Why this matters for concurrency (preview of Lesson 13)

Most concurrency bugs are aliasing bugs with a stopwatch: two threads hold the same mutable object and write to it without coordinating, so the final state depends on who-won-the-race — a data race. The standard fix is locking: make threads take turns. Locks are slow, easy to get wrong (deadlocks, forgotten locks), and they re-introduce ordering-dependence — the very thing we are trying to escape.

Immutability sidesteps the whole problem. If a value can never change, then it does not matter how many threads read it at once, in what order — there is nothing to coordinate, because there is no write. A shared immutable value needs no lock. This is the deepest reason the functional core from Lesson 00 is "safe to run in parallel": its data cannot be raced on. Lesson 13 develops this into safe streams and Future; for now, keep the slogan: no shared mutation, no data races, no locks.

5 · The cost worry, stated honestly

The fair objection arrives immediately: if every update builds a new value, am I not copying the entire structure on every change? Append to a million-element list a thousand times and surely that is a billion copies. If immutable updates really deep-copied everything, they would indeed be too slow to use.

They do not. The intuition to hold now: you only build the part that differs, and you share the part that does not. Prepending 1 :: xs does not copy xs — the new list is a single new node whose tail points at the existing xs. Both the old and new list share that same tail, and sharing is safe precisely because (§3) nobody can mutate it. So an "update" is often O(1) or O(log n) new nodes plus a pointer to the untouched rest, not a full copy.

Common mistakes / failure modes

Checkpoint exercise

class Account(var balance: Int) {
  def deposit(n: Int): Unit  = { balance += n }   // mutates in place
  def withdraw(n: Int): Unit = { balance -= n }   // mutates in place
}

Where this points next

Immutable data is the first pillar, but it is only half the story. You can have data that never changes and still write a function that reads the clock, logs to disk, or throws — and such a function still means different things at different times. Lesson 04 supplies the other half: purity and referential transparency. It defines precisely what it means for a function to depend only on its inputs and do nothing else, sharpens the substitution model from Lesson 01 into a proof tool, and shows that purity + immutability together are what make code testable and parallelizable. Where this lesson removed the bug of shared mutable state, the next removes the bug of hidden effects.

Interview prompts

• What is an aliasing bug, and why does immutability eliminate it? (§1 — two references to one mutable object let a change through one name surprise the others (action-at-a-distance); immutable data offers no in-place mutation, so the shared thing can never change and aliasing becomes harmless.)
• Distinguish a value from its identity. When does identity matter? (§2 — value is the contents (==); identity is which object (eq). Identity only matters when objects can mutate; with immutable data equal values are interchangeable forever, so identity stops being a question.)
• How do you "update" immutable data, and what happens to the old value? (§3 — copy-on-write: .copy(field = v), x :: list, list :+ x return a new value; the old one is untouched and still valid, giving free history/undo and safe sharing.)
• Why is val buf = ListBuffer(1,2) not immutable? (§Common mistakes — val fixes the reference, not the contents; buf += 3 still mutates in place. Immutability is a property of the data type, and you also need it deep, not just shallow.)
• Why does immutability make concurrency easier? (§4 — data races are aliasing bugs across threads; an unchangeable value has no writes to coordinate, so it can be shared with no locking, deadlocks, or order-dependence.)
• "Building a new value on every update must be wasteful." Is it? (§5 — no: structural sharing means an update builds only the changed part and points at the unchanged rest (safe because nothing mutates); often O(1)/O(log n). Lesson 12 supplies the persistent structures.)
• Why are caching and equality safe with immutable keys but treacherous with mutable ones? (§2 — an immutable key/value cannot drift after being stored, so == is a stable fact and a cache entry cannot be corrupted underneath you; a mutable key can change after insertion and break both.)