-
Notifications
You must be signed in to change notification settings - Fork 8
6.7 Structure de données et programmation par motif
LispE fournit un moyen de manipuler les types de données propres aux langages de programmation fonctionnelle.
Une structure de données dans LispE est créée par le mot clé : data suivi d'une liste de descripteurs :
;Structures de données de base
(data (D1 p1 p2 ...) (D2 p1 p2 ...) (D3 p1 p2 ...) ...)
;Groupe de structure de données identifié par un "nom
(data nom (D1 p1 p2 ...) (D2 p1 p2 ...) (D3 p1 p2 ...) ...)Chaque descripteur Dd est un atome suivi d'une liste de paramètres.
Vous pouvez éventuellement ajouter un nom à un groupe de définitions de structures de données.
;Quelques structures de données de base
(data (Point _ _) (Cercle _ ) (Rectangle _ _) )
;Nous créons une forme, qui est soit un triangle, soit un carré
(data Forme (Triangle _ _ _) (Carré _))
Nous utilisons "_" pour indiquer que le type du paramètre ne compte pas.
Note : "_" est en fait un alias pour nil. Vous pouvez donc remplacer cette description par :
(data (Point nil nil) (Cercle nil) (Rectangle nil nil) )Nous utilisons le "_" pour suivre une vieille tradition.
En passant, comme les parenthèses sont un peu trop nombreuses dans ces contextes, vous pouvez les remplacer par [] si vous le souhaitez. Ceci est également vrai pour les fonctions à motif. Par conséquent, vous pouvez remplacer les définitions ci-dessus par :
; Quelques structures de données de base
(data [Point _ _] [Cercle _] [Rectangle _ _] )
; Nous créons une forme, qui est soit un triangle, soit un carré
(data Forme [Triangle _ _ _] [Carré _])
Cette notation ne modifie pas la sémantique de ces définitions, mais elle agit comme un repère visuel et rend le code plus lisible. Notez que si vous commencez par un [, vous devez terminer par un ].
La création d'une instance est très simple. Vous implémentez simplement une liste qui contient le nom de votre structure de données avec ses arguments. LispE vérifie alors si la structure correspond à sa définition.
(setq v (Point 10 20))
(setq v (Point 10))
; Erreur : Incohérence de taille entre la liste d'arguments et la définition de la structure de donnéesIl est en effet possible de mettre une contrainte sur les arguments. LispE fournit déjà la liste suivante des types de base :
- atom_
- error_.
- integer_
- number_
- string_
- list_
- dictionary_
- dictionary_n_
Dans ce cas, vous pouvez forcer les arguments à être d'un certain type. Par exemple, vous pouvez forcer Point à n'accepter que des integer_.
(data (Point integer_ integer_))Si vous essayez de créer une structure de données qui ne correspond pas, une erreur sera renvoyée.
(setq v (Point 10 'test))
; Erreur : mauvais type pour l'argument : 2 (integer_ exigé)Bien sûr, vous pouvez définir des définitions imbriquées :
(data [Point _ _] [Cercle (Point _ _) _ ] [Rectangle (Point _ _) _ _ ] )
qui sera à nouveau appliqué par LispE.
defpat signifie : pattern function definition ou définition d'une fonction par motif.
defpat permet de définir des fonctions qui peuvent partager le même nom mais qui diffèrent par la définition de leurs paramètres (polymorphisme). LispE choisira la première fonction de la liste qui correspond à vos arguments.
Une fonction par motif peut prendre autant de paramètres (Pi) que vous le souhaitez (enfin... en fait jusqu'à 15). Un paramètre est défini comme suit :
- P -> (type P1...Pn) où type est une structure de données ou un type de base
- P -> (condition V1...Vn P) où condition est soit un appel de fonction, soit une instruction de base.
V1...Vnsont des valeurs. Il ne peut y avoir qu'un seul paramètre P, toujours à la fin de la condition. - P -> atome : une variable simple, qui peut être unifiée avec un argument.
- P -> valeur qui devrait correspondre à l'argument. Notez que cette valeur peut être une liste, si le premier élément de cette liste n'est pas un type, une fonction ou une instruction.
Bien sûr, toutes ces définitions peuvent être imbriquées les unes dans les autres.
Important: L'ordre dans lequel les fonctions sont appliquées est contraint par la présence d'un type sur le premier paramètre. Si ce type est manquant, lorsque P n'est qu'une condition ou un atome, alors cette fonction est considérée comme une fonction de repli et ne sera appliquée que lorsque toutes les fonctions typées correspondantes auront été testées. La sélection se fait donc en fonction du type d'argument...
; Le célèbre exemple de FIZZBUZZ
; On vérifie si le reste de v/d est 0
(defun checkmod (d v) (eq (% v d) 0))
; Nous avons ici une déclaration imbriquée :
; nous commençons par : P -> (type P)
; P -> (integer_ P')
; P' -> (checkmod v P'')
; P'' -> atome
; d'où : (integer_ (checkmod valeur atome))
; Si l'élément peut être divisé par 15, on retourne fizzbuzz
(defpat fizzbuzz ( [integer_ (checkmod 15 x)] ) fizzbuzz)
; Si l'élément peut être divisé par 3, on renvoie fizz
(defpat fizzbuzz ( [integer_ (checkmod 3 x)] ) fizz)
; Si l'élément peut être divisé par 5, on renvoie buzz
(defpat fizzbuzz ( [integer_ (checkmod 5 x)] ) buzz)
; Fonction de repli, pas de type, on retourne x
; Cette fonction ne sera appelée que si aucune de ces conditions ne s'applique
(defpat fizzbuzz (x) x)
; Nous appliquons "fizzbuzz" aux 100 premiers éléments.
; Le type d'argument est : integer_
(map 'fizzbuzz (range 1 100 1))Notez que si vous utilisez une macro au lieu d'une fonction, le dernier élément de la macro doit également être une variable qui sera celle avec laquelle l'argument sera unifié.
; Nous remplaçons "checkmod" par une macro...
; Il est à noter que dans ce cas, l'ordre des paramètres impose
; que le dernier élément soit une variable. Nous utilisons flip pour corriger ce problème
(defmacro checkmod (val var) (eq 0 (flip (% val var)))
; Comme checkmod est une macro, elle sera insérée dans la liste des paramètres de chaque fonction,
; qui impose que le dernier paramètre soit la variable
; qui sera unifié avec l'argument : ici var
; D'où, après application de la macro,
; Les fonctions fizzbuzz auront donc l'implémentation suivante :
(defpat fizzbuzz ( [integer_ (eq 0 (flip (% 3 x)))] ) 'fizz)
Bien sûr, une fonction par motif peut accepter une structure de données comme paramètres :
; Définissons d'abord notre structure de données
(data [Cercle integer_] [Rectangle integer_ integer_] )
; Nous définissons la surface en fonction du type d'objet :
; Voici la surface d'un cercle :
(defpat Surface ( [Cercle r] ) (* _pi r r))
; Voici la surface d'un rectangle
(defpat Surface ( [Rectangle w h] ) (* w h))
; Le triangle est ici équilatéral, une seule valeur suffit
(data Forme [Triangle _] [Carré _])
; Nous définissons une fonction par motif qui prend une Forme comme argument
(defpat dim( [Forme dimension] )
(println 'Dimension dimension)
)Nous avons défini notre structure de données avec deux définitions pour Surface, l'une pour un cercle, l'autre pour un rectangle. Maintenant, le système va automatiquement choisir la bonne fonction en fonction de ses arguments :
(println (Surface [Cercle 10] )) donne : 314.159
; Si nous fournissons une structure en rectangle
(println (Surface [Rectangle 10 20] )) donne : 200
; Ces deux appels sont possibles car Triange et Carré sont des Forme.
(dim (Triangle 10))
(dim (Carré 20))
Lorsque vous définissez votre fonction, vous pouvez également remplacer certains champs par un nil.
(defpat Largeur ( [Rectangle w _] ) w)
Le second paramètre pour Rectangle n'est pas nécessaire ici, il est simplement écarté.
Tout d'abord, les types de base sont en fait tous définis en tant que structure de données, ce qui signifie que vous pouvez les utiliser pour ajouter une contrainte sur le type des arguments. L'implémentation est exactement la même que ci-dessus, vous remplacez simplement le nom de votre structure de données par le type requis.
(defpat ajoute( [integer_ x] [integer_ y] )
(+ x y)
)
(ajoute 10 20) ; est valable
(ajoute 10 'x) ; n'est pas valide
Il est en fait possible de forcer un argument à correspondre à une fonction par motif via un appel à une fonction qui renverra soit "true" soit "nil".
En particulier, on peut vouloir vérifier une expression régulière sur un argument pour déclencher l'exécution d'une fonction.
Encore une fois, le formalisme est le même que ci-dessus, nous remplaçons simplement le type de données par un appel de fonction.
IMPORTANT Quand on utilise une fonction par motif, l'argument doit toujours être le dernier paramètre dans la description d'un paramètre. Si votre test nécessite un ordre différent, vous pouvez utiliser flip.
; Cette méthode compare deux éléments dans une liste
(defun moinsque (x) (< (car x) (cadr x))
; Cette fonction vérifie que le premier argument est conforme
; à l'expression régulière : \d\d (deux chiffres)
(defpat action ( [prgx `\d\d` x] u)
(println 'ok u)
)
; Cette fonction vérifie que le premier argument est conforme
; à l'expression régulière : %a+ (une séquence de caractères alphabétiques)
(defpat action ( [rgx `%a+` x] u)
(println 'Alpha u)
)
; Cette fonction permet de vérifier si la liste x est conforme à la
; définition de moinsque
(defpat action ( [moinsque x] u)
(println 'Yooo u)
)
; Ces trois appels fonctionnent
(action '(200 220) 'première)
(action "12" "enfin")
(action "Test" "bon")
; celui-ci échoue: 280 > 220
(action '(280 220) 'première)L'exemple suivant montre un cas où la comparaison n'est pas dans le bon ordre :
; Nous utilisons flip pour mettre les arguments dans le bon ordre
(defpat parcours ( [string_ (flip (in 'restaurant s))] )
(println 'ok s)
)
(defpat parcours ( [string_ s] )
(println "Pas de restaurant")
)
(parcours "la ville contient un bon restaurant italien")Note: Une remarque importante doit être faite sur l'exemple ci-dessus. Lorsque vous définissez une fonction par motif, le type du premier élément de la définition est utilisé comme clé pour accéder à ces fonctions. Ce type doit être soit un type de base (integer_, string_ list_ etc.), soit un type de structure de données, sinon il est nul. Si nous supprimons la définition "string_" dans la première fonction, elle sera considérée comme une fonction de repli, qui sera alors indexée sur "nil". En mettant cette contrainte, nous ajoutons cette première fonction à la liste des fonctions qui peuvent s'appliquer à une chaîne de caractères
Il est bien sûr possible de faire correspondre une structure avec des dictionnaires et des listes.
; Avec des dictionnaires
(defpat tst({"12":y x:y})
(println x y)
)
; Cet appel affichera : bidule et machine
; Le "12" déclenche l'unification de 'y' avec "machine"
; et seul le mot "bidule" en tant que clé correspond à la valeur de "machine
(tst {"12" : "machine" "truc" : "machin" "bidule" : "machine"})
Il est notamment possible d'utiliser l'opérateur "$" pour effectuer une comparaison avec des sous-listes. Cet opérateur est utilisé dans une définition de paramètre. Il essaie de faire correspondre la partie gauche de la liste de paramètres avec l'argument de liste. Le reste de la liste est ensuite stocké dans la variable finale, comme le montre le code suivant :
; 1. "z" est le reste de la liste
(defpat tst ( [x y $ z] )
(println x y z)
)
; 2. la liste ne doit contenir qu'un seul élément
(defpat tst ((x))
(println 'unique x)
)
; 3. comparaison avec la liste vide
(defpat tst ( ( ))
(println 'vide)
)
(tst ()) ; déclenche 3. et affiche vide
(tst '(1 2 3 4 5)) ; déclenche 1. et affiche : 1 2 (3 4 5)
(tst '(1 2)) ; déclenche 1. et affiche : 1 2 ()
(tst '(1)) ; déclenche 2. et affiche : unique 1L'opérateur "$" peut également être utilisé avec des dictionnaires. Cependant, dans ce cas, il est considéré comme une "clé".
; Le $ est suivi du :
(defpat tst({_:y _:y $:z})
(println y z)
)
(setq d {"12" : "machine" "truc" : "machin" "bidule" : "machine"})
; affiche : machine {"truc" : "machin"}
(tst d)