[Caml-list] Continuations

[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

[Caml-list] Site down

[Eric Merritt]

Everyone,

It seems the ocaml (www.ocaml.org) site is down. Does
anyone have any clue as to when it will come back up?

Thanks,
Eric

__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com
-------------------
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 --]

[Caml-list] Re: Continuations

[Michaël Grünewald]

Ceri Storey <cez@mrtall.compsoc.man.ac.uk> writes:

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

Are not they possible ? If i remember well (i did not check it back), the
following sample do what is called `Programming with rupture and
continuation' (i learned it from J. Chazarin "Programmer avec Scheme").

Help me: just after the "resoud_probleme" definition, you can spot ";;", the
i can not achieve to remove (i got a syntax error, then).

---- BEGIN CODE ----
type strategie = Abandonne | Ignore | Remplace of int

exception Rupture of (strategie -> int)

let resoud_probleme l =

    let rec continue ax togo strategy =
	match strategy with
	    | Abandonne -> 	ax
	    | Ignore -> 	resoud ax (List.tl togo)
	    | Remplace x -> 	resoud ax (x::(List.tl togo))

    and resoud ax l = 
	match l with 
	    | [] ->	ax
	    | 0::tl -> 	raise (Rupture (continue ax l))
	    | hd::tl -> resoud (ax + hd) tl

    in resoud 0 l
;;

let process_problem l s =
    try  resoud_probleme l
    with Rupture closure -> closure s
    	
in
let strategie_to_string s = 
    match s with
	| Abandonne -> "Abandonne"
	| Ignore -> "Ignore"
	| Remplace x -> Printf.sprintf "Remplace par %d" x

in
let monitor_problem l s =
    Printf.printf "Solution: %d (%s)\n" (process_problem l s) 
    (strategie_to_string s)

in

let main () = 
    let pblm = [10; 23; 33; 0; 12] in
	List.iter (monitor_problem pblm) [Abandonne; Ignore; 
					  Remplace 1; Remplace 12];
	exit 0

in main()
---- END CODE ----

This code is in the awful French/English mix i write when programming, there
is a little lexicon by the end of this message.

Maybe this is not what you call Rupture/Cotninuation (you did not speak of
rupture), but after my memories, this is.

Code explanation: `resoud_problem' must process an horrific and very looong
calculous (the sum of 5 or 6 integers from a list), but take the occurence
of '0' as a critical situation where the calculous cannot be resumed in a
consistent way, it asks the users which Strategy to apply (give up, ignore
critical value, correct the value).

Lexicon :
Abandonne : give up
Ignore : ignore (it could have been 'remove')
Remplace : replace

-- 
Michaël Grünewald <michael-grunewald@wanadoo.fr>  - RSA PGP Key ID: 0x20D90C12
-------------------
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: an implementation

[Christophe Raffalli]

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

Here is an implementation of callcc for OCaml using fork.

The only problems are:
- I did not test it (but it should work)
- The limited number of fork calls

Note: the implementation of fork on Linux, makes a minimum of page copying, so
it should be reasonably fast

-- callcc.mli --
(* callcc fn: standard callcc, uses exit code 3 for internal use. *)

val callcc : (('a -> 'b) -> 'a) -> 'a
----------------

-- callcc.ml ---
open Unix
open Sys

let all_signals = [
   sigabrt;   (* Abnormal termination *)
   sigalrm;   (* Timeout *)
   sigfpe;    (* Arithmetic exception *)
   sighup;    (* Hangup on controlling terminal *)
   sigill;    (* In id hardware instruction *)
   sigint;    (* Interactive interrupt (ctrl-C) *)
   sigkill;   (* Termination (cannot be ignored) *)
   sigpipe;   (* Broken pipe *)
   sigquit;   (* Interactive termination *)
   sigsegv;   (* In id memory reference *)
   sigterm;   (* Termination *)
   sigusr1;   (* Application-defined signal 1 *)
   sigusr2;   (* Application-defined signal 2 *)
(*  sigchld;       Child process terminated, do not ignore that one !*)
   sigcont;   (* Continue *)
   sigstop;   (* Stop *)
   sigtstp;   (* Interactive stop *)
   sigttin;   (* Terminal read from background process *)
   sigttou;   (* Terminal write from background process *)
   sigvtalrm; (* Timeout in virtual time *)
   sigprof   (* Profiling interrupt *)
]

let ignore_all_signals () =
   let previous = List.map (fun s -> try signal s Signal_ignore with Sys_error 
_ -> Signal_ignore) all_signals in
   fun () ->
     List.iter2 (fun s b -> try set_signal s b with Sys_error _ -> ()) 
all_signals previous


let callcc (fn : ('a -> 'b) -> 'a) =
   let filename = Filename.temp_file "callcc" "val" in
   let gn (x : 'a) =
     let ch = open_out filename in
     Marshal.to_channel ch x [Marshal.Closures];
     close_out ch;
     exit 3
   in
   let restore_signals = ignore_all_signals () in
   let pid = fork () in
   if pid = 0 then begin
     restore_signals ();
     fn gn
   end else
     let rec kn pid =
       match waitpid [] pid with
	_, WEXITED 3 ->
	  let ch = open_in filename in
	  let r = Marshal.from_channel ch in
	  close_in ch;
	  remove filename;
	  let pid = fork () in
	  if pid = 0 then (restore_signals (); r) else kn pid
       | _, WEXITED n -> exit n
       | _, _ -> exit 1
     in kn pid
----------------




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

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
>   

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

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

[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

[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