一个函数如何调用自身是可能的

作者: 荧惑
发布时间: 2024-04-19 12:50:53 (15天前)
转自：

5 条回复

0#
回复此人
拥有小太阳的向日葵 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <BLOCKQUOTE> 据我所知，计算机必须先完成功能分析才能定义。 </BLOCKQUOTE> 当编译器看到一个定义函数POW时，它会告诉自己：现在我们定义了函数POW。如果它然后在定义内部看到对POW的调用，那么编译器会对自己说：哦，这似乎是对我正在编译的函数的调用，然后它可以创建代码来进行递归调用。 </DIV>

编辑
1#
回复此人
CTO啊哦 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 我想看看这是如何工作的 一般来说 ，特别是在递归调用的情况下 不能 变成循环，值得思考一般编译语言如何工作，因为问题没有区别。 让我们假设编译器如何将此函数转换为机器代码： <pre> <code> (defun foo (x) (+ x (bar x))) </code> </pre> 我们假设它不知道任何事情 <code> bar </code> 在编译时。嗯，它有两个选择。 <OL> <LI> 它可以编译 <code> foo </code> 以这种方式打电话给 <code> bar </code> 翻译了一组说明，'查找名称下存储的函数定义 <code> bar </code> ，无论目前是什么，并安排用正确的参数调用该函数。 </LI> <LI> 它可以编译 <code> foo </code> 以某种方式对函数进行机器级函数调用，但该函数的地址保留为某种占位符。然后它可以附加一些元数据 <code> foo </code> 其中说：'在调用此函数之前，您需要找到名为的函数 <code> bar </code> ，找到它的地址，将它拼接到正确位置的代码中， 并删除此元数据 。 </LI> </醇> 这两种机制都允许 <code> foo </code> 在它知道什么之前定义 <code> bar </code> 是。请注意，而不是 <code> bar </code> 我本来可以写的 <code> foo </code> ：这些机制也处理递归调用。然而，他们与此不同。 <UL> <LI> 第一种机制每次都意味着 <code> foo </code> 被称为需要进行某种动态查找 <code> bar </code> 这将涉及一些开销（但这个开销可能非常小）： <UL> <LI> 因此，第一种机制将比它可能稍微慢一些; </LI> <LI> 但是，也是如此，如果 <code> bar </code> 重新定义，然后新的定义将被拾取，这是一个非常理想的交互式语言，Lisp实现通常是。 </LI> </UL> </LI> <LI> 第二种机制意味着，之后 <code> foo </code> 将其所有引用链接到其中的其他函数，然后调用发生在机器级别： <UL> <LI> 这意味着他们会很快; </LI> <LI> 但这种重新定义充其量只会更复杂，或者在最坏的情况下根本不可能。 </LI> </UL> </LI> </UL> 这些实现中的第二个与传统编译器编译代码的方式很接近：它们编译代码，留下一堆占位符和相关元数据，说明这些占位符对应的名称。一个 链接 （有时称为链接加载程序或加载程序）然后对编译器生成的所有文件以及其他代码库进行嵌套，并解析所有这些引用，从而生成一些实际可以运行的代码。 一个非常简单的Lisp系统可能完全由第一个机制工作（我很确定这就是Python的工作原理）。更高级的编译器可能会通过第一和第二机制的某种组合来工作。作为一个例子，CL允许编译器做出假设，即功能中的明显自我调用 是 自调用，因此编译器可以将它们编译为直接调用（实质上它将编译函数然后动态链接它）。但是在编译代码时，它可能会调用函数的“名称”。 事情可以做或多或少的英雄策略：例如，在第一次调用函数时，它会动态地链接到它引用的所有事物，并在 其 定义如果它们发生了变化，那么这个东西也需要取消链接，所以这一切都会再次发生。这些技巧曾经似乎难以置信，但像JavaScript这样的语言的编译器至少像现在这样一样毛茸茸。 <HR /> 请注意，现代系统的编译器和链接器实际上做了比我描述的更复杂的事情，因为共享库＆amp; c：我所描述的或多或少是共享库之前发生的事情。 </DIV>

编辑
2#
回复此人
Innate Mind | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 函数只是一个代码块。它的名字只是帮助，所以你不必计算它最终会得到的确切地址。编程语言会将名称转换为程序执行的位置。 一个函数如何调用另一个函数是通过在堆栈中存储此函数中的下一个命令的地址，可能是向堆栈添加参数然后跳转到函数的地址位置。函数本身跳转到它找到的返回地址，以便控制返回被调用者。语言实现了几种调用约定，哪一方做什么。 CPU实际上没有功能支持，所以就像模拟CPU功能中没有任何称为while循环的东西一样。 就像函数有名称一样，参数也有名称，但它们只是像返回地址一样的指针。在调用自身时，它只是将新的返回地址和参数添加到堆栈中并跳转到自身。堆栈的顶部将是不同的，因此相同的变量名称是调用的唯一地址 <code> x </code> 和 <code> y </code> 在之前的呼叫中，除了当前之外的其他地方 <code> x </code> 和 <code> y </code> 。事实上，调用自己并不需要特殊的处理，而不是调用任何其他东西。 历史上第一个高级语言Fortran不支持递归。它会调用自己，但是当它返回时它返回到原来的被调用者而不执行自调用后的其余功能。 Fortran本身在没有递归的情况下是不可能编写的，因此当它本身使用递归时它并没有将它提供给使用它的程序员。这种限制是John McCarthy发现Lisp的原因。 </DIV>

编辑
3#
回复此人
Charizard | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 编译器比你想象的要聪明得多。编译器可以在此定义中转换递归调用： <pre> <code> (defun pow (x y) (cond ((zerop y) 1) (t (* x (pow x (1- y)))))) </code> </pre> 进入 <code> goto </code> 从头开始重新启动功能的意图： <pre> <code> Disassembly of function POW (CONST 0) = 1 2 required arguments 0 optional arguments No rest parameter No keyword parameters 12 byte-code instructions: 0 L0 0 (LOAD&PUSH 1) 1 (CALLS2&JMPIF 172 L15) ; ZEROP 4 (LOAD&PUSH 2) 5 (LOAD&PUSH 3) 6 (LOAD&DEC&PUSH 3) 8 (JSR&PUSH L0) 10 (CALLSR 2 57) ; * 13 (SKIP&RET 3) 15 L15 15 (CONST 0) ; 1 16 (SKIP&RET 3) </code> </pre> 如果这是一个更复杂的递归函数，编译器无法展开到循环中，它只会再次调用该函数。 </DIV>

编辑

登录后才能参与评论