F# 编译器能否优化这些相互递归的函数？

Question

我编写了以下函数来检查括号表达式的有效性：

let matched str =
    let rec matched' stack = function
        | "" -> isEmpty stack
        | str ->
            match first str with
            | '(' | '[' | '{' as p -> matched' (push p stack) (rest str)
            | ')' -> matchClosing '(' stack str
            | ']' -> matchClosing '[' stack str
            | '}' -> matchClosing '{' stack str
            | _ -> matched' stack (rest str)

    and matchClosing expected stack s =
        match peek stack with
        | Some c when c = expected -> matched' (pop stack) (rest s)
        | _ -> false

    matched' [] str

如果我们将matchClosing的实现代入matched'，我们得到一个尾递归函数。 F# 编译器能否识别这一点并优化递归调用？

Answer 1

AFAICT 您的示例不完整，因此更难检查。我对其进行了一些补充并能够编译它。

使用ILSpy可以看出相互递归仍然存在：

// F#: | ')' -> matchClosing '(' stack str
case ')':
    return Program.matchClosing@39('(', stack, str);

// F#: | matched' t (tail s)
return Program.matched'@28(t, s.Tail);

因此，虽然在技术上应该可以将两个相互尾部递归函数解压缩到一个循环中，但这还没有完成。

检查 IL 代码时，我们发现调用标记有 .tail

// F#: | matchClosing '(' stack str
IL_0083: tail.  // Here
IL_0085: call bool Program::matchClosing@39(char, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<char>, valuetype Program/SubString)

// F#: | matched' t (tail s)
IL_002a: tail.  // Here
IL_002c: call bool Program::'matched\'@28'(class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<char>, valuetype Program/SubString)

.NET Jitter 处于发布模式，足以考虑 .tail 标志

// As you can see when debugging the code in WinDbg
02410bdf e8fbd3176b      call    clr!JIT_TailCall (6d58dfdf)

当我们在 WinDbg 中调试时，我们也看到堆栈没有增长。不幸的是，当查看 clr!JIT_TailCall 时，它做了相当多的工作，这意味着虽然它不消耗堆栈，但它消耗时钟周期，而不是像这里提到的那样：How to eliminate time spent in JIT_TailCall for functions that are genuinely non-recursive

但是在调试模式下（至少是旧版本的 Mono）.tail 标志被忽略

// As you can see when debugging the code in WinDbg (this is a normal call)
02f619c1 e8c2f4ffff      call    02f60e88

我们在 WinDbg 中调试时也看到堆栈增长。

所以你的问题的答案应该是：

不，F# 编译器无法将相互尾递归调用转换为循环。
但是，F# 编译器使用 .tail 属性标记调用
Release 模式 JIT:er 善意地考虑了 .tail 属性并生成不会增加堆栈（但效率低下）的尾部调用
在调试模式下（可能是单声道）.tail 属性被忽略并且 JIT:er 不会生成尾调用并且堆栈会增长。

F# 编译器能否优化这些相互递归的函数？

Can the F# compiler optimize these mutually recursive functions?

recursion

optimization

f#

tail-recursion

mutual-recursion