我知道递归,但我不知道它是如何可能的。我将使用这个例子来进一步解释我的问题。
(def(pow(x,y)) (cond((y = 0)1)) (x *(pow(x,y-1))))…
据我所知,计算机必须先完成功能分析才能定义。
当编译器看到一个定义函数POW时,它会告诉自己:现在我们定义了函数POW。如果它然后在定义内部看到对POW的调用,那么编译器会对自己说:哦,这似乎是对我正在编译的函数的调用,然后它可以创建代码来进行递归调用。
我想看看这是如何工作的 一般来说 ,特别是在递归调用的情况下 不能 变成循环,值得思考一般编译语言如何工作,因为问题没有区别。
让我们假设编译器如何将此函数转换为机器代码:
(defun foo (x) (+ x (bar x)))
我们假设它不知道任何事情 bar 在编译时。嗯,它有两个选择。
bar
foo
这两种机制都允许 foo 在它知道什么之前定义 bar 是。请注意,而不是 bar 我本来可以写的 foo :这些机制也处理递归调用。然而,他们与此不同。
这些实现中的第二个与传统编译器编译代码的方式很接近:它们编译代码,留下一堆占位符和相关元数据,说明这些占位符对应的名称。一个 链接 (有时称为链接加载程序或加载程序)然后对编译器生成的所有文件以及其他代码库进行嵌套,并解析所有这些引用,从而生成一些实际可以运行的代码。
一个非常简单的Lisp系统可能完全由第一个机制工作(我很确定这就是Python的工作原理)。更高级的编译器可能会通过第一和第二机制的某种组合来工作。作为一个例子,CL允许编译器做出假设,即功能中的明显自我调用 是 自调用,因此编译器可以将它们编译为直接调用(实质上它将编译函数然后动态链接它)。但是在编译代码时,它可能会调用函数的“名称”。
事情可以做或多或少的英雄策略:例如,在第一次调用函数时,它会动态地链接到它引用的所有事物,并在 其 定义如果它们发生了变化,那么这个东西也需要取消链接,所以这一切都会再次发生。这些技巧曾经似乎难以置信,但像JavaScript这样的语言的编译器至少像现在这样一样毛茸茸。
请注意,现代系统的编译器和链接器实际上做了比我描述的更复杂的事情,因为共享库& c:我所描述的或多或少是共享库之前发生的事情。
函数只是一个代码块。它的名字只是帮助,所以你不必计算它最终会得到的确切地址。编程语言会将名称转换为程序执行的位置。
一个函数如何调用另一个函数是通过在堆栈中存储此函数中的下一个命令的地址,可能是向堆栈添加参数然后跳转到函数的地址位置。函数本身跳转到它找到的返回地址,以便控制返回被调用者。语言实现了几种调用约定,哪一方做什么。 CPU实际上没有功能支持,所以就像模拟CPU功能中没有任何称为while循环的东西一样。
就像函数有名称一样,参数也有名称,但它们只是像返回地址一样的指针。在调用自身时,它只是将新的返回地址和参数添加到堆栈中并跳转到自身。堆栈的顶部将是不同的,因此相同的变量名称是调用的唯一地址 x 和 y 在之前的呼叫中,除了当前之外的其他地方 x 和 y 。事实上,调用自己并不需要特殊的处理,而不是调用任何其他东西。
x
y
历史上第一个高级语言Fortran不支持递归。它会调用自己,但是当它返回时它返回到原来的被调用者而不执行自调用后的其余功能。 Fortran本身在没有递归的情况下是不可能编写的,因此当它本身使用递归时它并没有将它提供给使用它的程序员。这种限制是John McCarthy发现Lisp的原因。
编译器比你想象的要聪明得多。 编译器可以在此定义中转换递归调用:
(defun pow (x y) (cond ((zerop y) 1) (t (* x (pow x (1- y))))))
进入 goto 从头开始重新启动功能的意图:
goto
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)
如果这是一个更复杂的递归函数,编译器无法展开到循环中,它只会再次调用该函数。