From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA20918; Sat, 6 Apr 2002 15:30:27 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA26152 for ; Sat, 6 Apr 2002 15:30:25 +0200 (MET DST) Received: from saul.cis.upenn.edu (SAUL.CIS.UPENN.EDU [158.130.12.4]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g36DUOT11102 for ; Sat, 6 Apr 2002 15:30:24 +0200 (MET DST) Received: from localhost (localhost [127.0.0.1]) by saul.cis.upenn.edu (8.12.2/8.12.2) with SMTP id g36DUGmI009208; Sat, 6 Apr 2002 08:30:16 -0500 (EST) To: caml-list@pauillac.inria.fr Subject: [Caml-list] Continuations -- summary of replies Cc: wand@ccs.neu.edu, William Lovas , kfm@seas.upenn.edu, Owen Gunden , Cyrus Najmabadi Reply-to: bcpierce@cis.upenn.edu Date: Sat, 06 Apr 2002 08:30:16 EST Message-ID: <9207.1018099816@saul.cis.upenn.edu> From: "Benjamin C. Pierce" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Thanks for all the responses! In case others are interested, here's a summary of what I got... - Benjamin ------------------------------------------------------------------------ From: Fermin Reig 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)" 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 To: Benjamin Pierce 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 From: "Benjamin C. Pierce" > 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 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 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 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)" Subject: RE: [Caml-list] Continuations tutorial/examples in OCaml To: I presume you've considered asking Andrew Appel, since he 'wrote the book' on 'Compiling with Continuations'. doug makofka -------------------------------------------------------------------------- From: Mitchell Wand To: "Benjamin C. Pierce" 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