Correspondance de motifs - Pattern matching

Cet article concerne la correspondance de modèles dans la programmation fonctionnelle . Pour d'autres utilisations, voir correspondance de chaînes et reconnaissance de formes .
Pour l'utilisation de critères de correspondance de variables dans la définition de modèles abstraits à faire correspondre, voir expression régulière .

En informatique , l' appariement de motifs est l'acte de vérifier une séquence donnée de jetons pour la présence des constituants d'un motif . Contrairement à la reconnaissance de formes , la correspondance doit généralement être exacte : « cela sera ou ne sera pas une correspondance ». Les motifs ont généralement la forme soit de séquences, soit d' arborescences . Les utilisations de la correspondance de modèle incluent la sortie des emplacements (le cas échéant) d'un modèle dans une séquence de jetons, la sortie d'un composant du modèle correspondant et le remplacement du modèle de correspondance par une autre séquence de jetons (c'est-à-dire rechercher et remplacer ).

Les modèles de séquence (par exemple, une chaîne de texte) sont souvent décrits à l'aide d' expressions régulières et mis en correspondance à l'aide de techniques telles que le backtracking .

Les modèles d'arbre sont utilisés dans certains langages de programmation comme un outil général pour traiter les données en fonction de leur structure, par exemple C# , F# , Haskell , ML , Python , Ruby , Rust , Scala , Swift et le langage mathématique symbolique Mathematica ont une syntaxe spéciale pour exprimer l'arbre modèles et une construction de langage pour l' exécution conditionnelle et la récupération de valeur basée sur celui-ci.

Souvent, il est possible de donner des modèles alternatifs qui sont essayés un par un, ce qui donne une puissante construction de programmation conditionnelle . La correspondance de motifs inclut parfois la prise en charge des gardes .

Les algorithmes d' analyse s'appuient souvent sur la correspondance de modèles pour transformer les chaînes en arbres de syntaxe .

Histoire

Les premiers langages de programmation avec des constructions de correspondance de motifs incluent COMIT (1957), SNOBOL (1962), Refal (1968) avec correspondance de motifs arborescente, Prolog (1972), SASL (1976), NPL (1977) et KRC (1981).

De nombreux éditeurs de texte prennent en charge la correspondance de modèles de différents types : l' éditeur QED prend en charge la recherche d' expressions régulières et certaines versions de TECO prennent en charge l'opérateur OR dans les recherches.

Les systèmes de calcul formel prennent généralement en charge la correspondance de formes sur les expressions algébriques.

Voir aussi : Expression régulière § Historique

Motifs primitifs

Le modèle le plus simple dans la correspondance de modèle est une valeur explicite ou une variable. Par exemple, considérons une définition de fonction simple dans la syntaxe Haskell (les paramètres de fonction ne sont pas entre parenthèses mais sont séparés par des espaces, = n'est pas une affectation mais une définition) : 

f 0 = 1

Ici, 0 est un modèle à valeur unique. Maintenant, chaque fois que f reçoit 0 comme argument, le motif correspond et la fonction renvoie 1. Avec tout autre argument, la correspondance et donc la fonction échouent. Comme la syntaxe prend en charge des modèles alternatifs dans les définitions de fonctions, nous pouvons continuer la définition en l'étendant pour prendre des arguments plus génériques : 

f n = n * f (n-1)

Ici, le premier nest un modèle de variable unique, qui correspondra à n'importe quel argument et le liera au nom n pour être utilisé dans le reste de la définition. En Haskell (contrairement à au moins Hope ), les motifs sont essayés dans l'ordre, de sorte que la première définition s'applique toujours dans le cas très spécifique où l'entrée est 0, tandis que pour tout autre argument, la fonction renvoie n * f (n-1)n étant l'argument.

Le motif générique (souvent écrit _) est également simple : comme un nom de variable, il correspond à n'importe quelle valeur, mais ne lie la valeur à aucun nom. Des algorithmes pour faire correspondre les caractères génériques dans des situations de correspondance de chaînes simples ont été développés dans un certain nombre de variétés récursives et non récursives.

Motifs d'arbres

Des modèles plus complexes peuvent être construits à partir des modèles primitifs de la section précédente, généralement de la même manière que les valeurs sont construites en combinant d'autres valeurs. La différence est alors qu'avec les parties variables et génériques, un modèle ne se fonde pas dans une valeur unique, mais correspond à un groupe de valeurs qui sont la combinaison des éléments concrets et des éléments qui sont autorisés à varier dans la structure du modèle .

Un modèle d'arbre décrit une partie d'un arbre en commençant par un nœud et en spécifiant des branches et des nœuds et en laissant certains non spécifiés avec une variable ou un modèle générique. Il peut être utile de penser à l' arbre syntaxique abstrait d'un langage de programmation et aux types de données algébriques .

En Haskell, la ligne suivante définit un type de données algébrique Colorqui a un seul constructeur de données ColorConstructorqui encapsule un entier et une chaîne. 

data Color = ColorConstructor Integer String

Le constructeur est un nœud dans un arbre et l'entier et la chaîne sont des feuilles dans les branches.

Lorsque nous voulons écrire des fonctions pour créer Colorun type de données abstrait , nous souhaitons écrire des fonctions pour s'interfacer avec le type de données, et donc nous voulons extraire des données du type de données, par exemple, juste la chaîne ou juste la partie entière de Color.

Si nous passons une variable de type Color, comment pouvons-nous extraire les données de cette variable ? Par exemple, pour qu'une fonction obtienne la partie entière de Color, nous pouvons utiliser un modèle d'arbre simple et écrire : 

integerPart (ColorConstructor theInteger _) = theInteger

Ainsi que: 

stringPart (ColorConstructor _ theString) = theString

Les créations de ces fonctions peuvent être automatisées par la syntaxe d' enregistrement de données de Haskell .

Cet exemple Ocaml qui définit un arbre rouge-noir et une fonction pour le rééquilibrer après l'insertion d'un élément montre comment faire correspondre sur une structure plus complexe générée par un type de données récursif. 

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with
    | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)
    | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)                                  
    | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))
    | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))
        ->  Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))
    | _ -> t (* the 'catch-all' case if no previous pattern matches *)

Filtrage des données avec des modèles

La correspondance de modèle peut être utilisée pour filtrer les données d'une certaine structure. Par exemple, en Haskell, une compréhension de liste peut être utilisée pour ce type de filtrage : 

[A x|A x <- [A 1, B 1, A 2, B 2]]

évalue à 

[A 1, A 2]

Correspondance de motifs dans Mathematica

Dans Mathematica , la seule structure qui existe est l' arbre , qui est peuplé de symboles. Dans la syntaxe Haskell utilisée jusqu'à présent, cela pourrait être défini comme 

data SymbolTree = Symbol String [SymbolTree]

Un exemple d'arbre pourrait alors ressembler à 

Symbol "a" [Symbol "b" [], Symbol "c" []]

Dans la syntaxe traditionnelle, plus appropriée, les symboles sont écrits tels quels et les niveaux de l'arbre sont représentés à l'aide de [], de sorte que par exemple a[b,c]est un arbre avec a comme parent, et b et c comme enfants.

Un modèle dans Mathematica consiste à mettre "_" à des positions dans cet arbre. Par exemple, le motif 

A[_]

correspondra à des éléments tels que A[1], A[2], ou plus généralement A[ x ] où x est n'importe quelle entité. Dans ce cas, Aest l'élément concret, tandis que _désigne le morceau d'arbre qui peut être varié. Un symbole ajouté à _lie la correspondance à ce nom de variable tandis qu'un symbole ajouté à _restreint les correspondances aux nœuds de ce symbole. Notez que même les blancs eux-mêmes sont représentés en interne comme Blank[]pour _et Blank[x]pour _x.

La fonction Mathematica Casesfiltre les éléments du premier argument qui correspondent au modèle du deuxième argument : 

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

évalue à 

{a[1], a[2]}

La correspondance de modèle s'applique à la structure des expressions. Dans l'exemple ci-dessous, 

Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

Retour 

{a[b[c],d], a[b[c],d[e]]}

car seuls ces éléments correspondront au modèle a[b[_],_]ci-dessus.

Dans Mathematica, il est également possible d'extraire des structures telles qu'elles sont créées au cours du calcul, peu importe comment et où elles apparaissent. La fonction Tracepeut être utilisée pour surveiller un calcul et renvoyer les éléments qui surviennent et qui correspondent à un modèle. Par exemple, nous pouvons définir la suite de Fibonacci comme 

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

Ensuite, on peut se poser la question : Étant donné fib[3], quelle est la séquence d'appels récursifs de Fibonacci ? 

Trace[fib[3], fib[_]]

renvoie une structure qui représente les occurrences du motif fib[_]dans la structure de calcul : 

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

Programmation déclarative

Dans les langages de programmation symbolique, il est facile d'avoir des motifs comme arguments de fonctions ou comme éléments de structures de données. Une conséquence de ceci est la possibilité d'utiliser des modèles pour faire des déclarations déclaratives sur des éléments de données et pour indiquer de manière flexible aux fonctions comment fonctionner.

Par exemple, la fonction MathematicaCompile peut être utilisée pour créer des versions plus efficaces du code. Dans l'exemple suivant, les détails n'ont pas particulièrement d'importance ; ce qui compte, c'est que la sous-expression {{com[_], Integer}}indique Compileque les expressions de la forme com[_]peuvent être supposées être des entiers à des fins de compilation : 

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

Les boîtes aux lettres en Erlang fonctionnent également de cette façon.

La correspondance de Curry-Howard entre les preuves et les programmes relie l' appariement de modèle de style ML à l' analyse de cas et à la preuve par épuisement .

Correspondance de motifs et chaînes

La forme de loin la plus courante de correspondance de motifs implique des chaînes de caractères. Dans de nombreux langages de programmation, une syntaxe particulière de chaînes est utilisée pour représenter des expressions régulières, qui sont des modèles décrivant des caractères de chaîne.

Cependant, il est possible d'effectuer certaines correspondances de modèles de chaîne dans le même cadre que celui qui a été décrit tout au long de cet article.

Motifs d'arbres pour les cordes

Dans Mathematica, les chaînes sont représentées comme des arbres de racine StringExpression et tous les caractères dans l'ordre comme des enfants de la racine. Ainsi, pour faire correspondre "n'importe quel nombre de caractères de fin", un nouveau caractère générique ___ est nécessaire contrairement à _ qui ne correspondrait qu'à un seul caractère.

Dans Haskell et les langages de programmation fonctionnels en général, les chaînes sont représentées sous forme de listes fonctionnelles de caractères. Une liste fonctionnelle est définie comme une liste vide, ou un élément construit sur une liste existante. Dans la syntaxe Haskell : 

[] -- an empty list
x:xs -- an element x constructed on a list xs

La structure d'une liste avec certains éléments est donc element:list. Lors de l'appariement de motifs, nous affirmons qu'un certain élément de données est égal à un certain motif. Par exemple, dans la fonction : 

head (element:list) = element

Nous affirmons que le premier élément de headl'argument de 's est appelé element, et la fonction renvoie ceci. Nous savons que c'est le premier élément à cause de la façon dont les listes sont définies, un seul élément construit sur une liste. Cet élément unique doit être le premier. La liste vide ne correspondrait pas du tout au modèle, car une liste vide n'a pas de tête (le premier élément qui est construit).

Dans l'exemple, nous n'avons aucune utilité pour list, nous pouvons donc l'ignorer, et ainsi écrire la fonction : 

head (element:_) = element

La transformation Mathematica équivalente est exprimée par 

head[element, ]:=element

Exemples de modèles de chaînes

Dans Mathematica, par exemple, 

StringExpression["a",_]

correspondra à une chaîne qui a deux caractères et commence par "a".

Le même schéma en Haskell : 

['a', _]

Des entités symboliques peuvent être introduites pour représenter de nombreuses classes différentes de caractéristiques pertinentes d'une chaîne. Par exemple, 

StringExpression[LetterCharacter, DigitCharacter]

correspondra à une chaîne composée d'abord d'une lettre, puis d'un nombre.

En Haskell, les gardes pourraient être utilisés pour réaliser les mêmes matchs : 

[letter, digit] | isAlpha letter && isDigit digit

Le principal avantage de la manipulation de chaînes symboliques est qu'elle peut être complètement intégrée au reste du langage de programmation, plutôt que d'être une sous-unité distincte à usage spécial. Toute la puissance du langage peut être exploitée pour construire les modèles eux-mêmes ou analyser et transformer les programmes qui les contiennent.

SNOBOL

Article détaillé : SNOBOL

SNOBOL ( StriNg Oriented and symBOlic Language ) est un langage de programmation informatique développé entre 1962 et 1967 aux laboratoires AT&T Bell par David J. Farber , Ralph E. Griswold et Ivan P. Polonsky .

SNOBOL4 se distingue de la plupart des langages de programmation en ayant des modèles en tant que type de données de première classe ( c'est-à - dire un type de données dont les valeurs peuvent être manipulées de toutes les manières autorisées pour tout autre type de données dans le langage de programmation) et en fournissant des opérateurs pour la concaténation et l' alternance de modèles . Les chaînes générées lors de l'exécution peuvent être traitées comme des programmes et exécutées.

Le SNOBOL a été assez largement enseigné dans les grandes universités américaines à la fin des années 1960 et au début des années 1970 et a été largement utilisé dans les années 1970 et 1980 comme langage de manipulation de texte dans les sciences humaines .

Depuis la création de SNOBOL, des langages plus récents tels que Awk et Perl ont rendu à la mode la manipulation de chaînes au moyen d' expressions régulières . Les modèles SNOBOL4, cependant, englobent les grammaires BNF , qui sont équivalentes aux grammaires sans contexte et plus puissantes que les expressions régulières .

Voir également

Les références

Liens externes