- Menu
- Modeles
- Menu
- Version Java2
- Version Java5
- Version Haskell
- Version Python
- Version Bytecode
Le pattern Visiteur décrit (dans le langage Java) précédemment est une solution (insatisfaisante) orientée-objet au problème fréquent du parcours générique de structure de données. On souhaite pouvoir appliquer un traitement (méthode, fonction) à certains éléments d'une structure, le traitement étant indépendant de la structure. Dans la plupart des cas, la taille du code nécessaire au parcours de la structure est plus importante que le code du traitement proprement dit.
Ce code est appelé boilerplate code et S.Peyton-Jones et Ralf Lämmel ont développé une technique de programmation fonctionnelle dans le langage Haskell pour réduire ce code à sa plus simple expression. Les deux ingrédients principaux de cette approche sont les classes Typeable et Term (appelée aussi Data dans les versions suivantes).
"Scrap your boilerplate"
La classe de type Typeable définit des opérations réflexives sur les type Haskell et permet d'obtenir une représentation du type à l'exécution. Ces fonctionnalités sont courramment disponibles dans les langages objets grâce à l'existence de méta-classes assurant la représentation à l'exécution des classes des objets. Plus les langages sont dynamiques (Smalltalk, Python , Ruby), plus l'information disponible est importante et permet de faire de la méta-programmation. Dans le cas de Java (et probablement de C#), la représentation des classes est essentiellement figée à l'exécution: les possibilités de méta-programmation offertes sont relativement limitées dans la boîte à outil de base du programmeur.
-- | The class 'Typeable' allows a concrete representation of a type to -- be calculated. class Typeable a where typeOf :: a -> TypeRep
La deuxiéme classe, Data est plus originale: elle définit des opérations génériques de parcours des instances de types: gmapT, gmapQ et gmapM. Chacune de ces fonctions applique une opération (d'où map) sur les sous-termes immédiats d'un noeud représentant une instance de type:
- gmapT décrit une transformation sur ce terme,
- gmapQ décrit une requête
- gmapM décrit une opération monadique (eg. opérations d'entrée/sortie sur le type en question).
previous class Typeable a => Data a where -- | A generic transformation that maps over the immediate subterms gmapT :: (forall b. Data b => b -> b) -> a -> a -- | A generic query that processes the immediate subterms and returns a list gmapQ :: (forall a. Data a => a -> u) -> a -> [u] -- | A generic monadic transformation that maps over the immediate subterms gmapM :: Monad m => (forall a. Data a => a -> m a) -> a -> m a
Ces opérations sont réductibles à un combinateur racine intitulé gfoldl (pour generic left fold) dont le typage est extrêmement abscons eit qu'il est préférable de laisser dans l'ombre.
previous -- | Left-associative fold operation for constructor applications gfoldl :: (forall a b. Data a => c (a -> b) -> a -> c b) -> (forall g. g -> c g) -> a -> c a
À partir de ces combinateurs de bases, on peut définir des fonctions parcourant l'ensemble d'une structure de donnée et, soit la transformant, soit produisant un résultat à partir des valeurs de la structure, en séparant clairement le parcours de la structure des opérations effectives sur les noeuds de cette structure. Les principaux combinateurs sont décrits succintement ci-dessous.
previous module Data.Generics.Schemes where -- parcours de l'arbre et application des feuilles a la racine everywhere :: (forall a . Data a => a -> a) -> forall a . Data a => a -> a -- parcours et application de la racine aux feuilles everywhere' :: (forall a . Data a => a -> a) -> forall a . Data a => a -> a -- parcours conditionel avec predicat generique pour filtrer everywhereBut :: GenericQ Bool -> GenericT -> GenericT -- .... {- fonctions generiques: taille de la structure, profondeur, nombre de noeuds satisfaisant un predicat... -} gsize :: Data a => a -> Int glength :: GenericQ Int gdepth :: GenericQ Int gcount :: GenericQ Bool -> GenericQ Int -- ...
En résumé, on a donc bien mis en oeuvre des méthodes génériques pour:
- d'une part, parcourir un noeud de l'arbre formé par une structure de données;
- d'autre part, appliquer une fonction à l'ensemble des noeuds d'un parcours.
Pour ce faire, il est nécessaire de disposer:
- d'une connaissance des types à l'exécution (RTTI) suffisamment réflexive pour décrire la structure d'une instance d'objet en détail et permettre le parcours de ses composants en définissants des méthodes typées ;
- de stratégies de parcours, sous forme de fonctione génériques s'appliquant sur n'importe quelle structure supportant le point 1.
Ce schéma est aisément transposable dans l'univers des langages orientés-objets, et l'a d'ailleurs été sous diverses formes, par exemple celle du Baladeur utilisant les mécanismes d'introspection de Java (voir Baladeur).
Dans les langage dynamiques, la mise en oeuvre de ce schéma est facilitée par la possibilité d'évaluer dynamiquement des expressions chaînes et donc de définir des fonctions et objets à l'exécution (voir cette approche en Python).
References
Scrap your boilerplate with class