5

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

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

如果我们替换matchClosinginto的实现matched'，我们会得到一个尾递归函数。F# 编译器可以识别这一点并优化递归调用吗？

4

1 回答 1

9

AFAICT 您的示例不完整，这使得检查变得更加困难。我对其进行了一些补充，并且能够编译它。

使用ILSpyone 可以看到相互递归仍然存在：

// 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它做了相当多的工作，虽然它不消耗堆栈，但它消耗时钟周期，而不是像这里指出的那样：如何消除真正非递归的函数在 JIT_TailCall 中花费的时间

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

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

当我们在 WinDbg 中调试时，我们还看到堆栈增长。

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

  1. 不，F# 编译器无法将相互尾递归调用转换为循环。
  2. .tail但是，F# 编译器使用属性标记调用
  3. 发布模式 JIT:er 善意地考虑.tail属性并生成不增长堆栈的尾调用（但效率低下）
  4. 在调试模式（可能是单声道）.tail中，属性会被忽略，并且 JIT:er 不会生成尾调用，并且堆栈会增长。
于 2017-02-02T20:35:47.340 回答