Re: [TCLCORE] Coroutines in HEAD

[Neil M. <ne...@Cs...>]

On 24 Aug 2008, at 21:02, Lars Hellström wrote:
> [...]
> COMPARISON OF [coroutine]/[yield] AND [suspend]/[resume]
>
> Roughly, [suspend] corresponds to [yield], whereas [resume] is more
> like the coroutine-cmds; there is no explicit [coroutine]-like command
> needed in the [suspend]/[resume] approach, since one is implicitly
> provided by the main event loop (when that is running).

It's an interesting idea whether the Tcl main program should itself  
be a coroutine. That would give a possibly useful semantics to  
[yield] called from outside of any explicit coroutine -- it would  
yield to the event loop (i.e. much like an [update], but capable of  
returning a value). The use of coroutines shown in http://wiki.tcl.tk/ 
21532 depends on the "main" procedure being a coroutine, so you can  
suspend/resume the entire program. This allows for very much  
continuation-like behaviour to be achieved. In practice, I leaving it  
as-is works better.

>
> *Existence.* Obviously, a big difference is that an implementation of
> [coroutine]/[yield] exists, whereas [suspend]/[resume] is at best a  
> sketch.
>
> *Model.* [coroutine]/[yield] is, as far as I can tell, modelled after
> the concept of a generator: a subroutine than can return several  
> times.

Similar, yes, although generators are not usually first-class objects.

> [suspend]/[resume] rather follows the continuation model: the rough
> idea of "the program from this point on" is given tangible existence.
> It is different from the LISPish (call-cc) in that the continuation is
> not given the form of an anonymous function, but that's natural given
> the more imperative nature of Tcl, and it is also different in that it
> is not the part of the program that calls [suspend] which gets to
> handle the continuation, but rather some generic handler at the top  
> level.

The scheme you have described sounds like an implementation of  
"escape continuations" -- i.e. continuations which act like  
exceptions. Such continuations are strictly less powerful than either  
full continuations or coroutines, IIRC.

> *Storage.* Since [suspend] starts putting data in the interpreter
> result, everything has to be put under a Tcl_Obj wrapper. This is
> potentially a slow operation (but probably not so slow that it becomes
> a major issue when suspending the handler for an event). By contrast,
> [coroutine]/[yield] hides everything under the opaque handle of a  
> command.

The opaque handle nature of coroutines is, I think, acceptable in  
this case. A coroutine encapsulates rather a complex chunk of  
interpreter state, so a string representation would be tricky to  
concoct (but perhaps not impossible). That state also changes every  
time the coroutine is invoked. The fact that coroutines automatically  
clean-up the command when they are "exhausted" also seems to reduce  
any difficulties with an opaque naming scheme. Creating uniquely- 
named coroutines in a special namespace (such as on the wiki page I  
linked above) will be mostly good enough. The case it misses is where  
a coroutine is created and then discarded before it has been allowed  
to run to completion. In this case an explicit clean-up would be needed.

> Giving continuations the form of a Tcl_Obj brings all the usual EIAS
> advantages: can pass by value and store in data structures, can  
> save on
> file or hand over to another thread, one can even resume the same
> continuation several times (thus admitting a native implementation of
> oracles for nondeterministic automata)! The cost is that one actually
> has to implement (for every resumable command!) a relevant
> freeIntRepProc, dupIntRepProc, updateStringProc, and setFromAnyProc.
> This _is_ just a Simple Matter Of Programming compared to
> [coroutine]/[yield], since the potentially nontrivial task of  
> isolating
> the internal state of the generator from the rest of the interpreter
> has already been done and all that remains is to serialize/deserialize
> this state. Designing a serialization format capable of expressing the
> necessary data structures is obviously possible. Designing it so that
> it can _only_ express sensible instances of the necessary data
> structures is perhaps less easy, but this is not technically required
> for EIAS.
>
> There is OTOH no principal problem in introducing explicit commands
> that serialize and deserialize a coroutine-command in the
> [coroutine]/[yield] approach (it just hasn't been done yet), and this
> could then be used to transport coroutines across thread boundaries,
> but there is probably a practical problem in that cooperation
> (serialization/deserialisation of clientData) would be required from
> anything that creates an NRE callback.

While I agree with the sentiment that it would be nice to have  
Tcl_Obj based representation of coroutines or some form of  
continuation, I think in practice it would be a lot of work for  
perhaps not a huge amount of gain. Opaque works for threads and  
interps; I think it will suffice for coroutines too.

> *Emulation.* [coroutine] and [yield] can be emulated using
> [suspend]/[resume], as follows (rough implementation):
>
> interp alias {} yield {} suspend yield
>
> proc coroutine {cmd args} {
>     if {[catch {{*}$args} res opt] != $::TCL_SUSPEND} then {
>        return -options $opt $res
>     }
>     switch -- [lindex $res 0 0] "yield" {
>        interp alias {} $cmd {} call-again $cmd $res
>        return [lindex $res 0 1]
>     }
> }
>
> proc call-again {cmd continuation value} {
>     rename $cmd ""
>     coroutine $cmd resume $continuation $value
> }
>
> I don't see how the converse would be possible (but since NRE is more
> than just [coroutine], that needn't be a problem).

Without a more thorough understanding of how suspend/resume are to  
work, I can't assess whether that really works or not (and thus  
whether suspend/resume offer more than escape continuations). I would  
guess it is at least much slower than the coroutine equivalent,  
having to save/restore command invocations from string reps.

>
> *Intervention.* Since a TCL_SUSPEND is a return code and can be  
> caught,
> it allows surrounding control structures to intervene and/or react to
> being suspended. As I understand it, NRE provides nothing in this  
> area.
>
> As an example of intervention, consider control structures that exist
> not to do flow control, but to guard the utilization of some limited
> resource. One such case is the transaction subcommand of a TDBC  
> handle:
>
> proc foo {db expr} {
>     ...
>     $db transaction {
>        ...
>        bar $expr $value
>        ...
>     }
>     ...
> }
> proc bar {expr value} {
>     ...
>     if $expr then {set value [yield $value]}
>     ...
> }
> coroutine baz foo $db $expr
>
> Chances are that the [$db transaction] above will count as recursion
> with respet to the NRE and thus cause [yield] to error out, with a  
> [$db
> rollback] as consequence, but if it does not then the database could
> stay locked for a rather long time, without a clear offender.

Note that this is already possible with the event loop -- e.g., a  
vwait inside the transaction can cause the same effect. Don't Do That!

> By
> contrast, if the [yield] had been a [suspend] instead then [$db
> transaction] would be explicitly informed about what is going on, and
> thus given a chance to react sensibly. Doing an immediate [$db
> rollback] and changing the TCL_SUSPEND into a TCL_ERROR is the most
> elementary reaction (and perhaps the only one directly supported by  
> the
> TDBC interfaces), but it might often be more practical to capture the
> operations made so far in some kind of diff, and attempt to reapply
> them when the transaction is resumed. In that case, the TCL_SUSPEND
> should be passed on.
>
> A complication for control structures implemented in Tcl is that they
> need to create some representation of their own internal state when
> passing on a TCL_SUSPEND. If a third command besides [suspend] and
> [resume] is needed, then this will probably be why. On the other hand,
> if the serialization format used for the internal state of a proc is
> documented, then all sorts of programming tricks (e.g.  
> disconnecting an
> [upvar]ed variable) can be implemented as [suspend]ing execution and
> having some detail in the state of some surrounding procedure  
> modified...

How does a Tcl proc get to restore itself on a [resume]? I don't  
really follow how [resume] works at all, to be honest.

-- Neil
This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.