F# 是否使用 |> Option.bind 执行 TCO（尾调用优化）

Question

这是我的函数：

let rec applyAll rules expr =
  rules
  |> List.fold (fun state rule ->
    match state with
    | Some e ->
      match applyRule rule e with
      | Some newE -> Some newE
      | None -> Some e
    | None -> applyRule rule expr) None
  |> Option.bind (applyAll rules)

它采用一组规则并应用它们，直到输入表达式尽可能地减少。我可以将 Option.bind 重写为 match 表达式，它显然会利用尾调用优化。然而，这对我来说更优雅，所以我想保持原样，除非它会不必要地消耗堆栈。 F# 是否使用此代码执行 TCO？

编辑：此代码总是 returns None；我会解决这个问题，但我认为这个问题仍然有意义。

Answer 1

答案是"no."

如您所说，调用将被"expanding" Option.Bind 优化为match 表达式。这样做会将对 applyAll 的递归调用正确地放在尾部位置。

随着Option.Bind在尾部位置，栈会像

一样增长

+ …
+ applyAll
+ Option.Bind
+ applyAll
+ Option.Bind
_ applyAll

并且 F# 编译器不会对此进行优化。

Answer 2

我已将您的代码粘贴到一个文件中 tco.fs。我添加了一个 applyRule 函数以使其可编译。

tco.fs

let applyRule rule exp =
    Some ""

let rec applyAll rules expr =
  rules
  |> List.fold (fun state rule ->
    match state with
    | Some e ->
      match applyRule rule e with
      | Some newE -> Some newE
      | None -> Some e
    | None -> applyRule rule expr) None
  |> Option.bind (applyAll rules)

然后我做了一个批处理文件来分析IL。

compile_and_dasm.bat

SET ILDASM="C:\Program Files (x86)\Microsoft SDKs\Windows\v10.0A\bin\NETFX 4.6 Tools\ildasm.exe"

Fsc tco.fs

%ILDASM% /out=tco.il /NOBAR /tok tco.exe

作为输出，我们发现 tco.il 包含 IL。相关函数在这里

.method /*06000002*/ public static class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!b> 
      applyAll<a,b>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!!a> rules,
                    string expr) cil managed
{
    .custom /*0C000003:0A000003*/ instance void [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute/*01000007*/::.ctor(int32[]) /* 0A000003 */ = ( 01 00 02 00 00 00 01 00 00 00 01 00 00 00 00 00 ) 
    // Code size       26 (0x1a)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  newobj     instance void class Tco/*02000002*//applyAll@13/*02000003*/<!!b,!!a>/*1B000004*/::.ctor(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!1>) /* 0A000004 */
    IL_0006:  newobj     instance void class Tco/*02000002*//'applyAll@6-1'/*02000004*/<!!a>/*1B000005*/::.ctor() /* 0A000005 */
    IL_000b:  ldnull
    IL_000c:  ldarg.0
    IL_000d:  call       !!1 [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.ListModule/*01000009*/::Fold<!!0,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<string>>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!1,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!0,!!1>>,
                                                                                                                                                                                                             !!1,
                                                                                                                                                                                                             class [FSharp.Core/*23000002*/]Microsoft.FSharp.Collections.FSharpList`1/*01000008*/<!!0>) /* 2B000001 */
    IL_0012:  tail.
    IL_0014:  call       class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!1> [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.OptionModule/*0100000A*/::Bind<string,!!1>(class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpFunc`2/*01000002*/<!!0,class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!1>>,
                                                                                                                                                                                                        class [FSharp.Core/*23000002*/]Microsoft.FSharp.Core.FSharpOption`1/*01000003*/<!!0>) /* 2B000002 */
    IL_0019:  ret
} // end of method Tco::applyAll

我们看到这里生成了尾操作码。这是 IL 编译器对 JIT 编译器（实际上生成可执行机器代码）的提示，这里应该可以进行尾调用。

尾调用是否实际执行取决于 JIT 编译器，可以阅读 here。

F# 是否使用 |> Option.bind 执行 TCO（尾调用优化）

Does F# do TCO (tail call optimization) with |> Option.bind

f#

tail-recursion