Conditionals and Loops

The previous chapter gave a program a cell whose contents change: a value can be written where an earlier one stood, and a later read finds the new one. Writing one assignment changes the cell once. A program that sums the numbers in a list, or counts up to a bound, or halves a number until it drops below one, changes a cell a number of times it does not know when it is written, and decides each time whether to change it again. Two forms are missing. One chooses whether to act according to a value; the other repeats an action. This chapter adds the conditional if and the loops while and for.

Their category is already settled. The opening chapter of this part placed if, while, and for among the expressions: an if takes the value of the branch it runs, and a loop takes the value (), since a loop runs for the effect its body has on the store rather than for a result. What that chapter left open, and this one fixes, is what each evaluates to — the rules that pick a branch, and the rules that repeat one. The store threads through them as it threads through every form now, one store in and one store out, env ⊢ ⟨e, σ⟩ ⇓ ⟨v, σ'⟩. (The reference’s rules thread the relation database of Part VII and carry the outcome a return produces; this part uses the env-and-store slice mutation.md introduced.) The rules below are written with the keyword forms if e then e else e and while e e; the concrete syntax braces them, if c { … } and while c { … }, with no then.

Choosing a branch: if

The conditional is among the oldest control forms, and its shape changed as languages moved the choice into the program’s expressions. Fortran’s conditional was the arithmetic IF: IF (e) n1, n2, n3 jumped to one of three statement labels according to whether e was negative, zero, or positive — a branch to a label, decided by a sign. Algol 60 gave the if c then S else S that chooses a course of action in place, named by the condition being true or false, and set beside it a conditional expression that chooses between two values — the two-form split the first chapter of this part traced. Bridger keeps the single expression form: one if, valued by the branch it takes.

if evaluates its condition to a boolean, then evaluates the chosen branch against the store the condition produced. The other branch is not evaluated, so only the taken branch’s effects happen:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{true},{\sigma }_1⟩\rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩}{\rho ⊢⟨\text{if}{e}_1\text{then}{e}_2\text{else}{e}_3,\sigma ⟩\Downarrow ⟨v,{\sigma }_2⟩}(\text{E-If-True})$$

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{false},{\sigma }_1⟩\rho ⊢⟨e_3,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩}{\rho ⊢⟨\text{if}{e}_1\text{then}{e}_2\text{else}{e}_3,\sigma ⟩\Downarrow ⟨v,{\sigma }_2⟩}(\text{E-If-False})$$

The condition threads its store into the branch, and the branch hands the store out; a write the condition makes is in place when the branch runs, and a write the branch makes is what the whole if leaves behind. The value the if yields is the branch’s value, which is what lets it stand where a value is wanted:

let n = if x > 0 { x } else { -x };

Because the whole form has one value, its two branches have to agree on a type — the result is the value of one branch or the other, and one form carries one type. That agreement is a typing rule, checked before the program runs; it is the subject of the type checker, and the evaluator here runs whichever branch the condition selects without consulting it.

An if may drop its else:

if x > 0 { print(x) };

runs its branch when the condition holds and does nothing when it does not. The form still has a value on both paths, so the missing branch has to supply one, and the only value the language can supply without a branch to evaluate is (). An else-less if reads as if e1 then e2 else () and is admitted only when its branch is itself ()-valued, so that both paths agree; a one-armed if whose branch produced an Int would have no matching value to give when the condition is false. Chained conditions are the else holding another if, if c1 { … } else if c2 { … } else { … }, which the grammar reads as an if in the else position rather than a new form.

Building it

if is one arm of eval_expr, matching the provided Expr::If node — a condition, a then-branch, and an Option for the else-branch that is absent in the one-armed form:

Expr::If(Box<Expr>, Box<Expr>, Option<Box<Expr>>, Span)

The two E-If rules say what the arm does: evaluate the condition, and on a Value::Bool evaluate the branch that boolean selects, leaving the other unevaluated; when the else-branch is absent and the condition is false, the value is Value::Unit. A condition that evaluates to anything but a boolean is a runtime type error, the conditional’s stuck case, ruled out ahead of time once the type checker of Part VI is in place.

Repeating an action: while

Repetition began as an arrangement of jumps. Early machine code and Fortran repeated work by testing a value and jumping back to a label with GO TO; the loop existed in how the jumps were placed rather than as a form the language named, and Fortran’s counting DO was the one repeat given a construct of its own. Structured programming replaced the placed jumps with constructs that control enters and leaves at a single point, so the repeat becomes a form in the grammar: the while that tests a condition and runs its body again as long as the condition holds. Dijkstra (1968) argued for retiring the GO TO in favor of such constructs, and Böhm and Jacopini (1966) had shown that sequence, selection, and iteration alone express any flowchart, so a language with if and while can describe any control a program of jumps could. Bridger’s while is that structured loop.

while needs the mutation of the previous chapter to do anything. Its condition is evaluated afresh each time around, and a re-evaluation can give a different answer only if something the condition reads has changed; without a store to change, a while whose condition starts true stays true and never stops, and one that starts false never runs. Ordering mutation before the loop is what lets the loop’s body move the condition toward false — a counter the body steps, a total it adds into, a list it shortens.

Two rules define it. When the condition is false the loop stops, yielding () and the store the condition produced:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{false},{\sigma }_1⟩}{\rho ⊢⟨\text{while}{e}_1{e}_2,\sigma ⟩\Downarrow ⟨(),{\sigma }_1⟩}(\text{E-While-False})$$

When it is true the loop runs the body, discards the body’s value, and then runs the same while again against the store the body left:

$$\frac{\begin{array}{c}\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{true},{\sigma }_1⟩\\ \rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩\\ \rho ⊢⟨\text{while}{e}_1{e}_2,{\sigma }_2⟩\Downarrow ⟨(),{\sigma }_3⟩\end{array}}{\rho ⊢⟨\text{while}{e}_1{e}_2,\sigma ,⟩\Downarrow ⟨(),{\sigma }_3⟩}(\text{E-While-True})$$

The third premise is a derivation of the very form the rule concludes. Every rule up to here broke a form into strictly smaller parts, and a derivation bottomed out when the parts were literals; this one names its own conclusion among its premises, and the store is what makes the naming finite. Each turn of the loop derives the next against a store the body has moved, and a run that reaches a false condition is a finite stack of E-While-True closed at the top by E-While-False. A loop whose condition never becomes false has no such finite stack — and so no derivation, and no value — which is the rule’s way of saying that a loop that never stops computes nothing to hand back. The store carries the difference between the two cases.

The counter the previous chapter allocated is what a while drives:

let counter = ref 0;
while deref counter < 3 {
  counter := deref counter + 1
};
deref counter                  // 3

counter holds a cell starting at 0. Each turn reads the cell, and while it is below 3 the body writes back one more; the store the body leaves is the store the next condition reads, so deref counter < 3 is true, true, true, false across four evaluations, and the loop stops with the cell at 3. The loop’s own value is (); the result the program wants is in the cell, read out afterward. A while with no cell to move — while true { } — matches only E-While-True, forever, and has no derivation.

Building it

The while arm matches the provided Expr::While node, a condition and a body:

Expr::While(Box<Expr>, Box<Expr>, Span)

The recursion the rule expresses as a repeated premise, the interpreter can express as a loop of its own: it need not call itself to run the next turn, since a host loop re-evaluates the condition and body in place, threading the one store on the interpreter exactly as the rule threads $\sigma$. The body’s value is evaluated and dropped, matching the rule’s discard of $v$, and the loop yields Value::Unit. A return reached in the body leaves the host loop at once — the interpreter carries it on the same Control channel it uses for an error, so the remaining turns do not run, the reference’s convention that a return abandons the whole while. That returning outcome is the subject of a later section.

Walking a list: for

A while repeats until a condition falls; a for repeats once for each element of a collection. Bridger’s for walks a list — the values written [1, 2, 3] and built with ::, introduced with the other compound values in Part II. A list there had no way to read its elements back out: there is no xs[i] and no xs.0, by design. for is the form that reads them, taking each element in turn and binding a name to it for the body:

let total = ref 0;
for x in [1, 2, 3] {
  total := deref total + x
};
deref total                    // 6

for evaluates the iterable to a list value, then walks it. The walk is two rules over the list’s structure — an empty list, and a cons of a head and a tail — with the evaluated list standing in the in position as the walk proceeds:

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v_{list},{\sigma }_1⟩\rho ⊢⟨\text{for}x\text{in}{v}_{list}{e}_b,{\sigma }_1⟩\Downarrow ⟨(),{\sigma }^{\prime }⟩}{\rho ⊢⟨\text{for}x\text{in}e{e}_b,\sigma ⟩\Downarrow ⟨(),{\sigma }^{\prime }⟩}(\text{E-For})$$

$$\frac{}{\rho ⊢⟨\text{for}x\text{in}[]e_b,\sigma ⟩\Downarrow ⟨(),\sigma ⟩}(\text{E-For-Nil})$$

$$\frac{\rho [x\mapsto v_h]⊢⟨e_b,\sigma ⟩\Downarrow ⟨v,{\sigma }_1⟩\rho ⊢⟨\text{for}x\text{in}{v}_t{e}_b,{\sigma }_1⟩\Downarrow ⟨(),{\sigma }_2⟩}{\rho ⊢⟨\text{for}x\text{in}(v_h::v_t)e_b,\sigma ⟩\Downarrow ⟨(),{\sigma }_2⟩}(\text{E-For-Cons})$$

An empty list runs the body no times. A cons binds x to the head, runs the body against the incoming store and discards its value, then walks the tail against the store the body left. The binding of x is fresh on each turn and belongs to the body alone; it is not a cell, so writing x := … is not how a for accumulates. To carry a result across the turns, the body writes a cell that outlives the loop — total in the example — the same division of labor as while: the loop supplies the repetition, the store supplies the memory. Like while, the whole for yields (), a return in the body abandons the rest of the walk, and a for over a value that is not a list is stuck.

Because the list is finite and the walk shortens it by one each turn, a for over a list always stops — the property while gives up in exchange for looping on an arbitrary condition. The one other thing a Bridger program walks is the set of solutions to a relational query, written for q { … }; that form belongs with the relations of Part VII, where the queries it draws from are defined.

Building it

The for arm matches the provided Expr::For node — the bound name, the iterable, and the body:

Expr::For(Name, Box<Expr>, Box<Expr>, Span)

The three E-For rules describe the walk: evaluate the iterable, require a list, and for each element extend the environment with a fresh binding of the name before running the body against the current store, the body’s value discarded each turn. An iterable that is not a list is the stuck case — there are no cells to walk. The per-element binding extends the environment without disturbing the outer one, so the name is in scope for the body and gone after, and the whole for yields Value::Unit. The relational Expr::ForQuery node is the second walk, filled in with Part VII.

Leaving early: return

The forms so far hand their value to the expression around them: an if gives its branch’s value to whatever holds the if, and a block gives its trailing expression’s value to its surroundings. return e sends its value the other way. It evaluates e and carries the value out — past the rest of the block, past the turns of a loop still to come — to the boundary of the function that encloses it, which takes that value as its result. Its rule is the one place evaluation in this part produces something other than an ordinary value: a returning outcome, written $\mathsf{Ret}v$, that the surrounding forms pass along instead of continuing past.

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v,{\sigma }^{\prime }⟩}{\rho ⊢⟨\text{return}e,\sigma ⟩\Downarrow ⟨\mathsf{Ret}v,{\sigma }^{\prime }⟩}(\text{E-Return})$$

Every other rule reads as it did, under one added convention: a premise that yields $\mathsf{Ret}v$ makes its own rule yield that same $\mathsf{Ret}v$, so a returning outcome travels outward on its own. This is what the loop rules meant in saying a return in the body abandons the loop — the body’s premise yields $\mathsf{Ret}v$, the loop yields it in turn, and the iterations that would have followed never run. The interpreter already carries such an outcome: the Control channel eval returns for an error is the one a return rides, which is why the ? in the loop arms above carries a return straight out of the host loop.

A return leaves the enclosing function, the subject of Part V; this chapter shows the returning outcome travelling out through the loops and blocks in its way, and that part supplies the function boundary that catches it and the calls that make an early exit worth writing. That a return stands inside a function at all is checked before the program runs — a return with none to leave is a static error rather than a value the evaluator computes.

The design space

Two decisions show through the forms of this chapter: what a conditional yields, and which loops a language provides.

Because Bridger’s if is an expression, its branches must agree on a type and a one-armed if is confined to (). A language whose if is a statement asks nothing of its branches, since the form yields nothing on either path; C and Java take that route and then add a second conditional, the operator c ? a : b, for the places a value is wanted — the split the first chapter of this part followed. The choice is whether one form serves both jobs, at the cost of the branch agreement, or two forms divide them, at the cost of carrying the conditional twice.

Loops vary more. C offers while, a do/while that tests after running the body once, and the three-part for (init; cond; step) that gathers a counter’s setup, test, and update into a header. Python and Rust make for a walk over an iterator — any value that yields elements on demand — and lean on it for counting too, over a range. Bridger provides while and a for that walks a list. while is the general loop: it repeats on any condition and can run without end, and the other shapes are while with state arranged around it — a counting loop steps a ref the body updates, a test-at-bottom loop runs its body before the first test. Bridger’s for names the one arrangement of walking a list’s elements, and it is bounded where while is not, stopping when the list runs out. What it does not do is walk an arbitrary producer the way an iterator protocol does; that generality rests on the traits and closures of later parts, while a list is the concrete sequence already in hand.

Beyond running to its end, a loop leaves only by the return of the previous section, which carries a value out past the loop and out of the enclosing function. There is no break to leave a loop early and no continue to skip to the next turn; a loop that must stop before its natural end folds that into its own condition, with a cell to signal it where the test alone will not do. The loops are kept to the two rules apiece that define them, and the state a program already has does the rest.

Structured control is one answer to the jump: name the loop and the branch as forms, and build a program from them. Another tradition answers the jump, the loop, and the branch together, by making none of them a primitive. Its programs compute by applying functions: repetition is a function that calls itself, so iteration becomes recursion; selection is an expression that evaluates one subexpression or another; and nothing jumps, since control travels where a call goes and resumes where the call returns. In the most reduced form of that tradition — the lambda calculus, whose notation Lisp borrowed — the function is the only construct, and the loop and the branch alike are things a program expresses with it rather than forms the language hands it. Bridger offers both answers: the conditionals and loops of this part, and the functions and recursion of Part V, with a program free to keep to either. return sits on the structured side of that line — a function in the recursive style has nowhere to jump out to, since its value is the expression it evaluates.

Further reading

Structured control flow: Edsger Dijkstra’s letter “Go To Statement Considered Harmful” (Communications of the ACM, 1968) makes the case for control constructs that are entered and left at one point, the shape Bridger’s if and while take, in place of the jump. Corrado Böhm and Giuseppe Jacopini’s “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” (Communications of the ACM, 1966) proves that sequence, selection, and iteration suffice to express any flowchart, so the loss of the general jump costs a language no control it could otherwise have.

Iteration constructs: CLU introduced the iterator, a for that draws successive values from a separate producer rather than from a stored collection, described in Barbara Liskov and colleagues’ “Abstraction Mechanisms in CLU” (Communications of the ACM, 1977); it is the arrangement Python’s and Rust’s for follow. The Rust Reference sets out the loop, while, and iterator-for that Bridger’s two loops are drawn from and pared against.

Concept checks