One of the signal features of Scheme is its
support for jumps or nonlocal control. Specifically, Scheme allows
program control to jump to arbitrarylocations in the program, in
contrast to the more restrained forms of program control flow allowed by
conditionals and procedure calls. Scheme’s nonlocal control operator is a
procedure named call?with?current?continuation
. We will see how
this operator can be used to create a breathtaking variety of control
idioms.
call?with?current?continuation
The operator call?with?current?continuation
calls
its argument, which must be a unary procedure, with a value
called the “current continuation”. If nothing else, this explains the
name of the operator. But it is a long name, and is often abbreviated call/cc
.1
The current continuation at any point in the execution of a program is an abstraction of the rest of the program. Thus in the program
(+ 1 (call/cc (lambda (k) (+ 2 (k 3)))))
the rest of the program, from the point of view of
the call/cc
-application, is the following
program-with-a-hole (with []
representing
the hole):
call/cc 过程的 "the rest of the program" 就是下面的有一个 [] 的语句:
(+ 1 [])
In other words, this
continuation is a program that will add 1
to
whatever is used to fill its hole.
This is what the argument of call/cc
is called with.
Remember that the argument of call/cc
is the procedure
(lambda (k) (+ 2 (k 3)))
This procedure’s body applies the continuation (bound now to
the parameterk
) to the
argument 3
. This
is when the unusual aspect of the continuation springs to the fore. The
continuation call abruptly(突然地) abandons its own computation and replaces it
with the rest of the program saved in k
!
In other words, the part of the procedure involving the addition of 2
is jettisoned(抛弃),
and k
’s
argument 3
is sent directly to the
program-with-the-hole:
(+ 1 [])
The program now running is simply
(+ 1 3)
which returns 4
.
In sum,
(+ 1 (call/cc (lambda (k) (+ 2 (k 3))))) => 4
The above illustrates what is called
an escaping continuation, one used to exit out of a
computation (here: the (+ 2 [])
computation). This is a useful
property, but Scheme’s continuations can also be used to return to previously
abandoned contexts, and indeed to invoke them many times. The “rest of the
program” enshrined in a continuation is available whenever and how many ever
times we choose to recall it, and this is what contributes to the great and
sometimes confusing versatility of call/cc
.
As a quick example, type the following at the listener:
(define r #f) (+ 1 (call/cc (lambda (k) (set! r k) (+ 2 (k 3))))) => 4
The latter expression returns 4
as before. The
difference between this use of call/cc
and the previous example is that
here we also store the continuation k
in
a global variable r
.
Now we have a permanent record of the continuation in r
. If we call it on a number, it will return that
number incremented by 1
:
(r 5) => 6
Note that r
will abandon its own continuation, which
is better illustrated by embedding the call to r
inside some context:
而把 r 调用嵌入在某些环境中更能证明 continuation 跳转的作用:
(+ 3 (r 5)) => 6
r 调用会将程序控制流直接跳转到 "the continuation" (+ 1 []) 处,再用 5 替换 [],执行那里的代码。
The continuations provided by call/cc
are
thus abortive continuations.
Escaping continuations are the simplest use of call/cc
and are very
useful for programming procedure or loop exits. Consider a procedure list?product
that takes a
list of numbers and multiplies them. A straightforward recursive definition
for list?product
is:
(define list-product (lambda (s) (let recur ((s s)) (if (null? s) 1 (* (car s) (recur (cdr s)))))))
There is a problem with this solution. If one of the
elements in the list is 0
, and if there are many elements
after 0
in
the list, then the answer is a foregone conclusion. Yet, the code will have us
go through many fruitless recursive calls to recur
before producing the answer. This is
where an escape continuation comes in handy. Using call/cc
, we can rewrite the
procedure as:
但是上面的计算方法有一个问题,就是列表中有一个元素为 0 并且其后还有许多个元素,当计算到 0 时,结果就可以确定为 0,而不用在与其后的元素相乘。此时,我们可以用 escaping continuations 重写 list-product 过程来避免这些无效的计算:
(define list-product (lambda (s) (call/cc (lambda (exit) (let recur ((s s)) (if (null? s) 1 (if (= (car s) 0) (exit 0) (* (car s) (recur (cdr s))))))))))
If a 0
element is encountered, the
continuation exit
is called with 0
, thereby avoiding further calls to recur
.
更多:
http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-15.html#node_chap_13
http://lispor.is-programmer.com/posts/23638.html
Teach Yourself Scheme in Fixnum Days 13 Jump跳转
原文:http://www.cnblogs.com/youxin/p/3551399.html