Best viewed in 24pt and full-screen

La métaprogrammation

La métaprogrammation est un domaine de programmation où les données sont des programmes. Chercher une caractéristique commune à tous les programmes risque fort de conduire à l'impasse qui consiste à observer que les programmes sont des textes. Cela ne les distingue pas de la multitude de textes qui ne sont pas des programmes. Il vaut mieux risquer de ne pas les comprendre tous et adopter un critère plus précis. Les programmes sont des textes très structurés, engendrés par des grammaires formelles, et dont la dénotation est donnée par un système formel. La métaprogrammation ne s'intéressant pas toujours à calculer la dénotation des programmes, elle n'a pas toujours besoin que celle-ci soit mécanisée en totalité. Un dernier trait important est que les programmes contiennent des noms qui sont liés à des valeurs par la dénotation des programmes. Ces noms sont généralement laissés au choix du programmeur dans le cadre de règles lexicales et syntaxiques qui permettent d'avoir plusieurs noms liés au même signifié (des synonymes) ou plusieurs signifiés pour le même nom (des homonymes) introduisant ainsi la notion de contexte dans lequel un nom doit être interprété. Les techniques de la métaprogrammation doivent donc permettre de construire des structures et d'y naviguer, et de manipuler les noms de manière cohérente.

On ne peut guère aller plus loin dans la caractérisation des programmes sans risquer d'en éliminer une part trop importante. Il est facile de voir que cette caractérisation s'applique autant aux formules qu'aux programmes. En fait, un programme est une formule accompagnée d'une intention particulière : l'exécuter. Tout cela montre que les techniques de la métaprogrammation s'appliquent aussi bien à la manipulation automatique de toute sorte de formules.

Ces manipulations sont en général décrites dans un métalangage mathématique employé sans trop y penser, mais qu'il faut bien comprendre, afin de pouvoir les automatiser dans des programmes. Ce métalangage est fait de conventions d'usage des noms, de quantifications implicites, de renommages implicites, et de combinaisons de théories. Ce métalangage est nécessaire pour la communication entre humains, mais il dissimule de nombreux pièges pour le programmeur qui voudrait automatiser les calculs décrits. L'exemple pour nous le plus fameux et celui de la «convention des variables» de Barendregt. En voici une version formaliste [Barendregt 81],

If , ..., occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

et une version plus familière [Barendregt 90],

For reasons of hygiene it will always be assumed that the bound variables occurring in a certain expression are different from the free ones.

Cette convention donne une règle de lecture des formules contenant des variables syntaxiques (en fait, des métavariables) : une variable syntaxique ne peut désigner que des termes ne liant pas arbitrairement les variables. Autrement dit, il n'y a que des variables liées «nécessaires». C'est important car beaucoup d'énoncés du -calcul prennent un tour «procédurier» uniquement pour tenir compte de la possibilité de liaisons intempestives. Par exemple, l'axiome de -équivalence*, , s'accompagne normalement de la condition que les variables libres de  ne sont pas liées dans , alors que cette condition va de soi si la convention des variables de Barendregt est adoptée. Notons enfin qu'il est extrêmement rare qu'une telle convention soit explicitée. Quand le lecteur de l'axiome de -équivalence devient métaprogrammeur, il ne doit pas se contenter de la face «visible» de la formule mais aussi implémenter l'effet des conventions sur la formule.

De telles conventions émergent dès que l'objet du discours se note dans un langage complexe avec des noms et des portées. Il est facile de produire des expressions de ces langages, mais il est difficile de les analyser car on ne peut pas sortir une sous-expression de son contexte sans précaution. Il est donc difficile de les manipuler en composant les manipulations des sous-expressions. C'est pourtant ce que l'on veut faire en raisonnant inductivement sur la structure des expressions. Par exemple, dans sa thèse (1928 [Herbrand 68]), Herbrand pose la convention suivante :

Pour éviter les ambiguïtés, nous supposerons jusqu'à la fin de ce chapitre que des variables apparentes différentes sont désignées par des lettres différentes.

Ici, «apparent» signifie «qui n'est pas réellement une variable», donc «lié». Cette convention permet à Herbrand d'éviter les collisions de noms de variable lorsqu'il sort des expressions de leur contexte, par exemple, pour constituer des collections de variables liées.

Au delà des problèmes de nommage, les auteurs ont souvent aussi le besoin de substituer des expressions à des noms. Par exemple, Barendregt substitue des termes à des noms pour parler de la -équivalence et Herbrand fait la même chose pour construire des instances de formules quantifiées.

Toutes ces conventions permettent d'utiliser une syntaxe agréable à l'utilisateur tout en en manipulant les expressions avec simplicité. Si l'on veut maintenant automatiser les manipulations, il faut les exprimer de manière complètement explicite et non ambiguë dans un langage de programmation. Cependant, ce n'est pas parce que le texte semi-formel est devenu un programme qu'il doit devenir beaucoup moins lisible. Il faut que le langage de programmation contiennent des conventions qui permettent de s'affranchir du choix des noms ou de remplacer des noms par d'autres expressions. Prolog est un tel métalangage qui emprunte ces conventions au -calcul*. Il en résulte des programmes pas toujours simples, car les conventions du métalangage ne le sont pas non plus. Inversement, Prolog peut donner des idées sur les conventions les plus riches et les mieux étayées par la théorie. Par exemple, utiliser les termes du -calcul au lieu de ceux du premier ordre fournit automatiquement une convention d'usage des variables qui élimine les captures intempestives. C'est ainsi que des problèmes de portée de variables fréquemment rencontrés dans les textes sur la transformation de programme sont simplifiés par l'emploi d'une meilleure métalangue. La notation du -calcul prend aussi en compte le besoin de composer des bribes d'expressions pour en construire de plus grosses dans le respect des portées de nom (la compositionnalité) et le besoin de substituer des expressions à des noms (la généricité) [Miller 91a].

Portée, compositionnalité et généricité ne sont bien sûr pas exclusives l'une de l'autre. Parmi les structures possédant une notion de portée, on trouve les formules logiques ou mathématiques (par exemple, les quantifications, , les sommations et produits, et , les dérivations, d/dx, etc.), et les programmes informatiques (par exemple, le paramétrage f(x) int x; {...}, les blocs { int x; ...}, etc.). Parmi celles possédant une notion de compositionnalité, on trouve les expressions de sémantiques compositionnelles (par exemple, sémantique dénotationnelle de Prolog :  [Nicholson et Foo 89], sémantique de Montague pour la langue naturelle [Montague 74], etc.). Enfin, les quantifications logiques dans une application de démonstration automatique possèdent aussi un caractère de généricité : on en crée des exemplaires par substitution pour construire les preuves.

Le tableau suivant illustre quelques représentations possibles qui utilisent la notation du -calcul.

 
		         				 (lambda x(F x))

		         				 (qqsoit u(P u))

		      				 (integrale 0 1 x(f x))

		 d f/ d x                				 (derivee x(f x))

		 { int x; ...}  				 (bloc int x ...)

		  				 t_g (B1 et B2) k(D1 (D2 k)) :-

		 		  				 t_g B1 D1, t_g B2 D2

L'opération clé de la composition de termes est la substitution d'une structure à une variable et elle doit être faite dans le respect des portées. La définition de la -réduction* permet une telle substitution. C'est pourquoi les -termes sont bien adaptés à la représentation de ces structures : la -abstraction* sert de quantification générique. La première ligne du tableau montre qu'elle peut même servir de quantification générique pour représenter des -termes. Ce n'est pas un cas particulier un peu extrême, c'est juste une application de la loi qui veut qu'on distingue la métalangue de la langue objet. En effet, il existe de nombreuses variantes du -calcul et il n'y a pas de raison que celui de la métalangue soit le même que celui de la langue objet. Par exemple, un même ouvrage peut traiter uniformément, avec la même métalangue et les mêmes conventions, plusieurs -calculs différents.