Tail-Call Optimization

Zym supports script-directed tail-call optimization via the @tco directive. This allows recursive functions to run in constant stack space, enabling deep recursion without stack overflow.

What is Tail-Call Optimization?

A tail call is a function call that is the last operation in a function — the return value of the called function is directly returned without further computation. When TCO is active, the runtime reuses the current stack frame instead of allocating a new one, turning recursion into an iterative loop internally.

tail call vs non-tail call

// TAIL CALL — result of factorial() is returned directly
func factorial(n, acc) {
    if (n <= 1) return acc
    return factorial(n - 1, n * acc)  // ← tail position
}

// NOT a tail call — multiplication happens AFTER the recursive call
func factorial_bad(n) {
    if (n <= 1) return 1
    return n * factorial_bad(n - 1)  // ← NOT tail position
}

The @tco Directive

TCO in Zym is opt-in via the @tco directive. Place it before a return statement or at the top of a file/function to indicate how tail calls should be optimized.

@tco directive

// Per-call annotation
func countdown(n) {
    if (n <= 0) return n
    @tco aggressive
    return countdown(n - 1)
}

countdown(1000000)  // runs in O(1) stack space

TCO Modes

Mode	Behavior	Use Case
`aggressive`	Optimizes any `return <call-expr>` in tail position — self-calls, cross-function calls, even dynamic callees like `arr[0]()` or lambdas	Maximum performance; mutual recursion; higher-order tail calls
`safe`	Only optimizes calls that the compiler can verify at compile-time are safe — pure self-recursion or calls to known functions with no captured upvalues. If the compiler cannot prove safety, the call is left as a normal call.	Conservative default; simple recursion with guaranteed correctness
`smart`	Tries compile-time verification first (like `safe`). If the compiler can’t verify, emits a runtime check: the VM inspects whether the callee has upvalues and only applies TCO if it doesn’t. Falls back to a normal call otherwise.	Best of both worlds — safe where provable, runtime-checked where not
`off`	Disables TCO entirely — all calls use normal stack frames	Debugging; ensuring full stack traces are preserved

Why upvalues matter: TCO reuses the current stack frame, which destroys local variables. If a closure has captured those locals as upvalues, applying TCO would break the closure. safe mode avoids this entirely at compile-time; smart mode checks at runtime; aggressive mode closes upvalues before the tail call (correct but has the overhead of the close operation).

Default mode: If no @tco directive is specified, the default mode is safe. Functions inherit the TCO mode from their enclosing scope.

mode examples

// Aggressive — optimizes any tail-position call
@tco aggressive
func factorial(n, acc) {
    if (n <= 1) return acc
    return factorial(n - 1, n * acc)
}
factorial(100000, 1)  // no stack overflow

// Safe — compile-time verified, no upvalues
@tco safe
func sum(n, acc) {
    if (n <= 0) return acc
    return sum(n - 1, acc + n)  // optimized — compiler verifies this is safe
}
sum(100000, 0)

// Smart — runtime fallback when compiler can't verify
@tco smart
func dispatch(fn, n) {
    if (n <= 0) return n
    return fn(n - 1)  // can't verify at compile-time → runtime upvalue check
}

Basic TCO Patterns

Accumulator pattern

The most common TCO pattern: carry a running result as an extra parameter so the recursive call is in tail position.

accumulator

@tco aggressive

func factorial(n, acc) {
    if (n <= 1) return acc
    return factorial(n - 1, n * acc)
}

factorial(5, 1)       // 120
factorial(10, 1)      // 3628800
factorial(100000, 1)  // runs without stack overflow

Deep recursion countdown

@tco aggressive

func countdown(n) {
    if (n <= 0) return n
    return countdown(n - 1)
}

countdown(1000000)   // 0 — runs in O(1) stack space

Mutual Recursion

With @tco aggressive, tail calls between different functions are optimized too — because aggressive mode optimizes any call expression in tail position, not just compile-time-verified ones. This enables mutual recursion patterns that would otherwise overflow the stack.

Even/Odd

mutual recursion

func isEven(n) {
    if (n == 0) return true
    @tco aggressive
    return isOdd(n - 1)
}

func isOdd(n) {
    if (n == 0) return false
    @tco aggressive
    return isEven(n - 1)
}

isEven(1000000)   // true — no stack overflow
isOdd(999999)    // true

Advanced TCO Patterns

Accordion pattern

Mutual recursion where the two functions have very different frame sizes. One function has a tiny frame (few locals); the other has a large frame (many locals). The runtime must correctly resize the frame on each tail call.

accordion pattern

func ping(n) {
    if (n == 0) return "Success"
    // Tiny frame → tail call to LARGE frame
    @tco aggressive
    return pong(n - 1)
}

func pong(n) {
    // Large frame: many local variables
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    var f = 6
    var g = 7
    var h = 8
    var i = 9
    var j = 10

    // Verify memory integrity
    var sum = a + b + c + d + e + f + g + h + i + j
    if (sum != 55) return "Memory corruption!"

    // Large frame → tail call to TINY frame
    @tco aggressive
    return ping(n - 1)
}

ping(1000000)   // "Success" — frames resize correctly

Shattered accordion pattern

A more extreme variant with three or more functions of different frame sizes in a mutual recursion chain. Tests that frame resizing works across multiple distinct sizes.

shattered accordion

func alpha(n, x) {
    if (n <= 0) return x
    // Tiny frame: 2 args, 0 locals
    @tco aggressive
    return beta(n - 1, x + 1, "extra")
}

func beta(n, x, junk) {
    // Medium frame: 3 args, 2 locals
    var v1 = x * 2
    var v2 = n + 1
    @tco aggressive
    return gamma(n - 1, v1, v2, "more", 42)
}

func gamma(n, a, b, c, d) {
    // Large frame: 5 args, 4 locals
    var l1 = 1
    var l2 = 2
    var l3 = 3
    var l4 = 4
    if (n <= 0) return "Success"
    @tco aggressive
    return alpha(n - 1, a / 2)
}

alpha(1000000, 1)   // "Success"

TCO with closures

TCO interacts correctly with closures. A tail-recursive function that captures variables from a closure will still be optimized, and the closure’s captured state is preserved.

TCO with closures

var history = [null, null, null, null, null]

func tortureTest(n, index, list) {
    if (n == 0) return list

    // Closure captures 'n' from the current frame
    func snap() { return n }
    list[index] = snap

    @tco aggressive
    return tortureTest(n - 1, index + 1, list)
}

tortureTest(5, 0, history)

history[0]()   // 5 — each closure captured its own 'n'
history[4]()   // 1

Interactions

TCO with memory semantics

TCO works correctly with all memory qualifiers (ref, val, slot, clone). When a tail call reuses the stack frame, the runtime emits an opcode to ensure that any data needed by the previous frame — such as ref targets, upvalues, and closure-captured locals — is preserved before the frame is recycled.

TCO with ref parameters

@tco aggressive

func countdown(ref counter, n) {
    if (n == 0) return counter
    counter = counter + 1
    return countdown(counter, n - 1)
}

var base = 0
countdown(base, 10)
// base is 10 — ref survived 10 tail-call frame reuses

Mixed qualifier signatures work too — ref, val, and normal parameters can all appear in the same tail-recursive function without issues.

mixed qualifiers with TCO

@tco aggressive

func accumulate(ref total, val snapshot, n) {
    if (n == 0) return total
    total = total + n         // modifies caller’s variable
    snapshot[0] = 999         // local copy only
    return accumulate(total, snapshot, n - 1)
}

var sum = 0
var data = [1, 2, 3]
accumulate(sum, data, 5)
sum        // 15 — ref wrote through across all frames
data[0]    // 1  — val protected the original

TCO with continuations

TCO and delimited continuations are fully compatible. A tail-recursive function can be captured mid-recursion and resumed later — the continuation correctly restores the optimized frame state, including any refs, closures, and local variables.

Here’s an example combining all three — ref, @tco aggressive, and delimited continuations — in a single function:

ref + TCO + continuations

var TAG = Cont.newPrompt("cap-val-nested")

@tco aggressive
func test_nested(ref counter, stepsLeft) {
    if (stepsLeft == 0) return counter

    if (counter == 3) {
        var x = Cont.capture(TAG)
        if (x != null) counter = counter + x
    }

    counter = counter + 1
    return test_nested(counter, stepsLeft - 1)
}

var base = 0

Cont.pushPrompt(TAG)
var k = test_nested(base, 10)

Cont.pushPrompt(TAG)
Cont.resume(k, 5)

print(base)   // 15

The function recurses with TCO (constant stack space), modifies the caller’s variable through ref, and pauses mid-recursion via Cont.capture. When resumed with a value, the continuation picks up exactly where it left off — the ref still targets base, and TCO continues reusing frames.

Best Practices

Use accumulator parameters to ensure recursive calls are in tail position.
Choose the right mode: Use safe (the default) for simple self-recursion with no closures, smart when the compiler can’t verify safety but you want TCO where possible, and aggressive for mutual recursion or maximum performance.
Place @tco before the return: The directive annotates the immediately following return statement.
Verify tail position: The call must be the last operation — no arithmetic, concatenation, or other operations on the result.
Use off for debugging: TCO removes stack frames, which can make stack traces harder to read. Use @tco off during development if needed.

Common mistake: return n * f(n-1) is not a tail call because the multiplication happens after f() returns. Restructure with an accumulator: return f(n-1, acc * n).