Expressions and Statements
Consider the line `x = f(y) + 1;` in a typical imperative program. Buried inside it is a subtlety. It trips up many beginners. It also shapes the design of every programming language. The call `f(y)` produces a value that feeds into the addition. The assignment as a whole produces no value at all. Instead it produces an effect, a change to memory. This distinction between things that compute a value and things that change the world is one of the oldest dividing lines in language design. It is also one of the most consequential. Every language must decide how much of its syntax lives on each side of this line. That decision ripples through everything else. It affects how programs compose and how compilers optimize. It affects how easy code is to reason about. It even affects whether a language is "functional" or "imperative" in spirit. Scheme and Rust lean toward making nearly everything an expression. Classic C and Pascal draw a sharp line between expressions and statements. Python sits in between. It deliberately keeps assignment a statement to avoid a class of bugs. Understanding this contrast is a prerequisite for understanding Evaluation and Reduction of Expressions, The Imperative Paradigm, and later, control flow and type systems. The distinction is not merely stylistic. It has semantic teeth. Expressions denote values under an evaluation relation. Statements transform a store (the mapping from locations to values) via an execution relation. A grammar built from Grammars and BNF can generate the same surface strings under either interpretation. But the meaning — what an interpreter actually does with a piece of syntax — depends entirely on which side of the expression/statement line that syntax falls on. This article gives the precise definitions. It gives the small-step semantics that make the contrast rigorous. It includes a worked trace through a real program. It covers the classic pitfalls: dangling-else style ambiguities, assignment-as-expression bugs, and statement-expression confusion. Finally, it traces the historical arc from FORTRAN's strict statement orientation to Lisp's radical expression orientation. It ends with the hybrid designs that dominate today.
- An expression evaluates to a value; a statement executes for its effect on the store.
- Formally: expressions have an evaluation relation `e ⇓ v`; statements have an execution relation `⟨s, σ⟩ → σ′`.
- Some languages (Lisp, ML, Rust) make almost everything an expression, including blocks and conditionals.
- Other languages (classic C, Pascal) enforce a hard syntactic split via separate grammar nonterminals.
- The split affects composability, optimizability (pure expressions can be reordered/memoized), and safety.
- Hybrid designs use expression statements (discard the value) and statement expressions (wrap effects).
Expressions denote values you can compose; statements denote effects you can only sequence.
The idea
An expression is a piece of syntax whose evaluation yields a value — a number, a boolean, a string, a pointer, a closure. Expressions compose: you can nest `f(g(x) + 1)` because `g(x) + 1` denotes a value that fits into the hole `f(·)` expects. Formally, we equip the language with an evaluation relation, written `e ⇓ v` or given by a small-step relation `e → e′`, that relates expressions to the values they reduce to. Evaluation may read the store (e.g., dereferencing a variable) but the defining output of an expression is its value. A statement (sometimes called a command) is a piece of syntax executed for its side effect on the program store — the abstract mapping `σ : Location → Value` introduced when discussing Values and Storage. Statements are related by an execution relation `⟨s, σ⟩ → σ′`, read "statement `s` run in store `σ` produces new store `σ′`." A statement by itself has no denotation as a value; `while (true) {}` does not compute anything you can plug into an addition. Statements compose only by sequencing (`s1 ; s2`), not by nesting inside value-producing positions. The key semantic asymmetry: expressions are usually referentially transparent in the pure fragment of a language (replacing `e` by its value `v` anywhere does not change the program's meaning), which licenses reordering, common-subexpression elimination, and memoization. Statements are inherently about order — swapping `x = 1; x = 2;` for `x = 2; x = 1;` changes the final store, so a compiler must preserve statement order (subject to a proven absence of interfering effects) far more conservatively than it treats expression order. This is why optimizing compilers built on grammars from Grammars and BNF keep expression trees and statement/control-flow graphs as distinct intermediate structures internally, even when the source syntax blurs the two. Languages differ in how strictly they enforce the split:
- Statement-oriented languages (FORTRAN, classic C, Pascal, COBOL) have two disjoint syntactic categories,
`Expr` and `Stmt`, with a grammar production `Stmt ::= Expr ;` (an expression statement) as the only bridge from the expression world into the statement world, discarding whatever value the expression produced.
- Expression-oriented languages (Lisp/Scheme, ML, Haskell, Rust) treat everything, including conditionals,
blocks, and even loops, as an expression that yields a value (a block yields the value of its last expression; a loop may yield `()`, the unit value, or `!`, the "never" type, if it diverges).
- Hybrid languages (Python, Java, JavaScript, Go) keep a syntactic Stmt/Expr split for readability and to
block certain bugs (Python famously disallows `if (x = 5):` — assignment is a statement, not an expression, so it cannot masquerade as a comparison), while still allowing conditional expressions (`a if c else b`) and expression statements.
How it works
The clean way to make the contrast precise is to define two mutually recursive syntactic categories and two separate semantic relations that operate over them.
Abstract syntax. ``` Expr e ::= n | x | e1 + e2 | e1 * e2 | e1 == e2 | (e1, e2) -- pairs | if e1 then e2 else e3 -- expression-level conditional (both branches are Expr) | { s ; e } -- block expression: run statement s for effect, then yield e's value Stmt s ::= skip | x := e -- assignment: an effect, produces no value | s1 ; s2 -- sequencing | if e then s1 else s2 -- statement-level conditional (branches are Stmt, no value) | while e do s -- looping: an effect | e ; -- expression statement: evaluate e, discard its value ```
Two judgments. Expressions are evaluated against a store to a value (they may read the store but the judgment's output is a value); statements are executed against a store to a new store. ``` Evaluation of expressions: ⟨e, σ⟩ ⇓ v (v is a value, σ unchanged unless e itself embeds a Stmt) Execution of statements: ⟨s, σ⟩ → σ′ (σ′ is the updated store) ``` The rules below are given as a small-step / big-step operational semantics, in the style used to define Evaluation and Reduction of Expressions rigorously. ``` -- EXPRESSION RULES (⇓) ------------------------------------------------- [E-Num] ⟨n, σ⟩ ⇓ n [E-Var] σ(x) = v ----------------- ⟨x, σ⟩ ⇓ v [E-Add] ⟨e1, σ⟩ ⇓ v1 ⟨e2, σ⟩ ⇓ v2 v = v1 + v2 ------------------------------------------------ ⟨e1 + e2, σ⟩ ⇓ v [E-If] ⟨e1, σ⟩ ⇓ true ⟨e2, σ⟩ ⇓ v ---------------------------------------- ⟨if e1 then e2 else e3, σ⟩ ⇓ v ⟨e1, σ⟩ ⇓ false ⟨e3, σ⟩ ⇓ v ---------------------------------------- ⟨if e1 then e2 else e3, σ⟩ ⇓ v [E-Block] ⟨s, σ⟩ → σ′ ⟨e, σ′⟩ ⇓ v ----------------------------------- ⟨{ s ; e }, σ⟩ ⇓ v -- STATEMENT RULES (→) --------------------------------------------------- [S-Skip] ⟨skip, σ⟩ → σ [S-Assign] ⟨e, σ⟩ ⇓ v -------------------------------- ⟨x := e, σ⟩ → σ[x ↦ v] [S-Seq] ⟨s1, σ⟩ → σ′ ⟨s2, σ′⟩ → σ″ ------------------------------------ ⟨s1 ; s2, σ⟩ → σ″ [S-IfTrue] ⟨e, σ⟩ ⇓ true ⟨s1, σ⟩ → σ′ --------------------------------------- ⟨if e then s1 else s2, σ⟩ → σ′ [S-IfFalse] ⟨e, σ⟩ ⇓ false ⟨s2, σ⟩ → σ′ --------------------------------------- ⟨if e then s1 else s2, σ⟩ → σ′ [S-WhileT] ⟨e, σ⟩ ⇓ true ⟨s, σ⟩ → σ′ ⟨while e do s, σ′⟩ → σ″ ----------------------------------------------------------- ⟨while e do s, σ⟩ → σ″ [S-WhileF] ⟨e, σ⟩ ⇓ false ----------------------------- ⟨while e do s, σ⟩ → σ [S-ExprSt] ⟨e, σ⟩ ⇓ v -------------------------- (value v discarded) ⟨e ;, σ⟩ → σ ``` The two judgment forms are the whole story. Notice the shape asymmetry: `⇓` always ends in a value (the store, if present, is a side channel), while `→` always ends in a store (there is no value at all). The only bridges between the worlds are `[E-Block]` (a statement's effect is sequenced before an expression's value is produced) and `[S-ExprSt]` (an expression's value is computed and thrown away for its effect).
Evaluating an interpreter built on this split walks the abstract syntax tree, dispatching on whether the current node is an `Expr` or a `Stmt` node, and threading the store only through the `Stmt` side (and through any embedded `Stmt` inside an `Expr` block): ``` function EVAL(e, σ): # Expr → Value, store read-only except via embedded Stmt match e: case Num(n): return n case Var(x): return σ[x] case Add(e1, e2): return EVAL(e1, σ) + EVAL(e2, σ) case If(c, e1, e2): return EVAL(e1, σ) if EVAL(c, σ) else EVAL(e2, σ) case Block(s, e1): σ' = EXEC(s, σ) # run the effectful part return EVAL(e1, σ') # then compute the value function EXEC(s, σ): # Stmt → Store match s: case Skip: return σ case Assign(x, e): v = EVAL(e, σ); return σ[x ↦ v] case Seq(s1, s2): return EXEC(s2, EXEC(s1, σ)) case If(c, s1, s2): return EXEC(s1, σ) if EVAL(c, σ) else EXEC(s2, σ) case While(c, body): while EVAL(c, σ): σ = EXEC(body, σ) return σ case ExprStmt(e): EVAL(e, σ); return σ # value computed, then dropped ```
Complexity & correctness
Complexity. Both `EVAL` and `EXEC` are structural recursions over the abstract syntax tree, so each call does `O(1)` work at a node plus recursive calls on its children. For a tree with `N` nodes and no loops in the source program, evaluation is `O(N)` — every subexpression and substatement is visited exactly once (memoized values and stores are threaded, not recomputed). This is the same linear-in-tree-size bound that applies to any tree-walking interpreter or to one-pass code generation over an AST produced by a parser from Grammars and BNF. The one wrinkle is `while`: its execution time is not bounded by the static size of the AST but by the number of loop iterations actually taken at run time, each of which re-walks the (statically bounded) body. So the honest bound is: ``` Time(EXEC(s, σ)) = O(size(s)) + Σ_{loop iterations i} O(size(body_i)) ``` which is `O(N)` for loop-free code and unbounded (as it must be, since the language is Turing-complete) in general — there is no static bound on iteration count without solving the halting problem, which is undecidable. Space is `O(d)` for the call stack, where `d` is the AST's nesting depth, plus `O(|σ|)` for the store itself.
Correctness — what "correct" even means here. The claim to prove is not an algorithmic optimization claim but a semantic well-formedness claim: the two relations `⇓` and `→` are total on well-typed programs and deterministic. Both follow by structural induction on the derivation. Determinism. By induction on the derivation of `⟨e, σ⟩ ⇓ v`: at each AST node exactly one rule's premises can apply (the rules are syntax-directed — `Add` only matches `[E-Add]`, `If` only matches one of the two `[E-If]` branches depending on the discriminant's value, never both since `true ≠ false`). Given deterministic recursive results for the children by the induction hypothesis, the conclusion is uniquely determined. The identical argument, structurally, gives determinism of `⟨s, σ⟩ → σ′`. Totality (termination) for the loop-free fragment. Define a measure `μ` = the number of AST nodes in the term being evaluated/executed. Every rule's premises evaluate/execute strictly smaller subterms (e.g. `[E-Add]` recurses on `e1` and `e2`, each strictly smaller than `e1 + e2`). By well-founded induction on `μ`, a derivation exists and terminates for every closed loop-free term. `while` breaks this measure (the body can be re-executed with the same size), which is exactly why totality fails there in general — consistent with The Imperative Paradigm's trademark tradeoff of expressive control flow against guaranteed termination. Store-safety invariant. If `σ` is well-formed (every variable used in `e` or `s` is in `σ`'s domain) before execution, it remains well-formed after: `[S-Assign]` only ever extends or overwrites a binding, it never removes one, so `dom(σ) ⊆ dom(σ[x ↦ v])`. This is the invariant a type checker relies on to guarantee "no undefined variable" errors at run time, once variables are pre-declared.
Honest tradeoffs. Making everything an expression (Lisp-style) buys uniform composability and lets a single evaluator handle the whole language, but it can make effects harder to spot by eye — `(set! x (+ x 1))` reads exactly like a value-producing call, so purity has to be tracked by convention or by an effect type system. Keeping a hard Stmt/Expr split (C-style) makes effectful code visually distinct and rules out certain bugs (see below), but it forces duplicate constructs — a statement-`if` and an expression-`?:` — and complicates "can I use this as a value?" questions that programmers ask constantly (hence C's ternary operator existing at all, as an expression-shaped escape hatch from the statement-shaped `if`).
Worked example
Trace the program (using the calculus above, with initial store `σ0 = {}`): ``` x := 3 ; y := { z := x + 1 ; z * z } ; -- z is scoped to this block for the example (x + y) ; -- an expression statement: computed, then discarded ``` Step-by-step derivation, threading the store:
| step | construct evaluated/executed | rule used | resulting value / store |
|---|---|---|---|
| 1 | `⟨3, σ0⟩ ⇓ 3` | [E-Num] | value `3` |
| 2 | `⟨x := 3, σ0⟩ → σ1` | [S-Assign] | `σ1 = {x ↦ 3}` |
| 3 | `⟨x, σ1⟩ ⇓ 3`, `⟨1, σ1⟩ ⇓ 1`, so `⟨x+1, σ1⟩ ⇓ 4` | [E-Var],[E-Num],[E-Add] | value `4` |
| 4 | `⟨z := x+1, σ1⟩ → σ1′` | [S-Assign] | `σ1′ = {x↦3, z↦4}` |
| 5 | `⟨z, σ1′⟩ ⇓ 4`, so `⟨z*z, σ1′⟩ ⇓ 16` | [E-Var],[E-Mult] | value `16` |
| 6 | `⟨{ z:=x+1 ; z*z }, σ1⟩ ⇓ 16` | [E-Block] (combines steps 4–5) | value `16` |
| 7 | `⟨y := { … }, σ1⟩ → σ2` | [S-Assign] | `σ2 = {x↦3, z↦4, y↦16}` |
| 8 | `⟨x, σ2⟩ ⇓ 3`, `⟨y, σ2⟩ ⇓ 16`, so `⟨x+y, σ2⟩ ⇓ 19` | [E-Var],[E-Add] | value `19` |
| 9 | `⟨(x+y);, σ2⟩ → σ2` | [S-ExprSt] | value `19` discarded, store unchanged |
The final store is `σ2 = {x ↦ 3, z ↦ 4, y ↦ 16}`. Step 9 is the pedagogically important one: the value `19` was genuinely computed (an `⇓` derivation exists and is used inside the compiler for, e.g., dead-code-elimination warnings — "expression result unused"), but the program's meaning, as a sequence of store transformations, is completely unaffected by that value. This is precisely why `x + y;` alone as a full statement is legal but useless C, and why linters flag it: the expression/statement distinction lets a compiler prove, syntactically, that a whole line has no observable effect. Contrast with an expression-oriented rendering of the same idea in an ML-like language: ``` let x = 3 in let y = (let z = x + 1 in z z) in x + y ( the WHOLE program is one expression; its value, 19, IS the answer ) ``` Here there is no analogue of step 9's "discard" — every subpart contributes to the final value, because `let`-expressions and the top-level program are themselves expressions all the way down. The same arithmetic* happens; what differs is which final judgment form (`⇓` producing a value vs. `→` producing a store) the language exposes as the program's ultimate meaning.
Common pitfalls & traps
| pitfall | why it happens | fix |
|---|---|---|
| Assignment mistaken for equality (`if (x = 5)` in C) | `=` is an expression that evaluates to the assigned value and is truthy/falsy | use `==`; some languages (Python) forbid `=` as an expression entirely |
| Expecting a `void`/statement-like construct to hand back a value | statement-oriented forms (`for`, plain `if`) have no `⇓` rule, only `→` | use the expression form (`?:`, expression-`if`, `match`) when a value is needed |
| Treating `e ;` as "the value of `e` becomes the statement's value" | `[S-ExprSt]` explicitly discards the value — there is no value on the Stmt side | if the value matters, bind it first: `v := e ;` then use `v` |
| Assuming expression evaluation order is unspecified-but-harmless | many languages do not fix the order of `e1 + e2`'s subevaluations, so embedded effects can race | avoid side effects inside expressions where order is unspecified (C, historically) |
| Dangling-`else` ambiguity conflating statement-`if` with an outer one | `Stmt ::= if e then s1 else s2` is ambiguous without a rule for "match nearest unmatched if" | grammar disambiguation (attach `else` to nearest `if`) — a Grammars and BNF concern, not a semantic one |
| Assuming a block-expression's last statement (not expression) yields the value | `{ s1 ; s2 }` where `s2` is a `Stmt`, not `Expr`, has no `⇓` derivation at all | the grammar must require the tail position to be an `Expr` (`[E-Block]`'s `e`, not another `s`) |
Pioneers & history
The expression/statement divide crystallized as FORTRAN (1957) and Algol (1958, 1960) formalized imperative control flow as statements operating on a store, while McCarthy's Lisp (1958) took the opposite stance: even `cond` (the conditional) and function bodies were expressions, because Lisp was built on the Values and Storage-agnostic idea that a program is fundamentally a value-computing device, with mutation as an optional extra (`setq`). Algol 60's report, edited by a committee including Peter Naur and John Backus, is also the origin of the BNF notation from Grammars and BNF used to state the Stmt/Expr grammar split precisely for the first time. Dennis Ritchie's C (1972) hardened the split further while adding the ternary `?:` as a deliberate expression-side escape hatch, and Guido van Rossum's Python (1991) later made the split a design principle — assignment is a statement specifically to prevent the `if (x = 5)` class of bug that plagues C.
Origins · 1 minJohn McCarthy and how this was discovered
McCarthy's 1960 paper "Recursive Functions of Symbolic Expressions" defined Lisp's `eval` as a function from expressions to values, treating even control flow (`cond`) as value-producing — a radical departure from the statement-oriented FORTRAN of the same era, and the direct ancestor of every later expression-oriented language.
Where this matters
Compiler intermediate representations (IRs) mirror this split directly: LLVM IR, for instance, is built almost entirely from instructions that produce SSA values (the expression side) interleaved with explicit store/load instructions and branch/terminator instructions (the statement side) that manage control flow and memory effects — the very distinction this article formalizes, made load-bearing at the machine-code level. Type systems for effects (Haskell's `IO` monad, Rust's ownership-checked mutation, Java's checked exceptions) are all, at bottom, mechanisms for statically tracking which parts of a program are "pure expression" and which are "has an effect," precisely the `⇓` vs `→` line drawn here. Static analyzers and linters (`-Wunused-value` in GCC/Clang, `no-unused-expressions` in ESLint) exist specifically to catch the "expression statement whose value is silently discarded" pitfall. Understanding this contrast is also the direct on-ramp to Evaluation and Reduction of Expressions (how the `⇓`/`→` relations are computed step by step) and to The Imperative Paradigm (which builds an entire programming style on the statement side of this line).
Ask the tutor: How does the choice between expression-oriented and statement-oriented syntax change how a type checker assigns types to blocks and conditionals?
Is "statement" just another word for "expression with no return value"?
Not quite — it is more precise to say a statement has no value denotation at all in the formal semantics, rather than a value of some special "no-value" type. Some languages do model this with a real unit type (`()` in ML/Rust), effectively turning every statement into a value-producing expression of trivial type — which is exactly how expression-oriented languages unify the two categories. But in a strict statement-oriented language like classic C, a bare statement genuinely has no place in the grammar where a value is expected; there is no unit value to plug in, only a separate nonterminal.
Why does C need both `if`-as-statement and `?:`-as-expression instead of just one?
Because C's grammar keeps `Stmt` and `Expr` strictly disjoint, `if` (defined only over `Stmt`) cannot appear where an expression is expected, e.g., inside `int m = if (a>b) a else b;` is illegal. The ternary `?:` was added specifically as an expression-shaped conditional to fill that gap. Languages that instead make `if` itself an expression (Rust, ML, Kotlin) need no separate ternary operator at all — `if a>b { a } else { b }` already type-checks as a value.
Does "expression-oriented" mean a language has no statements or effects?
No. Lisp, ML, and Rust still have mutation, I/O, and loops — real effects on the store. What changes is only the syntactic packaging: every construct, including a loop or an assignment, is parsed as an `Expr` and assigned a value (often the unit value `()` or the "never" type `!` for a divergent loop) rather than being confined to a separate `Stmt` nonterminal. The `⇓`/`→` semantic distinction from this article still exists underneath; it is just that a single `⇓`-style judgment is used uniformly, with side effects on `σ` threaded through as well.
How does this connect to referential transparency and compiler optimization?
A pure expression `e` (no effects, deterministic) satisfies `⟨e, σ⟩ ⇓ v` for a fixed `v` regardless of when it is evaluated, so a compiler can freely reorder, hoist, common-subexpression-eliminate, or memoize it — this is the formal content of referential transparency. Statements, by contrast, are executed for their effect on `σ`, so reordering `s1 ; s2` into `s2 ; s1` is only sound if a compiler proves the two have no observable interference (a data-flow analysis called independence or non-aliasing). This is exactly why optimizing compilers apply much more aggressive, unconditional transformations to expression trees than to statement/control-flow graphs.
Where does the dangling-else problem fit into this article's split?
It is a syntactic ambiguity, not a semantic one: the statement grammar `Stmt ::= if e then s1 else s2 | if e then s1` is context-free ambiguous for input like `if e1 then if e2 then s1 else s2`, since the `else` could attach to either `if`. This is resolved at the Grammars and BNF level (by convention, "match the nearest unmatched `if`") before the execution rules `[S-IfTrue]`/`[S-IfFalse]` given here are even applied — those rules assume the ambiguity has already been resolved into a single parse tree.
Why does this article matter for understanding later material on evaluation strategies?
Because "evaluation order" and "evaluation strategy" (call-by-value, call-by-name, strict vs. lazy) are questions that only make sense for the expression side — they ask "in what order do we reduce `e ⇓ v`, and how eagerly?" Statements, executed via `→`, are ordered by sequencing (`;`) as a primitive of the language, not by an evaluation strategy choice. Evaluation and Reduction of Expressions builds directly on the `⇓` judgment defined here, refining it into the small-step reduction sequences that let you talk precisely about laziness, strictness, and termination of individual expressions.