Le code et ses raisons
  1. Conventions : le retour
  2. Le code et ses raisons : goto en C
  3. Le code et ses raisons : typedef en C
  4. Pourquoi le C est moins puissant que votre langage favori
  5. Préprocesseur C : récursivité ou imbrication ?
  6. Le C et ses raisons : les pointeurs restreints
  7. Le C et ses raisons : assertions ou programmation défensive ?

Préprocesseur C : récursivité ou imbrication ?

(Nhat Minh Lê (rz0) @ 2010-10-15 12:17:05)

Aujourd’hui, j’ai décidé d’innover sur le blog avec un article éclair. Le principe est simple : je mange, entre deux TP à rendre pour la fin de la semaine, et en même temps, j’écris ce billet (le tout, avec seulement deux mains !).

En effet, il faut bien se l’avouer, on ne voit plus beaucoup ni bluestorm/gasche ni moi écrire, depuis quelques temps, et la tendance ne va pas en s’arrangeant. Du coup, ce midi, j’ai décidé qu’au lieu de m’adonner à mon activité usuelle (lire des mangas en mangeant), j’allais écrire un truc. Et voilà !

Récemment, j’ai eu une conversation fort intéressante avec alpounet (que j’ai interviewé récemment, souvenez-vous, c’était il y a un mois…) sur la vie, l’univers, et le reste, qui a fini par dériver sur un sujet tout à fait en rapport : le préprocesseur C.

Des macros récursives ?

Si vous faites du C++, vous connaissez peut-être (voire avez utilisé) Boost.Preprocessor, une bibliothèque de métaprogrammation utilisant le préprocesseur. Une des fonctionnalités fondamentales de Boost.Preprocessor est d’offrir la répétition pour peu d’effort : vous pouvez générer, grâce à elle, des séquences, non pas de valeurs mais de code. Cela se fait très facilement avec des macros telles que BOOST_PP_ENUM ou BOOST_PP_REPEAT. La documentation fournit l’exemple suivant :

#define TEXT(z, n, text) text
BOOST_PP_ENUM(4, TEXT, class) // expands to class, class, class, class

Normalement, à ce stade, si votre C n’est pas trop rouillé, vous devriez être choqués. En effet, la macro BOOST_PP_ENUM prend en paramètre le nombre d’éléments à générer, or, en C, le préprocesseur ne dispose pas de mécanismes d’itération… se pourrait-il alors que les macros prennent en charge la récurrence ?

Hélas (ou pas, selon les avis), la réponse est non. Il n’y a pas de récursivité possible avec le préprocesseur. Pour vous en convaincre, faites un test simple :

#define F() F() F()
F()

Si votre compilateur explose, c’est que vous vous êtes fait avoir.

En y réfléchissant, c’est même pire, il n’y a même pas moyen de faire de test dans une macro (et pas non plus de filtrage par motifs). Comment détecterait-on la fin de la récursion ?

Comment une bibliothèque telle que Boost.Preprocessor s’y prend-elle donc ? Une partie de la solution se trouve dans un article précédent de ce blog ; si vous ne l’avez pas lu, ou si vous avez besoin de vous rafraîchir la mémoire, je vous invite à y jeter un œil, et plus particulièrement à la partie intitulée Simulez les alternatives avec la concaténation. L’idée, je la rappelle ici, est qu’en utilisant la concaténation entre un paramètre et une partie fixe, il est possible de faire référence à différentes macros à chaque invocation de la macro appelante. Un petit exemple :

#define G(f) G_##f() G_##f()
#define G_F1() 1
#define G_F2() 2
G(F1)                 /* => 1 1 */
G(F2)                 /* => 2 2 */

Muni de cette astuce, il devient alors possible de dévier du graphe d’appels pour terminer une hypothétique récursion. Mais s’il est facile d’écrire un prédicat pour une valeur booléenne, la tâche se complique sensiblement pour les entiers, dont il faut énumérer toutes les valeurs à reconnaître (!), et tant qu’on y est, pourquoi ne pas énumérer toutes les itérations possibles, pour contourner l’interdiction sur la récursivité ! Mon prof d’algo dirait que cela ne change pas la complexité du travail (humain) déjà fourni (pour arriver à décrémenter notre compteur de boucle). C’est effectivement comme cela qu’opère Boost.Preprocessor, et, à ma connaissance, il n’y a pas d’autre moyen.

Dans le cas de Boost.Preprocessor, c’est légèrement plus complexe ; le truc de base est le même mais l’implémentation se veut maline. Si cela vous intéresse, je vous encourage à lire le code directement. Pour les curieux mais pas trop, je reproduis ci-dessous une implémentation possible de BOOST_PP_REPEAT tirée de la documentation officielle, légèrement altérée.

BOOST_PP_REPEAT(n, m, p) applique n fois la macro m en lui passant en paramètres, à chaque fois, le numéro de l’itération courante et la donnée p. Avec cette petite explication, vous devriez être capables de comprendre le code suivant :

#define BOOST_PP_REPEAT(n, m, p) BOOST_PP_REPEAT ## n(m, p)

#define BOOST_PP_REPEAT0(m, p)
#define BOOST_PP_REPEAT1(m, p) m(0, p)
#define BOOST_PP_REPEAT2(m, p) BOOST_PP_REPEAT1(m, p) m(1, p)
#define BOOST_PP_REPEAT3(m, p) BOOST_PP_REPEAT2(m, p) m(2, p)
#define BOOST_PP_REPEAT4(m, p) BOOST_PP_REPEAT3(m, p) m(3, p)
...

Récursivité ou imbrication ?

Au vu de ce que nous venons d’admettre, nous sommes en droit de nous demander si, tout compte fait, des macros récursives serviraient à quelque chose, avec un langage aussi limité.

Selon moi, il y a clairement des avantages… et des inconvénients. L’inconvénient évident est la menace que vos programmes pourraient ne jamais finir de compiler si vous entrez d’une manière ou d’une autre dans une récursion infinie du préprocesseur. D’un autre côté, le langage n’a pas réellement d’état, du moins, son état reste inchangé durant toute la durée de substitution d’une macro, ce qui signifie qu’une fois le processus lancé, le résultat d’une macro dépend uniquement de ses arguments. Il serait donc possible d’imaginer des stratégies pour éviter ce comportement désagréable.

Au niveau des avantages, il faut regardre du côté de la composabilité : le fait de pouvoir enchaîner les appels de macros. Avec le système actuel, il est possible, dans une certaine limite, de composer les appels de macros. En effet, si la récursion est interdite, il est possible de passer des appels de macros en paramètres à d’autres… et ce, même si ce sont les mêmes ! C’est ce que j’appelle l’imbrication syntaxique. Cela est dû au fait que les arguments sont entièrement développés au début de chaque substitution, avant que le corps de la macro ne soit considéré.

Ce qu’il est impossible de faire, en revanche, c’est une sorte d’appel indirect à la même macro : si nous ne passons pas l’expression entière contenant la substitution en paramètre, mais seulement le nom de la macro à invoquer, par exemple, en laissant le soin de cette opération à l’appelée, alors nous sommes à nouveau sujets aux restrictions sur la récursivité. Par exemple :

#define F(x) x
#define G(f) (1 + f(G))
F(F(1))               /* => 1 */
G(F)                  /* => (1 + G) */
G(G)                  /* => (1 + G(G)) */

Un exemple rigolo : des fermetures-macros ?

Mon dernier exemple n’était pas très utile, j’en conviens. Mais nous pourrions imaginer par exemple stocker dans des n-uplets des invocations de macros latentes, des espèces de « macros d’ordre supérieur avec application partielle », qui pourraient n’être déroulées qu’au moment voulu. Un format évident serait :

(macro, arg, ...)

En utilisant les capacités du C99 (principalement, les macros à nombre arguments variables) il est aisé d’extraire le premier élément du n-uplet, ou tous les éléments sauf le premier :

#define HEAD(a, ...) a
#define TAIL(a, ...) __VA_ARGS__

Armé de ces outils, nous voudrions pouvoir écrire ceci :

#define EXPAND(m) HEAD m (TAIL m)

Malheureusement, cela ne fonctionne pas. Pour plusieurs raisons. Tout d’abord, il est évident que si nous définissons une macro EXPAND, le vrai appel à la macro sous-jacente ne pourra pas faire appel à EXPAND. Nous devons donc nous résoudre à recopier l’incantation pour chaque application d’une fermeture-macro.

Malgré nos efforts (vous pouvez essayer avec votre compilateur, si vous n’êtes pas convaincus), cela ne marche toujours pas. Il y a un autre problème : telle qu’elle est donnée, l’application essaie d’appeler la macro avec un seul argument, le n-uplet privé de sa tête (et sans les parenthèses). Il serait possible de forcer l’évaluation de la liste d’arguments en utilisant une macro dans le genre de :

#define APPLY(f, args) f args

En effet, le passage en arguments force la substitution de ceux-ci. Cependant, nous nous retrouverions avec le même problème que précédemment, à savoir que les appels « récursifs » à APPLY ne seraient pas permis…

J’espère que par cet exemple, j’aurais réussi à vous faire sentir les difficultés liées aux limitations intrinsèques du langage ; toutefois, il est encore possible de pousser la bête un peu plus loin. Si l’on ne peut définir une macro APPLY générale, il est possible d’écrire deux versions de chaque macro, dont l’une ne prendrait qu’un seul argument :

#define F(x, y, z) ...
#define F_(args) F(args)

Souvenez-vous que le passage en argument force la substitution à l’intérieur de ceux-ci. Encore une fois, cet effort est vain, car il y a un autre problème fondamental que nous avons ignoré depuis le début. Examinons à nouveau le contenu de la macro EXPAND :

HEAD m (TAIL m)

L’ambiguïté se situe dans l’appel à HEAD. L’invocation de la macro représentée par m hérite, en effet, en partie du corps substitué par l’appel à HEAD m, et en partie de la suite du code (TAIL m). Dans ce cas de figure, très particulier au mode de fonctionnement d’un préprocesseur de texte, il convient de se demander s’il faut considérer cette invocation dans le contexte de HEAD ou pas, en d’autres termes, s’il faut interdire à celle-ci d’appeler à nouveau HEAD ou non. GCC le permet, MCPP ne le permet pas. La norme semble donner raison au second (même si je ne la trouve pas totalement explicite sur le sujet) ; je cite (emphase rajoutée par mes soins) :

After all parameters in the replacement list have been substituted and # and ## processing has taken place, all placemarker preprocessing tokens are removed. Then, the resulting preprocessing token sequence is rescanned, along with all subsequent preprocessing tokens of the source file, for more macro names to replace.

If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file’s preprocessing tokens), it is not replaced. Furthermore, if any nested replacements encounter the name of the macro being replaced, it is not replaced.

L’important, donc, semble-t-il, est que le nom de la macro fasse ou non partie du résultat d’un précédent appel. Je vous l’accorderais volontiers, cependant, on aura certainement vu plus clair !

Ceci étant dit, je pense que la conclusion raisonnable à tirer est qu’en tant qu’utilisateurs du langage, il est plus sage de s’abstenir d’abuser de telles propriétés… mais vous êtes, bien sûr, libres de penser autrement !