caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
From: lsanchez@dit.upm.es (Luis Sanchez Fernandez)
To: caml-list@margaux
Subject: Lazy evaluation and caml-light
Date: Tue, 2 Nov 1993 11:46:20 +0100	[thread overview]
Message-ID: <199311021046.AA05690@yeti.dit.upm.es> (raw)

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









             reply	other threads:[~1993-11-03  8:49 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
1993-11-02 10:46 Luis Sanchez Fernandez [this message]
1993-11-03 19:37 ` Christophe Raffalli
1993-12-09 19:36 Luis Sanchez Fernandez

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=199311021046.AA05690@yeti.dit.upm.es \
    --to=lsanchez@dit.upm.es \
    --cc=caml-list@margaux \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).