8

我在使用 F# 中的定点组合器时遇到问题：

let rec fix f a = f (fix f) a

fix (fun body num -> 
    if num = 1000000 
    then System.Console.WriteLine "Done!" 
    else body (num + 1)
) 0

（这段代码只是为了演示问题，它是专门写的，以便生成的IL代码易于阅读。）

这段代码——当编译时启用了优化和尾调用——会导致StackOverflowException. 我查看了 IL 代码，可以将问题追溯到调用中的 lambda fix：

.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014

ldstr "Done!"
call void Console::WriteLine(string)
ret

IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack.
ldc.i4.1
add

// Invoke the 'body' function with num+1 as argument.
callvirt instance !1 class FSharpFunc`2<int32, class Unit>::Invoke(!0)
// Throw away the unit result.
pop
ret
}

（我稍微修改了代码，以便于阅读。）

的原因StackOverflowException是调用body没有尾调用（callvirt底部的指令）。原因是编译器创建了对实际返回的 lambda 的调用Unit！

所以用 C# 术语来说：Body 是Func<Int32,Unit>它真正应该是Action<Int32>. 由于调用返回的东西必须被丢弃，所以它不能是尾调用。另请注意，该方法f@1被编译为void，而不是Unit，这就是必须丢弃调用参数的结果的原因。

这实际上是有意的还是我可以做些什么？编译器处理这个 lambda 的方式使得定点组合器对于我打算使用它的所有目的都无用。

我只想补充一点，只要您返回一些结果，它就可以正常工作。只有不返回任何内容的函数才能按预期工作。

这有效：

let rec fix f a = f (fix f) a

fix (fun body num ->
    if num = 1000000
    then System.Console.WriteLine "Done!"; 0
    else body (num + 1)
) 0
|> ignore

现在这是为 lambda 生成的代码：

.method assembly static int32 f@11 (class FSharpFunc`2<int32, int32> body, int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0015

ldstr "Done!"
call void Console::WriteLine(string)
ldc.i4.0
ret

IL_0015: ldarg.0
ldarg.1
ldc.i4.1
add
tail.
callvirt instance !1 class FSharpFunc`2<int32, int32>::Invoke(!0)
ret
}

现在有一个尾声。一切正常。

IL代码fix（用于评论中的讨论）：

.method public static !!b fix<a, b> (class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, class FSharpFunc`2<!!a, !!b>> f, !!a a) 
{    
    ldarg.0
    ldarg.0
    newobj instance void class Program/fix@11<!!a, !!b>::.ctor(class FSharpFunc`2<class FSharpFunc`2<!0, !1>, class FSharpFunc`2<!0, !1>>)
    ldarg.1
    tail.
    call !!0 class FSharpFunc`2<class FSharpFunc`2<!!a, !!b>, !!a>::InvokeFast<!!b>(class FSharpFunc`2<!0, class FSharpFunc`2<!1, !!0>>, !0, !1)
    ret
}

所以在我看来(fix f)，fix 的定义内部并不是此时发生的递归调用，而只是对fix自身的引用——连同参数f——被存储到一个被调用的闭包Program/fix@11中并传递给 lambda作为一个参数，然后fix通过这个闭包实际调用。

否则，这将是从一开始就无限递归并且fix毫无用处。

我正在使用 F# 版本 3.1.2，F# Interactive 版本 12.0.30815.0

请：

我对替代解决方案不感兴趣。我只想知道为什么Unit当 lambda 不产生结果时编译器会返回需要丢弃的 a 。

4

2 回答 2

7

In fact, you have already answered your own question. Quoting the comment from the source code,

// Throw away the unit result

is the pending operation after the call, preventing the compiler from using a tail call here.

There's a great blog post by Keith Battocchi, "Tail calls in F#" (scroll to section "Limitations / Calling function values returning unit") which discovers a lot of details.

In two words:
Normally, F# functions … -> unit are compiled to .NET methods returning void.
However, functions treated as values (e.g., those passed as arguments to higher-order functions) are stored in objects of type ('a->'b) so they actually return Microsoft.FSharp.Core.Unit, not void.
The compiler needs to pop the dummy unit value off of the stack before returning.
Therefore, there is a pending operation after the recursive call, and therefore the compiler can't optimize it to a tail call.

Good news:

Note that this issue only arises when using first-class functions as values. Calling normal .NET methods which return void doesn’t present this problem, because there is no return value to pop off of the stack.

于 2015-04-18T22:31:16.173 回答
3

要尾调用优化您的代码，编译器必须尾调用优化fix。修复了高阶函数，编译器很困惑。

如果您想要一个 tail-recursive fix，请尝试以不同的方式定义它：

let rec iter p f x =
  if p x then x
  else iter p f (f x)

iter ((=) 100000000) ((+) 1) 0

有趣的事实：fix由于 Haskell 评估表达式的方式，您不会在 Haskell 中堆栈溢出：Haskell 使用图形缩减，这与使用调用堆栈不同。

let fix f = f (fix f)
fix (\f x -> if x == 100000000 then -1 else f (x + 1)) 0

说到您的第二个示例，.NET 即时可能能够在运行时优化尾调用。由于它是一种优化，它取决于运行时的智能程度：是否有返回值可能会阻碍 JIT 优化器。例如，我机器上的 Mono 没有优化您的第二个示例。

另请参阅：生成尾调用操作码

于 2015-04-18T18:24:19.810 回答