F# 中更安全的递归

Amy Peng

January 9th, 20240 0

本篇翻译于David Schaefer的Safer recursion in F#。

这是David Schaefer的客座博客文章。David 是一名专注于函数式编程的自由软件开发人员。他是G-Research开源团队的一员。他致力于改进 F# 开发者工具的生态系统。此外，他还帮助维护各种开源的 F# 项目。

在函数式编程中，用递归的方式去定义算法是很常见的场景。这非常符合我们想要避免突变的心态，而且这通常不会导致性能下降。编译器在优化阶段会尝试将递归定义重写为更高效的循环。

然而，编译器并不总是能够将递归转换为循环。从这里开始，就有一定的危险了。

堆栈帧与生产环境

当我们在函数 f 内部调用函数 g 时，这个操作通常会在进程的调用堆栈上创建一个新的堆栈帧。函数g完成后，程序此时就不再需要它的堆栈帧了，从而可以重用它的空间。

现在，理解堆栈帧的创建对于递归函数是至关重要的。一般来说，对于每个递归调用，都会创建一个新的堆栈帧。在开发期间，当规模较小时，这通常不会引起问题。但在后期的生产环境中，随着规模的扩大，程序会因堆栈溢出而突然崩溃。

在生产环境中，由于递归调用创建了太多堆栈帧，堆栈的所有空间都被用完了，所以runtime决定停止它。为了演示这一场景，请看一下这个递归函数：

let rec countDown1 n =
    if n = 0
    then 0
    else
        countDown1 (n - 1) + 1

生成的 IL 代码如下所示：

.method public static 
    int32 countDown1 (
        int32 n
    ) cil managed 
{
    // Method begins at RVA 0x2050
    // Header size: 1
    // Code size: 17 (0x11)
    .maxstack 8

    IL_0000: nop
    IL_0001: ldarg.0
    IL_0002: brtrue.s IL_0006

    IL_0004: ldc.i4.0
    IL_0005: ret

    IL_0006: ldarg.0
    IL_0007: ldc.i4.1
    IL_0008: sub
    IL_0009: call int32 Program::countDown1(int32)
    IL_000e: ldc.i4.1
    IL_000f: add
    IL_0010: ret
} // end of method Program::countDown1

您可以在 IL_0009 处看到递归调用。当使用 n = 1_000 来调用 coundDown1时（就像在开发过程中随意写的数值）代码会正确的结束调用，但使用 n = 1_000_000 来调用它时，它会因堆栈溢出而崩溃。

将上面的内容与以下内容进行比较：

let rec countDown2 n =
    if n = 0
    then 0
    else
        countDown2 (n - 1)

结果是：

.method public static 
    int32 countDown2 (
        int32 n
    ) cil managed 
{
    // Method begins at RVA 0x2064
    // Header size: 1
    // Code size: 13 (0xd)
    .maxstack 8

    // loop start
        IL_0000: nop
        IL_0001: ldarg.0
        IL_0002: brtrue.s IL_0006

        IL_0004: ldc.i4.0
        IL_0005: ret

        IL_0006: ldarg.0
        IL_0007: ldc.i4.1
        IL_0008: sub
        IL_0009: starg.s n
        IL_000b: br.s IL_0000
    // end loop
} // end of method Program::countDown2

两段代码的不同之处在于，在 countDown1 中，递归调用的返回值还需要通过加 1 来输出函数的最终值。相反，在 countDown2 中，递归调用的返回值也是函数本身的值。这意味着，递归调用是函数定义中的最后一条指令——这种方式称为尾递归。这种风格允许编译器将函数转换为循环，从而无需创建新的堆栈帧。

除了编译器有机会将递归函数重写为循环之外，使用尾递归还将打开另一个逃生门：IL 前缀 tail。在ECMA-335中，是这样解释的：

它表示不再需要当前方法的堆栈帧，因此可以在执行调用指令之前将其删除。由于调用返回的值将是此方法返回的值，因此可以将调用转换为跨方法跳转。

为了演示它，我们使用 RFC-1011 中的示例，稍后会详细介绍。考虑相互递归的 F# 函数：

let foo x =
    printfn "Foo: %x" x

[<TailCall>]
let rec bar x =
    match x with
    | 0 ->
        foo x           // OK: non-tail-recursive call to a function which doesn't share the current stack frame (i.e., 'bar' or 'baz').
        printfn "Zero"

    | 1 ->
        bar (x - 1)     // Warning: this call is not tail-recursive
        printfn "Uno"
        baz x           // OK: tail-recursive call.

    | x ->
        printfn "0x%08x" x
        bar (x - 1)     // OK: tail-recursive call.

and [<TailCall>] baz x =
    printfn "Baz!"
    bar (x - 1)         // OK: tail-recursive call.

这里我们得到 bar 中案例 1 的以下 IL 代码：

    ...
    IL_0030: ldarg.0
    IL_0031: ldc.i4.1
    IL_0032: sub
    IL_0033: call void Program::bar(int32)
    IL_0038: nop
    IL_0039: ldstr "Uno"
    IL_003e: newobj instance void class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat`5<class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit>::.ctor(string)
    IL_0043: stloc.0
    IL_0044: call class [netstandard]System.IO.TextWriter [netstandard]System.Console::get_Out()
    IL_0049: ldloc.0
    IL_004a: call !!0 [FSharp.Core]Microsoft.FSharp.Core.PrintfModule::PrintFormatLineToTextWriter<class [FSharp.Core]Microsoft.FSharp.Core.Unit>(class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat`4<!!0, class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit>)
    IL_004f: pop
    IL_0050: ldarg.0
    IL_0051: tail.
    IL_0053: call void Program::baz(int32)
    IL_0058: ret
    ...

因为对 baz 的调用以尾递归方式进行，所以编译器可以在 IL_0051 中使用tail前缀。将此与 IL_0033 中对 bar 的调用进行比较。

让编译器理解你的意图

所以，为了继续优雅的使用递归函数，我们只要用尾递归的方式去定义它们，对吗？

说起来容易做起来难。随着函数的复杂性增加以及不同的程序员对代码的处理，确保以尾递归方式定义函数可能是一项挑战。因此，编译器最好能根据开发人员的意图，对应该是尾递归的，但却不是尾递归的函数发出警告

这正是 RFC-1011 所发生的情况。 F# 编译器中实现了新属性 [<TailCall>]。开发人员可以使用它来明确自己的意图——这个函数应该是尾递归的。使用此属性注释的函数将被检查是否确实是尾递归，如果不是，则会发出警告。

对警告的分析是在编译器的优化阶段之后进行的，因此这时候对递归函数的任何重写都已应用。否则，编译器可能会对一个可以重写为循环的函数发出错误警告。在分析过程中，将遍历类型化抽象语法树 (TAST)，并检查对具有新属性的函数的递归调用是否以尾递归方式发生。例如，序列表达式中的第一个位置会导致函数调用不具有尾部递归性。

将这个新属性应用于countDown1，如下所示：

[<TailCall>]
let rec countDown1 n =
    if n = 0
    then 0
    else
        countDown1 (n - 1) + 1

对于 F# 8，编译器会针对函数的非尾递归定义发出警告：

Program.fs(6,9): warning FS3569: The member or function 'countDown1' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way. [tailrec_blog.fsproj]

借助编译器的这一功能，开发人员将能够更加专注于他们的工作领域，而不必担心编译代码的技术细节。

致谢

实现此警告是迄今为止我对 F# 编译器的最大贡献。在 PR 获得批准之前，我不得不尝试不同的方法。随后我还修复了一些错误，这些错误没有在 .NET 8 中得到解决，但应该会在第一个补丁发布时得到解决。

我要感谢一路上帮助过我的所有人，以及感谢Avi Avni在多年前开启了此功能的第一个PR 。

如果大家有任何的技术问题，欢迎到我们的官方的.NET中文论坛提问.