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
`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; 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)

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 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 closures and local variables.

TCO + continuations

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

@tco aggressive
func test_nested(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)
}

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

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

The function recurses with TCO (constant stack space) and pauses mid-recursion via Cont.capture. When resumed with a value, the continuation picks up exactly where it left off 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, 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).