使用最終工作流程時，缺少尾部呼叫優化是一個障礙嗎？

Question

我使用從F＃規範的工作流程最終的修改版本我在Xbox的發展。看起來，Xbox上的.net框架不支持tail調用。因此，編譯時必須禁用尾部調用優化。儘管看起來這個限制可能會阻止在計算表達式中使用任何形式的循環，但我最初認爲「步進」可以避免這個問題：計算表達式中的遞歸函數f不會調用它本身直接返回一個包含調用f的lambda的最終值。

實驗表明，我是對的，而環（在計算表達式中使用時它們不會導致堆棧溢出），但不是遞歸函數。

爲了澄清，其工作原理：

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

在第二種情況下，棧跟蹤顯示呼叫的長序列「綁定@ 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實現有什麼問題嗎？

噢，我的頭！遞歸繼續傳遞給我頭痛......

編輯：「可以進行遞歸正在無害w.r.t.堆棧溢出」有一個名字，我剛剛得知。它被稱爲蹦牀。

Answer 1

替換最後呢！用回報！：

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

編輯

根據F＃的規格，呢！等待（）將被轉化爲綁定（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＃中的所有函數都必須返回一些東西。所以，如果我們看一下返回它的調用結果，後者又返回完成（R）的定義如下代碼

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

。

我做了兩個小任務測試。

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 

調用Computation Expression的MSDN文檔。