Control flow

01 · SEQUENCE

Sequence: one thing after another

The simplest flow is a straight line. Each statement runs once, in order, and each one sees the world the one before it left behind. On the stage, the token passes under four arches, and the chip above it shows x changing: 5, then 6, then 12.

let x = 5;
x = x + 1;       // x is now 6
x = x * 2;       // x is now 12
console.log(x);

Order matters. The same two steps, swapped, give a different answer, because x is a different number by the time each one runs:

// The same two steps, in the other order.
let x = 5;
x = x * 2;       // 10
x = x + 1;       // 11
console.log(x);

02 · IF / ELSE

if / else: choosing a track

An if statement asks a yes-or-no question and picks a track. If the condition is true the token takes the first branch; if not, it goes on to the else. Chain else ifs for more choices: they are tried top to bottom, and the first true one wins. Everything after it is skipped.

On the stage the program runs three times, with t at 30, 20 and 5. Watch the first switch go green for 30, red then green for 20, and red twice for 5. All three tracks meet again before console.log: an if splits the flow, and the flow rejoins after it.

const t = 30;     // try 20, then 5
let msg;
​
if (t > 25) {
  msg = "hot";
} else if (t > 15) {
  msg = "mild";
} else {
  msg = "cold";
}
​
console.log(msg);

The condition can be anything that gives true or false. Comparisons are the usual source:

console.log(3 > 2);          // true
console.log(3 === 3);        // true: same type and value
console.log(3 === "3");      // false: number vs text
console.log(3 == "3");       // true: == converts first (avoid it)
console.log("apple" < "banana");  // true: compared letter by letter
console.log(0.1 + 0.2 === 0.3);   // false! (chapter 2 says why)

03 · && AND ||

Boolean logic: && , || and !

Questions combine. AND (&&) is true only when both sides are true. OR (||) is true when at least one side is. NOT (!) flips true and false. A truth table lists every combination; there are only four for two inputs, and the board at the back of the stage lights the row being tested.

for (const a of [true, false]) {
  for (const b of [true, false]) {
    console.log(a, b, "  AND:", a && b, "  OR:", a || b, "  NOT a:", !a);
  }
}

Now watch the two layouts closely. The AND gate is two switches in a row: the token reaches B only if A was true. The OR gate is two switches side by side: if A is true, there's already a way through, and B is never asked. When a switch is skipped, its sign dims and says so.

That is short-circuit evaluation: JavaScript stops as soon as it knows the answer, and doesn't even run the right-hand side. This is in the language specification, not an optimisation you hope for, so you can rely on it:

function check(name, value) {
  console.log("  checking", name);
  return value;
}
​
console.log("A && B, with A false:");
console.log(check("A", false) && check("B", true));
​
console.log("A || B, with A true:");
console.log(check("A", true) || check("B", true));

The everyday use is a guard: check that something exists before you look inside it.

const user = null;
​
// Without the guard, user.name would throw a TypeError.
if (user !== null && user.name === "Ada") {
  console.log("Hello, Ada");
} else {
  console.log("no user, and no crash");
}
​
// The modern shortcuts built on the same idea:
console.log(user?.name);           // undefined, not a crash
console.log(user?.name ?? "guest"); // "guest"

JavaScript is relaxed about what counts as a condition. Any value can go in an if; it is converted to true or false. The values that count as false are called falsy, and there are only a handful. Everything else, including "0" and empty arrays, is truthy:

const things = [0, 1, -5, "", "0", "hi", null, undefined, NaN, [], {}];
​
for (const v of things) {
  const shown = typeof v === "string" ? JSON.stringify(v) : Array.isArray(v) ? "[]" : String(v) === "[object Object]" ? "{}" : String(v);
  console.log(shown.padEnd(10), Boolean(v) ? "truthy" : "falsy");
}

04 · SWITCH

switch: one question, many tracks

When you compare one value against a list of options, a switch reads better than a long else if chain. It works out the value once, then jumps to the case that matches it with ===, or to default if none does. On the stage a turntable swings to the right lane.

The catch: a case doesn't end on its own. Execution carries on into the next case's code until it hits a break. This is called fall-through. Watch "amber": its lane has no code and no break, so the track runs straight into the red lane and the token does what red does. Used on purpose, that's a neat way to share code.

function act(light) {
  let action;
  switch (light) {
    case "green":
      action = "go";
      break;
    case "amber":          // no break: falls through...
    case "red":
      action = "stop";      // ...into here
      break;
    default:
      action = "?";
  }
  return action;
}
​
for (const light of ["green", "amber", "red", "blue"]) {
  console.log(light, "→", act(light));
}

Used by accident, it's a classic bug. Predict the output before you run it:

const light = "green";
switch (light) {
  case "green":
    console.log("go");
    // oops: no break
  case "red":
    console.log("stop");
}

Newer languages learned from this. Go and Swift stop at the end of each case unless you write fallthrough; Python added match in version 3.10 with no fall-through at all:

t = 30
if t > 25:
    msg = "hot"
elif t > 15:
    msg = "mild"
else:
    msg = "cold"
 
for i in range(3):        # 0, 1, 2: the end is excluded
    print(i)
 
match msg:                # Python 3.10+: no fall-through
    case "hot" | "mild":
        print("go outside")
    case _:
        print("stay in")

05 · LOOPS

Loops: tracks that bend back

A loop is a decision at the top of a track that bends back to it. Each time round is called an iteration (or a lap). The for loop puts the three parts on one line: the start (let i = 0), the test asked before every lap (i < 3), and the update after every lap (i++). On the stage, the token passes the start once, then circles: test, body, update, back along the violet track. When the test turns red it leaves on the exit track.

for (let i = 0; i < 3; i++) {
  console.log("lap", i);
}
console.log("done");

A while loop is the same machine with only the test on top. Use it when you don't know in advance how many laps it will take:

// Halve a number until it's small. We don't know
// in advance how many laps that takes: a job for while.
let n = 100;
let laps = 0;
while (n >= 1) {
  n = n / 2;
  laps++;
}
console.log(laps, "halvings to get below 1");

Most of the time you just want each item of a list. for…of hands you the items one at a time, so there's no counter to get wrong. The crates at the back of the stage light up one per lap:

const items = ["a", "b", "c"];
​
for (const x of items) {
  console.log(x);
}
​
// for...of works on anything iterable: strings too.
for (const ch of "hey") {
  console.log(ch);
}

do…while puts the test at the bottom, so the body always runs at least once:

let tries = 0;
let roll;
do {
  roll = (tries * 7 + 3) % 6 + 1;   // a pretend dice roll
  tries++;
} while (roll !== 6);
console.log("got a 6 after", tries, "tries");

06 · BREAK · CONTINUE

break and continue: leaving early

Two words change a loop's track from inside. break leaves the loop at once, onto the exit (the pink track). continue abandons the rest of this lap and goes straight back to the top for the next one (the short violet track).

On the stage, the loop walks through [3, 8, -1, 7]. 3 is odd, so it's added. 8 is even: continue sends the token back before the addition. -1 is negative: break leaves the loop, so 7 is never even looked at. The sum is 3.

const nums = [3, 8, -1, 7];
let sum = 0;
​
for (const x of nums) {
  if (x < 0) break;          // stop the whole loop
  if (x % 2 === 0) continue; // skip to the next lap
  sum += x;
}
​
console.log(sum);   // 3: 8 was skipped, and we never reached 7

break only leaves the innermost loop. To leave an outer one from inside an inner one, give the outer loop a label:

// A label lets break leave an outer loop too.
const grid = [[1, 2], [3, 99], [5, 6]];
​
search:
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[r].length; c++) {
    if (grid[r][c] === 99) {
      console.log("found at", r, c);
      break search;
    }
  }
}

07 · NESTED LOOPS

Nested loops: a loop on every lap

A loop body can contain anything, including another loop. The inner loop then runs all of its laps on every lap of the outer one. On the stage the inner ring spins three times for each trip round the outer ring, and the grid fills in row by row: a times table.

for (let r = 0; r < 3; r++) {
  let row = "";
  for (let c = 0; c < 3; c++) {
    row += String((r + 1) * (c + 1)).padStart(3);
  }
  console.log(row);
}

That multiplication is the thing to remember. An outer loop of n laps around an inner loop of n laps does n × n steps. Ten items is a hundred steps; a thousand items is a million:

// How much work is a loop inside a loop?
for (const n of [10, 100, 1000]) {
  let steps = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      steps++;
    }
  }
  console.log(n, "items →", steps, "inner steps");
}

This is the first taste of Big-O: work that grows like n² is fine for small lists and painful for big ones. Chapter 6 is all about it.

08 · OFF BY ONE

Off by one: the most common loop bug

Arrays count from 0. An array of length 5 has slots 0, 1, 2, 3 and 4, and no slot 5. Write the test as i <= arr.length and the loop takes one lap too many. On the stage the token runs the buggy loop first: the sixth lap reaches for the slot that isn't there and gets undefined. Then it runs again with <, and stops after five.

const arr = [10, 20, 30, 40, 50];
​
for (let i = 0; i <= arr.length; i++) {
  console.log(i, arr[i]);
}

Its old name is the fencepost error: a 100 m fence with a post every 10 m has 10 sections but 11 posts. Counting the gaps when you meant the posts, or the other way round, is the same mistake.

// A 100 m fence with a post every 10 m: how many posts?
const length = 100, gap = 10;
console.log("sections:", length / gap);      // 10
console.log("posts:", length / gap + 1);     // 11, not 10
​
// Half-open ranges avoid the +1: start included, end excluded.
let count = 0;
for (let i = 3; i < 8; i++) count++;
console.log("3 up to (not incl.) 8 →", count, "= 8 - 3");

09 · LOOP VS RECURSION

Iteration vs recursion: a preview

There's a second way to repeat: a function that calls itself with a smaller problem, until the problem is so small the answer is obvious (the base case). That is recursion. On the stage the left token loops round a ring; the right token goes down a staircase. Each step down is a new call with its own copy of n, stacked on top of the one that called it. At countdown(0) it hits the base case, then climbs back up through every waiting call.

// The same countdown, two ways.
function countdownLoop(n) {
  while (n > 0) {
    console.log(n);
    n--;
  }
}
​
function countdown(n) {
  if (n === 0) return;     // the base case: stop
  console.log(n);
  countdown(n - 1);        // the same job, a bit smaller
}
​
countdownLoop(3);
countdown(3);

Both print 3, 2, 1. The loop needs one variable, however many laps it runs. The recursion needs a stack frame per waiting call, and the stack has a limit:

function depth(n) {
  return n === 0 ? 0 : 1 + depth(n - 1);
}
​
console.log(depth(1000));          // fine
try {
  depth(1e6);                       // a million frames
} catch (e) {
  console.log(e.name + ": " + e.message);
}

Recursion shines when the data itself is shaped like a tree (folders inside folders, the parse tree from chapter 1), where a loop would need you to manage a stack by hand. Some languages turn a call in "tail position" into a jump, so it costs no stack. The JavaScript standard has required that since 2015, but Safari is the only major browser that does it. Chapter 4 takes the call stack apart properly.

10 · FLOW GRAPH

The control-flow graph

Strip the railway down to its junctions and you get the tool compilers actually use: the control-flow graph. Cut the code into basic blocks, straight runs of statements with one way in (at the top) and one way out (at the bottom). Then draw an arrow for every way control can pass from one block to another. A condition has two arrows out, labelled T and F. A loop shows up as a back edge: an arrow to a block that came earlier.

let sum = 0;
for (let i = 1; i <= 4; i++) {
  if (i % 2 === 0) {
    sum += i;
  }
}
console.log(sum);

On the stage this program becomes six blocks. B0 sets up; B1 is the loop test; B2 is the if; B3 adds; B4 is i++, with the back edge to B1; B5 prints. The token takes the F arrow from B2 on odd laps and the T arrow on even ones, and leaves along B1's F arrow when i reaches 5. It prints 6.

let sum = 0;
for (let i = 1; i <= 4; i++) {
  if (i % 2 === 0) {
    sum += i;
  }
}
console.log(sum);

Every layout in this chapter was a control-flow graph in disguise. Compilers use them to find code that can never run, to spot variables used before they're set, and to find loops to speed up.

11 · JUMPS IN THE CPU

Down in the CPU: every branch is a jump

A processor knows nothing about if, while or switch. It has a program counter (PC) holding the address of the next instruction, and by default the PC just moves on to the next one: sequence. Control flow is done with jumps, instructions that load a new address into the PC. A conditional jump does that only if a condition holds; otherwise the PC carries on as usual.

Here is a C loop and roughly what a compiler turns it into on x86-64. The compiler flipped the test: "keep going while i < 3" became "jump out if i >= 3". cmp subtracts and sets flags; jge reads them. On the stage the PC token rides down the instructions, leaps back along jmp loop three times, and finally takes jge done.

#include <stdio.h>
 
int main(void) {
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        sum += i;
    }
    printf("%d\n", sum);
    return 0;
}

        mov  ecx, 0          ; i = 0
        mov  eax, 0          ; sum = 0
loop:   cmp  ecx, 3          ; compare i with 3 (sets flags)
        jge  done            ; if i >= 3, jump out
        add  eax, ecx        ; sum += i
        inc  ecx             ; i++
        jmp  loop            ; back to the test
done:   ret                  ; the answer is in eax

You can build this in a few lines. Here is chapter 1's stack machine with a JMP and a JZ (jump if zero) added. A loop is nothing more than pc = an earlier number:

// Chapter 1's stack machine, plus three jumps.
// JMP n: go to instruction n.  JZ n: pop; if it was 0, go to n.
const program = [
  "PUSH 3",     // 0  n = 3
  "DUP",        // 1  loop: copy n
  "JZ 7",       // 2  if n is 0, jump to the end
  "DUP",        // 3
  "PRINT",      // 4  print n
  "DEC",        // 5  n = n - 1
  "JMP 1",      // 6  back to the test
  "HALT",       // 7
];
const stack = [];
let pc = 0;
let steps = 0;
​
while (steps++ < 100) {
  const [op, arg] = program[pc].split(" ");
  pc++;                                    // by default: the next one
  if (op === "PUSH") stack.push(Number(arg));
  if (op === "DUP") stack.push(stack[stack.length - 1]);
  if (op === "DEC") stack.push(stack.pop() - 1);
  if (op === "PRINT") console.log(stack.pop());
  if (op === "JMP") pc = Number(arg);      // jump: just change pc
  if (op === "JZ" && stack.pop() === 0) pc = Number(arg);
  if (op === "HALT") break;
}

Branch prediction

A modern core works on many instructions at once, in a pipeline, so it has to fetch the instructions after a branch before it knows which way the branch goes. It doesn't wait: it guesses, and carries on along that path. Guess right and nothing is lost. Guess wrong and all the work on the wrong path is thrown away and the pipeline refills: on recent Intel and AMD cores, that costs about 15 to 20 clock cycles.

The simplest good predictor is the 2-bit saturating counter on the right of the board. Each taken branch moves it one step up, each not-taken one step down, and the top two states predict "taken". Watch it with jge: three times not taken (correct guesses), then taken, which it gets wrong: a flush. Real CPUs combine many such counters with the history of recent branches, and get the great majority right.

// A 2-bit saturating counter: 0,1 predict "not taken"; 2,3 predict "taken".
function mispredictions(outcomes) {
  let state = 1, misses = 0;
  for (const taken of outcomes) {
    const guess = state >= 2;
    if (guess !== taken) misses++;
    state = taken ? Math.min(3, state + 1) : Math.max(0, state - 1);
  }
  return misses;
}
​
// A tiny repeatable random number generator, so every run is the same.
let seed = 42;
const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
​
const data = Array.from({ length: 10000 }, () => Math.floor(rand() * 256));
const sorted = [...data].sort((a, b) => a - b);
​
// The branch inside the loop: if (x >= 128)
const branch = (arr) => arr.map((x) => x >= 128);
​
console.log("random order:", mispredictions(branch(data)), "misses in 10000");
console.log("sorted order:", mispredictions(branch(sorted)), "misses in 10000");

Compilers and careful programmers sometimes remove the branch altogether, turning the decision into arithmetic. No jump, nothing to mispredict:

// The same sum with no branch at all: turn the test into arithmetic.
const data = [200, 13, 150, 99, 128, 255, 0];
​
let a = 0;
for (const x of data) {
  if (x >= 128) a += x;           // a branch
}
​
let b = 0;
for (const x of data) {
  const keep = -(x >= 128);       // true → -1 (all bits 1), false → 0
  b += x & keep;                  // x, or 0: no jump needed
}
​
console.log(a, b);

To watch a CPU fetch, decode and execute instructions one clock at a time, open Inside the CPU.

// Mini project: a robot on a grid.
// F = forward, L = turn left, R = turn right. Walls stop it.
const map = [
  "#######",
  "#.....#",
  "#.###.#",
  "#...#.#",
  "#######",
];
const commands = "RFFLFFF";      // try your own
​
let x = 1, y = 1, dir = 0;            // 0 east, 1 south, 2 west, 3 north
const DX = [1, 0, -1, 0], DY = [0, 1, 0, -1];
​
for (const c of commands) {
  switch (c) {
    case "L": dir = (dir + 3) % 4; break;
    case "R": dir = (dir + 1) % 4; break;
    case "F": {
      const nx = x + DX[dir], ny = y + DY[dir];
      if (map[ny][nx] === "#") {
        console.log("bump at", nx, ny);
        continue;
      }
      x = nx; y = ny;
      break;
    }
    default:
      console.log("unknown command", c);
  }
}
console.log("ended at", x, y);