Réécriture

La réécriture est un modèle de calcul qui repose sur une idée d’une grande simplicité: transformer des suites de symboles en appliquant des règles de remplacement. On part d’une expression, une chaîne de signes quelconque, et l’on dispose d’un ensemble de règles indiquant que tel motif peut être remplacé par tel autre. Calculer consiste alors à repérer dans l’expression un endroit où une règle s’applique, à effectuer le remplacement, puis à recommencer sur le résultat obtenu, et ainsi de suite jusqu’à ce qu’aucune règle ne s’applique plus. Le résultat du calcul est l’expression finale ainsi atteinte. Ce mécanisme purement formel, qui ne fait que substituer des morceaux de texte selon des règles fixées d’avance, suffit à exprimer n’importe quel calcul.

Les systèmes de réécriture ont été étudiés dès les années 1910 et 1920 par le logicien norvégien Axel Thue, avant même l’invention des ordinateurs, puis approfondis par Emil Post dans les années 1940 avec ses systèmes de production. Ces recherches s’inscrivaient dans l’effort général pour comprendre ce que signifie manipuler mécaniquement des symboles, effort dont sont également issues les machines de Turing et le lambda-calcul. Comme pour les autres modèles, on a établi que la réécriture, dans sa forme générale, atteint exactement la même puissance que la machine de Turing et calcule donc précisément les fonctions calculables, ce qui en fait une nouvelle route vers la même frontière.

La réécriture est bien plus qu’une abstraction théorique et se retrouve au cœur de nombreux domaines pratiques. Les grammaires qui décrivent la structure des langages de programmation reposent sur des règles de ce type, et c’est en réécrivant du texte selon ces règles qu’un compilateur analyse un code source. On la retrouve aussi dans les moteurs de calcul formel qui simplifient des expressions mathématiques, dans certains langages de programmation fondés sur des règles, et dans les outils qui transforment automatiquement du code ou des documents. Le lambda-calcul lui-même peut se comprendre comme un système de réécriture particulier, ce qui montre à quel point cette idée simple de remplacement guidé par des règles traverse toute l’informatique.