How to achieve tail call optimization while traversing tree-like structure using continuation-passing style

Question

I try to implement tail call optimization to traverse tree-line structure using continuation-passing style in scala. Unfortunately my previous experience with fsharp does not help much. I have recursive call w/o tail optimization:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  def traverseTreeRec(tree: Tree, continuation: () => Unit, action: Int => Unit): Unit = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) => {
      traverseTreeRec(n1, () => traverseTreeRec(n2, continuation, action), action)
    }
  }
  traverseTreeRec(tree, () => (), action)
}

Afterwards I try to rewrite using @annotation.tailrec and TailCalls, but still not sure how to decorate continuation

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  @annotation.tailrec
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) =>
      // how to properly implement tail call here?
      // ERROR: it contains a recursive call not in tail position
      traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action)
  }
  traverseTreeRec(tree, () => done(), action)
}

Thanks in advance

ps: full sample on gist

The following question may be of use here: http://stackoverflow.com/questions/4428868/how-to-use-tailcalls — Rob Napier, Nov 24 '13 at 02:02

score 1 · Answer 1 · edited Sep 22 '17 at 21:20

Finally, I have an answer from Coursera discussion forum:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit]): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      continuation()
    }
    case Node(n1, n2) =>
      tailcall(traverseTreeRec(n1,
        () => traverseTreeRec(n2,
          () => tailcall(continuation()))))
  }
  traverseTreeRec(tree, () => done(())).result
}

ps: suggested question by @rob-napier contains some details why it should be applied in this way

score 0 · Answer 2 · answered Nov 24 '13 at 00:32

I have little knowledge of Scala but in your code I guess you can do:

tailcall(traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action))

Since the tailcall that were there were in fact in an other anonymous function it will call when hitting a leaf. Perhaps you need it in all tail positions:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = {
  @annotation.tailrec
  def traverseTreeRec(tree: Tree, continuation: () => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match {
    case Leaf(n) => {
      action(n)
      tailcall(continuation())
    }
    case Node(n1, n2) =>
      tailcall(traverseTreeRec(n1, () => tailcall(traverseTreeRec(n2, continuation, action)), action))
  }
  tailcall(traverseTreeRec(tree, () => done(), action))
}

In Scheme it would have been faster just to let the recursion into the first branch not be a tail call and the second to be one but I guess you can't mix in Scala because it need trampolining to do TCO.

In my tests, the above code fails with the same error "could not optimize tailrec annotated method traverseTreeRec: it contains a recursive call not in tail position" — Rob Napier, Nov 24 '13 at 02:03
Looks like continuation should be `taillcall` instead of second `traverseTreeRec`: `tailcall(traverseTreeRec(n1, () => traverseTreeRec(n2, () => tailcall(continuation()))))` — Akim, Nov 24 '13 at 07:28

How to achieve tail call optimization while traversing tree-like structure using continuation-passing style

2 Answers2