gauche.partcont- Partial continuations
Gauche internally supports partial continuations (a.k.a. delimited continuations) natively. This module exposes the feature for general use.
Partial continuations use two operators,
Those names are introduced in the original papers, and stuck in the
programming world. Unfortunately those names are too generic as
library function names. We thought giving them more descriptive names,
but decided to keep them after all; when you talk about partial
continuations you can’t get away from those names. If these names
conflict to other names in your program, you can use
import specifier (see Using modules), for example as follows:
;; Add prefix pc: to the 'reset' and 'shift' operators. (use gauche.partcont :prefix pc:) (pc:reset ... (pc:shift k ....) )
Saves the current continuation, and executes expr … with
a null continuation or empty continuation.
shift operator captures the continuation from the
expression to this null continuation.
Note on implicit delimited continuations:
There’s an occasion Gauche effectively calls
When C routine calls back to Scheme in non-CPS manner.
(If you know C API, it is
Scm_Apply() family of functions.) The callers
of such routines expect the result is returned at most once, which won’t
work well with Scheme’s continuations that have unlimited extent.
Such calls create delimited continuations implicitly.
For example, the
main routine of
gosh calls Scheme REPL by
Scm_Eval(), which means the entire REPL is effectively surrounded
reset. So, if you call
shift without corresponding
reset, the continuation of
shift becomes the continuation
of the entire REPL—which is to exit from
This may be surprising if you don’t know about the implicit delimited
Other places the implicit delimited continuations are created
are the handlers virtual ports (see Virtual ports),
object-apply methods called from
and GUI callbacks such as the one registered by
(See the document of Gauche-gl for the details), to name a few.
In general you don’t need to worry about it too much, since most built-in and extension routines written in C calls back Scheme in CPS manner, and works with both full and delimited continuations.
Packages the continuation of this expression until the current null
continuation marked by the most recent
reset into a procedure,
binds the procedure to var, then executes expr …
with the continuation saved by the most recent
That is, after executing expr …, the value is passed
to the expression waiting for the value of the most recent
When a partial continuation bound to var is executed, its
argument is passed to the continuation waiting for the value
shift. When the execution of the partial continuation
reaches its end, it returns from the expression waiting
for the value of invocation of var.
This is a wrapper of
(shift k expr …)
is equivalent to
(call/pc (lambda (k) expr …)).
Sometimes this similarity of
call/cc comes handy.
Well, … I bet you feel like your brain is twisted hard unless you are one of those rare breed from the land of continuation. Let me break down what’s happening here informally and intuitively.
Suppose a procedure A calls an expression B. If A expects a return value from B and continue processing, we split the part after returning from B into a separate chunk A’, then we can think of the whole control flow as this straight chain:
A -> B -> A'
A -> B is a procedure call and
B -> A' is a return,
but we all know procedure call and return is intrinsically the
same thing, right?
Procedure B may call another procedure C, and so on. So when you look at an execution of particular piece of code, you can think of a chain of control flow like this:
... -> A -> B -> C -> .... -> C' -> B' -> A' -> ...
The magic procedure
call/cc picks the head of the chain
following its execution (marked as
* in the figure below),
and passes it to the given procedure (denoted
k in the figure
k is invoked, the control goes through the
... -> A -> B -> (call/cc -> (lambda (k) ... ) ) -> B' -> A' -> ... | ^ \-----------> *
One difficulty with
call/cc is that the extracted chain
is only one-ended—we don’t know what is chained to the
right. In fact, what will come after that depends
on the whole program; it’s outside of local control. This global
call/cc makes it difficult to deal with.
reset primitive cuts this chain of
continuation. The original chain of continuation (the
in the following figure) is saved somewhere, and the continuation
reset itself becomes open-ended (the
in the following figure).
... -> A -> B -> (reset ... ) -> o x -> B ' -> A' -> ...
A rule: If control reaches to the
o-end, we pick the
x-end most recently saved.
Because of this,
reset alone doesn’t show any
difference in the program behavior.
Now what happens if we insert
This is a superficial view of inserting
somewhere down the chain of reset:
... -> (reset -> X -> Y -> (shift k ... ) -> Y' -> X' ) -> o
What actually happens is as follows.
shiftpackages the rest of the chain of work until the end of
reset, and bind it to the variable k.
shiftbecomes a null continuation as well, so after
shiftreturns, the control skips the rest of operations until the corresponding
... -> (reset -> X -> Y -> (shift k ... ) ---------> ) -> o | \-------> Y' -> X' ) -> o
In other words, when you consider the
reset form as
one chunk of task, then
shift in it
stashes away the rest of the task and immediately
returns from the task.
Let’s see an example. The walker argument in the following example is a procedure that takes a procedure and some kind of collection, and applies the procedure to the each element in the collection. We ignore the return value of walker.
(define (inv walker) (lambda (coll) (define (continue) (reset (walker (lambda (e) (shift k (set! continue k) e)) coll) (eof-object))) (lambda () (continue))))
A typical example of walker is
for-each, which takes
a list and applies the procedure to each element of the list.
If we pass
inv, we get a procedure
that is inverted inside-out. What does that mean?
See the following session:
gosh> (define inv-for-each (inv for-each)) inv-for-each gosh> (define iter (inv-for-each '(1 2 3))) iter gosh> (iter) 1 gosh> (iter) 2 gosh> (iter) 3 gosh> (iter) #<eof>
When you pass a list to
inv-for-each, you get an iterator
that returns each element in the list for each call. That’s because every
iter is called,
stashes away the task of walking the rest of the collection
and set it to
continue, then returns the current element e.
walker doesn’t need to work just on list. The following
for-each-leaf traverses a tree and
apply f on each non-pair element.
(define (for-each-leaf f tree) (match tree [(x . y) (for-each-leaf f x) (for-each-leaf f y)] [x (f x)]))
And you can inverse it just like
gosh> (define iter2 ((inv for-each-leaf) '((1 . 2) . (3 . 4)))) iter2 gosh> (iter2) 1 gosh> (iter2) 2 gosh> (iter2) 3 gosh> (iter2) 4 gosh> (iter2) #<eof>
util.combinations module (see Combination library)
provides a procedure that calls a given procedure with
every permutation of the given collection. If you pass
inv, you get a procedure that returns
every permutation each time.
gosh> (define next ((inv permutations-for-each) '(a b c))) next gosh> (next) (a b c) gosh> (next) (a c b) gosh> (next) (b a c) gosh> (next) (b c a) gosh> (next) (c a b) gosh> (next) (c b a) gosh> (next) #<eof>