First-Class Functions

A program from Part IV that adds up the squares of a list and a second program that adds up the cubes are the same loop with one line changed. Writing the loop once and handing it the line that differs requires two things. The loop has to be written somewhere that both programs can reach and given a name; and the line that differs — square this, cube this — has to become something that can be passed as a value, the same way a list is passed. Passing data between parts of a program is as old as stored-program computing; however, for years the code a program calls was treated as separate from the numbers it computed with—even if early machines stored data and code the same way. This chapter covers how programs started passing around code blocks (functions) as “first-class” values the same way as any other data a program computes with.

Subroutines

Herman Goldstine and John von Neumann’s Planning and Coding of Problems for an Electronic Computing Instrument (1948) wrote:

We call the coded sequence of a problem a routine, and one which is formed with the purpose of possible substitution into other routines, a subroutine.

and envisaged “an extensive collection of such subroutines” kept as a library on wire or tape. On the EDSAC the library was real: the relocation of Initial Orders 2, described in the history chapter, existed so that a library routine could be loaded wherever the store had room for it. What relocation did not solve is how a routine gets back. A routine reached by a jump has to finish by jumping to the order after the one that called it, and that order is in a different place for every caller.

The EDSAC’s answer, the Wheeler jump, used the fact that an order is a number. The addresses below come from a small program in Campbell-Kelly’s guide to the EDSAC, and they use the θ relocation of the history chapter: an address tagged θ counts from the start of the routine it appears in, and the loader adds that routine’s origin as the tape is read. The program’s master routine, loaded at 88, calls the library print routine P6, loaded at 56, with two orders:

 θ+7    A 7 θ      add the order at θ+7 — this order — into the accumulator
 θ+8    G 56 F     jump to the subroutine at 56

and the subroutine begins with two of its own:

 θ+0    A 3 F      add a constant kept in location 3: build the return jump
 θ+1    T 25 θ     store it at θ+25, the subroutine's exit: update the return jump

A 7 θ names its own position without the programmer knowing where that will be: loaded at 88, it arrives in the store as A 95 F, and reading location 95 reads the order itself. The subroutine’s address is written absolutely, G 56 F, because the programmer drew up a table placing each routine before the tape was punched, and location 3 lies inside the initial orders, which never move. Adding the fixed constant turns the copy of the calling order into a jump back to 97, the master routine’s θ+9, and the subroutine writes that jump into its own exit order. When the subroutine finishes it runs the updated return jump and lands after the call. The return address exists only while the call is in progress, as an order the routine wrote into itself — the self-modifying technique the history chapter showed loops using for arrays, applied to control.

David Wheeler’s two-page “The use of sub-routines in programmes” (1952) describes a sub-routine as “a self-contained part of a programme, which is capable of being used in different programmes,” and locates the hard part somewhere other than the coding: once a routine is written and tested, “there still remains the considerable task of writing a description so that people not acquainted with the interior coding can nevertheless use it easily. This last task may be the most difficult.” Its closing advice for building a library is “All complexities should—if possible—be buried out of sight.” The same paper describes an integration routine that is given “access to an auxiliary sub-routine which is capable of evaluating f(x)”: a routine whose job is only defined once it is handed another routine. That is the squares-and-cubes problem again, in 1952.

Functions and procedures

Fortran made routines part of its language, in two forms. Fortran I had functions in the sense that formulas already used — a sine or a square root, supplied by the system, written inside an arithmetic expression — and, documented in the 1957 addenda to its manual, a one-line function statement that let a program define its own, of the form FIRSTF(X) = A*X+B. A function was anything that could appear inside a formula and stand for one number. FORTRAN II, distributed in the spring of 1958, added separately compiled subprograms and a second kind of routine beside the function. A FUNCTION subprogram is used by writing its name in an expression; a SUBROUTINE is run by a CALL statement and produces its results by storing into its arguments, which it receives as locations. The FORTRAN II manual states the difference in two sentences:

A FUNCTION subprogram always produces a single result. A subroutine may produce as many results as are specified as arguments in the CALL statement.

The Algol 58 report drew the same line under different names: a function declaration declares an expression “to be a function of certain of its variables,” and a procedure declaration declares “a closed unit,” with input parameters, output parameters, and possible exits, “which may be regarded as a single compound operation (in the sense of a generalized function).” The Algol 60 report folded the two into the procedure. A procedure is called by a procedure statement; a procedure whose declaration carries a type, and whose body assigns to the procedure’s own name, may also be called inside an expression, where the call is a function designator and the last value assigned is its value. “Not every procedure declaration defines the value of a function designator.”

In all three languages, “function” names a position in the program — a call inside an expression, yielding one value — and “procedure” or “subroutine” names a call that stands as a statement. Neither word says whether the routine has effects. A Fortran function could change the variables it was handed, and an Algol function designator could assign to anything in scope, so evaluating f(x) + g(x) could give different answers depending on which call ran first. Some languages took the mathematical reading of the word and made it a rule. Niklaus Wirth’s 1970 report on Pascal, which kept procedure and function as separate declarations, put it plainly: “In order to eliminate side-effects, assignments to non-local variables are not allowed to occur within the function.” The Fortran 77 standard forbade a function reference from changing any other entity in the statement in which it appears, and required that its value not depend on the order in which the processor chose to evaluate the statement. Both rules protect the same freedom that Part II left open for +: an implementation may evaluate operands in any order only if no operand can see another’s effects.

C collapsed the two kinds into one. Every C routine is a function, and a routine called for its effect is a function whose result the caller ignores. The first edition of The C Programming Language (1978) had no word for “no result”; by Dennis Ritchie’s account it “mentioned neither the void or enum types,” both of which were in use well before the language was standardized. void gave the procedure a spelling of its own as a return type, without a second kind of declaration.

Second-class citizens

Being able to call a routine, from a statement or from an expression, still leaves open what else a program can do with it. In Algol 60 a procedure’s name could be passed as an argument to another procedure, so Wheeler’s integration routine could be written with its integrand as a parameter. It could do nothing else. A procedure could not be assigned to a variable, placed in an array, or returned as a result, and the report says why a procedure could not even be passed by value: procedure identifiers “do not possess values.”

Christopher Strachey’s 1967 lecture notes, Fundamental Concepts in Programming Languages, describe the asymmetry in a section titled “First and second class objects”:

In ALGOL a real number may appear in an expression or be assigned to a variable, and either may appear as an actual parameter in a procedure call. A procedure, on the other hand, may only appear in another procedure call either as the operator (the most common case) or as one of the actual parameters. There are no other expressions involving procedures or whose results are procedures. Thus in a sense procedures in ALGOL are second class citizens—they always have to appear in person and can never be represented by a variable or expression (except in the case of a formal parameter)…

The distinction between first- and second-class values is usually traced to these lectures. The test it sets is about the language rather than about any one program: is there anything a program may do with a number that it may not do with a function?

By 1967 a language that answered “no” had been running for years, on a notation older than any computer. Alonzo Church’s λ-calculus (introduced previously) has only functions, and writes one without naming it: $\lambda x.x+1$ is the function that adds one, an expression like any other that can be an argument to another function or the result of one. John McCarthy borrowed the notation for Lisp, and in his history of the language, written for the first History of Programming Languages conference, gives the reason:

To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions.

Lisp’s maplist applied a function given as an argument to each element of a list — the squares-and-cubes loop, written once. What a Lisp function value had to carry with it, and what Lisp at first got wrong about it, is the subject of a later chapter (cf. static and dynamic scope).

Functions as values in Bridger

In Bridger a function is a value. It can be bound by let, passed to another function, returned from one, and stored in a tuple, a list, or a cell, exactly as an integer can:

fn square(x: Int) -> Int = x * x;

fn twice(f: fn(Int) -> Int, x: Int) -> Int = f(f(x));

fn pick(double: Bool) -> fn(Int) -> Int {
    if double { |x: Int| x * 2 } else { |x: Int| x + 1 }
}

fn main() {
    let inc = |x: Int| x + 1;
    println(twice(inc, 5));                        // 7
    println(twice(square, 3));                     // 81
    let ops = [inc, square, pick(true)];
    println(map(ops, |g: fn(Int) -> Int| g(10)));  // [11, 100, 20]
    let cell = ref inc;
    cell := square;
    println((deref cell)(7));                      // 49
}

There are two ways to make a function value. A top-level fn declaration binds a name to one: square on its own, without an argument list, is an expression whose value is the function, and it is passed to twice in the same way inc is. A lambda, written |x: Int| x + 1, is an expression that produces a function without naming it — Church’s $\lambda x.x+1$ in Rust’s notation — and can appear anywhere an expression can: as a let’s right-hand side, as an argument, as a branch of an if. The parameter annotations and the type fn(Int) -> Int are read by the type checker of Part VI; the evaluator ignores them.

The prelude’s map, filter, and fold take a function argument, and the functions they are handed are ordinary values; so is map itself. The squares-and-cubes problem needs nothing more:

fn sum_of(f: fn(Int) -> Int, xs: [Int]) -> Int =
    fold(xs, 0, |acc: Int, x: Int| acc + f(x));

sum_of(square, range(1, 4))                        // 1 + 4 + 9 = 14

A Bridger function called for its effect is a function like any other. Bridger is expression-oriented: a form evaluated for its effect produces (), the value that reports only that the effect happened. A procedure is therefore a function whose result is (), and a declaration that omits its result type has result type ():

fn log(msg: String) {
    println("log: " ++ msg);
}

There is one kind of declaration; the Fortran II distinction survives as a type, () against everything else, and a procedure can be passed wherever a function is expected.

There are two things a program can do with an integer and cannot do with a function. Comparing two functions with == is stuck, for the reason Part II gave — no interpreter can decide in general whether two functions agree on every input — and a function has no printed form. Strachey’s test is about expressions and variables, and Bridger’s functions pass it; they are values without being data that can be inspected.

What a lambda evaluates to

Evaluating a lambda runs nothing. Its body is code to be run later, when the function is called, and until then it is not evaluated at all:

let never = |x: Int| x / 0;        // fine: nothing is divided

The division would be stuck, but no rule reaches it until never is applied to something.

What a lambda does record is the place it was evaluated. Its body may mention names that it does not bind — f in sum_of’s |acc: Int, x: Int| acc + f(x) is bound by sum_of’s parameter list, outside the lambda. These are the free occurrences of Part III, and Bridger’s lexical scope resolves each in the environment where the code is written. Until now, code always ran where it was written: a block’s body is evaluated in the environment the block extends, and nowhere else. A function body is the first code that runs somewhere else — wherever the function is called, which may be inside fold, or long after the block that built the function has finished. For the body’s free names to keep meaning what they meant where it was written, the function value has to take that environment with it. It does:

$$\frac{}{\rho ⊢⟨\lambda \vec{x}.e,\sigma ⟩\Downarrow ⟨⟨\lambda \vec{x}.e,\rho ⟩,\sigma ⟩}(\text{E-Lam})$$

The rule has no premises, since nothing is evaluated, and the store is handed back unchanged. The value $⟨\lambda \vec{x}.e,\rho ⟩$ is a closure: the parameters, the body, and the environment in force when the lambda was evaluated. A top-level fn evaluates by E-Var: the program’s environment binds its name to a closure whose environment is the program’s environment, which is how top-level functions can call one another (cf. recursion).

How a call uses the captured environment is the rule for application, in the next chapter. What the capture makes possible — a function that outlives the call that created it — is the subject of closures.

Building it

The AST node and the value it produces are both provided. A lambda is Expr::Lambda, whose parameters carry an optional type annotation; its value is the Closure variant of Value, which holds a shared pointer to one of two kinds of function:

Expr::Lambda(Vec<LambdaParam>, Box<Expr>, Span)

pub struct LambdaParam { pub name: Name, pub ty: Option<Ty>, pub span: Span }

Value::Closure(Rc<Closure>)

pub enum Closure {
    Bridger { params: Vec<Name>, body: Expr, env: Env },  // a lambda or a `fn`
    Native(BuiltinId),                                    // a prelude primitive
}

The Lambda arm of eval_expr is E-Lam: it builds a Closure::Bridger from the parameter names (the annotations are Part VI’s business and are dropped), a copy of the body, and the environment the arm was handed, and returns it as a Value::Closure. It evaluates nothing and cannot fail. Holding the environment is cheap: an Env is the shared chain of scopes chosen in Part III so that it could be captured without being copied.

Top-level functions need no arm of their own. The provided eval_program binds every fn to a Closure::Bridger whose env is the program environment before main runs, and the prelude’s built-in primitives — println, the readers — arrive as Closure::Native, so map(xs, println) passes a primitive exactly as it passes a lambda.

The design space

Whether a language has one kind of routine or two is a choice about what a call is allowed to mean. Fortran II and Pascal keep functions and procedures apart, and a reader who sees a call in an expression knows it yields one value; Pascal’s rule on non-local assignment goes further and tells the reader the call cannot disturb the expression around it. The cost is a second declaration form and, in Pascal’s case, a restriction that forbids a function from updating a counter or caching a result. C, ML, Rust, and Bridger have one kind of routine and mark a procedure by its result type — void in C, a unit type in the others — so a procedure can be passed wherever a function is expected, and map over a list with a printing function needs no special case. What they give up is the guarantee: a call in an expression may have any effect a statement could. Bridger answers the evaluation-order question by fixing the order, left to right, through the threaded store, rather than by restricting what a function may do. Languages that record effects in a function’s type, so that “this call does nothing but compute a value” is checked, are among the alternatives taken up with programming functionally.

How far a routine is a value is a second axis. Algol 60 and Pascal let a procedure be passed as an argument and nothing more. C lets a function be named by a pointer, and a pointer can be stored, passed, and returned — but C has no nested functions, so every name a function body mentions is either its own local or global to the whole program, and the pointer needs to carry nothing but the code’s address. The Lisp line, and then Scheme, ML, and Haskell, made functions values with no restrictions and a captured environment, and most languages in wide use now do the same — Python, JavaScript, C#, Rust, and Java since version 8. The restricted designs are simpler to implement for a concrete reason. A procedure passed down to a routine it calls is used while the procedure’s defining environment still exists, so a pointer to that environment on the call stack stays valid; a procedure returned up past its defining call, or stored somewhere that outlives it, carries a pointer to an environment that the stack has already discarded. Allowing that requires environments that live as long as any function refers to them, which is what Bridger’s shared Env provides and what closures examines.

Bridger takes the unrestricted end of both axes: one kind of routine, with () for procedures, and function values that are passed, returned, and stored with their environments. It stops short of treating functions as data — no equality and no printing — because neither has an answer that describes the function rather than its representation.

Further reading

Subroutines: Goldstine and von Neumann’s Planning and Coding of Problems for an Electronic Computing Instrument, Part II, Volume III (1948), sets out the subroutine and the library of them in §12 before any machine to run them had been built. Wheeler’s “The use of sub-routines in programmes” (1952) is two pages long and covers the EDSAC’s closed sub-routines, the library, interpretive routines, and the problem of describing a routine to the people who will use it. The calling sequence of the Wheeler jump is laid out order by order in Martin Campbell-Kelly’s Tutorial Guide to the EDSAC Simulator, where it can be run.

Functions and procedures in the first languages: Backus’s “The History of Fortran I, II, and III” (1978) records how function statements, and then separately compiled SUBROUTINE and FUNCTION subprograms, came into Fortran, and the FORTRAN II Reference Manual (IBM, 1958) gives the calling conventions down to where each argument’s address is found. The Algol 58 report and the Revised Report on Algol 60 (1963) show the function and the procedure as separate declarations and then as one; §4.7 and §5.4 of the latter define procedure statements, function designators, and the call-by-name rule taken up in the next chapter. Wirth’s “The Programming Language Pascal” (Acta Informatica, 1971) is the published form of the Pascal report, with procedure and function declarations in separate sections.

First-class functions: Strachey’s Fundamental Concepts in Programming Languages, lecture notes from 1967 first published in 2000, covers first- and second-class objects in §3.5.1 alongside l-values and r-values, parametric polymorphism, and the other terms it put into circulation. McCarthy’s “History of Lisp” (1979) describes borrowing Church’s notation and the first programs that passed functions as arguments. Church’s own account is The Calculi of Lambda-Conversion (Annals of Mathematics Studies 6, Princeton University Press, 1941).

Concept checks