2

我正在阅读The Little Schemer这本书，开始学习用 Lisp 进行思考。当你进入它并真正涵盖了 lambdas 的使用时，'remove' 过程以以下一般形式编写，它返回一个用于任意 test 的删除过程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再次调用该过程以生成一个新的封闭过程。这意味着当您在列表上调用返回的过程时，它会再次调用以重新rember-f生成相同的过程，然后该新的过程称为递归（如果不清楚，请参阅下面的修复）。我知道这可能会被优化掉，但是代替不知道它是否是（并且无论如何也试图让我了解这种语法），我在一些实验后设法将递归移动到过程本身而不是封闭程序如下：

(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))

我已经验证这可以按预期工作。返回值是一个删除与值 (arg 1) 匹配的列表 (arg 2) 的第一个元素的过程。在我看来，这个只调用rember-f一次，这保证它只生成一个封闭的过程（这次有一个名字，retfun）。

这对我来说实际上很有趣，因为与通常的尾调用优化不同，它不消耗调用堆栈上的空间，因此使递归与迭代一样有效，在这种情况下，编译器必须确定(rember-f test?)封闭过程范围未修改因此将其替换为相同的返回值，即匿名(lambda (a l) ...)。得知解释器/编译器没有捕捉到这一点，我一点也不感到惊讶。

是的，我知道方案是一种规范，并且有许多实现，它们在不同程度上获得了各种函数式编程优化。我目前正在通过在 guile REPL 中进行实验来学习，但会对不同的实现在这个问题上的比较感兴趣。

有谁知道 Scheme在这种情况下应该如何表现？

4

3 回答 3

1

这两个过程具有相同的渐近时间复杂度。让我们考虑对 的评估((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)时间和空间。所以它实际上并没有给调用函数的成本增加任何实质性的开销。充其量，分解函数将导致恒定因子加速并使用恒定数量的更少内存。

但是关闭真正需要多少内存呢？事实证明它只需要很少的内存。闭包由指向环境的指针和指向已编译代码的指针组成。基本上，创建闭包需要与制作单元一样多的时间和空间cons。因此，尽管在我展示评估时看起来我们使用了大量内存，但实际上用于创建和存储 lambda 的内存和时间非常少。

因此，本质上，通过分解递归函数，您分配了一个单元格，而不是编写代码，每次递归调用一次cons分配该单元格。cons

有关这方面的更多信息，请参阅Lambda 很便宜，并且 Closures are Fast。

于 2021-07-07T14:46:46.933 回答
1

您担心额外的重复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 而无需创建/评估额外的 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 ())

于 2021-07-07T16:34:07.513 回答
1

开始学习用 Lisp 思考

那本书不是关于 lisp 的思考，而是关于递归思考，这是 Goedel、Herbrand、Rozsa Peter 在 20 世纪发现的计算方式之一。

有谁知道 Scheme 在这种情况下应该如何表现？

完成小 lisper 后，您应该参加 SICP，这将使您了解语言的实现可以做出什么样的决定。你的意思是，不同的实现是如何起作用的。要了解他们的实施决策，最好的步骤是从 SICP 中学习。请注意，除非您已经是经过认证的计算机科学专业毕业生，否则如果您每天都学习这本教科书，您将需要几年时间才能掌握。如果你已经是一名毕业生，你只需要大约 1 年的时间就可以掌握。

于 2021-07-08T04:18:02.090 回答