Re: [Caml-list] Pattern matching

[Luc Maranget <luc.maranget@inria.fr>]

Ne nous énervons pas.
Comme c'est long je résume.

Le problème soulevé est celui du sens des variables dans les motifs.
La réponse est que ces variables sont liantes.
Changer cela pose plus de problèmes que vous ne semblez le penser.

Let us sum it up.
The real issue is about the semantics of variables in patterns.
These variables are ordinary binding occurrences. We'd better not
change that.


> Mon « argumentation » consiste à exhiber de mauvais programmes car je
> considère qu'un « bon » langage ne doit pas laisser un mauvais
> programmeur faire du mauvais code (dans la mesure du possible). Quand
> je dois passer trois heures à relire le code d'une tierce personne et
> que je me rends compte que l'erreur est dûe à la fonction suivante :

Pouquoi pas mais le problème est également dans ce cas un problème
d'apprentissage du langage et je considère que cet apprentissage est
facilité par des principes simples. L'erreur classique est ici de
surestimer le filtrage (pattern matching).


> 
> let f = function n ->
>    let g = function
>      | (n, i ) -> ...
>       ^^
> car le programmeur a cru que n était déjà liée (l'exemple est un peu
> exagéré mais bon...), j'ai tendance à taper (sans doute à tort) non
> sur le programmeur mais sur le concepteur du langage.
n est déjà liée, n est cachée par la nouvelle occurence liante
(aka déclaration en C par ex).
Ça c'est simple, ça se comprend, certes ça peu mener à des erreurs
mais bon, avant de bondir « Comment ça le compilo ne fait pas ce que
je veux », essayons de comprendre pourquoi il ne le fait pas.

> Je vais vous dire des choses que vous n'ignorez pas au sujet du
> pattern-matching, mais au moins serons nous clairs.
> 
> Il y a deux usages du pattern-matching :
> 
> le filtrage structurel (qui exige unification avec le motif et liaison
> des variables)
>   let somme = function
>     | [] -> 0
>     | [x] -> x
>     | [x ; y] -> x + y
>     | _ -> 0
>   ;;
> 
> le filtrage de valeurs qui correspond à un « if then else » en plus
> compact (et sans introduction de nouvelles variables)
>   let delta = function
>     | (0, 0, 1) -> 1
>     | _ -> 0
>   ;;
> 
C'est très intéressant, car le pattern matching n'a qu'une seule
définition.
Une présentation pédagogique inverserait, je crois, l'ordre de
présentation des deux usages.

Bon moi je dirait ça.

Il y les listes et les paires (pour ne pas parler des arbres).

Un motif est une description d'ensembles de paires, de listes, de
paires de listes etc.

Par exemple,
(1,2) représente la paire formée de 1 et de 2.
(1,_) représente toutes les paires dont la première composante est 1

[_; _] représente toutes les listes à deux elts etc.

(Au passage ``_'' représente n'importe quoi).

Le filtrage et bien ça marche en essayant les motifs les uns après les
autres (dans l'ordre) , par exemple comme ça

match x with
| (1,2) -> (* ici je sais que x est la paire (1,2) *)
| (1,_) -> (* ici je sais que x est la paire (1, autchose), où
              autchose n'est pas 2 *)
| _     -> (* ici x est tout le reste *)

Ce qui est merveillleux dans le filtrage c'est que je peux remplacer
les ``_'' par des variables. Alors oh joie (soyons positifs)
j'ai une variable qui vaut ``autchose'' dans le cas 2 ci dessus

par ex 

match x with
| (1,2) -> (* ici je sais que x est la paire (1,2) *)
| (1,snd) -> je sais que snd n'est pas 2
| (fst, snd) -> ...

Voilà c'est tout.
(on peut ici comparer une copie de liste en lisp et en ML si on veut)

(if (consp l) (cons (car l) (copy (cdr l))) ())

let rec copy l = match l with
| x::rem -> x::copy rem
| []     -> []



Théorisons un peut (terrorisons ?).
Bon, chouette mais comment définir ces fameux ensembles de valeurs
représentées par des motifs.

Bon, toujours avec les paires et les listes.
Je vais definir une relation dite de filtrage (notée <=) comme ça :

_ <= V (``_'' filtre toutes les valeurs *)

[] <= []  (* le motif [] filtre la liste vide)
n  <= n   (* le motif ``n'' (un entier) filtre la valeur entière n *)

(* Tout ça passe aux arguments *)

(p1, p2) <= (V1, V2) ssi p1 <= V1 et p2 <= V2
p1 :: p2 <= V1 :: V2


En plus je peux, partout ou on met ``_'' aussi mettre des variables.
Alors ces variables sont liées aux sous composants correspondants.

On peut (pourvu que la même variable ne se répète pas) calculer ces
liaisons comme ça :

Liasons (x, V) = [x, V]
Liasons ( (p1, p2), (V1, V2)) = Liaisons (p1, V1) |_| Liaisons (p2, V2)
                                                  ^^^^
                                                  Union.

Etc...

Bon évidemment, si la même variable est présente (par ex
dans p1 et p2 ci-dessus), ya un blème.
On peut le résoudre soit
  1. En rendant cette situation illégale.
  2. En obligeant les deux valeurs liées à être égales.

En Caml c'est ``1.'' qui est choisi.
Paske
    Le sens d'être égal n'est pas clair (égal structurel, qui peut
    boucler) ou egal physique (qui peut echouer).




> Ce dont je me « plains » est que la syntaxe actuelle de OCaml ne
> différencie pas clairement les deux et permet des mélanges qui peuvent
> donner lieu à du code douteux, à des erreurs difficiles à détecter...
Ben non, pour moi il y a un seul filtrage, pas deux.
Pour les erreurs, vous avez raison, mais elle proviennent plutôt d'une
méconnaissance de ce qu'est réellement le filtrage.
La solution ``protectrice'' serait tout simplement d'interdire de
cacher une variable en introduisant une variable homonyme dans un
motif.

Votre position (estimable) est je crois de changer le sens du filtrage
pour y ajouter plus d'expressivité  (de fait des égalités en plus).

Il y a deux niveaux
  1. Égalité entre deux variables du même motif.
  2. Égalité entre une variable d'un motif et une autre liée au
     préalable.

Je pense que votre combat est perdu d'avance, car c'est en fait
compliqué et l'utilisateur peut expliciter facilement ces égalités
quand il en a besoin. 

Je ne peux pas m'empêcher d'attirer votre attention sur ce que, si ces
changements (bon le no 2, le no 1 ne pose pas ce pb) rendent correct
(ie, conforme à ce que vous croyiez qu'il signifiait) le programme de
votre ami ; il rendront incorrects d'autres programmes écrits par les
(nombreux) utilisateurs qui ont la même vue du filtrage et de la
liaison statique que moi.

--Luc
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr