Tail call

also: tail call optimization, tco, tail recursion, tail position, tailcall

A call whose result is returned directly, with nothing left for the caller to do. The caller's frame can be reused for it, so a loop written as tail recursion runs in constant stack space. OCaml guarantees this, and the [@tailcall] attribute makes the compiler warn when a call marked with it is not one.

A call is in tail position when it is the last thing its function does. In x + sum xs the addition still has to happen after sum xs returns, so the frame holding x has to stay; moving the addition into an accumulator puts the recursive call in tail position.

let rec sum = function [] -> 0 | x :: xs -> x + sum xs
let rec sum_acc acc = function [] -> acc | x :: xs -> sum_acc (acc + x) xs

sum_acc 0 xs  ->  49999995000000
sum xs        ->  exception Stack_overflow

Whether a call is a tail call is easy to get wrong by reading, since a try around it or an argument evaluated after it takes it out of tail position. The attribute checks it:

let rec sum = function [] -> 0 | x :: xs -> x + (sum [@tailcall]) xs
 
Warning 51 [wrong-tailcall-expectation]: expected tailcall

Tail calls make CPS practical, since in CPS every call is a tail call. They do not make a program's memory use constant on their own: a tail-recursive loop that builds a growing accumulator, or in a lazy language a growing chain of thunks, still grows.

• CPSContinuation-passing style: instead of returning, a function takes an extra continuation argument and calls it with the result. Every call becomes a tail call, which is what lets a CPS-transformed program run in constant stack space wherever tail calls are eliminated, and it makes control flow a value that can be stored and resumed.
• Space leakMemory a program holds longer than it needs to. In a lazy language the usual cause is a chain of unevaluated thunks: a lazy left fold over a list builds one suspended addition per element and only performs them at the end. A heap profile by closure type shows it as a growing THUNK band.
• Effect handlerA construct that runs code which may perform an effect, and handles each effect by receiving it together with the continuation from the point where it was performed. OCaml 5 has them, with one-shot continuations: each can be resumed at most once.

• Tail CallsWhich languages guarantee them, which only sometimes deliver them, how to check, and what to do when you do not have them.

• G. L. Steele Jr., “Debunking the ‘expensive procedure call’ myth, or, procedure call implementations considered harmful, or, LAMBDA: the ultimate GOTO”, ACM Annual Conference (1977).
• W. D. Clinger, “Proper tail recursion and space efficiency”, PLDI (1998).