Lazy rewriting on eager machinery

We define Lazy Term Rewriting Systems and show that they can be realized by local adaptations of an eager implementation of conventional term rewriting systems. The overhead of lazy evaluation is only incurred when lazy evaluation is actually performed. Our method is modelled by a transformation of term rewriting systems, which concisely expresses the intricate interaction between pattern matching and lazy evaluation. The method easily extends to term graph rewriting. CR Subject Classification (1991): D.3.4 [Programming languages]: Processors -- Compilers, Optimization; D.1.1 [Programming Techniques]: Applicative (Functional) Programming; D.1.6: Logic Programming. AMS Subject Classification (1991): 68N20: Compilers and generators; 68Q05: Models of Computation; 68Q42: Rewriting Systems Keywords & Phrases: lazy term rewriting, program transformation. Note: Partial support received from the European Communities under the ESPRIT project 5399 (Compiler Generation for Parallel Machines -...