c# - 尾部。 ILAsm中的前缀–使用示例吗？

Question

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

Answer 1

您不会在当前的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的多余分配，轻松地将其转换为1。对 A的调用不是尾部调用，对 DoSomeCalls的调用也不是尾部调用，尽管它们是递归的。

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

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

尽管这不一定与递归相关，但是您在谈论递归时是正确的，因为在递归情况下消除尾部调用的好处比其他情况要大。实际使用函数调用机制时，使在堆栈空间中为O（n）的调用在堆栈空间中变为O（1），同时降低了每个项目的恒定时间成本（因此在此情况下仍为O（n）） ，但是O（n）时间意味着需要n×k秒，而我们有一个较小的k）。在许多情况下，这可能是有效的调用与引发 StackOverflowException的调用之间的区别。

现在，在ECMA-335中，有些案例说明了 tail.可能不总是被兑现的方式。 §III.2.4中特别指出：


  也可以有特定于实现的限制来防止尾巴。在某些情况下不遵守前缀。


从最宽松的角度来看，我们可以将其解释为在各种情况下都可以防止这种情况发生。

相反，即使 tail.没有要求，也允许抖动应用所有方式的优化，包括执行尾部消除。

因此，在IL中实际上有四种方法可以消除尾音：


在呼叫之前使用 tail.前缀，并对其进行尊重（不保证）。
请勿在呼叫前使用 tail.前缀，但应由抖动决定以任何方式应用它（甚至不能保证）。
使用 jmp IL指令，该指令实际上是消除尾部调用的一种特殊情况（C＃从未使用过，因为它通常会以相对较小的增益生成无法验证的代码，尽管有时由于其相对性，这有时是最简单的手动编码方法简单）。
重新编写整个方法以使用其他方法；特别是可以从尾调用消除中受益最大的那种递归代码，可以重写以显式地使用该尾调用消除有效地将递归转化为的迭代算法。*（换句话说，发生了尾调用消除在插页甚至编译之前）。


（在某些情况下，该调用是内联的，因为它不需要新的堆栈框架，并且通常在总体上确实有更强的改进，然后通常可以进行进一步的优化，但这不是。”通常认为这是消除尾部呼叫的一种情况，因为这是一种消除呼叫的方式，并不取决于它是否为尾部呼叫。

现在，抖动的第一个实现在很多情况下都倾向于不进行尾部呼叫消除，即使有要求也是如此。

同时，在C＃方面，有一个决定是不发出 tail.。C＃存在一种通用方法，即不对所生成的代码进行大量优化。进行了一些优化（尤其是清除死代码），但是在大多数情况下，由于优化工作只能复制抖动（甚至阻碍）进行的优化工作（更多的复杂性意味着更多的错误） ，而IL对许多开发人员来说更容易造成混淆），相对而言，其优势要大得多。使用 tail.是一个典型的例子，因为有时坚持尾调用实际上比使用.NET节省的成本要多，因此，如果在一个好主意时抖动已经在试图解决的话，则更大的机会是C＃编译器会使很多情况变得更糟，而其他情况则没有任何变化。

还值得注意的是，在C＃语言（例如C＃）中最常见的编码样式是：


与其他语言中更常见的样式相比，开发人员往往不会编写特别能从消除尾部调用中受益的代码。
开发人员倾向于知道如何优化递归调用的种类，方法是将它们重写为迭代的，这将最受益于尾部调用消除。
开发人员往往一开始就以迭代方式编写它们。


现在，F＃出现了。

在F＃鼓励的功能性和声明性编程中，很多情况下，在C＃中最自然地以迭代方式完成的事情最自然地是通过递归方法来完成的。用C风格的语言进行编程的人们学会将递归的情况转换为迭代代码，而用F＃风格的语言进行编程的人们则学会了将迭代的情况转换为递归代码，而无尾调用的递归代码则转换为尾部调用的递归代码。

因此，F＃经常使用 tail.。

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

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

同时，F＃员工不能仅仅依赖 tail.，因此F＃的编译器比C＃的编译器优化程度更高。正如我们可以像脚注中那样手动重写递归调用以使其具有迭代性，因此F＃编译器在生成IL时也执行等效操作。

因此，在很多时候，当您编写F＃方法时，希望看到一些使用 tail.的IL，实际上得到的是迭代地执行等效操作的IL。

但是，当一个方法以相互递归的方式调用另一个方法时，F＃仍将使用 tail.：

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)

我完全是从 this answer那里偷来的，因为我只在F＃上玩过一点，所以我宁愿依靠比我更熟悉的人。

在这种情况下，由于尾部调用不在单个函数中，因此不能仅在IL编译点重写尾部调用以消除它，因此它必须希望抖动能够消除它，并使用 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;
  }
}