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.

, ,
, ,
Department of Computer Science [CS]
Computer Systems & Telematics

Kamperman, J.F.T, & Walters, H.R. (1994). Lazy rewriting on eager machinery. Department of Computer Science [CS]. CWI.