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

Question

读完The Seasoned Schemer后,我觉得我理解得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实际上如何运作？

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的列表.

现在,由于我们可以看到如何使用continuation传递样式实现映射,我们可以使用它编写迭代器生成过程.该过程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一个过程,该过程在处理每个元素时将redfines 作为处理剩余部分的过程.重新定义后,它使用元素调用.传递的最后一个延迟实际上忽略了传递给它的结果,只是用符号调用.我们返回的不是价值,而是调用过程与延续.这里的间接意味着我们总是调用with 的最新值.传递作为延续意味着我们只需返回列表元素.nextlistlistnextkkmapkdoneiteratornextnextidentitynextidentityidentity

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

保存程序状态

在这两种实现中,您都在某种意义上"保存程序状态".您正在保存的重要状态是将继续迭代列表的状态.