Stream patterne matching

Stream patterne matching

[cr]

Ok, Si j'ai bien compris le fait d'abstraire une re`gle fait perdre des
factorisations. Ce qui est illustre' par l'exemple suivant :

#let E = function
#  [< '0; '1 >] -> true
# |[< '0; '2 >] -> false;;

est factorisable. Mais

#let pp = function p -> function
#  [< '0; '1 >] -> true
# |[< p _ ; '2 >] -> false;;

ne l'est pas. Pourtant (pp (function [<'0 >] -> ())) est e'quivalent a` E.

Es-je bien compris ?

Pourtant, j'ai un doute. si l'on essaye E, on s'aperc,oit qu'il y a un cas
inutilise dans le patterne matching. Une factorisation est donc ne'cessaire. Il
faut la faire a la main ! Tandis que dans pp, le compilo ne bronche pas. caml
fait donc de'ja une diffe'rence entre les deux.

Ne pourrais t'on pas au moins faire la factorisation quand le compilo signale
un cas inutilise' dans le matching ? Avec e'ventuellement un warning pour
l'utilisateur ?

Mais l'essentiel n'est-il pas que si (pp p) est factorisable alors E(p') l'est
aussi ? (cela esr vrai, je pense ?)

Y a-t'il des exemples plus complexes ?

Christophe

PS: Je crois que je commence a jouer l'avocat du diable. En effet en regardant
a` nouveau les analyseur que j'ai pu ecrire, je me dis que je ne sais plus trop
si je veux la factorisation. 

En effet, j'e'tait un peu e'nerve a chaque foi que je m'apercevais qu'une
factorisation etait ne'cessaire, et que je devais donc taper une dizaine de
lignes supplementaires.

Mais au total, le programme est en gros deux fois plus gros qu'avec camlyacc
(sauf qu'avec camlyacc, je n'aurais pas pus l'ecrire !). Ce n'est pas si
terrible. 

Et, le fait de factoriser soi-meme permet d'avoir un programme dont le
comportement est limpide.

Je ne sais donc plus se que je veux !!!!!

PS-bis: Je suis sure que certain d'entre vous ont des syste`mes automatiques
pour gerer les accents. Moi j'utilise emacs pour lire mon courier, quelqu'un
peut-il me suggerer quelque-chose. 

Re: Stream patterne matching

[Michel Mauny]

> Ok, Si j'ai bien compris le fait d'abstraire une re`gle fait perdre des
> factorisations. Ce qui est illustre' par l'exemple suivant :
> 
> #let E = function
> #  [< '0; '1 >] -> true
> # |[< '0; '2 >] -> false;;
> 
> est factorisable. Mais
> 
> #let pp = function p -> function
> #  [< '0; '1 >] -> true
> # |[< p _ ; '2 >] -> false;;
> 
> ne l'est pas. Pourtant (pp (function [<'0 >] -> ())) est e'quivalent a` E.
> 
> Es-je bien compris ?

Oui, tout a` fait.

> Pourtant, j'ai un doute. si l'on essaye E, on s'aperc,oit qu'il y a un cas
> inutilise dans le patterne matching. Une factorisation est donc ne'cessaire. Il
> faut la faire a la main ! Tandis que dans pp, le compilo ne bronche pas. caml
> fait donc de'ja une diffe'rence entre les deux.

Le compilo fait une diffe'rence et il peut envoyer un warning dans le
premier cas, alors que dans le second, il ne sait rien du tout.

> Ne pourrais t'on pas au moins faire la factorisation quand le compilo signale
> un cas inutilise' dans le matching ? Avec e'ventuellement un warning pour
> l'utilisateur ?

Il y a une diffe'rence importante entre envoyer un warning disant a`
l'utilisateur:

        Attention: votre programme ne fait peut-e^tre pas ce que vous
        attendez de lui!

et un autre disant:

        Attention: j'ai CHANGE' votre programme de sorte qu'il fasse
        ce que (je suppose) que vous attendez de lui!

J'exage`re un peu (de'sole'), mais l'important est que le comportement
des analyseurs actuels est uniforme, pas de cas particuliers, et cela
en facilite l'explication. Encore une fois, sur une notion plus
"declarative" de grammaires, je crois qu'on pourra faire beaucoup plus
de choses (analyses et optimisations) inte'ressantes.

> Mais l'essentiel n'est-il pas que si (pp p) est factorisable alors E(p') l'est
> aussi ? (cela esr vrai, je pense ?)

Oui, je crois que c'est vrai, mais c'est une e'quivalence qu'on
voudrait, car l'exemple d'abstraction de sous-expression que je
donnais dans mon message pre'ce'dent est re'versible en ``inlining''.
Ces manipulations (a` la main) de programmes sont tre`s courantes, et
il serait dommage qu'elles soient trop complexes a` cause de
subtilite's ope'rationnelles.

> Y a-t'il des exemples plus complexes ?

On doit tomber sur de ve'ritables casse-te^tes lorsqu'il s'agit de
traduire une grammaire BNF existante (Yacc ou whatever) en analyseurs
de Caml-Light, mais je n'ai personnellement que peu d'expe'rience en
la matie`re.

Michel

Re: Stream patterne matching

[murthy]

CR==Christophe
MM==Michel Mauny

CR> Y a-t'il des exemples plus complexes ?

	MM> On doit tomber sur de ve'ritables casse-te^tes lorsqu'il
	MM> s'agit de traduire une grammaire BNF existante (Yacc ou
	MM> whatever) en analyseurs de Caml-Light, mais je n'ai
	MM> personnellement que peu d'expe'rience en la matie`re.

J'ai fait pas mal des parsers pour l'analyse syntaxique, au niveau de
lexing et aussi ua niveau de parsing.  C'est un peu dificil, mais pas
vraiement.  Il s'agit simplemet d'ecrire un "analyseur", comme Michel
disait, et pas un "grammaire".  C'est-a-dire, dites a l'ordinateur
exactement ce que tu veux qu'elle fasse.  C'est tout.

C'est vrai que la factorisation serait utile.  Mais, comme Michel
disait, seulement en certains cas.  Ces cas-la, sont les cas quand on
veut utiliser cette systeme des "analyseurs", etc, comme un systeme
des "grammaires".

Boeuf.  En Anglais.  Having factorization done automatically is only
useful when you are using parsers/printers as a grammar facility.  It
is NOT such a facility.  In lots of other cases, having factorization
around could be a very bad thing.  Because it would change the
behaviour of your program.

An analogy which is quite familiar could be an ML compiler which used
beta-reduction for code inlining, rather than beta-value reduction.
If you aren't careful, you can end up "improving" programs which do
not terminate, into programs which _do_ terminate.  Its easy to do.
And this is bad because when I start debugging a non-terminating
program, I cut out pieces of the code, and start running them in a
context which is different from that of the original program.

So if the compiler all of a sudden can do new optimizations, say,
because I feed in more specific arguments to a function, and this
causes the compiler to "make the function terminate", then I can't
even do debugging.

The same thing is going on here.  Factorization could make buggy
parsers become un-buggy, when I replace an abstract parser by
something more concrete.

And this would make debugging of analyzers impossible.  Completely
impossible.

And frankly, if that happened, I'd stop using them.

Besides, if you want a "grammar" facility, then just write one.  It
isn't that hard.

--chet--

Re: Stream pattern matching

[Xavier Leroy]

En plus de corriger l'orthographe de la ligne "Subject", je voudrais
juste faire remarquer que la factorisation gauche automatique des
analyseurs n'est non seulement pas vraiment souhaitable, mais encore
infaisable dans toute sa generalite a cause des effets de bords:

        let f = function [< p x; 'Terminal "foo" >] -> ...
                       | [< p x; 'Terminal "bar" >] -> ...

n'est pas factorisable, car rien ne vous dit que "p" va se comporter
de la meme maniere lorsqu'il est appele deux fois sur le meme flux.
Telle est la puissance et la gloire des langages algorithmiques, mes
freres. La factorisation gauche automatique ne serait possible que
pour des motifs commencant par des terminaux, ce qui n'est pas tres
interessant.

- Xavier

Stream patterne matching

[Daniel de Rauglaudre]

> From: cr@dcs.ed.ac.uk
> Date: Mon, 15 Mar 93 14:11:28 GMT
> Message-Id: <25753.9303151411@damsay.dcs.ed.ac.uk>
> To: caml-list@margaux.inria.fr
> Subject: Stream patterne matching
>
> Pour quelles raisons le pattern matching sur les streams est-t'il destructif ?
> 
> Est-ce simplement une question de performance. Si oui il faut que le gain soit
> important. En effet, le pattern matching destructif implique un effet de bord
> implicite. Je trouverais plus propre d'avoir a utiliser soi-meme un pointeur
> lorsque-l'on veux simuler le pattern matching destructif.

Personnellement, j'aimais bien aussi la version purement
fonctionnelle. L'imple'mentation ne pose pas de proble`me. Cela permet
en plus de pouvoir imple'menter e'ventuellement un backtrack limite',
ce que la version impe'rative ne permet pas de faire.

La`, il y a eu un choix a` faire. Je crois que l'argument de mes
petits camarades est que le stream doit pluto^t e^tre vu comme
"quelque chose venant de l'exte'rieur". En effet, "stream_from" et
"stream_of_channel" rec,oivent leurs donne'es d'ailleurs, donne'es
qu'on ne peut pas leur demander de "recracher" a` la demande, ce
qu'exigerait une version purement fonctionnelle; ou alors, il faut
garder les donne'es rec,ues dans un coin, ce qu'est cense' faire
"stream_get" (il ne le fait pas, d'ailleurs, dans la version de
distribution, mais ce sera corrige' dans la future version de
Caml-Light, qui parai^tra a` la Saint-Glinglin).

Il y a certes un proble`me d'efficacite', quoique 1) on n'ait pas fait
de mesures 2) a` mon avis, avec les machines rapides qu'on a
actuellement, et l'imple'mentation ge'niale du runtime, ce n'est pas
si grave.

Je crois que le de'bat est ouvert et je trouve bien qu'il le reste. Je
trouve que la programmation fonctionnelle, c'est joli, plus su^r, et
c,a confe`re de "bonnes proprie'te's" aux programmes. La question est
de savoir comment les langages fonctionnels communiquent avec
l'exte'rieur. Et il n'y a pas (encore) de re'ponse de'finitive et
satisfaisante a` cette question.


> let test c s = let (b,_) = stream_get (s) in
> 	if b = c then (stream_next(s);c)
> 	else raise Parse_failure
> ;;

Mmm... Comme je disais ci dessus, si le stream passe' en parame`tre
vient de "stream_from" ou de "stream_of_channel", c,a ne marche pas;
il y a un bug dans Caml-Light 0.5, bug corrige' chez nous, mais pas
dans la distribution.


> si vous voulez parsez un element 
> donne en argument a une fonction, vous ne pouvez pas ecrire :
> 
> let test c = function
> 	[< 'b >] -> if b = c then c else raise Parse_failure
> ;;

Non, mais tu peux e'crire:

            stream_check (prefix = c)

"stream_check" est fait pour c,a. Son avantage est que si la condition
est fausse, la valeur n'est pas consomme'e dans le stream. La fonction
"stream_check" ne peut pas se simuler. C'est une fonction de base.


	Daniel

Stream patterne matching

[cr]

J'ecris, puis Michel repond :

> > Pour quelles raisons le pattern matching sur les streams est-t'il
> > destructif ?  
> >
> > Est-ce simplement une question de performance. Si oui il faut que le gain
> > soit important. En effet, le pattern matching destructif implique un effet
> > de bord implicite. Je trouverais plus propre d'avoir a utiliser soi-meme un
> > pointeur lorsque-l'on veux simuler le pattern matching destructif.
>
> Non, ce n'est pas simplement une question de performance: un autre
> avantage est d'e^tre bien adapte' aux entre'es-sorties destructives de
> ML. Un stream se manipule un peu comme un canal d'entre'e (type
> in_channel): lorsqu'on lit un caracte`re sur un canal (resp. stream),
> une seconde lecture lit le caracte`re suivant.
>
> Avec une semantique destructive du filtrage de streams, un stream
> construit a` partir de std_in aura le me^me comportement qu'un autre
> stream (construit par programme). Avec une se'mantique
> non-destructive du filtrage, cela n'est possible que si ce stream
> garde en me'moire le stream d'entre'e en entier (a` moins de garantir
> qu'il n'existe pas de pointeur vers ce stream).

N'est-ce pas au GC de recuperer l'espace occupe par le debut d'un stream, s'il
n'y a plus de pointeur dessus ?

A t'on deja chiffrer la perte en performance, si l'on n'utilise que des
streams conservateurs ?

--------------------

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. 


Christophe

Re: Stream patterne matching

[Michel Mauny]

For non French speaking members of this ,ailing-list, the point
discussed by Christophe in his message (quoted below) was the
destructive effect of stream matching on streams.  His main
arguments/questions were:

        1. Is there any reason other than efficiency?
        2. This destructive effect makes hard to do some parameterization
           of parsers (cf. "test" example below).
        3. It makes debugging more complex.

Briefly, my answers are:

        1. Yes. It is more consistent with the imperative IO model of
           ML. Streams and input channels behave in the same way.
        2. Not really. Instead of passing constants as arguments, pass
           parsers that recognize only these constants (cf. "bal" example, below).
        3. Yes, I agree.

Pour les francophones, maintenant:

Christophe Raffalli e'crit:

> Pour quelles raisons le pattern matching sur les streams est-t'il destructif ?
> 
> Est-ce simplement une question de performance. Si oui il faut que le gain soit
> important. En effet, le pattern matching destructif implique un effet de bord
> implicite. Je trouverais plus propre d'avoir a utiliser soi-meme un pointeur
> lorsque-l'on veux simuler le pattern matching destructif.

Non, ce n'est pas simplement une question de performance: un autre
avantage est d'e^tre bien adapte' aux entre'es-sorties destructives de
ML. Un stream se manipule un peu comme un canal d'entre'e (type
in_channel): lorsqu'on lit un caracte`re sur un canal (resp. stream),
une seconde lecture lit le caracte`re suivant.

Avec une semantique destructive du filtrage de streams, un stream
construit a` partir de std_in aura le me^me comportement qu'un autre
stream (construit par programme). Avec une se'mantique
non-destructive du filtrage, cela n'est possible que si ce stream
garde en me'moire le stream d'entre'e en entier (a` moins de garantir
qu'il n'existe pas de pointeur vers ce stream).

> De plus le pattern matching destructif augmente la complexite de toutes
> grammaires "parametrables". En effet, si vous voulez parsez un element 
> donne en argument a une fonction, vous ne pouvez pas ecrire :
> 
> let test c = function
> 	[< 'b >] -> if b = c then c else raise Parse_failure
> ;;
> 
> Mais vous devez ecrire :
> 
> let test c s = let (b,_) = stream_get (s) in
> 	if b = c then (stream_next(s);c)
> 	else raise Parse_failure
> ;;

L'ide'e pour re'soudre ce genre de proble`me est de parame'trer une
fonction par une autre fonction reconnaissant cette constante. Un
exemple un peu plus complexe que "test" ci-dessus, et qui me semble
bien illustrer le pb est un parser de suites de parenthe`ses
correctement balance'es, parame'tre' par les parenthe`ses. On retourne
(naivement) la liste des caracte`res reconnus:

let rec bal opar cpar = function
    [< opar p1; (bal opar cpar) l1; cpar p2; (bal opar cpar) l2 >] -> p1::l1@p2::l2
  | [< >] -> []
;;

let oparen = function [< '`(` >] -> `(`
and cparen = function [< '`)` >] -> `)`
and ocurly = function [< '`{` >] -> `{`
and ccurly = function [< '`}` >] -> `}`
;;

bal oparen cparen (stream_of_string "((()()(())))");;
bal ocurly ccurly (stream_of_string "{{}}{}{{}}");;

Je reconnais que la tentation premie`re est de passer les caracte`res
`(` et `)` en argument, et donc de parame'trer la fonction "bal" par
des caracte`res. Passer en argument les analyseurs qui reconnaissent
uniquement chacun de ces caracte`res n'est ni beaucoup plus complexe
ni beaucoup plus inefficace.

Toutefois, pour ce style particulier d'exemple, il existe une fonction
nomme'e
        stream_check : ('a -> bool) -> 'a stream -> 'a

qui permet de programmer "test" par:

let test c = stream_check (fun tok -> tok = c);;

> Ainsi, je trouve qu'un pattern matching non destructif permettrait d'ecrire
> des programmes plus naturels, dont les bugs seraient moin inextricables.  Par
> exemple essayez de programmez un analyseur lexical qui soit efficace et qui
> reconnait un ensemble de tokens stockes dans une table (sous un format
> adequate). Cette table pouvant etre modifiee.

Je suis d'accord sur le fait que les bugs sont en ge'ne'ral difficiles
a` localiser, et que le co^te' destructif n'arrange rien.

> A par ca je trouve que le pattern matching est une tres bonne methode pour
> ecrire des grammaires. On peut ecrire des grammaires dont les regles modifient
> la grammaire elle-meme .....              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  ^^^^^^^^^^^^^^^^^^^^^^
Si je puis me permettre, ca ne doit pas faciliter le debugging non plus :-)

> Christophe Raffalli.
> LFCS Edinburgh
> Logic team of Paris VII


Michel Mauny

Stream patterne matching

[cr]

Pour quelles raisons le pattern matching sur les streams est-t'il destructif ?

Est-ce simplement une question de performance. Si oui il faut que le gain soit
important. En effet, le pattern matching destructif implique un effet de bord
implicite. Je trouverais plus propre d'avoir a utiliser soi-meme un pointeur
lorsque-l'on veux simuler le pattern matching destructif.

De plus le pattern matching destructif augmente la complexite de toutes
grammaires "parametrables". En effet, si vous voulez parsez un element 
donne en argument a une fonction, vous ne pouvez pas ecrire :

let test c = function
	[< 'b >] -> if b = c then c else raise Parse_failure
;;

Mais vous devez ecrire :

let test c s = let (b,_) = stream_get (s) in
	if b = c then (stream_next(s);c)
	else raise Parse_failure
;;

Ainsi, je trouve qu'un pattern matching non destructif permettrait d'ecrire
des programmes plus naturels, dont les bugs seraient moin inextricables.  Par
exemple essayez de programmez un analyseur lexical qui soit efficace et qui
reconnait un ensemble de tokens stockes dans une table (sous un format
adequate). Cette table pouvant etre modifiee.


A par ca je trouve que le pattern matching est une tres bonne methode pour
ecrire des grammaires. On peut ecrire des grammaires dont les regles modifient
la grammaire elle-meme .....


Christophe Raffalli.
LFCS Edinburgh
Logic team of Paris VII