Tail call

A tail call is a call made as the last action of a function: the caller returns the callee's result unchanged. Since the caller has nothing left to do, its stack frame is no longer needed, and the call can be compiled as a jump that reuses the frame^[1]. A language implementation that does this for every tail call is properly tail recursive^[2], and in it a loop can be written as a recursive function without the stack growing. Scheme requires proper tail recursion^[3], and OCaml and most functional languages provide it; the Java virtual machine, Python and most JavaScript engines do not.

§ 01

Overview

When a function calls another, the caller's state, its local variables and where to resume, is saved in a stack frame until the callee returns. If the call is the caller's last action, nothing will be done with that saved state except to pass the result on, and the callee can return straight to the caller's caller. A function whose recursive calls are all tail calls then runs in constant stack space, like a loop:

Summing a list with a non-tail call and with a tail call.

(* The addition happens after the recursive call returns: not a tail call. *)
let rec sum = function [] -> 0 | x :: xs -> x + sum xs
 
(* The running total is passed along; the recursive call is the last
   thing the function does. *)
let rec sum_acc acc = function [] -> acc | x :: xs -> sum_acc (acc + x) xs

Running it on ten million elements with an 8 MB system stack.

sum_acc 0 xs  ->  49999995000000
sum xs        ->  Stack_overflow

In sum the addition waits for the recursive call, so every element of the list has a frame on the stack when the end is reached. In sum_acc the partial sum is passed in an accumulator, the recursive call is the last thing the function does, and the stack does not grow. The limit that sum runs into is set by the runtime. In OCaml 4 it is the system stack, 8 MB here; in OCaml 5 it is a separate limit on OCaml's own stacks, the l parameter of OCAMLRUNPARAM, 1 GiB by default. The length of list at which sum fails depends on that limit; sum_acc runs on a list of any length.

§ 02

Tail position

Whether a call is a tail call is a syntactic property of where it appears. The tail positions of an expression are defined by induction: the body of a function is in tail position, and

if e_{1} then e_{2} else e_{3} let x = e_{1} in e_{2} e_{1}; e_{2} match e with p_{1} \to e_{1} ∣ \dots ∣ p_{n} \to e_{n} e_{1} && e_{2} e_{1} || e_{2}

where the underlined subexpressions are in tail position if the whole expression is. A call in tail position is a tail call. The arguments of a call and the operands of an operator are never in tail position, and neither is the body of try … with, because the exception handler must remain installed until the body has returned. OCaml checks the expectation that a call is a tail call when it is marked with the [@tailcall] attribute:

Two calls marked as expected tail calls, neither of which is.

let rec sum = function [] -> 0 | x :: xs -> x + (sum [@tailcall]) xs
 
(* A call inside the body of try ... with is not in tail position: the
   handler has to stay installed until the call returns. *)
let rec find_index p i = function
  | [] -> raise Not_found
  | x :: xs -> try if p x then i else (find_index [@tailcall]) p (i + 1) xs with Exit -> -1

The compiler's warnings.

File "t3_warn.ml", line 1, characters 48-68:
1 | let rec sum = function [] -> 0 | x :: xs -> x + (sum [@tailcall]) xs
                                                    ^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall
File "t3_warn.ml", line 7, characters 38-75:
7 |   | x :: xs -> try if p x then i else (find_index [@tailcall]) p (i + 1) xs with Exit -> -1
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

The second case is a common mistake in OCaml: wrapping a recursive loop in an exception handler at every step makes each iteration keep a frame. The usual fix is to handle the exception outside the loop, or to use match … with exception, whose exception branch covers only the matched expression, so that the recursive call in a value branch stays in tail position.

§ 03

Implementation

A tail call is compiled by placing the callee's arguments where the callee expects them, releasing the caller's frame, and jumping to the callee instead of calling it. A self-recursive tail call becomes a jump to the start of the function, which is a loop. The code that OCaml's native compiler generates for sum_acc has no call at all:

The core of the x86-64 code for sum_acc, abridged, with comments added.

camlT2_loop__sum_acc:
        ...
.L101:  ...                        # (entry of the loop)
        testb   $1, %bl            # empty list?
        je      .L100
        ...
        ret                        # return acc in %rax
.L100:
        movq    8(%rbx), %rdi      # xs
        movq    (%rbx), %rbx       # x
        leaq    -1(%rax,%rbx), %rax  # acc + x, on tagged integers
        movq    %rdi, %rbx
        jmp     .L101              # the recursive call

Steele argued in 1977 that procedure calls had a reputation for being expensive because of how they were implemented, and that a call in tail position is a "GOTO that passes arguments"^[1]. Tail calls to other functions, not only to the function itself, are also jumps, so mutually recursive functions run in constant space as well. A finite-state machine can be written with one function per state and one tail call per transition:

A state machine that tests binary numbers for divisibility by three, and mutually recursive even and odd.

(* Tail calls between different functions: a state machine where each
   state is a function and each transition a tail call. It recognizes
   binary numbers divisible by three, reading bits left to right; the
   state is the remainder so far. *)
let rec r0 s i = if i = String.length s then true else if s.[i] = '0' then r0 s (i + 1) else r1 s (i + 1)
and r1 s i = if i = String.length s then false else if s.[i] = '0' then r2 s (i + 1) else r0 s (i + 1)
and r2 s i = if i = String.length s then false else if s.[i] = '0' then r1 s (i + 1) else r2 s (i + 1)
 
let rec even n = n = 0 || odd (n - 1)
and odd n = n <> 0 && even (n - 1)

Running it.

  9 = 1001     divisible by 3: true
 10 = 1010     divisible by 3: false
 21 = 10101    divisible by 3: true
100 = 1100100  divisible by 3: false
255 = 11111111 divisible by 3: true
10,000,000 ones: divisible by 3: true
even 100_000_001 -> false

If a callee needs more space for its arguments on the stack than the caller received, the caller's frame cannot simply be reused; calling conventions in which the callee removes its own arguments, or which pass arguments in registers, avoid the problem. In continuation-passing style every call is a tail call, and compilers that use CPS as their intermediate language rely on them being jumps^[14].

§ 04

Proper tail recursion

Clinger made the requirement precise by defining it as a property of space consumption: an implementation is properly tail recursive if it runs every program in no more space, up to a constant factor, than a reference machine that never keeps frames for tail calls^[2]. The definition matters because it constrains the implementation, not the program: in a properly tail-recursive language, an unbounded loop written as tail recursion is correct, and in one that is not, it is a program that fails on large inputs. Abelson and Sussman distinguish accordingly between a recursive procedure, one that calls itself, and a recursive process, one whose execution needs space for deferred operations; a tail-recursive procedure generates an iterative process^[5].

Accumulators

A function that performs work after its recursive call can often be made tail recursive by passing that work forward in an extra argument, as sum_acc does. When the pending work is an associative operation with a unit, such as addition, the accumulator holds the partial result:

sum (x :: x s) = x + sum x s ⇝ sum_acc a (x :: x s) = sum_acc (a + x) x s, sum x s = sum_acc 0 x s

where correctness is the invariant $sum_acc a x s = a + sum x s$ . When it is not, the accumulator has to hold a representation of the pending work, which in general is a continuation: converting a function to continuation-passing style makes every call a tail call, at the cost of allocating closures on the heap in place of frames on the stack.

§ 05

Tail recursion modulo cons

Many functions that build a list are not tail recursive only because of a constructor applied to the recursive result, as in map: f x :: map f xs. The constructor could be allocated before the call with a hole where the tail goes, and the call could fill in the hole, after which the call is the last action. This transformation, tail recursion modulo cons, has been known since the 1970s, and OCaml performs it, since version 4.14, for functions annotated with [@tail_mod_cons]^[6]^[7]:

map, map with tail recursion modulo cons, and map by reversing an accumulated list.

(* map is not tail recursive: the cons waits for the recursive call. *)
let rec map f = function [] -> [] | x :: xs -> f x :: map f xs
 
(* With [@tail_mod_cons] the compiler allocates the cons cell first, with
   a hole for its tail, and passes the hole to the recursive call, which
   fills it in. The call becomes a tail call. *)
let[@tail_mod_cons] rec map_trmc f = function [] -> [] | x :: xs -> f x :: map_trmc f xs
 
(* The usual alternative: an accumulator, and a reversal at the end. *)
let map_rev f xs = List.rev (List.rev_map f xs)

Running it on ten million elements with an 8 MB system stack.

map       ->  Stack_overflow
map_trmc  ->  10000000
map_rev   ->  10000000

The transformed function writes into a block after it has been allocated, which is safe because the block is not visible to any other code until the function returns. The standard library's List.map and several other list functions have been defined this way since OCaml 5.1. The alternative of accumulating the result in reverse and reversing it at the end also runs in constant stack space, but traverses the list twice and allocates it twice.

§ 06

In programming languages

Scheme was the first language to require proper tail recursion, in its definition from 1975^[4]^[3]. Standard ML, OCaml, Haskell, Erlang, Elixir and Lua implement it; in Haskell, where evaluation is lazy, the question of stack use depends on evaluation more than on tail position. ECMAScript 2015 made proper tail calls part of the JavaScript standard in strict mode^[8], but of the major engines only JavaScriptCore, in Safari, implemented them.

The Java virtual machine has no tail-call instruction, and its security model inspected the call stack, which made eliminating frames difficult^[11]. Scala therefore turns self-recursive tail calls into loops, and @tailrec reports an error when that is not possible, but does not eliminate other tail calls; Kotlin has tailrec for the same purpose, and Clojure an explicit recur. Python does not eliminate tail calls, and its designer has argued that doing so would make stack traces less useful for debugging^[12]. C and C++ compilers eliminate tail calls as an optimization when it is safe, but do not guarantee it; Clang's [[clang::musttail]] attribute makes a tail call an error if it cannot be compiled as a jump^[13]. WebAssembly added return_call instructions for tail calls, and Rust has a proposed become keyword for them.

Trampolines

Where the target does not support tail calls, a compiler or programmer can use a trampoline: each function returns either its result or a description of the next call, and a loop at the top performs the calls, so the stack never holds more than one of them^[9]:

A trampoline for mutually recursive even and odd.

(* A trampoline: for languages without tail calls. A function returns
   either a result or the next call to make, and a loop makes the calls. *)
type 'a bounce = Done of 'a | Call of (unit -> 'a bounce)
 
let rec run = function Done x -> x | Call f -> run (f ())
 
let rec even n = if n = 0 then Done true else Call (fun () -> odd (n - 1))
and odd n = if n = 0 then Done false else Call (fun () -> even (n - 1))

Running it.

run (even 100_000_001) -> false

Each bounce allocates a closure and returns to the loop, which makes trampolined code several times slower than direct tail calls. Compilers of Scheme to C have used trampolines, or Baker's technique of letting the C stack grow and discarding it with longjmp when it is full, having copied the live data to the heap^[10].

§ 07

Debugging

A tail call removes the caller's frame, so a stack trace taken in the callee does not show the caller. In a properly tail-recursive language this is the cost of running loops in constant space, and debuggers for such languages sometimes keep a bounded history of recent tail calls to compensate.

§ 08

History

Tail calls were understood as jumps in the implementation of Lisp and Algol-like languages in the 1960s. Sussman and Steele made proper tail recursion part of the definition of Scheme in 1975^[4], and Steele's 1977 paper argued that procedure calls, compiled correctly, need be no more expensive than jumps^[1]. Clinger gave the formal definition in terms of space in 1998^[2]. OCaml added the [@tailcall] check in 2016 and tail recursion modulo cons in version 4.14^[6].