Words of your own

The last chapter ended at a wall. In the prime-number task, checking a single number took seven lines, and those lines grew right into the loop. Suppose you want twin primes, pairs like 11 and 13 where both numbers are prime. Now there are two numbers to check, so the seven lines get written twice. Need primality somewhere else, and it’s three times. Then a bug turns up in one of the copies, and you have to fix it in all of them. We need a way to write a piece of work once, give it a name and call it by that name. The programmers of the first computers hit the same wall and found a way through in the first months their machines were running.

Cambridge, 1949: a library on paper tape

Today subroutines are called functions, and nobody writes their endings by hand: the language does it for you. The idea is still Wheeler’s. This chapter is a workshop: you’ll fill a toolbox with tools that come back again and again in the course, and each new tool brings out one more detail of how functions work.

Tool one: a square

We start with a tool whose result you can see. In the last chapter the turtle drew a square with a loop of two commands. To draw three squares of different sizes you would have to write that loop three times. Instead, we’ll teach Python a new word:

The line def draw_square(size): is the header. The word def (short for define) announces a new word. Then comes the name, then a parameter, size, in parentheses, then a colon, and under it, indented, the body. The definition draws nothing by itself; it only writes down a recipe under the name draw_square. The work starts when the function is called. The line draw_square(40) means “run the body with 40 in size.” The value passed in a call is an argument. One body, three calls with different arguments, three squares.

A named piece of a program that can be called with different arguments is a function. Python comes knowing plenty of functions—print, input, len—and you can add as many of your own as you like, so the language grows the words your problem needs.

A function can take several parameters. A polygon needs two numbers: how many sides it has and how long they are. The turn at each corner, as we found in the last chapter, is $360 / n$ degrees:

Arguments go to parameters in order: the first to sides, the second to size. Six polygons grow from one corner, from a triangle to an octagon, out of a single description of a polygon.

Now follow Python through a program with a function in it. Press “Steps” and watch the arrow. After line 6 it jumps into the function, to its header on line 1, goes through the body and comes back to line 7. A second frame appears in the “Frames” column: the call’s own workspace, where its parameter name lives. This is the Wheeler jump again, except that Python keeps track of the return address itself.

The definition comes before the calls, and for a reason: Python reads the program from top to bottom, and by the time it reaches greet("Ada") it must already know what greet is. Swap them and you get a familiar NameError.

Tool two: the digit sum

The square draws, and drawing is its whole job. More often we want an answer from a tool: work this out and tell me the result. Take the digit sum from the task in the last chapter and turn it into a function:

The last line of the body, return total, ends the function’s work and hands the value back to the place the function was called from. From then on, the call digit_sum(1843) in effect becomes the number 16: you can print it, add something to it, compare it or pass it to another function. The last line of the program does that: the digit sum of $2^{1000}$ is 1366, and the digit sum of 1366 is 16. What a function hands back with return is its return value.

Since the function gives back a number, we can build new tools out of it. Keep adding up the digits until only one is left, and you get the digital root:

For a positive number, the digital root is the remainder after dividing by 9 (when the remainder is zero, the root is nine). An old way of checking arithmetic, casting out nines, rests on this: the digital root of a correct product equals the digital root of the product of the factors’ roots. What interests us here is something else: digital_root fits in four lines because a ready-made tool does the heavy lifting.

This is where beginners get confused most often. Here is the same function with print instead of return at the end:

The number 16 is on the screen: the function printed it. But result holds None, a special value meaning “nothing,” which is what a function returns when it never reaches return. You can’t add one to nothing, hence the TypeError. Remember the difference: print shows a value to a person and forgets it at once, while return hands the value to the program so that it can go on working with it.

A game: the black box

From the outside, a function with return can be judged only by its answers. An input goes in, an output comes out, and what happens inside you can’t see and don’t need to know. Below are ten boxes with functions inside. Drop numbers into a box, watch what comes out, and when you’ve worked out the rule, press “I get it, test me”: the box will ask you three questions. Predict its answers, and it will open and show you its code.

Mathematicians think of functions the same way: the chapter on functions in “Mathematics, the Queen of the Sciences” opens with this game. So do programmers. You use print and len without ever looking inside them. Big programs rest on contracts of the form “give me this and you’ll get that”: they are assembled from parts, and nobody has to remember how each part works. Your own function is better off with such a contract written right into its code, and we’ll get to that soon.

Every call gets its own workbench

Inside digit_sum there are variables n and total. What if the main program has variables with the same names? The function grinds n down to zero. Will it wreck somebody else’s n?

Outside, n is still 1843 and total is still a thousand. For every call, Python sets up a new workspace for the function, called a frame, and every variable the function creates, parameters included, lives there. These are local variables: each call has its own, and they vanish when the call ends. The part of a program where a name means something is that name’s scope. Press “Steps”: during the call the “Frames” column holds two frames, the global one and digit_sum(), and each has its own n.

When functions call each other, the frames pile up. Call a function and a new frame goes on top; the function returns its answer, the frame comes off, and work carries on in the frame below. This pile is the call stack. Here are three functions that call one another: the perimeter of a right triangle with two given legs calls the hypotenuse, and the hypotenuse calls the square twice.

The two calls of perimeter make two “mountains” of the same shape: each rises to four frames while square is running and then comes back down. Within each mountain square is called twice, and those are two different frames, each with its own x.

Here you can see what the Wheeler jump couldn’t do. An EDSAC subroutine kept its return address in its own last cell, and there was only one copy of it. Had a subroutine called itself, the second call would have overwritten the first call’s return address, and the first would never have found its way back. In Python every call has its own frame with its own place to return to, so a function can call itself, that call can call itself again, and so on, hundreds of levels deep. What comes of this, and where the limit lies, is the subject of Chapter 9.

Default settings

A good tool doesn’t need to be told the obvious every time. Say the polygon should be drawn black with a side of 60 unless we ask for something else. For that, the header gives a parameter a default value:

The first call passes only the number of sides; everything else comes from the defaults. The second gives the size as well. The third skips the size and names the color: color="red". Arguments like this are called keyword arguments, and their order doesn’t matter: in the fourth call the size is named before the number of sides.

You used this back in the last chapter when you wrote print("#", end=""). print has parameters with default values too, and Python will gladly show them:

The header print(*args, sep=' ', end='\n', file=None, flush=False) reads like this: any number of values, with a space between them unless you say otherwise, and a newline '\n' at the end unless you say otherwise. When you wrote end="", you changed one setting and left the rest alone.

A tag on the tool

How did help know what print does? From a tag that the function’s authors attached to it. You can tag your own function the same way, with a string in triple quotes right under the header. This is a docstring, short for documentation string:

A tag states the contract, not the inner workings: what the function takes, what it returns and, where it helps, an example. A good example doubles as a test, and Chapter 11 shows how to run such examples automatically. The other half of the tag is the name. Functions that do something usually get a name that starts with a verb: draw_square, greet. Functions that compute a quantity are named after the quantity: digit_sum, hypotenuse. And question functions, the ones that answer yes or no, start with is_: is_prime, is_lucky.

Functions as beads

We have already strung one function onto another: digit_sum(digit_sum(2 ** 1000)), twice(twice(3)). One function’s answer becomes another’s input. This is composition, and with it a few simple tools make new ones without a single new line inside them. Try it with beads: each bead is a small function, and a number runs along the thread from left to right.

The first puzzle already shows that the order of the beads matters: “square, then plus one” turns 3 into 10, while “plus one, then square” gives 16. The notation is worth remembering too. The thread reads from left to right, but Python writes the same chain from the inside out: in inc(square(3)) the innermost function, square, runs first. Mathematicians write composition the same way, $f(g(x))$, and read it the same way.

Top down: the lucky ticket

Functions are for more than avoiding repetition. They let you solve a big problem without drowning in details. Here is one. Old Soviet tram and bus tickets carried a six-digit number, from 000000 to 999999. A ticket was lucky if the sum of its first three digits equaled the sum of the last three, as in 123321. How many lucky tickets are there?

We’ll solve it from the top down. First we write the solution as if the tool we need already existed: a function is_lucky that says whether a ticket is lucky. For now its place is taken by a stub that always says no:

The program runs, though it lies: it prints zero. Python skips the underscores in 1_000_000; they are there for the eye alone. But the top level is ready, and it is as plain as the problem itself: go through the tickets and count the lucky ones. One level down, we write is_lucky. The first three digits of the number are ticket // 1000, the last three ticket % 1000, and we already have a tool for adding up digits:

There are 55,252 lucky tickets, about one in eighteen. The function is_lucky returns the result of a comparison, which is already True or False, with no if needed, and no function here is longer than six lines. This way of solving problems is called top-down decomposition: first the main idea, written in terms of functions that don’t exist yet, then each of those functions on its own, and so on down to the simplest ones. Big programs are written this way too, from games to operating systems.

Pure tools

If you got as far as the tenth box in the game, you met a strange function: it gave different answers to the same input. Inside it is a global counter of calls, and every call changes it. Compare it with digit_sum, which answers from its argument alone and changes nothing around it: no variables outside, nothing on the screen. Functions like that are called pure.

Not every useful function is pure: the whole point of draw_square is that it draws, and of greet that it prints. But wherever you can, write pure ones. A pure function is easy to check: give it an input, compare the output with what you expect, and it makes no difference whether it has been called before. That is how the course’s server checks your tasks. You can rearrange pure functions and string them like beads without fear of surprises like the tenth box.

A tool for every day: the card number

Take any bank card. The digits of its number aren’t random: the last one is a check digit, chosen so that the whole number passes one simple test. Mistype one digit and the test notices, and an online shop will tell you “invalid card number” without even contacting the bank.

Here is Luhn’s rule. Go through the number from right to left and double every second digit (the second, fourth, sixth and so on from the end); if doubling gives more than nine, subtract nine. Add everything up. The number is valid if the sum is divisible by 10. Try it on the number below: tapping a digit changes it to the next one, and the buttons make typical typing mistakes.

The experiment under the figure tries every error in a single digit and catches each one. That will happen with any number, and it can be proved.

Swapping two neighboring digits is almost the same story: the check always catches it, with one exception, the pair 0 and 9. Zero adds zero whether it is doubled or not, and nine adds nine either way (18 − 9 = 9), so the swap 09 ↔ 90 leaves the sum unchanged. You can work out Luhn’s rule in your head, and yet it catches the most common typing mistakes. No single check digit can guard against every error at once.

Tasks: your toolbox

Four tools, each one a function. The tests call your function with different arguments and compare what it returned with what they expect—what it returned, not what it printed. There is no need to print anything inside the functions.

What next

The toolbox is full. Here is what’s in it and where each tool turns up again:

All our tools work on one number or one string at a time. luhn will check a card number, but what if there are a thousand numbers? is_prime answers for one number, but where do you put all the primes you find so you can work with them later? Making a thousand variables number1, number2… would be silly, and you don’t even know in advance how many you’ll need. We need one name for many values. It arrives in Chapter 6 and goes straight to work: you’ll get an earthquake log from the site’s tracker, thousands of records, along with the questions put to a seismologist on night duty.