Recursive computation expressions

Question

In a previous question I was told how to rewrite my computation expressions so it uses tail recursion. I rewrote my code but still got a StackOverflowException. To locate the problem I wrote some small code using a state monad (taken from this blog entry):

type State<'a, 's> = State of ('s -> 'a * 's)

let runState (State s) initialState = s initialState

let getState = State (fun s -> (s,s))
let putState s = State (fun _ -> ((),s))

type StateBuilder() =
  member this.Return a = State (fun s -> (a, s))
  member this.Bind(m, k) = 
    State (fun s -> let (a,s') = runState m s in runState (k a) s')
  member this.ReturnFrom a = a
let state = new StateBuilder()

let s max = 
    let rec Loop acc = state {
        let! n = getState
        do! putState (n + 1)
        if acc < max then
            return! Loop (acc + 1)
        else return acc
        }
    Loop 0

runState (s 100000) 0

This is throwing a StackOverflowException again, although the Loop function could use tail recursion(?). I guess something is wrong with the StateBuilder class. I tried to do something with the Delay method. Wraping everything in an extra lambda, without success. Im totally stucked at the moment. Here my second attempt (does not compile):

type State<'a, 's> = State of ('s -> 'a * 's)

let runState (State s) initialState = s initialState

let getState = fun () -> State (fun s -> (s,s))
let putState s = fun () -> State (fun _ -> ((),s))

type StateBuilder() =
  member this.Delay(f) = fun () -> f()
  member this.Return a = State (fun s -> (a, s))
  member this.Bind(m, k) = 
    fun () -> State (fun s -> let (a,s') = runState (m ()) s in runState ((k a) ()) s')
  member this.ReturnFrom a = a
let state = new StateBuilder()

let s max = 
    let rec Loop acc = state {
        let! n = getState
        do! putState (n + 1 - acc)
        if acc < max then
            return! Loop (acc + 2)
        else return acc
        }
    Loop 0

runState (s 100000 ()) 0

Answer 1

I'm afraid that you may be getting StackOverflowException because you're running the program in Debug mode with disabled tail-call generation. If you go to Project properties, then you can find Generate tail calls checkbox on the Build tab. When I create a new project, I can reproduce the behavior, but after checking this option, it works fine (even for much larger number of iterations).

The reason why tail-calls are disabled by default in the Debug mode is that it makes debugging a lot more difficult (if a call is performed as a tail-call, you wouldn't see it in the Call Stack window)

This would be a pretty silly reason for the error... sorry that I forgot to mention this when you asked earlier!