From: Lars H. <Lar...@re...> - 2008-08-29 12:37:36
|
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. 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! > 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? > 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 {}]] >> 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. >>> 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. >> >> The difference is that threads and interps (at least if you're running >> the event loop) have an internal state that can mutate while you're >> not looking. Coroutines are (I hope) immutable when they're not running. > > What state of a thread is mutated when it is not running? Threads and > coroutines are really quite similar. With the big difference that with threads you can *never* be sure that they are *not* running! Remember that "you" in this sense is sitting inside a thread too, and thus can have your time stopped just about anywhen the kernel feels like doing so. >>> 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. >> >> Remember that we have Tcl_Objs, and can stash data in the internal >> representation. The string rep wouldn't normally be generated, it is >> sufficient that it can be. >> >> 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). 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. >>> 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. >> >> There was a detail missing from my sketch: the continuation must >> record what command the resumption is to begin with; sorry about that. >> A proof-of-concept implementation of [suspend] and [resume] can be >> found at http://wiki.tcl.tk/21538. > > I still find it difficult to follow this and relate it to an eventual > implementation of Tcl in these terms. A proof of concept would be > something like the event-loop example given for coroutines, showing how > a normal set of Tcl procs can be suspended and resumed to perform a > concrete task. I mean, if we are allowed to transform the code > completely, then we may as well put everything in CPS form. Isn't transformation to CPS form exactly what NRE asks of all C-coded extensions? But if it makes you more comfortable, I can report that the transformation needed by the proof-of-concept implementation can be automated. The basic code for that is at http://wiki.tcl.tk/21556; I'll amend http://wiki.tcl.tk/21538 later. Lars Hellström |