Continuations

Continuations

[Tom]

[-- Attachment #1: Type: text/plain, Size: 97 bytes --]

Has anyone implemented continuations in pure, dirty OCaml yet?

(pure = no C, dirty = Obj.magic)

[-- Attachment #2: Type: text/html, Size: 107 bytes --]

Re: [Caml-list] Continuations

[Jacques Carette]

It can be done in pure, clean Ocaml.  See
http://caml.inria.fr/pub/ml-archives/caml-list/2006/07/530ba0e13ce88fab8ee0e981d65b70b1.en.html
as well as
http://caml.inria.fr/pub/ml-archives/caml-list/2006/02/8fc9c1a56c497b9743515a5e3432d704.en.html

If you want delimited continuations, see
http://caml.inria.fr/cgi-bin/hump.en.cgi?contrib=508

Jacques

Tom wrote:
> Has anyone implemented continuations in pure, dirty OCaml yet?
>
> (pure = no C, dirty = Obj.magic)
> ------------------------------------------------------------------------
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>   

[Caml-list] Continuations

[Sébastien Hinderer]

Dear all,

Is there a good tutorial or bibliographic reference about programming
with continuations around ?
I would be interested even by documentations dealing with continuations in
general (that is, not with Ocaml in particular).

Could someone explain me how the functions from the Printf module work, and
why continuations allow to consume the extra arguments given after the
format string ?

Many thanks for your help,
Sébastien.

-------------------
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

[Keith Wansbrough]

> Could someone explain me how the functions from the Printf module work, and
> why continuations allow to consume the extra arguments given after the
> format string ?

OCaml contains special magic to parse the format strings - they aren't
really strings.  Try doing

Printf.printf (if true then "%s,%s" else "%s.%s") "foo" "bar"

and see what happens...  (you have to use Pervasives.format_of_string
to make it work).

--KW 8-)



-------------------
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

[Nathaniel Gray]

On Fri, 13 Aug 2004 23:27:22 +0200, Sébastien Hinderer
<sebastien.hinderer@ens-lyon.org> wrote:
> Dear all,
> 
> Is there a good tutorial or bibliographic reference about programming
> with continuations around ?
> I would be interested even by documentations dealing with continuations in
> general (that is, not with Ocaml in particular).

I wrote a "simple" tutorial on continuations that you might try
reading.  You can find it here:
   http://mojave.caltech.edu/papers/cont-tut.ps

Let me know if there is anything that you think could be improved in
terms of clarity.

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

-------------------
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

[skaller]

On Tue, 2004-08-24 at 08:32, Nathaniel Gray wrote:

> I wrote a "simple" tutorial on continuations that you might try
> reading.  You can find it here:
>    http://mojave.caltech.edu/papers/cont-tut.ps
> 
> Let me know if there is anything that you think could be improved in
> terms of clarity.

This is a nice article to read if you know Python.
However I'm left a bit confused about what happens
to the call stack in an essentially recursive function.

CPS doesn't eliminate the call chain, because clearly
that's impossible -- so where does it go? The answer
is that the continuation is a closure which encapsulates
the local variables of the caller -- at least the ones needed
by the 'rest of the function' after the call point, including
the arguments -- which thus includes some other continuation.
Hence the continuations link these frames in a 'stack' 
in such cases anyhow -- the *machine* stack is eliminated
and replaced by a list of heap allocated objects.

This is likely to be inefficient in cases where the
machine stack *could* have been used effectively.
So I'm left wondering how to modify the CPS algorithm
to only transform 'essential' function calls.

In Felix, there is rule which determines whether this
is possible. The machine stack must be empty when
an explicit 'yield' operation is executed (yield
works by returning the point in the code to resume
plus its context)

So in some cases it is easy to determine (meaning --
without data flow analysis) that a call can safely
use the more efficient machine stack.

In particular, procedures can yield but
functions cannot -- so functional code always uses
the machine stack.

My guess is the modified CPS algorithm would first
apply the standard one then do a simplified kind
of data flow analysis to eliminate some non-essential
heap closures and put the information back on the stack.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

[Nathaniel Gray]

On 24 Aug 2004 16:47:31 +1000, skaller <skaller@users.sourceforge.net> wrote:
> On Tue, 2004-08-24 at 08:32, Nathaniel Gray wrote:
> 
> > I wrote a "simple" tutorial on continuations that you might try
> > reading.  You can find it here:
> >    http://mojave.caltech.edu/papers/cont-tut.ps
> >
> > Let me know if there is anything that you think could be improved in
> > terms of clarity.
> 
> This is a nice article to read if you know Python.

The intention was that that wouldn't matter.  :-)  Let me know if my
Python was too obtuse.

> However I'm left a bit confused about what happens
> to the call stack in an essentially recursive function.
> 
> CPS doesn't eliminate the call chain, because clearly
> that's impossible -- so where does it go? The answer
> is that the continuation is a closure which encapsulates
> the local variables of the caller -- at least the ones needed
> by the 'rest of the function' after the call point, including
> the arguments -- which thus includes some other continuation.
> Hence the continuations link these frames in a 'stack'
> in such cases anyhow -- the *machine* stack is eliminated
> and replaced by a list of heap allocated objects.

Yes.  I was mainly trying to communicate the way that the CPS
transformation changes the control flow of a program and I wanted to
avoid discussing closures since they're also hard for people to
understand.  As you and several others have pointed out, I may have
swept too much under the rug.

> This is likely to be inefficient in cases where the
> machine stack *could* have been used effectively.
> So I'm left wondering how to modify the CPS algorithm
> to only transform 'essential' function calls.
> 
> In Felix, there is rule which determines whether this
> is possible. The machine stack must be empty when
> an explicit 'yield' operation is executed (yield
> works by returning the point in the code to resume
> plus its context)
> 
> So in some cases it is easy to determine (meaning --
> without data flow analysis) that a call can safely
> use the more efficient machine stack.
> 
> In particular, procedures can yield but
> functions cannot -- so functional code always uses
> the machine stack.
> 
> My guess is the modified CPS algorithm would first
> apply the standard one then do a simplified kind
> of data flow analysis to eliminate some non-essential
> heap closures and put the information back on the stack.

I suppose you could put any non-recursive (or tail-recursive)
sub-computation on the stack.  That would preclude the use of CPS to
support microthreading, however.  Doesn't OCaml use some kind of
hybrid stack/CPS system?

Cheers,
-n8

-- 
>>>-- Nathaniel Gray -- Caltech Computer Science ------>
>>>-- Mojave Project -- http://mojave.cs.caltech.edu -->

-------------------
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

[skaller]

On Wed, 2004-08-25 at 08:18, Nathaniel Gray wrote:
> On 24 Aug 2004 16:47:31 +1000, skaller <skaller@users.sourceforge.net> wrote:
> > On Tue, 2004-08-24 at 08:32, Nathaniel Gray wrote:
> > 
> > > I wrote a "simple" tutorial on continuations that you might try
> > > reading.  You can find it here:
> > >    http://mojave.caltech.edu/papers/cont-tut.ps
> > >
> > > Let me know if there is anything that you think could be improved in
> > > terms of clarity.
> > 
> > This is a nice article to read if you know Python.
> 
> The intention was that that wouldn't matter.  :-) 

That's easy for a Python programmer to say. However I suggest
you pick some language you don't know and have someone
tell you how it works then look at some code... sure,
you can figure out what it does -- painfully -- but you
can't *see* what it does. Which you can for a language you're
familiar with. I think it's like driving a car. Knowing the 
theory is different to being able to do everything automatically.

> As you and several others have pointed out, I may have
> swept too much under the rug.

I wouldn't want to go thru the agony of CPS transforming
some code to avoid stacks -- only to find the result
just used a list instead :)

> I suppose you could put any non-recursive (or tail-recursive)
> sub-computation on the stack.  That would preclude the use of CPS to
> support microthreading, however. 

Ah no, but it doesn't!  Felix has an explicit yield
operator 'read event', it can only be used in procedures, 
not in  functions.  So functions are stackable, whilst 
procedures are not -- context switching isn't
supported in functional code, only in procedural code.

Perhaps that seems like an onerous restriction,
but it in theory it isn't -- functions aren't
allowed to have side effects.. and reading data
has a definite side effect.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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

[Caml-list] Continuations

[Ceri Storey]

I was just wondering if there any possibility of there being support
for continuations in a future version of ocaml?

They'd be useful in all sorts of situations, eg: restarable network
protocol parsers, or co-routines.
-- 
Ceri Storey <cez@compsoc.man.ac.uk>
-------------------
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

[Christophe Raffalli]

[-- Attachment #1: Type: text/plain, Size: 1812 bytes --]

Ceri Storey wrote:
> I was just wondering if there any possibility of there being support
> for continuations in a future version of ocaml?
> 
> They'd be useful in all sorts of situations, eg: restarable network
> protocol parsers, or co-routines.

Continuations are nice ... but they need to save all the stack. This can
be done in a reasonable way by saving only one page (or two if the first 
one is almost empty) of the stack and marking the other pages as 
unwritable and saving the next pages only when needed but:

- This is not portable to all platforms (windows may be OK ?).
- Intensive use of continuations are still time consuming.
- Saving all the stack leads to important memory leaks because in 
general only some of the information in the stack are necessary to call 
the continuation and the other leads to useless pointer kept for the GC.

It is in general better to implement yourself the bactracking you need 
by keeping a minimal record containing the information you need to 
backtrack and adding one argument (with such a list of records) to all 
the functions that may trigger backtracking.

But, still, if you program well, and you know about the possible memory 
leaks, you can program with continuations and it is a pity they are not 
there in OCaml :-( Especialy for those (like me) who extract programs 
from classical proofs :-)

-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

[-- Attachment #2: Type: application/pgp-signature, Size: 252 bytes --]