| Publication type: |
Article in Proceedings |
| Author: |
Berthold Hoffmann |
| Editor: |
Helene Kirchner, Giorgio Levi |
| Title: |
Term Rewriting with Sharing and Memoization |
| Book / Collection title: |
Proc. Algebraic and Logic Programming |
| Page(s): |
128 – 142 |
| Series: |
Lecture Notes in Computer Science |
| Number: |
632 |
| Year published: |
1992 |
| Publisher: |
Springer-Verlag, D-69121 Heidelberg, Germany |
| Abstract: |
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 |
| Keywords: |
term graph rewriting |
| Status: |
Reviewed |
| Last updated: |
06. 02. 2006 |
