E-Matching efficace : un nouvel outil pour les compilateurs optimisants
Les prouveurs de théorèmes modernes et les compilateurs optimisants reposent sur une technique ingénieuse : l’E-matching. Il ne se contente pas de faire correspondre la syntaxe, mais surtout la sémantique, en réalisant un raisonnement d’équivalence grâce aux E-graphs et à la clôture de congruence. Cet article explore les principes de l’E-matching, notamment comment trouver efficacement des motifs correspondants dans les E-graphs à l’aide d’arbres de discrimination et de la clôture de congruence, évitant ainsi l’inefficacité du parcours récursif traditionnel. L’auteur présente également son application dans le compilateur Zob, en compilant les motifs en instructions de machine virtuelle pour un E-matching efficace, améliorant ainsi considérablement l’efficacité de l’optimisation.