[SoC] Presentation of Boost.Coroutine
Hi all Boosters, During the summer, I have been working, with Eric Niebler as a mentor, on a coroutine library. The work is, as far as the Summer of Code is concerned, finished. Before a formal Boost review, I would like to smooth some rough edges in the code and polish the documentation. Still I would like to receive comments both on the current design and implementation and on the style of the documentation by interested Boosters. The source code is available from the boost-soc svn repository here: https://www.boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/corout... The SoC application that started it all is still available here: http://libstream.sf.net/index_c.html I've uploaded the current documentation here: http://h1.ripway.com/gpderetta/html/index.html Unfortunately ripway only allows up to 30MB of downloads every day. I'll see if i can find a better host. The current documentation is known to be full of errors and might not make any sense to anyone except the author (that is, me :) ) Unfortunately time was running out. Still it should be fairly complete and present 99% of the library (a true reference is still to be written). Many examples and use cases are shown. I'll be leaving for (hopefully deserved) vacations tomorrow in the early morning (circa 6 am UCT time zone). I'll be away from the internet for a week, so I won't be able to contribute to the the discussion untill the 28th of this month when I'll be back. I hope that many will find the library useful and at least interesting. It has been a great and instructive project, and I look forward for a boost review. I woud like to thank my mentor Eric Niebler for the invaluable help, expecially with aderence to boost standars. -- dremaing-for-vactions-ly your Giovanni P. Deretta
Giovanni Piero Deretta wrote:
I've uploaded the current documentation here:
I've hosted the docs for your enjoyment at: http://www.crystalclearsoftware.com/soc/coroutine/index.html Jeff
I have a few questions about the library: 1) will it be formally submitted to boost ? 2) is it possible to provide an example of web continuations using coroutines ? I think this example would drive usage for the library as it is not obvious how it can be done. Also, web continuations seems to be one of the ideal applications of the library 3) could the library be more seamlessly integrated with boost.asio ? Even as a separate library, it would be great if there are some examples (not just the docs usage) that clearly work together with boost.asio, specially a web continuations example that could work with the http server example that asio already provides Thanks for this great library ! On 8/20/06, Jeff Garland <jeff@crystalclearsoftware.com> wrote:
Giovanni Piero Deretta wrote:
I've uploaded the current documentation here:
I've hosted the docs for your enjoyment at:
http://www.crystalclearsoftware.com/soc/coroutine/index.html
Jeff _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 9/14/06, Jose <jmalv04@gmail.com> wrote:
I have a few questions about the library:
1) will it be formally submitted to boost ?
Definitely. I need to write more examples, polish the docs and some cleaning up. And of course time :)
2) is it possible to provide an example of web continuations using coroutines ? I think this example would drive usage for the library as it is not obvious how it can be done. Also, web continuations seems to be one of the ideal applications of the library
What do you exactly mean with web continuations? Is it session management done with coroutines instead of encoding state in session ids? I will see if i can come up with something. Ideas are wellcome.
3) could the library be more seamlessly integrated with boost.asio ? Even as a separate library, it would be great if there are some examples (not just the docs usage) that clearly work together with boost.asio, specially a web continuations example that could work with the http server example that asio already provides
Yes, i need more examples and some more documentation about asio+coroutines. I think that the integration is good, but some more utilities could be useful. I will try to 'port' some of asio examples to coroutine as soon as i have time.
Thanks for this great library !
Thank to you for your time. -- Giovanni P. Deretta
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
What do you exactly mean with web continuations? Is it session management done with coroutines instead of encoding state in session ids? I will see if i can come up with something. Ideas are wellcome.
The term is used when continuations are used to handle the app flow in web forms. It's one of the most popular topics in advanced web development ! Traditional session handling is done via session ids with cookies but it has big shortcomings when using back button or creating a new browser window plus coding the app flow is not as natural or elegant as it can be with web continuations. Web continuations handle the execution state not just the session state. Some references below. The basic hello example is a calculator app or a guessing game. The pdf below provides a real world example (a shopping cart) check section: Web Continuations revolutionizing webapp development http://it.sun.com/eventi/jc05/pdf/2-ProNetics.pdf Crossing borders: Continuations, Web development, and Java programming http://www-128.ibm.com/developerworks/java/library/j-cb03216/ Yield, Web Continuations! Article shows how to emulate web continuation in .NET framework http://www.codeproject.com/useritems/YeildContinuations.asp
On 9/14/06, Jose <jmalv04@gmail.com> wrote:
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
What do you exactly mean with web continuations? Is it session management done with coroutines instead of encoding state in session ids? I will see if i can come up with something. Ideas are wellcome.
The term is used when continuations are used to handle the app flow in web forms. It's one of the most popular topics in advanced web development ! Traditional session handling is done via session ids with cookies but it has big shortcomings when using back button or creating a new browser window plus coding the app flow is not as natural or elegant as it can be with web continuations. Web continuations handle the execution state not just the session state.
Some references below. The basic hello example is a calculator app or a guessing game. The pdf below provides a real world example (a shopping cart)
check section: Web Continuations revolutionizing webapp development http://it.sun.com/eventi/jc05/pdf/2-ProNetics.pdf
Crossing borders: Continuations, Web development, and Java programming http://www-128.ibm.com/developerworks/java/library/j-cb03216/
Yield, Web Continuations! Article shows how to emulate web continuation in .NET framework http://www.codeproject.com/useritems/YeildContinuations.asp
After a quick look I see that there could be some problems on implementing web continuations with coroutines. The problem is that coroutines are a subset of full continuations. One shot continuations and subcontinuations can be implemented with coroutines (and vice versa), but full continuations cannot. A continuation can be restored multiple times, and this behaviour is for example used to implement back button handling (the continuation relative to the previous page state is saved, so it can be restored when the previous state is reloaded). I do not see how this could be implemented with coroutines automatically unless coroutines where deepcopy-able (you could copy a coroutine and then resome that copy). Unfortuantely it is not feasible to make deep copies of them in the current language. As far as i can see, this is the only place where the 'fullness' aspect of web continuations is used. If you can handle the back button problem in some other way or simply ignore the problem, then coroutines are a good way to implement web continuations. BTW, unless I 'm missing something, the .NET implementation has the same limitation. -- Giovanni P. Deretta
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
A continuation can be restored multiple times, and this behaviour is for example used to implement back button handling (the continuation relative to the previous page state is saved, so it can be restored when the previous state is reloaded).
I do not see how this could be implemented with coroutines automatically unless coroutines where deepcopy-able (you could copy a coroutine and then resome that copy). Unfortuantely it is not feasible to make deep copies of them in the current language.
I don't understand what you mean by "automatically" . Also why is not feasible to make deep copies ? I don't know enough to understand that the back button results in full continuations and the other cases don't. As far as i can see, this is the only place where the 'fullness'
aspect of web continuations is used. If you can handle the back button problem in some other way or simply ignore the problem, then coroutines are a good way to implement web continuations.
From reading "Revisiting Coroutines", I thought full continuations could be created from coroutines, not just partial continuations but I must be mistaken.
http://rifers.org/wiki/display/RIFE/Web+continuations See the section on "Different continuation handling models" for info on how rife does this to fully support the back-button
On 9/14/06, Jose <jmalv04@gmail.com> wrote:
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
A continuation can be restored multiple times, and this behaviour is for example used to implement back button handling (the continuation relative to the previous page state is saved, so it can be restored when the previous state is reloaded).
I do not see how this could be implemented with coroutines automatically unless coroutines where deepcopy-able (you could copy a coroutine and then resome that copy). Unfortuantely it is not feasible to make deep copies of them in the current language.
I don't understand what you mean by "automatically" . Also why is not feasible to make deep copies ? I don't know enough to understand that the back button results in full continuations and the other cases don't.
Full continuations store the execution state when captured. You can restart them later and recapture the execution state in a new continuation without invalidating the previous continuation. Thus you get automatic backtracking (continuations are extremely good a that): you store a continuation for each state you might want to backtrack later and you are done. Coroutines (and one shot continuations) cannot. If a one shot continuation is restarted, it cannot be restarted one more time, thus they are not useful for backtracking. You need to implement backtracking by hands. It is not tivial. When the user clicks on the back button it wants to return to a previous state even if it did some progress since then. Full continuations are great to implement this. All other cases (that i can think of now) need to capture the current execution state only to restore it when more input from the user come in. There is no need to restart a continuation more than once. In practice this is one of the most obvious use cases for coroutines. Continuations are just used to implement them.
As far as i can see, this is the only place where the 'fullness' aspect of web continuations is used. If you can handle the back button problem in some other way or simply ignore the problem, then coroutines are a good way to implement web continuations.
From reading "Revisiting Coroutines", I thought full continuations could be created from coroutines, not just partial continuations but I must be mistaken.
Yes, the paper only talks about equivalence of coroutines with one shot continuations and semicontinuations.
http://rifers.org/wiki/display/RIFE/Web+continuations See the section on "Different continuation handling models" for info on how rife does this to fully support the back-button
In practice they use copyable coroutines. If a coroutine is copyable, you can copy it and restart the copy. Thus the original keep its execution state and is not invalidated. With copyable coroutines you could infact implement full continuations. Unfortunately copyable coroutines are hard and extremely expensive. RIFE has the advantage of being java-only, so they only need to target one (virtual) architecture. They (or at least i think this is how it works) can preprocess the bytecode and make copies of all local objects by invoking clone (remember that all java objects carry type information with them, except builtins, but this can be memcopyed safely) in a specific execution frame: as far as I understand you can call pause() *only* inside processElement() . This is even more restrictive than stackless coroutines. This limitation is not to get a performance hit in other code (probably to limit the amount of state to be copyed and the number of frames to be analized). As a final limitation, you cannot have backtracking if some local objects are not Cloneable (most are though). These are a too great limitation for a general purpose library like mine (even RIFE provieds a way to disable full continuations with setCloneContinuation(false)). Also walking the stack to search for object to copy cannot be implemented portably (or even non portably), unless one where to be restricted to never allocate non builtin stack objects and have all heap allocated objects inherit from a common base. This would kill performance, would be a very non iodimatic c++ and still be hard to do and very fragile. Theoretically compiler support could make coroutine copying possible and even relatively cheap (no much more than the cost of copying every single local object in scope) . In fact some compilers know at every moment the set of all objects alive in the stack for unwinding purposes. For the time being my library is stuck with non-copyable coroutines. -- Giovanni P. Deretta
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote: [ .. description on how RIFE implements full continuations in Java .. ] These are a too great limitation for a general purpose library like
mine (even RIFE provieds a way to disable full continuations with setCloneContinuation(false)). Also walking the stack to search for object to copy cannot be implemented portably (or even non portably), unless one where to be restricted to never allocate non builtin stack objects and have all heap allocated objects inherit from a common base. This would kill performance, would be a very non iodimatic c++ and still be hard to do and very fragile.
Theoretically compiler support could make coroutine copying possible and even relatively cheap (no much more than the cost of copying every single local object in scope) . In fact some compilers know at every moment the set of all objects alive in the stack for unwinding purposes.
For the time being my library is stuck with non-copyable coroutines.
Then I see two interesting and not mutually exclusive paths to follow: - implement the one shot continuation examples, although the multiple web cont. implementations out there seem to do full cont. (at least Scheme, Java, Ruby, ..) - experiment with an implementation for Linux only, and check whether performance and fragility are major issues (the interpreted versions out there don't seem to complain about that but I am not sure they are used in high performance cases) Thank you for helping me understand this complex topic !
Hi, Giovanni, I found 2 papers that shed some light on the solution using one-shot continuations. The key is to detect when the continuation is invoked a second time and provide a suitable error Interaction-Safe State for the Web http://www.cs.brown.edu/~sk/Publications/Papers/Published/mk-int-safe-state-... The Influence of Browsers on Evaluators<http://www-spi.lip6.fr/%7Equeinnec/PDF/webcont.pdf> http://www-spi.lip6.fr/~queinnec/PDF/webcont.pdf On 9/14/06, Jose <jmalv04@gmail.com> wrote:
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
[ .. description on how RIFE implements full continuations in Java .. ]
These are a too great limitation for a general purpose library like
mine (even RIFE provieds a way to disable full continuations with setCloneContinuation(false)). Also walking the stack to search for object to copy cannot be implemented portably (or even non portably), unless one where to be restricted to never allocate non builtin stack objects and have all heap allocated objects inherit from a common base. This would kill performance, would be a very non iodimatic c++ and still be hard to do and very fragile.
Theoretically compiler support could make coroutine copying possible and even relatively cheap (no much more than the cost of copying every single local object in scope) . In fact some compilers know at every moment the set of all objects alive in the stack for unwinding purposes.
For the time being my library is stuck with non-copyable coroutines.
Then I see two interesting and not mutually exclusive paths to follow:
- implement the one shot continuation examples, although the multiple web cont. implementations out there seem to do full cont. (at least Scheme, Java, Ruby, ..)
- experiment with an implementation for Linux only, and check whether performance and fragility are major issues (the interpreted versions out there don't seem to complain about that but I am not sure they are used in high performance cases)
Thank you for helping me understand this complex topic !
On 9/14/06, Jose <jmalv04@gmail.com> wrote:
Hi, Giovanni,
I found 2 papers that shed some light on the solution using one-shot continuations. The key is to detect when the continuation is invoked a second time and provide a suitable error
Interaction-Safe State for the Web http://www.cs.brown.edu/~sk/Publications/Papers/Published/mk-int-safe-state-...
The Influence of Browsers on Evaluators<http://www-spi.lip6.fr/%7Equeinnec/PDF/webcont.pdf> http://www-spi.lip6.fr/~queinnec/PDF/webcont.pdf
Hum, a quick read of the papers seems that they deal on how not executing full continuation a second time by making them one shot in some cases (for example in presence of database updates), so they are not really much relevant. In those papers, the detection is done from *inside* the continuation (a full continuation). We cannot do that and need to do it from the outside. This is nothing new. You need to do it even on web applications not built using continuations of any sorts. An innovative idea would be an easy way to have backtracking with one shot continuations. One of the examples in my library implements backtracking with coroutines. I'll see if it can be expanded, but it would require at least a new coroutine for backtracking point. BTW, posix has a nice and simple way for creating full continuations. It is called 'fork' :). Unfortunately it is a little too heavyweight. -- Giovanni P. Deretta
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
Interaction-Safe State for the Web
http://www.cs.brown.edu/~sk/Publications/Papers/Published/mk-int-safe-state-...
just a quote from section 8.2 ========= Another solution to this problem [22 - back button] relies on one-shot continuations [3]. These continuations detect when they are invoked a second time and produce a suitable error. .... However,this strategy cannot be used to implement the shopping cart example without severe transformation of the source program to propagate the called? binding to each code fragment that binds URLs. ========= I'll read the paper in detail so that I understand all the details, which I don't right now regards
On 9/14/06, Jose <jmalv04@gmail.com> wrote:
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
Interaction-Safe State for the Web
http://www.cs.brown.edu/~sk/Publications/Papers/Published/mk-int-safe-state-...
just a quote from section 8.2 ========= Another solution to this problem [22 - back button] relies on one-shot continuations [3]. These continuations detect when they are invoked a second time and produce a
suitable error. .... However,this strategy cannot be used to implement the shopping cart example without severe transformation of the source program to propagate the called? binding to each code fragment that binds URLs. =========
Your association of this text with 'back button' is wrong. The text actually refers to non-idempotent URL handling (while the bibliography reference is a generic web continuation paper):
From the beginning of section 8.3 (not 8.2):
[...] A sub-problem of [disabling old urls] has been ad- dressed by work targeted at preventing the duplication of non- idempotent requests. The Post-Redirect-Get pattern [10] is one strategy [...] Another solution [22] to this problem relies on one-shot con- tinuations [3]. These continuations detect when they are invoked a second time and produce a suitable error. [...] _________________________ -- Giovanni P. Deretta -- Giovanni P. Deretta
sorry, this is what happens for not reading in detail On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
On 9/14/06, Giovanni Piero Deretta <gpderetta@gmail.com> wrote:
Interaction-Safe State for the Web
http://www.cs.brown.edu/~sk/Publications/Papers/Published/mk-int-safe-state-...
just a quote from section 8.2 ========= Another solution to this problem [22 - back button] relies on one-shot continuations [3]. These continuations detect when they are invoked a second time and
On 9/14/06, Jose <jmalv04@gmail.com> wrote: produce a
suitable error. .... However,this strategy cannot be used to implement the shopping cart
example
without severe transformation of the source program to propagate the called? binding to each code fragment that binds URLs. =========
Your association of this text with 'back button' is wrong. The text actually refers to non-idempotent URL handling (while the bibliography reference is a generic web continuation paper):
From the beginning of section 8.3 (not 8.2):
[...] A sub-problem of [disabling old urls] has been ad- dressed by work targeted at preventing the duplication of non- idempotent requests. The Post-Redirect-Get pattern [10] is one strategy [...] Another solution [22] to this problem relies on one-shot con- tinuations [3]. These continuations detect when they are invoked a second time and produce a suitable error. [...] _________________________
-- Giovanni P. Deretta
-- Giovanni P. Deretta _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (3)
-
Giovanni Piero Deretta -
Jeff Garland -
Jose