Loops and invariants

Deciding between two branches is a real advance, but a fork is taken once, and a great many tasks need the same work done an unknown number of times.

The previous lesson built conditions out of comparisons: age >= 18 produces a boolean, and if acts on it. A loop uses the same kind of condition for a different purpose, asking it again and again. If you have arrived here directly, the only things assumed are that let binds a name that can be rebound and that a condition in brackets is a boolean test.

Saying it once and doing it many times

The simplest loop is while. It takes a condition and a block, and it runs the block over and over for as long as the condition holds:

let i = 1;
while (i <= 5) {
  console.log(i);
  i = i + 1;
}
// 1 2 3 4 5, one per line

Three parts are doing the work, and every loop you ever write will have all three even when the syntax hides them. There is an initialisation, let i = 1, which sets the state up before the first pass. There is a condition, i <= 5, tested before each pass, so a loop whose condition is false at the start runs zero times. And there is an update, i = i + 1, which changes the state so that a later test can fail.

Leave the update out and the condition stays true forever, which is the beginner's infinite loop, and it is worth causing one deliberately in a console so you know what it looks like. Nothing is printed, nothing crashes, the program simply never returns. That symptom, a program that hangs rather than failing, almost always means a loop whose state is not changing.

The variant do { ... } while (cond); tests after the body instead of before, so it always runs at least once. It is occasionally the right shape, for reading input until it validates, and it is rare enough that most codebases contain none.

The accumulator

Printing in a loop is the least interesting thing to do in one. The pattern that actually earns its keep is the accumulator: a name declared outside the loop, updated on every pass, and read after it finishes.

let total = 0;
let i = 1;
while (i <= 100) {
  total = total + i;
  i = i + 1;
}
console.log(total);
// 5050

The declaration has to be outside. A name declared inside the block is created fresh on each pass and destroyed at the end of it, so the sum would be thrown away every time. The starting value has to be the identity for the operation you are accumulating: 0 for a sum, 1 for a product, "" for building a string. Start a product at 0 and the answer is 0 whatever the data.

That result is checkable without a machine, which is the point of using it as the first example: the sum of the first $n$ whole numbers is $n(n+1)/2$, so for 100 it is $100\times 101/2=5050$. A loop you can check against a closed form is a loop you can trust, and it is worth reaching for such a case whenever you are unsure whether your loop is right.

for, and counting from zero

The while above spread its three parts over four lines, with the update at the bottom where it is easy to forget. for collects them into one line:

let total = 0;
for (let i = 1; i <= 100; i = i + 1) {
  total = total + i;
}

Initialisation, condition, update, separated by semicolons and in that order. It is the same loop, and i = i + 1 is usually written i++, which means the same thing here. Using let inside the for header also scopes i to the loop, so it does not leak into the code after it.

Now a convention that looks arbitrary and is not. Loops over data are written to start at 0 and use a strict <:

for (let i = 0; i < n; i++) { ... }

The reasons are worth stating, because this shape is everywhere and you should know why rather than copying it. The count of passes is n, readable straight off the header with no arithmetic. The bounds are half open, 0 <= i < n, so two adjacent ranges join without a gap or an overlap: 0 to n and n to m cover everything exactly once. And it matches how arrays are indexed in the next lesson, where the first element is at position 0 and the last is at n - 1. Edsger Dijkstra wrote the classic note on this in 1982, and the argument has held: half open ranges starting at zero produce fewer off-by-one errors than any alternative.

Example. How many times does the body of for (let i = 3; i < 12; i += 2) run, and what is the value of i afterwards?

i takes the values 3, 5, 7, 9, 11, and then 13, which fails the test. So the body runs five times. In general a loop from a while i < b stepping by s runs $\lceil (b-a)/s\rceil$ times, here $\lceil 9/2\rceil =5$. Afterwards i is 13, one step past the last value used, which is the value that failed the condition.

Now you. How many times does the body of for (let i = 0; i <= 20; i += 4) run, and what is i at the end?

What makes a loop correct

A loop can be traced by hand for small inputs, and that is a useful thing to do, but it is not an argument that the loop is right. Tracing three cases tells you about three cases. The argument that covers all of them is the loop invariant: a claim about the state that is true before the loop starts, stays true across every pass, and is strong enough at the end to give you what you wanted.

For the sum above, the invariant is: before each test of the condition, total holds the sum of the whole numbers from 1 up to i - 1.

The argument has three parts, and it is the same three every time. Establishment: before the first test, total is 0 and i is 1, so the claim says the sum from 1 to 0 is 0, which is true of an empty sum. Maintenance: assume it holds at the top of a pass, so total is the sum to i - 1. The body adds i and increments, giving the sum to i with the new i one larger, so the claim holds at the next test. Termination: the loop ends when i <= 100 is false, and since i grows by one it fails first at exactly i = 101. Substituting into the invariant, total is the sum from 1 to 100. Which is what was wanted.

This is not academic ceremony. It is the thing to write, in a comment or on paper, when you have a loop that is nearly right and you cannot see why it is not. Almost every incorrect loop is one whose invariant is fine at the top and broken by the body, and the moment you try to state the claim you find the line that breaks it. It is also the only technique in this course that scales to loops too subtle to trace, which in the following courses means binary search and the partition step of quicksort.

Example. State the invariant for this loop and use it to say what p holds at the end.

let p = 1;
for (let k = 1; k <= 10; k++) {
  p = p * k;
}

The invariant is that before each test, p holds the product of the whole numbers from 1 to k - 1. It is established with p = 1 and k = 1, since the empty product is 1. It is maintained because multiplying by k and then incrementing keeps the claim true one step along. The loop ends at k = 11, so p is the product from 1 to 10, which is $10!=3628800$.

Now you. State the invariant for this loop and say what count holds at the end, for n = 30.

let count = 0;
for (let d = 1; d <= n; d++) {
  if (n % d === 0) count++;
}

What makes a loop stop

Correctness and termination are separate arguments, and a loop can have a perfect invariant and still run forever. The termination argument needs a variant: a quantity that is a whole number, that never goes below zero, and that strictly decreases on every pass. Such a quantity cannot decrease forever, so the loop must end.

For for (let i = 0; i < n; i++), the variant is n - i. It starts at n, drops by exactly one per pass, and the loop stops when it reaches zero. That is a complete proof of termination, and for the great majority of loops it is this obvious. Where it stops being obvious is when the update is conditional, or when the bound changes inside the body, and those are exactly the loops that hang.

Be honest about the limit here, because it is a real one. Not every loop has a known variant. The Collatz loop is the standard example: start with any positive whole number, halve it if it is even, otherwise triple it and add one, and repeat until it reaches 1.

let n = 27;
let steps = 0;
while (n !== 1) {
  n = n % 2 === 0 ? n / 2 : 3 * n + 1;
  steps++;
}
console.log(steps);
// 111

Starting from 27 that takes 111 steps and climbs as high as 9232 on the way, which is not the behaviour of a quantity that decreases. Nobody has proved that this loop terminates for every starting value. It has been checked by computer for every start below about $2.95\times {10}^{20}$, a result of David Barina published in 2020, and it stopped every time, but a check is not a proof and the problem has been open since Lothar Collatz posed it in 1937. So "I ran it and it finished" is genuinely not the same claim as "it terminates", and knowing the difference is what stops you shipping a loop that hangs on the one input you did not try.

Off by one, in both directions

The commonest loop bug in any language is the off-by-one, and it comes in two flavours that are worth being able to name.

The first is the wrong comparison: writing <= where < was meant, or the reverse. for (let i = 0; i <= n; i++) runs n + 1 times, and when the body reads position i of something with n items, the last pass reads a position that does not exist. The second is the fencepost error, named for the observation that a straight fence 100 metres long with a post every 10 metres needs 11 posts and not 10. Counting the gaps when you meant the posts, or the other way around, is the same mistake as counting iterations when you meant boundaries.

There is a third that is specific to arithmetic and catches everybody once. Do not step a loop by a fraction:

let steps = 0;
for (let x = 0; x < 1; x += 0.1) {
  steps++;
}
console.log(steps);
// 11

Eleven, not ten. The previous lesson showed that 0.1 is not exactly a tenth, and ten of those slightly-off tenths add to 0.9999999999999999, which is still less than 1, so the body runs one extra time. Loop over whole numbers and compute the fraction inside: for (let k = 0; k < 10; k++) { const x = k / 10; ... }. The count is then exact by construction.

The general defence against all three is the same. Check the boundaries rather than the middle. Ask what happens on the first pass and the last, and what happens when the input is empty or has one element. That is where loops are wrong, and it is almost never in the middle.

Leaving early

Two statements interrupt the normal flow. break leaves the loop immediately, and continue skips the rest of the current pass and goes to the next test. break is the natural way to write a search that stops when it finds what it wanted:

function isPrime(n) {
  if (n < 2) return false;
  for (let d = 2; d * d <= n; d++) {
    if (n % d === 0) return false;
  }
  return true;
}

Here return does the leaving, which is even more direct than break. Two details of this loop are worth pulling out. The condition is d * d <= n rather than d <= n, because a divisor above the square root implies a matching one below it, so there is nothing left to find. For n = 97 that means eight trial divisions rather than 95. And the condition is written d * d <= n in preference to d <= Math.sqrt(n), which avoids both a repeated square root and the floating point question of what happens when n is a perfect square.

Both statements come with a caution. continue placed before the update in a while loop skips the update, which turns the loop infinite, and this is a genuinely common bug. In a for loop the update sits in the header and still runs, so the same code is safe there. Where a loop grows several breaks and continues, the honest reading is usually that it is doing two jobs and wants splitting into two.

Example. Rewrite this to leave as soon as the answer is known, and say how many passes it takes for the array [4, 9, 12, 5] looking for the first multiple of 3.

let found = -1;
for (let i = 0; i < values.length; i++) {
  if (values[i] % 3 === 0) found = i;
}

As written it keeps going and records the last match rather than the first, and it always makes n passes. Adding a break after the assignment fixes both: it stops at the first match and leaves found holding its index. For [4, 9, 12, 5] the test fails at index 0 and succeeds at index 1, so it takes two passes and found is 1. Without the break it takes four passes and found is 2.

Now you. How many passes does the isPrime loop make for n = 91, and what does it return?

The same block, with different numbers in it

Loops are where programs start being useful, and they are also where programs start being long. Write a few and a pattern appears: the same seven lines, computing an average or checking a divisor, turn up in three places with different names in them. Copying them is how a fix in one copy fails to reach the other two.

What is needed is a way to name a computation, write it once, and call it wherever it is wanted, with a clear statement of what goes in and what comes out. That is a function, and it is next.