Continuation Passing Style Computation Expression

Question

Can you implement CPS using computation expressions in F#?

Brian McNamara's blog gives this solution:

type ContinuationBuilder() = 
  member this.Return(x) = (fun k -> k x) 
  member this.ReturnFrom(x) = x 
  member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
  member this.Delay(f) = f() 

let cps = ContinuationBuilder()

Looks good. I can write List.map in CPS:

let rec mapk f xs = cps {
  match xs with
  | [] -> return []
  | x::xs ->
      let! xs = mapk f xs
      return f x::xs
}

But it stack overflows:

mapk ((+) 1) [1..1000000] id

What am I doing wrong?

Answer 1

The problem is that your Delay function in the computation builder is immediately calling the function - this means that when you call mapk, it will immediately run the pattern matching and then call mapk recursively (before passing its result to the Bind operation).

You can fix this by using an implementation of Delay that returns a function which invokes f only after it is given a final continuation - this way, the recursive call will just return a function (without doing more recursive calls that cause stack overflow):

member this.Delay(f) = (fun k -> f () k)

With this version of Delay, the your code works as expected for me.