递归期间在 Scheme 中创建封闭过程的性能影响
Performance Impact of Creating Enclosed Procedure in Scheme During Recursion
我正在阅读 The Little Schemer 这本书，开始学习用 Lisp 思考。当您深入了解并真正涵盖 lambda 的使用时，'remove' 过程以以下一般形式编写，其中 return 是用于任意测试的删除过程 test?:
(define rember-f
(lambda (test?)
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l)
((rember-f test?) a (cdr l))))))))
我明白这是如何工作的，但简单的阅读表明，在每个递归步骤中，再次调用过程 rember-f 以生成 new 封闭程序。这意味着当您在列表中调用 returned 过程时，它会调用 rember-f 再次生成相同的过程 anew 然后 new 一个是所谓的递归（如果不清楚，请参阅下面的修复）。我知道这可能会被优化掉，但代替不知道它是否是（并且无论如何也试图让我的头脑绕过这个语法），我在一些实验之后设法将递归移动到过程本身而不是封闭程序如下：
(define rember-f
(lambda (test?)
(define retfun
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (retfun a (cdr l)))))))
retfun))
我已确认这按预期工作。 return 值是一个过程，用于删除与值 (arg 1) 匹配的列表 (arg 2) 的第一个元素。在我看来，这个只调用 rember-f 一次，这保证它只生成一个封闭过程（这次有一个名称，retfun）。
这对我来说实际上很有趣，因为与通常的尾调用优化不同，尾调用优化是关于不在调用堆栈上消耗 space，从而使递归与迭代一样高效，在这种情况下，编译器会确定 (rember-f test?) 是未修改的封闭过程范围，因此将其替换为相同的 return 值，即匿名 (lambda (a l) ...)。得知解释器/编译器 没有 捕捉到这一点，我一点也不感到惊讶。
是的，我知道 scheme 是一个规范，有很多实现，它们在不同程度上对各种函数式编程进行了优化。我目前正在通过在 guile REPL 中进行实验来学习，但会对不同的实现在这个问题上的比较感兴趣。
有谁知道 Scheme 应该 在这种情况下如何表现？
两个过程具有相同的渐近时间复杂度。让我们考虑 ((rember-f =) 1 '(5 4 3 2 1 0)).
的评估
部分评估过程如下：
((rember-f =) 1 '(5 4 3 2 1 0))
((lambda (a l)
(cond
((null? l) (quote ()))
((= (car l) a) (cdr l))
(else (cons (car l)
((rember-f =) a (cdr l)))))) 1 '(5 4 3 2 1 0))
(cons 5 ((rember-f = 1 '(4 3 2 1 0))))
请注意，临时 lambda 过程的创建需要 O(1) 时间和 space。所以它实际上并没有给调用函数的成本增加任何实质性的开销。充其量，分解函数将导致常数因子加速和使用常数更少的内存。
但是闭包到底需要多少内存？事实证明它只需要很少的内存。闭包由指向环境的指针和指向已编译代码的指针组成。基本上，创建闭包需要的时间和 space 与制作 cons 单元一样多。因此，即使在我显示评估时看起来我们正在使用大量内存，但实际用于制作和存储 lambda 的内存和时间却很少。
因此，从本质上讲，通过分解递归函数，您已经分配了一个 cons 单元格，而不是编写每次递归调用一次分配该 cons 单元格的代码。
有关这方面的更多信息，请参阅 Lambda is cheap, and Closures are Fast。
您担心额外的重复 lambda 抽象是正确的。例如你不会写这个，是吗？
(cond ((> (some-expensive-computation x) 0) ...)
((< (some-expensive-computation x) 0) ...)
(else ...))
相反，我们将 some-expensive-computation 的结果绑定到一个标识符，这样我们就可以检查同一个值的多个条件 -
(let ((result (some-expensive-computation x)))
(cond ((> result 0) ...)
((< result 0) ...)
(else ...)))
您发现了所谓的“命名 let”表达式的基本目的。这是你的程序 -
(define rember-f
(lambda (test?)
(define retfun
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (retfun a (cdr l)))))))
retfun))
及其等效的使用 named-let 表达式。下面我们将 let 主体绑定到 loop，这是一个允许主体递归的可调用过程。请注意 lambda 抽象如何只使用一次，并且内部 lambda 可以在没有 creating/evaluating 额外 lambda 的情况下重复 -
(define rember-f
(lambda (test?)
(lambda (a l)
(let loop ; name, "loop", or anything of your choice
((l l)) ; bindings, here we shadow l, or could rename it
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))))) ; apply "loop" with args
让我们运行吧-
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
named-let 的语法是 -
(let proc-identifier ((arg-identifier initial-expr) ...)
body ...)
Named-let 是 letrec 绑定的语法糖 -
(define rember-f
(lambda (test?)
(lambda (a l)
(letrec ((loop (lambda (l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))))
(loop l)))))
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
同样，您可以想象使用嵌套的 define -
(define rember-f
(lambda (test?)
(lambda (a l)
(define (loop l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))
(loop l))))
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
PS，你可以写'()代替(quote ())
开始学习用 Lisp 思考
那本书不是讲的lisp思维，而是递归思维，递归思维是在20 世纪，Goedel、Herbrand、Rozsa Peter。
有谁知道 Scheme 在这种情况下应该如何表现？
完成 little lisper 后，您应该参加 SICP，这将使您了解语言的实现可以做出什么样的决定。你的意思是，不同的实现是如何运作的。要了解他们的实施决策，最好的步骤是从 SICP 中学习。请注意，除非您已经是经过认证的计算机科学专业毕业生，否则如果您每天学习这本教科书，您将需要几年时间才能掌握它。如果你已经是一名毕业生，那么你只需要大约1年的时间就可以掌握。
我正在阅读 The Little Schemer 这本书，开始学习用 Lisp 思考。当您深入了解并真正涵盖 lambda 的使用时，'remove' 过程以以下一般形式编写，其中 return 是用于任意测试的删除过程 test?:
(define rember-f
(lambda (test?)
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l)
((rember-f test?) a (cdr l))))))))
我明白这是如何工作的，但简单的阅读表明，在每个递归步骤中，再次调用过程 rember-f 以生成 new 封闭程序。这意味着当您在列表中调用 returned 过程时，它会调用 rember-f 再次生成相同的过程 anew 然后 new 一个是所谓的递归（如果不清楚，请参阅下面的修复）。我知道这可能会被优化掉，但代替不知道它是否是（并且无论如何也试图让我的头脑绕过这个语法），我在一些实验之后设法将递归移动到过程本身而不是封闭程序如下：
(define rember-f
(lambda (test?)
(define retfun
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (retfun a (cdr l)))))))
retfun))
我已确认这按预期工作。 return 值是一个过程，用于删除与值 (arg 1) 匹配的列表 (arg 2) 的第一个元素。在我看来，这个只调用 rember-f 一次，这保证它只生成一个封闭过程（这次有一个名称，retfun）。
这对我来说实际上很有趣，因为与通常的尾调用优化不同，尾调用优化是关于不在调用堆栈上消耗 space，从而使递归与迭代一样高效，在这种情况下，编译器会确定 (rember-f test?) 是未修改的封闭过程范围，因此将其替换为相同的 return 值，即匿名 (lambda (a l) ...)。得知解释器/编译器 没有 捕捉到这一点，我一点也不感到惊讶。
是的，我知道 scheme 是一个规范，有很多实现，它们在不同程度上对各种函数式编程进行了优化。我目前正在通过在 guile REPL 中进行实验来学习，但会对不同的实现在这个问题上的比较感兴趣。
有谁知道 Scheme 应该 在这种情况下如何表现？
两个过程具有相同的渐近时间复杂度。让我们考虑 ((rember-f =) 1 '(5 4 3 2 1 0)).
部分评估过程如下：
((rember-f =) 1 '(5 4 3 2 1 0))
((lambda (a l)
(cond
((null? l) (quote ()))
((= (car l) a) (cdr l))
(else (cons (car l)
((rember-f =) a (cdr l)))))) 1 '(5 4 3 2 1 0))
(cons 5 ((rember-f = 1 '(4 3 2 1 0))))
请注意，临时 lambda 过程的创建需要 O(1) 时间和 space。所以它实际上并没有给调用函数的成本增加任何实质性的开销。充其量，分解函数将导致常数因子加速和使用常数更少的内存。
但是闭包到底需要多少内存？事实证明它只需要很少的内存。闭包由指向环境的指针和指向已编译代码的指针组成。基本上，创建闭包需要的时间和 space 与制作 cons 单元一样多。因此，即使在我显示评估时看起来我们正在使用大量内存，但实际用于制作和存储 lambda 的内存和时间却很少。
因此，从本质上讲，通过分解递归函数，您已经分配了一个 cons 单元格，而不是编写每次递归调用一次分配该 cons 单元格的代码。
有关这方面的更多信息，请参阅 Lambda is cheap, and Closures are Fast。
您担心额外的重复 lambda 抽象是正确的。例如你不会写这个，是吗？
(cond ((> (some-expensive-computation x) 0) ...)
((< (some-expensive-computation x) 0) ...)
(else ...))
相反，我们将 some-expensive-computation 的结果绑定到一个标识符，这样我们就可以检查同一个值的多个条件 -
(let ((result (some-expensive-computation x)))
(cond ((> result 0) ...)
((< result 0) ...)
(else ...)))
您发现了所谓的“命名 let”表达式的基本目的。这是你的程序 -
(define rember-f
(lambda (test?)
(define retfun
(lambda (a l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (retfun a (cdr l)))))))
retfun))
及其等效的使用 named-let 表达式。下面我们将 let 主体绑定到 loop，这是一个允许主体递归的可调用过程。请注意 lambda 抽象如何只使用一次，并且内部 lambda 可以在没有 creating/evaluating 额外 lambda 的情况下重复 -
(define rember-f
(lambda (test?)
(lambda (a l)
(let loop ; name, "loop", or anything of your choice
((l l)) ; bindings, here we shadow l, or could rename it
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))))) ; apply "loop" with args
让我们运行吧-
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
named-let 的语法是 -
(let proc-identifier ((arg-identifier initial-expr) ...)
body ...)
Named-let 是 letrec 绑定的语法糖 -
(define rember-f
(lambda (test?)
(lambda (a l)
(letrec ((loop (lambda (l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))))
(loop l)))))
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
同样，您可以想象使用嵌套的 define -
(define rember-f
(lambda (test?)
(lambda (a l)
(define (loop l)
(cond
((null? l) (quote ()))
((test? (car l) a) (cdr l))
(else (cons (car l) (loop (cdr l))))))
(loop l))))
((rember-f eq?) 'c '(a b c d e f))
'(a b d e f)
PS，你可以写'()代替(quote ())
开始学习用 Lisp 思考
那本书不是讲的lisp思维，而是递归思维，递归思维是在20 世纪，Goedel、Herbrand、Rozsa Peter。
有谁知道 Scheme 在这种情况下应该如何表现？
完成 little lisper 后，您应该参加 SICP，这将使您了解语言的实现可以做出什么样的决定。你的意思是，不同的实现是如何运作的。要了解他们的实施决策，最好的步骤是从 SICP 中学习。请注意，除非您已经是经过认证的计算机科学专业毕业生，否则如果您每天学习这本教科书，您将需要几年时间才能掌握它。如果你已经是一名毕业生，那么你只需要大约1年的时间就可以掌握。