Tail Position, Accumulators, and Continuation-Passing Style

A recursive definition that returns n * f (n - 1) needs somewhere to keep n while the recursive call runs, and that somewhere is a stack frame. A definition that returns f (n - 1, n * acc) does not: the multiplication has already happened, and nothing remains to be done after the call returns. The difference between the two is syntactic, decidable by inspection, and it decides whether the recursion consumes stack or runs in constant space.

Tail position defined by the continuation

A call is in tail position when it is the last thing the enclosing function does with its result. The precise definition uses continuations: at any point in a program, the continuation is the function that receives the value of the current expression. An expression is in tail position exactly when its continuation is the continuation of the enclosing function body.

The definition is inductive and covers more cases than “last expression in the body”:

• The consequent and alternative of an if are in tail position if the if is.
• The body of a let is in tail position if the let is; the right-hand sides of the bindings are not.
• The last expression of a begin or do block is in tail position; the earlier ones are not.
• The argument of return in a language that has an explicit return is in tail position relative to the function.

An operand of + is never in tail position, because the addition must wait for it. Neither is the argument of a data constructor, because the constructor must wait. Neither is the right-hand side of an assignment.

Why the frame can be reused

Consider the machine-level picture. A call in non-tail position compiles to: save the return address, save the live registers, jump to the callee, restore on return, continue with the pending operation. The saved state is what makes the return address meaningful. A call in tail position compiles to: move the arguments into the callee’s parameter registers, jump. The caller’s frame is dead at that point because no code after the call reads anything from it, so the callee can reuse it.

Two conditions must hold for the optimization to be legal. First, the callee’s frame must fit in the caller’s, or the implementation must be able to discard the caller’s frame entirely. Second, the callee must not be able to observe the caller’s frame, which rules out constructs that capture the current continuation implicitly. In a language with call/cc, a tail call still discards the frame, and a continuation captured inside the callee does not include the caller’s frame; that is the correct semantics, and it is why invoking such a continuation later returns to whatever follows the tail call rather than to the code that was discarded.

The R7RS report for Scheme requires implementations to support proper tail calls: a tail call must execute in constant space even if the procedure called is not itself written recursively. The requirement is semantic, not an optimization, and a conforming implementation must make an unbounded number of tail calls without growing the stack. The definition of Standard ML is written so that a tail call does not extend the evaluation context, which is what allows an implementation to run one in constant space. Other languages specify the opposite: they guarantee a stack trace that includes every active call, which a tail call would erase, and they therefore cannot offer the guarantee.

Accumulators: moving the pending work before the call

The standard way to put a call in tail position is to carry the pending computation as an argument. The factorial is the canonical case:

fact 0 = 1
fact n = n * fact (n - 1)          -- not tail recursive

factAcc acc 0 = acc
factAcc acc n = factAcc (acc * n) (n - 1)   -- tail recursive

The second version moves the multiplication to before the recursive call, and the result is unchanged because multiplication is associative. That associativity is the licence for the transformation: the pending operation is reassociated so that it happens on the way down instead of on the way up.

The same move reverses a list:

rev xs = go xs []
  where
    go []     acc = acc
    go (y:ys) acc = go ys (y:acc)

Here the pending cons is moved before the call by consing onto the accumulator. The accumulator ends up holding the list backwards, and the reversal is exactly the reordering that the tail call performs. This is why reverse written this way is linear and reverse written with (++) is quadratic: the latter leaves a pending append on every level, and each append copies its left argument.

Associativity is not always available. A tree traversal that must rebuild the tree in order cannot be made tail recursive by an accumulator, because the pending work is not associative; the continuation of the left subtree includes the root and the right subtree, and those must be visited in a fixed order. The standard resolutions are an explicit stack, a continuation, or a traversal order that happens to be tail recursive (a right-to-left preorder, for instance). The general statement is that the accumulator transformation applies when the recursion is a fold whose pending operation can be pushed before the call, which is exactly when that operation is associative, as it is for a sum, a product, or a cons. That is the same universal property that fold rests on, restricted to the algebras whose operation is associative.

Strictness is part of the transformation

In a lazy language, moving the operation before the call changes the evaluation order unless the accumulator is forced. The accumulator in factAcc accumulates thunks; the strictness annotation or the strict version of the fold is what keeps the chain short. In a strict language the transformation is behaviour-preserving on total values and differs only where the original would have diverged during the pending operation. The transformation is therefore always legal for the final result and sometimes changes which intermediate values are demanded, which matters when an intermediate value is ⊥.

This is the same distinction that separates foldl from foldl' in call-by-need evaluation: the tail-recursive shape alone does not guarantee constant space, because the accumulator can still be a growing thunk.

Continuation-passing style

The general form of “move the pending work before the call” is to pass the pending work as a function. A function in continuation-passing style takes an extra argument, the continuation, and never returns; it calls the continuation with its result.

-- direct style
add :: Int -> Int -> Int
add x y = x + y

-- continuation-passing style
addCPS :: Int -> Int -> (Int -> r) -> r
addCPS x y k = k (x + y)

Every call in CPS code is a tail call, by construction: the body of a CPS function is a call to its continuation, and nothing follows it. The transformation from direct style is mechanical: each function gains a parameter k, each return e becomes k e, each call f a becomes f a (\v -> ...) with the rest of the computation inside the lambda. The result is a program in which control flow is explicit as data, and every transfer of control is a jump.

The CPS transformation has three consequences worth separating.

Control operators become expressible. With the continuation as an ordinary value, a function can store it, call it more than once, or discard it. Exceptions, generators, coroutines, and backtracking search all fall out of the same mechanism. This is why CPS is the standard intermediate representation for compilers that need to implement such features uniformly.

Allocation moves from the stack to the heap. A continuation that outlives its call must be heap-allocated, because a stack frame would be reclaimed. A continuation used once and immediately can be a stack frame, and a compiler that can prove single use keeps it there. The cost of CPS in a language without that analysis is that every non-trivial call allocates a closure instead of pushing a frame, with the allocation and the collector work that implies.

The transformation is not free of asymptotics. A CPS version of a function that recurses on both arguments, such as a naive Fibonacci, still does the same number of calls; the transformation changes the shape of the stack, not the number of steps. It cannot turn an exponential algorithm into a linear one.

Defunctionalizing the continuation

A continuation is a closure, and a closure is a code pointer plus an environment. If a program has only finitely many continuation shapes, the closure can be replaced by a tag plus the captured values, and the call site becomes a dispatch. This is Reynolds’s defunctionalization, and it is the inverse of the CPS transformation in the sense that it turns higher-order control into a first-order machine.

data Kont = Done | More Int Kont | Times Int Kont

apply :: Kont -> Int -> Int
apply Done        v = v
apply (More n k)  v = apply k (n + v)
apply (Times n k) v = apply k (n * v)

Each constructor corresponds to a distinct lambda in the original program, and apply is the single dispatch point. The resulting program has no closures at all, which is what makes it suitable as a target for a compiler whose runtime does not support them, and it is also how an interpreter written in a strict first-order language implements CPS code. The tag space is finite and known statically, so the dispatch is a jump table rather than a dynamic lookup. The same technique applied to ordinary data rather than control is covered in free monads and defunctionalization.

Trampolining where the language refuses

A language without proper tail calls can still run unbounded tail recursion if the programmer represents the pending call as data and returns it to a driver loop. Each recursive step returns either a final value or a request to call again, and the driver iterates. This is the trampoline, and it is the standard workaround in languages that guarantee stack traces.

data Step a = Done a | Again (() -> Step a)

run :: Step a -> a
run (Done a)   = a
run (Again th) = run (th ())

run itself is tail recursive and is the only function that recurses, so the depth is one. The cost is one closure allocation per step and one indirect call through the driver, against a direct jump in a language with proper tail calls. A trampoline also changes the failure mode: a program that would have overflowed the stack now runs until it exhausts the heap, which is a later and less diagnosable failure.

The choice between the four techniques is a choice of where the pending work lives. In the stack frame, it is cheap and bounded. In an accumulator, it is cheap and reassociated. In a heap-allocated continuation, it is general and costs an allocation. In a defunctionalized tag, it is general and costs a dispatch. Which one a language makes available is decided by its calling convention and by whether it is willing to erase frames that a debugger would otherwise show.