14/07/2007

[Lang] Pattern matching

Pattern matching simple

Le pattern matching est une fonctionnalité que l'on retrouve dans un certain nombre de langages, majoritairement fonctionnels. Dans sa forme la plus simple, c'est la capacité à déconstruire des types (en se basant sur les constructeurs de types) et à faire correspondre une valeur avec le motif associé. Par exemple, le type list est souvent défini récursivement comme étant : soit la liste vide, soit un élément suivi d'une liste.

On peut définir une fonction foo qui renvoie une liste dans laquelle un élément sur deux a été enlevé. Voici son code en Caml :

let rec foo = function
| [] -> []
| e1::[] -> []
| e1::e2::l -> e2 :: (foo l)

[] signifie la liste vide. L'opérateur :: est l'opérateur de construction de liste. Le pattern matching cherche à mettre en correspondance l'argument de la fonction (une liste) avec les différents motifs : liste vide, liste à un élément, liste à au moins deux éléments. On remarque d'une part que le test est totalement exhaustif : toute liste correspondra à au moins une branche, il ne peut donc pas y avoir d'erreur. On remarque d'autre part que le test est totalement non redondant : toute liste correspondra à au plus une branche, l'ordre des motifs ne change rien. C'est donc le type de pattern matching que gère Anubis.

Le compilateur peut ainsi, par analyse statique du programme, vérifier que le pattern matching est exhaustif et signaler une erreur à la compilation s'il manque une branche.

 

Pattern matching et redondance

Certains langages ne limitent pas le pattern matching à la déconstruction de types, ils permettent aussi de comparer des valeurs (un peu comme dans un switch). Dès lors que l'on introduit des valeurs, il y a risque de redondance. Par exemple, si on définit la fonction f suivante :

let f = function
 | 2 -> 2
 | n -> n + 1

On peut observer une "redondance" : la valeur 2 matche théoriquement les 2 motifs. Donc, l'ordre dans lequel les tests sont faits est important. Cet
ordre est défini dans les spécifications : c'est de haut en bas. Mais
quelque part, ça gêne un peu. Comment se fait-il que, quand on programme
en fonctionnel pur, l'ordre des définitions ait une quelconque
importance ? Au niveau théorique, on aimerait qu'il n'y en ait pas. C'est ce que Alain Prouté, concepteur d'Anubis, critique. Toutefois, le compilateur peut encore s'assurer que le pattern matching est exhaustif.

 

Autre exemple du même type, mais plus marquant :

let f = function
| n when n mod 2 = 0 -> 2
| n when n mod 3 = 0 -> 3
| n -> 0

L'ordre des tests a vraiment une importance, puisque le when définit une condition qu'il faut vérifier à l'exécution. Certains peuvent trouver cela moins propre, moins sûr ou plus éloigné du pattern matching standard. En effet, toutes les conditions doivent être testées dans l'ordre. Les détections d'exhaustivité et de redondance se retrouvent nettement affaiblies. Sans compter que les conditions peuvent cacher de lourds calculs ou même des effets de bord (c'est bien sûr très fortement déconseillé).

Cependant, ce n'est pas forcément à considérer comme dangereux, même pour quelqu'un qui place la sûreté du programme au centre de ses préoccupations. On peut voir cette construction comme du sucre syntaxique. Ce n'est rien de plus que le pattern matching traditionnel qui renvoie une conditionnelle (un "if") comme valeur. Au final, ce sucre apporte concision et expressivité, sans rien perdre au niveau sûreté.

Ce billet sert de transition entre la présentation d'Anubis et la présentation des active patterns de F# (à venir).