La macro-génération

La macro-génération est une technique « vieille comme le monde », à la fois largement utilisée et largement critiquée. On l'utilise dans deux optiques :

• Dans un souci d'efficacité : la génération de "code en ligne" est la plus simple des techniques d'optimisation. A l'interprétation d'un programme Lisp, on aimera bien ne pas trop attendre ; pour la compilation, on aimera éviter les appels incompilables à la fonction eval.
• Dans un souci d'abstraction : on exprime le problème dans ses termes, et on génère du code dans les termes du langage. Dans un langage comme COBOL, où l'on cherche à écrire un programme comme on écrirait un texte en anglais, la technique est presque un concept primitif du langage.

Le gros avantage de la macro-génération en est sa simplicité. Mais cette simplicité ne doit pas masquer certains dangers qui lui sont liés :

• On ne contrôle plus la taille du code généré : même si l'on tient compte de l'augmentation régulière de la puissance des ordinateurs, il faut malgré tout rester dans des limites raisonnables.
• On ne connaît pas a priori l'allure du code généré : la macro-génération peut construire un code totalement aberrant, ou subtilement aberrant ; par exemple en C, la macro-définition :
  #define max1(a,b) ((a<b)? (b):(a))
  offre toutes les garanties qu'on ne retrouverait pas dans la suivante :
  #define max1(a,b) ((a<b)? b:a)
  les deux définitions sont pourtant syntaxiquement très voisines.

On trouve dans [KoW 87] une syntaxe pour les macro-définitions en Lisp qui cherche à en faciliter la compréhension : au lieu de proposer classiquement une fonction qui permette de tester sur quelques exemples la macro-génération, on propose un moyen d'expression qui fait ressembler la macro-définition à sa forme macro-générée. Dans [TrY 80] on cherche à réduire l'initiative laissée au programmeur à l'utilisation d'une macro-définition (COBOL) : c'est la macro-définition syntaxique, où les paramètres effectifs doivent répondre à certaines contraintes d'ordre syntaxique qu'on impose à la définition.

1. Les données

2. Les traitements

1. Les données

On a présenté précédemment trois types abstraits de données identifiés :

1.1. la référence uniforme

On a vu que pour un phylum :
- les quatre premiers champs sont aussi des propriétés du type,
- le cinquième champ est d'accès plus complexe.

Dans une implantation efficace du type, on voudra accéder directement aux premiers champs et utiliser des fonctions pour les propriétés du dernier. Il se pose alors la question de référence uniforme : on aimerait nommer de la même façon des concepts qui ont une sémantique semblable mais une implantation différente.

Par exemple :
(1) PHYLNOMOPER
(2) NOMOPER(PHYL)
devraient s'interpréter identiquement. On utiliserait alors systématiquement la syntaxe (2), parce qu'elle permet de ne pas distinguer – sur le plan des choix d'implantation – le champ NOMOPER du champ PARENT :
NOMOPER(PHYL) deviendrait PHYLNOMOPER
PARENT(PHYL) resterait un appel fonctionnel

Dans un langage comme Alphard, la chose est vraie.

Dans un langage comme Ada, ceci est faux ; mais les outils développés autour du langage le rendent vrai – un optimiseur global, placé en aval du compilateur, reconnaît dans NOMOPER une "fausse fonction" qu'il génère par du code en ligne.

Dans un langage comme Lisp, ceci sera vrai à l'initiative du programmeur : il peut définir la fonction NOMOPER par une macro-définition qui remplace alors les appels de la fonction par du code en ligne (Note : on pourrait se placer dans cette situation en Ada avec l'utilisation d'un pragma – le pragma INLINE.

Dans d'autres langages, on utilise une définition « textuelle » : la propriété de référence uniforme, mal supportée par ces langages, est introduite en amont du compilateur (c'est-à-dire qu'on fournit au compilateur un texte macro-généré).

1.2. les similitudes de traitements

On s'intéresse ici aux propriétés qui définissent de "vraies fonctions".

La définition d'un Type Abstrait de données n'est jamais très éloignée de celle de Type Abstrait Algébrique (TAA) : on aimerait alors exprimer dans le texte les propriétés de consistance et de complétude qu'on peut vérifier dans le formalisme des TAA.

On regarde le type des drapeaux, pour lequel aucune propriété n'est une "fausse fonction". Le type est déclaré en Ada :

type TYPE_DRAP is record
                     CHP_PRESENT   : BOOLEAN;
                     CHP_VISIB     : INTEGER;
                     CHP_CHGTVISIB : BOOLEAN;
                  end record;

Les sous-programmes qui opèrent sur le champ CHP_PRESENT sont :

function PRESENT (DRAP:in TYPE_DRAP) return BOOLEAN is
begin
   return DRAP.CHP_PRESENT;
end;

procedure SETPRESENT (DRAP:in out TYPE_DRAP) is
begin
   return DRAP.CHP_PRESENT := TRUE;
end;

procedure RESETPRESENT (DRAP:in out TYPE_DRAP) is
begin
   return DRAP.CHP_PRESENT := FALSE;
end;

Les grandes similitudes entre ces trois sous-programmes sont la traduction dans le langage de l'effort du programmeur visant à obtenir la consistance et la complétude dans la définition du type. Une fois encore on ne va pas présenter un moyen de s'assurer ces propriétés mais seulement de les exprimer et de les conserver dans le programme.

Au vu des trois sous-programmes, on "devine" les étapes de construction.

Par exemple, ma procédure SETPRESENT se construit :

-- schéma général des sous-programmes

-- particularisation des procédures

-- particularisation de la procédure SETPRESENT

On donne en annexe l'arbre de construction des sous-programmes relatifs au champ CHP_PRESENT ainsi que sa représentation « textuelle ».

On pourrait définir des « textes » à un niveau de détail plus fin :

• Partant du type TYPE_DRAP et de l'objet DRAP, on déduit les propriétés applicables – dont celles qui nous intéressent ici : l'accès au champ CHP_PRESENT.
• La déclaration de la variable DRAP, paramètre des sous-programmes, est générée automatiquement.
• L'accès au champ CHP_PRESENT détermine le type de l'expression :
  • retournée par la fonction PRESENT : type BOOLEAN,
  • affectée dans les procédures SETPRESENT et RESETPRESENT : les constantes TRUE et FALSE respectivement.

On reconnaît dans les autres propriétés du type TYPE_DRAP les mêmes similitudes, relatives cette fois aux champs CHP_VISIB et CHP_CHGTVISIB.

1.3. la généricité

On introduit la structure générique des listes :

L'implantation intuitive est :

• une liste d'éléments,
• l'élément de tête est statiquement défini : ceci est nécessaire pour réaliser des « effets de bord »,
• qui n'est pas un tableau : on peut supprimer n'importe quel élément de la liste (et pas nécessairement le dernier = la pile).

La représentation qui s'impose de manière évidente est celle d'une liste chaînée.

Comment alors traduire cette structure sous la forme s'un paquetage générique ?

Première réponse

La première approche consiste à considérer la liste comme un type de structure ("record") dont les champs sont les propriétés de la liste :

informellement :

type LISTE is record
                 RECHERCHE : function ...;
                 INS       : procedure ...;
                 SUP       : procedure ...;
              end record;

en Ada :

package LISTE is
   function RECHERCHE ...;
   procedure INS ...;
   procedure SUP ...;
end LISTE;

On doit alors paramétrer le paquetage par :

Le grand nombre de paramètres de généricité soulève deux problèmes :

• d'une part à chaque instanciation il faudra définir toute une panoplie de sous-programmes pour instancier les paramètres formels, ce qui est encombrant et n'introduit aucune nouvelle abstraction intéressante – parce que les paramètres demandés "collent" de trop près la structure de données sous-jacente ;
• d'autre part le module générique a une sémantique floue : la moindre erreur de sémantique dans l'instanciation des paramètres rendra le comportement des procédures génériques tout à fait imprévisible – le module devient finalement inutilisable.

Deuxième réponse

Une deuxième possibilité est de réaliser un type générique dans le paquetage générique de la liste. C'est le type construit dans le paquetage qui sera utilisé pour les instances.

en Ada :

generic
   type TYPE_ELT;
   with function NOM (X:in TYPE_ELT) return STRING;
package LISTE is
   type TYPE_LISTE is ...;
   function RECHERCHE ...;
   procedure INS ...;
   procedure SUP ...;
end LISTE;

Les paramètres du paquetage se limitent alors uniquement aux "vrais" paramètres de généricité : TYPE_ELT et la fonction NOM. On retrouve dans cette approche le traditionnel exemple de la pile paramétrée par le type des éléments.

Dans le cas présent ce choix ne convient pas. En effet, les types de données manipulés sont :

type TYPE_PHYL;
type TYPE_OPER;
type TYPE_DRAP;

type TYPE_REFPHYL is access TYPE_PHYL;
type TYPE_REFOPER is access TYPE_OPER;
type TYPE_REFDRAP is access TYPE_DRAP;

type TYPE_PHYL is record
                     CHP_NOMPHYL  : TYPE_NOM;
                     CHP_ATTPHYL  : TYPE_ATTPHYL;
                     CHP_OPERPHYL : TYPE_REFDRAP;
                     CHP_PEREPHYL : TYPE_REFPHYL;
                     CHP_PARENT   : INTEGER;
                  end record;

type TYPE_OPER is record
                     CHP_NOMOPER  : TYPE_NOM;
                     CHP_ATTOPER  : TYPE_ATTOPER;
                     CHP_PHYLOPER : TYPE_REFDRAP;
                  end record;

type TYPE_DRAP is record
                     CHP_PRESENT   : BOOLEAN;
                     CHP_VISIB     : INTEGER;
                     CHP_CHGTVISIB : BOOLEAN;
                  end record;

Le type TYPE_LISTE des éléments chaînés se retrouve ici :

Il se trouve (par hasard) que la définition récursive du type TYPE_PHYL, par le champ CHP_PEREPHYL qui est une référence sur le type, interdit de définir le type TYPE_PHYL puis d'instancier le type des listes dans le paquetage LISTE.

Plus généralement on peut trouver l'approche peu naturelle : en effet elle demande de définir le cas général d'abord, puis de réaliser les cas particuliers à partir de ce cas général – on définit le type générique, puis on l'instancie. La démarche naturelle de paramétrisation est plutôt inverse : on réalise plusieurs objets, on les reconnaît bâtis sur un même modèle, on définit alors le modèle dont chaque réalisation devient une instance. C'est du reste la démarche qu'on a adoptée ici, et qui a conduit à se placer dans une situation qu'on ne peut pas inverser.