Continuations

From CodeCodex

In computer science, a continuation is a generalization of the concept of point of control in a program. Think of it as a program counter value combined with a current-environment pointer. A continuation can be saved at any point, representing the current position in the control flow of the program, and then resumed at any time thereafter, to jump back to the same point. The same continuation can be resumed any number of times. Continuations can be used to express any form of control construct, from basic looping up to coroutines—except gotos.

Contents

Scheme

In Scheme, call-with-current-continuation is a function that invokes a specified function, passing it a continuation, in the form of a function of one argument that, if invoked, resumes execution immediately following the call-with-current-continuation call, returning whatever value was passed to the continuation. As a very simple, even trivial, starting example, the expression

    (call-with-current-continuation
        (lambda (return)
            (return 99)
        ) ; lambda
    ) ; callcc

returns the value 99.

A Simple Loop Construct

As a slightly more elaborate example, here is a definition of a loop construct that repeats forever until the corresponding break function is called. The user gets to choose their own name for the break function, allowing distinct names to be used when loops occur within loops:

    (require 'macro)

    (define-syntax loop
        (syntax-rules ()
            (
                (loop ?break ?body ...)
                (call-with-current-continuation
                    (lambda (getout)
                        (define (?break) (getout (begin))) ; returns #<unspecified>
                        (define (repeat) ()) ; dummy def replaced below
                        (call-with-current-continuation
                            (lambda (here-again)
                                (set! repeat (lambda (x) (here-again x)))
                            ) ; lambda
                        ) ; callcc
                        ?body ...
                        (repeat ())
                    ) ; lambda
                ) ; callcc
            )
        ) ; syntax-rules
    ) ; define-syntax

and here is an example use of this construct, repeatedly prompting the user for a password until the correct entry is made:

    (define password "")
    (loop break
        (display "password: ")
        (set! password (read-line))
        (if (equal? password "password")
            (begin
                (display "password accepted\n")
                (break)
            ) ; begin
        ) ; if
        (display "invalid password entry\n")
    ) ; loop

Piped Coroutines

Probably the most elaborate use of continuations is in the implementation of coroutines, which are like threads but are non-preemptive—control has to be explicitly passed.

Here is a definition of a routine called pipe, which is invoked with a producer and a consumer function as arguments. The producer generates objects one at a time, which are passed in turn to the consumer. Execution ends when the producer terminates.

The way it works is by switching between continuations, one running the producer and the other running the consumer thread. The top-level variable passer contains the continuation that is not currently running; a switch occurs by exchanging this value with a new continuation for the current thread, and then passing control to the previous value.

    (define (pipe producer consumer)
    ;+
    ; where producer and consumer are functions of one argument.
    ; producer will be invoked with function of one argument, which
    ; each time it is invoked passes its argument value to consumer.
    ; consumer will be invoked with a function of no arguments,
    ; which each time it is invoked returns a value passed from producer.
    ;-
        (define passer ()) ; initial dummy value replaced below
        (define (produce val)
            (call-with-current-continuation
                (lambda (resume)
                    (define prev-passer passer)
                    (set! passer resume)
                    (prev-passer val)
                ) ; lambda
            ) ; callcc
        ) ; define produce
        (define (consume)
            (call-with-current-continuation
                (lambda (resume)
                    (define prev-passer passer)
                    (set! passer resume)
                    (prev-passer (begin))
                ) ; lambda
            ) ; callcc
        ) ; define consume
        (call-with-current-continuation ; start consumer first, run until it suspends on first consume call
            (lambda (resume)
                (set! passer resume)
                (consumer consume)
            ) ; lambda
        ) ; callcc
        (producer produce)
    ) ; define pipe

And here is an example use:

    (pipe
        (lambda (produce) ; producer
            (display "start producer\n")
            (for-each
                (lambda (item)
                    (display "producing ") (write item) (newline)
                    (produce item)
                ) ; lambda
                (list 3 2 1)
            ) ; for-each
            (display "stop producer\n")
        ) ; lambda
        (lambda (consume) ; consumer
            (define val ())
            (display "start consumer\n")
            (let repeat ()
                (display "consuming\n")
                (set! val (consume))
                (display "got ") (write val) (newline)
                (repeat)
            ) ; let
            (display "stop consumer\n")
        ) ; lambda
    ) ; pipe

which, when run, produces the following output:

start consumer
consuming
start producer
producing 3
got 3
consuming
producing 2
got 2
consuming
producing 1
got 1
consuming
stop producer

Exercise: as written above, the consumer is expected to run forever, with everything only terminating when the producer does. What happens if the consumer terminates before the producer? How would you modify the pipe function to handle this correctly?

Why Coroutines?

Why would you use coroutines/continuations at all, and not full preemptive threads, which are a standard feature of OSes nowadays? There are significant reasons:

  • Coroutines still have lower overheads.
  • Threads are hard to use correctly; the default “shared-everything” approach tends to lead to bugs. Careful locking is required to avoid race conditions, which can be very hard to test for.

Of course, preemptive threads can take advantage of multiple CPU cores, which coroutines cannot. But in this case you can also use separate preemptive processes which, with their default “shared-nothing” approach, are usually easier to debug.