Functions as values

The last chapter ended with a question: can you pass a function another function? The four functions that walked through nested lists, folder_size, show, nested_sum and flatten, differed only in what they did with a simple item, yet their common skeleton couldn’t be written once: we passed functions numbers, strings and lists, but never a piece of behavior. The same repetition shows up in simpler programs too, for example in three loops from earlier chapters.

Three loops, one skeleton: start an empty list, go through all the items, do something with each one, put the result in. Only the filling differs: q[4], q[4] >= 7, len(word). For the sake of one line we rewrite four every time. Cooks don’t work like that. A cookbook doesn’t explain dicing all over again for carrots and then once more for potatoes: “dice” is a technique, and what gets diced is filled in.

This chapter is a kitchen where programs are assembled from techniques, and the filling is handed to them as an argument. For that we have to learn to put a function in a variable, to pass it and to return it, the way we do with a number.

A function on the cutting board

In Chapter 2 we agreed that a name in Python is a label tied to an object. A number is an object, a string is an object, a list is an object. A function is an object too, and def does no more than create it and tie a label with its name to it. We can check.

Without parentheses, shout is the function itself, and you can do with it whatever you can do with any value: give it another name, put it in a list, pass it to another function. With parentheses, shout("fire") is a call: the function runs, and its result takes the place of the expression. This is a common slip. People write print(shout) instead of a call and get a baffling <function shout at 0x7f…>: that is how Python shows the function itself, with its address in memory.

Since a function is a value, functions can be put in a list and gone through with a loop, like knives on a magnetic rack:

A function keeps its own name inside it, in the attribute __name__. Five different functions pass through the same call, f(mags). And since a function can be put in a variable, it can also arrive as a parameter. So the skeleton from the start of the chapter can be written once, with the filling taken as an argument:

The second call passes str.upper, the string method you know from Chapter 7, taken on its own as a function of one argument: str.upper("broth") is the same as "broth".upper(). A function that takes other functions or returns them is called a higher-order function. Our apply_to_each is one of them: it knows how to walk through a list but not what to do with each item. It finds that out when it is called.

Technique one: chop each

The skeleton “do this to each item” is needed so often that it is built into Python under the name map: every item is mapped to the result of a function.

Instead of a list, the first print shows some map object: map hasn’t computed anything yet. What it returned is a promise to compute: an object that hands out results only when they are asked for. list(…) asked for all of them at once. Why such laziness is useful will become clear near the end of the chapter; for now we’ll wrap map in list.

Now for a more serious ingredient: the earthquake catalog from Chapter 6. The magnitude scale is logarithmic. By the Gutenberg–Richter formula, the energy of a quake grows as $10^{1.5M}$, so each unit of magnitude multiplies the energy by about 32. We’ll “chop” every record of the catalog into its energy, measured in units of “one magnitude 5 quake”:

Here one map sits inside another: the inner one turns a record into a magnitude, the outer one turns a magnitude into energy. This is the composition from Chapter 5, applied to a whole stream of values at once. The last line of the output says that a single quake, off Kamchatka on July 29, 2025 (UTC), released more than a quarter of the energy of all nineteen thousand quakes of magnitude five and up in eleven years. The formula is rough, and the catalog mixes several kinds of magnitude, but it gets the order of magnitude right: strong quakes are rare, and they decide everything.

A recipe on a napkin

The function magnitude got a name and two lines of the program, though it was needed for a moment, only to be handed to map. For such cases there is a short notation, the lambda:

The notation lambda q: q[4] reads “a function of q that returns q[4].” After the word lambda come the parameters, after the colon a single expression, and its value is returned without any return. Such a function has no name, and inside it there is only an expression: no loops, no assignments. It is a recipe on a napkin, jotted down right where it is needed and then thrown away. When a recipe runs longer than a line or is needed in two places, write an ordinary def, with a name and a docstring.

Technique two: keep what fits

The kitchen’s second technique is to sort through and keep what is good: berries without mold, mushrooms without wormholes. In Python this is the job of filter(condition, data). The condition is a function that answers True or False; such functions are called predicates. We’ll cut War and Peace into words and keep the palindromes from Chapter 7.

A familiar technique is at work in read_words: map walks through the 3.2 million characters of the novel and replaces every one that isn’t a letter with a space. Its lambda uses the conditional expression a if condition else b, a one-line if that gives a value of its own, one of the two. Then filter keeps the palindromes, set leaves one copy of each, and a second filter keeps only the long ones. Level, madam, refer, and even redder.

Technique three: mix it all

The third technique turns many into one: mix the ingredients into a dough, add numbers up into a sum, pick the strongest of the quakes. Each time we hold a bowl, the accumulator from Chapter 4, and stir the next item into it. Stirring in is a function of two arguments: what is in the bowl and what to add. Here is the skeleton, written by hand:

Press “Steps” and follow the third call: the bowl goes through 0, 1, 18, 184 and 1843, and the digits come together into a number, the year Ada Lovelace’s program was published. This technique is called a fold. In Python it lives in the functools module under the name reduce:

Without a starting value, reduce puts the first item in the bowl and stirs in the rest. So on an empty list it has nothing to put in the bowl, and it fails with a TypeError. If the data might turn out empty, pass a starting value.

reduce has a mixed reputation. In 2005 Guido van Rossum called it “the one I’ve always hated most”: nearly every time he saw reduce with a nontrivial function, he wrote, “I need to grab pen and paper to diagram what’s actually being fed into that function.” In Python 3, reduce was moved out of the built-in functions into functools. The common cases have ready-made folds, sum, max, min and "".join, and where there is none, a loop with an accumulator is often easier to read. The idea of a fold hasn’t gone anywhere, though, and at the end of the chapter it will process the whole web.

The conveyor

The three techniques line up into a conveyor: the output of one is the input of the next. Below is a kitchen where you can put one together by hand. Add stations, change the fillings and watch the food ride from top to bottom.

Try three experiments. On the “numbers” tab, swap “keep what fits” and “chop each.” The result stays the same (a square is even if and only if the number itself is even), but the filling gets called more often, because squares are now computed for numbers that will be thrown out anyway. Weeding out before chopping saves work. On the “words” tab, choose the filter “longer than 10 letters”: nothing gets into the bowl, and you get the error of an empty reduce from the last section. Finally, move the “chop each” station with len above the filter that measures the length of words, and Python refuses: a number has no length. The filling has to suit whatever is riding the belt.

A key to sorting

In Chapter 6 we found the ten strongest quakes with a workaround: we repacked every record into a new tuple with the magnitude in front, since tuples are compared by their first item. Now there is a simpler way. sorted, max and min have a parameter key, a function that says what to compare by.

sorted calls the key once for every item and orders the items by their keys, leaving the records themselves untouched: they only move to new places. max with a key looks for the item with the largest key and returns the item itself. A key can be any function: len, a lambda, a function of your own. If the key is a tuple, the comparison goes by its first element, then, on a tie, by the second, and so on. To have one field ascending and another descending, flip the sign of the number.

Rows with equal keys don’t get shuffled: sorting in Python is stable, and equal items keep their previous order. Sorting in several passes relies on this. Set the table to sort “what is on the table,” choose “magnitude ↓” first and then “country,” and you get the countries in alphabetical order, with the quakes in each country from strongest to weakest. A single tuple key gives the same order: the records on the table are laid out as (date, magnitude, depth, country), and the key is (q[3], -q[1]). In the catalog from the cell above the fields are numbered differently: there the magnitude is q[4]. One more trap hides in the character table itself: letters with accents come after z, so sorted(["éclair", "zucchini"]) puts the éclair last.

Short recipes: comprehensions

“Chop each” and “keep what fits” go together so often that Python has a special notation for them, the comprehension, or list comprehension. You have already seen one in Chapter 8, on the Zipf chart: [65000 / r for r in ranks]. Square brackets, and inside them what to put in, where to take it from and, if needed, which condition it has to pass:

The notation follows the mathematical definition of a set: $\{\,x^2 \mid x \in A,\ x > 2\,\}$, “the squares of those $x$ in $A$ that are greater than two.” Curly braces with a colon give a dictionary, and without a colon, a set. A comprehension is shorter than a loop and usually clearer than map with filter and a lambda, which is why Python programmers prefer it. It has its limits, though: a comprehension with two loops and three conditions can no longer be read, and then an ordinary loop is better.

War and Peace itself has a job for comprehensions. In Book Nine, Pierre Bezukhov comes across a Masonic reading of the Apocalypse. The French letters are given numbers: the first nine count from 1 to 9, the rest go up in tens. Write the words L’empereur Napoléon this way, and they add up to 666, the number of the beast. The table is printed right in the novel. In the Russian original its letters are set without spaces, so on the Russian text our read_words takes abcdefghiklmnopqrstuvwxyz for the longest word in the book; the Maudes spaced the table out into columns. Time to check Pierre’s arithmetic.

zip stitches two lists into pairs, like a zipper: the first letter with the first number, the second with the second. A dict made of such pairs is a finished table. And in number, inside sum(…), sits a comprehension without brackets of its own; more about that in the section on generators.

“Forty-two,” quarante deux, gives 666, while the emperor himself comes to only 661. The sum works out only if the article gets back the letter it lost: le empereur, five more. Tolstoy seems to have known this. A little further on, Pierre looks for 666 in his own name, gets 671, and drops the same e from the article: “By omitting the e, though incorrectly, Pierre got the answer he sought.” The program has caught what the novel only hints at.

Sourdough: functions that remember

A function can receive a function, and it can also return one. Here is a factory that makes multipliers:

By the time double(10) is called, the function make_scaler has long since finished, and its local variable k, by the rules of Chapter 5, should have vanished along with its frame. Yet scale remembers it. Press “Steps”: during the call double(10) the frame of scale holds k = 2 next to x, and during triple(10) it holds k = 3. The function took with it a piece of the place where it was born, the way a sourdough loaf carries a piece of the previous dough. A function together with the variables it remembers is called a closure.

It can remember things that change, too. In Chapter 5 we saw a counter crash with UnboundLocalError when it assigned to a global variable inside a function. A closure has a word for this, nonlocal: “this name belongs to the function outside; don’t make one of your own.”

Each counter has its own sourdough: a has counted to three, b has barely started. There is no global variable, and nobody outside can spoil the count. This is how closures hide state, and in Chapter 12 we’ll see objects doing the same thing in a different way.

Made to order: generators

Back to the riddle of the map object. A good restaurant doesn’t cook a hundred portions in the morning: it cooks to order. An order comes in, one plate is made and sent out, and the kitchen waits for the next one. In Python, generators work this way. They are functions with yield in place of return: “hand it over and wait.”

The call countdown(3) didn’t print “starting”: the body of the function hasn’t begun to run. What we got is a generator object, a cook at the stove. next(g) is an order: the generator runs up to the first yield, hands over a value and freezes on the spot, with all its variables. The next next carries on from the same line. A for loop places order after order until the cook says “that’s all.” Press “Steps”: the frame of countdown appears, disappears and appears again, and the n in it keeps its value every time.

The first benefit is memory. A list holds all its items at once, a generator only its current state. Here is the peak memory used while the sum of the squares of a million numbers is computed. The function peak takes a function, the recipe for how to prepare the data:

The sum is the same, but the memory is not, by a factor of tens of thousands: about 40 megabytes for the list, less than a kilobyte for the generator. The whole difference is in the brackets. A comprehension in parentheses is a generator expression: it builds nothing in advance and hands out the items one at a time. Inside a function call, the second pair of parentheses can be left out: sum(n * n for n in range(10)). That is how number worked for Pierre.

The second benefit is infinity. An infinite list fits in no memory, but an infinite generator takes a couple of lines. Here we look for squares that read the same in both directions, with no way of knowing in advance how many numbers it will take:

islice from the itertools module is a slice for generators: “give me the first twelve.” The chain works backwards. islice orders one value from filter, which orders one from the generator of squares, which orders one from naturals. A number travels back along the chain; if it doesn’t pass the filter, filter orders the next one. At no step is more than one number held, and the chain stops as soon as twelve have been collected. This is lazy evaluation: don’t do anything until you are asked. map and filter are built the same way: they too hand out values one at a time, and only on request.

A generator also answers the wall from the start of the chapter. The walk through nested lists from Chapter 9 can be written once, as a generator that hands out the simple items one at a time, and what to do with them is up to whoever receives them:

The skeleton of the walk lives in one place, and nested_sum from Chapter 9 has turned into sum(leaves(data)), flatten into list(leaves(data)). The double loop in the middle comes up so often that it has a shorthand: yield from leaves(x).

A file is read lazily too: the loop for line in open(…) takes it from the disk line by line, and a novel of hundreds of megabytes is handled as calmly as one of five. Laziness has one price: a generator can be used only once. Go through it, and it is empty. Take g = (n * n for n in range(5)): then sum(g) gives 30, and a second sum(g) gives zero, because the cook has already gone home. If you need the data twice, keep it in a list.

A coat of batter

All that remains is to combine the two skills: a function takes a function and returns a new one. The new one can be a wrapper around the old one, like batter around a piece of fish: inside is the same function, outside a new layer. Let the wrapper count calls. We’ll put it on the Fibonacci numbers from Chapter 9, whose call tree is full of repeats.

The line @count_calls above the definition is short for fib = count_calls(fib): after the def, the label fib is moved onto the wrapper. That is why the recursive calls inside fib also go through the wrapper, and the counter sees all 242,785 calls made for the sake of a single number, 75,025. A function that takes a function and returns an improved version of it is called a decorator. The counter here is an attribute of the wrapper function itself: a function is an object, and you can hang anything you like on it.

Decorators are written for things many functions need at once: timing, logging every call, checking permissions, remembering answers. For a wrapper to suit functions with any number of arguments, it is written as def wrapper(*args): the asterisk gathers all the arguments passed into a tuple, and f(*args) hands them back out. A wrapper that remembers answers already computed, and turns 242,785 calls into 26 computations, is in the standard library: functools.cache. Why it works and where else it helps is the subject of Chapter 22.

A kitchen for a thousand machines

The classic example from the paper is counting words. The map function gets a piece of text and produces a pair (word, 1) for every word in it. The library gathers all the pairs with the same word into one pile, a step called the shuffle, and hands each pile to the reduce function, which adds up the ones. Below are eight machines and the famous paragraph about the sky over Austerlitz from Book Three of War and Peace.

The experiments with the machines show two things from the paper. First, the time of the whole job is the time of its slowest machine. One machine with a bad disk holds back a thousand; the paper describes a case where a bug in the code that set machines up at startup disabled the processor caches on some of them, and they ran more than a hundred times slower. Backup tasks cure this almost for free: when the authors sorted a terabyte without them, the job took 44% longer. Second, a broken machine doesn’t need fixing: its chunk is recomputed on another one. When the authors killed 200 of 1,746 worker processes in an experiment, the whole computation took 5% longer.

Rerunning is safe only because map and reduce are pure functions. Computing a chunk twice is the same as computing it once: the answer depends only on the chunk. If map had a side effect, a global counter, say, a rerun would count words twice, and the result would depend on which machines had broken down. This is the condition the authors point to: when the user’s functions are deterministic, the result is the same as that of a sequential run on a single machine.

Here is the same computation on the whole novel, on “eight machines” inside the sandbox. You know the word counter Counter from Chapter 8; two counters can be added with +.

The map and reduce here are Python’s, not Google’s: each “machine” counts the words of its chunk on the spot, and what gets merged is finished counters. The paper does this too and calls it a combiner: it cuts down the shuffle a great deal. How to build the engine itself, in which pairs with the same key find each other, is the last task of the chapter. That engine has one boss, the MapReduce master; how machines can come to an agreement with no boss at all is the subject of Chapter 44.

Tasks: recipes for your book

Five tasks, from a warm-up to the hardest. In each one the tests call your functions and check what they return. Remember that a function is a value: in some places you’ll have to return the function itself, not the result of calling it.

What next

Our programs have got shorter, but each line now does more. In filter(lambda w: len(w) >= 5, found) it is easy to get the comparison wrong, in a sort key to forget the minus, in a closure to get caught by the loop’s shared variable. None of these mistakes makes a sound: the program quietly gives a wrong answer, as in Chapter 1. The longer the program, the more such places it has and the more a mistake costs.

On June 4, 1996, the new European rocket Ariane 5 broke up about 39 seconds after its main engine was ignited, on its very first flight. The cause turned out to be a piece of software carried over from the previous rocket, Ariane 4, where it had worked for years without a single failure. How to catch mistakes before they blow up a rocket, and what to do with the ones that happen anyway, is the subject of Chapter 11, the report of the board of inquiry.