What is wrong with 100000 factorial using ContinuationMonad?

Question

It is powerful technique using recursion because its strong describable feature. Tail recursion provides more powerful computation than normal recursion because it changes recursion into iteration. Continuation-Passing Style (CPS) can change lots of loop codes into tail recursion. Continuation Monad provides recursion syntax but in essence it is tail recursion, which is iteration. It is supposed to reasonable use Continuation Monad for 100000 factorial. Here is the code.

type ContinuationBuilder() =
   member b.Bind(x, f) = fun k -> x (fun x -> f x k)
   member b.Return x = fun k -> k x
   member b.ReturnFrom x = x
(*
type ContinuationBuilder =
  class
    new : unit -> ContinuationBuilder
    member Bind : x:(('d -> 'e) -> 'f) * f:('d -> 'g -> 'e) -> ('g -> 'f)
    member Return : x:'b -> (('b -> 'c) -> 'c)
    member ReturnFrom : x:'a -> 'a
  end
*)
let cont = ContinuationBuilder()
//val cont : ContinuationBuilder
let fac n =
    let rec loop n =
      cont {
              match n with
              | n when n = 0I -> return 1I   
              | _ -> let! x = fun f -> f n
                     let! y = loop (n - 1I)   
                     return x * y
           }
    loop n (fun x -> x)

let x2 = fac 100000I

There is wrong message: "Process is terminated due to StackOverflowException."

What is wrong with 100000 factorial using ContinuationMonad?

Answer 1

You need to compile the project in Release mode or check the "Generate tail calls" option in project properties (or use --tailcalls+ if you're running the compiler via command line).

By default, tail call optimization is not enabled in Debug mode. The reason is that, if tail-calls are enabled, you will not see as useful information about stack traces. So, disabling them by default gives you more pleasant debugging experience (even in Debug mode, the compiler optimizes tail-recursive functions that call themselves, which handles most situations).

Answer 2

You probably need to add this memeber to your monad builder:

member this.Delay(mk) = fun c -> mk () c