Addressed Term Rewriting Systems
Résumé
We propose Addressed Term Rewriting Systems (ATRS) as a solution to the still-standing problem of finding a simple yet formally useful framework that can account for computation with sharing, cycles, and side effects. ATRS are characterised by the combination of three features: they work with terms where structural induction is useful, they use a minimal ``back-pointer'' representation of cyclic data, and they ensure a bounded complexity of rewrite steps by eliminating implicit pointer redirection. In the paper we develop this and show how it is a very useful compromise between less abstract term graph rewriting and the more abstract equational rewriting.
Nous proposons les Systèmes de Réécriture de Termes à Adresses (ATRS) comme solution au problème de définition d'un cadre simple et formel qui permet de rendre compte de calculs mettant en oeuvre du partage, des cycles, et des effets de bord. Les ATRS sont caractérisés par la combinaison de trois aspects : ils sont basés sur une représentation des graphes par des termes, où l'induction structurelle est utile, ils mettent en oeuvre une représentation minimale des structures de données cyclique par ``pointeur arriére'', et ils assurent une complexité bornée des pas de réécriture en éliminant les redirections de pointeurs implicites. Dans cet article, nous développons ceci, et nous montrons qu'il s'agit d'un compromis très utile entre la réécriture de graphes, moins abstraite, et la réécriture équationnelle, plus abstraite.
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|