A brief introduction to closures and continuations for event-based programming

NEM 2008-01-22: Another day, another overly long page title! Still, at least it will show up in searches for the relevant keywords. Anyway, I was trawling through some old material on my disk and came across this little file I wrote some time last year. It is an attempt to explain the basic concepts behind closures and continuations and why somebody programming in Tcl might find them useful. In particular, it shows applications to event-oriented programming. This is partly a little taster for people who may be unfamiliar with the notions, and partly an attempt to get the clever Tcl-elves into thinking about how such constructs might be best supported in some future Tcl 3000. Anyway, I hope you enjoy it. The article is presented as a heavily commented Tcl file which you can run directly with wish, although it does need 8.5. You also need the code from dictutils.

#               Closures, Continuations and Event-Based Programming
#               ===================================================
wm withdraw .
rename exit quit
proc ---- {} { vwait ::done }
proc exit {} { set ::done 1 } 
# This file has a quick look at event-based programming, as common in Tcl, and
# the sorts of programming constructs that can be used to make this style of
# programming more natural in certain cases.
# Suppose we wish to write a program that asks the user for two numbers and
# then prints their sum. This is a trivial task, that you would expect to
# accomplish with ease when starting a new language. Here is one way to
# achieve that task in Tcl:
chan configure stdout -buffering none
proc ask {question} {
    puts -nonewline "$question "
    gets stdin
proc tell message { puts $message }
set num1 [ask "First number:"]
set num2 [ask "Second number:"]
tell "Sum = [expr {$num1 + $num2}]"
# Easy enough. However, let us say we now have become bored with command-line
# interfaces and decide to recode our application using a fancy Tk GUI.
# Ideally, we'd just be able to redefine our ask and tell procedures to do the
# job. A naive first attempt might look like the following:
proc ask {question} {
    toplevel .ask
    pack [label .ask.l -text $question] [entry .ask.e]
proc tell message { tk_messageBox -message $message }
# The tell part seems fine, but how do we complete our ask procedure? We need
# to wait for the user to type some text before we can return the result.
# However, a Tk GUI is event-driven rather than synchronous (like the
# console), so we have to wait for some event. We could use 'vwait' to wait
# for the event inside 'ask', but this is generally considered bad style, as
# vwait reenters the event loop, which can lead to problems. A better method
# would be to pass a callback to the ask method which can be invoked with the
# result:
proc ask {question callback} {
    toplevel .ask
    pack [label .ask.l -text $question] [entry .ask.e]
    raise .ask; focus .ask.e
    bind .ask.e <Return> [format {
        set ans [.ask.e get]
        destroy .ask
        %s $ans
    } $callback]
proc callback ans {
    tell "You typed: $ans"
ask "Type a message:" callback
# This works ok for this simple program, but things get messier for our
# original program:
proc cb1 a {
    ask "Second number:" [list cb2 $a]
proc cb2 {a b} {
    tell "Sum = [expr {$a + $b}]"
ask "First number:" cb1
# The logic here is split up and we have to jump around the program to work
# out what is going on. This sort of code is fairly typical when trying to
# accomplish some essentially linear sequence of steps in an event-based
# manner. (It is worth mentioning here that I have deliberately picked such a
# task. There are other tasks for which an event-based approach is perfectly
# natural). We can make things slightly easier using anonymous procedures in
# 8.5:
proc lambda {params body args} { linsert $args 0 apply [list $params $body] }
ask "First number:" [lambda a {
    ask "Second number:" [lambda {a b} {
        tell "Sum = [expr {$a + $b}]"
    } $a]
# This version now starts to look a little more like our original version, and
# should be a little clearer to follow. However, there is still a certain
# clumsiness to it: that little $a tacked on the end, for instance. The reason
# that is there is so that it gets passed to the second (inner) callback,
# otherwise it wouldn't be visible. Wouldn't it be nice if the inner callback
# had access to $a and any other variables defined in enclosing scopes
# automatically? This is what lexical closures achieve. A closure is simply a
# procedure together with a "captured" variable scope. We can implement simple
# closures using dictionaries and Tcl's variable introspection capabilities.
# Here we borrow the code from the dictutils page:
source dictutils.tcl
proc closure {params body args} {
    set env [dictutils capture 1 $params] ;# capture enclosing variable scope
    linsert $args 0 closure:apply $env [list $params $body]
proc closure:apply {env func args} {
    # Restore the scope and invoke the procedure
    dictutils apply env $func {*}$args
# This allows us to write the slightly improved version:
ask "First number:" [closure a {
    ask "Second number:" [closure b {
        tell "Sum = [expr {$a + $b}]"
# The structure of this program is beginning to resemble our original program
# more and more. However, we have still had to convert the program in order to
# achieve this. We can write our original console-based program in the new
# form as well:
proc ask {question callback} {
    puts -nonewline "$question "
    {*}$callback [gets stdin]
proc tell message { puts $message }
ask "First number:" [closure a {
    ask "Second number:" [closure b {
        tell "Sum = [expr {$a + $b}]"
# Note that the two programs are now identical, and it is just the
# implementation of tell and ask that has to change. This gives us a form of
# writing programs that allows us to switch between synchronous and
# asynchronous (event-based) implementations with ease. However, it is a bit
# of a chore to have to write your code in this style, and not very pleasing
# to read. Perhaps we can find a way to automate the translation from the
# simpler "direct"-style into this new style? Such a transformation does
# actually exist. The form we have developed is what is known as
# Continuation-Passing Style (CPS), because instead of calling a procedure and
# returning a value (direct style), we instead call a procedure and pass it a
# "continuation" -- i.e., the rest of our program -- and it invokes that with
# the result. A continuation is simply a closure that represents the
# computations we have still to do. In general, any expression of the form:
#   dosomething (somefunction args...)
# Can be transformed into an equivalent expression in CPS:
#   somefunction args... (\x -> dosomething x)
# It is possible to write an interpreter such that an entire program is
# transformed in this manner. In this way, instead of maintaining a stack of
# function calls we instead maintain a "current continuation" that represents
# the rest of the program and pass this as an extra (hidden) argument to every
# procedure. Some languages, such as Scheme, expose this "current
# continuation" through a mechanism like (call-with-current-continuation).
# This command passes the current continuation to the named procedure as an
# actual (non-hidden) argument so that it can be used. This enables the
# program to be written in direct-style and yet work as if it was written in
# continuation-passing style. For instance, supposing we had a call/cc command
# in Tcl, we could write:
proc call/cc {args} {return 0} ;# dummy
set a [call/cc ask "First number:"]
set b [call/cc ask "Second number:"]
puts "Sum = [expr {$a + $b}]"
# What call/cc does is pass the whole of the rest of the program as a
# continuation argument to ask. In other words, the code becomes:
ask "First number:" [closure _ {
    set a $_
    ask "Second number:" [closure _ {
        set b $_
        puts "Sum = [expr {$a + $b}]"
# where each closure represents the current continuation at that point. Tcl
# does not have this facility and it is impossible to fake it, without writing
# an entire meta-circular interpreter for Tcl in Tcl itself. For now, the best
# we can hope to achieve is to apply some syntactic sugar to the creation of
# closures. Here is an example:
proc let {var = args} {
    set body [lindex $args end]
    set cmd [lrange $args 0 end-2]
    set env [dictutils capture 1 $var]
    set fun [list closure:apply $env [list $var $body]]
    uplevel 1 [lappend cmd $fun]
let x = ask "First number:" in {
    let y = ask "Second number:" in {
        tell "Sum = [expr {$x + $y}]"
# We still end up with some nested code, but for many applications this will
# probably be bearable.
# To summarise, we can conclude the following lessons:
#   * Swapping from synchronous to event-based execution is non-trivial;
#   * Using continuation-passing style consistently can make it easier to swap
#     between implementation strategies;
#   * Closures make the use of CPS somewhat easier to bear;
#   * Call-with-current-continuation makes this even simpler;
#   * Adding support for real closures (that capture arrays and variable
#     traces) would be really cool!
#   * So would adding call/cc or some equivalent mechanism!

See coroutines for event-based programming for an example of how to achieve this using the experimental coroutine facilities in Tcl 8.6.