flux et filtrage de flux, Stream pattern matching

flux et filtrage de flux, Stream pattern matching

[murthy]

Hum ... OK ... si le debat est ouvert, je dirai qqchose pour une
implementation destructive.

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.

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

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.

Bien, c'est toujours faisable.  Aussi faisable qu'utiliser des
arguments supplementaires plutot qu'utiliser un champs mutable.  Et
aussi inefficace en termes de temps de programmation et d'exe'cution.

Et, encore pire, on peut dire qu'un programme ecrit comme ca, c'est
plus propre - mais, en fait, c'est simplement ecrit dans la "monade"
des flux, sauf que c'est sans l'aide des "definitions" de monades.
C'est-a-dire, il n'y a qu'un programme source.  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.

Si on l'ecrit dans un langage avec flux destructifs, le compilo le
fait.

En tout cas, c'est le meme programme.  Et ce sera aussi difficile de
verifier, une fois traduit dans le langage purement fonctionnel, que
ce l'etait dans le langage imperatif - la difference est une simple
expansion des definitions.

Je trouverai difficile la tache de programmer dans un langage sans
flux destructifs - aussi difficile que dans un langage purement
fonctionnel.

Et, pour revenir a` l'argument premier, j'attends toujours un systeme
lazy/purement fonctionnel qui est assez efficace pour qu'on puisse l'utiliser
pour la programmation systeme.  Les langages stricts comme ML sont a`
peine assez efficace.


Ah, oui - aussi, dire que les langages purement fonctionnels sont
assez efficace - a peu pres un facteur de 2 (ou 4 ou 10 ou whatever)
(up to a factor of 2 or whatever) n'est pas une reponse - le meilleur
espoir de tous les optimiseurs du monde, c'est de couper des facteurs
constants.

--chet--

[ Note du mode'rateur:
  La politique de l'e'quipe d'imple'mentation Caml sur le sujet a
  toujours e'te' pragmatique: on ne peut pas raisonnablement se passer
  de traits impe'ratifs, pour des raisons d'efficacite' (complexite'
  des algorithmes) aussi bien que de lisibilite'. La se'mantique
  de'notationnelle d'un programme qui passe explicitement une me'moire
  en argument supple'mentaire a` toutes les fonctions, est purement
  fonctionnelle et purement illisible.
  Les arguments en faveur du ``purement fonctionnel'' ne peuvent e^tre
  eux aussi que de pure lisibilite' et e'le'gance. Ce point est
  particulie`rement e'vident dans l'arithme'tique de Caml V3.1. La
  programmation purement fonctionnelle avec le type num est
  incomparablement plus facile et lisible que la programmation
  impe'rative avec le type nat. Il faut alors ne pas he'siter a`
  l'employer: il faut impe'rativement programmer fonctionnel. Ce n'est
  pas une raison pour l'e'riger en syste`me et se forcer a` ne jamais
  employer d'effets de bords.
  Les arguments de ``re'sultat e'quivalent'' sont des arguments de
  matheux pas d'informaticien.
  Finalement le proble`me vient de la connotation du mot ``pur''.
  Supposons que l'usage soit d'employer le mot ``be^te'' a` la place,
  personne ne viendrait re'clamer une version ``be^tement fonctionnelle''
  des flux! (Je me sens me^me obliger d'ajouter imme'diatement que je
  ne conside`re pas cette demande comme une be^tise, mais bien comme
  une purise)

Pierre Weis
----------------------------------------------------------------------------
Formel Project
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
----------------------------------------------------------------------------
]


From weis@margaux  Wed Mar 17 11:31:14 1993
Received: by margaux.inria.fr, Wed, 17 Mar 93 17:58:48 +0100
Received: from pauillac.inria.fr by margaux.inria.fr, Wed, 17 Mar 93 11:31:14 +0100
Received: by pauillac.inria.fr; Wed, 17 Mar 93 11:31:10 +0100
Message-Id: <9303171031.AA15612@pauillac.inria.fr>
Subject: Re: Stream patterne matching
To: cr@dcs.ed.ac.uk
Date: Wed, 17 Mar 1993 11:31:10 +0100 (MET)
Cc: Michel.Mauny@inria.fr, caml-list@margaux
In-Reply-To: <26877.9303152045@damsay.dcs.ed.ac.uk> from "cr@dcs.ed.ac.uk" at Mar 15, 93 08:45:23 pm
From: Michel.Mauny@inria.fr (Michel Mauny)
Reply-To: Michel.Mauny@inria.fr
Organization: INRIA, BP 105, F-78153 Le Chesnay Cedex, France
Phone: (+33) 1 39 63 57 96 -- Fax: (+33) 1 39 63 53 30
X-Mailer: ELM [version 2.4 PL13]
Content-Type: text
Content-Length: 3052      
Sender: weis@margaux
Status: O

Christophe e'crit:

> Un autre petit probleme avec le pattern matching : le fait qu'il soit
> predictif (c.a.d. qu'il decide uniquement sur le premier element du stream).
> 
> Cela n'est pas grave : si l'on veut matcher [< '0 ; '1>] ou [< '0 ; '2 >], 
> on ecrit [< '0 ; f c >] ou f match [< '1 >] ou [< '2 >]. 
> 
> Est-ce que le compilateur ne pourrait pas faire cela automatiquement ?
> 
> C'est a dire faire cette decomposition des qu'un certain nombre de patterns
> consecutifs commencent par une suite de patterns egaux (au noms des variables
> pres) ?
> 
> Cela simplifierait l'ecriture de la plupart des grammaires courantes. Tout en
> sachant bien que la semantique est la meme. 

On nous a de'ja` fait cette demande un certain nombre de fois, et ma
re'ponse a toujours e'te' ne'gative. Bien que je comprenne l'utilite'
et la ne'cessite' de la factorisation gauche sur des *grammaires*,
elle me semble dangereuse sur des *analyseurs*, car pas tre`s claire
se'mantiquement.

La factorisation gauche d'une grammaire BNF produit une grammaire
*e'quivalente* a` la grammaire originale (i.e. engendrant le me^me
langage).

Les de'finitions d'analyseurs a` base de streams ne sont pas des
grammaires, me^me si quelquefois la structure d'un analyseur
reconnaissant un langage L peut e^tre semblable a` la structure de la
grammaire BNF engendrant ce me^me langage L.

Une factorisation gauche d'un analyseur ne produit en ge'ne'ral pas un
analyseur e'quivalent.

On me re'pondra "Yaka de'finir la se'mantique des analyseurs en
fonction d'une e'ventuelle factorisation gauche". Le proble`me, c'est
que dans la situation actuelle, l'application d'un analyseur
parame'tre' pp a` un analyseur p est ope'rationnellement e'quivalente
a` l'analyseur obtenu par substitution de la valeur de p au parame`tre
formel de pp dans le corps de pp (ca s'appelle la beta-reduction dans
le lambda-calcul, excusez-moi d'enfoncer des portes ouvertes):

En d'autres termes, si pp = function a -> E(a), et p est un analyseur
quelconque, alors:

        pp p <-> E(p') ou` p' est la valeur de p

Pour e^tre comple`tement rigoureux, il faut travailler dans la
se'mantique ope'rationnelle du lambda-calcul par valeur avec filtrage,
des environnements, etc.

Or, il se peut que E(p') soit factorisable a` gauche, et que (pp p) ne
le soit pas. Le comportement de E(p') et de (pp p) n'est donc en
ge'ne'ral pas e'quivalent en cas de factorisation gauche.

Et qu'on ne me re'ponde pas que ce n'est pas grave: qui n'a pas
abstrait une sous-expression dans une fonction afin d'obtenir une
fonction plus ge'ne'rale? Quand on fait ca, on est endroit d'espe'rer
des programmes e'quivalents, pour le moins.

Pour re'sumer, attendons d'avoir une notion de grammaire a` partir
desquelles on calculera des parsers en faisant toutes les
optimisations possibles et imaginables. Le point, c'est que ces
optimisations seront juge'es correctes relativement a` une certaine
se'mantique de ces grammaires, et feront partie du processus de
compilation de ces grammaires en des analyseurs.

Michel