Recursion and Higher-Order Functions

The functions of this part so far have called other functions. This one calls itself. fact computes the factorial of a non-negative integer, $n!=n\times (n-1)\times \cdots \times 1$, with $0!=1$:

fn fact(n: Int) -> Int = if n == 0 { 1 } else { n * fact(n - 1) };

fn main() {
    println(fact(5));                                   // 120
}

The body of fact mentions fact. fact(5) evaluates 5 * fact(4), which needs fact(4), and so on down to fact(0), which is 1 without another call. The same definition written as a lambda inside main does not run:

fn main() {
    let fact = |n: Int| if n == 0 { 1 } else { n * fact(n - 1) };
    println(fact(5));                         // UnboundVariable fact
}

A function that counts its way through a range shows a third behaviour. sum_to(n) adds the integers from 1 to n:

fn sum_to(n: Int) -> Int = if n == 0 { 0 } else { n + sum_to(n - 1) };

fn main() {
    println(sum_to(10000));                             // 50005000
    println(sum_to(1000000));                           // StackOverflow
}

Nothing is wrong with the arithmetic of the second call; the prelude’s fold(range(1, 1000001), 0, |acc: Int, x: Int| acc + x) computes the same sum, 500000500000.

The three programs raise these questions:

• How does the body of fact find fact? A body runs in the environment its closure captured. For the call fact(n - 1) to work, that environment has to hold the closure that captured it.
• Why does the lambda in main fail, and can it be repaired? Is self-reference something a language has to provide, or can a program build it from functions it already has?
• What does each level of a recursion cost? What stops sum_to(1000000), and is there a way to write a recursive function that does not pay it?

The first languages to allow a function to call itself had to answer the first question in their notation and the third in their implementation.

A function that names itself

The program John McCarthy wanted to write in 1958 was a symbolic differentiator, and the language he first tried to write it in, FLPL, was a set of list-processing subroutines for Fortran. In his “History of Lisp” (1979) he recalls that the program “was not implemented that summer, because FLPL allows neither conditional expressions nor recursive use of subroutines.” Differentiating a sum means differentiating each of its terms, and the natural way to write that is a function that calls itself on the parts of an expression. The same history credits the differentiator with Lisp’s maplist, the function that applies a functional argument to each element of a list.

Fortran’s restriction held for a long time. The FORTRAN 77 standard (§15.2) still says: “A subprogram must not reference itself, either directly or indirectly.” Fortran 90 added a keyword, RECURSIVE, that a procedure must carry if it calls itself, so recursion there became something a procedure declares.

McCarthy’s paper “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (1960) wrote functions in Church’s λ-notation, and the notation had a gap. A λ-expression denotes a function without naming it, so a function written that way has no name to call itself by. The paper (§2f) says so directly: “The λ-notation is inadequate for naming functions defined recursively.” Its repair was a second binder, label: $label(a,\mathcal{E})$ stands for the expression $\mathcal{E}$, with each occurrence of $a$ inside $\mathcal{E}$ referring to the whole expression. In the history, McCarthy credits the notation to Nathaniel Rochester, and records that it was not strictly needed:

Logical completeness required that the notation used to express functions used as functional arguments be extended to provide for recursive functions, and the LABEL notation was invented by Nathaniel Rochester for that purpose. D.M.R. Park pointed out that LABEL was logically unnecessary since the result could be achieved using only LAMBDA - by a construction analogous to Church’s Y-operator, albeit in a more complicated way.

The implementation needed a place for the variables of each active call. A routine whose locals sit in fixed locations can have one call in progress at a time, the limit the Wheeler jump of first-class functions ran into with its return address. Lisp’s first implementers, McCarthy writes, “decided to use SAVE and UNSAVE routines that use a single contiguous public stack array to save the values of variables and subroutine return addresses in the implementation of recursive subroutines.” Edsger Dijkstra’s “Recursive Programming” (1960) made the same structure the organizing idea of an implementation for Algol 60. A routine that keeps its working storage in fixed places, he wrote, cannot be called “while one or more previous activations of the same subroutine have not yet come to an end, without losing the possibility of finishing them off properly later on.” A stack gives each activation its own storage, and the activation records that closures described are its entries.

Park’s remark is the subject of the next section: a language that has λ already has recursion, if it is willing to let a function be applied to itself.

Recursion as a fixed point

Start from the failing lambda. Its body needs a function to call for the smaller case, and nothing in scope provides one. A parameter can provide one. Give the lambda an extra parameter, me, and call me where the body called fact:

let f = |me, n| if n == 0 { 1 } else { n * me(me, n - 1) };
println(f(f, 5));                                       // 120

f(f, 5) runs the body with me bound to f itself and n to 5. The recursive case calls me(me, 4), which is f(f, 4): the same function, handed itself again, so that it can make the next call in turn. Each call passes the function down to the next. Nothing in the program refers to itself by name; each closure captures main’s environment, which has no f in it while the lambda is being built, and the self-reference travels as an argument. (The parameter is me because self is a reserved word in Bridger, kept for the methods of Part IX.)

The equation fact solves

The extra argument clutters the body. Separate the part that describes one step of factorial from the part that ties it to itself. One step, given some function me to use for the smaller case, is

$$F=\lambda me.\lambda n.\text{if}n=0\text{then}1\text{else}n\times me(n-1)$$

$F$ is not recursive. Handed a function, it returns a new function that handles 0 itself and passes every other case to the one it was handed. Handed a function that computes factorial, it returns a function that also computes factorial: the two agree on every input. Written as an equation,

$$fact=F(fact)$$

A value $x$ with $x=F(x)$ is a fixed point of $F$, and factorial is a fixed point of the one-step function $F$. Every recursive definition can be read this way: replace each recursive call with a call to a parameter, and the function being defined is the one that the result leaves unchanged.

A fixed-point combinator is a function fix that, given any such $F$, produces a fixed point of it, so that $fix(F)=F(fix(F))$. The one usually written $Y$ is

$$Y=\lambda g.(\lambda x.g(xx))(\lambda x.g(xx))$$

Apply it to $F$ and take one step, substituting the second $\lambda x.F(xx)$ for $x$ in the first:

$$YF\to (\lambda x.F(xx))(\lambda x.F(xx))\to F((\lambda x.F(xx))(\lambda x.F(xx)))$$

The argument handed to $F$ on the right is the expression on the left, so $YF$ unfolds to $F(YF)$ one step at a time. The function is applied to itself, x x, as f was applied to itself above; $Y$ is that trick with the one-step function factored out. Haskell Curry and Robert Feys’s Combinatory Logic (1958) calls $Y$ the paradoxical combinator, and McCarthy’s “Church’s Y-operator” is the same construction.

Fixed points under call by value

Written in Bridger, $Y$ does not produce factorial:

let y = |g| (|x| g(x(x)))(|x| g(x(x)));
let fact = y(|me| |n| if n == 0 { 1 } else { n * me(n - 1) });
                                                // StackOverflow at x(x)

The reason is the evaluation order that E-App fixes. A call evaluates its arguments before it runs the body, so g(x(x)) evaluates x(x) before g is ever called; x(x) is a call whose body is g(x(x)) again, which evaluates x(x) again. The unfolding that the reduction above performs one step at a time on demand, call by value performs eagerly and without end, and no call of g is ever reached. Under the call by name of Algol 60, the argument would be passed unevaluated, and $Y$ would work as written.

The repair is to hand g something whose evaluation runs nothing. A lambda is such a thing, by E-Lam. Wrap x(x) in a lambda that calls it only when it is itself called, |v| x(x)(v), and the result is the fixed-point combinator for call by value, often written $Z$:

$$Z=\lambda g.(\lambda x.g(\lambda v.xxv))(\lambda x.g(\lambda v.xxv))$$

let fix = |g| (|x| g(|v| x(x)(v)))(|x| g(|v| x(x)(v)));
let fact = fix(|me| |n| if n == 0 { 1 } else { n * me(n - 1) });
let fib = fix(|me| |n| if n < 2 { n } else { me(n - 1) + me(n - 2) });
println(fact(5));                                       // 120
println(fib(10));                                       // 55

fix takes the step functions and nothing else. Neither fact nor fib mentions its own name, and fix mentions no function but its argument; the recursion is built out of λ alone, as Park said it could be. It costs something. Each level of fact built this way passes through me, the self-application x(x), and g before it reaches the step’s body, and holds two frames at once where the top-level fact holds one: a sum written with fix runs 49 990 levels deep and fails at 50 010.

The program’s environment is a fixed point

The top-level fact is a fixed point too, of a different function. Appendix D defines the program’s environment ${\rho }_0$ by a condition that mentions ${\rho }_0$ on both sides:

$${\rho }_0\supseteq [f\mapsto ⟨\lambda \vec{x}.e_f,{\rho }_0⟩|(\text{fn}f(\vec{x})=e_f)\in prog]$$

Each top-level function is a closure whose captured environment is ${\rho }_0$, and ${\rho }_0$ holds each of those closures. Read as an equation, ${\rho }_0$ is a fixed point of the function that takes an environment and builds a closure over it for every fn in the program. When the body of fact reaches fact(n - 1), E-Var looks fact up in ${\rho }_0$ extended with n, finds the closure, and E-App runs its body in ${\rho }_0$ extended again. Nothing about the call is special; the environment already contains what the body needs.

The lambda in main has no such environment. E-Let evaluates its right-hand side in the environment before the binding, so E-Lam captures an environment that has no fact, and the binding added afterward is outside the closure’s reach.

Bridger’s recursion

Bridger provides recursion through the program’s environment and nowhere else. A top-level fn may call itself and every other top-level fn, whichever is written first. A let-bound lambda cannot call itself, as the environments chapter decided when it gave E-Let its scope. There is no let rec.

A program that wants a recursive function inside a block has two ways to build one from what the language already has. The first is the fixed-point combinator above. The second ties the knot through the store, using a reference cell: allocate a cell holding a placeholder function, then overwrite it with a function whose body calls whatever the cell holds.

let r = ref (|n: Int| 0);
r := (|n: Int| if n == 0 { 1 } else { n * (deref r)(n - 1) });
println((deref r)(5));                                  // 120

The lambda captures r, which is in scope because the cell was bound first. By the time the body runs, the cell holds the lambda itself, and (deref r)(n - 1) calls it. (A lambda on the right of := needs parentheses.)

Building it

There is no new evaluator arm in this chapter. The Var and Call arms of the last two chapters already run fact, is_even, and the knot through the store, and f(f, 5) and fix are lambdas and calls like any other.

${\rho }_0$ is provided. It is built the way the knot through the store is: the interpreter makes the program’s root scope first, with no functions in it, and then installs each top-level fn as a closure that captures that root.

impl Env {
    /// Install a top-level `fn` as a Bridger closure that captures *this*
    /// root environment.
    pub(crate) fn add_function(&self, name: Name, params: Vec<Name>, body: Expr);
}

The root’s bindings sit behind a RefCell so they can be added after the root is shared. When the last fn is installed, every closure in the root points to the root, which holds every closure: ${\rho }_0$, built by allocating the environment and then filling it in. As closures observed, this is the one reference cycle in the environments, and it lasts as long as the program does.

What a level costs

A call’s body is bracketed by enter_call and leave_call (evaluating function calls), and between them it holds a frame: a count of nested Bridger calls in progress. Every application of a top-level function, a lambda, or a method opens one, and enter_call refuses to open more than 100 000:

pub const MAX_DEPTH: usize = 100_000;

sum_to(1000000) needs a million frames at once. sum_to(n) cannot finish until sum_to(n - 1) has returned a value to add n to, so every level stays open until the bottom is reached. The evaluator reports StackOverflow at the call that would have opened the 100 001st frame.

The limit stands in for one the evaluator cannot otherwise control. Your eval_expr is a recursive Rust function, and a single Bridger call is several nested Rust calls of it, each with a frame on the Rust stack. Running out of that stack aborts the whole interpreter process without a Bridger error or a span. The provided main runs the interpreter on a thread with a 2 GiB stack, and the frame count stops a Bridger program well before that stack is exhausted, with an error that points at the call. The prelude’s map, filter, and fold are native: they iterate over their list in Rust and open no frames of their own, which is why the fold over a million elements in the opening ran. The function handed to them opens one per call, and returns before the next.

Recursive higher-order functions

A higher-order function can be recursive. fold_range folds a function over the integers from lo up to hi, as the prelude’s fold would over range(lo, hi):

fn fold_range(lo: Int, hi: Int, z: Int, f: fn(Int, Int) -> Int) -> Int =
    if lo >= hi { z } else { fold_range(lo + 1, hi, f(z, lo), f) };

fold_range(1, 5, 0, |acc: Int, x: Int| acc + x)         // 10
fold_range(1, 6, 1, |acc: Int, x: Int| acc * x)         // 120

Factorial and the sum are each one fold_range with a different step. fold_range names the recursion once and takes what varies as an argument: the starting value and the function that combines it with each integer. Graham Hutton’s tutorial on fold (1999) describes fold as a “standard operator that encapsulates a simple pattern of recursion for processing lists”. Recursion over a list itself needs a way to take a list apart into its first element and the rest, which is the pattern matching of Part VIII; with it, map, filter, and fold can be written in Bridger in a few lines each.

fold_range differs from sum_to in where its recursive call sits. sum_to’s call is an operand of +, so the caller still has work to do when it returns. fold_range’s call is the result: when it returns, its caller returns the same value and does nothing else. A call in that position is a tail call. Bridger gives tail calls no special treatment. fold_range(0, 1000000, 0, …) would hold a million frames, one per pending call with nothing left to do, and it stops with StackOverflow where fold(range(0, 1000000), …) runs.

The design space

Binding a recursive name

Languages place the recursive binding in different forms. ML and OCaml use let rec, a separate form whose name is in scope in its own right-hand side; Scheme’s letrec does the same and environments mentioned both. In Haskell every let and where binding is recursive, so the failing lambda in main would work there as written; the cost is that let x = x + 1 is a definition of x in terms of itself rather than a reference to an outer x. Rust lets a function item be declared inside a block, where it can call itself, but such an item cannot capture the block’s local variables; a Rust closure can capture them and cannot name itself. Bridger’s arrangement is the same split at a larger grain: the top level provides recursion, the lambda provides capture.

A language can also leave the binding alone and provide the fixed point. The step function $F$ above is an ordinary non-recursive function, and a primitive fix with the property $fix(F)=F(fix(F))$ gives every recursive definition in terms of one construct. Typed calculi used in the theory of programming languages often take this route, for the reason the next subsection gives.

Recursion and types

Part VI’s checker accepts the top-level fact, the knot through the store, and fold_range. It rejects f(f, 5), $Y$, and $Z$, each with the same error: cannot construct the infinite type. In me(me, n - 1), me is called with itself as an argument. If me had a type $T$, that type would have to be a function type whose first parameter is $T$: $T=\text{fn}(T,\text{Int})\to \text{Int}$. No type written with finitely many fns satisfies that equation, since substituting the right side into itself never ends. Every self-application has the same problem.

A type system like Part VI’s therefore cannot express recursion with λ alone, and a typed language supplies recursion as a construct of its own: recursive top-level declarations, let rec, or a primitive fix. In Bridger the top-level fn is that construct. The fixed-point combinators of this chapter run on the M4 evaluator, which checks nothing before it runs, and stop running once the checker arrives.

Tail calls

Guy Steele’s MIT memo “Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO” (1977) argued that a call with nothing left to do after it needs no frame of its own:

In this way, if the last thing a procedure does is call another (external) procedure, that call can be compiled as a GOTO. Such a call is called tail-recursive, because the call appears to be recursive, but is not, since it appears at the tail end of the caller.

The caller’s frame is no longer needed, so the callee can reuse it, and a chain of tail calls runs in the space of one frame. Scheme made this a requirement of the language. The R7RS report (§3.5) states that “Implementations of Scheme are required to be properly tail-recursive”, and gives the consequence in its overview (§1.1): “iteration can be expressed using the ordinary procedure-call mechanics, so that special iteration constructs are useful only as syntactic sugar.” In Scheme, fold_range is a loop.

The 2015 edition of ECMAScript specified the same guarantee for JavaScript’s strict mode (§14.6, “Tail Position Calls”). WebKit’s announcement of its implementation, “ECMAScript 6 Proper Tail Calls in WebKit” (2016), described the requirement — “such a call must reuse the stack space of its own frame instead of pushing another frame onto the call stack” — and its effect on debugging: “the tail deleted function will not show up in a stack trace.” V8’s team reported the same year that proper tail calls had “been implemented but not yet shipped”, and the flags were later removed.

Python’s designer declined it. In “Tail Recursion Elimination” (2009) Guido van Rossum gave the stack trace as the first reason: “when a tail recursion is eliminated, there’s no stack frame left to use to print a traceback when something goes wrong later”, and “Python’s default is and should always be to be maximally helpful for debugging.” Python instead bounds the depth, as Bridger does; its documentation says the limit “prevents infinite recursion from causing an overflow of the C stack and crashing Python.” Rust makes no guarantee either; an explicit form, a become keyword that the programmer writes in place of return to demand a tail call, has been proposed and exists as an experiment in the nightly compiler.

Bridger sides with the stack trace. Every call holds a frame until it returns, and a StackOverflow points at the call that would have gone deeper. Eliminating tail calls in a tree-walking evaluator is a change to the Call arm. A call in tail position would stop short of running its body and pass the closure and its arguments outward, through the control channel that already carries return, to the Call arm whose body it ends. That arm would run its body in a loop: on receiving a tail call, it would bind the new arguments and go around again, without a nested call of eval_expr, so neither the frame count nor the Rust stack would grow. Bridger’s semantics would say nothing different about such a program’s value; only the depth at which it fails would change.

Further reading

Recursion in early Lisp: McCarthy’s “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (1960) defines its functions by conditional expressions and recursion and introduces label in §2f; the author’s retyped copy is at jmc.stanford.edu. His “History of Lisp” (1979) describes the differentiation program, FLPL’s limits, maplist, LABEL, and the stack the first implementation used.

The stack: Dijkstra’s “Recursive Programming” (1960) describes a stack-based implementation of procedure calls, including the treatment of parameters and of procedures that call themselves; a scan of the journal printing is in the CWI repository.

Fixed points: Daniel Friedman and Matthias Felleisen’s The Little Schemer (4th ed., MIT Press, 1996), chapter 9, arrives at the call-by-value $Y$ by repeatedly removing the name from a recursive length function, in the book’s question-and-answer format.

Fold: Hutton’s “A tutorial on the universality and expressiveness of fold” (Journal of Functional Programming, 1999) uses one property of the right fold over lists to turn recursive functions into folds and to prove facts about them, and shows how much a fold can compute once it may return tuples and functions.

Tail calls: Steele’s “Lambda: The Ultimate GOTO” (1977) memo makes the case for compiling a procedure call as a jump with arguments, with examples in Lisp and in compiled code. Van Rossum’s first post and his follow-up, “Final Words on Tail Calls” (2009), give the case against, and the comments under each argue it.

Concept checks

fn is_even(n: Int) -> Bool = if n == 0 { true } else { is_odd(n - 1) };
fn is_odd(n: Int) -> Bool = if n == 0 { false } else { is_even(n - 1) };