Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

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

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-

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

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

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc