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