Является ли отсутствие оптимизации хвостового вызова препятствием при использовании рабочего процесса «В конце концов»?

Question

Я использую модифицированную версию рабочего процесса Eventually из спецификации F # для своей разработки на Xbox. .NET Framework на Xbox, кажется, не поддерживает хвостовые вызовы. Из-за этого я должен отключить оптимизацию хвостового вызова при компиляции.

Хотя на первый взгляд может показаться, что это ограничение предотвратит использование любой формы зацикливания в выражениях вычислений, я изначально думал, что «шагание» позволит избежать этой проблемы: рекурсивная функция f в выражении вычисления не вызывает себя напрямую вместо этого он возвращает значение «В конце концов», содержащее лямбду, которое вызывает f.

Эксперименты показывают, что я был прав насчет циклов while (они не вызывают переполнения стека при использовании в выражениях вычислений), но не в отношении рекурсивных функций.

Чтобы уточнить, это работает:

// 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()

Это вызывает переполнение стека:

// 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()
}

Во втором случае трассировка стека показывает длинную последовательность вызовов «bind @ 17-1», код которых показан ниже. Номер строки в трассировке стека - строка 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)

Где я не прав? Являются ли мои рассуждения о "степной рекурсии" безвредными в отношении W.r.t. переполнение стека неверно? Что-то не так с моей реализацией bind?

О, моя голова! Продолжение прохождения с рекурсией вызывает головную боль ...

РЕДАКТИРОВАТЬ: «степпируемая рекурсия безвредна при переполнении стека». У меня есть имя, которое я только что узнал. Это называется батут.

Answer 1

заменить последний do! на 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

согласно спецификации F #, делай! wait () будет преобразовано в Bind (wait (), fun () -> Zero ()), поэтому каждый рекурсивный вызов увеличивает уровень вложенности Bind (как вы видите в stacktrace)

в противоположном возвращение! wait () немедленно вернет новое вычисление «В конце концов», которое можно использовать на следующем шаге.

Answer 2

Один из способов понять, что происходит, - посмотреть на сигнатуры типов.

type TaskBuilder() =
    // do!
    // Eventually<'a> * ('a -> Eventually<'b>) -> Eventually<'b>
    member x.Bind(e, f) = bind f e

    // return!
    // Eventually<'a> -> Eventually<'a>
    member x.ReturnFrom(r : Eventually<_>) = r

    // return
    // 'a -> Eventually<'a>
    member x.Return(r) = result r


let result r = Completed(r)

Все функции в f # должны что-то возвращать. Итак, следующий код

let rec wait() = task {
    input.Update()
    if not (input.IsStartPressed()) then
        do! sys.WaitNextFrame()
        do! wait()
}

эквивалентно

let rec wait() = task {
    input.Update()
    if not (input.IsStartPressed()) then
        do! sys.WaitNextFrame()
        do! wait()
        return ()
}

Если мы посмотрим на определение Return, оно вызывает результат, который, в свою очередь, возвращает Completed (r).

Я сделал два небольших теста для задания.

let test7() =
    let sch = new Scheduler()
    let sys = new Environment(sch)

    let rec hop i = task {
        printfn "%i: Hop!" i
        //do! sys.Wait(1.0f)
        if i > 0 then
            do! hop (i - 1)
            return ()
    }

    runAllFixed sch 0.1f [| hop 3 |]

let test8() =
    let sch = new Scheduler()
    let sys = new Environment(sch)

    let rec hop i = task {
        printfn "%i: Hop!" i
        //do! sys.Wait(1.0f)
        if i > 0 then
            return! hop (i - 1)
    }

    runAllFixed sch 0.1f [| hop 3 |]

test7()
printfn "\n" 
test8()

С некоторыми инструментами он печатает.

Delay 3: Hop!
Delay Bind Running 2: Hop!
Delay Bind Running Running 1: Hop!
Delay Bind Running Running Running 0: Hop!
Zero Completed Running Running Return Completed Running Return Completed Return


Delay 3: Hop!
Delay ReturnFrom 2: Hop!
Delay ReturnFrom 1: Hop!
Delay ReturnFrom 0: Hop!
Zero

MSDN doc on Выражение вычислений звонки.