Limitations du filtrage

Limitations du filtrage

[Valentin Bonnard]

J'ai essaye' ce programme avec caml-light:

let x = 4;;
let f = fun x -> true
          | _ -> false;;

Je voulais faire une fonction qui teste si son 
argument vaut 4.

A ma grande surprise cela n'a pas fonctioner puisque 
caml-light interprete cela comme:

let f = fun _ -> true
          | _ -> false;;

Cela implique qu'il n'est pas possible de de'finir
de vraies constantes symboliques dans le langage.

De meme

let f = fun 2+2 -> true
          | _   -> false;;

n'est pas accepte'.

On ne peut pas introduire de variable valant 2+2;
comment faire si on ne sait pas calculer a la main
2+2 pour faire un filtrage ? (sans utiliser le
when).

De plus:

let rec compare_list = fun
      (x::_) (x::_)  -> x
    | (_::l) (_::l') -> compare_list l l'
    | _ _ -> raise No_Common_Elt
;;

Produit le message:
The variable x is bound several times in this pattern.

Bien sur on peut utiliser un when mais le filtrage est
sense' etre une solution elegante et je ne considere pas
le fait d'introduire deux noms de variables pour tester
si elle sont egale comme particulierement elegant.
(J'ai fais du Prolog avant de faire du Caml.)

Il n'est pas non plus possible d'utiliser la meme
variable dans un filtrage avec |

   | 1,x::_ | _,[x] -> une_action_complique'e x

n'est pas accepte'.

Il faut repeter

  | 1,x::_ -> une_action_complique'e x
  | 1,x::_ -> une_action_complique'e x

Qui est lourd est long si une_action_complique'e 
est long.

Y a t_il une raison profonde a ces limitations ?

Est-ce que les restrictions minuscules/majuscules
en O'Caml pourraient resoudre le probleme ?

-- 

+-----------------------------------------------+
+ Valentin Bonnard                              +
+ mailto:bonnardv@pratique.fr                   +
+ mailto:p6inf533@ufr-info-p6.cicrp.jussieu.fr  +
+ mailto:p6inf533@maya.cicrp.jussieu.fr         +
+-----------------------------------------------+

Re: Limitations du filtrage

[Pierre Weis]

[I apologize for the lack of english translation.
 Abstract of my answer:
 - there is no macro facility in Caml (in particular ``let'' does not
   define macros). 
 - non linear patterns are untractable, unless introducing the use of a generic
   equality in pattern matching. That would clobber the clean semantics
   of the pattern matching mechanism. We prefer explicit tests, written
   by the user in ``when'' clause.
 - although tricky, variables in orpat are consistent with the rest of
 the pattern matching mechanism and have been implemented
 in Caml V3.1]

Bonjour,

> J'ai essaye' ce programme avec caml-light:
> 
> let x = 4;;
> let f = fun x -> true
>           | _ -> false;;
> 
> Je voulais faire une fonction qui teste si son 
> argument vaut 4.
> 
> A ma grande surprise cela n'a pas fonctioner puisque 
> caml-light interprete cela comme:
> 
> let f = fun _ -> true
>           | _ -> false;;

Exact. La construction ``let'' ne sert pas a` de'finir des macros
(elle ne correspond pas au #define de C), mais a` lier des
identificateurs a` des valeurs.

En outre, les occurrences de variables dans les filtres sont toujours liantes;
outre ces variables les filtres ne comportent que des constantes
(pre'de'finies ou constructeurs de types concrets de l'utilisateur). 

Il vous fallait donc e'crire un filtre explicitement constant:

let f = function 4 -> true | _ -> false;;

> Cela implique qu'il n'est pas possible de de'finir
> de vraies constantes symboliques dans le langage.
> 
> De meme
> 
> let f = fun 2+2 -> true
>           | _   -> false;;
> 
> n'est pas accepte'.

Exact, et pour la me^me raison que ci-dessus (2 + 2 n'est pas une
constante, mais une valeur calcule'e).

> On ne peut pas introduire de variable valant 2+2;
> comment faire si on ne sait pas calculer a la main
> 2+2 pour faire un filtrage ? (sans utiliser le
> when).

On ne peut effectivement pas tester si un argument est e'gal a` un
entier sans calculer cet entier.

> De plus:
> 
> let rec compare_list = fun
>       (x::_) (x::_)  -> x
>     | (_::l) (_::l') -> compare_list l l'
>     | _ _ -> raise No_Common_Elt
> ;;
> 
> Produit le message:
> The variable x is bound several times in this pattern.

Effectivement, le proble`me ici est celui du filtrage non line'aire
(avec apparition de multiples occurrences de la me^me variable)
qui ne'cessite l'emploi de l'e'galite' au cours du filtrage.

> Bien sur on peut utiliser un when mais le filtrage est
> sense' etre une solution elegante et je ne considere pas
> le fait d'introduire deux noms de variables pour tester
> si elle sont egale comme particulierement elegant.
> (J'ai fais du Prolog avant de faire du Caml.)

Oui, j'allais vous proposer une clause ``when''. Je ne discuterai pas
de conside'ration d'e'le'gance, je ne suis pas spe'cialiste de cette
discipline. Cependant, si vous refusez l'emploi de ``when'', c'est
sans doute que vous supposez que le compilateur va re'soudre pour vous
le proble`me en testant l'e'galite' des deux occurrences de la
variable x, ou l'e'galite' de l'argument avec une ``constante
calcule'e''. Dans les deux cas, le compilateur doit introduire un test
d'e'galite' entre deux valeurs arbitraires.

On ne peut pas introduire une telle utilisation IMPLICITE de l'e'galite'
GE'NE'RIQUE dans le filtrage sans gravement mettre en danger la
se'mantique du langage. Le proble`me vient de la se'mantique de
cette e'galite' qui est extre^mement complexe, voire inde'cidable dans
certains cas: que faire si votre ``constante calcule'e'' (votre 2 + 2)
est une fonction ? une valeur boucle'e ? un flux infini ? une
expression qui boucle ? une valeur d'un type abstrait ?

Cet inconve'nient majeur disparai^t avec les clauses garde'es, puisque
l'utilisateur choisit lui-me^me la fonction qu'il appelle en la
mentionnant explicitement. On conserve ainsi un filtrage qui termine
toujours (et me^me en un temps proportionnel a` la complexite' de ce
filtrage [nombre de clause X longueur maximale des filtres]).

> Il n'est pas non plus possible d'utiliser la meme
> variable dans un filtrage avec |
> 
>    | 1,x::_ | _,[x] -> une_action_complique'e x
> 
> n'est pas accepte'.
> 
> Il faut repeter
> 
>   | 1,x::_ -> une_action_complique'e x
>   | 1,x::_ -> une_action_complique'e x
> 
> Qui est lourd est long si une_action_complique'e 
> est long.

Il n'y aurait pas de contre-indication the'orique, si ce n'est que
1) tous les filtres devraient comporter le me^me ensemble de variables
2) toutes les occurrences de cette variable devraient avoir le me^me type
3) ce trait impose des contraintes au compilateur (de'partage des
expressions de parties droites de clause ou acce`s anticipe' aux
variables des filtres ce qui poserait des proble`mes se'mantiques en
cas de structures paresseuses).

Ce trait existe dans Caml V3.1 avec la se'mantique du de'partage des
actions, ce qui peut e'videmment entrai^ner une croissance
exponentielle du code ge'ne're' (mais pre'serve la compatibilite avec
l'e'valuation des valeurs paresseuses).

> Y a t_il une raison profonde a ces limitations ?

Celles-ci dessus ?

> Est-ce que les restrictions minuscules/majuscules
> en O'Caml pourraient resoudre le probleme ?

Je ne vois pas vraiment en quoi cela re'soudrait le proble`me ...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis