gauche.partcont - Partial continuations ¶Gauche internally supports partial continuations (a.k.a. delimited continuations) natively. This module exposes the feature for general use.
Note:
Partial continuations use two operators, reset and shift.
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 :prefix
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 ....) )
{gauche.partcont}
Saves the current continuation, and executes expr … with
a null continuation or empty continuation.
The shift operator captures the continuation from the shift
expression to this null continuation.
Note on implicit delimited continuations:
There’s an occasion Gauche effectively calls reset internally:
When C routine calls back to Scheme in non-CPS manner.
(If you know C API, it is Scm_EvalRec(), Scm_ApplyRec*(),
Scm_Eval() and 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
by a 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 gosh.
This may be surprising if you don’t know about the implicit delimited
continuation.
Other places the implicit delimited continuations are created
are the handlers virtual ports (see gauche.vport - Virtual ports),
object-apply methods called from write and display,
and GUI callbacks such as the one registered by glut-display-func
(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.
{gauche.partcont}
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 reset.
That is, after executing expr …, the value is passed
to the expression waiting for the value of the most recent reset.
When a partial continuation bound to var is executed, its
argument is passed to the continuation waiting for the value
of this shift. When the execution of the partial continuation
reaches its end, it returns from the expression waiting
for the value of invocation of var.
{gauche.partcont}
This is a wrapper of shift. (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
below).
So, whenever k is invoked, the control goes through the
chain from *.
... -> 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
attribute of call/cc makes it difficult to deal with.
The reset primitive cuts this chain of
continuation. The original chain of continuation (the x-end
in the following figure) is saved somewhere, and the continuation
of reset itself becomes open-ended (the o-end
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 shift inside reset?
This is a superficial view of inserting shift into
somewhere down the chain of reset:
... -> (reset -> X -> Y -> (shift k ... ) -> Y' -> X' ) -> o
What actually happens is as follows.
shift packages the rest of the chain of work until the
end of reset, and bind it to the variable k.
shift becomes a null continuation as well,
so after shift returns, the control skips the rest of
operations until the corresponding reset.
... -> (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 for-each to 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
time iter is called, shift in inv
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
function 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 for-each.
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>
The util.combinations module (see util.combinations - Combination library)
provides a procedure that calls a given procedure with
every permutation of the given collection. If you pass
it to 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>