Abstract Origin tracking We are interested in generating interactive programming environments from formal language specifications and use term rewriting to execute these specifications. During the term rewriting process, pieces of the program such as identifiers, expressions, or statements, recur in intermediate terms. We want to formalize these recurrences and use them, for example, for associating positional information with messages in error reports, visualizing program execution, and constructing language-specific debuggers.
Origins are relations between subterms of intermediate terms and subterms of the initial term.
Origin tracking is a method for incrementally computing origins during rewriting. We give a formal definition of origins, and present a method for implementing origin tracking.