Le Pattern Matching, le Demolition Man intelligent

Le pattern matching, ou filtrage par motif, est un des outils de programmation fonctionnelle dont les capacités sont parmi les plus subtiles à apprécier pour les développeurs, surtout s’ils font beaucoup de programmation objet. Si vous l’avez déjà rencontré, vous l’avez certainement comparé (au moins dans un premier temps) à une série de if voire d’instructions switch sous stéroïde. Il peut d’ailleurs tout à fait remplacer cette instruction. Mais en réalité, l’intérêt du pattern matching réside dans sa capacité à déconstruire l’encapsulation en posant des conditions de structure afin d’extraire des valeurs et de les manipuler. Bref, c’est une façon très commode de traiter les données. Et je vais vous le démontrer.

Le pattern matching est un des outils basiques de la programmation fonctionnelle. Il est comparable aux instructions switch ou if en C, C# ou Java dans une version sous steroid. C’est l’usage le plus simple que l’on puisse en faire. Cependant on peut en obtenir bien plus car :

• • le pattern matching est plus simple à écrire,
  • le switchmanipule des valeurs constantes à la compilation,
  • le filtrage par motif repose à la fois sur les valeurs (qui peuvent être dynamiques) et sur la structure de l’élément qui est filtré,
  • le pattern matching peut être vérifié dynamiquement à l’écriture du code pour s’assurer à la fois de la justesse et de la complétude du filtrage.

Par exemple, le dispatch de méthode qui, dans les langages objets, est le mécanisme qui permet au compilateur de déterminer quelle version d’une méthode parmi les redéfinitions dans l’arbre d’héritage il faut utiliser. Et bien figurez-vous qu’il peut être remplacé par le filtrage par motif dans les langages fonctionnels. Si on le pousse, il permet même de donner un contrôle plus fort encore, au point d’éliminer tout utilité au dispatch dynamique de méthode (le “duck typing”).

Une affaire de déconstruction

Commençons par nous mettre en situation et admettons que nous soyons dans une situation où nous souhaitons travailler avec des données d’un tuple. Par exemple en F# :

let data = ("First",2,3.0)
let first = match data with | (f, s, t) -> f

Dans la première partie, on définit un tuple. Si l’on souhaite extraire le premier élément, il faut donc déconstruire le tuple et pour cela, on utilise ce que l’on connaît, la structure, c’est un tuple de trois éléments. La syntaxe match data with indique que l’on veut comparer l’entité data avec les éléments des motifs structuraux (qui suivent le caractère “|”) qui vont suivre. Dans notre cas, nous avons défini qu’un seul motif car nous avons une forme fortement définie (f, s, t) qui est composée de trois éléments. Il reste donc à renvoyer le premier élément, ce qui est fait avec “-> f”.

Pratique à l’usage du placeholder…

On peut également faire appel à un caractère spécial, qui indique que l’on sait que quelque chose se trouve à cet endroit mais que sa valeur ne nous est pas utile. En d’autres termes, il s’agit du “placeholder”. En F#, ce caractère est le “_”. Dans notre précédent exemple, on ne se sert ni de la deuxième, ni de la troisième valeur. On peut donc écrire :

let first = match data with | (f, _, _) -> f

En Scala c’est plus simple puisque n’importe quel caractère (ou chaîne de caractères) peut remplir cette office. D’ailleurs, ce qui compte ici c’est bien le motif et pas les caractères qui viennent remplir le pattern même s’il est possible de mettre des conditions sur les placeholder de ces motifs. En d’autres termes, écrire (f, _, _) et (f,,) revient, à peu de chose près, au même puisqu’ils sont structurellement équivalents, on indique dans les deux cas que l’on attend un tuple de trois valeurs.

… ou des fonctions

Le pattern matching peut s’appliquer directement dans la signature des fonctions. Voici une fonction first qui fait le même travail que le précédent exemple de let binding (à ceci près qu’une fonction est réutilisable).

let first (f, _, _) = f

On peut également l’utiliser en ligne dans le code comme suit (toujours en F#) :

let f,_,_ = data

Ici la fonction prend un tuple de trois éléments en entrée et renvoie le premier élément. On trouve nativement en F#, les méthodes fst et snd s’appliquent à des tuples de deux éléments et retournent réciproquement le premier et le second élément.

En Scala c’est un peu différent puisque l’on peut accéder directement à chacun des champs d’un tuples. Dans le même contexte que l’exemple en F#, on obtient :

val data = (“First”, 2, 3.0)
val first = data._1

Utile à la sauce unapply

Il est possible, quand cela est utile, de redéfinir la méthode unapply afin de préciser la façon de déconstruire un objet. Il n’est cependant pas nécessaire de redéfinir cette méthode. Une implémentation par défaut est fournie permettant au pattern matching de fonctionner. On peut trouver une belle analyse de l’utilisation de cette méthode ici dans une série de post comparant le F# et le Scala. Dans le code suivant, nous redéfinissons cette méthode afin de préciser comment le filtrage par motif doit être exécuté :

//Classe personne
class Person(val lastname: String, val firstname: String) {
}
object Person {
def unapply(person: Person): Option[(String,String)] =
Some((person.lastname, person.firstname))
}
// application de la méthode unapply dans le filtrage par motif
new Person("Luke", "SKYWALKER") match {
case Person(_, "SKYWALKER") => print("Welcome !") case _ => print("You are not member of the SKYWALKER family.")
}

Si on s’intéresse aux motifs employés dans le cas du tuple, on constate rapidement qu’il y a une seule structure sous-jacente, les trois éléments constituant le 3-tuple. Dès lors que les objets acceptent une seule représentation structurelle (comme les tuples et les records), il suffit bien souvent d’un seul cas pour traiter l’ensemble des situations. Cela se complique avec les “union type”.

Une affaire de contrôle du dispatch

Supposons que nous voulions afficher des message de log. Dans un premier temps nous pourrions définir le type suivant :

type log =
| Error of string
| Warning of string
| Info of string
| Debug of string

Que l’on peut définir de cette façon en Scala :

abstract class Log(msg:String)

case class Error(msg:String) extends Log(msg)
case class Warning(msg:String) extends Log(msg)
case class Info(msg:String) extends Log(msg)
case class Debug(msg:String) extends Log(msg)

Le but ici est de pouvoir fournir une fonction qui pourrait afficher chacun de ces types de log dans le bon format au bon endroit.

let printLog printError printWarning printInfo printDebug log =
match log with
| Error logMess   -> printError logMess
| Warning logMess -> printWarning logMess
| Info logMess    -> printInfo logMess
| Debug logMess   -> printDebug logMess

Ce qui donne en Scala :

def printLog = (log:Log) => {
  log match {
    case x:Error => printError(x)
    case x:Warning => printWarning(x)
    case x:Info => printInfo(x)
    case x:Debug => printDebug(x)
  }
}

Cette fonction est un peu particulière car elle prend en entrée quatre autres fonctions spécialisées pour chacun des messages. Le pattern matching ici nous permet d’une part de récupérer le message encapsulé dans l’objet de type log, et de rediriger ce message vers la bonne fonction d’autre part.

C’est l’équivalent fonctionnel du design pattern visiteur que l’on trouve en programmation objet. Mais dans ce cas le contrôle sur les fonctions est encore plus fin. Par ailleurs, on évite en F# le dispatch polymorphique de méthode d’interface, qui peut se révéler coûteux quand on utilise plusieurs implémentations différentes d’une interface représentant le visiteur.

Et le mot clé “function” apparut

En fait l’utilisation du pattern matching et des types algébriques généralisés est parfaitement adaptée pour permettre ce contrôle qui s’apparente au dispatch de méthode. Il existe d’ailleurs une syntaxe pour le cas du dispatch simple. Si on reprend la méthode printLog écrite plus haut, on peut la réécrire de la façon suivante :

let printLog printError printWarning printInfo printDebug = function
    | Error logMess   -> printError logMess
    | Warning logMess -> printWarning logMess
    | Info logMess    -> printInfo logMess
    | Debug logMess   -> printDebug logMess
 

L’argument log disparaît ou plus précisément, il est implicite dans cette syntaxe. De la même façon, la syntaxe exploitant le mot clef match disparaît. En revanche, un nouveau mot clé apparaît : function.

En poussant ce fonctionnement, on voit comment on peut facilement faire varier au runtime l’affichage des log en modifiant les fonctions injectées dans la fonction printLog afin de remplacer le “dynamic dispatch” (le “duck typing”). C’est assez amusant quand on pense que le F# est typé statiquement

Détecter les implémentations manquantes

A ce stade, plusieurs interrogations sont légitimes : qu’est ce qui me garantit que l’ensemble des motifs proposés me permettra de couvrir tous les cas ? Si j’ajoute un élément dans mon type log comment le gérer dans les fonctions qui l’utilisent ?

Le filtrage de motif est une construction statique appliquée à des types statiques, on peut donc se reposer sur les compilateurs des langages fonctionnels. Ces derniers sont capables d’indiquer via des “warning” les pattern manquant. lIs indiqueront également les parties qui ne seront jamais atteintes ainsi que les branches redondantes.

Guard clause

Le filtrage de motif offre des possibilités que le dispatch de méthode ne permet pas. Pour commencer, on peut avoir plusieurs filtrages encapsulés. Personnellement je ne suis pas certain que ce soit toujours une bonne chose. Cela peut nuire à la lisibilité autant que des imbrications de ifet de switch. Il faut donc bien prendre garde à évaluer l’intérêt de le faire face à la maintenabilité du code.

Ensuite, il est également possible d’ajouter des clause dites “guard clause” permettant d’ajouter une condition sur la valeur en plus des conditions de structure. Par exemple pour créer une fonction qui détecte si un entier est pair, on peut écrire en F# :

let isEven n =
    match n with
    | i when i%2 = 0 -> true
    | _ -> false

Et en Scala :

def isEven = (n:Int) => n match {
  case _ if n % 2 == 0 => true
  case _ => false
}

La clause apparaît dans le motif après le mot clef when. Avec le F#, il existe un excellent système pour étendre le matching, l’”active pattern” qui peut, bien des fois, venir remplacer l’utilisation des “guard clause”. Vous trouverez une excellente explication de son fonctionnement ici.

Jusqu’au filtrage par motif parallèle

Dans de nombreux langages fonctionnels, il est également possible d’utiliser le filtrage par motif parallèle. Il s’agit d’appliquer un filtrage à deux objets en même temps sans que ceux-ci soient liés d’aucune façon. Vous pourrez trouver ici une référence de ce qui se fait en OCaml avec cet outil. C’est également possible en F# et en Scala.

Pour bien comprendre prenons un exemple en construisant une fonction avec les spécifications suivantes :

1. On utilise en entrée: deux list, une fonction et des valeurs par défaut
2. On extrait le premier élément des deux list
3. On utilise les éléments extraits comme arguments de la fonction (passés en entrée)
4. On peut traiter le cas où les deux list sont de tailles différentes
5. On utilise une valeur par défaut fournie en entrée pour remplacer les valeurs manquantes

Voici ce que l’on peut écrire en F# :

let rec map2WithDefault func defaultValue l1 l2 =
    match l1, l2 with 
    | (hd1::tl1, hd2::tl2) -> (func hd1 hd2)::(map2WithDefault func defaultValue tl1 tl2)
    | (hd1::tl1, ([] as emptyList)) -> (func hd1 defaultValue)::(map2WithDefault func defaultValue tl1 emptyList)
    | (([] as emptyList), hd2::tl2) -> (func defaultValue hd2)::(map2WithDefault func defaultValue emptyList tl2)
    | _ -> []

Et en Scala :

def map2WtihDefault[A,B](func:(A,A)=>B, defaultValue:A, l1:List[A], l2:List[A]): List[B] = {
  (l1, l2) match {
    case (hd1 :: tl1, hd2 :: tl2) => List(func(hd1, hd2)) ++ map2WtihDefault(func, defaultValue, tl1, tl2)
    case (hd1 :: tl1, Nil) => List(func(hd1, defaultValue)) ++ map2WtihDefault(func, defaultValue, tl1, Nil)
    case (Nil, hd2 :: tl2) => List(func(defaultValue, hd2)) ++ map2WtihDefault(func, defaultValue, Nil, tl2)
    case _ => List.empty
  }
}

Plusieurs choses sont intéressantes dans cet exemple. En premier lieu les list. Il s’agit de l’équivalent natif en F# et en Scala du type stack que nous avions défini ici. L’opérateur cons noté “::” lie un élément (“head” noté hd) avec une liste (“tail” noté tl). Ainsi la syntaxe hd::tldésigne une nouvelle liste.

Dans le cas du filtrage par motif, cette syntaxe nous permet également de déconstruire la liste en séparant le premier élément du reste de la liste. La liste vide est notée [] en F# et Nil en Scala. Lorsque l’on rencontre cet élément, on sait que l’on a parcouru toute la liste.

Une petite optimisation bien utile

La syntaxe ([] as emptyList) dans le filtrage permet de lier l’élément [] de la liste déconstruite au nom emptyList. L’avantage ici, c’est qu’il est possible de réutiliser cet élément plus tard. On évite ainsi de recréer une nouvelle liste vide (et donc un nouvel objet). C’est une petite optimisation plutôt utile.

Le motif (hd1::tl1, hd2::tl2) désigne un tuple de deux listes non triviales (aucune des listes n’est vides). On peut alors utiliser les valeurs hd1 et hd2afin de construire le nouvel élément (func hd1 hd2 en F# et func(hd1, hd2) en Scala) de la liste que nous sommes en train de construire. Pour élaborer la suite de la liste, on va simplement ajouter cet élément à la liste que l’on construit en appelant récursivement la fonction map2WithDefault.

Si on rencontre un motif ou une des listes est vide comme (hd1::tl1,([] as emptyList)) en F# et son équivalent en Scala : (hd1 :: tl1, Nil), qui indique que la liste de gauche est vide dans les deux cas, il n’est pas possible d’extraire l’élément hd2. On va donc le remplacer par la valeur par défaut defaultValue, dans les appels de fonction func.

Ce comportement n’est pas impossible à écrire dans des langages qui ne sont pas des langages fonctionnels. Il serait cependant particulièrement difficile à maintenir. Ici l’inférence de type et le typage statique sont des alliés précieux qui nous simplifient la tâche.

Convaincu ? Moi oui

Le filtrage par motif, combiné avec les types algébriques généralisés et les fonctions, permet on le voit d’arriver à un résultat extrêmement puissant. C’est d’ailleurs dans les fonctions que se synthétisent le mieux la portée et la puissance des langages fonctionnels. Ce qui est intéressant c’est de voir le que petit à petit des langages impératifs ajoutent cette fonctionnalité à leur arsenal. Le C# 7.0 a étendu l’instruction switch pour pouvoir l’implémenter par exemple.

Personnellement, je trouve le choix de l’opérateur malheureux car le filtrage par motif n’est pas simplement une instruction de branchement. D’ailleurs ils ont également ajouté la notion de déconstructeur (comme la méthode unapply en Scala) qui permet de profiter pleinement des fonctionnalités du filtrage par motif. Le Java n’est pas en reste dans cette évolution. Le projet Amber prépare justement l’ajout de la fonctionnalité.

Mais l’évolution de ces langages n’en est pas à sa première injection de paradigme fonctionnel. Pensez aux fonctions Lambda, au LINQ en C# et à la présence de tuple… la liste est longue. Et finalement il y a fort à parier qu’ils deviennent complètement accros. L’avenir des langages objets devra-t-il passer par une mutation vers les langages fonctionnels ?

——–

Si le sujet vous intéresse, ci-dessous, les autres articles du dossier sur la programmation fonctionnelle, co-écrit avec Clément Carreau :
– La programmation fonctionnelle, un nouvel espoir
– Créer des types fonctionnel en F# et en Scala