Little Schemer仅限天数*& co [英] The Little Schemer evens-only*&co

问题描述

我很难理解第145页上的小计划者evens-only*&co的情况.

I'm having difficulty understanding what's going on with The Little Schemer's evens-only*&co example on page 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).很好，但是我想从newl，product，sum梳理出dnewl，dproduct，dsum时茫然无措.如果有人可以指导我如何设置DrRacket或Chez Scheme或MIT-Scheme以运行步进器，这也将很有帮助.

What I'm not getting is, with l as '((1) 2 3), it goes immediately into the final else with (car l) as (1) and (cdr l) as (2 3). Good, but my mind goes blank trying to sort out the dnewl, dproduct, dsum from the newl, product, sum. It also would be helpful if somebody could coach me on how to set up DrRacket or Chez Scheme or MIT-Scheme for running a stepper.

但是也许我太早了.初学者初次阅读此书真的应该理解这种疯狂的延续吗?

But maybe I'm spazzing too early. Is any beginner reading this for the first time actually supposed to understand this wild continuation?

推荐答案

我也发现本节在初读时也令人困惑，并且直到我在其他地方阅读了有关延续性和延续性传递风格(这就是这是什么).

I found this section confusing on first reading too, and only started to get it after I'd read up elsewhere about continuations and continuation-passing style (which is what this is).

冒着解释您已经得到的东西的风险，对我有帮助的一种查看方法是，将收集器"或延续"视为替换函数返回值的常规方法.在正常的编程风格中，您可以调用函数，接收值并在调用程序中对其执行某些操作.例如，标准递归length函数包含用于非空情况的表达式(+ 1 (length (cdr list))).这意味着，一旦(length (cdr list))返回一个值，就会产生一个等待生成的任何值的计算，我们可以将其视为(+ 1 [returned value]).在正常编程中，解释器会跟踪这些待处理的计算，这些计算往往会堆积"，如您在本书的前两章中所见.例如，在递归计算列表的长度时，我们有一个等待计算"的嵌套，其深度与列表的长度一样多.

At the risk of explaining something that you already get, one way of looking at it that helped me is to think of the "collector" or "continuation" as replacing the normal way for the function to return values. In the normal style of programming, you call a function, receive a value, and do something with it in the caller. For example, the standard recursive length function includes the expression (+ 1 (length (cdr list))) for the non-empty case. That means that once (length (cdr list)) returns a value, there's a computation waiting to happen with whatever value it produces, which we could think of as (+ 1 [returned value]). In normal programming, the interpreter keeps track of these pending computations, which tend to "stack up", as you can see in the first couple of chapters of the book. For example, in calculating the length of a list recursively we have a nest of "waiting computations" as many levels deep as the list is long.

采用连续传递样式，而不是调用函数并在调用函数中使用 returned 结果，我们通过向函数提供连续"来告诉函数在产生其值时该怎么做致电. (例如，这与异步Javascript编程中的回调操作类似，例如:您不必编写result = someFunction();而是编写someFunction(function (result) { ... })，而所有使用result的代码都放在回调函数中.)

In continuation-passing style, instead of calling a function and using the returned result in the calling function, we tell the function what to do when it produces its value by providing it with a "continuation" to call. (This is similar to what you have to do with callbacks in asynchronous Javascript programming, for example: instead of writing result = someFunction(); you write someFunction(function (result) { ... }), and all of the code that uses result goes inside the callback function).

这里的length为连续传递样式，仅供比较.我已经将延续参数称为return，该参数应该建议它在这里的工作方式，但是请记住，它只是一个普通的Scheme变量，与其他变量一样. (通常将延续参数在这种样式中称为k).

Here's length in continuation-passing style, just for comparison. I've called the continuation parameter return, which should suggest how it functions here, but remember that it's just a normal Scheme variable like any other. (Often the continuation parameter is called k in this style).

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

在有关延续的文章中，有阅读此代码的有用技巧. Little Schemer 的合著者Dan Friedman . (请参阅从第8页开始的II-5节).释义，这是上面的else子句所说的:

There is a helpful tip for reading this kind of code in an article on continuations by Little Schemer co-author Dan Friedman. (See section II-5 beginning on page 8). Paraphrasing, here's what the else clause above says:

想象您在(cdr lis)上调用length/k的结果，并且 称它为cdr-len，然后加一个并传递此加法的结果 到您的延续(return).

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))命名).连续或回调，我们已经使控制流(以及中间值的名称)明确了，而不是让解释器对其进行跟踪.

Note that this is almost exactly what the interpreter has to do in evaluating (+ 1 (length (cdr lis))) in the normal version of the function (except that it doesn't have to give a name to the intermediate result (length (cdr lis)). By passing around the continuations or callbacks we've made the control flow (and the names of intermediate values) explicit, instead of having the interpreter keep track of it.

让我们将此方法应用于evens-only*&co中的每个子句.由于此函数产生的是三个值而不是一个值，因此在这里有些复杂.偶数的乘积；和奇数之和.这是第一个子句，其中(car l)被认为是偶数:

Let's apply this method to each clause in evens-only*&co. It's slightly complicated here by the fact that this function produces three values rather than one: the nested list with odd numbers removed; the product of the even numbers; and the sum of the odd numbers. Here's the first clause, where (car l) is known to be an even number:

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

假设您得到了去除奇数的结果， 乘以偶数，然后从列表的cdr中添加奇数， 并分别命名为newl，product和sum. cons 列表的开头到newl上(因为它是偶数，所以应该去 结果)；将product乘以列表的开头(因为 我们正在计算偶数的乘积)；不理会sum；并通过这些 您的等待连续col三个值.

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.

在这种情况下，列表的开头是奇数:

Here's the case where the head of the list is an odd number:

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

和以前一样，但是将相同的newl和product值以及sum的总和和列表的开头传递给延续(即返回"它们)，因为我们正在求和向上的奇数.

As before, but pass the same values of newl and product to the continuation (i.e. "return" them), along with the sum of sum and the head of the list, since we're summing up odd numbers.

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

And here's the last one, where (car l) is a nested list, and which is slightly complicated by the double recursion:

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

想象一下，您获得了删除，求和和添加结果的结果. (car l)中的数字，并分别称为newl，product和sum；然后 假设您通过对(cdr l)做相同的事情而得到了结果， 并命名为dnewl，dproduct和dsum.恭候您的光临 继续，给出cons ing newl和dnewl所产生的值 (因为我们正在生成列表列表)；一起繁殖 product和dproduct;并添加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，在其他情况下话来说，您可以将我们在递归过程中建立的连续性链视为对传统编写函数的调用堆栈"进行建模！

Notice: each time we make a recursive call, we construct a new continuation for the recursive call, which "closes over" the current values of the argument, l, and the return continuation - col, in other words, you can think of the chain of continuations which we build up during the recursion as modelling the "call stack" of a more conventionally written function!

希望可以部分回答您的问题.如果我花了一点钱，那是因为我认为，在递归本身之后，延续是 The Little Schemer 和一般编程中的第二个真正整洁，易于扩展的想法.

Hope that gives part of an answer to your question. If I've gone a little overboard, it's only because I thought that, after recursion itself, continuations are the second really neat, mind-expanding idea in The Little Schemer and programming in general.

这篇关于Little Schemer仅限天数*& co的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！