Date: Tue, 2 Nov 1993 11:46:20 +0100
From: lsanchez@dit.upm.es (Luis Sanchez Fernandez)
Message-Id: <199311021046.AA05690@yeti.dit.upm.es>
To: caml-list@margaux
Subject: Lazy evaluation and caml-light
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