Again and again

The last chapter left us at the grate with the combination lock. The lock can say “too low” or “too high,” but it asks only once: get it wrong, and the quest is over. You can ask again only by copying a piece of the program, and keep asking until the player wins only by copying it without end. This chapter is about making the machine repeat: ten times, a million times, or until something happens.

Here is what repetition looks like without new tools. The program weaves a scrap of checkered cloth on the screen, four rows of it:

Four rows, four lines. A hundred rows, a hundred lines, and not one square may be wrong in any of them. Want the cloth wider? Rewrite all hundred. Two centuries ago the same trouble plagued the weavers of patterned silk, and they got out of it the way we will: they taught a machine to repeat.

Lyon, 1804: a loom that remembers the pattern

Babbage was designing his Analytical Engine at the time, and Ada Lovelace wrote a program for it that computed the Bernoulli numbers, with the bug we took apart in Chapter 1. The engine was to receive its instructions on punched cards, like Jacquard’s loom. In Note A to her translation Lovelace put it this way:

We may say most aptly, that the Analytical Engine weaves algebraical patterns just as the Jacquard-loom weaves flowers and leaves.

A chain of cards closed into a ring is what a programmer would call a loop: the same sequence of instructions carried out again and again. Our loom will be Python, and we will weave patterns out of numbers, characters and lines.

The shuttle runs while… The while loop

Python has two kinds of loop. The first reads almost like an English sentence: “while the condition holds, repeat.” Run the program, then press “Steps” and walk through it line by line: after the fourth line the arrow will jump back to the second.

It is built like the if from the last chapter: a header with a condition and a colon, and an indented block under it. There is one difference. Having run its block, if moves on, whereas while goes back to its condition and checks it again. As long as the condition is true, the block runs again, and again. As soon as it turns false, Python jumps over the block to the first line after it.

This construction is called a loop, the block under the header is the body of the loop, and one pass through the body is an iteration. Here there are three iterations, with throws equal to 3, 2 and 1. When throws reached zero, the condition throws > 0 turned false, and the loop ended.

Lovelace described this before there were machines that could do it. In Note C she explains that the Analytical Engine needs more than a loom’s way of feeding cards, and so a method was devised of “backing” them: the prism the chain hangs on is turned in the opposite direction. That way the same group of cards could be brought into use “any number of times successively.” And in Note E Lovelace gives a definition: “A cycle of operations, then, must be understood to signify any set of operations which is repeated more than once.”

Every while loop has three parts, and it pays to learn to see them from the start: the condition that decides whether to go round again; the work the loop was written for; and the change that brings the end closer. In our shuttle the change is the line throws = throws - 1. Delete it and think about what will happen. Don’t run it yet: the section on the infinite loop shows what becomes of a loop without a change.

The strength of while is that you don’t need to know the number of repetitions in advance. Back to the grate from the last chapter. Now the lock keeps asking for the code until it hears the right one, and after every mistake it gives a hint, as before:

Nobody but the player knows how many times the body of this loop will run: zero times if the code is right on the first try, and any number of times if the player is stubborn. A while loop is what you need when you have to repeat “until” rather than “so many times.” By the way, if you guess cleverly and halve the remaining range every time, as in the game from Chapter 0, any four-digit code opens in at most 14 tries.

Thread by thread: for and range

Often the number of repetitions is known: go over 24 warp threads, print 10 lines, check the numbers from 1 to 1000. For that there is the second loop, for:

It reads like this: “for each throw in range(5), run the body.” There is no counter to set up, increase and check: for puts the next value into the variable throw by itself and stops by itself when the values run out. It looks modest, but with for you can’t make two common while mistakes: forgetting to change the counter and getting the condition wrong.

The five throws in the output are numbered from 0 to 4, not from 1 to 5. That is how range works: range(5) is five numbers, starting from zero. It also has a full form, range(start, stop, step): from start in steps of step until you reach stop. The stop itself is never part of the sequence. Play with the ruler: the red circle marks the boundary the loop never steps on.

Leaving out the boundary is convenient in three ways at once. range(n) holds $n$ numbers, no more and no fewer. range(a, b) holds $b - a$ of them, with no “plus one.” And neighboring pieces join without gaps or overlaps: range(0, 10) and range(10, 20) together make range(0, 20), and the number 10 falls only in the second half. Mathematicians call such a stretch a half-open interval and write it $[a, b)$. The convenience costs one habit: when you need “from 1 to $n$ inclusive,” you write range(1, n + 1). A forgotten + 1 is one of the most common loop mistakes, and it has a name: the off-by-one error.

A for loop can walk over more than numbers. A string is a sequence too, and for goes through it one character at a time:

The new thing here is end=" ". Normally print finishes its text with a line break, and end says what to finish with instead: here, a space. The empty print() at the end puts the line break back. We’ll need it to weave patterns row by row. As for where print gets settings like this, the next chapter will make that clear.

The piggy bank: accumulators

According to a school legend, little Carl Friedrich Gauss added up all the numbers from 1 to 100 in a couple of minutes, although the teacher had hoped to keep the class busy for a long time. Gauss saw how to add them without going through them one by one; the math course explains how. We don’t need his insight: a machine doesn’t care whether there are a hundred terms or a million.

The line total += k is short for total = total + k: “increase total by k.” Here the variable total works as a piggy bank. Variables like this are called accumulators, and their recipe is always the same:

1. before the loop the accumulator gets a starting value: for a sum, zero;
2. in the body of the loop it is updated: the next number is added to it;
3. after the loop it holds the answer.

The starting value depends on what you are accumulating. For a product it is one, or else everything gets multiplied by zero. In how many ways can 25 different books be arranged on a shelf? The first is chosen from 25, the second from 24, and so on, which gives $25 \cdot 24 \cdots 1 = 25!$.

Twenty-six digits, and Python didn’t lose a single one: its whole numbers can be as long as you like. A counter is an accumulator too, except that it adds one, and only when a condition is met. How many numbers from 1 to 1000 are divisible by 7?

A hundred and forty-two. There are accumulators for records as well. The program below reads numbers until you enter zero and remembers the largest; here while and accumulators work together. The record starts out as the first number itself: there is no knowing in advance what numbers to expect, and if they all turn out negative, a record that started at zero would lie.

Cloth: a loop inside a loop

One row of cloth is a loop over the warp threads. Here is a row of 24 squares in which pairs of filled and empty squares take turns:

To get a whole piece of cloth, the row has to be repeated, and repeating is something we can now do: wrap the whole loop over columns in another loop, over rows. This is a nested loop: on every iteration of the outer loop, the inner one runs through all the threads, from first to last. Much as in Jacquard’s loom: the outer loop is the chain of cards, the inner one the needles, each feeling for its own hole in the card. The loom, admittedly, checks all the holes at once, while Python checks them one by one. In Note E Lovelace called this “a cycle that includes a cycle, or a cycle of the second order.”

The loom below works the same way, and its pattern is set by a single condition on the row number row and the thread number col. Press “Weave again” and watch the highlighting in the program: the inner loop runs over every thread of the row, and only then does the outer loop take the next card. Under the cloth is the punched card of the current row.

Try it yourself: what happens if you change the 4 in the stripes to a 3? How do you get horizontal stripes instead of vertical ones? What does row == col draw, and what about col % (row + 1) == 0? Every pattern here is the question “is this square filled?” asked for each pair (row, thread). The button under the loom copies the program into a cell where Python itself runs it:

The inner loop doesn’t have to cover the same ground every time. If its bound depends on the row number, the cloth stops being a rectangle. Here is a staircase where row number row holds row squares:

The same technique works with colored squares in place of characters. The sandbox has a canvas, Canvas: the command rect draws a rectangle with its top left corner at the point $(x, y)$, and the $y$ axis on the canvas points down. The square in row row and column col starts at the point (col * 20, row * 20). Change the condition and the colors (there are p0…p11, ink and paper), add a third branch, and weave a carpet of your own.

A turtle at the loom

Patterns don’t have to sit on a grid of squares. In Chapter 0 a turtle drew a tree. Its commands are simple: turtle.forward(100) means walk 100 steps forward, leaving a trail, and turtle.left(90) means turn left by 90 degrees. A square is “forward and left” four times over:

The first line, import turtle, brings in the module with the turtle, a set of ready-made commands that the language itself lacks. Change 4 to 6 and 90 to 60, and you get a hexagon. Going round a convex polygon, the turtle turns through one full circle in total, so in a regular polygon with $n$ sides each turn is $360 / n$ degrees.

If the angle doesn’t divide 360 evenly, the turtle won’t be back at the start after its first circle. It goes round a second time, a third… and closes the figure only when the sum of its turns is a multiple of 360. An angle of 144° gives a five-pointed star: $5 \cdot 144 = 720$, two full circles. An angle of 89° looks like a right angle, but the turtle gets back to the start only after 360 steps. And if the step grows a little every time, the figure never closes at all.

Nested loops work for the turtle as well. The inner loop draws a square, and the outer one turns the turtle by 10° and repeats the square 36 times, which makes a rosette:

Cutting the thread: break and continue

Sometimes a loop has to stop halfway: what you were looking for has turned up, and there is no point in searching further. For that there is break, which leaves the loop at once, without waiting for the range to run out or the condition to turn false. Here is a search for the smallest divisor of 1001 greater than one:

The loop tried 2, 3, 4, 5 and 6, found a divisor at seven and stopped. Without break it would have printed the other divisors too: 11, 13, 77, 91, 143 and 1001 itself, since $1001 = 7 \cdot 11 \cdot 13$. Had the smallest divisor turned out to be $n$ itself, the number would have had no divisors besides one and itself; in other words, it would be prime. This idea will come in handy in the tasks.

The second common pattern is an endless loop with an exit in the middle. Its condition is True, meaning “always,” and the only way out is break. It is a convenient way to keep asking until the answer is right: input is written once instead of twice, before the loop and inside it, as in the combination lock above.

Nearly every game is built this way: the main loop reads the player’s command, changes the world, draws it and goes round again, until the player says “quit”. The quest from the last chapter can now go on for as long as you like, and you can walk from the building back to the road:

break has a younger brother, continue. It doesn’t leave the loop: it cuts short only the current iteration and goes straight on to the next one. Here it prints the numbers from 1 to 20, skipping the multiples of three:

One subtlety. In nested loops, break and continue act only on the loop whose body they sit in, that is, the innermost one. The outer loop carries on as if nothing had happened.

A loom that never stops

If the condition of a while never turns false, the loop goes round forever. This is called an infinite loop. Run the program below without fear: the sandbox gives every program ten seconds and then stops it.

The variable i runs through 0, 3, 6, 9, 12, 15… and jumps over ten. The condition i != 10 is always true. Replace != with <, and the loop stops at twelve: a “less than” check catches the variable whether it lands on the finish line or jumps past it. Here are the three most common causes of an infinite loop, and each of them breaks the three-part rule from the start of the chapter:

• there is no change at all: somebody forgot throws = throws - 1;
• the change goes the wrong way: + 1 instead of - 1;
• there is a change, but it jumps over the boundary, the way i + 3 skips past ten.

If a loop like this also prints, the server stops it sooner, when it hits the limit on the amount of output. On your own computer nobody will come to the rescue after ten seconds: you stop the program with Ctrl+C, and Python answers with a KeyboardInterrupt traceback.

Some infinite loops are useful. The server that sent you this page has been going round the loop “wait for a request, answer it, wait for the next one” since the moment it started, and it should never stop. So has the operating system of your phone. An infinite loop is a bug only if you didn’t plan it.

How good is your eye for loops? Below are eleven short programs: for each one, predict how many times the marked line runs, and then compare with the counter.

Your own Collatz

In Chapter 0 you ran a program about the Collatz conjecture: if a number is even, halve it; if it is odd, multiply it by three and add one; go on until you reach one. Back then the program was a black box. Now we’ll build it ourselves, and there won’t be a line in it you don’t understand: a while loop with the condition “until it is one,” an if fork, an accumulator counting the steps and another one keeping the record height.

A hundred and eleven steps and a peak of 9232, as in Chapter 0. Now wrap this program in one more loop and go through every starting number from 1 to 10,000. Each one gives a point on a chart: across, the number; up, how many steps it needed. The square brackets and append are lists, the subject of Chapter 6; here they only collect the points for the chart.

The points fall into bands and streams. Part of this is easy to explain: the paths of different numbers often merge and then run together (the path of 97, for instance, reaches 94 on its thirteenth step and from there follows the path of 27), so equal lengths turn up in whole families. The more interesting part is the inner loop. For each of the ten thousand numbers it stopped, or we wouldn’t see a chart. But whether while n != 1 stops for every starting number, nobody knows: the Collatz conjecture says it does, and it has never been proved. We have written a loop that nobody can promise will end. Could there be, at least in principle, a program that looks at any loop and says whether it will stop? The answer is in Chapter 56.

Practice

Five tasks. All of them are complete programs: the tests run your code several times with different input and compare what it prints with what is expected. Trailing spaces at the ends of lines don’t count as mistakes, but extra text does, even a prompt inside input(): it ends up in the output too, which is why the starters have none.

1 2 3
2 4 6
3 6 9

2 3 5 7 11 13 17 19

#...#
.#.#.
..#..
.#.#.
#...#

What next

In the solution to the primes task, checking one number took seven lines, and they are welded into the loop over all the numbers. If primality is needed somewhere else (say, to find twin primes or to check what a user typed), those seven lines will have to be copied, then copied again, and then a bug found in one of the copies will have to be fixed in all of them. Loops spared us from repeating ourselves while the program runs, but the code itself still grows into a wall of identical pieces. We need a way to give a piece of work a name and call it by that name. The engineers of the first computers ran into this wall at once, and in 1949, in Cambridge, subroutines became an everyday tool. That is Chapter 5.