Little Schemer evens-only*&co

Question

我很难理解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))))

什么我没有得到的是,有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继续传递风格,仅供比较.我已经调用了continuation参数return,它应该建议它如何在这里起作用,但请记住它只是一个普通的Scheme变量,就像其他任何变量一样.(通常k以此样式调用continuation参数).

(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上面的条款所说的:

想象你有打电话的结果length/k上(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.为了你的等待延续,给予所产生的价值cons荷兰国际集团newl和dnewl (因为我们正在创造一个列表的列表); 乘以 product和dproduct; 并添加sum和dsum.

注意:每次我们进行递归调用时,我们为递归调用构造一个新的延续,它"关闭"参数的当前值l,以及返回延续 - col换句话说,你可以想到链的我们在递归过程中建立的延续,用于建模更常规编写函数的"调用堆栈"!

希望能为你的问题提供部分答案.如果我有点过分,那只是因为我认为,在递归本身之后,延续是The Little Schemer中第二个非常整洁,思想扩展的想法和一般的编程.