Streams

Streams

[Error404]

Hi,

I'm looking for some streams related tutorial or any other info. 
By stream i mean something like this (I don't know exact definition):

open Lazy;;
type 'a stream = Nil | Cons of 'a Lazy.t * 'a stream Lazy.t;;

(* For example stream of 'integers from x' would look like this: *)

let rec intsfrom x =
  Cons(lazy x,lazy (intsfrom (x+1)));;

If you know any www/book or anything on this kind of streams please mail me (error92@tlen.pl).
Many thanks.

Re: [Caml-list] Streams

[Jonathan Roewen]

The Stream module provides exactly this functionality.

With camlp4o, you can use the old parser syntax too.

#load "camlp4o.cma";

let rec enum_from n = [< 'n; enum_from (n + 1) >];;

let first_10 = Stream.npeek 10 (enum_from 1);;

Streams are also lazily evaluated. More complex examples can be had
too, and there is the parser keyword to deconstruct streams as well.
You should be able to find more info in the camlp4 manual at the caml
site.

Jonathan

On 8/10/06, Error404 <error92@tlen.pl> wrote:
> Hi,
>
> I'm looking for some streams related tutorial or any other info.
> By stream i mean something like this (I don't know exact definition):
>
> open Lazy;;
> type 'a stream = Nil | Cons of 'a Lazy.t * 'a stream Lazy.t;;
>
> (* For example stream of 'integers from x' would look like this: *)
>
> let rec intsfrom x =
>  Cons(lazy x,lazy (intsfrom (x+1)));;
>
> If you know any www/book or anything on this kind of streams please mail me (error92@tlen.pl).
> Many thanks.
>
> _______________________________________________
> 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] Streams

[Martin Jambon]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 975 bytes --]

On Thu, 10 Aug 2006, Error404 wrote:

> Hi,
>
> I'm looking for some streams related tutorial or any other info.
> By stream i mean something like this (I don't know exact definition):
>
> open Lazy;;
> type 'a stream = Nil | Cons of 'a Lazy.t * 'a stream Lazy.t;;
>
> (* For example stream of 'integers from x' would look like this: *)
>
> let rec intsfrom x =
>  Cons(lazy x,lazy (intsfrom (x+1)));;
>
> If you know any www/book or anything on this kind of streams please mail me (error92@tlen.pl).
> Many thanks.

I call this a lazy list. Anyway, I use the following definition:

   type 'a l = Empty | Cons of 'a * 'a t
   and 'a t = 'a l lazy_t   (* only one lazy object per cell *)

See attachment for the full implementation.

You can manipulate such lists like real lists, only the syntax is less 
comfortable. They are different from streams in the sense of the standard 
Stream module, which are mutable.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

[-- Attachment #2: Type: TEXT/PLAIN, Size: 2295 bytes --]

(* lazy lists *)

type 'a l = Empty | Cons of 'a * 'a t
and 'a t = 'a l lazy_t

let empty = lazy Empty
let is_empty l = Lazy.force l = Empty

let rec force l =
  match Lazy.force l with
      Empty -> ()
    | Cons (hd, tl) -> force tl

let hd l =
  match Lazy.force l with
      Empty -> invalid_arg "Lizt.hd"
    | Cons (x, _) -> x

let tl l =
  match Lazy.force l with
      Empty -> invalid_arg "Lizt.tl"
    | Cons (_, x) -> x

let peek1 l = 
  match Lazy.force l with
      Empty -> None
    | Cons (x, _) -> Some x

let peek2 l =
  match Lazy.force l with
      Empty -> None
    | Cons (x1, l) -> 
	match Lazy.force l with
	    Empty -> None
	  | Cons (x2, l) -> Some (x1, x2)

let peek3 l =
  match Lazy.force l with
      Empty -> None
    | Cons (x1, l) -> 
	match Lazy.force l with
	    Empty -> None
	  | Cons (x2, l) -> 
	      match Lazy.force l with
		  Empty -> None
		| Cons (x3, l) -> Some (x1, x2, x3)


let rec of_list l =
  lazy (match l with
	    [] -> Empty
	  | hd :: tl -> (Cons (hd, of_list tl)))

let rec to_list l =
  match Lazy.force l with
      Empty -> []
    | Cons (hd, tl) -> hd :: to_list tl

let from f =
  let rec make f i =
    lazy (match f i with
	      None -> Empty
	    | Some x -> Cons (x, make f (i+1))) in
  make f 0

let rec append l1 l2 =
  lazy (match Lazy.force l1 with
	    Cons (hd, tl) -> Cons (hd, (append tl l2))
	  | Empty -> Lazy.force l2)

let rec iter f l =
  match Lazy.force l with
      Empty -> ()
    | Cons (hd, tl) -> f hd; iter f tl

let rec map f l =
  lazy (match Lazy.force l with
	    Empty -> Empty
	  | Cons (hd, tl) -> Cons (f hd, map f tl))

let filter f l =
  let rec loop f l =
    match Lazy.force l with
	Empty -> lazy Empty
      | Cons (hd, tl) -> 
	  if f hd then lazy (Cons (hd, loop f tl))
	  else loop f tl in
  lazy (Lazy.force (loop f l))

let optmap f l =
  let rec loop f l =
    match Lazy.force l with
	Empty -> lazy Empty
      | Cons (hd, tl) -> 
	  match f hd with
	      Some y -> lazy (Cons (y, loop f tl))
	    | None -> loop f tl in
  lazy (Lazy.force (loop f l))

let rec fold_left f accu l =
  match Lazy.force l with
      Empty -> accu
    | Cons (hd, tl) -> fold_left f (f accu hd) tl

Re: [Caml-list] Streams

[Chris King]

On 8/10/06, Jonathan Roewen <jonathan.roewen@gmail.com> wrote:
> The Stream module provides exactly this functionality.

Don't forget about Fstream
(http://caml.inria.fr/pub/docs/manual-camlp4/manual008.html#toc30); it
does the same thing as Stream but in a functional manner (and with a
similar syntax, pa_fstream.cmo).

Re: [Caml-list] Streams

[Jon Harrop]

On Thursday 10 August 2006 11:51, Error404 wrote:
> I'm looking for some streams related tutorial or any other info.
> By stream i mean something like this (I don't know exact definition):
>
> open Lazy;;
> type 'a stream = Nil | Cons of 'a Lazy.t * 'a stream Lazy.t;;
>
> (* For example stream of 'integers from x' would look like this: *)
>
> let rec intsfrom x =
>   Cons(lazy x,lazy (intsfrom (x+1)));;
>
> If you know any www/book or anything on this kind of streams please mail me
> (error92@tlen.pl). Many thanks.

I just posted a link to some stuff on streams in the context of parsing but 
you can write intsfrom as:

# #load "camlp4o.cma";;
        Camlp4 Parsing version 3.09.2

# let rec intsfrom n = [< 'n; intsfrom(n+1) >];;

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

Re: streams

[Francis Dupont]

A propos de streams (flux dans le Val de Loire), en Lazy CAML c'est
un type liste sans contructeur [] (appele aussi 'Nil) et avec un
constructeur :: (appele aussi 'Cons) lazy (paresseux).
Un exemple figure dans ma these dans la section sur les applications
de l'evaluation paresseuse, en haut de la page 53:

type 'a stream = { lazy Hd : 'a ; lazy Tl : 'a stream };;

(PS: comme il n'y a qu'un seul constructeur on ne met pas de type somme).
(PS: une variante consiste a ne rendre que Tl paresseux).
Les valeurs de ce type sont toujours infinies et necessitent donc
une evaluation paresseux (implicite ou explicite, cad codee avec des fonctions)

Francis.Dupont@inria.fr

streams

[cr]

Le reponse de Xavier me satisfait pleinement. Et, desormais, je jette
stream_get a la poubelle, et les streams sont des donnees imperatives ....

D'ailleurs, mon programme qui l'utilisait, apres optimisation ne l'utilise
plus !

Par contre, j'aimerais bien des listes infinies fonctionnelles, avec le
pattern matching et tout le tin-toin. Peut-etre avant la release 1.0 de 2004 ?

(**************
Attention au terme "liste lazy" ????

Pour moi "liste lazy" = liste calculee lorsque l'on s'en sert la premiere fois,
puis conservee pour les utilisations futures. 

Donc les listes lazy permettent de faire des listes infinies, mais ce n'est
pas la meme chose.

Peut-etre que ma terminologie n'est pas la bonne ?
**************)


A propos des listes lazy, voici un petit programme : (les listes s'appelle des
streams ..... pardon)

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
-------------------------stream.ml-------------------------
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

(* le type des streams *)
type 'a l_stream =
	L of unit -> 'a * 'a stream
|	C of 'a * 'a stream
and 'a stream == 'a l_stream ref;;

(* deux cons *)
let Cons a s = ref (C (a,s));;
let LCons a s b = ref (L (function () -> (a,s b)));;

let stream_from f = 
  let rec stream_from_aux () = ref (L (function
	() -> (f(),stream_from_aux ())))
  in stream_from_aux ()
;;

let stream_get  = function
	ref (C (a,s)) -> (a,s)
|	ref (L f) as p -> let c = f () in
		p := C c;c
;;

let stream_next  = function
	ref (C (a,s)) as p -> p := !s;a
|	ref (L f) as p -> let (a,s) = f () in
		p := !s;a 
;;

(* pour eviter de garder une copie calculer quand on n'en a pas besoin *)
let stream_copy = function
	ref p -> ref p
;;

(* version destructive de do_stream et do_stream_bound *)
let do_stream_del f s = 
  while true do
    f (stream_next s)
  done
;;

let do_stream_bound_del f n s = 
  let pn = ref n in
  while !pn > 0 do
    f (stream_next s);
    decr pn
  done
;;

(* version non destructive *)
let do_stream f s = 
  let ps = ref s in
  while true do
    let (a,s0) = (stream_get !ps)  in
    f a;ps:=s0
  done
;;

let do_stream_bound f n s = 
  let ps = ref s in
  let pn = ref n in
  while !pn > 0 do
    let (a,s0) = (stream_get !ps)  in
    f a;decr pn;ps := s0
  done
;;

(* le map sur les streams *)
let map_stream f s = 
  let rec map_aux = function
        ref (C (a,s)) -> ref (L (function 
          () -> (f a,map_aux s)))
|	ref (L g) as p -> ref (L (function
          () -> let (a,s) as c = g () in
		p := C c;(f a,map_aux s)))
  in map_aux s
;;

(* une fonction un peu tordu *)
let rec_stream f s = 
   let rec rec_aux = function
        ref (C (a,s)) -> 
          f a (function () -> (rec_aux s))
|	ref (L g) as p -> 
          let (a,s) as c = g () in
		p := C c;f a (function () -> (rec_aux s))
  in rec_aux s
;;
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   
---------------------------------------------------------------
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Et voici un peti programme pour le stream des nombres premiers.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
----------------primes.ml--------------------------------------
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

#open "stream";;

let init_stream = 
  let rec init_aux n = 
    LCons n init_aux (succ n)
  in init_aux 2
;;

let raye n s = 
  let raye_aux a fs =
    if a mod n = 0 then 
      fs ()
    else 
      LCons a fs ()
  in rec_stream raye_aux s
;;

let primes =
  let rec primes_aux s =
    let (a,s) = stream_get s in
      LCons a primes_aux (raye a s)
  in primes_aux init_stream
;;

let print_int_stream = do_stream_bound
  (function a -> print_int a; print_string " "; flush stdout);;
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
----------------------------------------------------------------
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Remarque, ce programme est tres gourmant ...., et ce n'est pas parce-que la
liste est "lazy", j'ai essaye les streams pas "lazy" (sans references) et ca
craque quand meme tres vite en caml-light.

Pourquoi ? Je m'en doute un peu, mais peut-on reparer ca ? 


Christophe

PS: j'ai essaye en lsml (version 0.1) avec les listes built-in, c'est pire. 
lml (version 0.97) s'en tire bien.

Re: streams

[Xavier Leroy]

Chic, on commence a faire de l'ideologie! J'en profite pour vous
chanter mon "Credo", avec lequel un certain nombre de gens de
l'equipe Caml seront d'accord, je pense:

1- Les effets de bord et le style imperatif de programmation sont
essentiels non pas tant pour des raisons d'efficacite, mais pour des
raisons de clarte et de bonne structuration du code qu'on ecrit.
Contrairement a la propagande, du code imperatif ecrit avec soin, gout
et discernement est bien souvent plus clair que du code fonctionnel,
car il laisse implicite un certain nombre de choses (valeurs courantes
des variables, etats des I/O) qui doivent etre rendues explicites en
fonctionnel pur, alors que le bon programmeur les a tres clairement en
tete. Le code imperatif est egalement plus sur car il
permet de tenir a jour localement un etat local, et garantir ainsi
facilement des invariants sur cet etat local. Meme si le style
imperatif allait deux fois moins vite que le style applicatif, je
continuerai a utiliser le style imperatif a chaque fois que j'en
ressens le besoin.

2- Les entrees/sorties sont infiniment plus claires en imperatif qu'en
applicatif. Expliciter l'enchainement des I/O par des constructions de
listes, des bidules a continuations facon Haskell, voire des monades,
me semble nuire extremement a la clarte et a la modularite des
programmes.

3- Les streams de Caml sont concus comme un dispositif
d'entree-sortie. Ce n'est pas a priori une structure de donnee "liste
paresseuse" d'emploi general, meme si l'implementation actuelle des
streams peut en fait etre utilisee ainsi, comme Christophe le
souligne, mais une structure specialisee aux problemes
d'entree-sortie. (Dans cette optique, fournir stream_get est sans
doute une erreur; peut-etre aurions-nous du fournir a la place des
operations de plus haut niveau, comme par exemple une primitive qui
fait une copie d'un stream, au lieu de dire ``boarf, c'est
definissable avec stream_get''.)

4- Les operations de lecture sur les streams sont donc tout
naturellement en place; et je continue a me demander si les operations
d'ecriture ne devraient pas elles aussi etre en place.

5- On a parfois besoin de vraies listes paresseuses. On devrait alors
se les definir, ou les avoir dans la bibliotheque standard, mais
distinctes des streams. On doit meme pouvoir fournir des fonctions de
conversion stream <-> liste paresseuse raisonnablement efficaces, pour
faciliter l'interaction entre les deux.

Voila. Et maintenant, parlons d'efficacite:

1- Le GC.

Chet: C'est aussi vrai qu'un jour, le GC pourrait recuperer les donne'es
      utilise'es efficacement. Ce jour-la, ce n'est pas aujourd'hui. 

Christophe: Le GC actuel doit bien recuperer le debut des streams quand
      il ne sont plus utilises ! ou du moins je l'espere, sinon les
      programmes que j'ecris vont s'ecrouler.

Le GC de Caml Light n'est pas si inefficace que Chet le dit, surtout
compare au reste de l'implementation, puisqu'il ne depasse jamais 10%
du temps total d'execution. Des programmes qui sont de vrais memory
pigs (au hasard: les Constructions) tournent sans surcharger le GC, ce
qui n'est le cas ni en Caml V3.1, ni sans doute en SML-NJ.

Pour les streams, faire "stream_next s", ou bien "stream_get s" puis
abandonner s produit a peu pres la meme quantite de travail pour le
GC. Le probleme avec stream_get et les listes paresseuses, c'est que
les fuites de memoire sont beaucoup plus faciles a provoquer. Exemple:

        let s = stream_of_channel(open_in "/tmp/foo");;
        my_parser (my_lexer s);;

Dans le cas des flux fonctionnels, le global s pointe au debut du flux
pendant toute la suite du programme. my_lexer va parcourir le flux,
amenant en memoire tous les caracteres du fichier. A la fin, s pointe
vers la liste de tous les caracteres du fichier. Cette liste n'est pas
recuperable, puisque les variables globales sont des racines du GC. Et
en effet l'utilisateur peut tres bien acceder a s plus tard. Avec des
flux mutables, on n'a pas ce probleme: les cellules de liste sont
jetees au fur et a mesure qu'elles sont produites, c'est bien meilleur
pour le GC.

Ca n'est pas specifique au toplevel, d'ailleurs:

        let compile_program filename =
          let s = stream_of_channel(open_in filename) in
          let tokens = my_lexer s in
          let ast = my_parser tokens in
          ...

La aussi, "s" pointe sur la tete de la liste de tous les caracteres
lus pendant toute la duree d'execution de compile_program. Ce qui
signifie que cette liste ne peut pas etre recuperee par le GC pendant
l'evaluation des ... alors que vraisemblablement on n'en a plus
besoin. La liste ne peut etre recuperee qu'a la fin de
"compile_program", c'est-a-dire trop tard. Ou alors, il faut faire
tres attention au GC et ecrire autrement:

        let compile_program filename =
          let ast = my_parser(my_lexer(stream_of_channel(open_in filename))) in
          ...

La, y'a pas de fuite. Subtil, hein? Alors, bien sur, il y a des
techniques de compilation qui evitent les fuites, par une analyse de
duree de vie des variables bien sentie. Sauf que Caml Light 0.5 ne la
fait pas (et meme SML-NJ, pas directement en tout cas, quoique le CPS
donne un peu le meme resultat, oui mais leur mecanisme de closure
hoisting reintroduit des fuites, et je me demande si...). Je sais
faire, mais il faudra attendre Caml Light 1.0 (release prevue le 25
mars 2004).

> 	- L'utilisation des streams avec "stream_get" au lieu de "stream_next"
> fait-elle notablement baisser les performances ?

Mis a part les pb de fuites de memoire, je ne sais pas trop.
stream_get est plus compliquee que stream_next, y'a qu'a regarder le
source pour s'en rendre compte, mais bon, il faut bien reconnaitre que
stream_next lui-meme n'est pas aussi rapide qu'on pourrait le souhaiter...

> 	- Pour moi dans un langage fonctionnelle il doit y avoir des
> manipulations physiques, etc ..... Mais les fonctions de bases tel que le
> patterne matching devrait rester purement fonctionnelles.

Mhoui, belle profession de foi (sauf que "pattern" s'ecrit sans "e"
final, contrairement a "poterne"). J'en ai entendu pas mal, des comme
ca. "Le pattern-matching devrait rester purement fonctionnel". "Le
pattern-matching devrait etre en temps constant".  "Le if-then-else
devrait etre equivalent a un pattern-matching". Etc, etc. A chaque
fois, ca sonne bien, mais ces beaux preceptes partent d'a-priori
toujours discutables. Pour "le pattern-matching devrait rester
purement fonctionnel", l'a-priori est que le purement fonctionnel est
plus simple, plus elementaire, plus ``de base'' que l'imperatif.
Desole, mais c'est pas vrai. Pour "Le pattern-matching devrait etre en
temps constant", ca suppose que le programmeur n'a pas en tete le
modele operationnel du langage. Ca non plus, c'est pas vrai. Y'a plein
de ``principes'' de ce genre qu'on peut remettre en cause.

- Xavier