Skip to main content

Concurrency and Language-Level Abstractions over Mutation

What This Concept Is​

Once two processes share mutable state, time is of the essence (SICP §3.4). The same program that was obvious in a single thread becomes a source of races, lost updates, and interleaving bugs.

Languages respond by offering abstractions over mutation that make concurrent programs easier to reason about:

  • Mutual exclusion primitives. Locks, semaphores, monitors, condition variables. Protect a critical section so that only one thread touches shared state at a time. SICP discusses make-serializer in §3.4.2.
  • Higher-level primitives. Atomic variables, compare-and-swap (CAS), futures/promises, actors, channels.
  • Purely functional structures. Immutable data + reference swapping eliminates many races outright.
  • Transactional memory. Clojure refs, Haskell STM: wrap a block of reads/writes in a transaction; the runtime retries until it commits atomically.
  • Single-writer disciplines. The event loop (Node, Python asyncio), the actor model (Erlang, Elixir) -- only one entity ever mutates a given piece of state.

The point of this concept in this module is not to teach full concurrency. It is to see concurrency as a language-design problem, continuous with the rest of the module.

Why It Matters Here​

It ties the cluster together:

  • Concept 13 introduces mutation and identity.
  • Concept 14 shows a pure alternative.
  • Concept 15 shows what happens in the adversarial case -- multiple agents, shared state, uncertain order -- and how language choices shape whether bugs are catchable by a junior engineer or require expert-level concurrency reasoning.

It also connects to later semesters:

  • OS/networking (S5) will implement threads, locks, and scheduling.
  • Distributed systems (S6) will generalize the same problems across nodes.
  • Concurrent data structures sit on top.

For this module, the goal is a mental map you can carry forward.

Concrete Example​

The classic race, SICP style (§3.4.1):

(define balance 100)
(define (deposit amount) (set! balance (+ balance amount)))

;; two threads each call (deposit 10)

Interleaving -- both threads read 100, both compute 110, both write 110. Final balance is 110, not 120. One deposit is silently lost.

Serialized version (§3.4.2):

(define serialized-deposit (serializer deposit))

Calls through the serializer are mutually exclusive; only one deposit runs at a time.

Atomic alternative (CAS):

# pseudo-Python using atomics
while True:
    old = balance.load()
    new = old + amount
    if balance.compare_and_swap(old, new):
        break

The while-loop spins until a successful swap. No lock, no contention point.

Immutable alternative (Clojure ref / atom):

(def balance (atom 100))
(swap! balance + 10)    ; atomic

swap! retries internally; the user sees an ordinary update.

Event-loop alternative (asyncio):

async def handler():
    nonlocal balance
    balance += amount   # single-threaded within the loop; no race

Each strategy trades something: locks can deadlock; CAS can live-lock; actors add message-passing overhead; immutability pays for copies; event loops cannot parallelize CPU-bound work.

Common Confusion / Misconception​

  1. "Add a lock, done." Locks are necessary, not sufficient. Ordering between locks matters. Granularity matters. A coarse-grained global lock is correct but kills throughput; fine-grained locks invite deadlock.
  2. "Immutable = thread-safe by default." Reading immutable data is safe; creating new versions and publishing them to other threads still requires careful memory ordering. That publication step is what atomics and release/acquire semantics address.
  3. "Async/await is concurrency." It is cooperative multitasking, useful for I/O-bound code. It gives you interleavings, not parallel execution. CPU-bound workloads still need threads or processes.
  4. "CAS is always faster than locks." For low contention, yes. For high contention, busy-spinning CAS loops can be worse than a lock.
  5. Confusing concurrency with parallelism. Concurrency is structuring a program as independent tasks. Parallelism is actually running them at once. A single-core system can run concurrent code without parallelism.

How To Use It​

When you first meet a concurrency problem:

  1. List the shared mutable state. If it is empty, you are done -- the program is trivially safe.
  2. Pick the smallest abstraction that works. Immutable + CAS beats locks; one-owner (actor, event loop) beats shared locks; shared locks beat ad-hoc synchronization.
  3. Name the invariants each critical section preserves. If you cannot name them, you cannot protect them.
  4. Avoid holding a lock across an I/O call or a callback. The number one real-world deadlock.
  5. Test with stress harnesses. Race bugs do not show up in single-threaded tests. Tools like go test -race, Python's concurrent.futures stress drivers, or TLA+ specs for the hard cases.

In design reviews, flag every new mutable field on a shared object with: "who writes this, who reads it, and what prevents a race?" If there is no answer, insist on one.

Check Yourself​

  1. Why is x = x + 1 not atomic on most modern hardware?
  2. Name three distinct language-level abstractions over mutation and what each buys you.
  3. Give one case where immutability + message passing is strictly cheaper than a lock, and one where a lock is the right call.

Mini Drill or Application​

Design -- on paper -- a small inventory service with a single mutable stock map. Sketch it four ways:

  • (a) one big lock around every access
  • (b) per-item locks
  • (c) an atomic map using CAS-style updates
  • (d) a single actor that owns stock and is the only thing that mutates it

For each, identify:

  • the failure mode if two threads simultaneously want to decrement the same item
  • one workload where this design is the right choice
  • one workload where it is the wrong one

You are not asked to implement. You are asked to be articulate about the tradeoffs.

Read This Only If Stuck​