3

ECMA-335, III.2.4 指定tail.了可以在递归函数中使用的前缀。但是，我在 C# 和 F# 代码中都找不到它的用法。有没有使用 in 的例子？

4

1 回答 1

7

您不会在当前 MS C# 编译器生成的任何代码中找到它。您会在 F# 编译器生成的代码中找到它，但没有您想象的那么多，原因几乎相反。

现在，首先纠正您陈述中的一个错误：

ECMA-335，III.2.4 指定尾部。可用于递归函数的前缀。

严格来说，这不是真的。前缀可tail.用于尾调用；并非所有递归函数都是尾递归，也不是所有尾调用都是递归的一部分。

尾调用是对函数（包括 OOP 方法）的任何调用，其中该代码路径中的最后一个操作是进行该调用，然后返回它返回的值，或者如果被调用的函数没有返回值，则仅返回. 因此在：

int DoSomeCalls(int x)
{
  if(A(x))
    return B(x);
  if(DoSomeCalls(x * 2) > 3)
  {
    int ret = C(x);
    return ret;
  }
  return D(DoSomeCalls(x-1));
}

在这里，对B和的调用D是尾调用，因为在调用之后唯一要做的就是返回它们返回的值。对的调用C不是尾调用，但可以ret通过直接返回来删除多余的赋值，轻松地将其转换为尾调用。对 的调用A不是尾调用，也不是对 的调用DoSomeCalls，尽管它们是递归的。

现在，正常的函数调用机制是依赖于实现的，但通常涉及将调用后可能需要的值保存到堆栈上，将参数与当前指令位置一起放入堆栈和/或寄存器中（返回） ，移动指令指针，然后在指令指针移回调用完成后从寄存器或堆栈中读取返回值。使用尾调用可以跳过很多内容，因为被调用函数可以使用当前堆栈帧，然后直接返回到较早的调用者。

前缀请求通过tail.调用来完成此操作。

虽然这不一定与递归有关，但您在谈论递归时是正确的，因为在递归情况下消除尾调用的好处比其他情况更大；在实际使用函数调用机制时，在堆栈空间中进行 O(n) 的调用在堆栈空间中变为 O(1)，同时降低每个项目的常量时间成本（因此在此仍然是 O(n)考虑，但是 O(n) 时间意味着它需要 n×k 秒，并且我们有一个更小的 k)。在许多情况下，这可能是有效调用与抛出StackOverflowException.

现在，在 ECMA-335 中，有几个案例说明了如何tail.可能并不总是得到尊重。特别是 §III.2.4 中的文字指出：

也可能存在特定于实现的限制来阻止尾部。在某些情况下被服从的前缀。

在最宽松的情况下，我们可以将其解释为在各种情况下阻止它。

相反，允许抖动应用各种优化方式，包括执行尾调用消除，即使它不是由tail.

正因为如此，实际上有四种方法可以在 IL 中进行尾部调用消除：

  1. tail.在调用之前使用前缀，并尊重它（不保证）。
  2. 不要tail.在调用之前使用前缀，而是让抖动决定以任何方式应用它（甚至更不保证）。
  3. 使用jmpIL 指令，它实际上是尾调用消除的一种特殊情况（C# 从未使用过，因为它会生成无法验证的代码以获得通常相对较小的增益，尽管由于其相对简单，有时在手动编码时它可能是最简单的方法）。
  4. 重写整个方法以使用不同的方法；特别是可以重写从尾调用消除中获益最多的那种递归代码，以显式使用尾调用消除有效地将递归转换为的那种迭代算法。*（换句话说，尾调用消除发生在抖动甚至编译之前）。

（还有一种情况是调用是内联的，因为它不需要新的堆栈帧，并且确实通常总体上具有更强的改进，然后通常允许执行进一步的优化，但它不是' t 通常认为是尾调用消除的情况，因为它是不依赖于尾调用的调用消除）。

现在，在很多情况下，抖动的第一个实现倾向于不进行尾调用消除，即使它被请求。

同时，在 C# 方面，决定不发出tail.C# 的一般方法是不大量优化生成的代码。已经完成了一些优化（特别是删除死代码），但在大多数情况下，因为优化工作可能只是重复那些由抖动完成的优化（甚至妨碍他们）优化的缺点（更多的复杂性意味着更多可能的错误，并且 IL 会让许多开发人员更加困惑）相对大于好处。用于tail.是一个典型的例子，因为有时坚持尾调用实际上比使用 .NET 节省的成本要高，所以如果抖动已经在尝试解决，而这是一个好主意，那么 C# 编译器更有可能只是很多时候让事情变得更糟，其余的则没有任何区别。

还值得注意的是，对于像 C# 这样的 C 风格语言最常见的编码风格：

  1. 与其他语言中更常见的样式相比，开发人员往往不会编写特别受益于尾调用消除的代码。
  2. 开发人员倾向于知道如何通过将它们重写为迭代来优化最能从尾调用消除中受益的递归调用。
  3. 开发人员首先倾向于以迭代方式编写它们。

现在，出现了 F#。

由于 F# 所鼓励的函数式和声明式编程，在很多情况下，在 C# 中最自然地以迭代方式完成的工作最自然地通过递归方式完成。使用 C 风格语言进行黑客攻击的人学习将递归案例转换为迭代代码，使用 F# 风格语言进行黑客攻击的人学习将迭代案例转换为递归代码，以及将非尾调用递归代码转换为尾调用递归代码。

所以F#用tail.的很多。

它得到StackOverflowException了很多，因为抖动并没有兑现它。

这是导致抖动者增加消除尾音的情况的原因之一，无论是一般情况下，还是在tail.使用尾音的情况下都更进一步。

同时，F# 的人们不能仅仅依赖于tail.F# 的编译器将比 C# 的编译器进行更多的优化；就像我们可以像脚注中那样手动将递归调用重写为迭代，所以 F# 编译器在生成 IL 时会做同样的事情。

出于这个原因，很多时候，当您编写 F# 方法时，您希望看到一些使用tail..

tail.但是，当一个方法以相互递归的方式调用另一个方法时，F# 仍然会使用，例如：

let rec even n = 
  if n = 0 then 
    true 
  else
    odd (n-1)
and odd n =
  if n = 1 then 
    true 
  else
    even (n-1)

我完全从这个答案中偷走了，因为我只玩了一点 F#，所以我宁愿依赖比我更熟悉的人。

在这种情况下，由于tail-calls不在单个函数中，所以不能在IL编译点重写来消除它，所以它必须希望jitter来消除它，并使用tail.来增加很有可能会。

*将递归调用转换为迭代的示例是从递归调用开始，例如：

void ClearAllNodes(Node node)
{
  if(node != null)
  {
    node.Value = null;
    ClearAllNodes(node.Next)
  }
}

最简单的更改是手动添加尾调用消除所做的事情，我们自己设置参数，然后跳回到方法的开头：

void ClearAllNodes(Node node)
{
start:
  if(node != null)
  {
    node.Value = null;
    node = node.Next;
    goto start;
  }
}

既然有充分的理由可以避免的goto话，我们通常会通过更严格定义的循环机制将其更改为具有相同功能的东西：

void ClearAllNodes(Node node)
{
  while(node != null)
  {
    node.Value = null;
    node = node.Next;
  }
}
于 2014-02-17T00:36:57.080 回答