9.26 gauche.partcont - Partial continuations

Module: gauche.partcont ¶

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

Macro: reset expr … ¶

{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.

Macro: shift var expr … ¶

{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.

Function: call/pc proc ¶

{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.

1. shift packages the rest of the chain of work until the end of reset, and bind it to the variable k.
2. The continuation of 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>