Re: Stream patterne matching

[Michel.Mauny@inria.fr (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