1

我目前正在自学 F#（通过 try f# 站点）。我有以下（恕我直言）尾递归函数用于一元谓词（int-> bool）的存在量化。

let rec exists bound predicate = 
    if (bound<0) then false
    elif predicate(bound) then true
    else exists (bound-1) predicate

现在这个函数也可以写成

let rec exists bound predicate = (bound+1>0) && (predicate(bound) || exists (bound-1) predicate)

但是，第二种实现不是尾递归的。问题是编译器是否会将其优化为尾递归？

更简单（好吧，这有点傻）的例子的情况如何，说

let rec hasNoRoot f = 
    if (f x = 0) then false
    else hasNoRoot (fun x -> f (x+1))

相对

let rec hasNoRoot f = (f 0 <> 0) && (hasNoRoot (fun x-> f(x+1)))

在第二个示例中，为了将函数（实际上是它的描述）识别为尾递归，编译器只需要“知道”为了评估连接，不一定必须评估两个连接。

感谢您的建议

4

1 回答 1

1

我使用 VS2012 (F# 3.0) 编译了您的“exists”和“hasNoRoot”函数的第二个版本并进行了优化，然后使用 .NET Reflector 检查了编译器生成的 IL。编译器确实优化了“hasNoRoot”函数，但不幸的是，没有优化“exists”函数。不过，这似乎是一个合理的优化，所以它可能会被添加到下一个版本的编译器中。

对于后代，这是编译器生成的内容：

.method public static bool exists(int32 bound, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool> predicate) cil managed
{
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { new int32[int32(0x2)] { int32(0x1), int32(0x1) } }
    .maxstack 8
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: ldc.i4.1 
    L_0003: add 
    L_0004: ldc.i4.0 
    L_0005: ble.s L_001c
    L_0007: ldarg.1 
    L_0008: ldarg.0 
    L_0009: callvirt instance !1 [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool>::Invoke(!0)
    L_000e: brfalse.s L_0012
    L_0010: ldc.i4.1 
    L_0011: ret 
    L_0012: ldarg.0 
    L_0013: ldc.i4.1 
    L_0014: sub 
    L_0015: ldarg.1 
    L_0016: starg.s predicate
    L_0018: starg.s bound
    L_001a: br.s L_0001
    L_001c: ldc.i4.0 
    L_001d: ret 
}
于 2013-04-06T21:53:16.503 回答