Programming Functionally

The last chapter wrote fold_range, which names a pattern of recursion once and takes what varies as arguments. This chapter writes whole programs that way. A bank statement is a list of amounts, deposits positive and withdrawals negative. total_withdrawn adds up the withdrawals. Written with the loops and cells of Part IV, it walks the list and accumulates into a cell:

fn total_withdrawn(amounts: [Int]) -> Int {
    ref total = 0;
    for a in amounts {
        if a < 0 { total := deref total + abs(a) }
    };
    deref total
}

total_withdrawn([100, -20, 35, -5, -40])                // 65

The prelude’s abs is the absolute value, filter(xs, p) keeps the elements of xs for which p returns true, map(xs, f) applies f to each element, and fold(xs, z, f) combines the elements from the left starting from z (Appendix C). With them the same function is one expression, with no cell and no loop:

fn total_withdrawn(amounts: [Int]) -> Int =
    fold(map(filter(amounts, |a: Int| a < 0), abs), 0, |t: Int, w: Int| t + w);

Read from the inside out: keep the negative amounts, take the absolute value of each, add them up. Both versions return 65. The second raises these questions:

• What has become of the loop’s variables? The loop has a cell that changes four times; the pipeline has no name whose value changes. Where did the state go?
• Where do the stages come from? |a: Int| a < 0 is < with one argument fixed, and t + w is + taken whole. Can a program build such stages from functions it already has, instead of writing a lambda each time?
• When can one pipeline replace another? The same total can be computed with a single fold that tests and adds in one step. Is there a rule that turns one into the other, and when does it fail?
• What does the pipeline cost? filter builds a list of withdrawals and map a second list of their sizes, both before fold reads either. The loop builds neither.

A 1977 lecture by one of the designers of Fortran took up these questions, as an argument against the style Fortran had made standard.

The von Neumann style

John Backus led the team that built Fortran. His Turing Award lecture, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs” (delivered 1977, published 1978), argued that the languages descended from Fortran had inherited the shape of the machine they ran on. A von Neumann computer has a processor and a store joined by a single channel, which Backus called the von Neumann bottleneck, and it computes by sending words through that channel one at a time. A conventional language has the same shape: its variables imitate the machine’s storage cells and its assignments the machine’s fetches and stores. In Backus’s words, “The assignment statement is the von Neumann bottleneck of programming languages and keeps us thinking in word-at-a-time terms in much the same way the computer’s bottleneck does.”

His example was the inner product of two vectors, ${\sum }_i{a}_i{b}_i$, written in the style of Algol:

c := 0
for i := 1 step 1 until n do
    c := c + a[i] × b[i]

The loop version of total_withdrawn has the same structure: a cell set to zero, a loop that visits the elements one at a time, and an assignment that adds one more term. Backus listed the properties of such a program, beginning with “Its statements operate on an invisible ‘state’ according to complex rules.” To know what c holds at the end, a reader runs the loop in their head.

His alternative, a language he called FP, builds programs without assignment. A program is a function of one argument, and new programs are made from old ones by a fixed set of functional forms (his abstract also calls them combining forms): operations that take functions and return a function. Among them:

• Composition: $f\circ g$ is the function that applies $g$ and then $f$.
• Apply to all: $\alpha f$ applies $f$ to every member of a sequence. It is map.
• Insert: $/f$ combines the members of a sequence with $f$. It is a fold, grouped from the right: $/+$ applied to $⟨6,10,12⟩$ is $6+(10+12)$.
• Binary to unary: $(\mathbf{bu}fx)$ is defined by $(\mathbf{bu}fx):y\equiv f:⟨x,y⟩$, where $f:x$ is FP’s notation for applying $f$ to $x$. It turns a function of a pair into a function of one value by fixing the first member of the pair.

The inner product in FP is a single definition, given in the lecture first in full and then abbreviated:

$$\mathbf{Def}\mathrm{Innerproduct}\equiv (\mathrm{Insert}+)\circ (\mathrm{ApplyToAll}\times )\circ \mathrm{Transpose}$$

$$\mathbf{Def}\mathrm{IP}\equiv (/+)\circ (\alpha \times )\circ \mathrm{Trans}$$

Read right to left: transpose the pair of vectors into a sequence of pairs, multiply each pair, and insert + between the products. The definition mentions no vector, no index, and no accumulator. Backus’s list for this program answers the first one point for point; among its entries, “It does not name its arguments,” and it can be understood “without mentally executing it.”

The second half of the title is what the change buys. An FP program is an expression built from functions by a fixed set of forms, so programs satisfy algebraic laws, and one program can be turned into another by rewriting with them, as an equation is rewritten in school algebra. Backus called this an algebra of programs, and wrote that “it can help one to understand and prove things about programs in a systematic, rather mechanical way.” One of the laws he listed, numbered III.4, is

$$\alpha (f\circ g)\equiv \alpha f\circ \alpha g$$

Applying $f\circ g$ to every member is the same as applying $g$ to every member and then $f$ to every member of the result. The same lecture says where such properties come from and what removes them. Of the expressions on the right-hand sides of assignments, Backus wrote that they form “a world that has useful algebraic properties (except that those properties are often destroyed by side effects).”

FP found few users. The forms it gathered were older than the lecture; Lisp had maplist from its first years, as the last chapter recounted. Under these or similar names, map, filter, fold, and composition are part of the standard library of Lisp, ML, Haskell, Python, JavaScript, and Rust, and of Bridger’s prelude.

Programs built from functions

Bridger has no functional forms built in beyond the prelude’s three. A function that takes functions and returns a function is an ordinary closure, so each of Backus’s forms can be written as a Bridger function.

Composition

fn compose(f: fn(Int) -> Int, g: fn(Int) -> Int) -> fn(Int) -> Int =
    |x: Int| f(g(x));

compose(f, g) returns a closure that has captured f and g; calling it with x computes f(g(x)). The types here fix every function to Int, since that is the only kind of function type Bridger can write so far. The definition never looks at the integers, and Part VI gives it a type that says so: compose works for any g whose result f accepts. The same holds for every combinator in this section.

Fixing an argument

Backus’s $\mathbf{bu}$ takes a two-argument function and one argument and returns the function of the other:

fn bu(f: fn(Int, Int) -> Int, x: Int) -> fn(Int) -> Int = |y: Int| f(x, y);

fn add(x: Int, y: Int) -> Int = x + y;

map(range(1, 6), bu(add, 10))                           // [11, 12, 13, 14, 15]

Supplying some of a function’s arguments and getting back a function of the rest is called partial application. The predicate in total_withdrawn is a partial application written out by hand: |a: Int| a < 0 is < with its second argument fixed at 0. A function that returns such predicates makes the fixed value a parameter:

fn below(n: Int) -> fn(Int) -> Bool = |a: Int| a < n;

filter([100, -20, 35, -5, -40], below(0))               // [-20, -5, -40]
filter([100, -20, 35, -5, -40], below(-10))             // [-20, -40]

below(0) and below(-10) are two closures over two different bindings of n, as the adders of closures were.

A two-argument function can also be rewritten once, so that every partial application of it comes for free. curry turns a function of two arguments into a function of one that returns a function of the other, and uncurry turns it back:

fn curry(f: fn(Int, Int) -> Int) -> fn(Int) -> fn(Int) -> Int =
    |x: Int| |y: Int| f(x, y);
fn uncurry(f: fn(Int) -> fn(Int) -> Int) -> fn(Int, Int) -> Int =
    |x: Int, y: Int| f(x)(y);

fn mul(x: Int, y: Int) -> Int = x * y;

map(range(1, 6), curry(mul)(3))                         // [3, 6, 9, 12, 15]
uncurry(curry(add))(2, 3)                               // 5

curry(mul)(3) is mul with its first argument fixed, the same function as bu(mul, 3). The transformation is called currying, from its use in the work of the logician Haskell Curry, although Curry himself attributed it to Moses Schönfinkel’s 1924 paper on combinatory logic, and Gottlob Frege had used it earlier still. Felice Cardone and J. Roger Hindley’s history of the λ-calculus and combinatory logic (2006, §3) gives the sources. In the λ-calculus every function takes one argument, and a function of several arguments is written curried from the start: $\lambda x.\lambda y.x+y$. ML and Haskell follow the calculus, so that in those languages add 10 is already a function. Bridger’s functions take all their arguments at once, as Rust’s do, and partial application is a lambda or a bu away.

Laws

Each stage of total_withdrawn is a function applied to a whole list, and a stage’s result depends on nothing but its input. That makes it possible to state facts about pipelines that do not depend on what the stages are. Two such facts, for any list xs and any functions of the right types:

$$map(map(xs,g),f)=map(xs,f\circ g)$$

$$fold(map(xs,f),z,h)=fold(xs,z,\lambda (acc,x).h(acc,f(x)))$$

The first is Backus’s law III.4 written with map, and is called map fusion: mapping twice is mapping once with the composition. The second says that a map feeding a fold can be absorbed into the fold’s combining function. Both can be checked by following one element through each side: on the left of the first, x becomes g(x) in the intermediate list and then f(g(x)); on the right it becomes compose(f, g)(x), which is f(g(x)).

Laws like these are how one pipeline becomes another. The predicate in filter can be absorbed into a fold the same way, by a combining function that skips the elements it rejects. Applying the second law and then that one to total_withdrawn gives a single pass with no intermediate lists:

fn total_withdrawn(amounts: [Int]) -> Int =
    fold(amounts, 0, |t: Int, a: Int| if a < 0 { t + abs(a) } else { t });

It returns 65, like the other two. The derivation never ran the program; it rewrote one expression into an equal one.

An expression is referentially transparent when it can be replaced by its value, or by any other expression with the same value, without changing what the program does. The laws need the stages to be referentially transparent, because rewriting with them replaces expressions by equal ones and assumes nothing else notices. The term came up already in static and dynamic scope, where renaming a parameter changed a program’s output under dynamic scope; static scope is one of the conditions for it, and the absence of effects is another.

Where the laws fail

A stage that has an effect is not determined by its input, and the laws stop holding. Two stages that print what they are doing:

let g = |x: Int| { print("g"); print(x); print(" "); x * 2 };
let f = |x: Int| { print("f"); print(x); print(" "); x + 1 };

map(map([1, 2, 3], g), f)        // prints g1 g2 g3 f2 f4 f6, returns [3, 5, 7]
map([1, 2, 3], compose(f, g))    // prints g1 f2 g2 f4 g3 f6, returns [3, 5, 7]

The two sides return the same list and print different text. A stage that reads a cell another stage writes changes the value as well:

ref seen = 0;
let g = |x: Int| { seen := deref seen + 1; x };
let f = |x: Int| 10 * x + deref seen;

map(map([1, 2, 3], g), f)        // [13, 23, 33]
map([1, 2, 3], compose(f, g))    // [11, 22, 33], with seen reset to 0 first

On the left, g runs on every element before f runs on any, so f always sees 3; on the right, the two alternate. Map fusion assumes that the order in which stages run does not matter, and effects are exactly what makes it matter.

A call with an effect is not interchangeable with its value either. make_counter from closures returns a function that adds one to a captured cell and returns the new count:

let next = make_counter();
next() + next()                                         // 3

let next = make_counter();
let n = next();
n + n                                                   // 2

Naming the result of a call and using the name twice is the same replacement, and for next it changes the answer.

Bridger’s functional style

Bridger supports the style of this chapter and does not require it. Functions are values, closures capture under static scope, the prelude’s map, filter, and fold take functions, and every combining form above is a few lines of ordinary Bridger. Bindings never change; a list is a value, and map and filter return new lists and leave the lists they are given as they were. Mutation stays available, in the one place Part IV put it: a reference cell, allocated by ref and changed by :=.

Bridger also does not record in a function’s type whether calling it has an effect. g above and |x: Int| x * 2 have the same type, fn(Int) -> Int, and nothing stops the first from being handed to map. The laws of the last section are therefore laws about the pure part of the language, and a programmer applying them checks the side condition by reading the stages. Bridger checks purity mechanically in one place, where its semantics depends on it: the filters of a rule in Part VII, which the evaluator may run any number of times in any order. There a purity judgment works out, from the program itself, which functions can reach an effect.

The state the loop kept in a cell, a pipeline keeps in the accumulator of a fold. A fold whose accumulator is a tuple carries several values at once, so counting the withdrawals and totalling them takes one pass and no cells:

fold([100, -20, 35, -5, -40], (0, 0),
     |acc: (Int, Int), a: Int|
         if a < 0 { (acc.0 + 1, acc.1 + abs(a)) } else { acc })
                                                        // (3, 65)

Each step returns a new pair. The sequence of states is still there, as the sequence of values passed from one call of the combining function to the next, but no name holds more than one of them.

Recursion is the remaining replacement for the loop, and recursion and higher-order functions measured what it costs in Bridger: a frame per level, up to 100 000, with no tail-call elimination. The prelude’s map, filter, and fold are native and open no frames of their own, which is why a pipeline over a million elements runs where a recursive function of a million levels does not.

Building it

Nothing in this chapter adds to the evaluator. Every program above is lambdas, calls, tuples, and prelude functions, all of which the arms of the earlier chapters already evaluate. compose, bu, curry, and uncurry are user code, and the closure each one returns is built by E-Lam like any other. The milestone that closes this part tests the evaluator with programs of exactly this kind.

The design space

Purity

Languages with first-class functions differ in where they put effects, and so in how far the laws of this chapter can be trusted.

Haskell keeps them out of ordinary expressions altogether. As evaluating function calls described, an ordinary Haskell expression cannot perform an effect; a computation that does input or output has a type of its own, IO, and is combined with others through operations on that type. The Haskell 2010 Report (ch. 7) puts it as “The I/O system in Haskell is purely functional, yet has all of the expressive power found in conventional programming languages.” An ordinary Haskell function is therefore referentially transparent, and the laws hold without a side condition. The Glasgow Haskell Compiler puts them to work. Its User’s Guide gives map fusion as its first example of a rewrite rule, which a library states in its source and the compiler applies wherever the left side matches:

{-# RULES
 "map/map" forall f g xs. map f (map g xs) = map (f . g) xs
 #-}

Haskell writes application without parentheses and composition as .; the rule is the law of the previous section.

ML allows effects anywhere. Its bindings are immutable, and the OCaml manual (ch. 1) describes the alternative its standard library provides: “references, which are mutable indirection cells, with operators ! to fetch the current contents of the reference and := to assign the contents.” That is the model Bridger’s ref follows, and a function of type int -> int may print or update a cell as freely as Bridger’s g. ML programs are written mostly in the functional style, with mutation where it is convenient, and judging which laws apply is left to the programmer.

Rust records some of this in types. A Rust closure’s type says what it does to the variables it captured: one that only reads them implements the trait Fn, one that changes them FnMut, and one that consumes them FnOnce, and a function that takes a closure can demand the first. A closure that prints, or writes through a shared RefCell, is still an Fn, so the distinction tracks changes to captured variables, and printing falls outside it.

Bridger takes ML’s position for ordinary code and adds a checked judgment where the language’s own evaluation order is unspecified, in Part VII’s rule filters.

Intermediate lists

The pipeline version of total_withdrawn builds two lists that the program never names: the withdrawals, and their sizes. Bridger’s lists are values built in full as soon as they are computed, so a pipeline of $k$ stages over $n$ elements allocates up to $k-1$ intermediate lists of up to $n$ elements each, where the fused fold allocates none. Fusion by hand, as above, removes them, at the price of a combining function that does several things at once.

Other languages remove them without changing the program. Rust’s iterator adapters filter and map build nothing when they are called; they return an iterator that computes each element when the stage after it asks, so amounts.iter().filter(…).map(…).sum() runs as one loop. The Rust Programming Language states that “In Rust, iterators are lazy, meaning they have no effect until you call methods that consume the iterator to use it up,” and calls iterators “one of Rust’s zero-cost abstractions, by which we mean that using the abstraction imposes no additional runtime overhead.” Haskell’s lists are lazy, so an element of an intermediate list is computed only when something consumes it, and the compiler’s rewrite rules fuse many pipelines into loops before the program runs. Both depend on reordering the work of the stages: an element passes through every stage before the next element enters the first. The printing example above shows that reordering is exactly what an effect can observe. Rust’s iterators reorder anyway and leave the consequences to the programmer; Haskell reorders where nothing can observe it.

Modularity

John Hughes’s “Why Functional Programming Matters” (1989) makes the case for the style on different grounds from Backus’s. Its argument is about modularity. In the version of the paper on Hughes’s own site, “The ways in which one can divide up the original problem depend directly on the ways in which one can glue solutions together,” and functional languages “provide two new, very important kinds of glue”: higher-order functions and lazy evaluation. total_withdrawn as a pipeline is three parts, each of which can be written, tested, and replaced alone: a different predicate, a different measure, a different way of combining. The loop has the same three parts, written into one body and sharing one cell.

The fused fold is the loop again, in the form of a fold. The laws turn the modular version into the efficient one; a compiler that applies them, as GHC does, lets the programmer keep the first and run the second.

Further reading

Backus’s lecture: “Can Programming Be Liberated from the von Neumann Style?” (1978) contains the critique of von Neumann languages; the FP language, its functional forms, and programs for factorial, inner product, and matrix multiplication; the algebra of programs, with its list of laws and proofs that pairs of programs are equivalent; and, in Section 14, applicative state transition systems, a sketch of how the functional style could be made available in what Backus calls a “history-sensitive” system.

Modularity: Hughes’s “Why Functional Programming Matters” (1989), cited in evaluating function calls for its use of laziness, develops the higher-order half of its argument by separating a recursive list sum into a general recursion pattern and the parts specific to summing, then deriving a sequence of list and tree functions from the same pattern.

Laws in a compiler: Simon Peyton Jones, Andrew Tolmach, and Tony Hoare’s “Playing by the rules: rewriting as a practical optimisation technique in GHC” (Haskell Workshop, 2001) describes how a Haskell library states laws such as map fusion and how the compiler applies them.

Concept checks

fn flip(f: fn(Int, Int) -> Bool) -> fn(Int, Int) -> Bool = |x: Int, y: Int| f(y, x);
fn lt(x: Int, y: Int) -> Bool = x < y;
fn bu(f: fn(Int, Int) -> Bool, x: Int) -> fn(Int) -> Bool = |y: Int| f(x, y);

bu(flip(lt), 0)          // |y| lt(y, 0), that is, y < 0