Addressed Term Rewriting Systems - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1999

Addressed Term Rewriting Systems

(1) , (1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
RR1999-30.pdf (476.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102103 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102103 , version 1

Citer

Frédéric Lang, Daniel Dougherty, Pierre Lescanne, Kristoffer Rose. Addressed Term Rewriting Systems. [Research Report] LIP RR-1999-30, Laboratoire de l'informatique du parallélisme. 1999, 2+34p. ⟨hal-02102103⟩
11 Consultations
36 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More