Tail-Call Optimization

The problem:

(define (loop n)
   (if (= n 0)
       "done"
       (loop (- n 1))))

(loop 100000)   -> RecursionError

Every recursive call grows Python's call stack. After ~1000 frames it blows.

The fix: trampoline

A tail call is a call that's the LAST thing a function does. There's nothing to do after — no waiting result to combine. So we don't actually need a new stack frame; we can reuse the current one.

Implementation pattern:

def eval_with_tco(x, env):
    while True:
        # ... handle each form ...
        if (procedure call in tail position):
            env = new_env(...)
            x = procedure.body
            continue       # loop instead of recurse
        return value

The while True + continue IS the trampoline. The interpreter loops rather than recursing.

Scheme requires this

The R5RS spec MANDATES tail-call optimization. Code like this is the idiomatic loop:

(define (count-up n max)
   (if (= n max)
       n
       (count-up (+ n 1) max)))

In Scheme, (count-up 0 1000000) is required to work.

What counts as tail position

• The result of an if branch (when the if itself is in tail position).
• The last form of a begin.
• The last form of a procedure body.

A call inside (* 2 (recur ...)) is NOT tail — the multiplication is pending.

Why most mainstream languages don't have it

Java, Python, C# do not guarantee TCO (loss of stack frames hurts debuggers). C compilers do it informally. Scheme, Standard ML, OCaml, Haskell guarantee it.