[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"
    exit
}
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}]"
    exit
}
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}]"
        exit
    } $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}]"
        exit
    }]
}]
======
----
======
# 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}]"
        exit
    }]
}]
# 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!
#
quit
======

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

<<categories>> Concept | Tutorial