Les templates du C++ ou les modules génériques d'ADA sont des
mécanismes qui permettent de définir des classes (resp. modules) qui
sont paramètrées par des types, ces classes sont dites polymorphes. Grâce
au template il est est possible, par exemple, de définir une classe
pile indépendante du type des objets stockés. Un mécanisme d'instanciation
permet ensuite de spécaliser cette classe en fonction du type des objets
stockés.
En Java, il n'existe pas de mécanisme équivalent aux
templates.
En effet, Java a fait un choix différent (inspiré de Smalltalk) basé sur
le fait que toutes les classes héritent obligatoirement de la classe
Object. Ainsi,
pour simuler une classe pile paramètrée par le type des éléments, le
sous-typage est utilisé.
Celui-ci consiste à spécifier une pile d'Object, et comme tout
objet est de la classe Object
(grâce à l'héritage) il peut être placé dans la pile.
La différence fondamentale entre ces deux approches est qu'un
template de pile permet de générer n'importe quelle pile,
alors qu'une pile d'Object est une pile de n'importe quoi.
Le principale avantage des templates est qu'il n'y a pas perte de
l'information de type. Ce n'est pas le cas avec le sous-typage.
Par exemple, les objets stockés dans les classes conteneurs Vector
ou Hashtable de Java sont manipulés en tant qu'Object.
Pour pouvoir utiliser ces objets après le stockage, il est nécessaire
de les promouvoir dans leur type d'origine, ce qui entraîne un
surcoût à l'exécution et un travail inutile
de la part du programmeur (il doit écrire explicitement tous les
transtypages). La contrepartie est que dans le cas des templates une
classe est générée pour chaque instanciation alors que dans le cas de Java
une seule classe est nécessaire.
| Exemple d'un code d'utilisation d'une pile générique en Java utilisant le sous-typage. |
Stack stack=new Stack();
stack.push("the Quick and the Dead");
...
Iterator it=stack.iterator();
for(;it.hasNext();)
System.out.println(((String)it.next()).substring(9));
|
| Exemple d'un code d'utilisation d'une pile générique utilisant un template. |
Stack<String> stack=new Stack<String>();
stack.push("the Quick and the Dead");
...
Iterator<String> it=stack.iterator();
for(;it.hasNext();)
System.out.println(it.next().substring(9));
|
Dans un premier temps, je vais présenter quelques aspects et
problèmes susceptibles d'être rencontré lors d'une implémentation des
templates en Java.
Puis je présenterai diverses implémentations possibles avec
leurs avantages et leurs inconvénients.
Enfin, j'expliquerai une proposition d'implémentation faisant
la synthèse des idées de la partie précédente suivi des problèmes ou
solutions que cette proposition entrainera.
En C++, il n'y a aucune contrainte sur le type des paramètres,
le compilateur ne peut donc pas vérifier la validité des opérations
effectuées sur les paramètres du template.
Tant qu'un template n'a pas été instancié pour un type
particulier, il n'est donc pas possible de savoir si les méthodes de la
classe résultante sont valides.
Ceci est en contradiction avec le typage statique fort
qui garantit la sureté du code en Java.
- Typage des paramètres du template
Une solution élégante à ce problème consiste à typer les paramètres en obligeant à ce qu'un argument ne soit valide que si c'est un sous-type du type du paramètre. Ceci permet de déterminer statiquement la validité d'un template.
Exemple de contraintes de type :class Sorter<Object key1,String key2>1 { ... } Sorter<Object,Object> // illégal, Object n'hérite pas de String Sorter<Object,String> // légal Sorter<String,String> // légal, String hérite de Object Sorter<Integer,Integer> // illégal, Integer n'hérite pas de String Sorter<int,String> // illégal, int est un type primitif, // il n'hérite pas de Object
1. Une syntaxe équivalente est : class Sorter<key1 extends Object, key2 extends String>. - Les types primitifs
La solution précédente pose un problème avec les types primitifs (int, boolean, etc...), en effet, comment spécifier le fait que des types primitifs puissent être argument d'un template. Une solution pour résoudre ce problème est d'utiliser deux mots-clef supplémentaires :
- type
- pour indiquer que le paramètre peut prendre n'importe quel type primitif ou classe, les deux seules opératations valides sur un objet de ce type étant l'assignation et le test d'égalité.
- number
- le paramètre pouvant prendre alors les types : byte, char, double, float, int, long, short. Les opérations possibles étant l'assignation, l'addition, la multiplication etc...
Voici un exemple utilisant le mot-clef number :
class Sum<number Value> { abstract Value f(Value value); Value sum(Value debut,Value fin) { Value res=0; for(Value i=debut;i<=fin;i+=1) res+=f(i); return res; } }Pour une implémentation possible des types primitifs, voir paragraphe V.b. - Limitation lors de l'écriture du code d'un template
Un argument du template, peut être n'importe quelle classe qui est un sous-type du type paramètre du template. Ceci interdit donc certaines constructions qui seraient valides si le type argument était exactement le type paramètre. Dans l'exemple ci-dessous à gauche, si Item est Object, le code est valide mais si Item est un hérite de Object, par exemple Integer, le code n'est plus valide.
class Ref<Object Item> { Item get(int i) { if (i<0) // illégal return "no value"; else return items[i]; } Item items[]; }class Ref<Object Item> { Item get(int i) { if (i<0) // légal return (Item)(Object)"no value"; else return items[i]; } Item items[]; }Le code ci-dessus à droite est lui valide, mais peut entrainer une exception à l'exécution lors du transtypage de Object vers Item. En effet, si l'argument du template est Integer pour i est inférieur à zéro, la machine virtuelle Java va essayer de transtyper un objet de type String en Integer ce qui provoquera automatiquement une exception.
Pour garantir statiquement la validité du code, il est nécessaire d'interdire le code de gauche. Ceci est mis en oeuvre par une vérification de type simple.
- La spécialisation de méthodes
Le but de la spécialisation est de permettre à l'utilisateur de spécifier plusieurs codes pour une méthode donnée en fonctions du type des arguments du template.
Lors de l'instanciation du template, la méthode la plus précise suivant les arguments d'instanciation sera choisie parmi les méthodes ayant la même signature2. A la différence de la surdéfinition de méthode (cf [GLS96]), les autres méthodes ne figureront pas à l'interieur de la classe instanciée.
Ainsi, il est possible de définir deux types de méthodes :- les méthodes génériques
- ce sont des méthodes contenant un paramètre du template dans leur signature. Elles seront utilisées comme méthodes par défaut.
- les méthodes spécialisée
- ce sont les méthodes qui précisent une méthode générique en fonction d'arguments du template. Elles possèdent une classe3 à la place du paramètre du template dans leur signature. Elles sont utilisées que lors d'une instantiation du template avec pour argument la classe pré-citée, ou une de ses classes dérivées.
Exemple :
class Assoc<Object Key,Object Value> { // méthode générique Value get(Key key) { return hash.get(key); } // méthode spécialisée Value get(String key) { return null; } Hash<Key,Value> hash=new Hash<Key,Value>(); }La classe Assoc<String, Object> aura pour seule méthode get(String) la méthode spécialisée, tandis que la classe Assoc<Object, Object> aura pour méthode get(Object) la méthode générique.
Le code ci-dessous correspond au code des deux classes instantiées :class Assoc<String,Object> { // méthode spécialisée Object get(String key) { return null; } Hash<String, Object> hash= new Hash<String, Object>(); }class Assoc<Object,Object> { // méthode générique Object get(Object key) { return hash.get(key); } Hash<Object,Object> hash= new Hash<Object,Object>(); }
- Instanciation statique
Cette méthode [D97] est celle qui ressemble le plus à l'approche du C++, pendant l'étape de compilation, si le compilateur trouve une instanciation du template (Stack<String> par exemple) il génère automatiquement la classe en remplaçant dans le code source Java de la classe Stack toutes les références au paramètre d'instanciation par String.
Voici un exemple d'une classe écrite sous forme de template.
public class Stack<Item> { public void push(Item object) { tab[top++]=object; } ... int top=0; Item tab[]; }
Et le code résultant d'une une instanciation possible, ici avec la classe String, par la méthode expliquée ci-dessus.public class Stack<String> { public void push(String object) { tab[top++]=object; } ... int top=0; String tab[]; }
Cette implémentation possède un inconvénient majeur, elle crée statiquement une classe par instanciation du template ce qui pour une applet ou une application distribuée peut engendrer des temps de chargement plus long.
Par contre, elle permet facilement d'utiliser les types primitifs comme paramètres d'un template car l'instanciation s'effectue pendant la compilation. - Transtypage automatique
La méthode implémentée dans GJ [BOSW98] automatise la façon habituelle de créer et d'utiliser des classes génériques en Java.
class Ref<Item> { Item getValue() { return value; } Item value; } String f(Ref<String> ref) { return ref.getValue(); }Le compilateur remplace les paramètres du template par Object (ou par l'interface choisie) dans la classe générique, et effectue les transtypages appropriés lors d'appel aux méthodes ou aux attributs de la classe générique.
class Ref { Object getValue() { return value; } Object value; } String f(Ref ref) { return (String)ref.getValue(); }
Cette implémentation a l'avantage de ne pas générer trop de classes contrairement à l'implémentation précédente. Mais elle ne supprime pas l'éxécution de transtypages inutiles mème si le programmeur ne doit plus les écrire explicitement. - Instanciation dynamique
Comme son nom l'indique, cette implémentation [AFM97] instancie les templates de façon dynamique. Ici, le template est converti en une classe dite générique, que l'on peut se représenter comme étant une classe normale (du byte-code) avec des trous correspondant aux paramètres d'instanciation plus des informations sur le type de ces paramètres.
Le compilateur vérifie que lors de l'instanciation, les paramètres possèdent le bon type mais il ne crée pas les classes instanciées.
En effet, lors de l'exécution du programme, on ajoute un classloader (mécanisme en Java qui permet le chargement de classes) spécifique qui instanciera le template, pour cela il remplacera partout dans la classe générique correspondant au template, les paramètres de type par leur valeur.Cette implémentation permet de limiter le nombre de classes nécessaires à l'exécution du programme, les classes instanciées n'étant crées que pendant une exécution.
Ceci par contre entraîne un temps de chargement plus long, il faut en effet rajouter le temps d'instanciation de la classe, pour cela, la classe générique devra être écrite pour que l'étape d'instanciation soit la plus rapide possible.
Dans l'implémentation proposée par Agresen, Freund et Mitchell, [AFM97], la classe générique ne possède pas le même format qu'une classe Java normale, ceci empèche une compatibilité totale avec le JDK déja existant. Un programme utilisant la classe Stack sous forme de template ne pourra utiliser des parties de librarie déjà écrites qui utilise la version actuelle de la classe Stack.
Des différentes solutions proposées, l'instanciation dynamique est la meilleur, elle permet en effet, de posséder de réel template sans avoir une explosion du nombre de classe à fournir pour le fonctionnement d'un programme.
Dans le but d'améliorer l'implémentation utilisant l'instanciation dynamique des templates, voici quelques propositions :
- Assurer la compatibilité avec le Java standart
Pour cela, il faut que la classe correspondant au template (i.e la classe générique) soit au même format qu'une classe Java classique, le byte-code doit être compatible.
Un des bits du champ nommé access_flags disponible dans le byte-code d'une classe Java peut être utilisé pour indiquer que la classe est générique. Les informations nécessaires à l'instanciation du template devront être stockées sous forme d'attributes, champs d'extension prévus dans le format du byte-code Java voir [lY96].
La classe générique Stack possèdera donc, en plus du même byte-code que la classe Stack du JDK, les informations permettant l'instanciation de la classe générique.
spécification du format d'une classe générique
- Intégrer des types primitifs
En Java, chaque type primitif (int, char, boolean etc...) possède un objet associé (respectivement Integer, Character, Boolean), ces objets possèdent des méthodes qui permettent de convertir un type primitif en son objet équivalent et vice et versa.
Ceci permet d'utiliser les types primitifs avec les templates, le compilateur se chargera de rajouter les appels aux methodes de conversion.
Un exemple de code écrit avec un template :class Ref<Item> { Item setValue(Item val) { Item old=value; value=val; return old; } Item value; } int oldValue(Ref<int> ref) { return ref.setValue(3); }Et le code Java correspondant au byte-code de la version générée par le classloader pendant l'exécutionclass Ref<Integer> { Integer setValue(Integer val) { Integer old=value; value=val; return old; } Integer value; }Et le code d'appel généré par le compilateurint oldValue(Ref<int> ref) { return ref.setValue(new Integer(3)).intValue(); }
Attention, ceci ne permet pas de relacher la contrainte sur le type des paramètres des templates, on ne pourra appliquer sur le type Item que les opérations applicables sur une classe dérivant de Object. - API permettant l'instanciation partielle et dynamique de template
Un des concepts importants en Java est la réflexivité, c'est ce mécanisme qui permet par exemple d'appeler dynamiquement une méthode d'après son nom. En effet, une classe en Java est capable grâce aux méthodes de la classe java.lang.Class de connaître tous les attributs, les méthodes, les constructeurs etc... qu'elle possède.
Pour qu'un programmateur puisse utiliser dynamiquement les templates quatre méthodes doivent être ajoutées à la classe java.lang.Class :- la méthode isGeneric()
- permet de savoir si une classe est générique ou non.
- la méthode getGenericClass()
- permet de récupérer la classe générique à partir d'une classe instanciée. (si la classe est Stack<String>, la classe générique correspondante est Stack)
- la méthode getTemplateParametersType()
- qui dans le cas d'une classe générique renvoie le type des paramètres d'instanciation du template.
- la méthode instantiate()
- permet d'instancier un template en passant en paramètre les différents arguments d'instanciation.
méthodes à rajouter à la classe java.lang.Class
Instanciation partielle
Cette API propose aussi un mécanisme d'instanciation partielle, qui permet d'instancier une classe générique seulement sur certain paramètres.
La classe instanciée partiellement reste une classe générique tant qu'il reste des paramètres.
Lors de la création d'instance d'une classe générique, on utilisera le type des paramètres pour les arguments non définis. Une instance de la classe Stack sera donc équivalente à une instance de la classe Stack<Object>.
Ce mécanisme est à rapprocher du mécanisme de fermeture des langages fonctionnelles qui permet l'instanciation partielle de fonctions.
Le mécanisme des templates est un mécanisme important et utile qui ne fait pas pour l'instant partie de la norme Java. Nous avons vu qu'il existait déjà un certain nombre de spécifications proposées qui ont chacune leurs avantages. Nous proposons ici une spécification pour les templates qui tire partie de ces observations et qui ajoute un certain nombre de caractéristiques intéressantes, une intégration facile des types primitifs, une compatibilité avec les classes Java standart, une API pour la réflexivité et pour l'instanciation partielle des templates.