帮助理解Scheme中的Continuations

Question

我和The Little Schemer一起工作,学习Scheme并在我的环境中使用PLT-Scheme.

Little Schemer对递归给了我很大的帮助(现在对我来说很简单)但是我仍然坚持介绍"收藏家"这本书的一部分,并将整个函数称为一个延续.

这是他们使用的示例代码.我理解递归元素但是我被卡住了,特别是在lambda函数上 - 我的思想不能遵循路径以及如何设置lambda函数的参数(因为他们唯一的调用是在递归中再次调用它们,有功能体内没有具体用途).

如果有人能够或多或少地通过将函数递归到lambda收集器来分解计算路径,那可能对我有所帮助.

;; Build a nested list of even numbers by removing the odd ones from its
;; argument and simultaneously multiply the even numbers and sum the odd
;; numbers that occur in its argument.
(define (even-only-collector l col)
  (cond
    ((null? l)
      (col (quote ()) 1 0))
    ((atom? (car l))
      (cond
        ((even? (car l))
          (even-only-collector (cdr l)
            (lambda (newl p s)
              (col (cons (car l) newl)
                (* (car l) p) s))))
         (else
           (even-only-collector (cdr l)
             (lambda (newl p s)
               (col newl
                 p (+ (car l) s)))))))
    (else
      (even-only-collector (car l)
        (lambda (al ap as)
          (even-only-collector (cdr l)
            (lambda (dl dp ds)
              (col (cons al dl)
                (* ap dp)
                (+ as ds)))))))))

;; The collector function
(define (collector newl product sum)
  (cons sum
    (cons product newl)))

先感谢您!!

Answer 1

尝试更简单的东西,看看它是如何工作的.例如,这是一个list-sum接收延续参数(通常称为k)的函数版本:

(define (list-sum l k)
  (if (null? l)
    ???
    (list-sum (cdr l) ???)))

基本模式就在那里,缺失的部分是有趣的事情发生的地方.continuation参数是一个期望接收结果的函数 - 所以如果列表为null,很明显我们应该发送它0,因为这是总和:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) ???)))

现在,当列表不为null时,我们用列表的尾部递归调用函数(换句话说,这是一个迭代),但问题是延续应该是什么.这样做:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) k)))

显然是错误的 - 这意味着k最终会获得总和,(cdr l)而不是全部l.相反,在那里使用一个新函数,它将总结第一个元素l以及它接收的值:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum)))))

这越来越近,但仍然是错误的.但是考虑一下事情是如何工作的 - 这是一个很好的观点 - 我们正在调用list-sum一个本身会收到总和的延续,并将我们现在看到的第一个项目添加到它.缺少的部分很明显,我们忽略了这一点k.我们需要的是组合 k使用此功能-所以我们做同样的总和操作,那么结果发送到k:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l)))))))

这终于奏效了.(顺便说一下,请记住,这些lambda功能中的每一个都有自己的"副本" l.)您可以尝试以下方法:

(list-sum '(1 2 3 4) (lambda (x) x))

最后请注意,这与:

(define (list-sum l k)
  (if (null? l)
    (k 0)
    (list-sum (cdr l) (lambda (s) (k (+ s (car l)))))))

如果你明确表达了作品.

(您也可以在中间+ lambda学生语言中使用此代码,然后单击步进按钮以查看评估是如何进行的 - 这将需要一段时间才能完成,但您将看到延续函数如何嵌套,每个用它自己的列表视图.)