Re: Lazy evaluation and caml-light

Re: Lazy evaluation and caml-light

[Luis Sanchez Fernandez]

Hi,

this e-mail is related to the answer to another one that I sent
a month (more or less) ago. Sorry for the delay. Because of the
delay, I'm including the previous one to help to fix the ideas.


	The problem in your program is this function~:

	let rec recursive sb sd=selec({state=Evaluated (append true sb)},sd,
	   F(fun ()->distr2(sb,{state=Evaluated (recursive sb sd)})));;

	With the recursive call you compute an infinite number of time 
	the value of
	
	(recusive sb sd) !!!!!

You are right. That was the reason because I sent the first e-mail.
I didn't know how to do it better.

	Here is a better way to write the same program:

	**********************************************************************
	type 'a stream_aux = Str of ('a * 'a stream)
	                   | Unevaluated of (unit -> 'a stream)
	                   | Not_Ready (* use for fix_point only *)

	and 'a stream == 'a stream_aux ref;;

	let rec Eval p = p := Eval' !p; !p
	where Eval' = function
	  Str _ as s -> s
	| Unevaluated f -> Eval (f ())
	| Not_Ready -> raise (Failure "Can't evaluate any more")
	;;
	  
	let fix_point f = 
	  let fp = ref Not_Ready in 
	  fp := !(f fp);
	  fp
	;;

Mmm. I think that now I understand how fix_point works. The trick
is that the system keeps the local variable fp AFTER 
fix_point is called. If I call twice to fix_point,
two different local variables are kept. Am I right?

	let append x ls = ref (Str (x,ls));; (* not usefull *)
	let append' x f a = ref (Str(x, ref (Unevaluated (fun () -> f a))));;
	let stop_eval f a = ref (Unevaluated (fun () -> f a));;

	let rec selec (f,g,h) = 
	match  (Eval f) with Str (sf,rf) -> 
	  if sf then
	    match (Eval g) with Str(sg,rg) -> append' sg selec (rf,rg,h)
	  else
	    match (Eval h) with Str(sh,rh) -> append' sh selec (rf,g,rh);;

	let rec distr2 (f,g)= 
	let (Str(sf,rf)) = (Eval f) and (Str(sg,rg)) = (Eval g) in 
	  if not sf then 
	    append' sg distr2 (rf,rg)
	  else 
	    distr2 (rf,rg);;

	let rec recursive (sb,sd) = 
	  fix_point f where
	  f = function x -> selec (
	        (append true sb),sd,
	        stop_eval distr2 (sb,x))
	;;


Thanks for the help,

Luis Sanchez.

Lazy evaluation and caml-light

[Christophe Raffalli]

The problem in your program is this function~:

let rec recursive sb sd=selec({state=Evaluated (append true sb)},sd,
   F(fun ()->distr2(sb,{state=Evaluated (recursive sb sd)})));;

With the recursive call you compute an infinite number of time the value of 
(recusive sb sd) !!!!!

Here is a better way to write the same program:

******************************************************************************
type 'a stream_aux = Str of ('a * 'a stream)
                   | Unevaluated of (unit -> 'a stream)
                   | Not_Ready (* use for fix_point only *)

and 'a stream == 'a stream_aux ref;;

let rec Eval p = p := Eval' !p; !p
where Eval' = function
  Str _ as s -> s
| Unevaluated f -> Eval (f ())
| Not_Ready -> raise (Failure "Can't evaluate any more")
;;
  
let fix_point f = 
  let fp = ref Not_Ready in 
  fp := !(f fp);
  fp
;;

let append x ls = ref (Str (x,ls));; (* not usefull *)
let append' x f a = ref (Str(x, ref (Unevaluated (fun () -> f a))));;
let stop_eval f a = ref (Unevaluated (fun () -> f a));;

let rec selec (f,g,h) = 
match  (Eval f) with Str (sf,rf) -> 
  if sf then
    match (Eval g) with Str(sg,rg) -> append' sg selec (rf,rg,h)
  else
    match (Eval h) with Str(sh,rh) -> append' sh selec (rf,g,rh);;

let rec distr2 (f,g)= 
let (Str(sf,rf)) = (Eval f) and (Str(sg,rg)) = (Eval g) in 
  if not sf then 
    append' sg distr2 (rf,rg)
  else 
    distr2 (rf,rg);;

let rec recursive (sb,sd) = 
  fix_point f where
  f = function x -> selec (
        (append true sb),sd,
        stop_eval distr2 (sb,x))
;;


let rec strinf =fun []->failwith "lista vacia" | (a::b)-> append' a strinf b;;

let rec l1=false::false::false::false::false::true::true::false::false::true::l1;;
let rec l2=1::2::3::4::5::6::7::8::9::l2;; 
let s1=stop_eval strinf l1;; 
let s2=stop_eval strinf l2;; 
let s3=recursive (s1,s2);;

let rec get s = function
  0 -> ()
| n -> match  (Eval s) with Str (sf,rf) ->
 print_int sf; print_string " "; get rf (n -1)
;;

Lazy evaluation and caml-light

[Luis Sanchez Fernandez]

Dear Sir,

I have two questions, one related to caml-light and other
related to caml.

The first question is about using lazy evaluation in caml-light.
I have implemented the stream type using an example that I have
got from the caml-list. The problem appears trying to define a
stream which nth value depends (among other things) of previously
evaluated values of the same stream. The problem is that
with the code I'm using the system computes again
the previous values because it doesn't realize that they
have been previously calculated. Because of this
the system loses a lot of time. Here there is an
example:

*****************************************************************************
type 'a suspension =
  { mutable state: 'a suspension_state }
and 'a suspension_state =
    Unevaluated of (unit -> 'a)
  | Evaluated of 'a
;;

let F expr =
  { state = Unevaluated expr }
;;

let df susp =
  match susp.state with
    Unevaluated f ->
      let val = f () in
        susp.state <- Evaluated val; val
  | Evaluated val ->
      val
;;
type 'a stream = Str of ('a * 'a stream suspension);;
(* until here, the code taken from  caml-list *)
let first (Str(a,b)) = a;; 
let rest (Str(a,b)) = b;;
let append x ls = Str (x,ls);;

let rec selec (f,g,h) =
        if first (df f)
        then Str(first (df g),F (fun ()->
             selec(rest (df f),rest (df g),h)))
        else Str(first (df h),F (fun ()->
             selec(rest (df f),g,rest (df h))));;

let rec distr2 (f,g)= 
        if not (first (df f))
        then Str(first (df g),F (fun ()->distr2(rest (df f),rest (df g))))
        else distr2 (rest (df f),rest (df g));;

let rec recursive sb sd=selec({state=Evaluated (append true sb)},sd,
   F(fun ()->distr2(sb,{state=Evaluated (recursive sb sd)})));;

let rec resul ls=fun
    1->[first ls]
   |x->(first ls)::(resul (df (rest ls)) (x-1));;

let rec strinf =fun
    []->failwith "lista vacia"
   |(a::b)->Str (a,F (fun ()->strinf (b@[a])));;

let l1=[false;false;false;false;false;true;true;false;false;true];;
let l2=[1;2;3;4;5;6;7;8;9];;
let s1=strinf l1;;
let s2=strinf l2;;
let s3=recursive {state=Evaluated s1} {state=Evaluated s2};;
*****************************************************************************

When trying to obtain the first values of the stream s3
with the resul function the execution times I have
obtained with my PC in seconds are:

-------------------------------------------------------
|Number of values |  200 |  400 |  600 |  800 |  1000 |
|-----------------|------|------|------|------|-------|
|Execution time   |    9 |   38 |   94 |  175 |   280 |
-------------------------------------------------------

It is clear that this execution times are of order n*n
with the number of values. 
I can implement this code in caml using the lazy keyword
when defining the stream type and the execution times
are linear with the number of values.
With more complex functions the execution times in caml-light
could be even exponential but they keep linear in the caml version.
The question is if it is possible to make this execution
times linear in the caml-light version defining the 
recursive function as a function of the basic functions
selec, append and distr2.




The other question I have is if you are going to prepare a
version of caml for LINUX. I would be very interested
in such that version.

Thank you very much for your help,

Luis Sanchez

e-mail: lsanchez@dit.upm.es