Is the lack of tail call optimization an obstacle when using the Eventually workflow?

Question

I'm using a modified version of the Eventually workflow from the F# spec for my development on Xbox. The .net framework on the Xbox does not support tail calls, it seems. Because of this, I have to disable tail call optimization when compiling.

Although it might seem at first that this restriction would prevent the use of any form of looping in computation expressions, I initially thought that "stepping" would avoid that problem: A recursive function f in the computation expression does not call itself directly, instead it returns an Eventually value containing a lambda which calls f.

Experiments indicate that I was right about while loops (they don't cause stack overflows when used in computation expressions), but not about recursive functions.

To clarify, this works:

// Wait until "start" or "A" is pressed on one of the gamepads.
// Set "player" when that happens.
let player : PlayerIndex option ref = ref None
while (!player).IsNone do
    for p in all_players do
        let state = GamePad.GetState(p)
        if state.IsConnected
            && (state.Buttons.Start = ButtonState.Pressed
                || state.Buttons.A = ButtonState.Pressed) then
            player := Some p
    do! sys.WaitNextFrame()

This causes a stack overflow:

// Wait until "start" is pressed on the controlling gamepad.
let rec wait() = task {
    input.Update()
    if not (input.IsStartPressed()) then
        do! sys.WaitNextFrame()
        do! wait()
}

In the second case, the stack trace shows a long sequence of calls to "bind@17-1", whose code is shown below. The line number appearing in the stack trace is line 17.

let rec bind k e =
    match e with
    | Completed r ->
        Running(fun () -> k r)
    | Running f ->
        Running(fun () -> f() |> bind k)  // line 17
    | Blocked(dt, f) ->
        Blocked(dt, fun () -> f() |> bind k)
    | BlockedNextFrame f ->
        BlockedNextFrame(fun () -> f() |> bind k)
    | Yield f ->
        Yield(fun () -> f() |> bind k)

Where am I wrong? Is my reasoning about "steppable recursion" being harmless w.r.t. stack overflows incorrect? Is there something wrong with my implementation of bind?

Oh my head! Continuation-passing with recursion gives me headaches...

EDIT: "steppable recursion being harmless w.r.t. stack overflows" has got a name, I have just learned. It's called a trampoline.

Answer 1

replace the last do! with return!:

// Wait until "start" is pressed on the controlling gamepad.
let rec wait() = task {
    input.Update()
    if not (input.IsStartPressed()) then
       do! sys.WaitNextFrame()
       return! wait()
}

EDIT

according to F# spec, do! wait() will be transformed to Bind(wait(), fun() -> Zero()), so every recursive call will increase level of Bind nesting (as you see in stacktrace)

in opposite return! wait() will immediately return new 'Eventually' computation that can be consumed on the next step.