Des Templates en Java

Résumé
La programmation par template est un mécanisme important que l'on retrouve dans de nombreux langages objets mais qui manque encore à Java. Depuis un an, plusieurs implémentations ont été proposées pour intégrer ce mécanisme à Java. Quel est l'intérêt des templates ? Quelles sont les problèmes posés et les solutions proposées ?

Par Rémi Forax

  1. Pourquoi des templates en Java
  2. 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.

  3. Du typage des templates
  4. 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.

    1. Typage des paramètres du template
    2. 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>.

    3. Les types primitifs
    4. 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.

    5. Limitation lors de l'écriture du code d'un template
    6. 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.

    7. La spécialisation de méthodes
    8. 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>();
        }
              

      2. La signature d'une méthode correspond à la liste des paramètres d'appel de la méthode,
      le type de retour ne fait pas partie de la signature.
      3. Cette classe devra hériter du (ou implémenter le) type du paramètre du template.

  5. Les différentes solutions proposées
    1. Instanciation statique
    2. 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.

    3. Transtypage automatique
    4. 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.

    5. Instanciation dynamique
    6. Schéma du mécanisme d'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.

  6. Propositions d'implémentation
  7. Dans le but d'améliorer l'implémentation utilisant l'instanciation dynamique des templates, voici quelques propositions :

    1. Assurer la compatibilité avec le Java standart
    2. 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.

      Download spécification du format d'une classe générique

    3. Intégrer des types primitifs
    4. 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(); }
             

      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.

    5. API permettant l'instanciation partielle et dynamique de template
    6. 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.

      Download méthodes à rajouter à la classe java.lang.Class

      Instanciation partielle de template
      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.


  8. Conclusion
  9. 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.

  10. Bibliographie
  11. [GLS96] The Java Language Specification
    James Gosling, Bill Joy, Guy Steele.
    The Java Series 1996
    [LY96] The Java Virtual Machine Specification
    Tim Lindholm, Franck Yellin
    The Java Series Addison Wesley 1996
    [D97] The Jump Compiler
    Detlef Hoeffner
    http://ourworld.compuserve.com/homepages/DeHoeffner/jump.htm
    [AFM97] Adding Type Parameterization to Java Language
    Ole Agesen, Stephen N.Freund, John C.Mitchell
    Conference Proceedings OOPSLA 97
    [BOSW98] Adding Genericity to the Java Programming Language
    Gilad Bracha, Martin Odersky, David Stoutamire, Philip Wadler
    http://netlib.bell-labs.com/cm/cs/who/wadler/pizza/gj/Documents/index.html

Rémi Forax 1998 Université de Marne la Vallée
Java est une marque de Sun Microsystems, Inc Copyright 1995-98.