Erlang 的递归函数不只是 goto 吗？

Question

只是为了把它直接记在我的脑海里。考虑一下 Erlang 代码的这个示例：

 test() ->
      receive
          {From, whatever} ->
                %% do something
               test();
          {From, somethingelse} ->
               %% do something else
               test();
 end.

test() 调用不是只是一个 goto 吗？

我问这个问题是因为在 C 语言中我们了解到，如果执行函数调用，返回位置总是放在堆栈上。我无法想象 Erlang 中一定是这种情况，因为这会导致堆栈溢出。

我们有两种不同的调用函数的方式： goto 和 gosub。 goto 只是将程序流程引导到其他地方，而 gosub 会记住您来自哪里，以便您可以返回。

有了这种思维方式，我可以更容易地了解 Erlang 的递归，因为如果我只是将： test() 作为 goto 读取，那么就完全没有问题了。

因此我的问题是： :Erlang 不是只是使用 goto 而不是记住堆栈上的返回地址吗？

编辑：

只是为了澄清我的观点：

我知道 goto 可以在某些语言中用于跳转。但假设你不做 someFunction() 也可以这样做： goto someFunction() 在第一个示例中，流程返回，在第二个示例中，流程仅在 someFunction 中继续，并且永远不会返回。

因此，我们通过跳转到方法起点来限制正常的 GOTO 行为。

如果你这样看，那么 Erlang 递归函数调用看起来就像一个 goto。

（我认为 goto 是一个函数调用，无法返回您来自的位置）。这正是 Erlang 示例中发生的情况。

Answer 1

由于所执行的内务处理，尾递归调用更像是“返回并立即调用另一个函数”而不是 goto。

解决您的最新问题：记录返回点只是调用函数时执行的一小部分内务处理。返回点存储在堆栈帧中，其余部分必须分配和初始化（在正常调用中），包括局部变量和参数。使用尾递归，不需要分配新的帧，也不需要存储返回点（之前的值可以正常工作），但需要执行其余的内务处理。

函数返回时还需要执行一些内务处理，其中包括丢弃局部变量和参数（作为堆栈帧的一部分）并返回到调用点。在尾递归调用期间，当前函数的局部变量在调用新函数之前被丢弃，但不会发生返回。

就像线程允许比进程更轻量级的上下文切换一样，尾调用允许更轻量级的函数调用，因为可以跳过一些内务处理。

Perl 中的“goto &NAME”语句更接近符合你的想法，但不完全是，因为它抛弃了当地人。为新调用的函数保留参数。

还有一个简单的区别：尾部调用只能跳转到函数入口点，而 goto 可以跳转到大多数地方（某些语言限制 goto 的目标，例如 C，其中 goto 不能跳转到函数之外）。

Answer 2

你是对的，Erlang编译器会检测到这是一个尾递归调用，并且它不会继续在堆栈上移动，而是重用当前函数的堆栈空间。

此外，它还能够检测循环尾递归，例如

test() -> ..., test2().
test2() -> ..., test3().
test3() -> ..., test().

也将被优化。

这样做的“不幸”副作用是，当您跟踪函数调用时，您将无法看到尾递归函数的每次调用，而是看到入口点和出口点。

Answer 3

这里你有两个问题。

首先，不，在这种情况下，您不会面临堆栈溢出的任何危险，因为对 test() 的这些调用都是 尾递归。

其次，不，函数调用不是 goto，它们是函数调用。 :) 让 goto 出现问题的是它绕过了代码中的任何结构。你可以跳出语句、跳入语句、绕过赋值……各种古怪的行为。函数调用不存在这个问题，因为它们有明显的控制流程。

Answer 4

我认为这里的区别在于“真正的”goto 和在某些情况下看起来像 goto 的东西之间的区别。在某些特殊情况下，编译器可以检测到在调用另一个函数之前可以自由地清理当前函数的堆栈。这是当该调用是函数中的最后一次调用时。当然，不同之处在于，与任何其他调用一样，您可以将参数传递给新函数。

正如其他人指出的那样，这种优化不仅限于递归调用，还限于所有最后的调用。这用于 FSM 编程的“经典”方式。

Answer 5

这是一个 goto，就像 if 是 goto 和 while 是 goto 一样。它是使用（道德上等同于）goto 来实现的，但它并没有直接向程序员暴露 goto 的全部潜力。

Answer 6

事实上，根据 Guy Steele 的说法，这些递归函数是终极 GOTO。

Answer 7

这是一个更通用的答案，它取代了我之前基于调用堆栈的答案。由于之前的答案已被接受，我不会替换文本。

序言

有些架构没有所谓的“函数”，但确实有类似的东西（消息传递可能称它们为“方法”或“消息处理程序”；基于事件的架构有“事件处理程序”或简称“处理程序”） ”）。对于一般情况，我将使用术语“代码块”和“调用”，尽管（严格来说）“代码块”可以包含不完全是函数的东西。您可以将“调用”的适当变形形式替换为“调用”或“调用”，就像我在某些地方所做的那样。描述调用的体系结构的特征有时称为“样式”，如“连续传递样式”(CPS)，尽管这以前不是官方术语。为了防止事情过于抽象，我们将检查调用堆栈、连续传递、消息传递（类似于 OOP）和事件处理调用样式。我应该指定这些样式所使用的模型，但为了节省空间，我将它们省略了。

调用功能

，或者，C 代表延续、协调和上下文，这对我来说已经足够了

Hohpe 标识了调用堆栈风格的三个很好的头韵调用特征：Continuation、Coordination、Context（全部大写以将它们与单词的其他用法区分开）。

• 继续决定代码块完成后将在哪里继续执行。 “Continuation”功能与“一流的 Continuation”（通常简称为“Continuation” ”，包括我），因为延续使延续功能在程序级别上可见且可操作。
• 协调意味着代码在需要的数据准备好之前不会执行。在单个调用堆栈中，您可以免费获得协调，因为程序计数器在被调用函数完成之前不会返回到函数。协调成为（例如）并发和事件驱动编程中的一个问题，前者是因为数据生产者可能落后于数据消费者，而后者是因为当处理程序触发事件时，处理程序立即继续而不等待响应。
• 上下文是指用于解析代码块中的名称的环境。它包括局部变量、参数和返回值的分配和初始化。 调用约定也涵盖了参数传递（保持头韵）；对于一般情况，您可以将 Context 拆分为一个包含局部变量的功能，一个包含参数，另一个包含返回值。对于 CPS，返回值由参数传递覆盖。

这三个特征不一定是独立的；调用风格决定了它们的相互关系。例如，在调用堆栈样式下，协调与延续相关联。 Continuation 和 Context 一般是相连的，因为 Continuation 中涉及到返回值。

Hohpe 的列表不一定详尽，但足以区分尾部调用和 goto。警告：我可能会偏离主题，例如根据 Hohpe 的功能探索调用空间，但我会尽力克制自己。

调用功能任务

每个调用功能都涉及调用代码块时要完成的任务。对于Continuation，被调用的代码块自然地通过调用代码链相关联。当调用代码块时，通过在链的末尾放置对调用代码的引用（“调用引用”）来扩展当前调用链（或“调用链”）（下面更具体地描述此过程） 。考虑到调用还涉及将名称绑定到代码块和参数，我们发现即使是非束缚和纪律的语言也可以有同样的乐趣。

尾部调用

或，答案

或，其余基本上是不必要的

尾部调用都是为了优化延续，它是一个识别何时可以跳过主要延续任务（记录调用引用）的问题。其他功能任务是独立的。 “goto”代表优化延续和上下文的任务。这就是为什么尾部调用不是简单的“goto”的原因。接下来将充实尾部调用在各种调用风格中的样子。

特定调用风格中的尾部调用

不同的风格以不同的结构排列调用链，由于缺乏更好的词，我将其称为“缠结”。我们已经摆脱了意大利面条式的代码，这不是很好吗？

• 对于调用堆栈，混乱中只有一个调用链；延长链条意味着推动程序计数器。尾部调用意味着没有程序计数器推送。
• 在 CPS 下，缠结由现有的延续组成，形成 反向 树状结构（有向树，每条边都指向中心节点），每条路径返回中心是一个调用链（注意：如果程序入口点传递了“null”延续，则缠结可以是反向树状结构的整个森林）。一个特定的链是默认的，这是在调用期间添加调用引用的位置。尾部调用不会将调用引用添加到默认调用链。请注意，这里的“调用链”基本上与“延续”同义，在“第一类延续”的意义上。
• 在消息传递下，调用链是一个阻塞方法链，每个方法都等待链中之前的方法的响应。调用另一个方法的方法是“客户端”；调用的方法是一个“供应商”（我故意不使用“服务”，尽管“供应商”也好不了多少）。消息传递缠结是一组未连接的调用链。这种缠结结构很像具有多个线程或进程堆栈。当该方法仅将另一个方法的响应作为其自己的响应进行回显时，该方法可以让其客户端等待其提供者而不是其本身。请注意，这提供了一种稍微更一般的优化，其中涉及优化协调和连续。如果方法的最后部分不依赖于响应（并且响应不依赖于最后部分中处理的数据），则一旦将其客户端的等待依赖项传递给其提供者，该方法就可以继续。这类似于启动一个新线程，其中方法的最后部分成为线程的主函数，然后是调用堆栈样式的尾调用。

事件处理风格怎么样？

对于事件处理，调用没有响应，处理程序也不会等待，因此“调用链”（如上面所使用的）不是一个有用的概念。您拥有事件的优先级队列（由通道拥有）和订阅（侦听器-处理程序对的列表），而不是混乱。在某些事件驱动架构中，通道是侦听器的属性；每个听众都拥有一个频道，因此频道就成为听众的代名词。调用意味着在通道上触发一个事件，该事件会调用所有订阅的侦听器处理程序；参数作为事件的属性传递。依赖于另一种样式的响应的代码将成为事件处理下的单独处理程序，并具有关联的事件。尾部调用是一个处理程序，它在另一个通道上触发事件，之后不执行任何其他操作。尾调用优化将涉及从第二个通道到第一个通道重新订阅事件侦听器，或者可能让在第一个通道上触发事件的处理程序而不是在第二个通道上触发（这是由程序员而不是编译器进行的优化） /口译员）。这是之前的优化的样子，从未优化的版本开始。

1. 侦听器 Alice 使用处理程序“party”订阅 BBC 新闻上的事件“就职”
2. Alice 在 BBC 新闻频道上触发事件“选举”
3. Bob 正在侦听 BBC 新闻上的“选举”，因此调用 Bob 的“openPolls”处理程序
4. Bob 订阅事件CNN 频道的“就职典礼”。
5. Bob 在 CNN 频道上触发事件“投票”
6. 其他事件被触发并被删除。处理。最终，其中之一（例如“胜利”）在 CNN 上触发了“就职典礼”活动。
7. Bob 被禁止的处理程序在 BBC 新闻上触发“就职”，
8. Alice 的就职处理程序被调用。

优化版本：

1. 监听器 Alice 订阅 BBC 新闻上的事件“就职”
2. Alice 在 BBC 新闻频道上触发事件“选举”
3. Bob 正在监听 BBC 新闻上的“选举”，因此调用 Bob 的“openPolls”处理程序
4. Bob 订阅任何监听的人BBC 新闻中的“就职典礼”改为 CNN* 的就职典礼。
5. 鲍勃在 CNN 频道上触发了“投票”事件
6. 其他事件被触发并被取消处理。最终，其中一位在 CNN 上发布了活动“就职典礼”。
7. Alice 的就职处理程序被调用用于 CNN 的就职事件。

请注意，尾部调用在事件处理下更加棘手（站不住脚？），因为它们必须考虑订阅。如果爱丽丝后来取消订阅 BBC 新闻的“就职典礼”，则也需要取消订阅 CNN 的就职典礼。此外，系统必须确保它不会不恰当地多次为侦听器调用处理程序。在上面的优化示例中，如果 CNN 上的另一个“就职典礼”处理程序在 BBC 新闻上触发“就职典礼”怎么办？ Alice 的“聚会”活动将被解雇两次，这可能会给她带来工作上的麻烦。一种解决方案是让 *Bob 在步骤 4 中取消订阅 BBC 新闻中的所有听众“就职典礼”，但随后您会引入另一个错误，其中 Alice 将错过不通过 CNN 提供的就职典礼活动。也许她想同时庆祝美国和英国的就职典礼。出现这些问题是因为我在模型中没有做出区分，可能是基于订阅类型。例如，也许有一种特殊的一次性订阅（例如 System-V 信号处理程序）或某些处理程序自行取消订阅，尾调用优化仅适用于这些情况。

接下来怎么办？

您可以继续更全面地指定调用功能任务。从那里，您可以找出可以进行哪些优化以及何时可以使用它们。也许可以识别其他调用特征。您还可以想到更多调用样式的示例。您还可以探索调用功能之间的依赖关系。例如，同步和异步调用涉及显式耦合或解耦延续和协调。它永远不会结束。

明白这一切了吗？我自己还在努力消化。

参考文献：

1. Hohpe，Gregor； “事件驱动架构”
2. Sugalski，Dan； “CPS 和尾调用——两种美妙的味道结合在一起”

Answer 8

在这种情况下，可以进行尾部调用优化，因为我们不需要做更多的工作或使用局部变量。所以编译器会将其转换为循环。

Answer 9

<块引用>

（我认为 goto 是一个函数调用，无法返回您来自的位置）。这正是 erlang 示例中发生的情况。

这不是 Erlang 中发生的事情，你可以返回到你原来的地方。

这些调用是尾递归的，这意味着它“有点”是 goto。在尝试理解或编写任何代码之前，请确保您了解尾递归是什么。如果您是 Erlang 新手，那么阅读 Joe Armstrong 的书可能不是一个坏主意。

从概念上讲，如果您使用 test() 调用自己，则使用您传递的任何参数（本例中没有）调用函数的开头，但不会将任何内容添加到堆栈中。因此，所有变量都被丢弃，函数重新开始，但您没有将新的返回指针推入堆栈。因此，它就像 goto 和传统命令式语言风格函数调用（如 C 或 Java 中的函数调用）之间的混合体。但是从调用函数的第一次调用开始，堆栈上仍然有一个条目。因此，当您最终通过返回一个值而不是执行另一个 test() 退出时，该返回位置将从堆栈中弹出，并在调用函数中恢复执行。