Re: [Caml-list] recursive or loop

Re: [Caml-list] recursive or loop

[Jonathan Harrop]

On Mon Mar  6 16:42 , Michael Wohlwend <micha-1@fantasymail.de> sent:
>On Monday 06 March 2006 15:15, you wrote:
>> > If you're doing purely functional programming then you'll be passing the
>> > state as an argument to the recursive function.
>>
>> How do you restore the call stack?
>
>yes the state is not the problem, the callstack is the (my) problem...

Write in CPS?

Cheers,
Jon.

Re: [Caml-list] recursive or loop

[Michael Wohlwend]

On Monday 06 March 2006 18:25, Jonathan Harrop wrote:
> Write in CPS?
>

no experience with that. Doesn't it need support of the language?

 Michael

Re: [Caml-list] recursive or loop

[Thomas Fischbacher]

On Mon, 6 Mar 2006, Michael Wohlwend wrote:

> On Monday 06 March 2006 18:25, Jonathan Harrop wrote:
> > Write in CPS?
> 
> no experience with that. Doesn't it need support of the language?

No it does not. But never mind. It would not help either.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] recursive or loop

[Anil Madhavapeddy]

On Mon, Mar 06, 2006 at 07:25:35PM +0100, Michael Wohlwend wrote:
> On Monday 06 March 2006 18:25, Jonathan Harrop wrote:
> > Write in CPS?
> >
> 
> no experience with that. Doesn't it need support of the language?

It's conceptually pretty simple; every function takes an extra
argument which receives the result instead of explicitly returning
it.  It permits a neat alternative to threading since you can
``suspend'' a computation by not applying it to the next function
in the chain of control, and so write custom thread scheduling
policies without depending on your OS to do the right thing.

In practise, it does need some support from the language to be
useful.  Syntactic help is essential to avoid lots of (fun () ->
()) style closures for every statement; this may be something you
want to play with using camlp4, but is not for the faint of heart.

A more serious problem is that their creation can require the
contents of the stack to be copied if you suspend the continuatation.
This is obviously a bad thing performance-wise if you love your
recursion.  A notable difference between SML/NJ and OCaml is that
the former natively supports continuations; OCaml adopts an abstract
machine which maps more cleanly onto modern hardware but makes the
efficient use of continuations without stack copying difficult.

To answer your original question, I wouldn't get too religious about
recursive vs imperative styles; OCaml lets you choose and mix them,
so pick the one that gets the job done for you and move on to the
finer things in life :-)

-- 
Anil Madhavapeddy                             http://anil.recoil.org
University of Cambridge                      http://www.cl.cam.ac.uk

Re: [Caml-list] recursive or loop

[Michael Wohlwend]

On Monday 06 March 2006 20:25, Anil Madhavapeddy wrote:
>
> To answer your original question, I wouldn't get too religious about
> recursive vs imperative styles; OCaml lets you choose and mix them,
> so pick the one that gets the job done for you and move on to the
> finer things in life :-)

yop, that's true; it's just that in my case the recursive version is pretty 
nice :-)

 thanks,
 Michael

Re: [Caml-list] recursive or loop

[Alan Falloon]

Michael Wohlwend wrote:
> On Monday 06 March 2006 20:25, Anil Madhavapeddy wrote:
>   
>> To answer your original question, I wouldn't get too religious about
>> recursive vs imperative styles; OCaml lets you choose and mix them,
>> so pick the one that gets the job done for you and move on to the
>> finer things in life :-)
>>     
>
> yop, that's true; it's just that in my case the recursive version is pretty 
> nice :-)
>   
If you can easily convert it to a tail-recursive function, then you 
don't need to record any stack info, and its as easy as recording the 
current arguments like Jon Harrop pointed out.

Converting a recursive function to a tail-recursive one is as hard as 
converting it to an interative algorithm: the two forms are pretty much 
the same.

--
Alan Falloon

Re: [Caml-list] recursive or loop

[Michael Wohlwend]

On Tuesday 07 March 2006 17:02, Alan Falloon wrote:
> Converting a recursive function to a tail-recursive one is as hard as
> converting it to an interative algorithm: the two forms are pretty much
> the same.

I have indeed some problems converting it to a loop or to a tail-recusrsive 
function. It's of the form:

let rec search result =
	if some_test then record_the result
	else begin
		iter (fun element ->
			iter (fun ...);
			search (element :: result); (* !!! *)
			iter (fun ...);
		) data
	end
;;	

so the recursive call is in the middle and in an List.iter statment :-(

cheers
 Michael

Re: [Caml-list] recursive or loop

[Matthew O'Connor]

Thomas Fischbacher wrote:
> On Mon, 6 Mar 2006, Michael Wohlwend wrote:
> 
>> On Monday 06 March 2006 18:25, Jonathan Harrop wrote:
>>> Write in CPS?
>> no experience with that. Doesn't it need support of the language?
> 
> No it does not. But never mind. It would not help either.
> 

Doesn't CPS enable you to basically keep the entire call stack (or
equivalent) in the heap?  Can you explain why it wouldn't help?  Thanks.


Matt

Re: [Caml-list] recursive or loop

[Thomas Fischbacher]

On Wed, 8 Mar 2006, Matthew O'Connor wrote:

> > No it does not. But never mind. It would not help either.
> 
> Doesn't CPS enable you to basically keep the entire call stack (or
> equivalent) in the heap?

Yes, it does.

>  Can you explain why it wouldn't help?  Thanks.

You still would have to write out a closure if you want to write all the 
state to disk.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] recursive or loop

[Till Varoquaux]

On 3/8/06, Thomas Fischbacher <Thomas.Fischbacher@physik.uni-muenchen.de> wrote:
>
> On Wed, 8 Mar 2006, Matthew O'Connor wrote:
>
> > > No it does not. But never mind. It would not help either.
> >
> > Doesn't CPS enable you to basically keep the entire call stack (or
> > equivalent) in the heap?
>
> Yes, it does.
>
> >  Can you explain why it wouldn't help?  Thanks.
>
> You still would have to write out a closure if you want to write all the
> state to disk.

I beleive specifying Marshal.Closures when marshalling should do the trick...

Another way to get along with suspending resuming is by marshalling a
continuation. You can use Xavier Leroy's callcc library and see if
this works out you (just call suspend when you went to exit with a
save point):

open Callcc
open Netchannels
open Marshal

let suspend ()=
  let save_state k=
    let pipe = new Netencoding.Base64.encoding_pipe() in
    with_out_obj_channel
      (new output_channel (open_out "state"))
      (fun ch ->
         let ch' = new output_filter pipe ch in
         ch' # output_string(to_string k [Closures]);
         ch' # close_out()
      );
    (* Skips a warning because this function does not return (it is an exit
       point)*)
    ignore(exit 0)
  in
  callcc save_state
(*
  Saves the "state" the application is in as an base64 encoded marshalled
  continuation.
*)
let _ =
  if (Sys.file_exists "state") then
    let res =
      (let pipe = new Netencoding.Base64.decoding_pipe() in
       with_in_obj_channel
         (new input_channel (open_in "state"))
         (fun ch ->
            let ch' = new input_filter ch pipe in
            let s = string_of_in_obj_channel ch' in
            s
         )) in
    Sys.remove("state");
    let k=Marshal.from_string res 0 in
      throw k ()

Although this has worked callcc is a proof of concept so be ready to
have some nasty bugs... (I've had weird segfaults for instance).
Cheers,
Till

> --
> regards,               tf@cip.physik.uni-muenchen.de              (o_
>  Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
> (lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
> (if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)
>
> _______________________________________________
> 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] recursive or loop

[Thomas Fischbacher]

On Wed, 8 Mar 2006, Till Varoquaux wrote:

> I beleive specifying Marshal.Closures when marshalling should do the trick...

Have you ever tried this with production code? Say, from the toplevel? 
Marshalling Closures is severely limited (aside from the fact that the 16 
MB string length often hits badly when one tries to marshal closures).

I would not recommend it.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] recursive or loop

[Jon Harrop]

On Wednesday 08 March 2006 22:13, Thomas Fischbacher wrote:
> On Wed, 8 Mar 2006, Till Varoquaux wrote:
> > I beleive specifying Marshal.Closures when marshalling should do the
> > trick...
>
> Have you ever tried this with production code?

Yes.

> Say, from the toplevel?

I don't use the top-level for my production code.

> Marshalling Closures is severely limited (aside from the fact that the 16
> MB string length often hits badly when one tries to marshal closures).

Presumably only when you try to marshal your closure to a string on a 32-bit 
machine?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] recursive or loop

[Michael Wohlwend]

On Monday 06 March 2006 15:15, you wrote:
> > If you're doing purely functional programming then you'll be passing the
> > state as an argument to the recursive function.
>
> How do you restore the call stack?

yes the state is not the problem, the callstack is the (my) problem...

 Michael

Re: [Caml-list] recursive or loop

[Thomas Fischbacher]

On Mon, 6 Mar 2006, Jonathan Harrop wrote:

> >How do I jump out of a recursive algorithm and be able to 
> >continue it at the same point?
> 
> If you're doing purely functional programming then you'll be passing the state as an argument to the 
> recursive function.

How do you restore the call stack?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] recursive or loop

[Jonathan Harrop]

On Mon Mar  6 12:09 , Michael Wohlwend <micha-1@fantasymail.de> sent:
>Is that true?

No.

>How do I jump out of a recursive algorithm and be able to 
>continue it at the same point?

If you're doing purely functional programming then you'll be passing the state as an argument to the 
recursive function. So you just raise an exception that carries the current state, catch it outside 
and save the state. To restart you just load the state and pass it as an argument to the recursive 
function.

If you're doing impure programming (i.e. with side-effects) then you do the same sort of thing but 
instead of carrying the state in the exception you have to capture it yourself (as you do in the 
looping version) and reset it yourself before you restart.

There is probably no difference in difficulty.

Cheers,
Jon.