Re: [TCLCORE] Coroutines in HEAD

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

On 29 Aug 2008, at 13:38, Lars Hellström wrote:
> Neil Madden skrev:
>> On 28 Aug 2008, at 12:07, Lars Hellström wrote:
>>> Neil Madden skrev:
>>>> Similar, yes, although generators are not usually first-class  
>>>> objects.
>>>
>>> Did that come out backwards? The NRE coroutines doesn't seem to  
>>> be first-class objects, but I can imagine coroutines elsewhere as  
>>> a rule being first-class.
>> First-class as in you can pass them to/from commands etc. You can  
>> do that with coroutines -- just pass the command name.
>
> FOTC.

Flight of the Conchords?

> To "pass the command name" is usually considered to be pass-by- 
> reference. If that sufficies for being "first-class", then arrays  
> are "first-class" too!

Pass by value/reference is orthogonal to whether something is first- 
class. E.g. Java objects are considered first class, but are passed  
by reference. You can indeed have "first class references" (see e.g.  
ML), without that being an oxymoron. The difference between commands  
and arrays is that you don't have to perform any extra step to use a  
passed command name, i.e.:

  proc foo {cmd args} { $cmd ... }
vs
  proc foo {arrName args} { upvar 1 $arrName arr; something $arr 
(foo) .. }

>
>> Generator functions, as I understand it, have no per-instance  
>> command or object, so you can't pass them around. Instead, the  
>> creation and use of an instance is all captured within some  
>> iteration-like construct.
>
> You mean, like a [foreach] where list elements would be generated  
> as they are needed?

Essentially yes. Python's [for] statement can operate in this manner.

>> An escape continuation can only be used to escape back up the  
>> stack, like an exception. You can't use them to jump back to a  
>> point further down the stack that has already unwound. Looking at  
>> your proposal in more detail, I can see that [resume] is more than  
>> this. However, it's still not clear how you would implement e.g.  
>> call/cc in this proposal.
>
> Roughly as follows:
>
> proc TCL_SUSPEND_handler {bgerror cont opt} {
>    if {[dict get $opt -code] != $::TCL_SUSPEND} then {
>       return [{*}$bgerror $cont $opt]
>       # Or [tailcall], if you prefer that.
>    }
>    # Now for the TCL_SUSPEND handling...
>    switch -- [lindex $cont 0 0] "after" {
>       # Syntax: suspend after $ms
>       after [lindex $cont 0 1] [list resume $cont]
>    } "vwait" {
>       # Syntax: suspend vwait $varname
>       trace add variable [lindex $cont 0 1] write [list ::apply {
>          {varname cont name1 name2 op} {
>             # Trace removal omitted
>             after 0 [list resume $cont]
>          } ::
>       } $varname $cont]
>    } "call-cc" {
>       # Syntax: suspend call-cc $cmd ?$arg ...?
>       # The $cmd will be called as:
>       #    $cmd ?$arg ...? $continuation
>       after 0 [lrange [lindex $cont 0] 1 end] [list $cont]
>    } default {
>       # Report error...
>    }
> }
> interp bgerror {} [list TCL_SUSPEND_handler [interp bgerror {}]]

OK, so you tear down the entire stack and then recreate it again? Or  
do you just call the command from the toplevel? If the latter, that's  
not call/cc. It's an intriguing idea, but I have to wonder - why bother?

>
>>> Ultimately, we may always fall back to what is written on the  
>>> tape of our Turing machine. :-)
>> Well, a programming language interpreter usually goes beyond what  
>> is considered by a Turing machine -- I/O for one example.
>
> Nitpicking!
>
>>> More practically, also the NRE has to separate the per-coroutine  
>>> state from the general interpreter state, and IMHO that is where  
>>> you might encounter nontrivial issues. The rest should just be  
>>> the hard work of serializing a well-defined data structure.
>> That is (a) a lot of hard work,
>
> Is there an echo? Noone denies it would be hard work.
>
>> and (b) to be at all efficient is probably going to involve  
>> serialising a lot of implementation details.
>
> Not sure how efficiency would fit into any of this, but yes, you'd  
> get to see lots of implementation details. Which can, I suppose, be  
> scary if you're not prepared to document what can be relied upon  
> and what cannot be.

This worries me quite a lot, actually. People almost certainly would  
start relying on these implementation details.

>>>> [...]
>>> That said, it is probably not possible to make [suspend] as fast  
>>> as [yield], but it is also more general.
>> I don't see any evidence for this claim. Coroutines are extremely  
>> general, as demonstrated in the Lua paper that Miguel has linked  
>> to before.
>
> I'm not considering coroutines in general, I'm just comparing  
> [suspend]/[resume] with the existing [tcl::unsupported::coroutine].  
> In this comparison:
>
>  1. [suspend]/[resume] gets some additional power from having its
>     continuation under a Tcl_Obj wrapper. Example of applications:
>     * Transport across thread boundaries.
>     * Oracles (in the NP sense -- simulating a nondeterministic
>       computer; an implementation of this sits on my hard drive).

Non-determinism can also be simulated with coroutines -- this is one  
of the examples in the Lua paper. Indeed, they demonstrate that  
coroutines (as implemented by Miguel) are roughly equivalent in  
expressive power to one-shot continuations.

>
>  2. [suspend]/[resume] gets further additional power from the
>     exposure the implementation details, since this means they
>     can fiddle around with the state at that level.
>     Example of application:
>     * Undoing [upvar]s: [suspend], have the TCL_SUSPEND handler
>       remove the part of the continuation that encodes this [upvar] 
> ing,
>       [resume] the modified continuation.
>
> Whether it is a good idea to exercise the second category of powers  
> is debatable (it's a bit like POKE in the old BASIC era), but the  
> power is a consequence of the model.

That isn't part of the expressive power of [suspend] or [resume], it  
is a side-effect.

Having looked at your sample implementation, I can only say that the  
concept seems doomed to be hopelessly inefficient to implement, while  
not buying any practical advantage over the coroutines mechanism. I'd  
much rather spend more time discussing the pros and cons of the  
coroutine mechanism.

-- 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.