Why Use Scala / Tail-Call optimization

Introduction

As software engineers, we have a hate / love relationship towards recursion: it may be a bit difficult to grasp at first but, once you get the hang of it, you can solve complicated problems in a very elegant fashion; however, if you don't assess carefully the dimension of the input problem, you might incur in nasty production issues.

Suppose we have function that walks a day's orders and accumulates a balance, written the obvious recursive way:

case class Order(id: String, amount: Double)

def settle(orders: List[Order], balance: Double = 0.0): Double = orders match
  case Nil          => balance
  case head :: tail => settle(tail, balance + head.amount)

(That head :: tail is the extractor we described in the previous post, if you want the details of how the pattern works.)

This function looks perfectly good, and passes review and its unit tests just fine, so we obviously approve the PR, merge it, and deploy it to production. Then, one Friday night, some cron job decides to execute it against a month worth of trades, and the process dies with a stack overflow. The logic was never wrong: it just assumed an input size that had never been realistic to begin with.

Wouldn't it be great if the language could optimize recursive calls, such that those nasty stack overflow exceptions would never occur? Today, we will see how different languages tackle this problem.

Python: a hard ceiling at 1000

The choice made by Python was quite pragmatic: instead of optimize tail calls, they decided to impose a fixed recursion limit to the interpreter:

import sys
from dataclasses import dataclass

@dataclass(frozen=True)
class Order:
    id: str
    amount: float

def settle(orders, balance=0.0):
    if not orders:
        return balance
    head, *tail = orders
    return settle(tail, balance + head.amount)

print(sys.getrecursionlimit())            # 1000

small = [Order(f"o{i}", 1.0) for i in range(100)]
settle(small)                             # 100.0, fine

big = [Order(f"o{i}", 1.0) for i in range(50_000)]
settle(big)                               # RecursionError: maximum recursion
                                          # depth exceeded while calling a Python object

A thousand frames does not sound much, and it really isn't: any collection coming from a real DB, rather than a fixture, will blow the process for sure. There is a hack around it, which is to call sys.setrecursionlimit(); but this really is a hack because the documentation is very clear: if the limit is too high, and the real C stack runs out first, you will crash the entire application with a segfault, rather than having an exception thrown.

Therefore, the practical answer in Python is not to write recursions; instead, rewrite the function as a loop, and carry the accumulator by hand. Bummer.

TypeScript: the spec says yes, the engines say no

JavaScript is one interesting case, because proper tail calls are actually supported by the language since ES6, over a decade ago. The catch is that almost nobody implemented them: JavaScriptCore shipped it; V8 and SpiderMonkey begun, then backed out. And because Node runs on V8, a tail-recursive function gets no special treatment at all:

type Order = { id: string; amount: number };

// This call is in perfect tail position. ES6 says it should not grow the stack.
const settle = (orders: Order[], i = 0, balance = 0): number =>
  i === orders.length ? balance : settle(orders, i + 1, balance + orders[i].amount);

const mk = (n: number) => Array.from({ length: n }, (_, i) => ({ id: `o${i}`, amount: 1 }));

settle(mk(100));      // 100
settle(mk(200_000));  // RangeError: Maximum call stack size exceeded

We binary-searched the actual limit on Node 20 while writing this: the function above overflows at roughly 5,500 frames. All the tail-call optimization may be thrown away, depending on the engine you're actually running on.

Java: the JVM will not do it for you

The JVM does not perform tail-call optimization, despite being a topic of discussion for years, and the long-running work in Project Loom's vicinity. As of today though, tail-recursive methods still allocates a frame per call like any other:

record Order(String id, double amount) {}

// Also in tail position. Also allocates a frame per call.
static double settle(List<Order> orders, int i, double balance) {
    if (i == orders.size()) return balance;
    return settle(orders, i + 1, balance + orders.get(i).amount());
}

settle(small, 0, 0.0);   // fine
settle(big, 0, 0.0);     // StackOverflowError at ~19,000 frames

Java gets further than Node before falling over, and you can push it further still with -Xss, but the problem is still the same: a limit that depends on deployment flags, discovered at runtime, on whatever input happens to be largest. The real fix is the same as Python's: rewrite it as a loop and maintain the accumulator yourself.

Scala: the compiler proves it

Despite running on the same JVM, Scala does provide tail-call optimization: whenever the compiler encounters a self-recursive call in tail position, it will rewrite it into a jump, turning that method into a loop in the bytecode. The settle from the top of this post can handle a million orders without ever throwing a stack overflow.

However, because that is a compiler optimization that happens without the developer noticing it, it may also happen that another developer can modify it in few months, break the conditions that makes is a tail-recursive function, therefore having nasty stack overflows in production.

This is why the Scala library ships with this useful@tailrec annotation. Its purpose is twofold: inform the developer that the method is tail-recursive and therefore the compiler can optimize it into a loop, and asserting that the optimization is possible, thus failing the whole compilation process in case it isn't:

import scala.annotation.tailrec

@tailrec
def settle(orders: List[Order], balance: Double = 0.0): Double = orders match
  case Nil          => balance
  case head :: tail => settle(tail, balance + head.amount)

settle(List.tabulate(1_000_000)(i => Order(s"o$i", 1.0)))   // 1000000.0

Now write the same function the way most people write it first, with the addition on the outside of the call:

@tailrec
def settle(orders: List[Order]): Double = orders match
  case Nil          => 0.0
  case head :: tail => head.amount + settle(tail)

// error: Cannot rewrite recursive call: it is not in tail position
//   case head :: tail => head.amount + settle(tail)
//                                      ^^^^^^^^^^^^

This version is the one that will die in production, and the beauty of all of this, is that it won't ever happen because the compiler detected that it can't optimize it into a loop. How nice is that?

The property being checked is a subtle one, which is the argument for having a machine check it. Here is a change that looks completely harmless:

@tailrec
def settle(orders: List[Order], balance: Double): Double = orders match
  case Nil          => balance
  case head :: tail => try settle(tail, balance + head.amount)
                       catch case _: Throwable => 0.0

// error: Cannot rewrite recursive call: it is not in tail position

Wrapping the call in a try-catch block, effectively puts a handler on the stack that has to outlive it, therefore the overall call stops being a tail call. Nobody adding defensive error handling to a working function is thinking about frame layout, and why would they, by the way? Without @tailrec the code would compile, run, pass the tests, and blow up in production.

Where the annotation stops helping

Of course, you can be creative and stress the limits of what @tailrec can do: for example, it only covers a function calling itself. Two functions calling each other are not covered, and the compiler says so rather than pretending:

@tailrec
def isEven(n: Int): Boolean = if n == 0 then true else isOdd(n - 1)
def isOdd(n: Int): Boolean  = if n == 0 then false else isEven(n - 1)

// error: TailRec optimization not applicable,
//        method isEven contains no recursive calls

For mutual recursion, the standard library answer is scala.util.control.TailCalls, a so called trampoline: each step returns a description of the next call instead of making it, and a driver loop runs them one after another on a flat stack.

import scala.util.control.TailCalls.*

def isEven(n: Int): TailRec[Boolean] = if n == 0 then done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean]  = if n == 0 then done(false) else tailcall(isEven(n - 1))

isEven(1_000_000).result   // true

It costs you allocations and a .result at the end, so it is a real trade rather than a free win. But it exists in the standard library, and the compiler failure driven by @tailrec is what sends you looking for it.

A property that survives the next edit

Every language here can express this simple function. The difference is what happens six months later, when somebody who has never read this post adds a try around the recursive call, or reorders an expression, or wraps the result in a log statement.

That somebody is increasingly an AI agent, and this is a failure mode agents are especially prone to. Asked to add error handling to settle, wrapping the body in a try is a reasonable and idiomatic move in four languages out of four. In three of them it compiles, the tests pass on the fixture with twelve orders, and the regression is invisible until the input gets big. In Scala the build fails with a message naming the exact expression. The agent gets told, immediately, in the only channel it reliably reads.

Stack safety here is not a comment or a naming convention or a line in a design document, which are the three places this kind of requirement usually lives and the three places nobody looks during a refactor. It is a compiler error attached to the function it applies to.