Origin Tracking for Higher-Order Term Rewriting Systems
Arie van Deursen, T. B. Dinesh · Amast series in computing · 1996
Origin Tracking is a technique which, in the framework of first-order term rewriting systems, establishes relations between each subterm t of a normal form and a set of subterms, the origins of t, in the initial term. Origin tracking is based on the notion of residuals. It has been used successfully for the generation of error handlers and debuggers from algebraic specifications of programming languages. Recent experiments with the use of higher-order algebraic specifications for the definition of programming languages, revealed a need to extend origin tracking to higher-order term rewriting systems. This extension is discussed, covering a definition and some alternatives, as well as an assessment with respect to existing specifications. 1 Origin Tracking When algebraic specifications are being executed as term rewriting systems (TRSs), computations are performed by reducing an initial term to its result value --- its normal form. Often, it is enough just to compute this result value,...