为什么 F# 编译器不为此函数创建尾调用？

Question

我在使用 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代码易于阅读。）

此代码 - 在启用优化和尾调用的情况下编译 - 导致 WhosebugException。我查看了 IL 代码，可以将问题追溯到 fix:

调用中的 lambda

.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
}

（我稍微修改了代码以便更容易阅读。）

WhosebugException的原因是对body的调用不是尾调用（最下面的callvirt指令）。其原因是因为编译器创建了对 lambda 的调用，实际上 returns Unit!

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

这是真的有意为之还是我可以做些什么？编译器处理此 lambda 的方式使定点组合器无法用于我打算使用它的所有目的。

我只想补充一点，只要你 return 结果是什么，它就可以正常工作。只有 return 什么都没有的功能无法按预期工作。

这个有效：

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
}

现在有尾声。一切正常。

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

.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 定义中的 (fix f) 不是此时发生的递归调用，而只是对 fix 本身的引用 - 以及参数 f - 被存储到一个名为 Program/fix@11 的闭包中，并作为参数传递给 lambda，然后通过该闭包实际调用 fix。

否则从一开始就是无限递归，fix就没用了

我使用的是 F# 版本 3.1.2，F# Interactive 版本 12.0.30815.0

请：

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

Answer 1

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

如果您想要尾递归 fix，请尝试以不同的方式定义它：

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

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

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

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

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

另请参阅：Generate tail call opcode

Answer 2

事实上，你已经回答了你自己的问题。引用源码注释，

// Throw away the unit result

是在调用之后的挂起操作，防止编译器在这里使用尾调用。

Keith Battocchi 有一篇很棒的博客 post，"Tail calls in F#"（滚动到 "Limitations / Calling function values returning unit" 部分）发现了很多细节。

两个字：
通常，F# 函数 … -> unit 被编译为 .NET 方法 returning void.
但是，函数被视为值（例如，那些作为参数传递给高阶函数的函数）存储在类型 ('a->'b) 的对象中，因此它们实际上 return Microsoft.FSharp.Core.Unit，不是 void.
编译器需要在 returning.
之前将虚拟 unit 值从堆栈中弹出因此，在递归调用之后是一个未决操作，因此编译器无法将其优化为尾调用。

好消息：

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.

为什么 F# 编译器不为此函数创建尾调用？

Why does the F# compiler not create a tail call for this function?

f#

tail-recursion

tail-call-optimization

f#-3.1

fixpoint-combinators

请：