Czy brak optymalizacji wywołań końcowych jest przeszkodą podczas korzystania z przepływu pracy W końcu?

Question

Używam zmodyfikowanej wersji Ostatecznie workflow ze specyfikacji F # do mojego rozwoju na Xboksie. Wydaje się, że platforma .net na Xboksie nie obsługuje połączeń wychodzących. Z tego powodu podczas kompilacji muszę wyłączyć optymalizację połączeń końcowych.

Chociaż może się wydawać, że to ograniczenie uniemożliwi użycie jakiejkolwiek formy pętli w wyrażeniach obliczeniowych, początkowo myślałem, że "krokowanie" pozwoli uniknąć tego problemu: funkcja rekurencyjna f w wyrażeniu obliczeniowym nie nazywa się sama bezpośrednio, zamiast tego zwraca wartość końcową zawierającą lambdę, która wywołuje f.

Eksperymenty wskazują, że miałem rację co do pętli (nie powodują one przepełnień stosu w wyrażeniach obliczeniowych), ale nie dotyczą funkcji rekursywnych.

Aby wyjaśnić to działa:

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

To powoduje przepełnienie stosu:

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

W drugim przypadku, ślad stosu przedstawia długą sekwencję wywołań „wiążą @ 17- 1 ", którego kod przedstawiono poniżej. Numer wiersza pojawiający się w zapisie stosu to linia 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) 

Gdzie się mylę? Czy moje rozumowanie o "steppable recursion" jest nieszkodliwe w.r.t. przepełnienie stosu jest nieprawidłowe? Czy coś jest nie tak z moją implementacją bind?

O, moja głowa! Kontynuacja - przekazywanie z rekursją daje mi bóle głowy ...

EDYCJA: "rekurencja krokowa jest nieszkodliwym przepełnieniem stosów w.r.t" ma nazwę, właśnie się nauczyłem. Nazywa się to trampoliną.

Answer 1

wymienić ostatnie zrobić! z 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

według specyfikacji F #, zrobić! wait() zostaną przekształcone do Bind (wait(), zabawy() -> Zero()), więc każde wywołanie rekurencyjne wzrośnie poziom Bind gniazdowania (jak widać w stacktrace)

w przeciwnym zamian! wait() natychmiast zwróci nowe obliczenia "W końcu", które mogą zostać wykorzystane w następnym kroku.

Answer 2

Jednym ze sposobów zrozumienia, co się dzieje, jest sprawdzenie sygnatur typu.

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) 

Wszystkie funkcje w f # muszą zwrócić coś. Więc następujący kod

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

jest równoważna

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

Jeśli spojrzymy na definicji zwrotu wywołuje efekt który z kolei zwraca zakończone (R).

Zrobiłem dwa małe testy dla zadania.

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

Z niektórymi oprzyrządowaniem drukuje.

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 na numerach Computation Expression.