Coroutines for event-based programming

NEM 2008-08-26: In A brief introduction to closures and continuations for event-based programming I described a simple programming task which is very simple to write when interacting with a console or other synchronous device, but which becomes trickier to implement in an event-oriented manner. The difficulty is that we not only have to change the particular implementation of our software, but we also have to restructure the flow of control of the entire program to accommodate an event-based approach. I then discussed how various programming features, such as closures (which we (can) have), and continuations (which we don't) can help to improve this situation. In this article, I want to show how the experimental coroutine facilities provided in the 8.6 alphas can be used to address the same task. Hopefully this demonstrates a powerful example of what these facilities can achieve, whilst focussing attention on those areas that might need more thought.

As a recap, the original problem is to write a program that asks the user for two numbers and then displays their sum. The "spec" for the program is represented by this simple main routine, written in direct style:

proc main {} {
    set x [ask "First number:"]
    set y [ask "Second number:"]
    tell "Sum = [expr {$x + $y}]"
}

The task then is to implement suitable tell and ask procedures, ideally without having to alter the main routine at all. For a simple console application, this is straight-forward:

proc ask question {
    puts -nonewline "$question "
    flush stdout
    gets stdin
}
proc tell message { puts $message }
main ;# Works as expected

When we move to a Tk GUI implementation, however, things start to fall apart. The trouble is that Tk GUIs just don't work in this direct style; they work in an event-based style. In the above linked page, I show how to adapt the program to this new style, and then how to slowly move back to something resembling the simple direct program. I won't recap that here. I did however, hint at how continuations can be used to completely recapture the direct style program. In this page, I want to show how a similar result can be achieved using the coroutines that MS has provided for us. Indeed, the kind of coroutines implemented are roughly equivalent to a kind of one-shot continuation. Indeed, with the facilities in the 8.6 version of Tcl, our main can be exactly the same as the simple version above. All that needs to change is our implementation of tell and ask and a simple change to the way main is called. This is something of a holy grail of event-oriented programming, and says a lot for the power of the coroutine mechanism. Here's the new procedure implementations:

proc ask q {
    toplevel .ask
    pack [label .ask.l -text $q] [entry .ask.e]
    raise .ask; focus .ask.e
    bind .ask.e <Return> [format {
        set ans [.ask.e get]
        destroy .ask
        %s $ans
    } [info coroutine]]
    yield
}
proc tell msg { tk_messageBox -message $msg }

These are essentially the same as the callback versions from the previous page, but with a mysterious yield at the end of the ask procedure. To tie this all together, we implement a spawn command to launch the initial main coroutine:

proc spawn cmd {
    set k [gensym]
    coroutine $k $cmd
}
proc gensym {{prefix "::coroutine"}} {
    variable gensymid
    return $prefix[incr gensymid]
}

Finally, we can call our main:

spawn main

If you run this, you'll see that it does in fact work.

So what's actually going on here? Well, the trick is to make the main routine itself into a co-routine, so that it can be interrupted and resumed as events occur. The spawn procedure simply creates a unique coroutine that calls the main proc. The ask procedure then creates the GUI and uses this coroutine argument as the callback to be called when the user enters data. It then calls yield cause the main computation to suspend (and thus yielding back to the event loop). The event GUI then carries on until the user enters a number and hits Return. At this point, the coroutine is invoked, resuming the main computation and returning the result as the result of the yield. This then becomes the result of the ask procedure as if it had worked exactly like our original synchronous version. Voila!

Hopefully this is comprehensible. So, what conclusions/issues can we draw from this?

  • The proposed coroutine mechanism is very powerful, and meshes well with existing Tcl/Tk idioms.
  • In particular, this is a promising approach to taming event-based programming.
  • There is the need to generate unique names for the coroutines (not a massive burden).
  • We need a spawn to convert the main into a coroutine (again, not a massive burden).

Overall, an extremely interesting capability.


NEM 2009-03-05: Updated to current Tcl 8.6 status. Coroutines are now fully integrated into the core, as coroutine, yield, and info coroutine.

MS (2008-08-28) notes that [infoCoroutine] did not make to Tcl8.6a2, this code requires cvs HEAD to run. With a small modification to the helper procs it can be run in Tcl8.6a2 too:

 proc infoCoroutine {} {uplevel #1 {set name}}
 proc spawn cmd {
    set k [gensym]
    coroutine $k ::apply [list name $cmd] $k
 }

This exploits the fact that within a running coroutine #0 is as usual, #1 gives access to the coroutine's first level: in this case, to the local scope of the coroutine's defining lambda.


NEM Discussion welcome.

MS your wish is my command: HEAD now has tcl::unsupported::infoCoroutine that returns the fully qualified name of the currently executing coroutine. With this I think that the pesky $k can go. Too bad it didn't make it in time for Tcl8.6a2.

NEM Updated above to make use of the new facilities. Here is also a little ensemble wrapper around the unsupported facilities: (Note: the following code will clash with the actual 8.6 implementation, so don't use!)

# coroutine.tcl --
#
#       Ensemble wrapper around the coroutine facilities in Tcl 8.6
#
package require Tcl         8.6a2
package provide coroutine   1.0

namespace eval ::coroutine {
    namespace export create spawn yield current
    namespace ensemble create -map {
        create      ::tcl::unsupported::coroutine
        spawn       ::coroutine::spawn
        yield       ::tcl::unsupported::yield
        current     ::tcl::unsupported::infoCoroutine
    }
    variable gensymid 0
    
    # wrapper around [coroutine create] that generates a unique name.
    proc spawn {cmd args} {
        set id [gensym]
        coroutine create $id $cmd {*}$args
    }
    proc gensym {{prefix "coroutine"}} {
        variable gensymid
        return [namespace current]::$prefix[incr gensymid]
    }    
}

CMcC 2008Aug27 - I just had a cool idea for uniquely naming coroutines for fileevent handling - name the coroutines after the file handle. Those should be unique.

NEM Indeed. The really good thing about these coroutines is that they automatically clean up once the coroutine is "exhausted". Something like the coroutine spawn I provide above is really pretty much good enough already: the commands are created in a separate namespace, so should be free of clashes, and they are automatically deleted when no longer needed, so there is no garbage collection issues. It really works out very well.

CMcC one fileevents problem is that a socket server can generate file handles faster than you can clean up after a file has closed. This means that all your handlers can be reading/writing a socket which has the same file handle name as that they were created for, but which is actually a different connection.

If one uses the coroutine abstraction, and names fileevent handling coroutines after the file they are dedicated to, one will get an error at the point of coro creation, indicating that there's still a handler which could conceivably be trying to manipulate the socket which has now disappeared. The timely, simple detection of this, at a time when one has the new socket's name, and hence the handler's name, may make it possible to neatly avoid this problem.

Further reflection leads me to conclude that there's nothing inherent in tcl causing this race condition, that good socket hygeine would dictate that you fully process the closure of a socket before actually closing the socket handler. However, the naming convention suggested defensively detects the race condition however caused.

ferrieux Yes, the EOF condition doesn't instantly destroy the socket handle. Instead, the script has to detect the condition, and possibly decide to take action like close, at which point it is natural to get rid of any associated persistent things (like coroutines or array keys). So there is no race condition to begin with ;-)

NEM Example of CMcC's idea:

proc chaniter chan {     
  coroutine $chan ::apply {chan {
    yield ;# start-up
    while {[gets $chan line] >= 0} { yield $line }
    close $chan
    return -code break
  }} $chan
  return $chan
}
set in [chaniter [open $somefile]]
while 1 { puts [$in] }

Jaf (20080903) Am I being overly thick here, or why am I still not "getting it"?

I Just can't help thinking that a trace on the first variable (x) and one on the second (y), with the trace calling a proc yielding the result would do the job, just as effectively (??).

NEM But you can't implement that without adjusting the original "main" proc. This is the point of things like coroutines -- they don't expand the capabilities of the language, but just make certain styles of programming, and more importantly, certain styles of refactoring easier or more natural. See the discussion on a brief introduction to closures and continuations for event-based programming for more motivating background.

Jaf Let's see if I got it right: the "main" has been tried and proven working on a console type system, now we want to "transform" the application to a GUI-driven one with the minimum change in "program flow"? (I'm still a bit uneasy on this, so please correct if I'm wrong & sorry if I'm really overly thick :-)

NEM Exactly. Indeed, we might want to have both interfaces available, sharing common program logic. Closures, coroutines, and continuations, all increase the ability to shape the control flow around your logic, rather than the other way around.

jcw 20090419 - cool stuff (following copied from a brief email exchange with NEM):

How about a coroutine with the following structure:

        while {1} {
          {*}[yield]
        }

IOW, process the yield return as a command to evaluate in the context of the coroutine? That means the coroutine becomes an object to which you can send messages, right?

NEM Pretty much, yes. Try this:

  % coroutine obj apply {{} {
   set answer ""
   while 1 { set answer [eval [yield $answer]] }
  }}
  % obj { set a 1 }
  1
  % obj { incr a }
  2
  % set a
  can't read "a": no such variable

AM (21 april 2009) In other words: you create private persistent variables this way that can not be accessed from elsewhere!

NEM 2009-11-09: Exactly. In fact, with this technique you can create fully encapsulated objects, in which there is no way for code outside the coroutine to access any information from within the coroutine except that which is explicitly made available. This provides a lighter-weight sandboxing capability than a full interp, but with some of the same benefits. One use would be to implement an object-capability security system in which each object represents a capability to perform some set of actions (the methods it provides), and only those actions. For example, we can create a bank account object which provides deposit and balance methods, but doesn't allow withdrawals:

proc account {balance} {
    while 1 {
        lassign [yield $balance] method amount
        switch $method {
            deposit   { incr balance $amount }
            balance   {  }
        }
    }
}
coroutine acc account 100
acc { deposit 100 }
acc { withdraw 500 } ;# returns an error message

The point here is that code can now only call the deposit and balance methods, and it is impossible to break into the account and steal the money.


AM Here is my attempt at using coroutines: Discrete event modelling with coroutines