Skip to content

Yaaec (Yet another attempt to explain continuations)!

July 22, 2009
It seems blogs related to Scheme or Ruby contains at least one attempt to demystify continuations. Here is mine.
It is assumed that the reader is familiar with basic concepts like expressions and their evaluation, closures etc.
A continuation is a point in an expression being evaluated, frozen in time. Consider the following code:
</div>
<div id="_mcePaste" style="position: absolute; left: -10000px; top: 0px; width: 1px; height: 1px; overflow-x: hidden; overflow-y: hidden;"><span style="font-family: Georgia; line-height: 19px; white-space: normal; font-size: 13px; ">(+ 2 3) ;; => 5<span style="font-family: Consolas; line-height: 18px; font-size: 12px; white-space: pre; ">
This expression can be split into three points: +, 2 and 3. We can freeze the program at any of these points and store it away. This is accomplished with the procedure call-with-current-continuation or call/cc. The name itself gives a hint as to what it does. call/cc takes a procedure as argument and evaluates it. The evaluated procedure is passed a closure which contains the expression upto where call/cc was called. Let us see call/cc in action by freezing the point where the value 3 is supplied:
</pre>
</div>
<div id="_mcePaste" style="position: absolute; left: -10000px; top: 0px; width: 1px; height: 1px; overflow-x: hidden; overflow-y: hidden;">(define frozen #f)</div>
<div id="_mcePaste" style="position: absolute; left: -10000px; top: 0px; width: 1px; height: 1px; overflow-x: hidden; overflow-y: hidden;">(+ 2 (call/cc (lambda (k) (set! frozen k) 3))) ;; => 5</div>
<div id="_mcePaste" style="position: absolute; left: -10000px; top: 0px; width: 1px; height: 1px; overflow-x: hidden; overflow-y: hidden;">
<pre style="font: normal normal normal 12px/18px Consolas, Monaco, 'Courier New', Courier, monospace;">
The current continuation is wrapped into the procedure object ”k”. We store this in the global variable ”frozen” and return the value 3 as required by the original expression. So, when it is evaluated the first time, the result will be 5.  An easy way to understand continuations is to look at the expression as consisting of the procedure ‘+’ and two holes:

  (+ [] [])  

The first hole is filled by the value 2:

  (+ 2 [])  

The second hole is filled by whatever ”call/cc” evaluates to (in this case 3):

  (+ 2 3) ;; => 5  

The expression with the hole is stored in the continuation object. Anytime in the future, we can reuse this object like this:

  (frozen 10) ;; => 12  

What really happened when we evaluated ”frozen”? The expression (+ 2 []) was resurrected and the hole was filled by the value returned by ”frozen”. Thus the expression becomes (+ 2 10) and gets evaluated to 12.  If you are a C programmer, continuations could be understood in the context of the ”setjmp” and ”longjmp” functions. While C allows you to jump back up the stack, ”call/cc” allows moving in any direction. This is achieved by saving the entire stack at the point where ”call/cc” was called. In our example, ”frozen” is actually a closure that stores the stack up to the point where ”call/cc” was evaluated.  One common use of continuations is in emulating keywords that provide ‘escape’ from a context. In the C family of languages these keywords are ”return”, ”break” and ”continue”. Let us see how we can emulate one of them – the ”return” keyword:

  ;; This procedure searches a list for a value. ;; If the value is found, the procedure exits by ;; ''returning'' that value.  (define (find-element list-to-search is?)   (call/cc    (lambda (return)      (for element in list-to-search <span style="white-space: pre;"> </span> (if (is? element) <span style="white-space: pre;"> </span> (return element)))      #f)))  ;; Test  (define (is-1900? e)   (= e 1900))  (find-element (list 1890 2009 1900 2001) is-1900?) ;; => 1900 (find-element (list 1890 2009 1901 2001) is-1900?) ;; => #f  

The definition of ”find-element” can be visualized as:

  (define (find-element list-to-search is?) <span style="white-space: pre;"> </span>[])  

When the searched element is found, it is passed as the argument of ”return”, which actually represents the point where the evaluation of the body of ”find-element” starts. Each time ”find-element” is evaluated, the hole is filled with either #f or the argument passed to the inner call to ”return”. This creates an illusion that ”find-element” actually ”returns” a value, while in effect the entire body of ”find-element” (the hole) is getting replaced (or filled) by the value to which the continuation procedure evaluates.  There is a built-in form that makes it easy to create escape continuations called ”let/ec”. Here is the ”find-element” procedure re-written using ”let/ec”:

  (define (find-element list-to-search is?)   (let/ec return <span style="white-space: pre;"> </span> (for element in list-to-search <span style="white-space: pre;"> </span> (if (is? element) <span style="white-space: pre;"> </span> (return element))) <span style="white-space: pre;"> </span> #f))  

We can also use ”let/ec” to emulate the ”break” keyword, which can be used to terminate a loop prematurely:

  (define i 0)  ;; This loop prints up to 5 ;; and breaks. (let/ec break <span style="white-space: pre;"> </span>(while (< i 10) <span style="white-space: pre;"> </span> (printf "~a~n" i) <span style="white-space: pre;"> </span> (if (= i 5) <span style="white-space: pre;"> </span> (break #f)) <span style="white-space: pre;"> </span> (set! i (add1 i))))  

Continuations find use in implementing features like exception handling, green threads, co-routines etc. Most of these are already taken care of by abstractions built into Spark, so the programmer is saved from directly dealing with continuations. But understanding how continuations work is important because it can be used to provide intuitive solutions to certain kind of problems.  Some links that provide more information on continuations:  1. [http://community.schemewiki.org/?call-with-current-continuation] 2. [http://en.wikipedia.org/wiki/Continuation] 3. [http://www.ps.uni-sb.de/~duchier/python/continuations.html] (Uses Python) 4. [http://www.ibm.com/developerworks/library/j-contin.html] (Uses Java)

Here is my short, simple explanation of continuations. The code examples are in Scheme.

It is assumed that the reader is familiar with basic concepts like expressions and their evaluation, closures etc.

A continuation is a point in an expression being evaluated, frozen in time. Consider the following code:


(+ 2 3) ;; => 5

This expression can be split into three points: +, 2 and 3. We can freeze the program at any of these points and store it away. This is accomplished with the procedure call-with-current-continuation or call/cc. The name itself gives a hint as to what it does. call/cc takes a procedure as argument and evaluates it. The evaluated procedure is passed a closure which contains the expression up to where call/cc was called. Let us see call/cc in action by freezing the point where the value 3 is supplied:


(define frozen #f)

(+ 2 (call/cc (lambda (k) (set! frozen k) 3))) ;; => 5

The current continuation is wrapped into the procedure object k. We store this in the global variable frozen and return the value 3 as required by the original expression. So, when it is evaluated the first time, the result will be 5.

An easy way to understand continuations is to look at the expression as consisting of the procedure ‘+’ and two holes:

  (+ [] [])  

The first hole is filled by the value 2:

  (+ 2 [])  

The second hole is filled by whatever call/cc evaluates to (in this case 3):

  (+ 2 3) ;; => 5  

The expression with the hole is stored in the continuation object. Anytime in the future, we can reuse this object like this:

  (frozen 10) ;; => 12  

What happened when the above expression was evaluated? The expression (+ 2 []) was resurrected and the hole was filled by the value returned by frozen. Thus the expression becomes (+ 2 10) and gets evaluated to 12.

If you are a C programmer, continuations could be understood in the context of the setjmp and longjmp functions. While C allows you to jump back up the stack, call/cc allows moving in any direction. This is achieved by saving the entire stack at the point where call/cc was called. In our example, frozen is actually a closure that stores the stack up to the point where call/cc was evaluated.

One common use of continuations is in emulating keywords that provide ‘escape’ from a context. In the C family of languages these keywords are return, break and continue. Let us see how we can emulate one of them – the return keyword:

  
(define (find-element list-to-search is?)
  (call/cc
   (lambda (return)
     (for element in list-to-search
	  (if (is? element)
	      (return element)))
     #f)))

;; Test

(define (is-1900? e)
  (= e 1900))

(find-element (list 1890 2009 1900 2001) is-1900?) ;; => 1900
(find-element (list 1890 2009 1901 2001) is-1900?) ;; => #f

The definition of find-element can be visualized as:

  
(define (find-element list-to-search is?)
      [])  

When the searched element is found, it is passed as the argument of return, which actually represents the point where the evaluation of the body of find-element starts. Each time find-element is evaluated, the hole is filled with either #f or the argument passed to the inner call to return. This creates an illusion that find-element actually returns a value, while in effect the entire body of find-element (the hole) is getting replaced (or filled) by the value to which the continuation procedure evaluates.  There is a built-in form that makes it easy to create escape continuations called let/ec. Here is the find-element procedure re-written using let/ec:

 
(define (find-element list-to-search is?)
  (let/ec return
	  (for element in list-to-search
	       (if (is? element)
		   (return element)))
	  #f))
 

We can also use let/ec to emulate the break keyword, which can be used to terminate a loop prematurely:

;; This loop prints up to 5
;; and breaks.
;; Note: while is a special form in Spark-Scheme.
(define i 0)
(let/ec break
(while (< i 10) (printf "~a~n" i) (if (= i 5) (break #f)) (set! i (add1 i)))) [/sourcecode] Continuations find use in implementing features like exception handling, green threads, co-routines etc. Most of these are already taken care of by abstractions built into Spark, so the programmer is saved from directly dealing with continuations. But understanding how continuations work is important because it can be used to provide intuitive solutions to certain kind of problems. Links and references:

  1. http://community.schemewiki.org/?call-with-current-continuation
  2. http://en.wikipedia.org/wiki/Continuation
  3. http://www.ps.uni-sb.de/~duchier/python/continuations.html (Examples in Python)
  4. http://www.ibm.com/developerworks/library/j-contin.html (Examples in Java)
Advertisements
4 Comments leave one →
  1. aaronla permalink
    July 28, 2009 6:20 am

    Hi, I am generally a fan of the “box” approach used in teaching continuations you use here, I think it’s a great way to visualize them.

    However, there is a small bug in your first example. Sure enough, if you invoke (frozen 10), the repl will print 12. But if you invoke (+ 1 (frozen 10)), it will _again_ print 12, not 13. “frozen” doesn’t represent (+ 2 []), but it represents _all_ of the program state up the call stack, including the fact that you entered it at the repl — invoking “frozen” could even lead to _undefining_ things you defined after setting “frozen”, because you invoked a continuation that captured the REPL at an earlier point in time.

    Here’s the repro in SISC:

    $> sisc
    SISC (1.16.6)
    #;> (define call/cc call-with-current-continuation)
    #;> (define frozen #f)
    #;> (+ 2 (call/cc (lambda (k) (set! frozen k) 3)))
    5
    #;> (frozen 10)
    12
    #;> (+ 1 (frozen 10))
    12
    #;>
    

    I covered this a bit here: http://bit.ly/jOPKU . I’ve since learned about delimited continuations in PLT Scheme, and they may also be an interesting read — http://bit.ly/14kufm .

    • vijaymathew permalink*
      July 28, 2009 12:25 pm

      Hello Aaron,

      Thanks for reading my blog and posting comments. I agree with what you said. But I think you haven’t read the whole article. I explain later that a continuation actually represents the call stack.

      Thanks,

      — Vijay

  2. vijaymathew permalink*
    July 30, 2009 5:37 am

    This post was redditted: http://www.reddit.com/r/programming/search?q=Yaaec.

Trackbacks

  1. Another explanation of continuations | Wisdom and Wonder

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: