coroutine

coroutine, a built-in Tcl command, creates a new coroutine context and an associated command.

Synopsis

coroutine name cmd ?arg ...?

Description

coroutine creates a coroutine context and an associated coroutine command named name. It then evaluates cmd in the coroutine context, passing it any supplied arg values. If at any point during the evaluation of cmd yield or yieldto is called, the coroutine context is interrupted, the value of yield or yieldto is returned to the caller. The next time name is called, the coroutine context resumes at that same yield or yieldto call. If cmd returns, the coroutine context is deleted and name is also deleted.

cmd is the entry point to the coroutine context, but the coroutine context itself consists of the entire execution stack that began with the evaluation of cmd. Because an execution stack persists across calls into the coroutine context, a coroutine can be used to model objects, generators, actors, and other agents in concurrent systems.

From its own perspective, a coroutine isn't doing anything particularly special. It just calls a command named yield or yieldto, which, like any other command returns a value. The fact that in the meantime, control is transferred off somewhere else and eventually returns, is a property of the system that the programmer can then take advantage of. Because a coroutine must itself yield, it implements non-preemptive multitasking. No mechanism is provided for an external event to preemptively interrupt the evaluation of a coroutine. Coroutines are entirely synchronous. At any given moment only one routine has control of its interpreter. That said, a coroutine used in conjunction with asynchronous mechanisms can be a nice approach. For example, a coroutine could be used in the handler for a channel event.

Coroutines can be used to invert the traditional callback style. For example, without coroutines, something like fileutil::traverse that walks a filesystem hierarchy uses callbacks to process the files it encounters, making the traverser the client and the callback the server. A coroutine would instead yield a pathname each time it was called, making the caller the client, and the traverser the server.

yieldto allows peer-to-peer style, with coroutines yielding to each other.

Timeline

Coroutines were introduced in Tcl8.6. For a period these commands resided in the tcl::unsupported namespace, but are now full-fledged citizens and an important tool in any Tcler's kit.

NRE made the implementation of coroutines possible.

MS added yieldto as Tcl 8.6 was about to be released, when it became clear that yieldto was a more general treatment than yieldm.

See Also

Core commands

yield
exit the current coroutine context, which continues to exist, by arranging for the associated coroutine command to return some value.
yieldto
exit the current coroutine context, which continues to exist, by arranging for some command to be tailcalled by the associated coroutine command.
info coroutine
the name of the current coroutine

Tcllib

coroutine
provides alike commands for after, vwait, read, gets designed for use within coroutines
coroutine::auto
wraps the above in extra magic!

Internals

TIP#328
the original TIP that proposed coroutines
NRE (non-recursive engine)
the mechanism that makes coroutines possible

Wiki pages

anonymous coroutine
Provides gensym to obtain an unused name for a command.
corovars
a brief explanation of coroutine-local (actually coroutine-global) storage upvar #1
coroutine is the new main
Advice to structure all Tcl scripts, even those that premeditate a single control flow, as coroutines.

Iteration

Iterator Protocol
a coroutine-friendly pattern for iterators
for ... in, by pooryorick
includes a toy example of a coroutine
foreach with coroutines, by KBK
Going Loopy with Coroutines, by NEM

Networking

Coronet
CMcC provides a skeleton for networking with coroutines
coroutines and sockets, by aspect
illustrates adapting a naive socket server to coroutine style
parsing with coroutine
some examples of how to exploit coroutines in parsers

Interprocess communication

async, by AMG
Package for asynchronously running and communicating with any number of child processes.

Event models and state machines

coroutine-enabled event handling, by CGM
a rough demo
fiber, by APN
co-operative multitasking via message passing.
Coroutines for event-based programming, by NEM
Coroutines for cooperative multitasking, by JBR
also Coroutines for pre-emptive multitasking
A Coroutine-Enabled Interactive Command Line, by NEM
ycl coro relay, by PYK
A small but complete system for communication between cooperating asynchronous coroutines

Pedagogy

Discrete event modelling with coroutines, by Arjen Markus
a very neat demo using coroutines for a simulation
Modelling a queueing system, by Arjen Markus
Compares and contrasts implementations using the event loop, threads, and coroutines
Coroutines for the Dazed and Confused, by jblz
Polygon intersection
the second algorithm uses a chain of coroutines to check subject polygon edges against each segment of a clip polygon in turn.
Same Fringe
Using coroutines to enumerate the fringes of two trees, so that a simple iteration can test whether the trees have the same fringe.

Coroutines in Action

Playing VHDL, by Peter Spjuth
Сопрограммы, их повадки и применение, by Anton Kovalenko
open
the section, "Asynchronously Capture stdout, stderr and Child Exit Status", contains a coroutine example
TkAlign4
contains a fairly simple example of using coroutine instead of update for an animation. The coroutine does double duty as a synchronization mechanism, preventing another move from being initiated while a move is in progress.
Wub
csp
Golang inspired concurrency library for Tcl

Obsolete / historical pages

multi-arg coroutines
a proposition by CMcC that contributed to the development of yieldto. Also presents a shim to support the transition.
co-routines
an early exploration by AM emulating coroutines at the script level
tcor - A Tcl Coroutines Extension
an extension by GPS adding coroutines before 8.5

Reference: Asymmetric Stack Coroutines

An implementation of asymmetric stackful coroutines (see Lua's team survey (pdf!) [1] and tutorial [2], and/or the Wikipedia article [3]).

(DKF: Seems to be actually a "generator" according to the definitions referred to on Wikipedia.) (NEM: The definition on wikipedia seems wrong to me. The difference between a generator and a coroutine is that the former can only produce values, whereas the latter can be both a producer and a consumer. In practical terms, this means that yield can both generate a value and receive a value to return: set y [yield $x]. C.f. Python which extended its generators to full coroutines in version 2.5 by adding exactly this capability.)

aspect: Andy Wingo wrote a great survey of coroutine-like things in various languages as he was developing continuations and generators in Guile Scheme. The referenced notes and papers from Oleg Kiselyov are deep: after doing crazy things with call/cc for a long while, Oleg eventually argues strongly and convincingly that `call/cc` is ''too'' powerful.

This opinion was once neatly echoed by kbk in the chat: coroutines, closures, continuations, green threads, all have attributes in common. Scheme tries to distill them down to an irreducible minimum as 'call/cc'. But every time I want to work with 'call/cc', I have to spend a week meditating upon Continuation Passing Style before I can make sense of it.

Discussion

  Other languages with coroutines

jima 2009-11-11 notices goroutines in [4] (and, incidentally, the use of UTF-8 in go language).

  • DKF: Their documentation is not quite as clear as it should be (notably on whether there's shared mutable state available or if not, just how things are protected) but it looks like what they're really doing is lightweight threads, not coroutines. We might want to suggest “borrowing” their channel abstraction though; it's a model that works really well.

  The original announcement

From c.l.t.[5]

Just stating what I understand and where I stand.

- A - Experimental coroutines are in HEAD and 8.6a2

     * they do allow new and simpler ways to express things
     * what's in there is experimental infrastructure
     * please play with code and concept, help us make it better

- B - Some design decisions I consider necessary, where the alternatives I saw
fall in one or more of the following categories:

     (a) semantics not clear (to me and/or generally)
     (b) no hope in hell to have it in 8.6 (compat)
     (c) no hope in hell to have it in 8.6 (time)

    Among these:
     * the coroutine bodies run in [uplevel #0]
     * coroutines are not serializable
     * coroutines are like one-shot continuations, not restartable

- C - Some design decisions where made with possibly insufficient info:

    (0a) [coroutine] creates a command and not a special object with subcommands
         Justification:
           (a) provides all that is needed
           (b) does not require new (sub)commands to resume, delete, ...
           (c) leverages Tcl's command management code (for instance, automatic cleanup
               on namespace deletion)
           (d) implementation simplicity
    (0b) [coroutine] runs the body up to the first [yield] instead of just creating the
         command
         Justification:
           (a) this is not really restrictive
           (b) it does not create commands that take different arguments at first and
               successive calls
           (c) implementation simplicity
    (1)  coroutines are self-cleaning
    (2)  [coroutine] requires a command name ([cmd] in the rest of this post]
    (3)  [cmd] takes a single argument: [yield]'s inside return value
    (4)  [yield] takes a single argument: the outside return value
    (5)  [yield] always return an "ok" code, both inside and outside

    Of these, only (5) restricts functionality; it was taken because *I* can
not see how to make the alternative (a) useful, (b) semantically clear, (c) play
nicely with (1). I may be wrong, eager to learn.

     (1) I think is valuable: when the coroutine is exhausted there's nothing
else that can be done with it, so let the command disappear instead of burdening
the caller to clean up.

     The other three are ... irrelevant at this stage! Simple script wrappers
can provide alternative syntax at minimal perf cost. They do not constrain
experimentation in any way. Should we want more than one available, standard
wrappers could be in tcllib or TIPped and "builtin". Should the perf penalty be
too large, they can at any time be coded in C (or even bytecompiled!) as solving
perf bugs.

- D - I am eager to get help making this better

     (a) Looking mostly for "mental bugs", things that are stopping me from
writing a TIP right away:
       * does it make sense? are there inconsistencies and semantic snafus?
       * are there B-type restrictions that could be lifted in time for 8.6?
       * is there more C-type stuff that I am missing, and that is losing
generality?

     (b) Looking for arguments that would tip C-decisions one way or the other;
this includes primarily real use cases. Mainly interested in (1) and (5), and
possibly other decisions that I may have made unconsciously (help me find them!).

  Limitations of the implementation

AMG: According to MS's documentation, "a yield is only allowed if the C stack is at the same level as it was when the coroutine is invoked." Does this mean that yield cannot be used as the SQLite progress callback?

DKF: In theory, it could. In practice, not with the current code because it recursively calls the interpreter rather than using the NRE evaluation mechanism. The tdbc version might work though (it's founded on NRE-enabled stuff).

PYK 2017-05-25: I think that at some point the progress callback became NRE-enabled, and can now yield.


  Limitations of yield

AMG: yield doesn't work across multiple interps.

% coroutine foo [interp create] eval yield
yield can only be called in a coroutine
% coroutine foo info coroutine
::foo
% coroutine foo [interp create] eval info coroutine
% # returns empty string

I was considering a design where a script run in a safe interp repeatedly yields to the invoking interp, but I guess I can't do this.

MS Your example is designed to illustrate that you cannot directly yield across interps, which is true. Trying to guess the real aim of the exercise, I suggest something like

set i [interp create]
$i eval coroutine foo mycmd ...
interp alias {} foo $i foo

You can now call foo from the main interp and have the coroutine named foo run in the slave; when the coroutine yields, you are back in the main interp. Is this somehow related to what you really wanted to do?

AMG: Very interesting! I'm not entirely sure I can use this on my current project (I was just casting about for ideas), but I'm sure this will come in handy at some point. Thank you for explaining how to use coroutines across interpreters and for writing NRE/coroutine in the first place.

AMG, much later: Here's more code that mixes coroutines and interps. Unfortunately, it doesn't work, at least not in Tcl 8.6b1. TclExecuteByteCode() fails with "C stack busy".

proc splitscript input {
    set slave [interp create -safe]
    $slave eval {unset {*}[info vars]}
    foreach command [$slave eval {info commands}] {
        $slave hide $command
    }
    $slave alias unknown apply {args {yield $args}}
    coroutine nextline apply {{slave input} {
        yield
        $slave eval $input
    }} $slave $input
    set result {}
    while 1 {
        set line [nextline]
        if {$line ne {}} {
            lappend result $line
        } else {
            interp delete $slave
            return $result
        }
    }
}

Is this by design, am I up against an unimplemented feature, is this a Tcl bug, or is there a mistake in my code or my understanding?

MS: same as above: you cannot yield across interp boundaries; more concretely, cross-interp aliases are not nre-enabled, they consume stack ("C stack busy") and block yield. I know I thought of some security risk in allowing this, but that is not the only reason: enabling this would have meant bigger changes in the core which I thought were unwarranted for a first version.

AMG: This is not quite the same as before, as indicated by the different error message. The yield happens in the same interpreter as the coroutine, which is the requirement not met by the code I posted long ago. Inside unknown, info coroutine returns nextline. But between the invocation of the coroutine and the yield, there are two interpreter switches: the coroutine calls into the slave interpreter, which then calls back into the master, which yields. And as you say, cross-interp aliases are not NRE-enabled. I can't think of any security problems with this, since all the coroutine stuff is done inside a single interpreter. However, I certainly do understand your second concern. You can't NRE-enable the world, not all at once anyway. :^)

AMG: By the way, here's a non-coroutine version of the above:

proc splitscript {input} {
    set slave [interp create -safe]
    $slave eval {unset {*}[info vars]}
    foreach command [$slave eval {info commands}] {
        $slave hide $command
    }
    $slave expose lappend lappend*
    $slave invokehidden proc unknown* {args} {
        lappend* ::script* $args
    }
    $slave invokehidden namespace unknown unknown*
    $slave invokehidden set script* {}
    $slave eval $input
    set script [$slave invokehidden set script*]
    interp delete $slave
    return $script
}

AMG: See Config file using slave interp for another variation on the above script, plus discussion on its use.

AMG, nine years later: I ran into this problem again, came here to report it, and found I was the one who reported it to begin with. I'm running user code in a slave interpreter with various commands aliased back to the master interpreter, but some of those commands need to be able to [yield] back to the event loop (so the GUI stays alive) while they wait for an external event to occur (timeout, child process readability, incoming network data, and so on).

My current implementation uses separate threads, mostly because coroutines aren't available in the old version of Tcl I was targeting, but I've since changed all GUI usage of my program to 8.6. I want to get away from threads because they are complicated and don't do anything to let me use Tkcon to inspect and edit live code and data. With threads, I have an interpreter that's unresponsive to events while it waits for [after] or [read] or whatever to complete. Coroutines solve this problem, but it looks like it does so at the expense of slave interpreters.

Unless anyone has any better ideas, I'm afraid I must downgrade from running the user code in slave interpreters to running it in a namespace. This is especially frustrating because the majority of times my program will be used will be non-GUI (hence no requirement for Tkcon) and with Tcl 8.5.8 (hence no coroutine capability in the first place), so I'll be losing functionality everywhere for the sake of a nice feature used in rare (but important) circumstances.


  Tricks, wise or otherwise

DKF: You can do a "global coroutine" like this:

coroutine foo eval {yield "in the coro 1"; yield "in the coro 2"; return "finishing"}

But that doesn't mean that I think it is a good idea. For example, you don't get nice variable handling this way.

NEM: Or, using a lambda:

coroutine foo apply {{} { yield "in the coro 1"; ... }}

DKF: Yes, but with lambdas you get that nice variable handling. That's because it comes from the local variable context that gets pushed as part of the apply (or the procedure if you're using a "traditional" coroutine).


Unconditionally terminate the currently running coroutine:

rename [info coroutine] ; yield

Terminating the currently running coroutine, catchable within the coroutine:

return -level [info level]

LV: In an environment which supports threads and safe interps, what questions should a new developer ask when determining the appropriate technology? And are there situations where one might want/need to combine these in ways?


DKF: This example (from the Tcl docs) shows how to generate primes with the sieve of eratosthenes in Tcl using coroutines...

proc filterByFactor {source n} {
    yield [info coroutine]
    while 1 {
        set x [$source]
        if {$x % $n} {
            yield $x
        }
    }
}
coroutine allNumbers apply {{} {while 1 {yield [incr x]}}}
coroutine eratosthenes apply {c {
    yield
    while 1 {
        set n [$c]
        yield $n
        set c [coroutine prime$n filterByFactor $c $n]
    }
}} allNumbers
for {set i 1} {$i <= 20} {incr i} {
    puts "prime#$i = [eratosthenes]"
}

It might be interesting if someone (TM) attempted a translation of A Curious Course on Coroutines and Concurrency.


2015-12-02 sometimes I have code segments that can only run in a coroutine context (typically: sending a message, waiting for the reply, ...). I usually mark the entry point with a call to "coroutine::required":

namespace eval ::coroutine {}
proc ::coroutine::required {} {
    if {![coroutine?]} {
        return -code error "coroutine required"
    }
}
proc ::coroutine? {} {
    expr {[info coroutine] ne ""}
}

PYK 2016-04-23: Here's a trick to make sure the current context is a coroutine context. It's a essentially a no-op in the coroutine context, and an error otherwise:

yieldto [info coroutine]

  Introspection

jbr 2010-05-05:

Coroutine names don't appear in the info procs list? Is this by design? Below I can call "xxx" but I cannot see if its currently defined by asking info.

proc yield-once {} {yield; puts Called}
coroutine xxx yield-once

puts [info procs *]

xxx

exit

Output does not contain xxx:

auto_load_index unknown auto_import throw auto_execok clock auto_qualify auto_load yield-once try tclLog

AMG: Coroutines aren't procs, they're commands.

proc yield-once {} {yield; puts Called}
coroutine xxx yield-once
info commands x* ;# returns "xxx"

yield-once is a proc, but yield-once is not a coroutine. The coroutine command is created by yield, not coroutine. In this case yield calls the coroutine "xxx", since that's the name provided to it by coroutine.

jbr: Thanks - the documentation is correct and makes sense now that you point is out, coroutine creates a command just like the man page says.

  Cloning

AMG: Is there a way to clone a coroutine? I'm not talking about making a new coroutine that has the same command and arguments as an existing coroutine. Cloning a coroutine would produce a new command whose only difference from the original coroutine command is return value of [info coroutine]. The two coroutine commands would not be linked, they'd just have the same state at the moment of cloning.

% coroutine keaton apply {{} {
      yield
      foreach i {0 1 2 3} {
          puts "$i [info coroutine]"
          if {$i == 1} {
              yield
          }
      }
  }}
% keaton
0 keaton
1 keaton
% CloneCoroutine -old keaton -new kid_a
% kid_a
2 kid_a
3 kid_a
% keaton
2 keaton
3 keaton

DKF 2012-02-01: As things stand, no.

AMG: Basically this would establish a means to checkpoint a coroutine and resume execution at any old saved checkpoint, independent of what that coroutine has done (or what has been done to that coroutine) since the time the checkpoint was created.

I wonder what would come of coroutines cloning themselves. I'm afraid that with that kind of power they might try to take over the world. ;^) The CloneCoroutine command would return empty string when it is (initially) called, but when the newly created coroutine commands are called with an argument, they would see CloneCoroutine return that argument, similar to yield. That way, they could tell themselves apart without having to rely on [info coroutine], plus they could be passed arbitrary data. Why would it be advantageous to not depend on [info coroutine]? A coroutine could be cloned, then later that clone could be renamed on top of the original. In this situation, [info coroutine] would not be sufficient to distinguish between the original and the cloned invocations, though a global variable could also be used for this purpose. I don't know if this would be useful, I'm just playing with the idea.

AMG: Are there fundamental technical restrictions preventing the implementation of coroutine cloning? I can understand there being a lack of interest, since the subject hasn't come up before. But is that the only real obstacle?

MS: The real obstacle is that each coroutine has its own tcl stack, which stores (among other things) pointers to itself. Making a copy of that stack implies fixing those autorefs, which in turn implies storing the nature of each entry in the stack to know if it has to be fixed or not (and how), which in turn implies a redesign of the tcl stack.

  Identifying the calling coroutines

AMG: Coroutine invocations form a stack separate from the normal call stack, with the limitation that coroutines are expressly non-reentrant and are not permitted to simultaneously appear more than once on the stack. When a coroutine yields, execution returns to whichever coroutine called it, if in fact it was called by a coroutine. The info coroutine command returns the name of the current coroutine, but there is no direct way to identify the calling coroutine or its callers.

That's not to say it can't be done. yieldto can be used to ask the caller to run [info coroutine], then to report the result back to the current coroutine. Like so:

proc parentCoroutine {} {
    lindex [yieldto apply {{resume} {
        $resume [info coroutine]
    }} [info coroutine]] 0
}

How about getting the caller's caller? Or the entire coroutine stack? The above can be extended to traverse the entire stack:

proc coroutineStack {} {
    if {[set self [info coroutine]] ne {}} {
        list {*}[yieldto apply {{resume} {
            $resume {*}[coroutineStack]
        }} $self] $self
    }
}

For example:

% coroutineStack
% coroutine coro1 coroutineStack
::coro1
% coroutine coro1 coroutine coro2 coroutine coro3 coroutineStack
::coro1 ::coro2 ::coro3
% coroutine coro1 apply {{} {apply {{} {
    coroutine coro2 apply {{} {apply {{} {
        coroutine coro3 apply {{} {apply {{} {
            coroutineStack
        }}}}
    }}}}
}}}}
::coro1 ::coro2 ::coro3

The last example above demonstrates that [coroutineStack] still works even when there are many normal call stack layers present.

To just get the top-level coroutine, try:

proc coroutineTop {{resume return}} {
    set self [info coroutine]
    if {$self eq {}
     || [set top [lindex [yieldto coroutineTop $self] 0]] eq {}} {
        $resume $self
    } else {
        $resume $top
    }
}

Take a moment to appreciate how bizarre all this is. The traditional call stack is flipped on its head. Execution proceeds down the coroutine stack and the call stack within each coroutine, then when [coroutineStack] or [coroutineTop] is invoked, execution proceeds backwards up the coroutine stack, with each coroutine being instructed to call the coroutine that originally called it, then to relay the result back to the coroutine that most recently called it. The coroutine stack unwinds and then rewinds, all the while preserving the call stacks within each coroutine.

Here's a lambda version using apply, ready to be used inline if there's only one place in your program that needs to know the toplevel coroutine:

apply {{next} {
    set self [info coroutine]
    set command [list yieldto apply [lindex [info level 0] 1] $self]
    if {$self eq {} || [set top [lindex [{*}$command] 0]] eq {}} {
        $next $self
    } else {
        $next $top
    }
}} return