Design Patterns : Saison 2
Design Patterns are signs of weakness in programming languages -- Mark Dominus
Our patterns assume Smalltalk/C++-level language features, and that choice determines what can and cannot be implemented easily -- Design Patterns, Gang Of Four
Face aux lacunes de chaque langage, les programmeurs ont inventé des mécanismes réutilisables pour faire face à un certain nombre de problèmes récurrents. Au travers de plusieurs exemples concrets, cet article va montrer comment un programmeur peut rendre son code plus compact en choisissant un langage de programmation qui ne souffre pas des mêmes problèmes.
Un peu d'histoire
En langage machine et en assembleur, la fonction n'existait pas. Des conventions d'appel bas niveau furent découvertes, intégrées dans des macros assembleur, puis rendue systématique dans tous les langages procéduraux. La fonction fut l'un des premiers Design Patterns.
Les programmeurs C furent ensuite confrontés à un problème similaire: leurs structures contenaient fréquemment d'autres structures, accompagnées de routines spécialisées. Ils faisaient de la programmation objet avant l'heure, avant que le C++ ne leur offre une structure plus formelle.
Aujourd'hui les Design Patterns les plus célèbres tournent autour des langages à objets.
Cet article va revisiter plusieurs design patterns classiques du développement orienté objet, et proposer pour chacun d'entre eux un équivalent simple et instructif dans le langage techniques de parallélisation.
Les exemples resteront assez simples, car la plupart des patterns "objet" deviennent transparents lorsque le langage utilisé propose un certain nombre d'outils. Parmi ces outils on utilisera en particulier:
- Des fonctions de haut niveau: fonctions qui prennent en paramètre une ou plusieurs autres fonctions,
- Des types algébriques : types de données abstraits qui se déclinent en plusieurs types concrets, chacun avec des champs propres
- Le pattern matching : Un mécanisme de dispatch agrémenté de sucre syntaxique
Ces exemples seront aussi instructifs. Ils permettront de rappeler la philosophie de ces design patterns, tout en permettant à ceux qui le souhaitent de réaliser un premier pas dans le monde de la programmation fonctionnelle.
Quelques éléments de syntaxe du langage Haskell
Ces trois éléments de syntaxe devraient permettre au lecteur de survivre jusqu'à la fin de l'article. Ils ne concernent pas les patterns directement.
Définition d’un type algébrique. Un Personnage peut être un humain, un troll ou un nain . Chaque type de personnage contient deux champs. L’annotation 'deriving (Show)' définit un pretty-print basique (fonctions print et show, qui sérialisent les objets d'une manière lisible pour l'humain). Le pipe (|) introduit un nouveau type concret. L'opérateur deux-points (::) indique les types des champs.
data Character = Human {name :: String, strength :: Int}
| Troll {name :: String, strength :: Int}
| Dwarf {name :: String, strength :: Int}
deriving (Show)
gimli = Dwarf "Gimli" 20
Appel de la fonction print sur l'objet gimli (la ligne de résultat commence par >>> ):
print gimli
>>> Dwarf {name = "Gimli", strength = 20}
Définition d'une fonction simple. La première ligne définit son prototype (entier vers entier) grâce à l'opérateur '::' . La deuxième ligne définit son corps (multiplication par deux).
double :: Int -> Int
double x = x * 2
Usage d’une fonction de haut niveau, fmap (comme le map de map/reduce) :
fmap double [1,2,3,4]
>>> [2,4,6,8]
fmap (\x -> x*2) [1,2,3,4]
>>> [2,4,6,8]
fmap (*2) [1,2,3,4]
>>> [2,4,6,8]
fmap applique une fonction à chaque élément d'une liste, et retourne une nouvelle liste.
La troisième fonction, (*2), donne un exemple de currying. La fonction de multiplication (*) n'a reçu que son deuxième argument (2), et le résultat est une nouvelle fonction (d'un seul argument) qui multiplie par deux. Cette fonction est strictement équivalente à (\x -> x*2). Le currying est un élément de syntaxe pratique qui permet de définir une fonction anonyme sans utiliser la notation lambda.
Pattern Itérateur
Objectif : Traverser un conteneur Équivalent fonctionnel: Liste paresseuse, puis usage de fonctions de haut niveau (avec currying) pour les transformations
L'itération sur des listes est une opération transparente en Haskell. Pour aller au delà d'une simple itération, nous allons calculer par exemple la somme des trois premiers nombres carrés qui valent plus de 100. Ces trois lignes de code vont introduire plusieurs concepts nouveaux qui seront expliqués au moment opportun.
Première étape: déclaration d'une liste d'entiers assez grande. Pour être plus économe en mémoire, Haskell ne va pas l'allouer entièrement avant son utilisation. Au lieu de cela, ses éléments seront générés un à un pour la fonction qui les consomme : c'est une liste "paresseuse" (pour les curieux : il est même possible de définir une liste infinie [1..] qui aura exactement le même comportement).
let list = [1..10000000]
Voici la fonction fct qui va réaliser le calcul. Il faut lire cette définition de droite à gauche, chaque point indiquant une composition de fonction: on commence par appliquer map, et on finit par sum.
fct = sum . take 3 . filter (> 100) . map (\x -> x*x)
Et le résultat :
print (fct list)
>>> 434
Explications complémentaires:
- map (\x -> x*x) calcule le carré de chaque élément reçu
- (> 100) est une fonction anonyme qui retourne True pour tout entier supérieur à 100. Cette notation est une forme de currying car la fonction > ne reçoit pas immédiatement tous ses paramètres
- filter ne laisse passer que les éléments qui répondent à son prédicat : (> 100)
- take 3 demande des éléments à une liste paresseuse, un par un, et arrête de demander après trois éléments. Voilà un deuxième exemple de currying: seul le premier paramètre (3) est fourni.
- Enfin, sum reçoit ses trois entiers et réalise la somme finale
Ce calcul fonctionne un peu comme une commande shell avec des pipes. Chaque élément de la liste est passé à l'étape suivante, sans jamais stagner en mémoire. Il est quasiment optimal en terme de consommation mémoire et en terme de vitesse (à chaque instant de l'exécution de fct, les fonctions sum et take 3 auront instancié respectivement un accumulateur et un compteur, et un seul entier de list existera dans le reste de la fonction).
Pour être rigoureux avec le pattern itérateur, il faudrait que la liste d'entrée soit une liste d'objets plus complexes. Pour répondre à ce problème il suffirait alors d'ajouter le getter adéquat au début du pipe.
fct2 = fct . map getAccountCredit
print (fct2 accounts)
Pattern Stratégie
Objectif : Appliquer une famille d'algorithmes interchangeables Équivalent fonctionnel : Une fonction de haut niveau. L’algorithme choisi est alors la fonction passée en paramètre
On dispose de trois fonctions de tri (bubbleSort, quickSort et mergeSort). Ces trois fonctions possèdent le même prototype et le même usage :
- Je prends en entrée une liste mono-typée (type [a])
- Je retourne une liste du même type
- Le type 'a' doit être Ordonnable
-- Prototypes des 3 fonctions
bubbleSort :: (Ord a) => [a] -> [a]
quickSort :: (Ord a) => [a] -> [a]
mergeSort :: (Ord a) => [a] -> [a]
Et maintenant, le coeur de la Stratégie: sortWith est une fonction de haut niveau, qui prend en paramètres sortingFunction et mylist :
- sortingFunction pointe vers une fonction trieuse
- mylist est la liste à trier, de type [a]
sortWith :: (Ord a) => ([a] -> [a]) -> [a] -> [a]
sortWith sortingFunction mylist = sortingFunction mylist
print (sortWith quickSort [1,2,5,3])
>>> [1,2,3,5]
print (sortWith bubbleSort [1,2,5,3])
>>> [1,2,3,5]
Pattern Visiteur
Objectif : Séparer un algorithme de la structure sur laquelle il travaille Équivalent fonctionnel : Une fonction de haut niveau (ici: fmap)
On redéfinit une structure d'arbre simple. Un nœud est soit une feuille, soit une branche qui contient une liste de nœuds :
data Tree a = Leaf a | Branch [Tree a]
deriving (Show)
En définissant la fonction générique fmap pour la structure Tree, on définit comment "mapper" une fonction sur un arbre :
- Appliquer la fonction à chaque feuille
- Renvoyer un nouvel arbre de même structure
instance Functor Tree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Branch trees) = Branch (fmap (fmap f) trees)
(fmap f) est une fonction (currying), mappée sur tous les trees.
On instancie un arbre et une liste aux contenus similaires :
tree = Branch [Leaf "Feuille1",
Branch [Leaf "Feuille2",Leaf "Feuille3"]]
list = ["Feuille1", "Feuille2", "Feuille3"]
Application de la même fonction length aux deux structures (liste et arbre). length est appliquée sur chaque String :
print (fmap length tree)
>>> Branch [Leaf 8,Branch [Leaf 8,Leaf 8]]
print (fmap length list)
>>> [8,8,8]
En Haskell, une fonction telle que length n'a pas besoin de connaitre la collection sur laquelle elle va travailler. Les amateurs d'algèbre linéaire reconnaitront que fmap length est un homomorphisme: il préserve la structure et transforme le contenu.
fmap fonctionne sur tous les conteneurs du langage, et sur d'autres types plus abstraits, tout en étant rigoureux sur les types mis en jeu.
Pattern Interpréteur
Objectif : Évaluer une expression sous la forme d'un arbre syntaxique Équivalent fonctionnel : Type algébrique et pattern matching
Une expression peut être soit un entier, soit une addition, soit une soustraction. Elle est naturellement représentée par un type algébrique :
data Expr a = EInt Int
| Plus (Expr a) (Expr a)
| Minus (Expr a) (Expr a)
La fonction d'évaluation eval prend un arbre syntaxique et renvoie un entier :
eval :: Expr a -> Int
eval (EInt i) = i
eval (Plus a b) = eval a + eval b
eval (Minus a b) = eval a - eval b
Exemple de calcul: 3+(6-4) :
result = eval (Plus (EInt 3)
(Minus (EInt 6) (EInt 4)))
print result
>>> 5
Pratique pour implémenter un petit moteur de règles! En bonus, le type Expr implémente très clairement le pattern Composite, tout comme le type Tree défini plus haut.
Pattern Commande
Objectif : Encapsuler les détails d'une action pour l'exécuter plus tard Équivalent fonctionnel : Un type algébrique et pattern matching
Commandes réifiées et représentées par un type algébrique :
import Control.Concurrent (forkIO)
import Control.Concurrent.Chan
data Action = TurnOn | TurnOff | SetTemperature Int
deriving (Show)
Donnons un exemple d'état à modifier: l'état d'un climatiseur (On/Off et température)
data State = State {turnedOn :: Bool, temperature :: Int}
deriving (Show)
Et maintenant on peut envoyer ces commandes, via n'importe quel mécanisme. Exemple d'envoi sur une queue de message (appels à writeChan) :
main :: IO()
main = do
queue <- newChan
forkIO (listener (State False 19) queue) -- lancer le listener
writeChan queue TurnOn -- Premiere commande
writeChan queue (SetTemperature 23) -- Deuxieme commande
>>> Commande : TurnOn
>>> -> State {turnedOn = True, temperature = 19}
>>> Commande : SetTemperature 23
>>> -> State {turnedOn = True, temperature = 23}
Pour rendre cet exemple auto-portant, il faudrait encore définir la fonction listener (lecture facultative):
listener :: State -> Chan Action -> IO()
listener state queue = do
command <- readChan queue
let newState = case command of
TurnOn -> state {turnedOn = True}
TurnOff -> state {turnedOn = False}
SetTemperature t -> state {temperature = t}
print ("Commande : " ++ show command)
print (" -> " ++ show newState)
listener newState queue
Un autre exemple, plus idiomatique en Haskell, serait simplement :
action = print "toto"
Il s'agit d'une action réifiée et placée dans la variable action, exécutable maintenant ou plus tard, dans ce thread ou ailleurs.
Conclusions
Les langages de programmation tendent à devenir de plus en plus expressifs. L'un des mécanismes de cette évolution consiste à identifier dans les langages mûrs les idiomes les plus répétitifs, puis à intégrer de nouveaux outils dans des langages de la génération suivante, qui rendront ces répétitions inutiles.
En l'occurrence, on a vu comment plusieurs patterns du monde orienté-objet peuvent disparaitre. Peter Norvig a remarqué que 16 patterns sur les 23 du GoF disparaissent en Lisp/Dylan, et Edward Yang a montré que la totalité disparait en Haskell. Cette évolution existe aussi chez des langages plus mainstream: Clojure est un Lisp, Scala fournit le pattern matching, les types algébriques et les fonctions de haut niveau. Les closures sont introduites dans Java 8, et même C++ est en train de recevoir des composantes fonctionnelles.
Le résultat de cette évolution: un code concis et bien typé, qui indique plus clairement l'intention du programmeur. On remarque aussi un excellent découplage entre les structures de données et les processus qui les utilisent. Ce découplage est positif pour l'écriture de tests, la maintenance et la réutilisabilité.
Une conséquence de ce découplage concerne les frameworks de développement. Il n'existe pas de framework en Haskell, car leur mécanisme de base, l'inversion de contrôle, est rendu obsolète par les fonctions de haut niveau et l'évaluation paresseuse. Dans tous les langages qui possèdent ces deux outils, les inconvénients des frameworks (courbe d'apprentissage, rigidité, obsolescence, ...) disparaissent au profit d'une collection de librairies simples et réutilisables. Bye bye Spring!
Il existe bien sûr d'autres patterns, plus abstraits, en Haskell et dans le monde fonctionnel : foncteurs, monades, monades applicatives… Ces patterns font l'objet de recherche actuellement. Ils seront probablement mieux compris et intégrés dans une prochaine vague de langages de programmation.
Sources :
Mark Dominus : Exemple de design pattern en C, intégré en C++ avec l'arrivée des classes. Réflexion générale sur l'évolution des langages de programmation blog.plover.com/2006/09/11
Peter Norvig : Design Patterns in Dynamic Programming www.norvig.com/design-patterns
Edward Z. Yang : Liste complète des patterns du GoF en Haskell blog.ezyang.com/2010/05/design-patterns-in-haskel
Wikipedia: Les macros assembleur fr.wikipedia.org/wiki/Assembleur#Macro-assembleur
Axel-Tobias Schreiner: Les patterns objet en C www.cs.rit.edu/~ats/books/ooc.pdf
Paul Graham: Réflexion sur la différence d'expressivité des langages de programmation (section "The Blub Paradox") www.paulgraham.com/avg.html
Tutorial Haskell http://learnyouahaskell.com