Author
Vandeursen, A; Klint, P; Tip, F
Abstract
The notion of an 'origin' is introduced in the framework of conditional, not necessarily orthogonal, term rewriting systems. Origins are relations between subterms of intermediate terms which occur during rewriting, and subterms of the initial term. Original tracking is a method for incrementally computing origins during rewriting. Origins are a generalization of the well known concept of residuals (also called descendants). A formal definition of origins is given and a method for implementing them is presented. Origin tracking is a highly versatile technique when applied to the prototyping of algebraic specifications of programing languages. For example, origin tracking allows program execution to be visualized in a semi-automatic way, given an algebraic specification of the dynamic semantics of the programming language. Furthermore, various notions of breakpoints for generic debuggers can be defined without difficulty. Given a specification of the static semantics of a programming language, origin tracking enables, once an error (such as type-incompatability) has been detected, the position of the error in the source program to be inferred automatically.
