10

我正在使用 F# 规范中的最终工作流的修改版本在 Xbox 上进行开发。Xbox 上的 .net 框架似乎不支持尾调用。因此，我必须在编译时禁用尾调用优化。

尽管乍一看这种限制会阻止在计算表达式中使用任何形式的循环，但我最初认为“步进”会避免这个问题：计算表达式中的递归函数 f 不会直接调用自身，而是它返回包含调用 f 的 lambda 的最终值。

实验表明我对 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)

我哪里错了？我关于“​​可步进递归”是无害的 wrt 堆栈溢出的推理不正确吗？我的绑定实现有问题吗？

哦，我的头！递归的继续传递让我头疼......

编辑：“可步进递归是无害的 wrt 堆栈溢出”有一个名字，我刚刚了解到。它被称为蹦床。

4

2 回答 2

11

替换最后一个做！与回报！：

// 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()将转换为 Bind(wait(), fun() -> Zero())，因此每次递归调用都会增加 Bind 嵌套的级别（如您在堆栈跟踪中看到的）

在相反的回报！wait()将立即返回可以在下一步使用的新的“最终”计算。

于 2011-02-04T17:27:07.600 回答
6

了解正在发生的事情的一种方法是查看类型签名。

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 的定义，它会调用 result，而 result 又会返回 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 文档。

于 2011-02-05T03:52:17.463 回答