Re: Tail calls via trampolining and an explicit instruction

The phrase "tail call optimization" often confuses because it sounds like proponents primarily want things to be "faster" - after all speed is the most common target of optimizations.   But while faster is certainly nicer, what we really want from TCO is for things to not explode in the face of large or even infinite sequences of tail calls.   It's a space optimization rather than a time optimization.  In the right circumstances is optimizes O(n) memory stack usage to O(1).  That's often far more important than a mere constant factor loss in time performance.

Hickey made an interesting choice.   He makes the user do the work to indicate when trampolining should be used.  That means the user gets to make the choice about the trade-offs involved.

A variation in Scala

  object Sometime {
    def tailCall[X](x : => Sometime[X]) = new Later({x})
    implicit def xToSometime[X](x : => X) = new Now({x})
    def trampoline[X](x : Sometime[X]) = x.eval
  }
  sealed abstract class Sometime[X] {
    def eval : X = {
      def eval[X](x : Sometime[X]) : X = x match {
        case x : Now[X] => x.get
        case x : Later[X] => eval(x.get)
      }
      eval(this)
    }
  }
  class Now[X](x : => X) extends Sometime[X] {
    protected def get = x
  }

  class Later[X](x : => Sometime[X]) extends Sometime[X] {
    protected def get = x
  }

  import Sometime._
  def foo(n : Long) : Sometime[Unit] = {
    if ( n > 0)
      tailCall(bar(n - 1));
  }
 
  def bar(n : Long) : Sometime[Unit] = {
    if ( n > 0)
      tailCall(foo(n - 1));
  }

trampoline(foo(1000)), or, equivalently foo(1000).eval