JR 18Apr2005 What I think would be a nifty use for continuations would be to unnest vwait. As everyone knows, if you call vwait from inside an event handler then the outer vwait cannot return until the inner one does. This gets messy when things that you may not expect call vwait internally, with the general conclusion of vwait considered harmful. However, it is also very useful in some circumstances which makes this all a pain. If we had continuations, then vwait could simply be reimplemented as something like
proc vwait {var} {
uplevel trace variable $var w [info continuation 1]
return -code return
}Where info continuation level returns a command that executes the continuation. Then make the stack frames into Tcl_Objs and increment the reference counts to keep them around and it all works naturally. (if only it were that simple)Lars H, 20 April 2005: I think this more script-level point of view deserves more attention. Discussing implementation techniques is important, but at the same time a bit premature before one knows what should be implemented. Sometimes what looks like a problem resolves itself when specs are being drafted.One way of handling e.g. vwait continuations could be to have a pair of primitives suspend and resume. A usage example could look something like proc A {data args} {
# ...
foreach datum $data {
# ...
if {[undecided $datum]} then {
puts "Going into suspended animation."
suspend
puts "But now I'm resumed!"
}
set result [getResultFor $datum]
# ...
}
# ...
}When suspend is evaluated, the entire local context is somehow recorded and put in suspension. Lets say it is all encoded into a Tcl_Obj which is put in the variable state_of_A. At some later time, something (e.g. an after or fileevent script) evaluates the commandresume $state_of_Aand this causes A to resume where it was suspended, thus printing "But now I'm resumed!" and continuing at precisely the right iteration of the foreach loop, with all variable values restored. I think this can serve as a first draft for continuation semantics; even if there is some feature that is missing, it should then be a basis for explaining what that feature is.How would this kind of suspend/resume work, then? Recording all local variables and their values isn't too hard (that can probably even be done entirely on the script level), but recording the point in the program where execution was suspended is an entirely different matter. AFAICT there's no script level mechanism of determining that the call to a command (be that command suspend or whatever) was made in the second command of the then part of an if command that itself was the Nth command of a foreach body etc. As I understand it even Tcl doesn't know this too well, and this information can be presented in an errorInfo only because the call stack gets unwinded when an error occurs. But maybe this is how suspend should work too!What if suspend was implemented as a sixth standard return code, that all commands would know and react to by recording their complete state in the interpreter result (or whereever)? This would certainly make suspend halt execution in precisely the expected way. resume has it a bit harder. Although it has all the necessary information, it will also need to be able to restart commands in a nonstandard position. This could require something as deep as a sibling of the Tcl_ObjCmdProc: a C function that is called when the command is to be started in a nondefault position. This naturally leads to the concept of resumable commands -- only those commands for which a resumeProc was supplied upon creation are resumable, and consequently all other commands should convert suspend returns to errors ("I'm not suspendable")!And yes, suspend returns should be catchable. Indeed, that would be how to get the state into the above state_of_A variable in the first place:
if {[catch {A $data -someOption 1} state_of_A] == 5} then {
after 1000 {resume $state_of_A}
}NEM I'm not sure I understand this. You'd have to wait for the new exception to propagate all the way up to the toplevel in order to properly capture everything (catch only catches information up to this point). If you then immediately restore the context from the toplevel, it sort of works (though, of course, you have to restore to the next instruction -- i.e., the current continuation at the point that suspend was called). The big problem I see though, is that there is no mutation and no parametrization: when you restore, you seem to restore everything (all vars) to their original values, and can't pass an argument. Unless you rely on external state (e.g. in a database, or filesystem, or user input), then this is essentially pointless: you just repeat an exact same computation that you've already done. This isn't to say that there aren't alternatives to call/cc -- there are several. (e.g. shift/reset [5] is similar to what you propose, I think).Lars H: I can't comment on the shift/reset reference, since that seems to be available only to ACM members. Regarding the "no mutation, no parametrization":- It could be argued that there typically will be an external state at hand, because if there isn't then there cannot be anything that stopped you from carrying out the computation in the first place, so why would then call suspend? (You might do it for purposes of multitasking, but then you don't want the state to mutate.)
- If the state is a transparent Tcl_Obj (and I think it should be), then you do have a mutation possibility: to change the value of something directly in the state. This requires a bit of surgery, but nothing outrageous.
SS: I think the only good way to implement continuations in Tcl is ala Scheme via a call-cc procedure [6]. That's at least how I'll implement it in Jim at some point. This way is very general and powerful, and starting from call-cc one can create more high-level abstraction in Tcl itself.Lars H: The reference you give isn't all that clear (and for a large part very Algol-language-family-centric, but then again, so was I before I discovered Tcl :-), but AFAICT this call/cc is very similar to the suspend I sketched above. The main difference is that call/cc isn't catchable, or rather can only be catched by the main event loop of the program, but that's not much of an advantage. Instead of having an explicit resume command the call/cc semantics seems to be to create an anonymous command for resuming at a particular point in the program, but that's just a matter of style (and what degree of obfuscation one desires). A cool use for really returning a frozen state is for more complete introspection (maybe even debugging).
AM (21 april 2005) Here is a small experiment with continuations or (more precisely) generators in pure Tcl - at least as I understand them to work.There are lots of caveats and the implementation is not as elegant perhaps as it ideally would be - too much gets exposed at the user level, but, well, it is doing its intended job :).
# continuation.tcl --
# Experiment with continuations or, rather, generators
#
# generator --
# Create a generator procedure
# Arguments:
# name Name of the procedure
# arglist List of arguments
# _init_ Dummy (keyword init)
# initbody Body for the initialisation
# _repeat_ Dummy (keyword repeat)
# repeatbody Body for the main loop
# Result:
# None
# Side effect:
# Procedure created by name $name
#
proc generator {name arglist _init_ initbody _repeat_ repeatbody} {
set initbody [string map {yield gensave;return} $initbody]
set repeatbody [string map {yield gensave;return} $repeatbody]
proc $name [concat _ $arglist] \
[string map [list INITBODY $initbody REPEATBODY $repeatbody] {
upvar 1 $_ __
if { [lindex $__ 1] eq "init" } {
INITBODY
} else {
eval [lindex $__ 2]
REPEATBODY
}}]
}
# gencreate --
# Create an actual generator (or the context for running it)
# Arguments:
# name Name of the generator
# Result:
# Context for running the generator
#
proc gencreate {name} {
list $name init {}
}
# genrun --
# Run the generator
# Arguments:
# name Name of the _variable_ holding the context
# Result:
# Whatever the generator gives
#
proc genrun {name} {
upvar 1 $name context
[lindex $context 0] context
}
# gensave --
# Save the visible variables
# Arguments:
# None
# Result:
# None
# Side effect:
# The context is updated (the variable in the caller proc)
#
proc gensave {} {
upvar 1 __ context
set save {}
foreach v [uplevel 1 {info vars}] {
if { $v ne "__" && $v ne "_" } {
lappend save "set $v [uplevel [list set $v]]"
}
}
lset context 1 repeat
lset context 2 [join $save "\;"]
return
}
# Example --
# As an example: use a Fibonacci numbers generator twice
#
generator fib {} init {
set i 0
set j 1
yield 1
} repeat {
foreach {i j} [list $j [expr {$i+$j}]] {break}
yield $j
}
puts [info body fib]
set first [gencreate fib]
set second $first
for {set i 0} {$i < 20} {incr i} {
puts "First: [genrun first]"
if { $i > 10 } {
puts "Second: [genrun second]"
}
}SS the above code shows once again the flexibility of Tcl, but every case covered above is much more conveniently handled with a closure. For instance in Jim this is fully equivalent (but much more clear) of the above:
proc make-fib-generator {} {
lambda {} {{i 0} {j 1}} {
foreach {i j} [list $j [expr {$i+$j}]] break
return $j
}
}
set first [make-fib-generator]
set second [make-fib-generator]
for {set i 0} {$i < 20} {incr i} {
puts "First: [$first]"
if { $i > 10 } {
puts "Second: [$second]"
}
}The point of generators implemented with continuations is that they are similar to coroutines, i.e. you don't need to serialize by hand but instead you can write something like: generator foobar {
set x 0
while {$x < 1000} {
incr x
yield $x
}
}Because there is no way to leave and re-enter a function without to lost the state there is no way to do this in pure Tcl. This is *very* important with some kind of algorithms. For instance to write a generator that yields an element of a binary tree at every iteration is trivial this way, because you can write the vanilla recursive procedure to print a tree in order but substitute puts with yield, and you are done.AM Actually, with a bit extra code even that can be done - just add a list of variables in the lexical scope to the argument list of the generator proc. When generator is called it adds code in the init part to set variables with the same name to the value of those listed variables. (Oh, this sounds confusing, but the idea is just the same as in Jim closures)MAKR I have certain bad feelings about this. Having just read a couple of articles about continuation I recognized the concept already dates back into the late 70s of the last century (an overview of publications: [7]). It has not come very far since and there might be good reasons for this...
- As it seems, most developers find this concept - let's say - mind boggling. Even those who claim to understand it, admit it is difficult to grok at first. That makes it an academical concept for me, because the code I write needs to be understood by the ordinary software developer. There is no room for anything they would have to think twice, they would just prog around it...
- Also - it somehow strikes me again and again this whole concept is about reintroducing the evil goto statement, but kind of neat and nifty so none would recognise. But this could be because I still might haven't grokked it yet...
AM I would like to add two things to this rather interesting discussion, one is just a personal opinion and the other a question:
- While I respect Edsger Dijkstra - him truly being a mental giant, I do not even begin to reach his kneecaps - and I fully appreciate the dangers of unbounded use of GOTOs and similar constructs (like exceptions, break and continue :)), I do think that it is clearer to jump out of a do-loop nested three levels deep via a GOTO to handle some error condition than by setting flags or what have you. In other words: a disciplined use of GOTO can clarify your code!
- On thinking about a Tcl-only approximation to continuations, I realised that a continuation might have to have certain properties - that is it should behave as a pure function (without any side effects) given the context and other input parameters. Is my understanding correct? If not, then the side effects would limit the usefulness of such a continuation to a single instance, right?
SS I agree with you Arjen, that goto in some language is just important, like in C. Also Continuations and goto are very very unrelated, the first jumps, the second restore the full state of the program. goto is about space: the program jumps in some other place of itself. Continuations are about time, the program is restored to the state it had at the time you saved the continuation.About your question on continuations, I think your question is about generators actually. Continuations are a way to implement generators, of course, but they in the pure form don't have some specific problem with side effects. Of course if the global state changed (for example a file was modified), a continuation will not really compute what it was expected to compute when it was saved. With generators, you are right of course. While there may be some case for a generator with side effects (for example a shared global incremental ID?) most of the time the generator limits the side effects in its internal environment, i.e. the one that gets copied for every generator of this type.
fredderic: A little thought on how the ideas of this topic might be implemented script-wise...As I understand it a continuation represents breaks in a single process. You start something, stop it to do something else, then return to it later. But do they support having multiple instances of a given proc going at the same time? That, as I understand it, is what generators are better at. There, you have a kind of named instance of a procedure call which returns a value at certain points, and can be resumed independently of other calls of that same procedure. And what happens if you call it with different arguments? Or if you want to resume it with whatever arguments it was called with last time?A simple example:
proc foo {start {inc 1}} {for {set x $start} {1} {incr x $inc} {yeild $x}}The expected behaviour would be that calling foo 5 would return 5, and successive calls would return the series {6 7 8 ...}. But what to pass as the argument of successive calls?In the case of a generator, you get a token which you would call. Perhaps this is the solution then. A procedure call would normally occur in a kind of global continuation space, and would cancel any pre-existing partial run. To get the generator functionality, you would call it through a special command that sets the procedure going in its own continuation space, returning a token for it.
set seq1 [generator create foo 5]
set seq2 [generator create foo 10 -1]
for {set i 0} {i < 5} {incr i} {
lappend list [list [$seq1] [$seq2] [foo 3]]
}would result in the sequence:
{5 10 3} {6 9 3} {7 8 3} {8 7 3} {9 6 3}The advantage of doing it this way, is you could then do generator delete $seq1 $seq2 when you don't need them anymore, and regular use of the procedure would still do exactly what you'd normally expect it to do; return a value and finish. However, you could extend the concept one notch further with a generator resume ?handle? ?args? command, that would resume a previously yielded procedure call (the global one if no handle was given), optionally applying new values to the procedure arguments, allowing the procedure flow to be altered where it makes sense.
% foo 5
5
% foo 8
8
% generator resume {}
9
% generator resume {} {1 3}
12
% generator resume
15note that in this instance, changing the first argument start has no effect, however changing the inc argument takes effect on all future resumes.Though what to do when the procedure finishes? I suppose the stack would collapse, and trying to use the generator handle would cause an error. So a generator exists ?handle? command would come in handy to see if it still exists or not.Also coming to mind, are uses for a generator clone ?handle? ?args? command that would copy an existing continuation state, returning it under a new handle.
% set seq1 [generator create foo 3 2]
3
% $seq1
5
% set seq2 [generator clone $seq1]
% $seq1
7
% $seq1
9
% $seq2
7
% list [$seq1] [generator resume $seq2 {- 3}]
{11 10}
% list [$seq1] [$seq2]
{13 13}Just a bundle of ideas I had to hopefully stir things up a little, while sitting on the loo this morning. :)fredderic: A brief revision of my own mind...Creating commands all the time is wasteful. So how about this for an option...
- generator create ?proc? ?args...? does all the stack frame setup involved in calling a procedure, stopping just short of actually executing any code. It generates a unique continuation name for this call, and returns that as a token which can be passed to ...
- generator invoke $token ?args...? as an alternative to the badly named resume. The statement [foo] is therefore equivalent to [generator invoke {} foo].
- generator new ?proc? ?args...? for those who really did like the [$token] invocation style. It would basically just call [generator create], and then establish a [proc] or [interp alias] to call [generator invoke $token] for you. It would also need to do some trickery to clean up after itself if the procedure finishes, or gets ended.
- generator rename ??oldname? newname? to handle a few corner cases I ran into thinking about the concept a little further. Basically, rename an existing call stack (continuation) and return the new name. With a single argument, it would rename the current call stack to the name specified, and with neither argument, it would pick a new name along the lines of [generator create].
jkl 10-Nov-2006: My attempt to contribute to the Continuation...Several years ago, I implemented some sort of continuation in the Tcl 7.3 version. Some months later I found in the Internet an other implementation of continuations in a Tcl Interp called AgentTcl; I didn't try to understand how it was done, my impl. worked for me.Some years later, I had a look at the Tcl 8.x versions and discovered the switch from "pure strings" to the "Tcl_Obj" and also the "byte-compiler"; this didn't inspire me much to "reimplement continuations"....This summer, I made a "real try", first beginning with a "pure tcl" way-of-doing, based on "code instrumentation" (but soon I realized that this wouldn't be satisfying for a "strong" and "truly usable" feature), followed by attempt to do it as a Tcl Extension. This was better looking from the "application side" (tcl scripting), but "too bad" regarding the C code (too much duplication of Tcl core code, no chance to be maintained...). Finally I came up with an impl. as Extension requiring some changes in the Tcl C core...Further reading is available at my (specially made for the purpose of tcl continuation) web home page: [8]
DKF: The reason why continuations are difficult is that it is hard to jump back into the depths of the stack when some parts of the stack are coded in C extensions, which is pretty common in Tcl. Solving this is hard work, and would require breaking a lot of third-party code.jkl: Yes, I agree, but even with a limitation like being able to "suspend" ONLY in a "continuable stack state" (only Tcl Core function calls OR calls from Extensions modified to be cnt-compatible" on the C stack), continuations can be very useful.DKF: Sure, but that's very hard to characterize without reference to the implementation.
See http://groups.google.com/group/comp.lang.tcl/msg/b6788be58c67be4b?dmode=source
for a comp.lang.tcl posting from the the author of http://jacqkl.perso.chez-alice.fr/ , who has written a continuation implementation as a Tcl 8.x extension. jkl: to be correct, not a pure Tcl Extension, it requires a patched Tcl Core.jkl: 18-Mar-2008: My new attempt to provide Continuations in Tcl, this time as "true first-class" Tcl objects..... if interested have a look at [9]MS Not quite continuations, but see Coroutines for event-based programming
