최종 워크 플로우를 사용할 때 꼬리 호출 최적화가 어려움이 있습니까?

Question

Xbox에서의 개발을 위해 F # 사양의 최종 워크 플로의 수정 된 버전을 사용하고 있습니다. Xbox의 .net 프레임 워크는 꼬리 호출을 지원하지 않습니다. 이 때문에 컴파일 할 때 꼬리 호출 최적화를 비활성화해야합니다.

처음에는이 제한으로 인해 계산식에서 루핑 형식이 사용되지 않는 것처럼 보일 수도 있지만 처음에는 "스테핑"으로 문제를 피할 수 있다고 생각했습니다. 계산식의 재귀 함수 f가 자체를 호출하지 않습니다. 대신에 f를 호출하는 람다를 포함하는 Eventually 값을 반환합니다.

실험은 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() 
} 

을, 스택 추적 통화의 긴 순서를 보여줍니다에 "바인드 @ 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) 

어디에서 잘못 되었나요? "steppable recursion"에 대한 나의 추론은 무해한가? 스택 오버플로가 잘못 되었습니까? 바인드 구현에 문제가 있습니까?

오 마이 머리! 재귀와 지속적인 통과는 내게 두통을 준다 ...

EDIT : "무거운 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() 

일부 계기로 인쇄됩니다. Computation Expression 전화에

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의 문서.