Tail-Call Optimisation

Tail-Call Optimisation lets you write

public void forever(long n) {
 System.out.println("looking for the last number: " + n)
 if (isTheLastNumber(n)) {
  return;
 }
 forever(n + 1);
}

- and never get a StackOverflowError. Yes. Never. When a recursive call to forever exits, there is nothing left for the parent invocation of forever to do, so its stack frame can be discarded, and if it is, the stack simply doesn't grow.

Here's an arc example:

(def a ()
 (b)
 (e))

(def b ()
 (c)
 (d))

(def e ()
 (f)
 (g))

(def g ()
 (h)
 (i)
 (j))

Remeber, the return value of a function is the value of the last expression of the function. So the return value of (b) is (d).

After the call from b to (c) returns, execution continues with the call from b to (d). However, when (d) returns, b has nothing more to do, so it can return directly to a.

So, when we call c, we tell it to return to b at Instruction 2. However, when we call d, instead of telling it to return to b, we tell it to return to a. The stack frame representing b at this point is no longer referenced: the continuation for d is pointing back to a, bypassing b altogether.

Ultimately, by the time we get to the call to j, we will tell j to return to whoever a's caller was, because neither a, nor e, nor g, make use of the value of (j). Presumably, a's caller does.

I hope this is making sense.

Here is the implementation in rainbow. Inside the current continuation, the variable f is the function we're evaluating, and f.nth(i) gives us the nth expression of that function. To interpret the nth expression, rainbow does (approximately) this:

   ArcObject expression = f.nth(index++);
   Interpreter.interpret(f.last(index) ? caller : this, expression);

So if I'm on the last expression, I tell the interpreter to return to my caller instead of to me once it's finished. Mission accomplished.

See wikipedia's tail-recursion article for more information. btw, rainbow doesn't do TCO modulo cons (see article). Arc on scheme, it seems, does. I will have to figure that out.