我知道Scheme是尾部递归的,但是如果一个函数从let绑定中调用自己,那么绑定值即使不需要也会留在内存中吗?我有类似这样的代码:
(define (some-function)
(let ((c (read-char)))
(some-function)))
实际的函数有点复杂,但这应该无关紧要,因为流程等是相同的。"c"的值是否会被保留,因为函数是从let块内部调用的?如果这个函数持续运行一段时间,我不想占用大量的额外内存。
如果一个函数是尾部递归的,也就是说,如果递归函数调用是作为函数的一部分计算的最后一个东西,这是你的代码中的情况,递归不会在内存中保留任何局部变量,因此堆栈空间消耗保持不变。
如果它不是尾部递归的,也就是说,如果递归后仍然有一些事情要做,那么c
必须保存在内存中,使函数消耗O(n)
堆栈空间,其中n
是递归的数量。例如:
(define (some-function)
(let ((c (read-char)))
(+ c (some-function))))
这里的加法将在递归之后执行,所以c
必须在递归调用执行时保存在内存中。
考虑您的示例:
(define (some-function)
(let ((c (read-char)))
; <HERE>
(some-function)))
(some-function)
假设我们运行这个程序。程序将反复循环调用some-function
。在某个时刻,垃圾收集器被激活。为了便于讨论,假设进程(正在运行的程序)在标记为<here>
的点被中断。
垃圾收集器的工作是回收不再使用的内存。"使用中"是什么意思?
如果一块内存(或占用内存的值)在程序继续时可能被使用,则该内存正在使用中。名称c
绑定了一个字符,因此该字符不能被回收。但是,由于对some-function
的调用是尾递归的,因此每次只有一个some-function
调用是活动的。这意味着c
的所有旧值都可以回收。
对于一个命名循环,其中循环函数是尾部调用的,只有最近的值在使用。(这些值一直保留在内存中,直到垃圾收集器被激活)。
一个小实验,试试:
(let loop ((v 0))
(loop (make-vector 100000 42))
这个程序循环往复。每轮分配一个长度为100000的向量。如果内存耗尽,您知道v
的值不会被垃圾收集。如果程序不间断地运行,那么垃圾收集器已经使回收内存成为可能。
在尾部位置,绑定变量不需要存在。只有在创建过程时可用的变量在调用时可用。
(define (some-function)
;; only global variables exist at this point
(let ((c (read-char)))
;; c exists for a brief time
(some-function)))
在过程中对变量some-function
求值后,在应用some-function
求值之前删除c
。一次只能存在一个c
'
想象一下这个稍微改变的版本:
(define (some-function previous)
(let ((c (read-char)))
(some-function c)))
这里我们有相同的,除了some-function
和c
在c
和previous
被移除之前被求值,并开始应用。
要求以这种方式处理过程和变量。这叫做尾部呼叫优化。
创建过程时,在过程中使用的变量需要在过程存在期间存在:
(define (some-function2)
(let ((c (read-char)))
(lambda () c)))
(define test (some-function2))
(define test2 (some-function2))
。当some-function2
调用完成时,变量被移动为连接到过程的东西,但仍然不是环境的一部分。这些过程被称为闭包,每个过程中的c
都是闭包变量,即使在绑定过程完成后也会继续存在。如果你习惯其他语言,你可以把这些变量放在堆上。这些"自由变量"使Scheme在70年代被创造出来时变得特别,此后的每一种编程语言或多或少都基于这一原则。