为什么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代码易于阅读.)

此代码 - 在使用优化和尾调功能进行编译时 - 会导致a 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#术语中:身体就是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不产生结果时需要抛弃的东西.

Answer 1

事实上,您已经回答了自己的问题.引用源代码中的注释,

// Throw away the unit result

是调用后的挂起操作,阻止编译器在此处使用尾调用.

Keith Battocchi发表了一篇很棒的博客文章,"F#中的Tail调用"(滚动到"限制/调用函数值返回单位"部分),它发现了很多细节.

用两个词来说:
通常,F#函数… -> unit被编译为.NET方法返回void.
但是,作为值处理的函数(例如,作为高阶函数的参数传递的函数)存储在类型的对象中,('a->'b)因此它们实际返回Microsoft.FSharp.Core.Unit,而不是void.
编译器需要在返回之前弹出unit堆栈的虚拟值.
因此,存在是一个挂起的操作后的递归调用,因此,编译器不能将其优化到尾调用.

好消息:

请注意,仅在将第一类函数用作值时才会出现此问题.调用返回void的普通.NET方法不会出现此问题,因为没有返回值从堆栈中弹出.