6

读完《老谋深算》后，我觉得我理解call/cc正确。但是，在看到一些 WOW 技巧后，call/cc我发现我错了。

(define cc 0)
(define (f)
  (call/cc (lambda (k)
             (set! cc k)
             3)))

(+ 1 2 4 (f)) ; eval's to 10
(cc 13) ; eval's to 20

这完全符合我的理解。我想当我call/cc接到电话时，我只是在保存程序状态。并用函数调用它旁边的函数。如果从某个地方调用该函数 ( )，那么我只是用给它的参数k替换整个东西。上面的程序似乎也是这样工作的(call/cc ...)

但，

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)
    (call/cc (lambda (k) (state k))))
  generator)

(define (next)
  (itr (range 2)))

调用next3 次会产生 0、1 和'done. 这意味着当state使用它提供的功能时k，generator它并没有恢复程序的状态。我只是向你展示了我试图理解它。

那么，call/cc实际上是如何工作的呢？

4

2 回答 2

8

带有继续传递样式（不带call/cc）

如果您实现一个使用显式延续传递样式而不是call/cc首先使用的版本，则可能更容易理解此示例。在这种情况下，让我们从 的延续传递版本开始map：

(define (kmap fn list k)
  (if (null? list)
      (k list)
      (fn (car list)
          (lambda (head)
            (kmap fn
                  (cdr list)
                  (lambda (tail)
                    (k (cons head tail))))))))

(define (identity x) x)

(kmap (lambda (x k) (k (+ 1 x))) '(1 2 3 4) identity)
;=> (2 3 4 5)

如果你不熟悉连续传球风格，这可能有点绕你的头，但它并不太难。请记住，kmap每个fn最后都需要一个额外的参数，应该用“结果”调用。因此，当我们调用fnwith时(car list)，我们还向它传递了一个过程，该过程(lambda (head) ...)负责为我们处理其余的映射。映射的其余部分kmap再次定义。每次调用都kmap需要一个最终的延续，该延续期望接收由映射列表产生fn的列表。

现在，由于我们可以看到如何使用延续传递样式实现映射，我们可以使用它编写迭代器生成过程。该过程iterator接受一个列表并返回一个过程，我们可以调用该过程来获取list.

(define (iterator list)
  (define (next k)
    (kmap (lambda (item more-next)
            (set! next more-next)
            (k item))
          list
          (lambda (results)
            (k 'done))))
  (lambda ()
    (next identity)))

> (define get (iterator '(1 2)))
> (get)
1
> (get)
2
> (get)
done
> (get)
done

> (define get (iterator '(a b c)))
> (get)
a
> (get)
b
> (get)
c
> (get)
done
> (get)
done

这里的诀窍是我们定义了一个本地过程next。它调用kmap一个过程，该过程重新定义 next的每个元素何时list被处理为将处理 的其余部分的过程list。重新定义后，它与元素一起next调用。k传递给它的最后一个延续kmap实际上忽略了传递给它的结果，只是k用符号调用done。我们返回的iterator不是 的值，而是一个用 continuationnext调用的过程。这里的间接意味着我们总是调用with的最新值。通过nextidentitynextidentityidentity因为延续意味着我们只取回列表元素。

和call/cc

既然我们看到了如何在没有 call/cc的情况下做到这一点，我们就可以更好地了解如何使用call/cc来做到这一点。回想一下问题中的定义：

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)                   
    (call/cc (lambda (k) (state k))))   
                                        
  generator)

返回生成器

首先请注意

  (define (generator)
    (call/cc (lambda (k) (state k))))

  generator

可以简化为

(lambda () (call/cc (lambda (k) (state k))))

这就是我们在实施中所做的。当您从 REPL 调用它时，您k想要做的就是获取该值并返回它（并打印它）。在我们的版本中，我们通过简单地返回原样来近似它。也就是说，我们使用identity，并且我们使用名称next而不是state。所以

(lambda () (call/cc (lambda (k) (state k))))

就像

(lambda () (next identity))

（state或next）过程

剩下的

  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

也与我们所做的非常相似。我们不使用kmap带有fn两个参数（项目和延续）的 and a，而是使用for-each带有单个参数（项目）的过程，并且在该过程中，我们使用它call/cc来获取延续。所以

(for-each
  (lambda (item)
    (call/cc (lambda (h)
               ...

就像

(kmap (lambda (item h)
        ...

for-each不需要最终的延续参数，所以我们不能通过 result-ignoring (lambda () (k 'done))。相反，我们只是在调用之后(k 'done) 调用for-each。那是，

(for-each fn list)
(k 'done)

就像

(kmap fn
      list
      (lambda (result)
        (k 'done)))

保存程序状态

在这两种实现中，您在某种意义上都在“保存程序状态”。您要保存的重要状态是将继续迭代列表的状态。

于 2014-06-12T14:51:57.983 回答
1

你怀疑有问题是正确的。代码完全被破坏了，这从生成器在调用项目时无法捕获主线程序的新延续这一事实中显而易见。或者更确切地说，它摸索并扔掉了那个延续。结果是在尝试获取第二项时调用了错误的延续，导致无限循环。

首先，让我们从您的问题的措辞中纠正一些问题。调用next不会产生项目；调用next产生生成器函数。next应该使用的方式示例如下：

(let ((g (next)))
  (list (g) (g) (g)))  ;; should return (0 1 done)

但是，实际上它是行不通的。让我们检查一下：

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)
    (call/cc (lambda (k) (state k))))
  generator)

(define (next)
  (itr (range 2)))

让我们追溯正在发生的事情。

setup:调用时(next)，表达式(iter (range 2))返回，在绑定和变量generator的环境中捕获的闭包。itrlststate

第一次迭代：next因此调用返回的生成器的第一次调用generator。现在generator捕获它自己的延续，它出现k在 中lambda，并将其传递给state。所以 thenstate运行，并且generator's 延续绑定到k。它进入第一次迭代，并通过将自己替换为新的延续来保存自己的状态：(set! state h)。至此，之前state对define-d函数的绑定就被覆盖了；state现在是恢复for-each. 下一步是让步item给k延续，这让我们回到generator返回项目。太好了，这就是第一次调用(next).

第二次迭代：从这里开始，事情就出错了。再次返回的对生成器的第二次调用next再次捕获延续并调用state现在是生成协同例程的延续。生成器将自己的延续传递给state. 但state不再是define-d by的功能itr！因此，新捕获的延续 ingenerator不会与k. 的词法范围内的参数连接for-each。当(k item)被调用来产生第二个项目时， thisk仍然是指原始k绑定，它在第一次调用中保存最初捕获的延续generator。这类似于向后 goto 并导致非终止行为。

以下是我们可以解决的方法：

(define (itr lst)
  (define yield '()) ;; forward definition (could use let for this).

  (define (state)    ;; k parameter is gone
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (yield item))))  ;; call yield, not k
              lst)
    (yield 'done))  ;; yield, not k.

  (define (generator)
    (call/cc (lambda (self) 
               (set! yield self) ;; save new escape on each call
               (state))))
  generator)

;; test
(let ((g (itr (range 2))) ;; let's eliminate the "next" wrapper
  (display (list (g) (g) (g))))

输出是(0 1 done)。

于 2016-06-20T14:50:11.910 回答