Purity and referential transparency

Lesson 03 gave us data that never changes in place, killing aliasing bugs. But a value standing still is only half the story — the functions that read and transform it can still misbehave: they can reach out and touch the world, or quietly depend on it. This lesson nails down the second pillar precisely. A pure function depends only on its arguments and does nothing observable besides return a result; referential transparency is the property that lets you replace any such call with its result without changing what the program means. That property is exactly what makes the substitution model from Lesson 01 a valid proof tool rather than a hand-wave.

Book source

Maps to Widman's treatment of pure functions and referential transparency — the chapter that turns the informal "no side effects" slogan into a checkable definition and connects it to equational reasoning. We follow that arc (define purity, enumerate the effects that break it, show substitution as proof, list the payoffs) but the examples, traces, and the impure counter-example are original.

Linear position

Prerequisite: Lesson 03 (immutable data — a value means one thing forever) and Lesson 01 (the substitution model — replace an expression with its value).
New capability: a precise, testable definition of a pure function and of referential transparency, and the ability to use substitution as a proof tool — to prove two expressions equal by equational reasoning, and to see exactly where that reasoning fails for impure code.

The plan

Six moves. (1) Define a pure function in two clauses you can check. (2) Enumerate every common way to break purity, with a one-line impure example of each. (3) Define referential transparency and show it is what licenses the substitution model. (4) Work an equational-reasoning proof, then run the same steps on an impure function and watch them break. (5) Collect the payoffs, each tied directly to RT. (6) Answer "but I need effects" — purity does not ban them, it relocates them to the shell (Lesson 14).

1 · What a pure function is — two clauses

A function is pure if it satisfies both of these, every time, for every input:

clause 1 — result depends only on arguments

The returned value is a function of the inputs alone. Nothing else feeds in: no global, no field, no clock, no file, no random source. Same arguments ⇒ same result, always, forever, on any machine.

clause 2 — evaluating it has no observable effect

Calling it does nothing to the world beyond producing the result: it does not mutate anything reachable elsewhere, write to a screen/file/network, or alter any state a later observer could detect. The only thing that "happens" is the value comes back.

Read clause 1 as "the function is a faithful lookup table from inputs to outputs," and clause 2 as "running it leaves no fingerprints." A function that passes both is a closed, self-contained mapping — to know what it does you read its signature and body, nothing else. That is the whole prize, and everything below is consequences of it.

// pure: result is determined by n alone, and nothing happens but the return
def square(n: Int): Int = n * n
// pure: same list in, same length out, no fingerprints
def size[A](xs: List[A]): Int = xs.length   // reads the list, returns a number

2 · The side effects that break purity

A side effect is anything a function does besides compute its return value from its arguments — it violates clause 1 (an extra input sneaks in) or clause 2 (an extra output leaks out). Here is the field guide; each line is impure for the reason named.

Effect	Breaks	One-line impure example
Mutating external state	clause 2	`def add(x: Int) = { buffer += x; buffer.sum }` — edits a shared `buffer`
I/O (console/file/network)	clause 2	`def greet(n: String) = println(s"hi $n")` — writes to the console
Throwing an exception	clause 2	`def head(xs: List[Int]) = if (xs.isEmpty) throw new Exception else xs.head`
Reading the clock	clause 1	`def stamp() = System.currentTimeMillis()` — result depends on when
Reading randomness	clause 1	`def roll() = scala.util.Random.nextInt(6)` — different each call
Depending on a global	clause 1	`def withTax(p: Double) = p * Config.taxRate` — hidden input
Mutating a global	clause 2	`def tick() = { Counter.n += 1 }` — changes shared state

Notice the symmetry: clause-1 breaks smuggle an extra input (the clock, the RNG seed, a global) the signature never declares; clause-2 breaks emit an extra output (a print, a mutation, a thrown control-flow jump) the return type never declares. A pure function's type signature is the whole contract; an impure one's signature lies by omission.

3 · Referential transparency — and why it licenses substitution

An expression is referentially transparent (RT) if you can replace it with its resulting value anywhere it appears and the program means exactly the same thing afterward. The link to purity is tight and goes both ways: every call to a pure function is referentially transparent, and a function whose every call is RT is pure. Purity is a property of functions; RT is the same property viewed from the expression side.

This is precisely the validity condition for Lesson 01's substitution model. That model said: to evaluate a program, repeatedly replace an expression with the value it reduces to. That rule is only sound when each replacement preserves meaning — i.e. when the expressions are RT. So RT is not a separate idea; it is the licence that makes substitution a legal move. Where calls are pure, you may substitute freely and reason about code the way you do about algebra. Where they are not, substitution silently changes the program, and equational reasoning is forbidden.

pure f ⟺ for all e: replace f(e) by its value ⇒ program meaning unchanged ⟺ f is referentially transparent

4 · Worked example — substitution as a proof tool

Worked example — proving f(x) + f(x) == 2 * f(x)

Let f be pure: def f(x: Int): Int = x * x + 1. We claim f(3) + f(3) == 2 * f(3). Because f is pure, f(3) is RT, so wherever f(3) appears we may replace it with its single value. Trace it:

f(3) + f(3)
=  (3*3 + 1) + (3*3 + 1)   // substitute the body — legal, f is RT
=  10 + 10
=  20
2 * f(3)
=  2 * (3*3 + 1)           // same substitution
=  2 * 10
=  20                       // both reduce to the same value ⇒ equal. ∎

The proof rested entirely on "f(3) denotes one fixed value, so I may replace each occurrence by it." That is RT doing the work. A compiler may use the same fact to memoize f(3) — compute it once, reuse it — and the program is unchanged.

The same reasoning is invalid for an impure f

Now let f have an effect — it increments a counter and returns the new count:

var n = 0
def f(x: Int): Int = { n += 1; n }   // impure: reads & mutates a global

Try the "proof." Calling twice and calling once are no longer interchangeable (Scala evaluates the left operand of + first, so the two calls return 1 then 2 — and the fact that the order now changes the answer is itself the disease):

f(3) + f(3)   // first call returns 1, second returns 2  ⇒  1 + 2 = 3
2 * f(3)      // single call returns 1                    ⇒  2 * 1 = 2
3 != 2        // the identity FAILS

The step "replace each f(3) by its value" is illegal here, because f(3) does not have a single value — each evaluation produces a different one and leaves a fingerprint. The moment a function breaks purity, equational reasoning, memoization, and reordering all become unsound. This is the entire practical difference between the two pillars meeting.

5 · The payoffs — each is RT cashed out

Local reasoning

To understand a pure call you read its arguments and body — never the surrounding history. RT means the call means the same thing in isolation as in context, so you debug by reading, not by simulating global state.

Trivial testing

Same input ⇒ same output, no fingerprints, so a test is one line: feed inputs, assert the output. No mocks, no setup of hidden state, no teardown, no flakiness from a clock or RNG.

Legal memoization / caching

Because f(x) always equals one value, you may compute it once and reuse it. Caching a pure call can never be observed; caching an impure one drops its effects and changes behavior.

Safe parallelism & reordering

RT calls share nothing mutable and produce no ordering-sensitive effects, so they can run in any order, or at the same time, with the same result — the basis for safe concurrency (Lesson 13).

6 · "But I need effects" — purity relocates them, it does not ban them

A program that computes purely and never touches the world is useless — it must eventually print, persist, or respond. Purity is not a vow of inaction; it is a discipline about where effects live. As Lesson 00 framed it, you keep a large functional core of pure functions and push every effect to a thin imperative shell at the edge: the shell reads inputs, hands them to the core, and carries out whatever the core described. The core stays RT — testable, cacheable, parallelizable — and the small effectful rim is the only part you must reason about with care. Lesson 14 takes the final step: it makes effects themselves into ordinary values (an IO you build purely, then run once at the very edge), so even the description of an effect obeys RT.

Common mistakes / failure modes

"Logging is harmless"

A println or logger call is still I/O — an observable output the signature never declares. It breaks clause 2 and therefore RT, even though it "doesn't affect the result." Harmless to the answer is not the same as pure.

Hidden impurity via shared mutable defaults

A function closing over a mutable buffer, a cached var, or a shared default collection is impure even if it looks like it only reads — later calls see earlier mutations. The smuggled input/output hides in a closure.

Exceptions as control flow

Throwing to signal "not found" or "bad input" is an effect (a non-local jump) that breaks clause 2 and RT: f(x) no longer denotes a value. This is exactly what motivates typed failure with Option/Either in Lesson 11.

"Same output this run" ≠ pure

Reading the clock or a config that happens not to change today is still a clause-1 break: purity demands the same output for the same arguments always, on any machine, at any time — not just coincidentally right now.

Checkpoint exercise

Try it

Classify each function as pure or impure, and justify via RT — can you replace a call with its value everywhere without changing the program?

// a
def discount(price: Double, pct: Double): Double = price * (1 - pct)
// b
def now(): Long = System.currentTimeMillis()
// c
def shout(s: String): String = { println(s); s.toUpperCase }
// d
def total(xs: List[Int]): Int = xs.sum
// e  (cache is a shared mutable Map captured in the closure)
def memoLen(s: String): Int = cache.getOrElseUpdate(s, s.length)

Answers: a pure (result from args, no effect — RT). b impure, clause 1 (depends on the clock; two calls differ — not RT). c impure, clause 2 (the println is observable I/O even though the return is a function of s). d pure (RT). e impure, clause 2 (mutates the shared cache; the result is stable but the call leaves a fingerprint, so the call is not freely replaceable in all contexts). For each impure one, name whether a hidden input or a leaked output is the culprit.

Where this points next

Immutable data (03) plus pure functions (04) give us pieces that are trustworthy: a value that never changes, transformed by a function that means one thing and leaves no trace. But a trustworthy piece is only useful if it combines. Lesson 05 makes functions first-class values — things you can pass, return, and snap together with compose/andThen and higher-order functions like map/filter/reduce. Purity is what makes that composition safe: because each piece is RT, composing them never introduces a hidden interaction. Pillars two and three together turn "small reliable parts" into "large programs built, not tangled."

Takeaway

A function is pure when its result depends only on its arguments (clause 1: no smuggled inputs — no clock, RNG, or global) and evaluating it has no observable effect (clause 2: no leaked outputs — no mutation, I/O, or thrown jump). The expression-level view of that property is referential transparency: a pure call may be replaced by its value anywhere with no change in meaning — purity ⟺ every call is RT. RT is precisely what makes Lesson 01's substitution model a valid proof tool: with it you can prove f(x)+f(x)==2*f(x) by replacing each f(x) with its single value, and you can watch that exact reasoning collapse for an impure f whose two calls differ. The payoffs — local reasoning, one-line tests, legal memoization, and safe parallelism/reordering — are all RT cashed out. Purity does not forbid effects; it pushes them to the thin imperative shell (Lesson 14 makes effects themselves into values), keeping a large core you can reason about for free.

Interview prompts

Define a pure function precisely. (§1 — two checkable clauses: the result depends only on the arguments, and evaluating it produces no observable effect; equivalently, same input ⇒ same output, always, with no fingerprints.)
What is referential transparency, and how does it relate to purity? (§3 — an expression is RT if replacing it with its value preserves program meaning; purity ⟺ every call to the function is RT — same property, function-side vs expression-side.)
Why is referential transparency what makes the substitution model valid? (§3 — substitution replaces an expression with its value; that step only preserves meaning when the expression is RT, so RT is the licence for equational reasoning.)
Show that f(x) + f(x) == 2 * f(x), and explain when it fails. (§4 — for pure f, substitute the single value of f(x) on both sides; it fails for an impure f (e.g. one that increments a counter) because two calls return different values — calling twice ≠ once.)
Is logging a side effect? Why does it matter if it doesn't change the result? (§2, common mistakes — yes; it is observable I/O that breaks clause 2 and RT, so the call is no longer freely replaceable, killing memoization/reordering even though the return is unaffected.)
Name the categories of side effect and which clause each breaks. (§2 — clause-1 breaks add a hidden input: clock, randomness, reading a global; clause-2 breaks leak an output: mutation, I/O, thrown exceptions, mutating a global.)
If FP requires purity, how does any real program do I/O? (§6 — purity relocates effects rather than banning them: a large pure core, a thin imperative shell at the edge; Lesson 14 turns effects into values (IO) so even effect descriptions stay RT.)