wordpress邮件插件,windows优化大师值得买吗,ui界面设计app,凡科快图下载作者#xff1a;David Schaefer 排版#xff1a;Alan Wang 这是 David Schaefer 的客座博客文章。David 是一名专注于函数式编程的自由软件开发人员。他是 G-Research 开源团队的一员。他致力于改进 F# 开发者工具的生态系统。此外#xff0c;他还帮助维护各种开源的 F# 项目… 作者David Schaefer 排版Alan Wang 这是 David Schaefer 的客座博客文章。David 是一名专注于函数式编程的自由软件开发人员。他是 G-Research 开源团队的一员。他致力于改进 F# 开发者工具的生态系统。此外他还帮助维护各种开源的 F# 项目。
在函数式编程中用递归的方式去定义算法是很常见的场景。这非常符合我们想要避免突变的心态而且这通常不会导致性能下降。编译器在优化阶段会尝试将递归定义重写为更高效的循环。
然而编译器并不总是能够将递归转换为循环。从这里开始就有一定的危险了。
堆栈帧与生产环境
当我们在函数 f 内部调用函数 g 时这个操作通常会在进程的调用堆栈上创建一个新的堆栈帧。函数 g 完成后程序此时就不再需要它的堆栈帧了从而可以重用它的空间。
现在理解堆栈帧的创建对于递归函数是至关重要的。一般来说对于每个递归调用都会创建一个新的堆栈帧。在开发期间当规模较小时这通常不会引起问题。但在后期的生产环境中随着规模的扩大程序会因堆栈溢出而突然崩溃。
在生产环境中由于递归调用创建了太多堆栈帧堆栈的所有空间都被用完了所以 runtime 决定停止它。为了演示这一场景请看一下这个递归函数
let rec countDown1 n if n 0then 0elsecountDown1 (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 8IL_0000: nopIL_0001: ldarg.0IL_0002: brtrue.s IL_0006IL_0004: ldc.i4.0IL_0005: retIL_0006: ldarg.0IL_0007: ldc.i4.1IL_0008: subIL_0009: call int32 Program::countDown1(int32)IL_000e: ldc.i4.1IL_000f: addIL_0010: ret
} // end of method Program::countDown1您可以在 IL_0009 处看到递归调用。当使用 n 1_000 来调用 coundDown1时就像在开发过程中随意写的数值代码会正确的结束调用但使用 n 1_000_000 来调用它时它会因堆栈溢出而崩溃。
将上面的内容与以下内容进行比较
let rec countDown2 n if n 0then 0elsecountDown2 (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 startIL_0000: nopIL_0001: ldarg.0IL_0002: brtrue.s IL_0006IL_0004: ldc.i4.0IL_0005: retIL_0006: ldarg.0IL_0007: ldc.i4.1IL_0008: subIL_0009: starg.s nIL_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 doesnt share the current stack frame (i.e., bar or baz).printfn Zero| 1 -bar (x - 1) // Warning: this call is not tail-recursiveprintfn Unobaz x // OK: tail-recursive call.| x -printfn 0x%08x xbar (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.0IL_0031: ldc.i4.1IL_0032: subIL_0033: call void Program::bar(int32)IL_0038: nopIL_0039: ldstr UnoIL_003e: newobj instance void class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat5class [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.0IL_0044: call class [netstandard]System.IO.TextWriter [netstandard]System.Console::get_Out()IL_0049: ldloc.0IL_004a: call !!0 [FSharp.Core]Microsoft.FSharp.Core.PrintfModule::PrintFormatLineToTextWriterclass [FSharp.Core]Microsoft.FSharp.Core.Unit(class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.PrintfFormat4!!0, class [System.Runtime]System.IO.TextWriter, class [FSharp.Core]Microsoft.FSharp.Core.Unit, class [FSharp.Core]Microsoft.FSharp.Core.Unit)IL_004f: popIL_0050: ldarg.0IL_0051: tail.IL_0053: call void Program::baz(int32)IL_0058: ret...因为对 baz 的调用以尾递归方式进行所以编译器可以在 IL_0051 中使用 tail 前缀。将此与 IL_0033 中对 bar 的调用进行比较。
让编译器理解你的意图
所以为了继续优雅的使用递归函数我们只要用尾递归的方式去定义它们对吗
说起来容易做起来难。随着函数的复杂性增加以及不同的程序员对代码的处理确保以尾递归方式定义函数可能是一项挑战。因此编译器最好能根据开发人员的意图对应该是尾递归的但却不是尾递归的函数发出警告。
这正是 RFC-1011 所发生的情况。F# 编译器中实现了新属性 []。开发人员可以使用它来明确自己的意图——这个函数应该是尾递归的。使用此属性注释的函数将被检查是否确实是尾递归如果不是则会发出警告。
对警告的分析是在编译器的优化阶段之后进行的因此这时候对递归函数的任何重写都已应用。否则编译器可能会对一个可以重写为循环的函数发出错误警告。在分析过程中将遍历类型化抽象语法树TAST并检查对具有新属性的函数的递归调用是否以尾递归方式发生。例如序列表达式中的第一个位置会导致函数调用不具有尾部递归性。
将这个新属性应用于 countDown1如下所示
[TailCall]
let rec countDown1 n if n 0then 0elsecountDown1 (n - 1) 1对于 F# 8编译器会针对函数的非尾递归定义发出警告
[TailCall]
let rec countDown1 n if n 0then 0elsecountDown1 (n - 1) 1借助编译器的这一功能开发人员将能够更加专注于他们的工作领域而不必担心编译代码的技术细节。
致谢
实现此警告是迄今为止我对 F# 编译器的最大贡献。在 PR 获得批准之前我不得不尝试不同的方法。随后我还修复了一些错误这些错误没有在 .NET 8 中得到解决但应该会在第一个补丁发布时得到解决。
我要感谢一路上帮助过我的所有人以及感谢 Avi Avni 在多年前开启了此功能的第一个 PR。
