Re: Tail calls via trampolining and an explicit instruction

It's a neat technique, and one we can easily adopt for Scala. Here's
the necessary code to do that:

package scala.util.control

abstract class TailRec[+A]

object TailRec {

  case class Call[A](rest: () => TailRec[A]) extends TailRec[A]
  case class Done[A](result: A) extends TailRec[A]

  def tailcall[A](rest: => TailRec[A]) = new Call(() => rest)

  def done[A](result: A) = new Done(result)

  def trampoline[A](body: TailRec[A]): A = {
    def loop(body: TailRec[A]): A = body match {
      case Call(rest) => loop(rest())
      case Done(result) => result
    }
    loop(body)
  }
}

I am toying with the idea of putting this into Scala 2.8. Here's a
test that uses mutual recursion to find out whether a list has even
length:

  import scala.util.control.TailRec._

  def isEven(xs: List[Int]): TailRec[Boolean] =
    if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

  def isOdd(xs: List[Int]): TailRec[Boolean] =
    if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

  def testEven(xs: List[Int]) = trampoline(isEven(xs))

Everything works as expected. But it works quite slowly. The numbers
below show 5 runs each of a benchmark with direct calls to
isEven/isOdd on lists as shown above and a benchmark with trampolining
calls. The trampolining call benchmark is about 4 times slower.

util.control.RecListBench$ 886 671 558 573 554
util.control.TrampListBench$ 2700 2263 2302 2350 2302

Compared to Clojure, the Scala solution needs an extra wrapper around
the closure in order to make the sum. It might be that this explains
part of the relatively worse performance of trampolines in Scala. Or
it might be that the base case (direct call) is faster in Scala than
in Clojure. It would be interesting to find out more.

Clojure seems to have lots of other interesting ideas as well, for
instance its transactional memory and immutable datastructures.
It's definitively a welcome addition to the JVM languages zoo!
Ironically, Clojure's maps are based on work which Phil Bagwell did
as an associate of my group at EPFL. We never put that into the Scala
collection libraries (Phil being a C++ person), but now we have new
motivation to do so.

Cheers

 -- Martin