Expression Evaluation

Computation as reduction

Expression evaluation concerns expressions and the values they return. A computation proceeds by stepwise reduction:

$E_0 \rightarrow E_1 \rightarrow E_2 \rightarrow \dots \rightarrow v$

We write $E \rightarrow E'$ to say that $E$ reduces to $E'$. Mathematically, $E = E'$, but the computation goes from $E$ to $E'$ and never the other way.

A value is something that cannot be further reduced — a number like 42, a string like "hello", or a function like <fun>.

Functional vs imperative programming

Style	Focus	Example
Functional	Expressions computing values	area 2.0 returns a float
Imperative	Commands changing state	x := x + 1 updates storage

Functional programming stays at the level of expressions. This may seem far removed from hardware, but for computing solutions to problems it is entirely adequate. Imperative programming requires a notion of states that can be observed and changed — assigning to variables, performing input/output — leading to conventional programs as coded in C.

Expressions vs values

An expression like 3 + 4 is not yet a value; it evaluates to 7. The expression nsum 3 evaluates through a sequence of reductions before yielding the value 6. The key distinction:

• Expressions may contain function calls, operators, and sub-expressions that need further evaluation
• Values are the end results: numbers, booleans, strings, functions, or constructed data

Stepwise reduction in OCaml

OCaml uses call-by-value evaluation: before applying a function, its argument is fully evaluated to a value. This means:

1. The argument expression is reduced to a value
2. The function body is then evaluated with the parameter bound to that value

This contrasts with call-by-name (evaluate the argument each time it is used) and call-by-need (evaluate at most once, caching the result). OCaml’s strict evaluation means recursive functions must have a base case that is reached without infinite descent.

Why expression evaluation matters

Modelling interaction and control (input/output, mutable state) requires additional concepts beyond pure expressions. But for the core of algorithm design — computing results from inputs — expression evaluation provides a clean, mathematically tractable foundation. The OCaml programmer thinks in terms of what an expression is (its value), not what it does (its effects).