StackOverflow in continuation monad

Question

Using the following continuation monad:

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

I fail to see why the following gives me a stack overflow:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! xs = map xs
                return f x :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

While the following doesn't:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! v = fun g -> g(f x)
                let! xs = map xs
                return v :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

Note that I am on VS 2012 RC, if anyone could test it has the same behavior on the current release of VS2010. — David Grenier, Jun 25 '12 at 14:13
Yes, and it also has the same behavior in OCaml. See my answer below. — t0yv0, Jun 25 '12 at 16:45
FWIW, this behavior can still be observed with VS2015, F# 4.0, Update 3 (though the answers indicate it cannot be blamed onto the compiler). — Abel, Dec 17 '16 at 20:41

t0yv0 · Accepted Answer · 2012-06-25T16:48:01.767

To fix your example, add this method to your definition of the monad:

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

Apparently the part that overflows is the destruction of the large input list in the recursive call of map. Delaying it solves the problem.

Note that your second version puts the recursive call to map behind another let! which desugars to Bind and an extra lambda, in effect delaying the recursive call to map.

I had to pursue a few false trails before reaching this conclusion. What helped was observing that StackOverflow is thrown by OCaml as well (albeit at a higher N) unless the recursive call is delayed. While F# TCO has some quirks, OCaml is more proven, so this convinced me that the problem is indeed with the code and not the compiler:

let cReturn x = fun k -> k x
let cBind m f = fun c -> m (fun a -> f a c)

let map f xs =
  (* inner map loop overflows trying to pattern-match long lists *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (map xs) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fixed f xs =
  (* works without overflowing by delaying the recursive call *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fused f xs =
  (* manually fused version avoids the problem by tail-calling `map` *)
  let rec map xs k =
    match xs with
      | [] -> k []
      | x :: xs ->
        map xs (fun xs -> k (f x :: xs)) in
  map xs (fun x -> x)

You can solve this problem without adding the Delay member -- see my comment on John Palmer's response. — Jack P., Jun 25 '12 at 16:01
@JackP., I agree that adding the Delay member is not the only fix. However, you have to delay pattern-matching the input list so that it does not happen on entirely on the stack. If you do not do that, the code will overflow (if not at `N=100000` then at a higher `N`. — t0yv0, Jun 25 '12 at 16:09

score 4 · Answer 2 · answered Jun 25 '12 at 12:18

4

The F# compiler is sometimes not very clever - in the first case it computes map xs then f x and then joins them, so map xs is not in a tail position. In the second case, it can reorder the map xs to be in tail position easily.

answered Jun 25 '12 at 12:18

John Palmer

25,356
3
48
67

I fail to see how `(f x)` can be computed anywhere but inside the continuation generated by the workflow. – David Grenier Jun 25 '12 at 14:03
@DavidGrenier -- John is correct. `(f x)` is computed inside the continuation generated by the workflow, but it is not computed inside it's *own* continuation. That is, the workflow only creates one continuation which wraps `(f x) :: xs` -- so when that continuation is called, it can't make a tail-call to `f`. When that continuation is executed, it has to push a stack frame every time it calls `f`, and since it's doing so recursively you're getting the `StackOverflowException`. In your second example, the F# compiler is able to generate tail-calls for everything. – Jack P. Jun 25 '12 at 15:59
@JackP I disagree with both the comment and your response. `map` returns immediately, tail-calling `map` is not relevant. `f` is not recursive, tail-calling `f` is not relevant either. Also, the fault is not with the F# compiler, OCaml does the same here, based on my tests. – t0yv0 Jun 25 '12 at 16:05
1

I see now in what sense John's comment is correct. Having `map xs k`, rather than just `map xs`, in tail position is crucial. I just would phrase this differently, since F# compiler does not reorder code - this is all about how it is written. – t0yv0 Jun 25 '12 at 16:17

StackOverflow in continuation monad

2 Answers2

Linked