Encore du pattern matching et des streams

Encore du pattern matching et des streams

[cr]

Ok, les arguments de Michel Mauny, pour la factorisation m'ont a peu pres
convaincu.

Quand au patterne matching destructif, je repond a Chet Murphy :
 
> C'est vrai qu'on garde "les bonnes proprietes" en utilisant un
> langage purement fonctionnel.  Mais ... en tant que programmeur qui
> n'est meme pas satisfait avec Lucid CommonLisp, ne parlons pas de
> SML/CAML/gnagna, je trouve qu'on a des anne'es-lumie`res a` traverser avant
> qu'on puisse dire que nos langages sont assez efficaces pour qu'on puisse
> garder des choses comme les flux (streams) fonctionnels.

Les flux (streams) fonctionnels, ne sont rien de plus que des listes
eventuellement infinies. De toutes facons, les streams actuels de
camllight (avec correction du bug, j'ai la chance d'avoir le patch pour le
corriger) sont bien des listes infinies fonctionnelles. La fonction
"stream_get" existe !

Donc un patterne matching non destructif ne changera rien a la representation
des streams. 

> 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.  Et
> caml-light, c'est cense' etre un langage d'aujourd'hui _et_ demain.
> Pas simplement demain.  Comme disait qqun: "la verification formelle,
> c'est l'avenir de l'informatique - ca l'a ete toujours, et ca le sera
> toujours".

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. 

> Mais, plus se'rieusement, j'ai des objections a` un langage dans lequel
> on e'crit des programmes manipulant des flux fonctionnels.  C'est
> tre`s bien quand on ecrit simplement des flux et des motifs de flux.
> Mais quand on les me'lange avec d'autres fonctions, il me
> faudrait passer comme argument, et recuperer comme resultat, tous les
> flux que j'utilise.

Manipuler des flux fonctionnels (que sont actuellement les streams de caml)
n'empeche pas d'avoir des pointeurs (references) globaux qui pointent sur des
streams pour simuler le pattern matching destructif. Cela n'est pas trop
couteux.

> ....
> Si on l'ecrit dans un
> langage sans flux destructifs, il reste au PROGAMMEUR a` traduire
> ce programme dans le langage pauvre et purement fonctionnel.

Je ne parle pas de programmes dans un langage purement fonctionnelle, mais
simplement de changer le comportement du patterne matching sur les streams,
qui si l'on oublie la fonction stream_next semblent purement fonctionnels.

> .......

Donc en resume :

	- Pour moi, si l'on excepte le patterne matching et la fonction
stream_next, et que l'on a le patch pour corriger le bug, les streams sont
purement fonctionnels.

	- Alors pourquoi ne pas changer le comportement du patterne matching ?

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

	- 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.


Christophe

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

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

[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