Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.
Sometimes continuations can be too powerful for the task at hand. A continuation will capture the complete rest of the computation when sometimes you only want a portion of that computation. When calling a continuation, that call will never return since we are effectively replacing the current call stack with that of the continuation.
An example of where this can cause problems is demonstrated here, using the Scheme programming language. This 'bad' example will capture and store the current continuation and then attempt to call that continuation from within another function. Since the call to a continuation will never return the result can sometimes be non obvious.
The function that saves the continuation is:
;; Define a variable to hold the saved continuation
(define temp-cont #f)
(define (bad-example1)
(call/cc (lambda (k) (set! temp-cont k)))
(display "Exiting bad-example1\n"))
This function, when called will store the current continuation in a variable, 'temp-cont' and display a message. Calling this saved continuation will result in the message 'Exiting bad-example1' being displayed:
(bad-example1)
;=> Exiting bad-example1
(temp-cont #f)
;=> Exiting bad-example1
(temp-cont #f)
;=> Exiting bad-example1
What is non-obvious in this example is that when the continuation 'temp-cont' is called control is not returned back from that call. Instead the callstack of the continuation replaces the existing callstack. This cannot be seen from the simple interaction above, but becomes obvious when a call to that continuation is embedded inside other code:
(define (use-bad-example1)
(temp-cont #f)
(display "Exiting use-bad-example1\n"))
With this function we may naievely expect that 'Exiting bad-example1' will be displayed followed by 'Exiting use-bad-example1'. This may be what we want, but it is not what will occur. The 'temp-cont' call will not return and we will instead be returned back to the top-level loop as that is included in the continuation that was captured:
(bad-example1)
;=> Exiting bad-example1
(use-bad-example1)
;=> Exiting bad-example1
This situation can occur in the practical use of continuations quite commonly. For example, in the use of continuations in a continuation based web server we want to capture the current continuation, display the HTML output to the user, and then return, waiting for the next user request. When that request occurs we need to call the previously captured continuation but keep within our current call stack.
A workaround for this problem is to capture the current continuation before calling the saved one. That saved one will do its stuff and then call the continuation we just captured to return back to the correct call stack:
(define (workaround-example1)
(let ((go-back-to (call/cc (lambda (k) (set! temp-cont k) #f))))
(display "Exiting workaround-example1\n")
(when go-back-to
(go-back-to #f))))
Here we save the current continuation. When that continuation is called the result will be stored in the 'go-back-to' local variable. The message 'Exiting workaround-example1' is displayed and if 'go-back-to' has a value, it is called. This will usually be the continuation to resume. Here's how it is used:
(workaround-example1)
;=> Exiting workaround-example1
(define (use-workaround-example1)
(call/cc
(lambda (k)
(temp-cont k)))
(display "Exiting use-workaround-example1\n"))
(use-workaround-example1)
;=> Exiting workaround-example1
Exiting use-workaround-example1
The source code for the 'splitter' operator is available in splitter.scm and was obtained from Christian Queinnec's PCALL code. A paper by Christian Queinnec and Bernard Serpette describes the motivation behind and the implementation of 'splitter': A Dynamic Extent Control Operator for Partial Continuations
In the previous example we've effectively called the continuation and then returned back to the caller of that continuation. What we really want to do is capture a 'partial continuation' or 'subcontinuation'. That is, not the entire continuation but a section of it and then return back to the caller.
The 'splitter' operator mentioned above implements exactly that. It marks the point at which a continuation should be captured up to, instead of the entire continuation. A 'partial continuation' can then be reified up to this point. Here is the same example above, implemented with 'splitter':
(define (good-example1)
(splitter
(lambda (mark)
(call/pc mark (lambda (pk) (set! temp-cont pk)))
(display "Exiting good-example1\n"))))
A call to 'splitter' will execute the lambda function passed to it, giving that function a 'mark' object. This 'mark' object is used to identify the point in the current continuation where a request for a partial continuation will capture up to. 'splitter' can be nested with different 'mark' objects identifying the requested point.
The first thing we do is reify a 'partial continuation' with the 'call/pc' function. We pass 'call/pc' the mark that we want the partial continuation to start at. The actual partial continuation (in the 'pk' variable above) can be stored and called exactly like a full continuation. So the 'pk' partial continuation function above only captures a continuation up to the 'splitter' call. It is effectively the same as the following function:
(define (pk-is-the-same-as value)
(display "Exiting good-example1\n"))
Usage of the partial continuation looks and works like our workaround example previously:
(good-example1)
;=> Exiting good-example1
(define (use-good-example1)
(temp-cont #f)
(display "Exiting use-good-example1\n"))
(use-good-example1)
;=>Exiting good-example1
Exiting use-good-example1
A 'fake' continuation based web framework is shown below. This is a 'fake' framework in that it works from the REPL. Web pages are text displayed to the console and the 'URL' to continue that the user would normally click on is printed in that text. To simulate a user click, from the REPL, the function 'click-web-url', passing it the number of the URL, will resume as if an URL had been clicked. While simple it demonstrates the basic operation of a full continuation based web framework.
The framework uses the workaround method described above to return to the caller of the continuation. It is later modifed to use the 'splitter' operator and shows an implementation using partial continuations.
In the description of the framework I assume the reader is familiar with continuation based web frameworks.
The first thing we need is to allow associating a continuation with an URL and retrieving the continuation given an URL:
(define url-counter 0)
(define continuations (make-vector 1000))
(define (url->continuation num)
(vector-ref continuations num))
(define (continuation->url k)
(let ((counter url-counter))
(vector-set! continuations counter k)
(set! url-counter (+ 1 url-counter))
counter))
We simply store the continuations in a fixed size vector. The 'URL' is the index into that vector. A counter is kept and incremented whenever a continuation is stored in the vector.
A variable 'exit-continuation' is used to hold the 'continuation to return to'. This is the 'go-back-to' continuation from the workaround example presented previously:
(define exit-continuation #f)
The function that resumes an URL first captures the 'exit-continuation', and calls the continuation associated with the requested URL. That continuation will eventually call the 'exit-continuation' returning back to our current continuation:
(define (click-web-url url)
(call/cc
(lambda (exit)
(set! exit-continuation exit)
((url->continuation url) #f)))
(display "Exiting click-web-url\n"))
The 'show' function is used to display a page to the user and return. When the user requests the URL on that page, computation is resumed from the show call. 'show' is passed a function that accepts a single argument, the URL to display in the page:
(define (show page-function)
(call/cc
(lambda (k)
(let ((url (continuation->url k)))
(page-function url)
(exit-continuation #f))))
(display "User returned from url...\n"))
When the page is shown we call the exit-continuation to return back to our caller. When the page is resumed via calling the continuation associated with the URL the message 'User returned...' will be displayed. An example of a couple of show calls is:
(define (simple-web-example1)
(show
(lambda (url)
(display "Click Url to continue: ")
(display url)
(newline)))
(display "After first show\n")
(show
(lambda (url)
(display "Click another url to continue: ")
(display url)
(newline)))
(display "After second show\n"))
A function to 'kick-off' a 'web application' in this framework is:
(define (start-web-example thunk)
(click-web-url
(continuation->url (lambda (ignore) (thunk)))))
The simple 'fake' framework is now complete. An example interaction:
;; Start the initial web application
(start-web-example simple-web-example1)
;=> Click Url to continue: 1
Exiting click-web-url
;; 'Click' on the given URL
(click-web-url 1)
;=> User returned from url...
After first show
Click another url to continue: 2
Exiting click-web-url
;; Click on the next URL
(click-web-url 2)
;=> User returned from url...
After second show
Exiting click-web-url
;; Resume an existing URL (eg. returning to a bookmark)
(click-web-url 1)
;=> User returned from url...
After first show
Click another url to continue: 3
Exiting click-web-url
The 'fake' framework demonstrates the basic implementation of a continuation based web framework. The following code will change the framework to use partial continuations via the 'splitter' operator.
The changes to the previous framework to get it to use 'splitter' are:
;; Instead of storing an 'exit-continuation' we need to
;; store the current splitter mark.
(define current-mark #f)
;; Capture the partial continuation that we will
;; resume when the URL is acessed. Use the 'abort'
;; splitter operator to abort out of the current
;; marked splitter block.
(define (show page-function)
(call/pc
current-mark
(lambda (pk)
(let ((url (continuation->url pk)))
(page-function url)
(abort current-mark (lambda () #f)))))
(display "User returned from url...\n"))
;; Use 'splitter' to limit the extent of the
;; partial continuation that is captured.
(define (click-web-url url)
(splitter
(lambda (mark)
(set! current-mark mark)
((url->continuation url) mark)))
(display "Exiting click-web-url\n"))
Given these changes the web framework should work exactly as before. But instead of a full continuation being captured the much smaller partial continuation is used instead.
Notice that we had to store the 'current-mark' to identify what 'splitter' call limits the partial continuation. We also have to call 'abort' to abort out of the splitter code. This results in code which looks very similar to our 'workaround' code using 'exit-continuation' so we don't really gain any advantages in terms of the actual code written.
The main reason for this is splitter's need for the 'mark' and the fact that it doesn't implicitly abort if the partial continuation is not called. Other partial continuation operators behave differently in this area and can result in simplified code. The trade-off is not being able to nest calls. A useful paper that discusses the different control operators is A Library of High Level Control Operators.
I used the following papers to learn about partial continuations and alternative control operators.