当前继续通话-状态保存概念 [英] call-with-current-continuation - state saving concept
问题描述
在阅读《 经验丰富的计划者》 之后，我觉得我对call/cc的理解正确.但是，看到call/cc的一些WOW技巧后，我发现我错了.
After reading The Seasoned Schemer I felt I understood call/cc properly. But, after seeing some WOW tricks with call/cc I found I was wrong.
(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 ...)内容. 上面的程序似乎也是如此
That perfectly match my understanding. I think when I reach a call/cc call I am just saving the program state. and calling the function next to it with a function. If that function (k) is called from somewhere than I just replacing the entire (call/cc ...) stuff with the parameter given to it. The above program seems to worked that way too
但是
(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)))
调用3次next会产生0、1和'done.这意味着当state使用generator给定的功能k时，它没有恢复程序的状态. 我只是告诉你我想了解它.
Calling next 3 times produces 0, 1 and 'done. That means when state used the function k given by generator it didn't restore the state of the program. I just showed you I tried to understand it.
那么，call/cc实际上如何工作?
So, how does call/cc actually work?
推荐答案
具有连续传递样式(没有call/cc)
如果实现的版本使用显式连续传递样式而不是首先使用call/cc，则可能更容易理解此示例.在这种情况下，让我们从map的连续传递版本开始:
With Continuation Passing Style (without call/cc)
It may be easier to understand this example if you implement a version that uses explicit continuation passing style rather than call/cc first. In this case, let's start with a continuation passing version of 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各自在末尾都带有一个附加参数，该参数应与结果"一起调用.因此，当我们用(car list)调用fn时，我们也将其传递给过程(lambda (head) ...)，该过程负责为我们处理其余的映射.其余的映射再次根据kmap进行定义.每次对kmap的调用都会进行最后的延续，希望能收到将fn映射到列表上而得到的列表.
If you're not familiar with continuation passing style, this may be a bit to wrap your head around, but it's not too too hard. Remember that kmap and fn each take an additional parameter at the end that should be called with "the result". So when we call fn with (car list), we also pass it a procedure (lambda (head) ...) that's responsible for taking care of the rest of the mapping for us. The rest of the mapping is defined in terms of kmap again. Each call to kmap takes a final continuation that expects to receive the list that results from mapping fn over the list.
现在，由于我们可以看到如何使用连续传递样式来实现映射，因此我们可以使用它来编写迭代器生成过程.过程iterator获取一个列表，并返回一个过程，我们可以调用该过程来获取list的每个元素.
Now, since we can see how a mapping can be implemented with continuation passing style, we can write an iterator generation procedure using it. The procedure iterator takes a list and returns a procedure that we can call to get each element of 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.当将list的每个元素处理为将处理list其余部分的过程时，它将使用重新定义 next的过程调用kmap.重新定义next后，它将使用元素调用k.传递给kmap的最后一个延续实际上忽略了传递给它的结果，仅使用符号done调用k.我们从iterator返回 的值不是next的值，而是一个以identity继续调用next的过程.这里的间接表示我们总是用identity调用next的 latest 值.继续传递identity表示我们只返回了列表元素.
The trick here is that we define a local procedure next. It calls kmap with a procedure that redfines next when each element of list is processed to be the procedure that will process the remaining part of list. After redefining next, it calls k with the element. The final continuation passed to kmap actually ignores the results passed to it, and just calls k with the symbol done. What we return from iterator is not the value of next, but a procedure that calls next with the continuation identity. The indirection here means that we always call the latest value of next with identity. Passing identity as the continuation means that we just get the list element back.
现在，我们看到了如何在没有 call/cc的情况下执行此操作，我们将更好地了解如何使用call/cc进行此操作.回顾问题中的定义:
Now that we see how can we do this without call/cc, we're better equipped to see how we can use call/cc to do it. Recall the definition from the question:
(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)
退还发电机
第一个注意事项
Returning the generator
First note that
(define (generator)
(call/cc (lambda (k) (state k))))
generator
可以简化为
(lambda () (call/cc (lambda (k) (state k))))
这就是我们在实现过程中所做的事情.当您从REPL调用此函数时，k想要做的就是获取值并将其返回(并打印).在我们的版本中，我们通过简单地将其返回不变来近似.也就是说，我们使用identity，并且使用名称next而不是state.所以
and that's just about what we did in our implementation. When you're calling this from the REPL, all that the k wants to do is get the value and return it (and print it). In our version, we approximate that by simply returning it unchanged. That is, we use identity, and we used the name next instead of state. So
(lambda () (call/cc (lambda (k) (state k))))
就像
(lambda () (next identity))
state(或next)过程
其余的
The state (or next) procedure
The rest of it
(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抓住延续.所以
is very similar to what we did, too. Instead of using kmap and a fn that takes two arguments (the item and the continuation), we use for-each which takes a procedure of a single argument (the item) and inside that procedure, we use call/cc to grab the continuation. So
(for-each
(lambda (item)
(call/cc (lambda (h)
...
就像
(kmap (lambda (item h)
...
for-each不需要最终的延续参数，因此我们无法传递忽略结果的(lambda () (k 'done)).相反，我们只是在for-each调用之后调用(k 'done) .就是
for-each doesn't need a final continuation argument, so we can't pass the result-ignoring (lambda () (k 'done)). Instead, we just call (k 'done) after the for-each call. That is,
(for-each fn list)
(k 'done)
就像
(kmap fn
list
(lambda (result)
(k 'done)))
保存程序状态
在这两种实现中，您都在某种意义上保存了程序状态".您要保存的重要状态是将继续遍历列表的状态.
Saving program state
In both of these implementations, you're "saving the program state" in some sense. The important state that you're saving is the one that will continue iterating over the list.
这篇关于当前继续通话-状态保存概念的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
