Abstractly, a continuation is a representation of the state of an execution, and especially its "execution stack" [http://en.wikipedia.org/wiki/Continuation]. There's a delightful article explaining continuations at [http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons]. [LV] I recall a very similar concept from back in my ancient days writing BAL code on IBM/MVS systems. We called it ''concurrent'' programming back then. ''[DKF] 17-Apr-2005:'' Interesting. I just wish it was easy to apply in [Tcl], but our openness to extension, especially by [C] libraries, makes this very tricky indeed. ''[WHD] 17-Apr-2005:'' Damn. I want this. The idea of User Interface Continuations makes me drool. ''[jcw] - Yeah, me too, same reaction. DKF, yes the C stack can cause trouble, but only when C calls back into Tcl. There are probably many cases when this need not be a show stopper. I think there are ways to get there. Might be something to discuss at the tcl2005e conf - are you going to be there?'' ''[NEM] 18-Apr-2005:'' You could sort of get this to work, if we went a similar route to Stackless [Python] (from what little I know of that project [http://stackless.com] and [http://www.stackless.com/wiki/]). You'd have to change all the C-API so that instead of re-calling into the interpreter with Tcl_Eval* APIs, they instead return a TCL_CALL or similar code with some code of where to go next in the interpreter result (i.e. [trampoline]). This is very similar to the recent proposals for tail-call optimisation (which is also very connected to continuations, through continuation-passing style, CPS). Obviously, it'd be an enormous amount of work to restructure the core and many many C extensions to do things this way. Continuations rock. (I should be at tcl2005e, and would love to discuss these ideas with people). ''The core is not that far from doing it. At one point I had an experimental patch working, which copied the C stack away and back. Not sure it covered all the cases, but it was definitely very close to full contins across all of Tcl and C. -[jcw]'' ''[WHD]:'' I don't see why the C stack is an issue, based on what the article says. A [closure] consists of a stack frame and its parent stack frame, and so on recursively, it says; but a continuation, so far as I can tell, is a single stack frame. Suppose we made the rule that you could "yield" only from the body of a normal proc.... '''Oh.''' If you do it from within a while loop, say, you've got the C stack involved. '''Never mind.''' (Or is there something else I'm missing?) ''Will, the stack becomes a tree, because processing (and further nesting) can proceed at any continuation point. Yes, C loops and C re-entering Tcl (as [foreach] and [proc] do now when evaluating their bodies) is where things get tricky. -[jcw]'' '''[RHS]''' ''17Apr2005'' One of the most interesting (and informative) descriptions I've seen of the use of continuations was in the area of web programming. The programmers used them to use web pages as if they were stateful. The "process" that the web pages are involved with work linearly. Each time it needs input from the user it saves its current continuation (which contains everything about where it is in the process) in a hashtable. It then returns a web page with a form to the user, and one of the elements of the form (a hidden one, I presume) contains the key into the hash table for the current continuation. Once the user fills in the form and hits submit, the process can look up the continuation in the hash table and continue right where it left off... Only, now, it has the data it needs to continue, as provided by the form. '''[SS]''' ''18Apr2005''' Using setcontext and getcontext calls that are POSIX and AFAIK also available in some form on every platform Tcl supports allows for continuations without a stackless interpreter (basically you save the C stack too). This is how it's in plan to implement continuations into [Jim]. (this is also how [Ruby] implements continuations IIRC). [jcw] - Setcontext/getcontext (SC/GC) work by switching stacks, which is not 100% as general as being able to resume any stack frame in what can become a tree of stack frames in the general case. There's also the issue of whether lower stack frames are treated as copy-on-write or not, i.e. whether changes are isolated, when these frames are shared by multiple continuations. '''[SS]''' Sure [jcw], what SC/GC does is to make you able to implement continuations without to write a stackless interpreter. Of course the Tcl stackframes are to be copied (in the trivial implementation at least) but that's not a too big problem as it is as simple as to copy some hashtable and linked data structure. The real problem is to write a stackless interpreter and given that it's a major work and that there are other systems to reach the goal why don't use them. '''[chi] 19Apr2005:''' I mean to remember, that Ruby does its continuation and thread thingy by simply copying the whole C stack from some point remembered during initialization of the interpreter up to the context of the calling C function. Switching back to that continuation simply copies back that remembered stack. So it works within C functions. Unfortunately setcontext and getcontext seem not to be widely available :-( Perhaps the same implementation as in [Lua] could be facilitated? In Lua, C context will not be remembered, AFAIK. So a C function has to come back. But a Lua function could be suspended. This restriction seems not to be too hurting, would it? '''[SS] 19Apr2005:''' Indeed the Ruby trick may work well on many platforms where there is no support for SC/GC, about Lua, maybe the ability to suspend a function allows for coroutine and generators? Btw given that there are ways to copy the whole C stack why not :) In Tcl the ability to reactivate a single procedure may be more complex than what happens in other languages because there is [upvar]/[uplevel] that may notice the difference. Not that this is a big problem after all... the user can just avoid them. Well an interesting alternative btw. Oh.. well also there is another problem with the Lua approach, in Tcl the interpreter calls itself recursively even in the context of a single procedure! While in languages like Lua it only happens when a function calls another one I guess. '''[chi] 19Apr2005:''' That Tcl interpreter calls itself recursively should not matter at all. We would being restoring the whole C stack. So the interpreter would itself find back in the C function it was called to save the context. I had once written an extension for another language that worked pretty well. Then I had simplified the extension to make a C module out of it so that it could be used even in plain C programms. But to use such an extension in Tcl or Jim, we would need a mechanism to store the Tcl/Jim stack as well to protect it against freeing by refcount dropping to zero, though. And we would have to restore the Tcl/Jim stack as well. Further I would not like to keep secret, that there is some performance penalty taking this approach for implementing continuations, as the whole C stack has to be copied over and over again. But it should be doable. '''[SS]''' Agreed. What I mean is that "without to copy the C stack" some language is still able to do generators (ala Python), just activating the same function every time it's needed. This is sometimes possible in languages that have recursive calls to the interpreter only when functions are called, and not for every thing like [if], [while] and so on like Tcl. Btw this is poor anyway, you can't even write recursive generators. Copying the C stack, there is no problem at all of course. Also to copy the stack frames should not be hard, for instance in Jim there is just a linked list of stackframes containing an hashtable of local variables. There is just to duplicate the list and hash tables just incr-ref-counting every object representing a variable, this should be pretty easy but as you said is very slow, you don't only need to copy the C stack but the whole Tcl stack. Still I think it's nice enough as a first try just to experiment with it. After all in Jim at least I create an hash table with local vars at every function call... and still it's not as slow as you may think, so maybe even to copy the C stack and the stackframes is viable. A bit slow... bust still useful, and requires very little work. So maybe we should try ;) In Jim there are tailcalls, anonymous functions, closures. It seems like that the other big missing abstraction is continuations. [DKF]: I get very uneasy about tinkering around with the C stack. I know that it is definitely asking for trouble in Tcl's implementation as there are a number of places where we use pointers into the stack, which means that copying will not work. In theory, we could arrange for the byte-compiling of all core commands (we're actually pretty close) but that would massively raise the bar for anyone wanting to produce a third-party block-structured command in C, and there are lots of those about. Possible? Perhaps. Easy? No. Cheap to execute? Very unlikely (the stack can be multiple megabytes long). Worth it? You be the judge... [SS]: It always works even if you have pointers on the stack. You ''save'' it, don't ''use'' it while it's saved. When you restore it, it gets copied at the same place it used to be. About complexity, I think I can implement this for [Jim] as an extension without to touch the core at all. '''[chi] 19Apr2005:''' If you do, perhaps you should add refcounting to the Jim stack as well? Then it would be unnecessary to copy it. Simply IncrRefCount'ing every interesting element and then the Jim stack as well. The continuation could store a pointer to that shared stack then. Should be a bit cheaper then, no? [SS]: Yes, I think my first try will be very simple, copying everything, just to avoid complexity that may make debugging of the C-level continuations harder, for the next step I was thinking about to add the refcount to individual stackframes instead to add it to the whole stack, this way a continuation is cheap to create and even if there is some copy-on-write occurring it's likely to interest only a minor part of the stack (few stackframes) in many uses. Btw if to copy the whole stack is reasonably fast I'll be more happy to have slow continuations as an extension that does not make the core more complex, so after I've a working "vanilla" version there will be to do some benchmarking to check if it's acceptable or too slow to be used. ---- '''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 command resume $state_of_A and 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 [catch]able. 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 parameterization: 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 [http://portal.acm.org/citation.cfm?id=91622] 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. But then again, what I wrote above was mostly thinking loud; I don't claim it's a finished solution. Indeed, upon reading the call-cc reference SS gives below, it occurred to me that there ''should'' be argument passing between suspend and resume. For passing in data, we can allow '''resume''' to take an extra (optional?) argument, and specify that this argument will be the value returned by the '''suspend''' that is resumed. Passing out data is in principle no problem either, since any arguments of '''suspend''' can become embedded into the state in such a way that they are easily inspected (e.g., they could be the first list element of the state), but one probably needs some convention for how to interpret them. Ideally, '''suspend'''/'''resume''' should be possible to use for several different high level constructions (e.g. [vwait]) within the same context, and they probably need to be treated slightly differently at the catching end. ---- [SS]: I think the only good way to implement continuations in Tcl is ala [Scheme] via a '''call-cc''' procedure [http://www.eleves.ens.fr:8080/home/madore/computers/callcc.html]. 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 [catch]able, 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 articels about [continuation] I recognized the concept already dates back into the late '''70s''' of the last century (an overview of publications: [http://library.readscheme.org/page6.html]). 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 noone would recognise. But this could be because I still might haven't grokked it yet... BUT, as pointed out in the [vwait] page, many people meeting vwait for the first time assume that it introduces parallelism and need to have it pointed out that "Multiple vwaits nest". If we could introduce continuations here we could bring vwait's behaviour into line with intuitive expectations. [Colin Macleod] [NEM] The same arguments against continuations can also be made against [eval], and various other features that make Tcl powerful. It took me a little while to grok how to use the [event loop], and until I did it was hard for me to read event-oriented code. The same can be said for continuations: it takes a little while to get used to them, but you can build some incredibly powerful abstractions with them. If your organisation thinks that their developers won't be able to understand them, then you can always use coding standards and code reviews to outlaw their use. What exactly is an "ordinary software engineer"? Your statement seems dangerously close to saying that a software engineer should never be introduced to a new concept, for fear of upsetting their delicate minds! :) Regarding "goto": continuations are in some ways like goto, but they are first-class (goto labels are not), and they are parameterized (they are [closures]/procedures). So, you can think of them as a much more controlled goto. [SS]: [MAKR] wrote ''It has not come very far since and there might be good reasons for this...'': sure, most programmers are not good. The same applies to anonymous functions, closures, and many non trivially algol-like things in programming. This is also the same reason why [Java] is a very used language this days. ---- [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. ---- [Category Concept]