Menu
▾
▴
Re: [TCLCORE] Coroutines in HEAD
|
From: Lars H. <Lar...@re...> - 2008-08-24 20:02:45
|
To continue where I left off...
C API
(Not my strong side, but one that has to be addressed.) Since the idea
is mostly to give new meaning to things that can already happen, there
isn't /that/ much that has to be added on the C side, but one major
thing is the prototype for the function that is called when a command
is resumed; let's call this a resumeProc:
typedef int Tcl_ObjResumeProc(
ClientData clientData,
Tcl_Interp *interp,
int objc,
Tcl_Obj *const objv[],
int resumeIdx,
Tcl_Obj *const resumeData[] );
The idea here is that the resumeData should be the objv from applying
Tcl_ListObjGetElements to the result caught with the TCL_SUSPEND, and
resumeIdx is the index into this array of the element which is relevant
for this command; the resumeProc will eventually call the resumeProc of
the command it received TCL_SUSPEND from with the same resumeData but
resumeIdx-1.
For practical convenience, it is probably also useful to have a library
function for calling the resumeProc of a particular command, so
Tcl_EvalObjEx (or whichever is the core one these days) would get the
cousin
int Tcl_ResumeObjEx(interp, objPtr, flags, resumeIdx, resumeData)
The tricky part is of course that all these resumeProcs must be
provided when the command is created. For a long time I thought that
this meant nothing of this could be implemented before Tcl 9 anyway
(hence there would be no rush to generate a string representation :-]
of the suspend/resume idea), but now I'm not so sure -- it's perfectly
reasonable to have e.g. Tcl_CreateObjCommand create commands without a
resumeProc (resumeProc==NULL), and instead introduce a new function
Tcl_Command Tcl_CreateSuspendableCommand(
interp, cmdName, proc, clientData, deleteProc, resumeProc
)
for creating commands that do have it. Calling Tcl_ResumeObjEx for a
command that doesn't have a resumeProc won't work, but we can simply
report that as an error, so it's no big deal (at the C level).
However, rather than reporting such errors at the resuming stage, it
would be better to detect them at the suspend stage. In principle, that
could be done by having Tcl_Eval* verify that any command returning a
TCL_SUSPEND also has a resumeProc, or else convert that TCL_SUSPEND
into an appropriate error. As far as I can tell, that would be the only
***potential incompatibility*** of this scheme against current Tcl.
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).
*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.
[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.
*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.
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.
*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).
*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. 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...
miguel sofer skrev:
> Lars Hellström wrote:
>> miguel skrev:
>>> I managed to commit an experimental implementation of coroutines in
>>> time for 8.6a2. This provides two new commands
>>> ::tcl::unsupported::coroutine
>>> ::tcl::unsupported::yield
>>>
>>> A brief description can be found at
>>> http://msofer.com:8080/wiki?name=Coroutines, otherwise the code in
>>> tests/unsupported.test is the only documentation.
>>>
>>> Test! Enjoy! Help make it better
>>
>> This might fall in the "help make better" category, although it's
>> really some loose sketches for an alternative realization of the same
>> concept that I've been contemplating on and off during the last couple
>> of years (judging from http://wiki.tcl.tk/13232, since April 2005).
>> I'm posting this mostly to provide an alternative point of view --
>> maybe some details of the Tcl interface would be better if done
>> differently? -- although it seems this approach could actually do some
>> things mentioned as unsolved in the NRE implementation (moving
>> coroutines between threads, handle C-coded commands calling Tcl_Eval).
>
> Thanks.
>
> There is one problem with this approach: it breaks every extension that
> calls for an evaluation, as it doesn't know about TCL_SUSPEND nor what
> to do with it. Some of those are under our control (Tk for example), but
> unknown quantities are not.
>
> A second (or is it the same?) problem is that extensions may well be
> using their own return codes ... a new return code is not something that
> we can do until Tcl9.
Hadn't thought of that one, but OTOH I was mostly thinking Tcl9 anyway
(until recently).
Realistically though, if some TCT member had come up with an idea that
required usurping another return code, then I doubt there would have
been much opposition against doing so within the 8.x series. Also, that
noone else reported bug#647307 is perhaps an indication that
nonstandard return codes aren't that heavily used. ;-)
> A third problem with the special return code is that [catch] would block
> it; the current code can yield in arbitrarily nested catch ranges.
*That* is not a bug; it is a feature (as explained above)!
Late addition: One could improve interoperability between
[suspend]/[resume] and old control structures implemented in Tcl by
making it so that [catch] only catches TCL_SUSPEND if it has an extra
argument -- thus extending the syntax to
catch $script ?resvar? ?optionsvar? ?resumeitemvar?
-- where the resumeitemvar is filled in with the resumeData item that
would resume processing in this proc from within that [catch]. Then the
coroutine emulator above could let non-yield TCL_SUSPENDs pass through
if changed to
proc coroutine {cmd args} {
if {[catch {{*}$args} res opt item] != $::TCL_SUSPEND} then {
return -options $opt $res
}
switch -- [lindex $res 0 0] "yield" {
# This kind of [suspend] is handled here.
interp alias {} $cmd {} call-again $cmd $res
return [lindex $res 0 1]
} default {
# Other kinds get to suspend also [coroutine],
# backing up to the [catch] above.
lappend res $item
return -code suspend $res
}
}
> The thing I implemented is 100% compatible, extensions that do not adapt
> keep on working but may block suspending. There is an api for extenders
> to adapt.
No big difference there, I'd say.
> This is also one of the reasons why you have to "declare" a coroutine:
> you have to prepare the infrastucture to be able to suspend a "thread"
> (?), which may or may not mean returning to the top level.
>
> Your ideas would still fail to produce coroutines that can migrate
> accross threads, at least without big changes in the core: the problem
> is that the same interp cannot be run in different threads. The same
> problem as the ones in head.
Thread migration would be done via serialization, as explained above.
Reconstructing the state of a proc from string rep in another thread
may seem like a hazardous task, but probably no more so than in the
original interp. In particular, I suspect one must be able to handle
changes in the bytecode for the procedure one is resuming, since
redefenitions of other command may well have triggered a recompilation,
can they not?
Are you otherwise saying that NRE is employing threads to do its work?
Or did you assume [suspend] would? (It doesn't.)
> What I implemented relies on the NRE execution model: (newer, adapted) C
> code never calls an eval, it rather queues a callback with enough info
> do any post-processing or cleanup it needs to do after the evaluation,
> schedules the new evaluation and returns TCL_OK. There is a trampoline
> that runs the evaluation and then the callbacks. If a C function
> actually does call an eval using the regular API, trying to suspend
> before it returns will raise an error.
>
> That means that no C function is ever suspended: it was implemented as a
> two-part function to begin with. Even though your email got truncated, I
> imagine this is not too different in spirit to the two-entry-point
> system you were about to describe?
Slightly different in spirit, but perhaps not in nature. In order to
make a typical resumeProc for Tcl_CreateSuspendableCommand, one should
be able to just take the corresponding proc and add "spaghetti" for
jumping to the place where resuming requires one to be -- provided that
one has the "stomach" for such violations of Structured Programming
dogma. By contrast, the NRE API of callbacks one can add rather
suggests that the proc should be transformed into an automaton. It is
possible that any resumeProc obtained through adding spaghetti will
also be possible to operate as an automaton through the
Tcl_NRAddCallback interface, in which case the two would indeed not be
different in nature, but I haven't explored the design in that much detail.
(A completely unrelated fact is that I've been contemplating writing a
[proc]-simulacrum that cuts up the body script into little automaton
pieces to permit asynchronous evaluation, but that is in Tcl. Failure
to do it perfectly there isn't as disastrous as it can be in C.)
Lars Hellström
|
