Continuation examples (was Re: So, what the heck is a continuationanyway?)

[Eric Kidd <address@hidden>]

On Mon, 2001-12-10 at 15:39, Dan Sugalski wrote:
> Is the copying fully required, and does anything that happens after the 
> snapshot's taken affect the snapshot?

Here's my understanding of the semantics, down at the implementation
level.  This isn't an /efficient/ way to do things, but it should convey
the general idea.

Everybody, please correct me if I get this wrong. :-)

1) Allocate your "stack" frames on the heap, and chain them up through
their parents.

2) When saving a continuation, keep a pointer to the appropriate stack
frame (and some sort of program counter).

3) Don't destroy stack frames on exit.  Let the garbage collector figure
out when there are no outstanding continuations (or closures)
referencing a particular frame, and clean up the stack frames for you.

4) When a continuation is invoked, jump to the saved stack frame and PC.

In this scenario, there's only one copy of any particular stack frame,
but you can still jump back to a previous function call.

Note that this complicates life a bit--in addition to throwing /out of/
a function, you can also throw back /into/ it later, so you basically
need to implement some sort of try/setup/finally construct so you can
automatically acquire resources when jumping into a routine.  Twisted.

> For example, if I have:
> 
>     {
>        int i = 0;
>        make_continuation();
>        print i;
>        i = 3;
>     }
> 
> Will that print 0 or 3 when the continuation is invoked? And if I invoke 
> that continuation a second time will it print 0 or 3?

This will print '0' the first time through, and '3' thereafter (unless
I'm badly mistaken).

Continuations allow you to implement basically any known control
structure as a macro: exceptions, co-routines, generators, co-operative
threads, block-exit procedures (say, C's "return" as a first-class
function), and even GOTO.

Kent Pitman once showed me a profoundly evil bit of Scheme code.  Here's
a recreation I keep sitting in home directory:

((call-with-current-continuation
  (lambda (goto)
    (letrec ((start
	      (lambda ()
		(display "start")
		(newline)
		(goto next)))
	     (froz
	      (lambda ()
		(display "froz")
		(newline)
		(goto last)))
	     (next
	      (lambda ()
		(display "next")
		(newline)
		(goto froz)))
	     (last
	      (lambda ()
		(display "last")
		(newline)
		#f)))
      start))))

This fragment implements an honest-to-goodness GOTO in Scheme.  It uses
all the major Scheme features--continuations, lexical scoping, closures,
tail-calls and first class functions--all at once.  It's beautiful.  And
it's even more evil than my generator-in-C hack. :-)  Once you
understand it, you've got a good handle on most of Scheme's most
counter-intuitive features.

Yes, I'm going to leave deciphering this code as an exercise for the
reader.  (Hint: The continuation returns into a '(' ')' pair, so it
calls the argument passed to 'goto'.)

I've appended another neat continuation hack implementing Prolog-style
backtracking for Scheme.  (Yes, my home directory is really full of this
stuff.)

Continuations are terribly powerful; they let you build weird new
control structures in a user library.  But continuations aren't
free--they require some tricky stack handling and they constrain some
implementation decisions elsewhere.

Cheers,
Eric

;;; Indicate that the computation has failed, and that the program
;;; should try another path.  We rebind this variable as needed.
(define fail
  (lambda () (error "Program failed")))

;;; Choose an arbitrary value and return it, with backtracking.
;;; You are not expected to understand this.
(define (choose . all-choices)
  (let ((old-fail fail))
    (call-with-current-continuation
     (lambda (continuation)
       (define (try choices)
         (if (null? choices)
             (begin
               (set! fail old-fail)
               (fail))
             (begin
               (set! fail
                    (lambda () (continuation (try (cdr choices)))))
               (car choices))))
       (try all-choices)))))

;;; Find two numbers with a product of 15.
(let ((x (choose 1 3 5))
      (y (choose 1 5 9)))
  (for-each display `("Trying " ,x " and " ,y #\newline))
  (unless (= (* x y) 15)
    (fail))
  (for-each display `("Found " ,x " * " ,y " = 15" #\newline)))

;; Prints:
;; Trying 1 and 1
;; Trying 1 and 5
;; Trying 1 and 9
;; Trying 3 and 1
;; Trying 3 and 5
;; Found 3 * 5 = 15