从let绑定内部递归-方案



我知道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-functionccprevious被移除之前被求值,并开始应用。

要求以这种方式处理过程和变量。这叫做尾部呼叫优化。

创建过程时,在过程中使用的变量需要在过程存在期间存在:

(define (some-function2)
  (let ((c (read-char)))
    (lambda () c)))
(define test (some-function2))
(define test2 (some-function2))

。当some-function2调用完成时,变量被移动为连接到过程的东西,但仍然不是环境的一部分。这些过程被称为闭包,每个过程中的c都是闭包变量,即使在绑定过程完成后也会继续存在。如果你习惯其他语言,你可以把这些变量放在堆上。这些"自由变量"使Scheme在70年代被创造出来时变得特别,此后的每一种编程语言或多或少都基于这一原则。

最新更新