Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

About CONTINUATIONS

 [1/16] from: robbo1mark:aol at: 19-Feb-2002 13:39


from the REBOL 1.x user guide ..... Continuation The catch function allows you to return to a specified point in a script using a method called continuation. A continuation is a saved point in the flow of execution that can be called and returned to at a later time. Think of it as a bookmark that saves your location and current context. Continuations are first class. They can be stored in variables, passed as arguments, and returned from functions. As such, they provide a powerful mechanism for advanced scripting in REBOL &#8212; especially for handling operations such as exceptions. To use catch you provide a symbol and a block: catch symbol body The symbol is used as the name for a new function which holds the continuation point. This function becomes available within the context of the body block, where it can be called to return to the point just after the catch. Think of it as a throw function if you are familiar with that concept from other languages. It takes one argument: a value which will be returned as the result of the catch. print catch 'throw [ loop 100 [ if (random 10) > 5 [throw "hit"] ] miss ] The symbol throw is used here as the name of the continuation function. When it is applied, its argument is used as the return from its associated catch. In the above example, its behavior is identical to a return function. Non-local Return The function named by catch is local to the block passed to catch. However, there may be times when you want to return from functions called outside the block. To do so, define a word outside the context of the block to hold the continuation function. rand-it: func [num] [ loop num [ if (random num) > (num / 2) [resume "hit"] ] miss ] print catch 'throw [ resume: :throw rand-it 100 ] Here the word resume is given the function value of throw and is used outside the block as a non-local return to the catch. True Continuation With the indefinite extent concept discussed later, continuations can be preserved even beyond the return point of the catch. If after the example above, you were to write the line: resume "test" you would return to the same point as before &#8212; just after the catch &#8212; and the "test" string would be passed to the print function. Note that the entire context of the catch is preserved. Here is another example: times: func [num] [num * catch 'here [resume-times: :here 1]] result: times 1 print result if result < 100 [resume-times (result * 3)] In this example, the catch marks the return point within the function times. When the resume-times function is applied, it passes a new value back to the multiplication. Notice that even the return point from times is preserved! The assignment to result and print result are all done again, because they follow the initial call to times. ........ end of snip .......... I started using REBOL just on the cusp of the version 2.x changeover, Brian Hawley & Daan Oosterveld did have old windows versions of REBOL 1.x but Iam not sure if they still do or if they're even still on this list. LADISLAV, I've studied Continuations A LOT recently, albeit the Scheme CALL-WITH-CURRENT-CONTINUATION ( abreviated Call/cc ) type and although it appears the REBOL 1.x type of conitinuations are not as powerful as Scheme I THINK IT'S A SHAME REBOL lost these capabilities along with proper tail recursion. If anybody wants to learn more about this then go to http://www.scheme.com where Kent Dybvig has LOADS of information and literature about continuations, proper tail recursion etc. as well as an excellent freely available Scheme implmentation to experiment these with called PetiteChez Scheme. MZScheme also has these capabilities and is GPL free software, MZScheme is the under the hood Scheme in the DR-Scheme programming environment. Stackless-Python also has continuations and proper tail recursion and is a patch to implement these capabilities into regular Python. If anybody needs anymore info or explanations or URL's etc. just let me know I've got tonnes of literature on this here. cheers, Mark Dickson

 [2/16] from: chaz:innocent at: 20-Feb-2002 0:12


On 17-Jun-2000 Brian Hawley had this to say about Continuations http://www.rebol.org/userlist/archive/205/393.html Continuations: Scheme has them (base of its execution model); REBOL dropped these too when it switched to a stack engine. Continuations don't make much sense with a stack engine - they only work well when the execution model is continuation-based. If you can't refactor your code to use callbacks or some such, you probably don't understand it well enough to be programming with continuations. Take a look at Icon - its goal-directed evaluation beats continuations any day of the week ----- Original Message ----- From: <[Robbo1Mark--aol--com]> To: <[rebol-list--rebol--com]> Sent: Tuesday, February 19, 2002 10:39 AM Subject: [REBOL] About CONTINUATIONS from the REBOL 1.x user guide ..... Continuation The catch function allows you to return to a specified point in a script using a method called continuation. A continuation is a saved point in the flow of execution that can be called and returned to at a later time. Think of it as a bookmark that saves your location and current context. Continuations are first class. They can be stored in variables, passed as arguments, and returned from functions. As such, they provide a powerful mechanism for advanced scripting in REBOL &#8212; especially for handling operations such as exceptions. To use catch you provide a symbol and a block: catch symbol body The symbol is used as the name for a new function which holds the continuation point. This function becomes available within the context of the body block, where it can be called to return to the point just after the catch. Think of it as a throw function if you are familiar with that concept from other languages. It takes one argument: a value which will be returned as the result of the catch. print catch 'throw loop 100 [ if (random 10) > 5 [throw "hit"] ] miss ] The symbol throw is used here as the name of the continuation function. When it is applied, its argument is used as the return from its associated catch. In the above example, its behavior is identical to a return function. Non-local Return The function named by catch is local to the block passed to catch. However, there may be times when you want to return from functions called outside the block. To do so, define a word outside the context of the block to hold the continuation function. rand-it: func [num] loop num [ if (random num) > (num / 2) [resume "hit"] ] miss ] print catch 'throw resume: :throw rand-it 100 ] Here the word resume is given the function value of throw and is used outside the block as a non-local return to the catch. True Continuation With the indefinite extent concept discussed later, continuations can be preserved even beyond the return point of the catch. If after the example above, you were to write the line: resume "test" you would return to the same point as before &#8212; just after the catch &#8212; and the "test" string would be passed to the print function. Note that the entire context of the catch is preserved. Here is another example: times: func [num] [num * catch 'here [resume-times: :here 1]] result: times 1 print result if result < 100 [resume-times (result * 3)] In this example, the catch marks the return point within the function times. When the resume-times function is applied, it passes a new value back to the multiplication. Notice that even the return point from times is preserved! The assignment to result and print result are all done again, because they follow the initial call to times. ........ end of snip .......... I started using REBOL just on the cusp of the version 2.x changeover, Brian Hawley & Daan Oosterveld did have old windows versions of REBOL 1.x but Iam not sure if they still do or if they're even still on this list. LADISLAV, I've studied Continuations A LOT recently, albeit the Scheme CALL-WITH-CURRENT-CONTINUATION ( abreviated Call/cc ) type and although it appears the REBOL 1.x type of conitinuations are not as powerful as Scheme I THINK IT'S A SHAME REBOL lost these capabilities along with proper tail recursion. If anybody wants to learn more about this then go to http://www.scheme.com where Kent Dybvig has LOADS of information and literature about continuations, proper tail recursion etc. as well as an excellent freely available Scheme implmentation to experiment these with called PetiteChez Scheme. MZScheme also has these capabilities and is GPL free software, MZScheme is the under the hood Scheme in the DR-Scheme programming environment. Stackless-Python also has continuations and proper tail recursion and is a patch to implement these capabilities into regular Python. If anybody needs anymore info or explanations or URL's etc. just let me know I've got tonnes of literature on this here. cheers, Mark Dickson

 [3/16] from: robbo1mark:aol at: 20-Feb-2002 4:30


Chaz, What point are you making in relation to REBOL? Icon's Goal Directed Evaluation is based on backtracking which requires every part of the expression to have a success or failure continuation, so the continuation model *IS* there in ICON. ICON also has generators & co-expressions which are based on the continuation model. In a message dated Wed, 20 Feb 2002 3:21:09 AM Eastern Standard Time, "chaz" <[chaz--innocent--com]> writes:

 [4/16] from: chaz:innocent at: 22-Feb-2002 1:03


From: <[Robbo1Mark--aol--com]>
>What point are you making in relation to REBOL?
I apologize for being so obscure, please let me try again. There may indeed be something of value with regards to REBOL and continuations, but speaking as an observer, only, I've seen little evidence of interest in continuations, in this community. http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/msg00679.html This posting is apparently by Joe Marshall the man who put continuations in REBOL 1.0 in the first place. If anyone should be an strong advocate for having continuation is REBOL he would be that person, but in fact poster merely states that continuations provide some advantages in coding the language, but in general they are unnecessary, and that he himself doesn't care whether or not a language contains them. ...The fact of the matter is that first-class continuations *aren't* used very often in `standard' code, and that CATCH/THROW, structured error handling, and a thread package will cover virtually all practical of first-class continuations. For this reason I don't much care if a language has first-class continuations or not. Sure, it is a bonus, and I *always* put them in to languages that I implement (REBOL 1.0 has first-class continuations), and they make writing the error handler and debugger far, far easier, but the end user doesn't care..."

 [5/16] from: joel:neely:fedex at: 22-Feb-2002 6:36


Hello, Chaz, Not that it changes your point... chaz wrote:
> http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/msg00679.html > This posting is apparently by Joe Marshall the man who put > continuations in REBOL 1.0 in the first place... > ... poster merely states ... >
That post was anonymous. It's not clear to me that it was from Joe Marshall, especially since the footnotes reference an earlier post from Marshall which seems less flame-bait-like: One cost of call-with-current-continuation is the hurdle it introduces to acceptance of the language. People think `oooh, cwcc is scary and bizarre, I don't want to hack scheme because I need to understand cwcc in toto before I write *anything*'. (quoted in its entirety). Cruising back further Marshall also opined: I may be inviting the wrath of other schemers, but I don't consider call-with-current-continuation to be essential to scheme. At any rate, I think your conclusion is absolutely correct:
> There may indeed be something of value with regards to REBOL > and continuations, but speaking as an observer, only, I've > seen little evidence of interest in continuations, in this > community. >
But it seems to me that your statement expresses a more general truth about the way communities respond to unfamiliar ideas. I've seen little evidence of interest in REBOL in my local Linux community (despite having made two presentations on REBOL to the local users' group myself). However, at last night's meeting we had a rambling discussion about wiki engines, programming, and other topics (including .NET and even more bizarre things). When I hit www.rebol.org and showed a wiki and a web server or two, each in only a page or two of REBOL, one of the more experienced alpha-geek types said (essentially), "Hmmm. I'm gonna have to look at that." It seems to me that most folks view learning something new as a cost. The best way to motivate the learning is to show them how they'll get a return on that investment. Unless/until someone believes that there's something that (s)he can do with REBOL more "cheaply" than with his/her current favorite language, (s)he just won't bother. Of course, it has to be something which (s)he actually *cares* about doing, and the effort of learning REBOL is counted as part of the cost comparison! To return to your comment, as long as a language (e.g. REBOL) has enough features (or is used for small/simple enough tasks) that the benefits aren't perceived, most folks won't bother even to learn all of what's *in* the language, much less ask for capabilities that aren't there (especially highly abstract ones such as continuations). Finally, to tie this back to the "Worse Is Better" vs. "The Right Thing" discussion... Worse Is Better drives language design and implementation based on what features the users ask for, or are perceived as willing to deal with. It would say, "Few users care about that feature, so we'll take it out (or not bother to put it in at all)." The Right Thing drives language design and implementation based on clearly-thought-out conceptual models and goals. It would say, "Few users understand that feature, so we need to communicate to them how important/useful it is." -jn- -- ; sub REBOL {}; sub head ($) {@_[0]} REBOL [] # despam: func [e] [replace replace/all e ":" "." "#" "@"] ; sub despam {my ($e) = @_; $e =~ tr/:#/.@/; return "\n$e"} print head reverse despam "moc:xedef#yleen:leoj" ;

 [6/16] from: robbo1mark:aol at: 24-Feb-2002 15:27


Joel / Chaz, I'm not sure about this one as I don't have first hand knowledge, but did Joe Marshall put Continuations in REBOL 1.x or were they part of Carl Sassenraths original design for the REBOL language? Even if Joe Marshall was lead implementor I'm certain that nothing would go in without Carl's approval. If they were deemed an important and interesting enough feature to be in the first release of the product then presumably this was the view taken by the lead implementor AND language designer. Whilst continuations are a tricky concept to come to terms with initially and joe average user won't bother to learn about them it doesn't mean that they are not a desirable language feature. In my opinion they ARE definitely on a list of desirable language features. Do I wish they were still in REBOL? probably YES. Continuations make loads of intersting and advanced things possible without detracting anything away from the user / programmer who doesn't use or understand them. Scheme and Common Lisp both have them and so does Stackless Python and ML. There is loads of interesting Comp Sci literature on continuations and they are a well understood and used feature for advanced programming in the above languages, especially in the field of modelling concurrency and parallel programming. They interest me that's why I wish REBOL still had them. Having read Joe Marshall's cons regarding continuations I don't think it was necessary to throw the baby out with the bath water in the change over to REBOL 2.x when we lost continuations and tail call optimisation. From what I can see they didn't fully explore the continuation model to it's full extent, Joe Marshall states as such. Iam sure there is a LOT they could have learned from advanced Scheme & ML implementations which STILL have these features. These languages are not SO fundamentally different from REBOL which is at it's core a prefix functional language. This is all theoretical but raises some interesting issues regarding language design and implementation. I was a bit disturbed that Joe Marshall stated that with his implementation "nobody else in the company could extend the interpreter.." SURELY NOT? What about Carl Sassenrath? Also "You need a degree in Comp. Sci from a few select places to really understand all this.." IS THAT A PROBLEM? Is there anything wrong with that? I don't think these points are valid, the literature is readily available that discusses and has SOLVED a lot of these thorny problems. SCHEME and ML have efficient interpreters AND optimising compilers and fast incremental compilers using various implementation techniques which explore and attempt to / SOLVE the problems Joe Marshall highlighted in relation to REBOL. The solutions *ARE* there if you take the time to learn and understand them. However I'm sure Carl & RT had other goals for REBOL 2.x like "speed" which they considered to be of higher precedence and importance. It's a pity when a language loses capabilities or features as it closes of some doors. Can a Language Designer / Implementor foresee all the possible uses or interesting applications of their creation? Of course not! Maybe the Comp. Sci people at those "select places" could provide some insights into solving those problems and we get back the languages feature that were lost! That's my wish for REBOL 3.x cheers, Mark Dickson In a message dated Fri, 22 Feb 2002 8:03:52 AM Eastern Standard Time, Joel Neely <[joel--neely--fedex--com]> writes:

 [7/16] from: holger:rebol at: 24-Feb-2002 17:34


On Sun, Feb 24, 2002 at 03:27:39PM -0500, [Robbo1Mark--aol--com] wrote:
> Whilst continuations are a tricky concept to come to terms with initially and joe average user won't bother to learn about them it doesn't mean that they are not a desirable language feature. In my opinion they ARE definitely on a list of desirable language features. > Do I wish they were still in REBOL? probably YES.
Ok, since you are not going to stop complaining until someone from RT makes a statement, I hereby do so :-). Continuations were not "removed" by us. They became a victim of a complete reimplementation of REBOL, by necessity. There was never an option of keeping continuations and still advance REBOL in the way it has happened, and there is still no such option. In order to understand how continuations fit into a language interpreter we first need to examine the different ways an interpreter can be constructed. There are three fundamental ways of doing this: 1) Using a Stack Machine (SM). This is what REBOL 2.x does. In a stack machine-based interpreter the calling path through the interpreted program somewhat corresponds to the calling path within the interpreter, i.e. whenever a function is called in the program, the interpreter also calls a function within the interpreter, to evaluate the function. Similarly for expressions etc. Recursive interpretation is handled by recursively calling interpreter functions, i.e. such functions have to be reentrant. This means that in an SM-based interpreter a significant portion of the "state" of the interpreter is kept implicitly, on the stack or in local variables, CPU registers etc., i.e. it is not available at the language level. Because of that continuations (which require all state information to be explicit, to allow it to be manipulated at the language level) cannot be implemented in a purely SM-based interpreter. 2) Using a Finite State Machine (FSM). This is what REBOL 1.x did. In an FSM-based interpreter all interpreter state is stored explicitly. The CPU stack is hardly used at all, and the interpreter does not recurse on itself. Rather recursive evaluation is performed by extending the size of the state structure. This can allow the interpreter stack to become a first-class datatype at the language level. 3) A combination. See below. The distinction between FSM-based and SM-based systems is not unique to interpreters. You will find a similar distinction in other places. For example in an application (top-down or event-driven, i.e. bottom-up), and in different pieces of operating systems (filesystem, network stack, GUI engine etc.), so anyone who has some non-trivial experience in software development should be familiar with the significance of this (and the problems that occur when both models "clash" in some way). So what are the advantages and disadvantages of both methods, when applied to interpreters ? FSM-based interpreters tend to be more flexible. Some features, such as continuations, are only available in FSM-based interpreters, because they require explicit access to the interpreter state. Other features, such as threading and coroutines are much easier to implement in FSM-based interpreters. FSM-based interpreters integrate better with environments which are FSM-based as well. For instance if the OS is FSM-based, such as PalmOS, then having an FSM-based interpreter tends to allow better integration, smoother user interaction etc. On the other hand SM-based interpreters integrate better with operating systems that are SM-based as well, which pretty much covers all modern operating systems, with the exception of parts of the GUI engine. In particular operating systems which rely heavily on a "top down with callbacks" model, like Windows, integrate better with SM-based interpreters, if those callbacks are supposed to be exposed at the language level in some way. FSM-based interpreters usually cannot adequately expose OS features that are SM-based at the language level. For instance, REBOL exposes OS library calls in /Pro and /Command, with callbacks in the soon-to-be-released new View/Pro and Command versions. This would be pretty much impossible to do with an FSM-based environment. To understand why, just imagine that within the callback a new continuation chain branches off, the main branch returns, through the OS function, and then the program decides to continue within the continuation, and finally return through the OS function again. Obviously that is impossible, because the stack frame of the OS function no longer exists. A large number of features of contemporary operating systems rely on a stack frame, in one way or another, i.e. exposing those features at the language level is only possible by interpreters which correlate stack frame to interpreter state. An FSM-based interpreter does not do that, so it cannot expose those features. FSM-based interpreters are inherently slower and usually require more memory: C compilers, CPUs etc. have been designed with SMs in mind and highly optimize SM-related operations, which are for the most part standardized for each platform these days (stack frames, calling conventions etc.). On the other hand FSM designs always require explicit FSM code, more elaborate memory management etc., and cannot make use of the existing resources as well. For instance where an SM-based interpreter can implicitly store the result of a condition in a CPU flag and act on it immediately (conditional jump), an FSM-based interpreter needs to allocate a data structure for it and store the result as a flag, then loop back in the interpreter, examine the state, and finally examine the flag, remove it from the state, and act on it. That is an order of magniture more work. FSM-based interpreters are usually much more difficult to write and maintain, just like event-driven programs tend to be more difficult to work with than procedural programs (with few exceptions, like class-based GUI engines). That is probably what Joe Marshall's comments regarding qualifications and requirements for developers comes from. The side effect of this is that FSM-based interpreters tend to be less agile: development and testing take more planning and effort. Changes happen more slowly. 3) Finally, here is that third method I mentioned above: It is possible for an interpreter to use a "hybrid" method of FSM and SM, by using a stack machine most of the time, and capturing pending information within an on-the-fly continuation structure. The main advantage of this method is that most of the time, performance is about as good as you can expect from an SM-based interpreter. The problem is that this is usually not practical, at least not in non-trivial interpreters. That's because there are only two ways of doing it: explicitly, by unrolling and recreating function calls, or by "hacking it in", using assembly language stubs that analyze and synthesize stack frames. Even though some languages have successfully used both methods in some limited scope and on selected platforms, they are not suitable for REBOL. Explicit unrolling is infeasible because it would have to be supported in too many places. REBOL/Core has around 100 natives. Add to that actions and ops, and it becomes several hundred. Adding code to serialize the state to all of those functions would take months to implement and probably years to test. The "hack" solution is easier to do on some platforms, but very platform-specific, i.e. not suitable for REBOL. Besides, even though continuation could be supported either way, this would still not solve the problem that continuations are fundamentally incompatible with stack-based OS features, such as library calls with callbacks.
> Continuations make loads of intersting and advanced things possible without detracting anything away from the user / programmer who doesn't use or understand them.
Yes, and they also make loads of interesting and advanced things IMpossible. In an error!-based error handling scheme such as REBOL it is possible to safely handle error conditions even with libraries and callbacks, and with event-driven programs. With continuations this would be impossible. You would end up with an environment which offers multiple features, but without the ability to use them in combination. From a modularity point of view that is much worse than offering a smaller set of features with full orthogonality.
> Scheme and Common Lisp both have them and so does Stackless Python and ML. There is loads of interesting Comp Sci literature on continuations and they are a well understood and used feature for advanced programming in the above languages, especially in the field of modelling concurrency and parallel programming.
Yes, that's the point, really. Continuations are a somewhat theoretical concept. They severely clash with how operating systems and runtime systems are designed. This is why they are only implemented in languages which are academic in nature. When a language matures to the point that it becomes interesting beyond the academic realm, other considerations, such as performance, integration with existing environments etc. become more important. This kind of maturing is exactly what happened in the transition from REBOL 1.x to 2.x.
> From what I can see they didn't fully explore the continuation model to it's full extent, Joe Marshall states as such. Iam sure there is a LOT they could have learned from advanced Scheme & ML implementations which STILL have these features. These languages are not SO fundamentally different from REBOL which is at it's core a prefix functional language.
That's completely besides the point. Continuations have nothing to do with the language model, only with the interpreter model.
> This is all theoretical but raises some interesting issues regarding language design and implementation.
Yes, exactly. Implementation more than design. The only aspect interesting for design is whether continuations should be first class.
> I was a bit disturbed that Joe Marshall stated that with his implementation "nobody else in the company could extend the interpreter.." SURELY NOT? What about Carl Sassenrath? > Also "You need a degree in Comp. Sci from a few select places to really understand all this.." IS THAT A PROBLEM? Is there anything wrong with that?
Don't take these comments too literally :-). Joe was just trying to make a point. The current interpreter is an order of magnitude easier to maintain, extend and test.
> The solutions *ARE* there if you take the time to learn and understand them.
Sort of. Solutions are not universal. They only apply to certain domains. For instance if you sacrifice OS interaction, or graphics, or networking or certain other things, then this may allow you to make certain implementation changes that allow the implementation of other features. Java demonstrates this nicely: it has one interesting and important feature: operational safety and isolation of the virtual machine from its environment. It pays a high price though: no pointers, no unions, no arrays of structures, very limited casting, extremely high numbers of run-time tests, and thus overall bad performance. Some say, in retrospect, that this was too high a price. What this illustrates is that just because a solution is theoretically possible and even has been shown to work well in one domain does not mean that is is even applicable in another one, and some choices are mutually exclusive. That's why there IS more than one language you can choose from. Keeping continuations in REBOL would have prevented REBOL from entering certain domains. For instance /View would have been impossible, for performance reasons. There is the library/callback issue. There is agility, integration with existing software packages and libraries. There are other issues... And to answer the inevitable second question, regarding tail recursion optimization (or more generally, tail call optimization): First of all, we need to distinguish between the interpreter and compiler case, because the way they deal with tail call optimization is quite different: In a compiler the optimization is not performed at run time, but at compile time, and it involves unrolling the stack frame before making the final call. Sometimes that is as easy as replacing "jsr...; rts" with "jmp", but arguments make it more tricky. In any case, there is generally NO reason NOT to do it. The only price you pay is, perhaps, slightly longer compilation time. The resulting code is usually shorter, quicker and needs less memory, i.e. it is better . In an interpreter the situation is different. The interpreter needs to determine at run time whether a call is a "tail call" and allows optimization. Because of that there is a trade-off: the benefit of successful tail call optimization has to be weighed against the additional effort to determine, dynamically, whether such optimization is possible. If that determination on the average takes up more CPU time or memory than the actual optimization saves, then such an optimization should not be implemented. Compilers obviously do not have that problem. I do not have any hard data regarding that particular trade-off, but my impression is that in "normal" programs (i.e. programs that were not written particularly to prove a point, demonstrate a concept etc., in the academic domain), it is very rare to have tail calls that benefit from optimization, so I tend to suspect that adding tail call optimization may, in most cases, have a detrimental effect. It would certainly be possible to add tail call optimization back in, although it is somewhat more difficult to do in an SM-based interpreter than an FSM-based interpreter (because it is not enough to just prune the state structure -- the stack has to be unrolled, too). However I could think of probably dozens of feature requests for REBOL that I would consider more important, benefitting more users, and resulting in more significant improvements, so don't count on tail call optimization to be very high on our priority list :-). -- Holger Kruse [kruse--nordicglobal--com]

 [8/16] from: koopmans:itr:ing:nl at: 25-Feb-2002 10:10


OK, my 2 eurocents ;-)
> Ok, since you are not going to stop complaining until someone from RT makes > a statement, I hereby do so :-). > > Continuations were not "removed" by us. They became a victim of a complete > reimplementation of REBOL, by necessity. There was never an option of > keeping continuations and still advance REBOL in the way it has happened, > and there is still no such option. >
What is interesting is the necessity. Speed? Features? Below you suggest that certain features would be impossible otherwise, such as View or library. We'd take that as the necessity for now.
> In order to understand how continuations fit into a language interpreter we > first need to examine the different ways an interpreter can be constructed.
<<quoted lines omitted: 12>>
> to be explicit, to allow it to be manipulated at the language level) cannot > be implemented in a purely SM-based interpreter.
OTOH REBOL exposes a lot of 'external' information to be fully reflexive. This gets you close to the point where you want to be in most cases. Especially combined with catch/throw.
> 2) Using a Finite State Machine (FSM). This is what REBOL 1.x did. In an > FSM-based interpreter all interpreter state is stored explicitly. The CPU
<<quoted lines omitted: 10>>
> development should be familiar with the significance of this (and the > problems that occur when both models "clash" in some way).
Well said. But the clashing is often solvable (otherwise you wouldn't have GUI engines, and VI ruled ;-)
> So what are the advantages and disadvantages of both methods, when applied > to interpreters ?
<<quoted lines omitted: 7>>
> then having an FSM-based interpreter tends to allow better integration, > smoother user interaction etc.
Yes. But better is not the same as impossible! Harder and with different trade-offs, yes. More or less feasible, yes. Impossible, no. See below.
> On the other hand SM-based interpreters integrate better with operating > systems that are SM-based as well, which pretty much covers all modern
<<quoted lines omitted: 17>>
> stack frame to interpreter state. An FSM-based interpreter does not do > that, so it cannot expose those features.
First, I like the soon-to-be-released part ;-) But then... there are abstraction layers possible (at a cost, yes). MzScheme clearly shows that you can have all sorts of OS features available in a continuation-based language (proof by counter-example ;-) This is not to say integration is easy, of course. Or desirable. *Cannot* is perhaps a bit too .... stated? Desirable with regards to all kinds of cost factors is a different thing. What I read between the lines is that given the RT constraints (little manpower, lots of real-life features, agressive cross-platformness) FSM is not the best choice.
> FSM-based interpreters are inherently slower and usually require more > memory: C compilers, CPUs etc. have been designed with SMs in mind and
<<quoted lines omitted: 8>>
> the interpreter, examine the state, and finally examine the flag, remove it > from the state, and act on it. That is an order of magniture more work.
Yes. But most problems to day can be solved pretty fast with lots of memory. Of course this is a recurring argument, as hardware always gets faster, and there 's is a turnaround point for some kinds of application every x years. For FSM based interpreters (possibly with C-code generation) that point has passed. That is not to deny that efficiency is a good thing and that a more efficient environment is always desirable. Especially if you have a product like Express coming, which has to be able to run on PDA's (probably) as well. Different cost metrics, again.
> FSM-based interpreters are usually much more difficult to write and > maintain, just like event-driven programs tend to be more difficult to work
<<quoted lines omitted: 3>>
> of this is that FSM-based interpreters tend to be less agile: development > and testing take more planning and effort. Changes happen more slowly.
So... higher cost (I know, I keep repeating)....
> 3) Finally, here is that third method I mentioned above: It is possible for > an interpreter to use a "hybrid" method of FSM and SM, by using a stack
<<quoted lines omitted: 115>>
> significant improvements, so don't count on tail call optimization to be > very high on our priority list :-).
And there is something else to realize: let's take REBOL and Scheme as examples. Both allow for easy semantic prototyping of other languages, sublanguages etc. The important thing is "easy" h

 [9/16] from: brett:codeconscious at: 25-Feb-2002 20:12


Thank you for spending your time to post such an informative message Holger. Very educational :) Brett.

 [10/16] from: chaz:innocent at: 25-Feb-2002 0:24


Holger's email has much to ponder. His article (hope he submits it to REBOLforces!) helps explain why RT chose to base the REBOL interpreter on Stack Machine (SM) technology, rather than going with Finite State Machine (FSM). Because they went that way, REBOL developers gain 1) REBOL's legendary compatibility with major operating systems, unlike with FSM 2) more efficient use of memory, than with FSM 3) error handling of diverse REBOL features like /Command libraries and /View events, apparently not possible with FSM 4) better support from RT because the REBOL interpreter is easier for RT to maintain But of course "For every door that opens, a door closes." Because RT chose SM instead of FSM, we get 1) greater incompatibility with PalmOS 2) no continuations 3) a much lower probability that RT will implement tail recursive optimization, a feature which doesn't apparently make sense to implement on an interpreter like REBOL, anyway. We also get a nice slam on Java, as an extra bonus! Now if only RT folks would show up on this list more often. Articles like this go a long way towards really deepening developer understanding. ----- Original Message ----- From: "Holger Kruse" <[holger--rebol--net]> To: <[rebol-list--rebol--com]> Sent: Sunday, February 24, 2002 5:34 PM Subject: [REBOL] Re: About CONTINUATIONS On Sun, Feb 24, 2002 at 03:27:39PM -0500, [Robbo1Mark--aol--com] wrote:
> Whilst continuations are a tricky concept to come to terms with initially
and joe average user won't bother to learn about them it doesn't mean that they are not a desirable language feature. In my opinion they ARE definitely on a list of desirable language features.
> Do I wish they were still in REBOL? probably YES.
Ok, since you are not going to stop complaining until someone from RT makes a statement, I hereby do so :-). Continuations were not "removed" by us. They became a victim of a complete reimplementation of REBOL, by necessity. There was never an option of keeping continuations and still advance REBOL in the way it has happened, and there is still no such option. In order to understand how continuations fit into a language interpreter we first need to examine the different ways an interpreter can be constructed. There are three fundamental ways of doing this: 1) Using a Stack Machine (SM). This is what REBOL 2.x does. In a stack machine-based interpreter the calling path through the interpreted program somewhat corresponds to the calling path within the interpreter, i.e. whenever a function is called in the program, the interpreter also calls a function within the interpreter, to evaluate the function. Similarly for expressions etc. Recursive interpretation is handled by recursively calling interpreter functions, i.e. such functions have to be reentrant. This means that in an SM-based interpreter a significant portion of the state of the interpreter is kept implicitly, on the stack or in local variables, CPU registers etc., i.e. it is not available at the language level. Because of that continuations (which require all state information to be explicit, to allow it to be manipulated at the language level) cannot be implemented in a purely SM-based interpreter. 2) Using a Finite State Machine (FSM). This is what REBOL 1.x did. In an FSM-based interpreter all interpreter state is stored explicitly. The CPU stack is hardly used at all, and the interpreter does not recurse on itself. Rather recursive evaluation is performed by extending the size of the state structure. This can allow the interpreter stack to become a first-class datatype at the language level. 3) A combination. See below. The distinction between FSM-based and SM-based systems is not unique to interpreters. You will find a similar distinction in other places. For example in an application (top-down or event-driven, i.e. bottom-up), and in different pieces of operating systems (filesystem, network stack, GUI engine etc.), so anyone who has some non-trivial experience in software development should be familiar with the significance of this (and the problems that occur when both models "clash" in some way). So what are the advantages and disadvantages of both methods, when applied to interpreters ? FSM-based interpreters tend to be more flexible. Some features, such as continuations, are only available in FSM-based interpreters, because they require explicit access to the interpreter state. Other features, such as threading and coroutines are much easier to implement in FSM-based interpreters. FSM-based interpreters integrate better with environments which are FSM-based as well. For instance if the OS is FSM-based, such as PalmOS, then having an FSM-based interpreter tends to allow better integration, smoother user interaction etc. On the other hand SM-based interpreters integrate better with operating systems that are SM-based as well, which pretty much covers all modern operating systems, with the exception of parts of the GUI engine. In particular operating systems which rely heavily on a "top down with callbacks" model, like Windows, integrate better with SM-based interpreters, if those callbacks are supposed to be exposed at the language level in some way. FSM-based interpreters usually cannot adequately expose OS features that are SM-based at the language level. For instance, REBOL exposes OS library calls in /Pro and /Command, with callbacks in the soon-to-be-released new View/Pro and Command versions. This would be pretty much impossible to do with an FSM-based environment. To understand why, just imagine that within the callback a new continuation chain branches off, the main branch returns, through the OS function, and then the program decides to continue within the continuation, and finally return through the OS function again. Obviously that is impossible, because the stack frame of the OS function no longer exists. A large number of features of contemporary operating systems rely on a stack frame, in one way or another, i.e. exposing those features at the language level is only possible by interpreters which correlate stack frame to interpreter state. An FSM-based interpreter does not do that, so it cannot expose those features. FSM-based interpreters are inherently slower and usually require more memory: C compilers, CPUs etc. have been designed with SMs in mind and highly optimize SM-related operations, which are for the most part standardized for each platform these days (stack frames, calling conventions etc.). On the other hand FSM designs always require explicit FSM code, more elaborate memory management etc., and cannot make use of the existing resources as well. For instance where an SM-based interpreter can implicitly store the result of a condition in a CPU flag and act on it immediately (conditional jump), an FSM-based interpreter needs to allocate a data structure for it and store the result as a flag, then loop back in the interpreter, examine the state, and finally examine the flag, remove it from the state, and act on it. That is an order of magniture more work. FSM-based interpreters are usually much more difficult to write and maintain, just like event-driven programs tend to be more difficult to work with than procedural programs (with few exceptions, like class-based GUI engines). That is probably what Joe Marshall's comments regarding qualifications and requirements for developers comes from. The side effect of this is that FSM-based interpreters tend to be less agile: development and testing take more planning and effort. Changes happen more slowly. 3) Finally, here is that third method I mentioned above: It is possible for an interpreter to use a "hybrid" method of FSM and SM, by using a stack machine most of the time, and capturing pending information within an on-the-fly continuation structure. The main advantage of this method is that most of the time, performance is about as good as you can expect from an SM-based interpreter. The problem is that this is usually not practical, at least not in non-trivial interpreters. That's because there are only two ways of doing it: explicitly, by unrolling and recreating function calls, or by "hacking it in", using assembly language stubs that analyze and synthesize stack frames. Even though some languages have successfully used both methods in some limited scope and on selected platforms, they are not suitable for REBOL. Explicit unrolling is infeasible because it would have to be supported in too many places. REBOL/Core has around 100 natives. Add to that actions and ops, and it becomes several hundred. Adding code to serialize the state to all of those functions would take months to implement and probably years to test. The hack solution is easier to do on some platforms, but very platform-specific, i.e. not suitable for REBOL. Besides, even though continuation could be supported either way, this would still not solve the problem that continuations are fundamentally incompatible with stack-based OS features, such as library calls with callbacks.
> Continuations make loads of intersting and advanced things possible
without detracting anything away from the user / programmer who doesn't use or understand them. Yes, and they also make loads of interesting and advanced things IMpossible. In an error!-based error handling scheme such as REBOL it is possible to safely handle error conditions even with libraries and callbacks, and with event-driven programs. With continuations this would be impossible. You would end up with an environment which offers multiple features, but without the ability to use them in combination. From a modularity point of view that is much worse than offering a smaller set of features with full orthogonality.
> Scheme and Common Lisp both have them and so does Stackless Python and ML.
There is loads of interesting Comp Sci literature on continuations and they are a well understood and used feature for advanced programming in the above languages, especially in the field of modelling concurrency and parallel programming. Yes, that's the point, really. Continuations are a somewhat theoretical concept. They severely clash with how operating systems and runtime systems are designed. This is why they are only implemented in languages which are academic in nature. When a language matures to the point that it becomes interesting beyond the academic realm, other considerations, such as performance, integration with existing environments etc. become more important. This kind of maturing is exactly what happened in the transition from REBOL 1.x to 2.x.
> From what I can see they didn't fully explore the continuation model to
it's full extent, Joe Marshall states as such. Iam sure there is a LOT they could have learned from advanced Scheme & ML implementations which STILL have these features. These languages are not SO fundamentally different from REBOL which is at it's core a prefix functional language. That's completely besides the point. Continuations have nothing to do with the language model, only with the interpreter model.
> This is all theoretical but raises some interesting issues regarding
language design and implementation. Yes, exactly. Implementation more than design. The only aspect interesting for design is whether continuations should be first class.
> I was a bit disturbed that Joe Marshall stated that with his
implementation "nobody else in the company could extend the interpreter.." SURELY NOT? What about Carl Sassenrath?
> Also "You need a degree in Comp. Sci from a few select places to really
understand all this.." IS THAT A PROBLEM? Is there anything wrong with that? Don't take these comments too literally :-). Joe was just trying to make a point. The current interpreter is an order of magnitude easier to maintain, extend and test.
> The solutions *ARE* there if you take the time to learn and understand
them. Sort of. Solutions are not universal. They only apply to certain domains. For instance if you sacrifice OS interaction, or graphics, or networking or certain other things, then this may allow you to make certain implementation changes that allow the implementation of other features. Java demonstrates this nicely: it has one interesting and important feature: operational safety and isolation of the virtual machine from its environment. It pays a high price though: no pointers, no unions, no arrays of structures, very limited casting, extremely high numbers of run-time tests, and thus overall bad performance. Some say, in retrospect, that this was too high a price. What this illustrates is that just because a solution is theoretically possible and even has been shown to work well in one domain does not mean that is is even applicable in another one, and some choices are mutually exclusive. That's why there IS more than one language you can choose from. Keeping continuations in REBOL would have prevented REBOL from entering certain domains. For instance /View would have been impossible, for performance reasons. There is the library/callback issue. There is agility, integration with existing software packages and libraries. There are other issues... And to answer the inevitable second question, regarding tail recursion optimization (or more generally, tail call optimization): First of all, we need to distinguish between the interpreter and compiler case, because the way they deal with tail call optimization is quite different: In a compiler the optimization is not performed at run time, but at compile time, and it involves unrolling the stack frame before making the final call. Sometimes that is as easy as replacing "jsr...; rts" with "jmp", but arguments make it more tricky. In any case, there is generally NO reason NOT to do it. The only price you pay is, perhaps, slightly longer compilation time. The resulting code is usually shorter, quicker and needs less memory, i.e. it is better . In an interpreter the situation is different. The interpreter needs to determine at run time whether a call is a "tail call" and allows optimization. Because of that there is a trade-off: the benefit of successful tail call optimization has to be weighed against the additional effort to determine, dynamically, whether such optimization is possible. If that determination on the average takes up more CPU time or memory than the actual optimization saves, then such an optimization should not be implemented. Compilers obviously do not have that problem. I do not have any hard data regarding that particular trade-off, but my impression is that in "normal" programs (i.e. programs that were not written particularly to prove a point, demonstrate a concept etc., in the academic domain), it is very rare to have tail calls that benefit from optimization, so I tend to suspect that adding tail call optimization may, in most cases, have a detrimental effect. It would certainly be possible to add tail call optimization back in, although it is somewhat more difficult to do in an SM-based interpreter than an FSM-based interpreter (because it is not enough to just prune the state structure -- the stack has to be unrolled, too). However I could think of probably dozens of feature requests for REBOL that I would consider more important, benefitting more users, and resulting in more significant improvements, so don't count on tail call optimization to be very high on our priority list :-). -- Holger Kruse [kruse--nordicglobal--com]

 [11/16] from: robbo1mark:aol at: 25-Feb-2002 4:00


Holger, EXCELLENT REPLY & EXPLANATION! Much appreciated, Iam sorry that you see my constant inquisitiveness and searching for a more comprehensive understanding of REBOL as "complaining". I just want to understanding more of the HOW & WHY that's all. Thanks, Mark Dickson In a message dated Sun, 24 Feb 2002 8:42:50 PM Eastern Standard Time, Holger Kruse <[holger--rebol--net]> writes:

 [12/16] from: g:santilli:tiscalinet:it at: 25-Feb-2002 10:03


At 21.27 24/02/02, Mark wrote:
>Having read Joe Marshall's cons regarding continuations I don't think it was necessary to throw the baby out with the bath water in the change over to REBOL 2.x when we lost continuations and tail call optimisation.
The fact that REBOL 1.x was 10 to 100 times slower doesn't count? Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r

 [13/16] from: g:santilli:tiscalinet:it at: 25-Feb-2002 10:21


At 02.34 25/02/02, Holger wrote: [I have to say I agree wholeheartedly with Holger! I only have a question...]
>In an interpreter the situation is different. The interpreter needs to >determine at run time whether a call is a "tail call" and allows optimization.
Would it be possible to offer a recursive-function! datatype that ALWAYS does tail recursion optimization? This way the user is the one making the choice. (Not that this wouldn't be impossible to do in REBOL itself, following the lines of Joel's article on RebolForces...) Or, more useful and interesting, would it be possible to do it for PARSE rules? Recursive rules are simpler and shorter that iterative ones in a lot of situations, but cannot really be used in REBOL because of stack overflow (if you don't know the size of the input in advance --- e.g. when it comes from a TCP connection --- you cannot risk using a recursive rule). What do you think? Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r

 [14/16] from: g:santilli:tiscalinet:it at: 25-Feb-2002 18:14


At 10.10 25/02/02, Maarten wrote:
>If REBOL (and the likes) offer anything, it is the ability to morph it into >whatever you like. So if it is not there, try to add it yourself and make it >available. It is something RT does not stress enough: if you need it and it >is not there, morph it into what you want.
I agree wholeheartedly! This point should REALLY be stressed. Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r

 [15/16] from: robbo1mark:aol at: 25-Feb-2002 12:50


Gabriele, *SPEED* is always relative and dependant upon many factors, Interpreted REBOL code is slower than native compiled code, but I wasn't talking about speed. I know SPEED was one of the crucial factors in the change over from REBOL 1.x to REBOL 2.x implementation however I was enquiring why these LANGUAGE features were dropped, which Holger answered excellently, my original line of enquiry was wouldn't have been possible to try to improve and optimise the continuation model citing other functional languages that appear to have solved some of Joe Marshall cons' rather than drop it altogether. Holger splendidly outlined the reasons why & the design trade offs involved. Maarten Koopman also pointed out that MzScheme achieves a lot of the things which Holger said would be much more difficult by not using the current version 2.x stack based implementation model. MzScheme is based on the continuation model, there is also a native code compiler MZC for MZScheme. There are always alternative avenues of possibility to be explored / experimented with. For lots of reasons the current 2.x model is superior to REBOL 1.x but as Holger states it precludes some other things. Maybe opening up the abandoned REBOL 1.x tree would allow those interested to fully explore the benefits and pitfalls of the continuation model? Perhaps it might be easier to develop a REBOL compiler from the knowledge and sources available for Scheme / Lisp / ML compilers via this route / source tree? I just wish it wasn't so difficult to explore these issues in REBOL. cheers, Mark Dickson In a message dated Mon, 25 Feb 2002 11:53:54 AM Eastern Standard Time, Gabriele Santilli <[g--santilli--tiscalinet--it]> writes:

 [16/16] from: chaz:innocent at: 25-Feb-2002 21:28


Maarten also said:
>You can make a continuation based mechanism in REBOL, especially with all
the
>reflexive features you have available. This is of course not an interpreter >internal (what the discussion above is), but a mini interpreter implemented >on top of a very good interpreter model such as Scheme of REBOL offers.
Interesting. The thought of implementing other languages, building on top of REBOL (much the way Microsoft is building its new ".Net" family of languages on top of its new "Common Language Runtime"). We could call them ".REB" imagine, then, this very realistic (-_o) conversation, between two people shipwrecked on a island, a young nubile lass, and a dashing REBOL developer. Although they have replaced their computer's power supply with solar panels, they are too far away from any wireless internet connection. Like so many young nubile lasses, she is a functional programmer. She is despairing because she cannot download a Scheme interpreter. She cries out. YNL: "Oh! such disappointment! Here I am, a young nubile lass with a zip disk of Scheme source code, and not an interpreter in sight!" DRD: "No fear, miss," says the dashing REBOL developer, pulling out a floppy disk "behold!" YNL: "What is it? Where did you get it?" DRD: "It's a full implementation of Scheme.REB! I helped develop it!" YNL: "My hero!" ----- Original Message ----- From: <[Robbo1Mark--aol--com]> To: <[rebol-list--rebol--com]> Sent: Monday, February 25, 2002 9:50 AM Subject: [REBOL] Re: About CONTINUATIONS
> Maybe opening up the abandoned REBOL 1.x tree would allow those interested
to fully explore the benefits and pitfalls of the continuation model? Perhaps it might be easier to develop a REBOL compiler from the knowledge and sources available for Scheme / Lisp / ML compilers via this route / source tree?

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted