What is functional programming?

Lesson 00 made a claim — that FP controls complexity by building programs from pure functions over immutable data — but "pure," "immutable," and "composition" were still slogans. This lesson makes them operational: a short checklist you can hold against any snippet to judge how functional it is, a single shared-mutation bug shown in two worlds, and the one rule that powers every reasoning advantage the series will claim — the substitution model: anywhere an expression appears, replace it with the value it evaluates to, and the program's meaning is unchanged.

Book source

This maps to Widman's framing of what functional programming is — the move from statements that do things to expressions that have values, and the idea that reasoning about a program should be as simple as reasoning about algebra. We keep the arc (operational definition → contrast with imperative → substitution model) but the examples, bug, and traces here are original.

Linear position

Prerequisite: Lesson 00 — the thesis (complexity comes from mutable state + side effects) and the functional-core / imperative-shell target architecture.
New capability: apply a checkable definition of FP to real code, explain precisely why a functional rewrite cannot harbour a shared-mutation bug, and run the substitution model by hand — including watching it break on impure code, which motivates the formal purity of Lesson 04.

The plan

Five moves. (1) An operational definition with a 4-point checklist — "how functional is this snippet?" (2) The contrast: one concrete shared-mutation bug, then the same logic functionally, and exactly why the bug becomes impossible. (3) Expressions vs statements — why if returning a value is the hinge. (4) The substitution model, stated as a rule, traced on pure code, then watched failing on impure code. (5) FP vs OOP — not opposites; the real axis is pure-immutable vs mutable-effectful.

1 · An operational definition you can check

"Functional programming" is not a language or a syntax — Scala, the language of this series, lets you write thoroughly imperative code. It is a discipline, and a discipline is only useful if you can tell whether you are following it. So here is a definition built to be checked, not admired:

FP = programming with pure functions over immutable data, built from expressions (every construct yields a value), composed by ordinary function composition.

Each word is load-bearing, and each becomes a question you can ask of any snippet. Run the snippet through this checklist; the more "yes" answers, the more functional it is. Functionality is a gradient, not a badge.

1. Pure functions?

Does each function return a result that depends only on its arguments, and do nothing else — no writing files, no mutating shared state, no throwing, no reading the clock? Same input ⇒ same output, every time. (Sharpened in Lesson 04.)

2. Immutable data?

When something needs to "change," is a new value built rather than an existing one edited in place? Does a binding mean the same thing for its whole lifetime? (Lesson 03.)

3. Expressions, not statements?

Is the code a tree of things that evaluate to values (so you can ask "what is this worth?"), rather than a sequence of commands that do something and yield nothing? (This section.)

4. Composed by composition?

Are bigger behaviours built by feeding one function's output into the next — f andThen g, or just g(f(x)) — rather than by sharing and stepping on mutable state? (Lesson 05.)

Notice what the checklist does not ask. It does not ask "do you use lambdas?" — you can write a lambda that mutates a global and fails every box. It does not ask "did you avoid vals or loops?" — local bindings and even local mutation that never escapes a function are fine. The checklist is about where state and effects live and whether they leak, exactly the two engines of complexity from Lesson 00.

2 · The same bug, two worlds

The fastest way to feel the definition is to watch a bug that only the imperative version can have. Here is a tiny task: given a list of order amounts, compute a running balance and also return how many were "large" (over 100). A helper mutates a shared accumulator.

Imperative — shared mutable state, with a bug

class Ledger {
  var balance: Int = 0           // shared, mutable

  // "helper": also nudges balance as a side effect
  def isLarge(amount: Int): Boolean = {
    balance += amount            // MUTATES shared state while classifying
    amount > 100
  }

  def summarize(amounts: List[Int]): (Int, Int) = {
    var largeCount = 0
    for (a <- amounts) {
      if (isLarge(a)) largeCount += 1   // calling isLarge silently moves balance
    }
    (balance, largeCount)
  }
}

Call summarize once and the numbers look right. Call it twice on the same Ledger and the balance double-counts, because balance survives between calls. Worse: isLarge reads as a pure predicate at every call site, but it is quietly editing balance. The bug lives in the gap between what the name promises and what the function does — and you cannot see it by reading summarize alone; you must simulate the whole object's history.

Now the functional version. Nothing is shared, nothing is mutated, and each function returns exactly what its type says.

Functional — values in, values out

def isLarge(amount: Int): Boolean = amount > 100          // pure: depends only on amount

def summarize(amounts: List[Int]): (Int, Int) = {
  val balance    = amounts.sum                            // a new value, computed from input
  val largeCount = amounts.count(isLarge)                 // a new value, computed from input
  (balance, largeCount)
}

isLarge now does one thing and says so. summarize takes a list and returns a pair derived from it — call it a thousand times with the same list and you get the same pair, because there is no balance hiding between calls to accumulate. The whole function is readable in isolation.

Why the functional version cannot have the bug — precisely. The imperative bug required two ingredients: (a) a piece of state that outlives a single call (balance as a field), and (b) a function that both returns a value and edits that state. The rewrite removes both. There is no field, so nothing outlives a call; and isLarge returns a Boolean and touches nothing else, so calling it cannot move any number. "Double-counting on the second call" is not a bug we fixed — it is a sentence that no longer typechecks against reality, because there is no second-call state to count into. This is the recurring shape of FP wins: you do not patch the bug, you remove the place the bug could be.

3 · Expressions vs statements

The third checklist item is the quiet hero, so it gets its own section. A statement is executed for its effect and evaluates to nothing useful; an expression is evaluated for its value. The difference shows up sharply in if.

Statement style (effect)	Expression style (value)
`var label = "" // mutate later if (score >= 60) label = "pass" // do something else label = "fail"`	`val label = // if HAS a value if (score >= 60) "pass" else "fail"`

In Scala — and this is central — if/else is an expression: it evaluates to one branch's value. The right column needs no var and no mutation, because the if itself is the value being bound. The left column reaches the same place by mutating a variable in two arms, which means label means "" for a moment and something else later — exactly the "means different things at different times" problem from Lesson 00.

Expression-orientation is what makes the substitution model (next) even possible. If every construct yields a value — if, match, a block { ... } whose value is its last expression, even a method body — then any piece of a program can be named by the value it computes, and you can reason about the program by swapping pieces for their values. A statement evaluates to nothing to swap; it only leaves a footprint in the world. Whole-program substitution requires whole-program expression-orientation.

4 · The substitution model

Here is the rule that underwrites every "you can reason locally" claim in the series. State it plainly:

The substitution rule

Anywhere an expression appears, you may replace it with the value it evaluates to (or vice versa), and the program's meaning is unchanged. Equally: a function call may be replaced by its body with the arguments substituted in. Code you can transform this way is said to be referentially transparent.

This is just high-school algebra applied to programs. If x = 3, then x + x and 3 + 3 and 6 are interchangeable; nobody worries that writing x "ran" something. The substitution model says the same should hold for function calls. Trace it on a pure snippet:

Worked substitution — a pure trace

def square(n: Int): Int = n * n
val r = square(4) + square(4)

square(4) + square(4) = (4 * 4) + square(4) -- replace the call by its body, n := 4 = 16 + square(4) -- replace the expression 4*4 by its value = 16 + 16 -- the SECOND square(4) is the same value, so the same answer = 32

Because square is pure, square(4) is 16 — interchangeably, every time it appears. We could even hoist it: val s = square(4); s + s has identical meaning. Substitution holds in every direction.

Now watch it fail. Make the function impure — give it a side effect on shared state — and the model stops working, which is the whole point of why purity will matter.

Worked substitution — where it breaks

var counter = 0
def next(): Int = { counter += 1; counter }   // impure: mutates and reads shared state
val r = next() + next()

What is r? You cannot compute it by substitution. The first next() is 1, the second is 2, so r is 3 — but if you "simplified" by replacing next() with its value, which value? They differ. And rewriting val n = next(); n + n gives 2 (=1+1), a different answer — so the call is not interchangeable with its value. The substitution model is broken precisely because next() depends on and changes hidden state: same expression, different value. Reasoning now requires tracking counter across the whole program — Lesson 00's complexity, returned.

That contrast is the engine of the series. The pure version can be understood by local rewriting; the impure version forces global simulation. Lesson 04 will turn "the substitution model holds for it" into the formal definition of a pure function, and use it as a proof tool for equational reasoning.

5 · FP vs OOP — not opposites

A common confusion: that functional and object-oriented programming are rival camps and Scala forces a choice. They are not opposites, and Scala deliberately blends them — it has classes, traits, and inheritance and first-class functions, immutable case classes, and pattern matching. OOP is about how you organize and bundle code (objects grouping data with the operations on it, polymorphism via subtyping); FP is about how values behave (pure, immutable, composed). You can have well-organized objects that are also immutable and pure.

The axis that actually matters is orthogonal to "objects vs functions":

The real axis

pure & immutable ⟷ mutable & effectful. This is the thing Lesson 00 said drives complexity. An object can sit at the pure end (an immutable case class with methods that return new values); a "functional-looking" pipeline of lambdas can sit at the mutable end if each closure pokes a shared var.

How Scala blends them

Use OOP to structure (traits to model a sum of cases, classes to bundle behaviour) and FP to reason (keep those types immutable, keep methods pure, push effects to the shell). The series uses both: sealed traits + case classes (Lesson 02, 06) are an OOP mechanism serving an FP goal.

Common mistakes / failure modes

Watch for these

"It uses lambdas, so it's functional." No. list.foreach(x => total += x) is a lambda that mutates shared state — it fails checklist items 1 and 2. Higher-order syntax is neither necessary nor sufficient; purity over immutable data is the test.
"FP bans variables and loops." No. It bans mutation and effects that escape a function. A local var used inside a tail-recursive helper and never observed outside is fine; a while loop computing a value with no external footprint is fine. The line is leakage, not keywords. (Lesson 12 reframes loops as recursion anyway.)
"Pure means it never does anything." No — a pure core computes results; the program still acts, in the thin imperative shell (Lesson 00). Purity localizes effects; it does not abolish them.
Confusing FP with OOP as enemies. The enemy is unmanaged state and hidden effects, in either paradigm.

Checkpoint exercise

Try it

Take this snippet and apply the substitution model by hand to find exactly where it breaks:

val log = scala.collection.mutable.ListBuffer[String]()
def greet(name: String): String = {
  log += name                 // record who we greeted
  s"Hello, $name"
}
val msg = greet("Ada") + " and " + greet("Ada")

(1) Is greet a pure function? Apply checklist items 1–2. (2) Try to replace both greet("Ada") calls with a single named value val g = greet("Ada") and compare the resulting program's behaviour — what differs, and is it the string result or something else? (3) State, in one sentence, the precise ingredient that makes substitution fail here, and which checklist item it violates. Then rewrite greet so the substitution model holds, and say where the logging belongs in the functional-core / imperative-shell picture.

Where this points next

We now have a checkable definition, the bug that motivates it, and the substitution rule that turns "reason locally" into something mechanical. But the examples have leaned on Scala notation — val/var, case, lambdas, List, match — without explaining it. Lesson 02 is a fast Scala crash course: just enough syntax (everything-is-an-expression, immutable bindings, case classes, sealed traits, pattern matching, List/Option, lambdas) to make every later example readable. After it, we return to the first pillar — immutability (Lesson 03) — and then sharpen "pure" into referential transparency using exactly the substitution model introduced here (Lesson 04).

Takeaway

Functional programming is a checkable discipline: pure functions over immutable data, built from expressions, composed by function composition — and "how functional is this code?" is a four-question test, not a yes/no badge. The payoff is concrete: a shared-mutation bug needs both state that outlives a call and a function that returns a value and mutates, so a pure-immutable rewrite does not patch the bug — it deletes the place the bug could exist. Expression-orientation (an if that has a value, not one that mutates a var) is what enables the substitution model: replace any expression with the value it evaluates to, meaning unchanged. That model holds for pure code and visibly breaks on impure code like next() or a logging greet — which is exactly why purity (Lesson 04) is the property worth chasing. FP and OOP are not rivals; Scala blends them, and the axis that matters is pure-immutable vs mutable-effectful.

Interview prompts

Give an operational definition of functional programming and a way to test code against it. (§1 — pure functions over immutable data, built from expressions, composed by composition; apply the 4-point checklist, treating functionality as a gradient.)
Why can't the functional rewrite of the ledger have the double-counting bug? (§2 — the bug needs state that outlives a call plus a function that both returns and mutates; the rewrite removes both, so there is no shared balance to accumulate into — the bug's location is deleted, not patched.)
What does "uses lambdas" have to do with being functional? (§1, common mistakes — nothing necessarily; a lambda that mutates a shared var fails the purity/immutability checks. Higher-order syntax is neither necessary nor sufficient.)
Why does expression-orientation matter, concretely? (§3 — if every construct yields a value (if, match, blocks), any sub-program can be named by its value, which is the precondition for reasoning by substitution; statements leave only effects, nothing to substitute.)
State the substitution model and show where it fails. (§4 — replace any expression with the value it evaluates to, meaning unchanged; it fails on next() because the impure call yields different values at different times, so it is not interchangeable with any single value, forcing global state tracking.)
Does FP forbid variables and loops? (§ common mistakes — no; it forbids mutation and effects that escape a function. Local, non-leaking mutation is fine; the line is leakage, not keywords.)
Are FP and OOP opposites, and where does Scala stand? (§5 — not opposites: OOP is how you organize/bundle, FP is how values behave. The real axis is pure-immutable vs mutable-effectful; Scala blends both, e.g. sealed traits + immutable case classes.)