[Caml-list] Continuations -- summary of replies

[Caml-list] Continuations -- summary of replies

[Benjamin C. Pierce]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 10177 bytes --]

Thanks for all the responses!  In case others are interested, here's a
summary of what I got...

      - Benjamin

------------------------------------------------------------------------

From: Fermin Reig <reig@ics.uci.edu>
To: bcpierce@cis.upenn.edu
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml

> I've been discussing programming idioms based on continuations with some
> students, and I'd like to find a nice tutorial or compendium of examples
> illustrating some of the useful and mind-bending things that can be done.

I know about this paper:

Hayo Thielecke
Continuations, functions and jumps
Logic Column 8, SIGACT News, July 1999.
(http://www.cs.bham.ac.uk/~hxt/research/htpapers.html)

Hope it helps,
Fermín

PS: could you post a summary of the replies? Thanks

--------------------------------------------------------------------------

From: "Gurr, David (MED, self)" <David.Gurr@med.ge.com>
To: bcpierce@cis.upenn.edu
Subject: RE: [Caml-list] Continuations tutorial/examples in OCaml
Date: Wed, 3 Apr 2002 19:44:12 -0600 

I like compiler and interpreter examples.  The elp/sml (or
is it sml/elp?) paper that derives a sml implementation of
lambda prolog is nice (Felty et al).  The 3-Lisp papers 
(B. C. Smith et al) and Blond papers (Danvy et al) on reflective
interpreters too.  The Danvy et al partial evaluation papers 
are harder to read (but may not be harder to understand with 
a good intro).  L.I.S.P (Lisp in Small Pieces) Quinnac(sp?)
ought to be good but I have not read it.  Filinsky's work on
effects and previous work is pretty wild.  Congrats on your
new book.  -D
P.S. Bigloo had (prob. still has) a pattern matching compiler
that is one of a family of Scheme pattern matching compilers
and interpreters.  I forget who wrote what when, but both
useful and mind-bending.
P.P.S. Clos's method combination & dispatch system seems to
be a related to compositions of partial continuations.  If
there is a explanation of a relation, I would like to 
hear it.


--------------------------------------------------------------------------
From: Zhe Yang <zheyang@saul.cis.upenn.edu>
To: Benjamin Pierce <bcpierce@cis.upenn.edu>
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml

On Wed, 3 Apr 2002, Benjamin C. Pierce wrote:

> I've been discussing programming idioms based on continuations with some
> students, and I'd like to find a nice tutorial or compendium of examples
> illustrating some of the useful and mind-bending things that can be done.
>
> I know there are lots of tutorials from the Scheme community, but they
> tend to depend on continuations as a *language* mechanism (call/cc),
> which OCaml (which is the context of this discussion) doesn't have.  So
> I'd prefer to find something that develops the same ideas in a more
> concrete way, using an explicit continuation-passing style.  [Scheme (or
> Haskell, SML, or whatever) syntax is no problem, as long as the
> continuations are explicit.]
>
> Pointers appreciated...
>
>      Benjamin

One way to get many such programs is to take a program that uses operators
that have computational effects (side-effects, I/O, exception,
non-determinism, and even callcc)  and apply the CPS monadic translation
of Filinski (POPL 94; just read the initial few sections) to get a purely
functional version of the program.  Note that without the effectful
operators, i.e., the original program is functional, one gets a program in
the standard CPS style.  Only the translation of the effective operators
result to program fragments that do not conform to syntax of CPS terms.

The benefit of the CPS monadic translation, compared with the standard
monadic translation, is that all standard constructs are translated
uniformly regardless of the monad itself.

Two major classes of examples are the success/fail continuations for
simulating backtracking, and using continuations for simulating
coroutines.  Both of them can be formulated using monads (non-determinism
monad and resumption monad).

I guess that Olivier has a collection of (pointers to) programs in
explicit CPS style, written by himself and by other people, since he has
written quite a few papers on that.

Zhe
--------------------------------------------------------------------------
To: bcpierce@cis.upenn.edu
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml
Date: Thu, 04 Apr 2002 12:04:17 +0900
Sender: Eijiro Sumii <sumii@yl.is.s.u-tokyo.ac.jp>

From: "Benjamin C. Pierce" <bcpierce@saul.cis.upenn.edu>
> I've been discussing programming idioms based on continuations with some
> students, and I'd like to find a nice tutorial or compendium of examples
> illustrating some of the useful and mind-bending things that can be done.

The following paper includes a nice application of CPS to backtracking
in regular expression matching.  It is implemented in (Standard) ML,
of course!

  Robert Harper.  Functional Pearl: Proof-directed debugging.  Journal
  of Functional Programming, 9(4):463-469, July 1999.  Also in
  Proceedings of the Workshop on Functional and Declarative
  Programming in Education, 1999.

--
Eijiro Sumii (http://www.yl.is.s.u-tokyo.ac.jp/~sumii/)
Research Associate of Yonezawa Laboratory, University of Tokyo
--------------------------------------------------------------------------
From: Olivier Danvy <danvy@brics.dk>
To: zheyang@saul.cis.upenn.edu
CC: bcpierce@cis.upenn.edu
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml

Good morning,

> I know there are lots of tutorials from the Scheme community, but they
> tend to depend on continuations as a *language* mechanism (call/cc),
> which OCaml (which is the context of this discussion) doesn't have.

Well, it is an undocumented feature, at least, and the current
implementation is the most inefficient one (ie, it copies the stack to
the heap).  As for CPS programs, OCaml is not geared to run them.

----------

I concur with Zhe: looking at the CPS encoding of any monadic program
provides a wealth of examples.

In addition:

- one can just CPS-transform existing examples with call/cc to obtain CPS
  programs;

- one can also look into iterating the CPS transformation (which leads to
  delimited continuations) and to transforming programs back to direct
  style, including call/cc;

- continuations are also used for transforming programs (cf. Mitch Wand's
  paper in JACM'80 or "Defunctionalization at work" at PPDP'01);

- there are also continuation-based programs to express things like
  printf, type-directed partial evaluation, etc.;

- there are also other ways of programming with control, that are
  inspired by type isomorphisms (eg, to split a continuation expecting a
  sum into 2 separate continuations);

- Hayo Thielecke has been doing pretty impressive stuff with
  continuations and CPS over the last few years.

I just gave a double lecture on continuations in a spring summer school
in France (http://www.pps.jussieu.fr/~ecole).  It was a wonderful
occasion to put all that I know about continuations in some semblance of
order, and I am now embarking in writing lecture notes, including an
array of examples.

----------

Let me conclude with a plea: despite IT technologies, BTA analysis, Meta
ML, etc., let us resist to CPS style, OK?

Kind regards,	-- Olivier :-)
--------------------------------------------------------------------------
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>
Date: Thu, 4 Apr 2002 09:37:14 +0200 (MEST)
To: bcpierce@cis.upenn.edu
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml

Hello,

You may be interested in  the following paper, by François Pottier and
myself:

	Producing All Ideals of a Forest, Functionally
	(submitted for publication to the JFP)

        http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz

It  is a  functional implementation  of Koda-Ruskey's  algorithm using
continuations,  compared to two  C implementations  by Knuth.  Code is
written in ocaml (of course :-).

Best regards,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)


--------------------------------------------------------------------------
From: Benedikt Rosenau <Benedikt.Rosenau@dlr.de>
Subject: Re: [Caml-list] Continuations tutorial/examples in OCaml
To: bcpierce@cis.upenn.edu
Date: Thu, 4 Apr 2002 14:21:46 +0200 (DFT)

Hello Bejamin,

> So I'd prefer to find something that develops the same ideas in a more
> concrete way, using an explicit continuation-passing style.  [Scheme (or
> Haskell, SML, or whatever) syntax is no problem, as long as the
> continuations are explicit.]

There is a Scheme-to-C compiler going through Continuation Passing
Style. It uses Henry Bakers approach of Garbage Collection. The basic
idea is that only the memory visible for the continuation currently
active is alive, the rest may be collected.

http://linux.rice.edu/~rahul/hbaker/CheneyMTA.html is the original paper.
http://www.call-with-current-continuation.org/ has the Scheme implementation.

And, of course, there is Appel's book "Compiling with Continuations"

Regards,
   Benedikt

--------------------------------------------------------------------------
Date: Thu, 04 Apr 2002 09:22:32 -0500
From: "Makofka, Doug (HT-EX)" <DMakofka@GI.com>
Subject: RE: [Caml-list] Continuations tutorial/examples in OCaml
To: <bcpierce@cis.upenn.edu>

I presume you've considered asking Andrew Appel, since he 'wrote the book'
on 'Compiling with Continuations'.
doug makofka

--------------------------------------------------------------------------
From: Mitchell Wand <wand@ccs.neu.edu>
To: "Benjamin C. Pierce" <bcpierce@cis.upenn.edu>
Subject: tricks by writing in CPS

Another thought:  I had a paper in JACM back in 1980,
"Continuation-Based Program Transformation Strategies", that showed
some neat optimizations obtainable by looking at the CPS.  No call/cc
there.  Dunno if that's sufficiently "tricky" for you, though.

--Mitch 
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Continuations -- summary of replies

[Brian Rogoff]

Thanks for the summary! A practically oriented page of cool continuation
tricks would be a very useful thing.

Lloyd Allison, who wrote an excellent, short introduction to denotational
semantics, has a few papers on practical uses of continuation passing
style, including one in Java (!) I think.

L.Allison. Continuations implement generators and streams.
    Computer Journal 33(5) 460-465 1990

L. Allison, Generator and search objects in Java.
   J J. Res. and Practice in Inf. Tech.

Some of the papers are available here

http://www.csse.monash.edu.au/~lloyd/Paperz.shtml

I'm a bit surprised by this comment from Olivier Danvy

> Let me conclude with a plea: despite IT technologies, BTA analysis, Meta
> ML, etc., let us resist to CPS style, OK?

I guess he's saying that we shouldn't write CPS style code (I can't say
for sure), but I find some of the nice CPS examples (like his
functional unparsing one) really compelling. Oh well, I'll still be
anxiously awaiting those lecture notes.

-- Brian
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Continuations -- summary of replies

[Zhe Yang]

> > Let me conclude with a plea: despite IT technologies, BTA analysis, Meta
> > ML, etc., let us resist to CPS style, OK?
>
> I guess he's saying that we shouldn't write CPS style code (I can't say
> for sure), but I find some of the nice CPS examples (like his
> functional unparsing one) really compelling. Oh well, I'll still be
> anxiously awaiting those lecture notes.

No, he's only alluding to the fact that we are constantly repeating a word
already appearing in the abbrevation :-)

Cheers,
Zhe

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners