14

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

这是代码：

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

我没有得到的是，使用las时，它会立即使用as和as'((1) 2 3)进入决赛。很好，但是我的大脑一片空白，试图从, ,中找出, , 。如果有人可以指导我如何设置 DrRacket 或 Chez Scheme 或 MIT-Scheme 来运行步进器，那也会很有帮助。else(car l)(1)(cdr l)(2 3)dnewldproductdsumnewlproductsum

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

4

4 回答 4

23

我在第一次阅读时也发现这部分令人困惑，并且只是在我在其他地方阅读了有关延续和延续传递风格（这就是它）之后才开始理解它。

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

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

这里是length连续传递风格，只是为了比较。我已经调用了 continuation 参数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)))))))

在Little Schemer的合著者 Dan Friedman的一篇关于 continuations 的文章中，有一个阅读此类代码的有用提示。（见第 8 页开始的第 II-5 节）。解释一下，这就是else上面的条款所说的：

假设你有调用length/kon的结果，然后(cdr lis)调用它cdr-len，然后加一个并将这个加法的结果传递给你的延续 ( 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)))

想象一下，您有从列表中删除奇数、乘偶数和添加奇数的结果cdr，并将它们newl分别称为product、 和sum。cons列表的头部到newl（因为它是偶数，它应该在结果中）；乘以product列表的头部（因为我们正在计算偶数的乘积）；不理会sum；并将这三个值传递给您的等待继续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))))))

想象一下，您有删除、求和和添加数字的结果，(car l)并调用这些newl,product和sum; 然后想象你有做同样事情的结果(cdr l)，并调用它们dnewl，dproduct和dsum。对于您的等待继续，给出由consing newland生成的值dnewl （因为我们正在生成列表列表）；product和相乘 dproduct；并添加sum和dsum。

注意：每次我们进行递归调用时，我们都会为递归调用构造一个新的延续，它“关闭”参数的当前值l，以及返回延续 - col，换句话说，你可以想到我们在递归期间建立的延续作为对更传统编写函数的“调用堆栈”的建模！

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

于 2012-05-22T11:52:22.490 回答
2

The answer by Jon O. is a really great in-depth explanation of underlying concepts. Though for me (and hopefully, for some other people too), understanding of concepts like this is a lot more easier when they have a visual representation.

So, I have prepared two flow-charts (similar to ones I did for multirember&co, untangling what is happening during the call of evens-only*&co

given l is:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2)

and col is:

(define the-last-friend
    (lambda (newl product sum)
        (cons sum (cons product newl))
    )
)

One flow-chart, reflecting how variables relate in different steps of recursion: Visual walkthrough showing relations between variables Second flow-chart, showing the actual values, being passed: Visual walkthrough with values

My hope is, that this answer will be a decent addition to the Jon's explanation above.

于 2017-11-08T08:41:37.080 回答
0

我一直在阅读如何设计程序（felleisen et.al.）。我正在浏览他们定义本地定义的部分。我已经编写了一个代码，它使用本地定义实现了上述 evens-only&co。这是我写的：

(define (evens-only&co l)
  (local ((define (processing-func sum prod evlst lst)
            (cond ((null? lst) (cons sum (cons prod evlst)))
                  ((atom? (car lst))
                   (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst)))
                         (else
                          (processing-func (+ sum (car lst)) prod evlst (cdr lst)))))
                  (else
                   (local ((define inner-lst (processing-func sum prod  '() (car lst))))
                   (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst)))))))
    (processing-func 0 1 '() l)))

为了测试，当我输入 (evens-only&co '((9 1 2 8) 3 10 ((9 9) 7 6) 2)) 时，它返回 '(38 1920 (2 8) 10 (() 6) 2)正如小计划者所期望的那样。但是，我的代码在一种情况下失败：当根本没有偶数时，偶数的乘积仍然显示为 1。例如 (evens-only&co '((9 1) 3 ((9 9) 7 )))返回'(38 1 () (()))。我想我需要一个额外的功能来纠正这个问题。@melwasul：如果您不熟悉本地定义，很抱歉在这里发布。我建议你也阅读 HTDP。这是一本适合初学者的好书。但是方案专家也可以在我的代码上发表他们的评论。我对本地定义的理解是否正确？

于 2012-05-24T19:18:38.140 回答
0

在等式伪代码（类似KRCf x y的表示法，为 call编写(f x y)，它是明确的）中，这是

evens-only*&co l col 
   = col [] 1 0                                     , IF null? l
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col (cons (car l) newl)
                            (opx (car l) product)
                            sum )                   , IF atom? (car l) && even? (car l)
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col  newl  product  (op+ (car l) sum) )      , IF atom? (car l)
   = evens-only*&co (car l) 
                    ( anewl aproduct asum =>
                         evens-only*&co (cdr l)
                                        ( dnewl dproduct dsum =>
                                             col (cons anewl    dnewl)
                                                 (opx  aproduct dproduct)
                                                 (op+  asum     dsum) ) )   , OTHERWISE

这是一个CPS代码，它从输入嵌套列表（即树）中收集所有偶数，同时保留树结构，并找到所有偶数的乘积；至于非偶数，它总结了它们：

  • 如果l是一个空列表，则三个基本（身份）值作为参数传递给 col；

  • 如果(car l)是偶数，则处理的结果是 和 ，(cdr l)然后将newl它们作为参数传递给 ，而前两个通过 consing ⁄ 乘以（偶数）来增加；productsumcol(car l)

  • 如果(car l)是一个不是偶数的原子，则处理的结果是 和 ，(cdr l)然后将newl它们作为参数传递给第三个，通过与（非偶数原子）求和而增加；productsumcol(car l)

  • 如果(car l)是一个列表，处理的结果(car l)是anewl，aproduct和asum，然后处理的结果(cdr l)是dnewl，dproduct和dsum，然后三个组合的结果作为参数传递给col。

[]和基本情况分别是列表幺半群、乘法下的数字和加法下的数字1的0单位元素。这只是意味着组合到结果中时不会改变结果的特殊值。

作为说明，对于'((5) 2 3 4)（接近问题中的示例），它创建了计算

evens-only*&co [[5], 2, 3, 4] col
=
col  (cons []                   ; original structure w only the evens kept in,
           (cons 2              ;   for the car and the cdr parts
              (cons 4 [])))
     (opx 1                     ; multiply the products of evens in the car and 
          (opx 2 (opx 4 1)))    ;   in the cdr parts
     (op+ (op+ 5 0)             ; sum, for the non-evens
          (op+ 3 0))

与我的其他答案（对姐妹问题）类似，这是另一种编写方式，使用模式匹配伪代码（带警卫）：

evens-only*&co  =  g   where
  g [a, ...xs...] col 
         | pair? a    = g a  ( la pa sa =>
                         g xs ( ld pd sd =>
                                        col [la, ...ld...] (* pa pd) (+ sa sd) ) )
         | even? a    = g xs ( l p s => col [ a, ...l... ] (* a  p )       s     )
         | otherwise  = g xs ( l p s => col         l            p   (+ a  s )   )
  g []            col =                 col []              1         0

这种表示法的经济性（和多样性）确实使它更清晰，更容易看到，而不是迷失在函数和变量等长名称的单词沙拉中，括号作为列表数据的语法分隔符重载，子句分组（像在cond表达式中），名称绑定（在表达式中）和lambda函数调用指示符看起来都非常相似。S 表达式符号的相同一致性有利于机器（即 lispread和宏）的操作，这对人类的可读性是有害的。

于 2018-01-22T18:20:45.150 回答