Using continuation to transform binary recursion to tail recursion

Question

As I'm reading the Programming F# book, I found the example code snippet on page 195 as follows:

type ContinuationStep<'a> =
  | Finished
  | Step of 'a * (unit -> ContinuationStep<'a>)

let iter f binTree =
  let rec linearize binTree cont =
    match binTree with
    | Empty -> cont()
    | Node(x, l, r) ->
      Step(x, (fun () -> linearize l (fun() -> linearize r cont)))

  let steps = linearize binTree (fun () -> Finished)

  let rec processSteps step =
    match step with
    | Finished -> ()
    | Step(x, getNext)
      -> f x
        processSteps (getNext())

  processSteps steps

By using continuation, the binary recursion of traversing a binary has been transformed to tail-recursive function processSteps. My question is that the other function, linearize seems to be non-tail-recursive. Does that mean we are not able to transform a binary-recursion to a tail-recursion completely even using continuation?

Answer 1

The example is a bit subtle because it does not use ordinary continuations, but instead builds a structure that can be evaluated step-by-step. In a place where you would normally make a recursive call, it returns a value Step that contains the function that you'd (recursively) call.

In the second case, the linearize function returns a Step containing a function that will call linearize recursively, but it does not immediately make the recursive call. So the function does not make a recursive call (it just stores a recursive reference).

It only makes sense to consider whether the program is tail-recursive when you look at processSteps, because that does the actual looping - and that is tail-recursive, because it runs a Step by Step without keeping stack space for each Step.

If you wanted to construct a list instead of a chain of lazy steps then you'd have to make the recursive call to linearize immediately inside the continuation:

let rec linearize binTree cont = 
  match binTree with 
  | Empty -> cont [] 
  | Node(x, l, r) -> 
      linearize l (fun l -> linearize r (fun v -> cont (x::v)))

This is essentially the same as the previous function, but it actually calls linearize instead of building Step containing a function that will call linearize.