10

只是为了让我直截了当。考虑一下这个 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 示例中正在发生的事情。

4

9 回答 9

14

由于执行了内务处理,尾递归调用更像是“返回并立即调用其他函数”而不是 goto。

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

当函数返回时,还需要执行内务处理,包括丢弃局部变量和参数(作为堆栈帧的一部分)并返回调用点。在尾递归调用期间,当前函数的局部变量在调用新函数之前被丢弃,但没有返回发生。

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

Perl 中的 " goto &NAME" 语句更接近您的想法,但不完全是,因为它丢弃了本地变量。为新调用的函数保留参数。

还有一个简单的区别:尾调用只能跳转到函数入口点,而 goto 几乎可以跳转到任何地方(某些语言限制 goto 的目标,例如 C,其中 goto 不能跳转到函数之外)。

于 2009-09-27T13:30:51.443 回答
8

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

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

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

也会被优化。

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

于 2009-09-27T11:58:51.507 回答
4

你这里有两个问题。

首先,不,在这种情况下,您没有任何溢出堆栈的危险,因为这些对 test() 的调用都是tail-recursive

其次,不,函数调用不是 goto,它们是函数调用。:) 使 goto 出现问题的原因是它绕过了代码中的任何结构。你可以跳出语句,跳入语句,绕过赋值......各种诡异。函数调用没有这个问题,因为它们有明显的控制流。

于 2009-09-27T11:45:25.103 回答
3

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

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

于 2009-09-27T16:38:53.817 回答
3

goto与为什么ifgotowhile是相同的goto。它是使用 (道德等价的) 来实现的,但它并没有直接向程序员goto展示完全自足的潜力。goto

于 2009-09-27T17:02:53.230 回答
2

事实上,这些递归函数是Guy Steele的终极 GOTO 。

于 2009-09-27T12:25:18.370 回答
2

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

序幕

一些架构没有他们称之为“函数”的东西被“调用”,但确实有一些类似的东西(消息可能称它们为“方法”或“消息处理程序”;基于事件的架构有“事件处理程序”或简称为“处理程序” )。对于一般情况,我将使用术语“代码块”和“调用”,尽管(严格来说)“代码块”可以包括不完全功能的东西。您可以用“调用”或“调用”的适当变形形式来代替“调用”或“调用”,就像我在几个地方可能的那样。描述调用的体系结构的特征有时称为“样式”,如“延续传递样式”(CPS),尽管这以前不是官方术语。为了避免过于抽象,我们将检查调用堆栈、继续传递、消息传递(à la OOP)和事件处理调用样式。我应该为这些样式指定我使用的模型,但为了空间,我将它们排除在外。

调用功能

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

Hohpe确定了调用堆栈样式的三个很好的头韵调用特征:Continuation、Coordination、Context(全部大写以将它们与单词的其他用法区分开来)。

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

这三个特征不一定是独立的。调用方式决定了它们的相互关系。例如,Coordination 在调用堆栈样式下与 Continuation 相关联。Continuation 和 Context 通常是相连的,因为 Continuation 中涉及返回值。

Hohpe 的列表不一定详尽,但足以区分尾调用和 goto。警告:我可能会偏离正题,例如根据 Hohpe 的特性探索调用空间,但我会尽量控制自己。

调用功能任务

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

尾调用

或者,答案

或者,其余的基本上是不必要的

尾调用完全是关于优化 Continuation,它是识别何时可以跳过主要 Continuation 任务(记录调用引用)的问题。其他功能任务独立存在。“goto”代表优化了Continuation和Context的任务。这就是为什么尾调用不是简单的“goto”的原因。接下来的内容将充实尾部调用在各种调用样式中的样子。

特定调用样式的尾调用

不同的风格将调用链安排在不同的结构中,我称之为“tangle”,因为没有更好的词。我们摆脱了意大利面条式代码不是很好吗?

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

事件处理风格怎么样?

对于事件处理,调用没有响应,处理程序也不会等待,因此“调用链”(如上所用)不是一个有用的概念。您有事件的优先级队列(由通道拥有)和订阅(即侦听器-处理程序对的列表),而不是缠结。在某些事件驱动架构中,通道是侦听器的属性;每个听众都拥有一个频道,因此频道成为听众的同义词。调用意味着在通道上触发一个事件,该事件调用所有订阅的侦听器处理程序;参数作为事件的属性传递。依赖于另一种样式的响应的代码将成为事件处理下的单独处理程序,并带有关联的事件。尾调用将是一个处理程序,它在另一个通道上触发事件,之后什么也不做。尾调用优化将涉及将事件的侦听器从第二个通道重新订阅到第一个通道,或者可能让在第一个通道上触发事件的处理程序而不是在第二个通道上触发(由程序员而不是编译器进行的优化/翻译)。这是以前的优化的样子,从未优化的版本开始。

  1. 听众 Alice 使用处理程序“party”订阅 BBC 新闻上的事件“就职典礼”
  2. 爱丽丝在 BBC 新闻频道上举办“选举”活动
  3. Bob 正在收听 BBC 新闻上的“选举”,因此调用了 Bob 的“openPolls”处理程序
  4. Bob 订阅了 CNN 频道上的“就职典礼”事件。
  5. Bob 在 CNN 频道上发起“投票”活动
  6. 其他事件被触发和处理。最终,其中之一(例如“获胜”)在 CNN 上触发了“就职典礼”事件。
  7. 鲍勃的禁止处理程序在 BBC 新闻上触发“就职典礼”
  8. Alice 的就职典礼处理程序被调用。

和优化版本:

  1. 听众爱丽丝订阅了 BBC 新闻上的“就职典礼”活动
  2. 爱丽丝在 BBC 新闻频道上举办“选举”活动
  3. Bob 正在收听 BBC 新闻上的“选举”,因此调用了 Bob 的“openPolls”处理程序
  4. Bob 订阅任何在 BBC 新闻上收听“就职典礼”的人订阅 CNN* 上的就职典礼。
  5. Bob 在 CNN 频道上发起“投票”活动
  6. 其他事件被触发和处理。最终,其中一个在 CNN 上引发了“就职典礼”事件。
  7. 为 CNN 上的就职典礼调用 Alice 的就职典礼处理程序。

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

下一步是什么?

您可以继续更全面地指定调用功能任务。从那里,您可以弄清楚哪些优化是可能的,以及何时可以使用它们。也许可以识别其他调用特征。您还可以考虑更多调用样式的示例。您还可以探索调用功能之间的依赖关系。例如,同步和异步调用涉及显式耦合或解耦继续和协调。永无止境。

得到这一切?我还在努力自己消化。

参考:

  1. 霍普,格雷戈尔;《事件驱动架构
  2. 苏加尔斯基,丹;“ CPS 和尾声——两种美妙的味道结合在一起
于 2009-09-30T04:14:20.680 回答
1

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

于 2009-09-27T11:45:01.677 回答
0

(我认为 goto 是一个函数调用,无法返回您来自的地方)。这正是 erlang 示例中正在发生的事情。

这不是 Erlang 中正在发生的事情,你可以回到你来自的地方。

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

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

于 2009-09-28T18:02:04.737 回答