From mboxrd@z Thu Jan 1 00:00:00 1970 Received: by margaux.inria.fr, Tue, 16 Mar 93 18:56:59 +0100 Subject: flux et filtrage de flux To: caml-redistribution@margaux Date: Tue, 16 Mar 1993 18:56:59 +0100 (MET) X-Mailer: ELM [version 2.4 PL13] Content-Type: text/plain From: murthy@margaux Message-Id: <9370.732388390@margaux.inria.fr> To: caml-list@margaux Subject: Stream pattern matching Return-Receipt-To: murthy@margaux Date: Tue, 16 Mar 93 17:43:02 N 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