recursion - The Little Schemer Evens-only*&co

Question

我很难理解 The Little Schemer 的 evens-only*&co 发生了什么事情第 145 页的示例。

这是代码:

(define evens-only*&co
 (lambda (l col)
   (cond
    ((null? l)
     (col '() 1 0))
    ((atom? (car l))
     (cond
      ((even? (car l))
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col (cons (car l) newl)
                           (opx (car l) product)
                           sum))))
      (else
       (evens-only*&co (cdr l)
                    (lambda (newl product sum)
                      (col newl product (op+ (car l) sum)))))))
    (else
     (evens-only*&co (car l)
                  (lambda (newl product sum)
                    (evens-only*&co (cdr l)
                                    (lambda (dnewl dproduct dsum)
                                      (col (cons newl dnewl)
                                           (opx product dproduct)
                                           (op+ sum dsum))))))))))

初始 col可:

(define evens-results
 (lambda (newl product sum)
   (cons sum (cons product newl))))

我没有得到的是， l如 '((1) 2 3) ，它立即进入最终 else与 (car l)如 (1)和 (cdr l)如 (2 3) .很好，但我的大脑一片空白，试图理清 dnewl , dproduct , dsum来自 newl , product , sum .如果有人可以指导我如何设置 DrRacket 或 Chez Scheme 或 MIT-Scheme 来运行步进器，那也会很有帮助。

但也许我太早了。第一次阅读这篇文章的初学者是否真的应该理解这种疯狂的延续？

Answer 1

我发现这部分在第一次阅读时也很困惑，直到我在其他地方阅读了关于延续和延续传递风格(这就是什么)之后才开始理解它。

冒着解释你已经得到的东西的风险，一种对我有帮助的看待它的方式是将“收集器”或“延续”视为替代函数返回值的正常方式。在正常的编程风格中，你调用一个函数，接收一个值，然后在调用者中用它做一些事情。例如，标准递归 length函数包含表达式 (+ 1 (length (cdr list)))对于非空情况。这意味着一旦 (length (cdr list))返回一个值，无论它产生什么值，都会有一个计算等待发生，我们可以将其视为 (+ 1 [returned value]) .在正常的编程中，解释器会跟踪这些待处理的计算，这些计算往往会“叠加”，正如您在本书的前几章中看到的那样。例如，在递归计算列表的长度时，我们有一个“等待计算”的嵌套，与列表的长度一样深。

在延续传递风格中，我们不是调用函数并在调用函数中使用返回的结果，而是通过向函数提供要调用的“延续”来告诉函数在产生其值时要做什么。 (这类似于您在异步 Javascript 编程中对回调所做的处理，例如:不是编写 result = someFunction();，而是编写 someFunction(function (result) { ... }) ，并且所有使用 result 的代码都在回调函数中)。

这是length以连续传递风格，仅供比较。我已经调用了延续参数 return ，这应该表明它在这里是如何工作的，但请记住，它只是一个普通的 Scheme 变量，就像其他任何变量一样。 (在这种风格中，延续参数通常称为 k)。

(define (length/k lis return)
  (cond ((null? lis) (return 0))
        (else
         (length/k (cdr lis)
                   (lambda (cdr-len)
                     (return (+ cdr-len 1)))))))

在 an article on continuations by Little Schemer co-author Dan Friedman 中有阅读此类代码的有用提示。 . (参见第 8 页开始的第 II-5 节)。解释一下，这就是 else上面的条款说:

imagine you have the result of calling length/k on (cdr lis), and call it cdr-len, then add one and pass the result of this addition to your continuation (return).

请注意，这几乎正是解释器在评估 (+ 1 (length (cdr lis))) 时必须做的事情。在函数的正常版本中(除了它不必为中间结果命名 (length (cdr lis)) 。通过传递延续或回调，我们使控制流(和中间值的名称)显式，而不是让解释器跟踪它。

让我们将此方法应用于 evens-only*&co 中的每个子句.由于此函数生成三个值而不是一个值，因此这里稍微有点复杂:删除了奇数的嵌套列表；偶数的乘积；和奇数之和。这是第一个子句，其中 (car l)已知为偶数:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col (cons (car l) newl)
                       (opx (car l) product)
                       sum)))

Imagine that you have the results of removing odd numbers, multiplying evens, and adding odd numbers from the cdr of the list, and call them newl, product, and sum respectively. cons the head of the list onto newl (since it's an even number, it should go in the result); multiply product by the head of the list (since we're calculating product of evens); leave sum alone; and pass these three values to your waiting continuation col.

下面是列表头部为奇数的情况:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col newl product (op+ (car l) sum))))

和以前一样，但传递相同的值 newl和 product到延续(即“返回”它们)，以及 sum 的总和和列表的头部，因为我们正在总结奇数。

这是最后一个，其中 (car l)是一个嵌套列表，并且由于双递归而稍微复杂:

(evens-only*&co (car l)
                (lambda (newl product sum)
                  (evens-only*&co (cdr l)
                                  (lambda (dnewl dproduct dsum)
                                    (col (cons newl dnewl)
                                         (opx product dproduct)
                                         (op+ sum dsum))))))

Imagine you have the results from removing, summing and adding the numbers in (car l) and call these newl, product, and sum; then imagine you have the results from doing the same thing to (cdr l), and call them dnewl, dproduct and dsum. To your waiting continuation, give the values produced by consing newl and dnewl (since we're producing a list of lists); multiplying together product and dproduct; and adding sum and dsum.

注意:每次我们进行递归调用时，我们都会为递归调用构造一个新的延续，它“关闭”参数的当前值， l ，以及返回继续 - col ，换句话说，您可以将我们在递归过程中建立的延续链视为对更常规编写的函数的“调用堆栈”进行建模!

希望能部分回答您的问题。如果我有点过火，那只是因为我认为，在递归本身之后，延续是 The Little Schemer 和一般编程中的第二个真正整洁、扩展思想的想法。