Higher-Order Programming » Lab Sessions

Session 10

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Continuation Passing Style

In a previous lab session we have seen the following function to search for an element in a list:

(define (in-list? x ys) (cond ((null? ys) #f) ((eq? x (car ys)) #t) (else (in-list? x (cdr ys)))))

and their continuation-passing-style (CPS) variants.

(define (in-list-cont? x ys cont) (cond ((null? ys) (cont #f)) ((eq? x (car ys)) (cont #t)) (else (in-list-cont? x (cdr ys) cont)))) (define (in-list-cont2? x ys succ fail) (cond ((null? ys) (fail)) ((eq? x (car ys)) (succ)) (else (in-list-cont2? x (cdr ys) succ fail))))

We can similarly translate a tree search algorithm into CPS:

(define (in-tree? x tree) (cond ((pair? tree) (or (in-tree? x (car tree)) (in-tree? x (cdr tree)))) ((eq? x tree) #t) (else #f))) (define (in-tree-cont? x tree cont) (cond ((pair? tree) (in-tree-cont? x (car tree) (lambda (inleft) (if inleft (cont inleft) (in-tree-cont? x (cdr tree) cont))))) ((eq? x tree) (cont #t)) (else (cont #f)))) (define (in-tree-cont2? x tree succ fail) (cond ((pair? tree) (in-tree-cont? x (car tree) succ (lambda () (in-tree-cont? x (cdr tree) succ fail)))) ((eq? x tree) (succ)) (else (fail))))

The tree version is more interesting, because instead of just passing the continuation through, it builds up, by using anonymous lambdas for backtracking in case of a failure. The continuation thus forms a functional representation of a control stack.

At its core, the CPS based evaluator is simply an evaluator written in this style. This in itself is nothing extra-ordinary: every program can be translated (even fully automatically) into CPS form. The benefit is, that by having explicit access to the continuation of a program in the evaluator, we can implement new forms of control operators. The most prominent one is call-with-current-continuation.

Escape Continuations via call-with-current-continuation

When you enter an expression in the Read-Eval-Print Loop in DrRacket, the top-most continuation is something that expects a value, prints it, and asks for a new expression to evaluate. This is what happens when an expression gets evaluated. If you type a complicated expression, different continuations exists.

↓(+ 5 (/ 20 2))

I will be using using a down arrow (↓) to point to a location in a program, it is not part of the actual program text.

The continuation at ↓ in this program expects a value, and prints it to the REPL. Thus the result of evaluating (+ 5 (/ 20 2)) will be printed on the REPL.

(+ 5 ↓(/ 20 2))

The continuation at ↓ expects a value (which will be the result of evaluating (/ 20 2)), and adds the number five to it. It will then print this number to the REPL.

This is how continuations are used by the Scheme evaluator. However, in Scheme, the procedure call/cc (the abbreviated name of call-with-current-continuation) is used to get a first-class continuation. Just like procedures, continuations are first-class entities in Scheme (they can be assigned to variables, and passed as arguments to procedures).

(+ 5 ↓(call-with-current-continuation (lambda (cnt) (/ 20 2))))

call/cc will call the procedure given to it as argument, and pass the continuation as a value to that procedure. In other words, the anonymous procedure, created using lambda in this example, will receive the continuation (denoted using ↓) as its argument for cnt. In this example, it is not used.

Normally, the last evaluated expression will be used to generate the return value of a procedure application. However, we can "cheat" this system by making use of this first-class continuation value. The following example program introduces a procedure called foo that, in its body, calls cnt. When we pass foo to call-with-current-continuation, what value is returned by the last expression? What is printed?

(define (foo cnt) (display "hello") (cnt 10) (display "world") (/ 20 2)) (+ 5 (call-with-current-continuation foo)) ; --> ???

For brevity, I skip the definition of foo, and the evaluation of + and 5, and immediately go to the evaluation of (call-with-current-continuation foo).

The continuation around (call-with-current-continuation foo) is something that expects a value, and adds five to it. And then prints this value to the Read-Eval-Print Loop. This continuation is passed to foo. Thus its body will be evaluated in an extended environment where cnt is bound to that continuation.

During the evaluation of the body, the string "hello" is printed. Then (cnt 10) is evaluated. Since cnt is bound to a continuation, it will therefore pass its arguments as the value to that continuation. In other words, it will jump back to the ↓ in (+ 5 ↓(call-with-current-continuation foo)) and will therefore evaluate (+ 5 10), and print its result (15) to the Read-Eval-Print Loop. The rest of the body of foo is not evaluated: the string "world" is not evaluated, nor does it evaluate (and therefore, not even return) (/ 20 2).

Example: Tree Search

The following code shows the tree search example that uses Scheme's call/cc instead of

(define (in-tree-call/cc? x tree) (call-with-current-continuation (lambda (cont) (define (traverse t) (cond ((pair? t) (traverse (car t)) (traverse (cdr t))) ((eq? x t) (cont #t)))) (traverse tree) (cont #f))))

The way we used continuations in this Section is a restricted form: the procedures that we used with call/cc only invoked the continuations they were given, but did not store the continuation somewhere and did not return continuations as results. This restricted forms of continuations are called escape continuations. In the control stack analogy, invoking an escape continuation will reset (trim) the control stack to the state that it was in, when the continuation was created. Note however, the R5RS standard does not stipulate how (escape) continuations are to be implemented, only what their semantics should be.

General call/cc

Continuations can be stored in variables. In other words...

(define c #f) (+ 100 (call-with-current-continuation (lambda (cnt) (set! c cnt) 100))

will bound the variable c to a continuation that adds 100 to a given value, and prints it to the Read-Eval-Print Loop. It will also print 200 as the result of evaluating the procedure given to call-with-current-continuation is the number 100 (and $100 + 100 = 200$).

When we later encounter the following in the program (assuming that the variable c has not been modified).

(+ 100 (c 200))

The value 200 is given to that continuation: it will thus calculate $100 + 200 = 300$, and print that to the Read-Eval-Print Loop. Note that this value is not returned as the result of evaluating (c 200) inside (+ 100 (c 200)), as the continuation ↓ in (+ 100 ↓(c 200)) is simply discarded.

In the control stack analogy, call/cc will make a copy of the stack and when invoking a continuation, the current stack is discarded and replaced by the stored stack. Again, this is not necessarily how continuations are implemented.

Exercise: Predict what happens

Predict what happens in the following Scheme programs.

Program A:

(+ 1 (call-with-current-continuation (lambda (ignore) (+ 2 3))))

Program B:

(define c #f) (* 10 (call-with-current-continuation (lambda (cnt) (set! c cnt) 5))) ; -> output? (c 7) ; -> output? (+ (c 20) 50) ; -> output?

What happens when you put this program in a procedure, and then call this procedure?

Program C:

(define c #f) (define (loop a) (if (even? a) (c (- a)) (loop (+ a 1)))) (call-with-current-continuation (lambda (cnt) (set! c cnt) (display "init") (newline))) ; -> output? (c 100) ; -> output? (loop 101) ; -> output?

Example: Goto revisited

This is the definition of label and goto from the lectures. label simply returns the current continuation which we store in the variable start in the example.

(define (label) (call-with-current-continuation (lambda (cont) cont))) (define (goto cont) (cont cont)) (define (display-nats n) (define i 0) (define (loop) (define start (label)) (display i) (newline) (set! i (+ i 1)) (if (< i n) (goto start))) (loop)) (display-nats 10)

Example: Cooperative Multitasking

This is an example showing the implementation of a simple cooperative (aka non-pre-emptive) threading library, i.e. a thread is never interrupted and runs until it explicitly releases control.

The heart is a global list of threads that can be run:

(define readyList '())

Exiting a thread checks if there is any other thread waiting to be run. If so it causes the next thread to run, otherwise it calls the original exit which exits the whole environment.

(define exit ;; The original exit which we override. (let ((exit exit)) ;; The overriding function. (lambda () (if (not (null? readyList)) ;; There is another thread waiting to be run. So we run it. (let ((cont (car readyList))) (set! readyList (cdr readyList)) (cont '())) ;; Nothing left to run. (exit)))))

Takes a one argument function with a given argument and forks it off. The forked function's new thread will exit if/when the function ever exits.

(define (fork fn arg) (set! readyList (append readyList (list (lambda (x) (fn arg) (exit))))))

The yield function gives up control for the next thread waiting to be run and will only regain it when the continuation is called.

(define (yield) (call-with-current-continuation ;; Capture the continuation representing THIS call to yield (lambda (thisCont) ;; Stick it on the ready list (set! readyList (append readyList (list thisCont))) ;; Get the next thread, and start it running. (let ((cont (car readyList))) (set! readyList (cdr readyList)) ;; Run it. (cont '())))))