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.
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>. |
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 :
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.
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.
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 :
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.
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>();
}
|
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[]; }
public class Stack<String> { public void push(String object) { tab[top++]=object; } ... int top=0; String tab[]; }
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(); }
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 :
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
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écution
class 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 compilateur
int oldValue(Ref<int> ref) { return ref.setValue(new Integer(3)).intValue(); }
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 :
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.