| Art der Veröffentlichung: |
Artikel in Konferenzband |
| Autor: |
Berthold Hoffmann |
| Herausgeber: |
Helene Kirchner, Giorgio Levi |
| Titel: |
Term Rewriting with Sharing and Memoization |
| Buch / Sammlungs-Titel: |
Proc. Algebraic and Logic Programming |
| Seite(n): |
128 – 142 |
| Serie / Reihe: |
Lecture Notes in Computer Science |
| Ausgabe: |
632 |
| Erscheinungsjahr: |
1992 |
| Verleger: |
Springer-Verlag, D-69121 Heidelberg, Germany |
| Abstract / Kurzbeschreibung: |
Jungle evaluation is an approach to define term rewriting with sharing based on graph grammars. This approach preserves important properties of term rewriting like termination, and confluence for terminating systems (under mild restrictions). In this paper, term rewriting with sharing is further accelerated, by memoization known from functional programming languages: The result of evaluating a function with some arguments is tabulated so that it can be looked up later on when the function is re-applied to the same argument. We show that term rewriting with sharing and memoization is correct and complete w.r.t.jungle evaluation if the rules are non-overlapping and non-looping. Redundant re-evaluation of functions is avoided, independent of a particular strategy for applying evaluation rules.
|
| PDF Version: |
http://www.informatik.uni-bremen.de/~hof/papers/ALP92.pdf |
| PostScript Version: |
http://www.informatik.uni-bremen.de/~hof/papers/ALP92.ps.gz |
| Schlagworte: |
term graph rewriting |
| Status: |
Reviewed |
| Letzte Aktualisierung: |
06. 02. 2006 |
