[Caml-list] Pattern matching

[Caml-list] Pattern matching

[Diego Olivier Fernandez Pons]

An english translation follows

Pourrait quelqu'un expliquer les raisons pour lesquelles dans un
pattern matching toutes les variables introduites sont considérées
comme de nouvelles variables ? Est-ce pour des questions de choix
entre égalité physique et égalité structurelle ?

En effet, le code suivant :

(* couples 4 = (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) *)
let couples = function n ->
  let rec couplesCPS = function
    | (n,_) -> [ ]
    | (i,n) -> (i,n) :: couplesCPS (i+1, i+2)
    | (i,j) -> (i,j) :: couplesCPS (i, j+1)
  in    couplesCPS (1,2)
;;

me semble nettement plus lisible que le code qu'il faut écrire en Caml
actuellement :

(* couples 4 = (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) *)
let couples = function n ->
  let rec couplesCPS = function
    | (i,_) when (i = n) -> [ ]
    | (i,j) when (j = n) -> (i,j) :: couplesCPS (i+1, i+2)
    | (i,j) -> (i,j) :: couplesCPS (i, j+1)
  in    couplesCPS (1,2)
;;

Bien sûr, si l'on passait des listes on aurait le choix entre les deux
types d'égalité, mais on pourrait toujours définir une syntaxe
alternative pour le cas de l'égalité physique par exemple (laisser le
when pour ce cas là et autres types de comparaisons...)

Pourquoi demande-t-on à un motif d'être « linéaire » ? (c'est à dire
si je comprends bien la documentation qu'une variable ne peut
apparaître qu'une fois dans un motif). Il est bien évident que
certains motifs ne doivent pas être permis

let egalite = function
   | (x,x) -> true
   | (x,y) -> false
;;
# This variable is bound several times in this matching

mais x est ici une nouvelle variable ce qui n'était pas le cas de n
dans la fonction couple.

    Diego Olivier

< Your function will always return 1, because variables on the
< left-hand side of a pattern-match are bound like in a let
< expression.

Could someone explain why are variables on the left-side of a
pattern-match bound like in a let expression ? Is it a problem of
structural versus physical equality ? In which case, why not choosing
structural by default and leaving physical for the « when » syntax ?

« Patterns are linear: a variable cannot appear several times in a
given pattern. In particular, there is no way to test for equality
between two parts of a data structure using only a pattern (but when
guards can be used for this purpose). » (manual 6.6)
Could someone explain why must patterns be linear ?


-------------------
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

Re: [Caml-list] Pattern matching

[Pixel]

"Diego Olivier Fernandez Pons" <FernandezPons@iFrance.com> writes:

[...]

> let couples = function n ->
>   let rec couplesCPS = function
>     | (n,_) -> [ ]

vs

> let couples = function n ->
>   let rec couplesCPS = function
>     | (i,_) when (i = n) -> [ ]

the problem is an expressivity one. Something like 

(function A(e) -> e | _ -> ...) 

become dependent on the context: is there a variable "e" in the surrounding
context. This is not good.

One could add some sugar allowing:

> let couples = function n ->
>   let rec couplesCPS = function
>     | (@@n,_) -> [ ]

where @@n force the scope of n to be non-local. But too much sugar makes the
language harder to learn :)

[...]

> let egalite = function
>    | (x,x) -> true
>    | (x,y) -> false
> ;;
> # This variable is bound several times in this matching

i wonder why this one is not allowed since it can't have any other meaning
than the one it has in prolog. What's the reason for not having it rewritten
to:

> let egalite = function
>    | (x,x') when x=x' -> true
>    | (x,y) -> false

maybe you're right than the kind of equality (= vs ==) may be the problem...
-------------------
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

Re: [Caml-list] Pattern matching

[Luc Maranget]

About pattern matching.
> 
> "Diego Olivier Fernandez Pons" <FernandezPons@iFrance.com> writes:
is right to stress on the fact that variables in patterns are
binding variables, some variable is bound to something.
when you write

let x = ex in
let x = ex' in

You certainly do not mean that ex and ex' are equal (whatever it
means).



On linearity :

> 
> > let egalite = function
> >    | (x,x) -> true
> >    | (x,y) -> false
> > ;;
> > # This variable is bound several times in this matching
> 
> i wonder why this one is not allowed since it can't have any other meaning
> than the one it has in prolog. What's the reason for not having it rewritten
> to:
> 

Does not mean :

> > let egalite = function
> >    | (x,x') when x=x' -> true
> >    | (x,y) -> false
> 

Well, it could be that way. But it is not.

This can be argueed as follows.

  As already said the meaning of (x,x) is not clear, should we use
  ``='' (and then pattern matching may last for ever, or may raise
  an exception (for functions)) or ``=='' (and this is not very useful).

  Futhermore the theory of non-left-linear rewriting is more
  complicated than the one of left-linear rewriting and this theory
  somehow applies to ML pattern matching.


So my opinion is that non-linear pattern brings little benefits to
users, complicates much the life of the compiler writer and may even
introduce subtle bugs in users programs.


--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

Re: [Caml-list] Pattern matching

[Diego Olivier Fernandez Pons]

An english abstract follows

Fabrice Le Fessant a écrit :

>  (* couples 4 = (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) *)
>  let couples = function n ->
>    let rec couplesCPS = function
>      | (n,_) -> [ ]
>      | (i,n) -> (i,n) :: couplesCPS (i+1, i+2)
>      | (i,j) -> (i,j) :: couplesCPS (i, j+1)
>    in    couplesCPS (1,2)
>  ;;
[...]

let succ n = n + 1;;

Le langage introduit nombre de quantificateurs existentiels ou
universels, ne serait-ce que dans la définition même des fonctions :
je lis la définition de la fonction successeur : « soit successeur la
fonction qui a tout n de N associe (n + 1) ». Cela n'a jamais posé la
moindre difficulté aux programmeurs qui, dans la fonction couple - à
votre image - comprennent tous que n est déjà liée tandis que i et j
ne le sont pas.

D'accord, j'utilise quand je peux la syntaxe :
let succ = function n -> n + 1;;
(mais le compilateur en n'admettant pas let f = function x y -> vous
force parfois à utiliser cette horreur de syntaxe)

J'emprunte l'exemple (terrifiant !) suivant à David Alexander Madore,
lequel d'ailleurs dans son message original servait à illustrer autre
chose mais peu importe

let x = 42;;
let lot f x =
  print_string "Madame Irma va maintenant répondre à la grande
question :\n";
  print_string "Le CAML a-t-il une syntaxe aberrante ?";
  print_string "(Has CAML a weird syntax ?)";
  x+1;;
let f x = x+1;;
lot f x = x+1;;

# val x : int = 42
# val lot : 'a -> int -> int = <fun>
# val f : int -> int = <fun>
# Madame Irma va maintenant répondre à la grande question :
# Le CAML a-t-il une syntaxe aberrante ?
# (Has CAML a weird syntax ?)  - : bool = true

Revenons au sujet : le problème est que la définition du
pattern-matching est déjà en soi étrange
let delta = function
  | 0 -> 1
  | _ -> 0
;;
D'accord car on a disjoint l'ensemble de définition

let delta = function
  | i when (i = 0) -> 1
  | i -> 0
;;
à mettre en parallèle avec :
let delta = function
  | i when (i = 0) -> 1
  | j -> 0
;;
Etrange car on a attrappé deux fois de suite une variable qui prend
des valeurs sur tout l'ensemble de définition et on ne comprend pas
très bien pourquoi cette variable est muette. Si l'on accepte cela
(qui est conséquence de l'absence de liaison explicite de i une seule
fois pour toutes), pourquoi n'accepterait-on pas qu'une variable dans
le motif soit déjà liée : ce serait tout aussi pratique.

Ou alors adopter pour unique syntaxe quelque chose comme
let couple = function n ->
   let rec coupleCPS = function (i,j) ->
     match (i,j) with
       | (n,_) -> [ ]
       | (_,n) -> (i, j) :: coupleCPS (i+1, i+2)
       | (_,_) -> (i, j) :: coupleCPS (i, j+1)
     in
   coupleCPS (1,2)
;;

On peut utiliser i, j et n dans les motifs et dans le reste du code
car les trois variables ont été liés correctement au préalable

< alors le simple fait de definir 'i' avant la fonction
< change le sens de la fonction par rapport a quand
< 'i' n'etait pas defini ?

Voyez un peu le code de Madore ! L'égalité change de sens dans chacune
des propositions
    let f x = x+1;;
    lot f x = x+1;;

        Diego Olivier

Fabrice said « (It is my translation) How could the compiler know than
"i" is a free variable while "n" is not ? And even if he could notice
the difference, defining "i" would then change the meaning of the
function »
The problem is that in the pattern matching, variables i and j seem to
be bounded several times (see the delta example).The "let" declaration
is omitted (which is very usefull anyway). A strange program by David
Madore is provided as well as an alternate syntax for the pattern
matching.






-------------------
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

Re: [Caml-list] Pattern matching

[Luc Maranget]

> 

> Fabrice Le Fessant a écrit :
> 
> >  (* couples 4 = (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) *)
> >  let couples = function n ->
> >    let rec couplesCPS = function
> >      | (n,_) -> [ ]
> >      | (i,n) -> (i,n) :: couplesCPS (i+1, i+2)
> >      | (i,j) -> (i,j) :: couplesCPS (i, j+1)
> >    in    couplesCPS (1,2)
> >  ;;
> [...]
> 
> let succ n = n + 1;;
> 
> Le langage introduit nombre de quantificateurs existentiels ou
> universels, ne serait-ce que dans la définition même des fonctions :
> je lis la définition de la fonction successeur : « soit successeur la
> fonction qui a tout n de N associe (n + 1) ». Cela n'a jamais posé la
> moindre difficulté aux programmeurs qui, dans la fonction couple - à
> votre image - comprennent tous que n est déjà liée tandis que i et j
> ne le sont pas.
> 
> D'accord, j'utilise quand je peux la syntaxe :
> let succ = function n -> n + 1;;
> (mais le compilateur en n'admettant pas let f = function x y -> vous
> force parfois à utiliser cette horreur de syntaxe)
Je ne comprends pas trop tous ces arguments.
Il n'en reste pas moins que
  1. Les fonctions sont des citoyens de première classe en Caml
    et qu'il n'est pas toujours nécessessaire de leur donner un nom.
    Dans ce cadre la notation (fun x -> ...) est logique.

    Mais, comme vous semblez le dire vous même, ``let f = fun x -> ...''.
    c'est lourd.
      Il y a donc une notation ``let f x = ... ''


Je coupe un example de syntaxe bizarre, sur la base de ce qu'on peut
écrire de mauvais programmes dans tous les langages.
Je trouve plus intéressant de chercher à définir un style de bonne
programmation.



> let delta = function
>   | 0 -> 1
>   | _ -> 0
> ;;
> D'accord car on a disjoint l'ensemble de définition
> 
> let delta = function
>   | i when (i = 0) -> 1
>   | i -> 0
> ;;
> à mettre en parallèle avec :
> let delta = function
>   | i when (i = 0) -> 1
>   | j -> 0
> ;;
> Etrange car on a attrappé deux fois de suite une variable qui prend
> des valeurs sur tout l'ensemble de définition et on ne comprend pas
> très bien pourquoi cette variable est muette.
Je pense qu'elle est muette parce que c'est comme ça. Et je l'admet en
toute modestie (j'exagère bien entendu).
> Si l'on accepte cela
> (qui est conséquence de l'absence de liaison explicite de i une seule
> fois pour toutes), pourquoi n'accepterait-on pas qu'une variable dans
> le motif soit déjà liée : ce serait tout aussi pratique.
> 
Ben moi ça ne me choque pas.
if blabla then let i = ... else let i = ... 
ne me pose que peu de problème, parceque les deux i ne coexistent pas.

let i = .. in
if blabla then
  let i = ...
else
  ...
me fait dresser le sourcil, sans me choquer outre mesure.
Tout ça dépend probablement de l'intention du programmeur.





Au fond Je ne comprends pas l'argument et je dis que, sur cet exemple
l'emploi du filtrage est mal venu.
Si j'étais prof (et je le suis) il faut écrire

let delta i = if i=0 then 1 else 0
Qui me semble la bonne facon de procéder.
(ou alors match i with 0 -> 1 | _ -> 0, tout aussi bien)

Je decouvre souvent des matchs sans justification dans des copies
d'élèves et je me demande à chaque fois pourquoi ne pas utiliser des
constructions simples (ici le if ou le match sans when) partout où
elles s'appliquent.

Maitenant personne ne veut supprimer le when, nous sommes sans doute
d'accord. Mais on les verra ailleurs.



> Ou alors adopter pour unique syntaxe quelque chose comme
> let couple = function n ->
>    let rec coupleCPS = function (i,j) ->
>      match (i,j) with
>        | (n,_) -> [ ]
>        | (_,n) -> (i, j) :: coupleCPS (i+1, i+2)
>        | (_,_) -> (i, j) :: coupleCPS (i, j+1)
>      in
>    coupleCPS (1,2)
> ;;
Sans rire c'est exactement ce que je recommanderais, non pas au
concepteurs du compilo, mais aux programmeurs, surtout débutants
(et d'ailleurs j'ecris généralement dans ce style).
Ne pas utliser le filtrage dans les définitions de fonction, toujours
utiliser des match explicites.

A part ça, le fait de rigidifier la syntaxe ne change rien à l'affaire
de mon point de vue. Les variables des filtres sont liantes comme les
autres, c'est une
règle simple et compréhensible, que je refuse de laisser tomber pour
une amelioration d'expressivité (une égalité cachée) dont je persite à
croire qu'elle a fort peu d'intérêt.


> 
> On peut utiliser i, j et n dans les motifs et dans le reste du code
> car les trois variables ont été liés correctement au préalable
Correctement hum ? Les variables sont liés par les motifs, c'est
simple et direct.

De toute façon, ça ne correspond pas au langage actuel Aet de loin,
car dans Caml actuel, toutes les constructions liantes (ou presque)
sont exprimées par des motifs, dont les variables sont tout simplement
liantes.

l'écriture  ``fun (x,y) -> ... ''' revèle que la règle est
 expression = ... | fun pat -> expression | ...

(pat pouvant être une variable d'ailleurs) les variables de pat sont
liantes comme partout. Le tout est de le savoir.

Je crois comprendre l'idée de privilègier en quelque sorte les
variables liées dans un ``fun''.
Mais bon, pourquoi alors les deuxièmes liaisons de x dans
(fun x -> (fun x -> ...) )
et dans
(fun x -> match y with x -> 
auraient-elles une signification différente ?

Sincèrement, ça ne tient pas la route. Ça va trop contre un principe
général et bien établi à l'heure actuelle.
C'est dur à expliquer et sans grande portée pratique.



Ce qui pourrait être admis (pour progresser à petits pas sur
l'existant) serait, dans certains circonstances
l'interdiction (ou le déconseil par un avertissement) de
l'introduction de variables homonymes.
Genre
(fun x -> match y with x -> ...)
                       ^^
                        |
Warning: pas bo, dangereux.

Mais bof c'est certainement moins simple à bien spécifier que ça en a
l'air.



> 
> < alors le simple fait de definir 'i' avant la fonction
> < change le sens de la fonction par rapport a quand
> < 'i' n'etait pas defini ?
> 
> Voyez un peu le code de Madore ! L'égalité change de sens dans chacune
> des propositions
>     let f x = x+1;;
>     lot f x = x+1;;
Madore a fait une erreur, la syntaxe ne l'aide pas, mais bon.
Elle est du même ordre que = / == en C.


En conclusion j'insisterait sur la nécessité pour chacun de se définir
un style propre (dans les deux sens) d'écriture qui limite ce type de
danger. Bizarrement (cf. l'exemple du if) cela revient souvent à
choisir la  construction de programmation adaptée à ce que l'on
shouhaite exprimer et, parfois,  à s'abstenir de traits avancés.
(Soit si ya pas de motif pourquoi utiliser un match).
Rapelons au passage que filtrer c'est d'abord destructurer.


D'autre part, lorsque l'on a effectivement besoin de ces traits
avancés, il vaut mieux, je crois, se contraindre à les exprimer
toujours de la même façon simple.

Ensuite et j'enfonce le clou. Chaque fois que j'utilise des variables
de même nom (y compris dans des liasons qui ne semble pas poser de pb,
comme les let) j'arrête la programmation en mode automatique et je me
pose la question de pourquoi je fais ça, c'est à chaque fois une
situation qui demande de toute façon d'y regarder à deux fois, (en
particulier parceque la résistances aux modifications ultérieures
chute) et la réponse est rarement qu'il y a égalité implicite entre
variables homonymes.


--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

Re: [Caml-list] Pattern matching

[Diego Olivier Fernandez Pons]

An english abstract follows

< Je coupe un example de syntaxe bizarre, sur la base de ce qu'on peut
< écrire de mauvais programmes dans tous les langages.
< Je trouve plus intéressant de chercher à définir un style de bonne
< programmation.

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 :

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.

< Sans rire c'est exactement ce que je recommanderais, non pas au
< concepteurs du compilo, mais aux programmeurs, surtout débutants
< (et d'ailleurs j'ecris généralement dans ce style).
Mais ??? ce code ne marche pas ! (n n'est pas lié)

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
  ;;

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...

let somme = function n ->
   let rec sommeCPS = function
      | (total, k) when (k = 0) -> total
      | (k, total) -> sommeCPS (total + k, k - 1)
         ^  ^^^
  in
       sommeCPS (0, n)
;;

Ici on est en train de filtrer des valeurs, donc d'après moi il ne
devrait y avoir qu'une seule liaison des variables total et k (et
j'estime que la syntaxe doit forcer à ce que ce soit le cas). Il
suffit d'une fonction interne un tant soit peu plus grande pour
que cette erreur soit difficile à voir.

Une rigidification de la syntaxe qui permet d'éviter des erreurs
(communes comme le prouve le nombre des messages de débutants sur ce
sujet, la mise en garde dans le manuel...) est d'après moi
parfaitement justifiée. Et puisqu'il y a deux syntaxes équivalentes
(une avec match with explicite, l'autre sans), je proposais que :
 - la syntaxe « match with » soit réservée au filtrage de valeurs
 - l'on puisse utiliser des variables précédemment liées dans le
filtrage de valeurs (puisqu'il n'introduit pas de nouvelles variables)
 - laisser le filtrage de structure tel qu'il est (et donc
l'unification avec le motif, autrement dit les variables liantes)

Je conçois cependant que l'on puisse ne pas être d'accord à ce sujet.

        Diego Olivier

There are two kind of pattern matching :

i) structure matching
  let add = function
    | [] -> 0
    | [x] -> x
    | [x ; y] -> x + y
    | _ -> 0
  ;;

ii) value matching
  let delta = function
    | (0, 0, 1) -> 1
    | _ -> 0
  ;;

mixing both allows mistakes that could be sometimes very hard to find
let add = function n ->
   let rec addCPS = function
      | (total, k) when (k = 0) -> total
      | (k, total) -> addCPS (total + k, k - 1)
         ^  ^^^
  in
       addCPS (0, n)
;;

I was just proposing :
- to use the « match with » syntax for value matching only
- to allow the use of bounded variables in the value matching
- to leave the structure match as it is of course





-------------------
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

Re: [Caml-list] Pattern matching

[Fabrice Le Fessant]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=us-ascii, Size: 2080 bytes --]



> 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 :

C'est aussi faux que de dire qu'une bonne loi previent tout
delit. Qu'est ce qui empechera un mauvais programmeur de croire que
ton "match" sans liaison est en fait avec liaison ? Si je pousse a
l'extreme, je mets un singe devant mon clavier, et j'envoie des
rapports de bugs pour chaque phrase tappee que le compilateur
n'accepte pas ?

> I was just proposing :
> - to use the « match with » syntax for value matching only
> - to allow the use of bounded variables in the value matching
> - to leave the structure match as it is of course

Pourquoi changer ce dont tout le monde a part toi est heureux ? Tu
fais du pattern-matching hyper-simple (deux a trois cas sans liaison)
qui serait probablement cent fois mieux traite par un "if", et tu
rales. Ce n'est pas le programmeur qui s'est plante, c'est celui qui
lui a appris qu'il fallait utilise un "match" la ou il aurait du
utiliser un "if".

Essaie donc de faire du pattern-matching avec 30 cas (un arbre de
syntaxe par exemple), et tu te rendras compte que le pattern-matching
avec liaison est mille fois plus utile ! Je te vois mal ecrire
l'equivalent du compilateur de ocaml avec ce pattern-matching que tu
proposes... 

Exercice 1 d'une modification de syntaxe: prendre un code existant et
le traduire dans ta syntaxe. Je te propose de jeter un oeil a
typing/typecore.ml ...

I was just proposing:
- to use << match with >> on complex structures.
- to use << if >> on simple structures where no binding is required.
- to learn the semantics of a construct before using it.

- Fabrice

-------------------
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

[Caml-list] If ou Pattern-matching ?

[Diego Olivier Fernandez Pons]

Je reconnais être un peu borné, j'applique en effet sans réfléchir
certaines recommandations de Pierre Weis (Conseils de programmation
Caml) : « On n'aura jamais peur d'abuser du filtrage ! » mais aussi
« Programmer simple et clair avant tout »

La question (soulevée d'ailleurs par Rémi Vanicat) est celle de
l'équivalence des codes suivants :

  let somme = function
    | 0 -> 0
    | k -> k + somme (k-1)
  ;;

et

  let somme = function n ->
    if n = 0 then 0
    else (k + somme (k-1))
 ;;

Employons donc la méthode proposée par Le Fessant : éxagérons !

let conditions = function
  | (0, 1, 1, 1, _) -> 1
  | (1, 0, 0, _, m) -> m
  | (1, 1, 0, L, 0) -> 1
  | (i, j, 0, L, m) when (i = j) && (L = m) ->  0
  | _ -> 1
;;
(Je n'ai pas écrit 30 cas mais l'idée y était)

Exercice 1 : réécrire ce code avec des « if then else »
Exercice 2 : répondre à la question « lequel des deux codes est le
plus lisible ? »

Fabrice Le Fessant à écrit :
< Tu fais du pattern-matching hyper-simple (deux a trois cas sans
< liaison) qui serait probablement cent fois mieux traite par un "if",
[...]
< Ce n'est pas le programmeur qui s'est planté, c'est celui qui
< lui a appris qu'il fallait utiliser un "match" là où il aurait dû
< utiliser un "if".
[...]
< Essaie donc de faire du pattern-matching avec 30 cas

Le filtrage est-il une alternative acceptable aux enchaînements de «
if then else » ? A mon avis oui car il est nettement plus lisible,
présente les informations de manière compacte et immédiatement
compréhensible. Cela minimise les risques d'erreur, réduit la longueur
des programmes, en facilite la maintenance, etc.

Encore un extrait des excellents conseils de Weis
< Au-delà d'une page, on se perd dans le code, l'indentation est peu
< lisible et difficile à maintenir correcte.
Le code avec filtrage que je présente assure :
 - une indentation uniforme (ce qui ne serait pas le cas avec des if)
 - une compacité qui ne nuit aucunement à la compréhension
Il est vrai qu'il est plus lent (on peut regrouper des cas avec if)

Les questions suivantes sont « dans quelle mesure il faut-il calquer
les fonctionnalités du filtrage sur celles de "if" ? » « Comment
concilier les éventuelles incompatibilités introduites ? » « Est-ce
bien raisonnable ? »

  i) il est évident qu'on ne pourrait pas se passer du filtrage avec
liaison, comment écrire sinon
    let longueur = function ->
       | [ ] -> 0
       | (_ :: reste) -> 1 + longueur (reste)
   Cette question est donc réglée, il n'est pas question d'éliminer le
filtrage avec liaison

  ii) quelles différences entre un filtrage et un « if then else » ?
      - le « if then else » permet la comparaison avec des valeurs
précédemment liées
      - le filtrage masque les valeurs précédemment liées

  Proposition :
      - introduire une seconde version de filtrage sans liaisons qui
serait identifiable par une syntaxe particulière (j'ai proposé match
mais ce peut-être autre chose si cela casse du code) et permettrait la
comparaison avec des valeurs précédemment liées.

  Critiques :
      - c'est compliqué à expliquer aux programmeurs (Maranget)
      - cela rompt l'unité conceptuelle du filtrage (Maranget)
      - c'est compliqué à introduire dans le compilateur (Maranget)
      - égalité structurelle ou égalité physique ? (Fernandez Pons)
      - tout le monde est heureux dans la vie sauf toi (Le Fessant)
      - tu serais incapable d'écrire un compilateur Caml (Le Fessant)
      - apprends la sémantique des constructions Caml avant de les
utiliser (Le Fessant)

  Réponse :
      - cela permet d'éviter certaines constructions douteuses
      - le filtrage actuel fait déjà des égalités avec les constantes
      - les nombreux messages des débutants sur cette liste, les
multiples avertissements dans le manuel montrent que la version
actuelle du filtrage n'est pas si intuitive non plus

  Critiques :
      - on peut toujours obtenir du code robuste en évitant les
constructions douteuses (Maranget)
      - on peut modifier le compilateur pour qu'il affiche un warning
idoine (Maranget)

   Réponse :
      - le langage devrait aider le programmeur à coder facilement des
programmes robustes et lisibles
      - on peut adopter une position flexible (ne pas obliger le
programmeur à utiliser cette nouvelle syntaxe)

Annexe : j'ai fait d'autres propositions (liaison dans le filtrage
avec les variables n'apparaissant pas précédemment) mais elles
introduiraient plus de difficultés qu'elles ne résolvent de problèmes.

Commentaire : si la locution « pattern-matching » vous hérisse, je
peux dire plutôt que je propose l'introduction d'un « multi-switch »
qui serait bien utile.

  iii) Est-ce bien utile de faire tout ce tapage, des modifications à
la sémantique du langage, etc. pour une « amélioration » aussi
insignifiante et qui a plus de conséquences que je ne semble croire ?

A cette question je ne puis répondre, c'est pour cela que je vous
écris. Comme le signale à propos Le Fessant, je me suis jamais
distingué par une connaissance approfondie du code source du
compilateur Caml, ni par ma virtuosité au maniement de la sémantique
du langage.

        Diego Olivier




-------------------
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

Re: [Caml-list] If ou Pattern-matching ?

[Fabrice Le Fessant]

L'ajout d'une nouvelle construction en complement du "match" ne me
semble pas indispensable, il peut suffir de rajouter un peu de sucre
syntaxique pour eviter l'ecriture du "when". On peut ainsi preceder
les identificateurs non liants d'un "=" dans le match, en utilisant
camlp4 pour cela.

Le filtrage propose par Caml n'est evidemment pas le seul possible. Il
existe un bon livre de Christian Queinnec sur ce sujet (disponible
gratuitement, voir "Le Filtrage" sur
http://youpou.lip6.fr/queinnec/WWW/Pedagogy.html). La question est de
savoir lequel est le plus adapte a la majorite des programmes, et doit
donc posseder la syntaxe la plus simple...

 - Fabrice
-------------------
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

Re: [Caml-list] If ou Pattern-matching ?

[Nicolas Barnier]

On Wednesday 14 November 2001 00:57, Diego Olivier Fernandez Pons wrote:
>
> Je reconnais être un peu borné, j'applique en effet sans réfléchir
> certaines recommandations de Pierre Weis (Conseils de programmation
> Caml) : « On n'aura jamais peur d'abuser du filtrage ! » mais aussi
> « Programmer simple et clair avant tout »

Si si, ces deux conseils doivent s'appliquer en réfléchissant.

>   let somme = function n ->
>     if n = 0 then 0
>     else (k + somme (k-1))

Pourquoi des "function" quand la fonction n'est pas définie par extension ?

> Le code avec filtrage que je présente assure :
>  - une indentation uniforme (ce qui ne serait pas le cas avec des if)

Mais si, on peut indenter de manière uniforme et structurée (si on regroupe 
des cas, chose que l'on fait également avec des pattern matching imbriqués) 
avec des if :

if then
else if then
else if then
else

Tout est indenté au même niveau.

>     let longueur = function ->
>
>        | [ ] -> 0
>        | (_ :: reste) -> 1 + longueur (reste)
>
>    Cette question est donc réglée, il n'est pas question d'éliminer le
> filtrage avec liaison
>
>   ii) quelles différences entre un filtrage et un « if then else » ?
>       - le « if then else » permet la comparaison avec des valeurs
> précédemment liées
>       - le filtrage masque les valeurs précédemment liées

Il n'y a pas de différences sémantique, c'est de la syntaxe. D'ailleurs le 
code suivant est très proche du précédent (mais il faut un rec et en général 
on évite de mettre des parenthèses autour des arguments sinon les étudiants 
ont du mal à comprendre le concept d'application) :

let rec longueur l =
  if l = [] then 0
  else let _ :: reste = l in 1 + longueur reste

Sauf que c'est insupportable parce que ça génère un warning. De toute façon, 
dès qu'on doit effectuer un traitement uniforme sur une structure de données 
de type somme, on recopie la définition du type et on remplace les "of" par 
des flèches. Les listes ne font pas exception. Pour un type produit au 
contraire, le choix entre les deux constructions est moins immédiat - et 
parfois uniquement une affaire de goût, mais, vous me rétorqueriez sans 
doute "Chacun son mauvais goût".

>   Proposition :
>       - introduire une seconde version de filtrage sans liaisons qui
> serait identifiable par une syntaxe particulière (j'ai proposé match
> mais ce peut-être autre chose si cela casse du code)

Ce souci de compatibilité vous honore.

> et permettrait la comparaison avec des valeurs précédemment liées.
>
>   Critiques :
>       - tout le monde est heureux dans la vie sauf toi (Le Fessant)
>       - apprends la sémantique des constructions Caml avant de les
> utiliser (Le Fessant)

Je dois dire que je soutiens les commentaires de Fabrice Le Fessant.

>       - le langage devrait aider le programmeur à coder facilement des
> programmes robustes et lisibles

A quel langage pensez-vous ? Personnellement, je n'en ai jamais rencontré qui 
permette autant que Caml d'éviter les constructions foireuses : les règles 
sont simples et claires, et on peut se contenter d'un sous-ensemble très 
cohérent du langage pour l'enseignement (e.g. obliger à mettre les "fun" ou 
interdire les "then" sans "else" même quand on n'effectue qu'un effet de 
bord).

> peux dire plutôt que je propose l'introduction d'un « multi-switch »
> qui serait bien utile.

Ben nan parce qu'on a déjà le pattern matching.

>   iii) Est-ce bien utile de faire tout ce tapage, des modifications à
> la sémantique du langage, etc. pour une « amélioration » aussi
> insignifiante et qui a plus de conséquences que je ne semble croire ?
>
> A cette question je ne puis répondre, c'est pour cela que je vous
> écris.

Mais vous refusez d'entendre raison malgré les efforts multiples de l'équipe 
de développement qui a sûrement des choses importantes à faire ! Et vous 
faites des commentaires erronés et désobligeants :

> [...] sous peine de produire un langage qui - comme Caml actuellement - ne 
> dépassera jamais le cadre des universitaires.

On soupçonne donc un tempérament peu enclin à se laisser convaincre même par 
les arguments les plus rationnels et plutôt disposer à en découdre à tout 
prix - uniquement sur le sujet du pattern matching bien entendu. Bref votre 
opinion est ferme et définitive et vous n'écrivez pas pour qu'on éclaire 
votre lanterne.

> Comme le signale à propos Le Fessant, je me suis jamais
> distingué par une connaissance approfondie du code source du
> compilateur Caml, ni par ma virtuosité au maniement de la sémantique
> du langage.

Sans commentaire.

Cordialement.

-- Nicolas
-------------------
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

[Caml-list] Warnings possibles

[Diego Olivier Fernandez Pons]

La question du filtrage semble tranchée. Essayons une proposition qui
se veut constructive :

- Est-il possible d'avoir un warning quand on masque une variable lors
d'un filtrage ?
- Est-il possible (je veux dire est-ce réalisable ? difficile ? utile
?...) de signaler que deux motifs ne sont pas exclusifs

let f = function
  | (0,1) -> 1
  | (x,1) -> x
  | (1,y) -> y
  | _ -> 1

# Attention les motifs (x,1) et (1,y) ne sont pas disjoints par
exemple (1,1)

Je suppose qu'il doit y avoir des problèmes liés au motif universel _
(que l'on pourrait peut-être ignorer)

let f = function (x,y) ->
 match (x,y) with
  | (0,1) -> 1
  | (_,1) -> x
  | (1,_) -> y
  | _ -> 1
;;

ok !

(la superposition de motifs est ignorée car on utilise _ qui est
ignoré sauf pour le dernier qui assure que tous les cas sont traités)
Peut-être un flag "pedantic" comme en C pour avoir ces avertissements
là ?

        Diego Olivier



-------------------
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

Re: [Caml-list] Warnings possibles

[Luc Maranget]

> 
> La question du filtrage semble tranchée. Essayons une proposition qui
> se veut constructive :
> 
> - Est-il possible d'avoir un warning quand on masque une variable lors
> d'un filtrage ?
Peut-être, fonction de la demande populaire.
Il faut quand même remarquer que trop de warning tue le warning.


> - Est-il possible (je veux dire est-ce réalisable ? difficile ? utile
> ?...) de signaler que deux motifs ne sont pas exclusifs
C'est possible et moins dur que les filtrages non-exhaustifs.

Mais je ne vois pas de raison de le faire, il s'agit d'un trait reconnu du
filtrage. Je ne vois pas l'intérêt de considérer que des motifs
non-disjoints c'est mal.



> Peut-être un flag "pedantic" comme en C pour avoir ces avertissements
> là ?

C'est bien là un point d'achoppement. On essaie de limiter les
options.
Mais dans avec l'idée de cibler l'enseignement, on pourrait
effectivement le faire (pour la première suggestion).
Mais avec une option -cautious (j'aime pas ``pedantic'' pas très bien
connoté en français).

Bon, je ne m'y mets pas demain.
> 
>         Diego Olivier

--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

Re: [Caml-list] If ou Pattern-matching ?

[Luc Maranget]

Je répond en bloc à tout et brièvement.


Sans penser que nous (implémenteurs Caml etc.) détenons la science
infuse, je crois que notre avis sur comment doit être compris un trait
a un certain poids.


Donc le filtrage doit être interprété comme je l'ai expliqué
dans mon message précédent (prédicat ``<='' + liasons).
Ce n'est pas si dur à comprendre.

Le mot « sémantique » fait peut être peur, mais ça ne veut rien dire
d'autre que « voilà ce que votre programme fait ».
Une explication pas trop dure est de dire : voila comment votre
filtrage se traduit en ``if'' et en fonction d'accès aux champs

let f liste = match liste with
| [] -> 0
| x::_ -> x

C'est en fait :

let f liste =
  if liste = [] then 0
  else
    let x = car liste in
    x

Où ``car'' est une fonction spéciale qui accède au premier champ d'une
cellule de liste.

NB le fait que l'on puisse définir ``car'' à l'aide du filtrage ne
doit pas nous cacher que, dans le cadre de cette explication ``car''
est ``plus primitif'' que le filtrage.


Votre façon de considérer le filtrage est un brin trop compliquée.
Non seulement ça n'aiderait pas à concevoir le langage (mais c'est
notre problème), mais ça ne vous aide pas a programmer.

Maintenant, je reconnais un déficit d'explication sur ce qu'est le
filtrage aux utilisateurs et en particulier aux débutants.


--Luc Maranget


-------------------
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

Re: [Caml-list] Pattern matching

[Luc Maranget]

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

[Caml-list] Deux types de pattern-matching ?

[Diego Olivier Fernandez Pons]

< C'est très intéressant, car le pattern matching n'a qu'une seule
< définition.

Je ne suis pas informaticien de formation, encore moins spécialiste de
la sémantique des langages. Mon approche pour cette raison est
purement pragmatique :

let valeur = function
  | (1,2) -> 0
  | (1, snd) -> snd
  | (fst, snd) -> fst

Filtrage par valeurs : on peut transformer en « if then else »

let valeurs = function (x, y) ->
    if (x = 1) && (y = 2) then 1
    else if (x = 1) then y
    else x
;;

De même le code suivant

let valeur = function
  | [ ] -> 0
  | [1; 3] -> 1
  | _ -> 2

Par contre

let structure = function
  | [ ] -> 0
  | [x; 1] -> x
  | _ -> 2
;;

on ne peut pas transformer en « if then else » seul, il faut
utiliser un let destructurant (pour faire l'unification)

let structure = function liste ->
  if (liste = [ ]) then 0
  else
      let (x :: reste) = liste in
      if (reste = [1]) then x else 2
;;

Pour moi un code comme :

match couple with
| (0, 1) -> 0
| (1, y) -> y
| (x, y) -> x

commence par destructurer couple puis fait un filtrage de valeurs

let (x,y) = couple in
  match (x,y) with
  | (0,1) -> 0
  | (1, _) -> y
  | (_, _) -> x

Une seule liaison des variables x et y puis comparaisons (les
unifications multiples ne se justifient pas)
C'est d'ailleurs ce que fait la définition d'une fonction

let valeurs = function (x,y) -> [...]
let valeurs = function couple -> let (x,y) = couple in [...]

Autrement dit, je décompose le filtrage de motif en deux opérations
élémentaires :
  i) l'unification
  ii) disjonction de cas

Ce qui donne 3 « types » de filtrages
  - disjonction de cas (éventuellement précédée d'une unification)
  - unification (éventuellement suivie d'une disjonction)
  - mélange des deux

Je proscris pour les raisons déjà expliquées le mélange (risques
d'erreur liées aux variables muettes...) et recommande au lieu
l'enchaînement des deux opérations élémentaires

Bien sûr, formellement le code suivant
  match liste with
  | [x; 1] -> x
est équivalent à une disjonction de cas infinie
  ...
  | [0; 1] -> 0
  | [1; 1] -> 1
  | [2; 1] -> 2
  ...
Ce qui en ferait un filtrage de structure serait l'utilisation dans le
second membre d'un motif interne au premier membre, cela dit

let valeur = function
 | [ ] -> 0
 | [ _ ; 1] -> 1
 | _ ->2

ne peut pas se transformer en « if then else » sans unification et
n'utilise pas de motif interne au premier membre ce qui finit
d'achever la séparation des deux notions  : d'un point de vue
théorique elle est parfaitement vaseuse.

De toutes les façons, vous ne pouvez pas demander aux utilisateurs
d'un langage de comprendre parfaitement les fondements théoriques de
celui-ci pour l'utiliser correctement, sous peine de produire un
langage qui - comme Caml actuellement - ne dépassera jamais le cadre
des universitaires. Il faut résoudre un certain nombre de problèmes
pragmatiques liés à l'usage, et les erreurs (nombreuses) liées au
pattern matching en sont un.

        Diego Olivier






-------------------
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

[Caml-list] Re: Deux types de pattern-matching ?

[Luc Maranget]

> 
> < C'est très intéressant, car le pattern matching n'a qu'une seule
> < définition.
> 
> Je ne suis pas informaticien de formation, encore moins spécialiste de
> la sémantique des langages. Mon approche pour cette raison est
> purement pragmatique :
Bon j'en ai rajouté. Mais mon point reste de proposer une
vue simple et uniforme du filtrage. Nul besoin d'être spécialiste
de la sémantique, je vais essayer un point de vue de compilation de
Caml dans lui même.

> 
> let structure = function
>   | [ ] -> 0
>   | [x; 1] -> x
>   | _ -> 2
> ;;
> 
> on ne peut pas transformer en « if then else » seul, il faut
> utiliser un let destructurant (pour faire l'unification)
> 
Ben c'est pas comme ça que je présenterais les choses

> let structure = function liste ->
>   if (liste = [ ]) then 0
>   else
>       let (x :: reste) = liste in
>       if (reste = [1]) then x else 2
> ;;
Ça ne résoud pas le pb du pt de vue de la compilation, car il reste un
filtrage.
Supposons en plis du if, données deux fonctions ``car'' et ``cdr''
(qui sont en fait de facons plus génerales des fonction d'accès aux 
champs d'une cellule de liste, ie des accès indexés)
car x est (getfield 0 x)
Alors la compilation de structure est
 let structure = function liste ->

   if (liste = [ ]) then 0
   else
      let x = car x and reste = cdr list in
      if (reste = []) then 2
      else
        let tmp1 = car reste and tmp2 = cdr reste in
        if tmp1 = 1 then
           if tmp2 = [] then
             x
           else
             2
        else
          2
> 
> Pour moi un code comme :
> 
> match couple with
> | (0, 1) -> 0
> | (1, y) -> y
> | (x, y) -> x
> 
> commence par destructurer couple puis fait un filtrage de valeurs
> 
> let (x,y) = couple in
>   match (x,y) with
>   | (0,1) -> 0
>   | (1, _) -> y
>   | (_, _) -> x
> 
> Une seule liaison des variables x et y puis comparaisons (les
> unifications multiples ne se justifient pas)
> C'est d'ailleurs ce que fait la définition d'une fonction
> 
> let valeurs = function (x,y) -> [...]
> let valeurs = function couple -> let (x,y) = couple in [...]
> 
> Autrement dit, je décompose le filtrage de motif en deux opérations
> élémentaires :
>   i) l'unification
>   ii) disjonction de cas
Non c'est,
   filtrage (et non pas unification, c'est pas pareil)
   avec liasons éventuelle de variables des variables des filtres
   aux champs correspondants des valeurs filtrées.

J'ai l'air d'un vieux chouf, mais je crois que c'est comme ça
qu'on comprend le mieux.


> 
> Je proscris pour les raisons déjà expliquées le mélange (risques
> d'erreur liées aux variables muettes...) et recommande au lieu
> l'enchaînement des deux opérations élémentaires
> 
> Bien sûr, formellement le code suivant
>   match liste with
>   | [x; 1] -> x
> est équivalent à une disjonction de cas infinie
>   ...
>   | [0; 1] -> 0
>   | [1; 1] -> 1
>   | [2; 1] -> 2
>   ...
Non. La définition complète du filtrage (reporter vous au
prédicat ``<='' du message précédent) n'a pas besoin de ce truc
pour définir le filtrage par un motif contenant une variable.
(Même si en un sens l'équivalence est valide, mais elle n'aide pas
à comprendre ce qui se passe.
au niveaux élémentaire un filtre ``_::_'' est équivalent au prédicat
``c'est un cons'' (consp en lisp).



> Ce qui en ferait un filtrage de structure serait l'utilisation dans le
> second membre d'un motif interne au premier membre, cela dit
> 
> let valeur = function
>  | [ ] -> 0
>  | [ _ ; 1] -> 1
>  | _ ->2
> 
> ne peut pas se transformer en « if then else » sans unification et
> n'utilise pas de motif interne au premier membre ce qui finit
> d'achever la séparation des deux notions  : d'un point de vue
> théorique elle est parfaitement vaseuse.
> 
> De toutes les façons, vous ne pouvez pas demander aux utilisateurs
> d'un langage de comprendre parfaitement les fondements théoriques de
> celui-ci pour l'utiliser correctement, sous peine de produire un
> langage qui - comme Caml actuellement - ne dépassera jamais le cadre
> des universitaires. Il faut résoudre un certain nombre de problèmes
> pragmatiques liés à l'usage, et les erreurs (nombreuses) liées au
> pattern matching en sont un.
> 
C'est bien le problème. Pour avoir un langage de programmation
pas trop bizarre, un peu de théorie ne nuit jamais.
La « théorie » n'est pas le mal, n'est pas hors de portée.
Je ne crois pas que l'on puisse réellement programmer en utlisant le
filtrage, sans tout à fait comprendre ce qui se passe.

prenons un exemple extrêment simple qui évite les motifs trop
compliqués (c'est aussi un pb)

let f liste = match l with
| [] -> 0
| x::_ -> x

c'est

let f liste =
  if liste = [] then 0
  else
    




>         Diego Olivier
> 
> 
> 
> 
> 
> 

-------------------
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