|
|
 |
 |
 |
 |
Scheme Programming Language
|
 |
 |
 |
 |
 |
 |
 |
 |
Delimited continuations in (Common) Lisp
The presence and use of call/cc has always been a subject of healthy debate between the Scheme and Common Lisp communities. Just to give one example, in http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations.html Kent Pitman outlines the issues (at least with respect to unwind-protect) in supporting continuations in Common Lisp. In addition, he references Will Clinger's and Dorai Sitaram's work in response. However, it is my impression that continuation support is the most common Scheme feature that Common Lisp users end up wanting to implement. Would delimited continuations be a better fit for Common Lisp? Matt -- "You do not really understand something unless you can explain it to your grandmother." Albert Einstein.
Matthew D Swank wrote: > The presence and use of call/cc has always been a subject of healthy > debate between the Scheme and Common Lisp communities. > Just to give one example, in > http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations.html Kent > Pitman outlines the issues (at least with respect to unwind-protect) in > supporting continuations in Common Lisp. In addition, he references > Will Clinger's and Dorai Sitaram's work in response. > However, it is my impression that continuation support is the most common > Scheme feature that Common Lisp users end up wanting to implement.
I think you have the wrong impression here. See for example http://groups.google.com/group/comp.lang.lisp/msg/5f92f1356e2b3523 Of course, it could just be that those who want full continuations just switch to other languages, most probably Scheme, but that's very speculative. I also have the impression that some Schemers talk about advantages of continuations when they actually "just" have simple uses in mind which are already available in Common Lisp in the form of block/return-from and catch/throw. > Would delimited continuations be a better fit for Common Lisp?
Maybe. One advantage of delimited continuations is that you can treat them as plain functions. Another advantage is that they can be relatively easily added on top of Common Lisp while full continuations can't. However, they don't get rid of some of the issues that continuations have, as far as I can tell. A problem with continuations is that they may expose implementation details of library functions that are otherwise hidden by such a library. See for example http://www.r6rs.org/formal-comments/comment-36.txt The problem here is that two different kinds of effects (side effects and control effects) don't mesh very well. My current take on this is that continuations are indeed useful but that call/cc is probably the wrong abstraction. I suspect that shifting continuations to a meta-level API would be more adequate, like in 3-Lisp. But that's just a guess... Apparently, the goal of the ANSI CL committee was to not forbid a CL implementation to use something like call/cc in the background, but to also not require implementations to provide first-class continuations. Very theoretically, this leaves the door open for other designs. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Sat, 05 May 2007 19:09:35 +0200, Pascal Costanza wrote: > I think you have the wrong impression here. See for example > http://groups.google.com/group/comp.lang.lisp/msg/5f92f1356e2b3523 > Of course, it could just be that those who want full continuations just > switch to other languages, most probably Scheme, but that's very > speculative. I also have the impression that some Schemers talk about > advantages of continuations when they actually "just" have simple uses > in mind which are already available in Common Lisp in the form of > block/return-from and catch/throw.
Well, the existence of projects like Arnesi seem to indicate there is some demand. However, the problem with mini(or maxi in this case) languages like with-call/cc is that they end up being second class citizens compared to compiler supported facilities like catch and throw. Matt -- "You do not really understand something unless you can explain it to your grandmother." Albert Einstein.
For what it's worth, I kinda like the schemish unlimited continuations. The ability to abstract flow of control is very cool and in principle I'm all for unlimited expressiveness. But that's also the ability to subvert flow of control, and I've come to dread actually using call/cc because the bugs it generates can be hard to understand and fix. It's a lot like "Goto" in that way. Call/cc can unexpectedly jump the flow of control out of the middle of something that takes a function as an argument and calls it, but depends for its correctness on flow of control returning from that function. My code that implements trees using cons cells, for example, can silently leave a branch of the tree unlinked, losing data, if the ordering predicate unexpectedly jumps away. And I don't think it's a bug in my tree library; I just think it's a type error to use that library with an ordering function of the wrong type. But my problem is that there's no way to catch such a type error without crashing. If I could put asserts or type declarations on my tree-insert! routine that would stop it instantly rather than losing data if it got a non-returning function for an ordering predicate, I would. But there's not. This is the sort of thing that makes me want to invoke something like static type checking; functions that may transfer control to some other part of the program rather than returning, are fundamentally unlike functions that will definitely return, and there needs to be some way to tell the difference *before* calling them, or to restrict the unintended type of functions from being used as arguments. Bear
Matthew D Swank wrote: > On Sat, 05 May 2007 19:09:35 +0200, Pascal Costanza wrote: >> I think you have the wrong impression here. See for example >> http://groups.google.com/group/comp.lang.lisp/msg/5f92f1356e2b3523 >> Of course, it could just be that those who want full continuations just >> switch to other languages, most probably Scheme, but that's very >> speculative. I also have the impression that some Schemers talk about >> advantages of continuations when they actually "just" have simple uses >> in mind which are already available in Common Lisp in the form of >> block/return-from and catch/throw. > Well, the existence of projects like Arnesi seem to indicate > there is some demand. However, the problem with mini(or maxi in this > case) languages like with-call/cc is that they end up being second class > citizens compared to compiler supported facilities like catch and throw.
IIUC, Arnesi is a library that has been developed for use in a continuation-based web application framework. The notion of continuation-based web applications is a very recent idea, and I seriously think that it is only a passing fad. AJAX, Flash, Silverlight, Vistascript, HOP, what have you, will take over. Who cares about the back button. ;) I could be wrong, of course. Anyway, delimited continuations are good enough for such applications. If this idea sticks, someone will probably integrate them in some CL implementation sooner or later... Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Sat, 05 May 2007 19:09:35 +0200, Pascal Costanza wrote: > I also have the impression that some Schemers talk about > advantages of continuations when they actually "just" have simple uses > in mind which are already available in Common Lisp in the form of > block/return-from and catch/throw.
I would like to get away from the "you don't really want continuations" thread of argument. I am familiar with this point view. However, my uses aren't simple, and I am interested the kind things re-entrant continautions facilitate. What I hope to do is provoke a discussion of the implementation burden and feasibility of delimited continuations compared to the whole enchilada that Scheme provides. Matt -- "You do not really understand something unless you can explain it to your grandmother." - Albert Einstein.
Matthew Swank wrote: > On Sat, 05 May 2007 19:09:35 +0200, Pascal Costanza wrote: >> I also have the impression that some Schemers talk about >> advantages of continuations when they actually "just" have simple uses >> in mind which are already available in Common Lisp in the form of >> block/return-from and catch/throw. > I would like to get away from the "you don't really want continuations" > thread of argument. I am familiar with this point view. However, my > uses aren't simple, and I am interested the kind things re-entrant > continautions facilitate.
OK > What I hope to do is provoke a discussion of the implementation burden and > feasibility of delimited continuations compared to the whole enchilada > that Scheme provides.
I don't know, but maybe http://library.readscheme.org/servlets/cite.ss?pattern=sperber-icfp2002 is a good starting point. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
In article <pan.2007.05.05.19.24.25.349 @c.net>, Matthew Swank wrote: > What I hope to do is provoke a discussion of the implementation > burden and feasibility of delimited continuations compared to the > whole enchilada that Scheme provides.
IIUC, if you have references in your language, then delimited control operators (eg, shift and reset) and full call/cc are equivalent. You can implement shift/reset in terms of call/cc + set!, and vice versa. So the overall implementation burden can't fundamentally differ. However, from the user pov, delimited control might be a better option as the basic primitive, because you may get finer control over memory usage by grabbing just the subcontinuation you're interested in. (I'm imagining needless live pointers to large objects living in the control context of a full continuation, that a delimited continuation might not grab.) -- Neel R. Krishnaswami n@cs.cmu.edu
On Sat, 05 May 2007 21:29:33 +0200, Pascal Costanza wrote: >> What I hope to do is provoke a discussion of the implementation burden and >> feasibility of delimited continuations compared to the whole enchilada >> that Scheme provides. > I don't know, but maybe > http://library.readscheme.org/servlets/cite.ss?pattern=sperber-icfp2002 > is a good starting point.
This is good paper. I've been reading "Abstacting Control" by Olivier Danvy and Andrzej Filinski (http://citeseer.ist.psu.edu/danvy90abstracting.html). This dovetails nicely with that. Skimming "Final Shift for Call/cc" seems to confirm that the precision of shift/reset can yield better performance and memory consumption in a applications where call/cc might normally be used. Also, though I am relatively new to shift/reset, the code I have written with it seems easier to reason about. Matt -- "You do not really understand something unless you can explain it to your grandmother." - Albert Einstein.
Ray Dillinger <b @sonic.net> writes: > But my problem is that there's no way to catch such a type > error without crashing. If I could put asserts or type > declarations on my tree-insert! routine that would stop it > instantly rather than losing data if it got a non-returning > function for an ordering predicate, I would. But there's > not. Can't dynamic-wind do what you want in this case? -russ
On May 5, 6:42 pm, Matthew D Swank <akopa-is-very-much-like-my-mail-
addr @c.net> wrote: > The presence and use of call/cc has always been a subject of healthy > debate between the Scheme and Common Lisp communities. > Just to give one example, inhttp://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations.html... > Pitman outlines the issues (at least with respect to unwind-protect) in > supporting continuations in Common Lisp. In addition, he references > Will Clinger's and Dorai Sitaram's work in response. > However, it is my impression that continuation support is the most common > Scheme feature that Common Lisp users end up wanting to implement. > Would delimited continuations be a better fit for Common Lisp? > Matt > -- > "You do not really understand something unless you > can explain it to your grandmother." - Albert Einstein.
Do you personally need continuations support?I do not. That doesn't mean that I'm right and you're wrong but that I could live without it in my projects. For your uses I suggest you to see first On Lisp http://www.paulgraham.com/onlisp.html chapter 20 it might do the trick.
On Mon, 07 May 2007 01:38:31 -0700, antoanjamison wrote: > Do you personally need continuations support?I do not. That doesn't > mean that I'm right and you're wrong but that I could live without it > in my projects. For your uses I suggest you to see first On Lisp > http://www.paulgraham.com/onlisp.html chapter 20 it might do the > trick. I've used continuations in various things more times than I can count. The problem is making things efficient and complete, which the hacks in On Lisp don't really address. A lot of my projects remain toys partly because having to write a custom compiler for Common Lisp is a lot of work*. Matt *though the code walker in Arnesi is a nice tool for that. -- "You do not really understand something unless you can explain it to your grandmother." - Albert Einstein.
Neel Krishnaswami wrote: > IIUC, if you have references in your language, then delimited control > operators (eg, shift and reset) and full call/cc are equivalent. You > can implement shift/reset in terms of call/cc + set!, and vice > versa. So the overall implementation burden can't fundamentally > differ.
I'm afraid the reality is more complex. If the language has no exceptions and no other (implicit or explicit) dynamic binding, and if one doesn't care about memory leaks -- then indeed, shift/reset is easily implementable via call/cc and one mutable cell. It should be noted that call/cc captures (and restores, when invoked) the _whole_ evaluation context (informally, all of the `stack'). OTH, shift captures only the part of the context; the invocation of shift-captured continuation _prepends_ the captured part to the existing context rather than _replaces_ the existing context. The dynamic environment (at least conceptually) can be thought of as pieces of information associated with some places in context. It is clear then call/cc and shift differ in a fundamental way: shift is capable of combining two pieces of dynamic environment together whereas call/cc cannot do that. For some examples of dynamic environment (e.g., exceptions) it is possible to emulate this splicing, in a round-about kind of way. In general, if the language offers no way to cut a part of and then combine parts of the dynamic environment, then shift is not implementable via call/cc. This issue is discussed in detail in Delimited Dynamic Binding http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding which gives several example of the surprising behavior of the familiar implementations of shift/reset. One should also note that the simple way of expressing shift via call/cc (in the absence of dynamic environment) leaks memory, because call/cc captures more of the context than strictly necessary. Therefore, garbage referenced in that extra captured context cannot be collected. One has to do trampolining. Granted, call/cc is attractive theoretically because it `gives' us classical logic. Other than that, it's hard to make any case for call/cc. It seems undelimited continuations hardly ever occur in practice. Furthermore, most of the patterns of using call/cc in practice involve a mutable cell -- thus these patterns embody (perhaps, poor) implementation of shift or other delimited control operator. It seems most (if not all) code using call/cc would have been simpler, more insightful and more efficient if a delimited control operator were used instead. Previously, the use of delimited control operators was perhaps hindered by the fact that there are too many to choose from. Now we know that they are all inter-macro-expressible. One should choose whichever one likes. It seems high time call/cc obsoleted and supplanted by a delimited control operator.
On May 8, 10:00 am, o@pobox.com wrote: > Previously, the use of delimited control operators was perhaps > hindered by the fact that there are too many to choose from. Now we > know that they are all inter-macro-expressible.
I don't yet believe this, though the question may come down to what "macro-expressible" means. It's a matter of space consumption, again. I am not aware of an implementation of `control0' in terms of just `shift', for example, that perserves the space complexity of programs using `control0'. An relevant example is the program (define loop (lambda (dummy) ((control0 k (k loop)) loop))) (prompt (loop 0)) With your or Ken Shan's encoding of `control0' via `shift', this program consumes unbounded space as it loops. With a more direct implementation of `control0', it consumes constant space. Here's a model that demonstrates what I mean in detail: http://www.cs.utah.edu/~mflatt/delim-cont-space-model.ss The solution to this problem can be as easy as adding an `eqv?' that works on continuations and patching up the trampoline. See "A monadic framework for delimited continuations" R. Kent Dybvig, Simon Peyton Jones, and Amr Sabry JFP (to appear) http://www.cs.indiana.edu/~dyb/pubs/monadicDC.pdf I believe that continuation marks (as in PLT Scheme) enable essentially the same solution to repair the trampoline. But it's not clear to me that we have the right notion of "macro-expressible" if the encoding requires the insertion of a trampoline. Having to install a trampoline means that I can't put `control0' in a library and drop a use in the middle of a program; the "outside" of the program has to change, too, to insert the trampoline. It's also not clear to me that the difference in space consumption matters. In other words, I don't know whether the `loop' above models anything practical. To the best of my knowledge, though, there's still a choice facing implementors about which delimited-continuation primitives to support. Matthew
Matthew Flatt wrote: > To the best of my knowledge, though, there's still a choice facing > implementors about which delimited-continuation primitives to support.
So are there any conjectures or gut feelings what would be the best set of base operators? Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On May 8, 4:04 pm, Pascal Costanza <p@p-cos.net> wrote: > Matthew Flatt wrote: > > To the best of my knowledge, though, there's still a choice facing > > implementors about which delimited-continuation primitives to support. > So are there any conjectures or gut feelings what would be the best set > of base operators?
For PLT Scheme, we went with the tagged variants of Sitaram's `%' and `fcontrol': "Handling Control" Sitaram PLDI 93 http://www.ccs.neu.edu/scheme/pubs/pldi93-sitaram.pdf Sitaram's dissertation: http://www.ccs.neu.edu/scheme/pubs/thesis-sitaram.ps.gz except that we split `fcontrol' into separate capture and abort operations to give programmers more control in the interaction with `dynamic-wind'. We chose `%' and `fcontrol' because it's easy to express lots of other operators with them: http://svn.plt-scheme.org/plt/trunk/collects/mzlib/control.ss Dybvig, Peyton Jones, and Sabry (JFP, to appear) make almost the same choice for the same reason. One difference is that they don't split the `fcontrol' counterpart into separate capture and abort operations, but they also don't consider `dynamic-wind'. Another difference is that their prompts don't have an abort handler; the abort handler has been important in improving PLT Scheme's exception system (in the current pre-release). Matthew
> I've used continuations in various things more times than I can count. > The problem is making things efficient and complete, which the hacks in On > Lisp don't really address. A lot of my projects remain toys partly > because having to write a custom compiler for Common Lisp is a lot of work*.
I can't agree with you more. I've been missing delimited continuations for long and I really appreciate if someone implements it as an extension in SBCL (please! :-). I don't care if it's portable or not. Jianshi
Matthew Flatt wrote: > On May 8, 4:04 pm, Pascal Costanza <p @p-cos.net> wrote: >> Matthew Flatt wrote: >>> To the best of my knowledge, though, there's still a choice facing >>> implementors about which delimited-continuation primitives to support. >> So are there any conjectures or gut feelings what would be the best set >> of base operators? > For PLT Scheme, we went with the tagged variants of Sitaram's `%' and > `fcontrol': > "Handling Control" > Sitaram > PLDI 93 > http://www.ccs.neu.edu/scheme/pubs/pldi93-sitaram.pdf > Sitaram's dissertation: > http://www.ccs.neu.edu/scheme/pubs/thesis-sitaram.ps.gz > except that we split `fcontrol' into separate capture and abort > operations to give programmers more control in the interaction with > `dynamic-wind'. > We chose `%' and `fcontrol' because it's easy to express lots of other > operators with them: > http://svn.plt-scheme.org/plt/trunk/collects/mzlib/control.ss > Dybvig, Peyton Jones, and Sabry (JFP, to appear) make almost the > same choice for the same reason. One difference is that they don't > split the `fcontrol' counterpart into separate capture and abort > operations, but they also don't consider `dynamic-wind'. Another > difference is that their prompts don't have an abort handler; the > abort handler has been important in improving PLT Scheme's exception > system (in the current pre-release). > Matthew
Thanks a lot for the response! Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
In article <5aeh5nF2odbk @mid.individual.net>, Pascal Costanza wrote: > Thanks a lot for the response!
Yes; I appreciate both Oleg and Matthew's comments very much. -- Neel R. Krishnaswami n@cs.cmu.edu
|
 |
 |
 |
 |
|