Functions that take functions

Six numbers are wanted: three candidate rules for the minutes table, scored under two ways of charging for a wrong answer. The rules are round down, round to nearest, and the lookup rule that copies the notebook. The two charges are the count of wrong rows and the size of the error in minutes.

Write the program naively and you have written it six times, because five of the six copies differ from the first in exactly two lines. The line that requests an answer from a rule changes, and the line that turns a disagreement into a number changes. Everything else stays identical, including the loop, the division and the order of the additions. !The six scoring programs differ only in two places: the rule that answers, and the charge that turns a disagreement into a number. The figure writes the shared skeleton once, with the two places left as dashed slots. Filling the rule slot with round down, round to nearest or lookup, and the charge slot with the count of wrong rows or the size of the error in minutes, produces all six programs from one definition; the loop, the division and the order of the additions never change. Status: schematic.

Copying is considerably worse than tedious, because on the fourth copy you will alter a line you did not intend to alter and nothing will report the mistake: all six programs return numbers, and all six numbers look plausible. A program accepts another program so that the pattern gets written once and the differences become arguments. The name for a program that does this is a higher-order function: it takes another function as an argument, or returns one as its result. That single permission turns six copies into one definition. !Composition applies the second procedure first. Adding one to 6 gives 7, and squaring 7 gives 49, so composing squaring with adding one returns 49. The pipeline fixes the order: the procedure named first runs second. Neither procedure knows the other exists; the order comes from the wiring, not from the names. Status: schematic.

Arithmetic makes the two places visible without a story in the way. Three procedures each add up a series of terms between two whole numbers. The first adds the integers themselves, the second adds their cubes, and the third adds terms of the series 1/(1·3) + 1/(5·7) + 1/(9·11) + …, which converges very slowly toward an eighth of pi [S:13:104].

A series is a sum of terms taken in order, and it converges when its partial sums approach a fixed number as more terms are added, without the sum ever necessarily reaching it. The source compares the three and finds that they differ only in the name of the procedure, in the function of the running value used to compute the term, and in the function that supplies the next value [S:13:105].

Write down what is common and leave those two places blank, and the three procedures collapse into one with two arguments standing where the blanks were. Mathematicians made this move first, and the parallel is worth naming. Sigma notation exists so that the concept of summation can be handled on its own rather than only through particular sums [S:13:105]. The blank in the template is the programmer's version of the same manoeuvre, and filling it requires handing a procedure to a procedure.

Worked example. Add the integers from 1 to 10 and the answer is 55; add their cubes and the answer is 3025 [S:13:106]. The two runs differ in a single argument, and the same definition produces both.

The fourth use of that definition has nothing to do with series. Approximate an area under a curve by chopping the interval into strips, taking the height of each strip at its midpoint, adding the heights and multiplying by the width. Hand the general procedure the cubing function and the strip width, and the area under the cube from 0 to 1 comes out close to one quarter, with the same definition that summed the integers.

Whether a language permits any of this depends on the restrictions it imposes. Elements with the fewest restrictions are said to have first-class status. The rights are four: to be named by a variable, to be passed as an argument, to be returned as a result, and to be stored inside a data structure [S:13:130]. The source offers that list as some of the rights of a first-class element rather than as a definition, and among the common languages of its time only Lisp grants procedures all four [S:13:130]. Procedures have all four here, and this chapter has already used two of them: procedures have been passed as arguments, and the next paragraph returns one as a result.

The third right reads strangest and pays best. A procedure may compute a procedure and hand it back, exactly as another procedure computes a number and hands that back. Averaging a value with the result of applying a procedure to it is one such case. Hand the averaging procedure the squaring function and it returns a procedure, not a number; apply that returned procedure to 10 and the answer is 55, the average of 10 and 100 [S:13:126].

Applying one procedure after another is the other case, and it has a name. The composition of two procedures applies the second and then the first. Compose squaring with adding one, call the result on 6, and the answer is 49: add one to obtain 7, then square it. Neither the squaring procedure nor the adding procedure knows that the other exists.

That price is real and it is the limitation. Six separate copies state their purpose inside their own bodies, and one general procedure states only a shape, so every call site now carries the burden of saying what it meant. The slots must also be filled at every call, and filling a slot with the wrong procedure produces a number of the right kind and the wrong value, which is the most difficult kind of mistake to notice. This chapter's final section returns to that problem, because a promise written beside a call is what replaces the missing body.

The formal statement. A procedure is higher-order when it takes a procedure as an argument or returns one as a result. The summation template takes a term procedure, a lower bound, a next-value procedure and an upper bound, and returns a number. The term procedure maps a value to a number and the next-value procedure maps a value to the next value. The template applies both in a fixed order until the bound is passed [S:13:105].

Two definitions belong beside that one. An element has first-class status when the language grants it four rights: to be named by a variable, passed as an argument, returned as a result, and stored inside a data structure [S:13:130]. The composition of two procedures applies the second and then the first [S:13:131].

The derivation. The three summation procedures differ in exactly two positions, the function that computes the term and the function that supplies the next value [S:13:105]. Abstract those two positions into parameters and the three bodies become one body. Instantiate the term slot with the identity and the next slot with the increment, and the template sums the integers from one to ten, giving 55 [S:13:106]. Instantiate the term slot with the cubing procedure instead, and the same body gives 3025 [S:13:106]. The second run differs from the first in one argument, and the loop, the bound test and the order of the additions are unchanged.

Returning a procedure needs one more step, and it is the step that carries the weight. The averaging procedure accepts a procedure f and hands back a procedure that averages its argument with the value of f at that argument [S:13:125]. Hand it the squaring procedure and apply the result to ten, and the answer is 55 [S:13:126]. The returned procedure works because it carries f inside it. That carrying is the closure, and the rule licensing it is that a procedure keeps the values its free names had where it was written.

An edge case. Suppose the template calls its term slot twice per step and uses the first result. The number 55 does not change, and the cost doubles. Suppose the slot also prints, or advances a counter, and the answer changes as well. So the sentence "the two programs differ only in an argument" is true of the value and false of the run. The template fixes how often and in what order the slot is called, and the slot's author cannot see that schedule from the call site.

What L1 hid, and why that was safe there. L1 said the pattern is written once and the difference becomes an argument. The refinement is that each slot carries its own contract, and the template's promise is conditional on the slots keeping theirs [S:13:105]. In the arithmetic examples every slot is total on the range, so the conditional never fires, and the reader can meet the idea before meeting the obligation.

Where the analogy breaks. Sigma notation lets a mathematician treat a sum as one object, and the order of the terms is free because addition does not care. The programmer's blank is stricter: the template fixes an order and a count of calls, and a slot with effects can tell the difference.

Where the idea comes from. Section 1.3 of Structure and Interpretation of Computer Programs builds the idea in four steps: procedures as arguments [S:13:104], a template with slots, procedures as returned values, and finally first-class status [S:13:130]. SICP credits the notion of first-class status to Christopher Strachey [S:13:130], and it names the mathematical precedent for the move: sigma notation exists so that the concept of summation can be handled rather than only particular sums [S:13:105].

The composition of two procedures appears there as an exercise with the answer 49 [S:13:131]. That exercise is the smallest case of the section's claim, because the two procedures involved know nothing about each other.

What the field has not settled. Whether abstraction costs anything at runtime, and how much a compiler can recover. SICP states the mechanism of the cost: returning a procedure as a value requires reserving storage for its free variables even while it is not running [S:13:131]. What follows from that is an accounting question rather than a mathematical one, and the answer varies by language and by optimiser. The evidence that would settle it for one toolchain is a measurement: run the template and six hand-written copies on the same table, and compare time and allocation counts. A compiler that inlines the template can erase the difference; one that allocates a closure per call cannot.

What depends on it. The derivative is a procedure that takes a procedure and returns one [S:13:128], and that single sentence is the door to automatic differentiation. Reverse-mode differentiation walks a recorded computation graph and applies the chain rule node by node, which is the machinery behind every backward pass in Part IV [S:88:28]. Every framework there rests on procedures returned as values and on programs treated as data.

What to read next. Read SICP section 1.3 in full, ending with the first-class status list [S:13:130]. Then read the computation-graph section of Goldberg's primer, which shows the abstraction carried into machine learning practice [S:88:28]. The exercises on repeated application and composition are worth doing before that, because they make the difference between a procedure and the function it computes concrete [S:13:131].