scheme - call-with-current-continuation - 状态保存概念

Question

看完经验丰富的计划者 我觉得我明白了call/cc适本地。但是，在看到 call/cc 的一些 WOW 技巧之后我发现我错了。

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

调用 next 3 次产生 0、1 和 'done .这意味着当 state使用函数 k由 generator 给出它没有恢复程序的状态。 我只是向你展示了我试图理解它。

那么， call/cc 怎么样？实际工作？

Answer 1

带有延续传递样式(不带 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每个最后都需要一个额外的参数，应该用“结果”调用。所以当我们调用 fn与 (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 返回的内容不是 next 的值, 但是一个调用 next 的过程继续 identity .这里的间接意味着我们总是调用 next 的最新值。与 identity .路过 identity因为延续意味着我们只取回列表元素。
与 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需要两个参数(项目和延续)，我们使用 for-each它采用单个参数(项目)的过程，在该过程中，我们使用 call/cc捕获延续。所以

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

就像

(kmap (lambda (item h)
        ...

for-each不需要最终的延续参数，所以我们不能传递结果忽略 (lambda () (k 'done)) .相反，我们只需调用 (k 'done)在 for-each 之后称呼。那是，

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

就像

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

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