Term rewriting is an appealing technique for performing program analysis and program transformation. Tree (term) traversal is frequently used but is not supported by standard term rewriting. We extend many-sorted, first-order term rewriting with <em>traversal functions</em> that automate tree traversal in a simple and type safe way. Traversal functions can be bottom-up or top-down traversals. They can be either sort preserving transformations, or mappings to a fixed sort. We give examples and describe the semantics and implementation of traversal functions.

, , ,
Software Engineering [SEN]
Software Analysis and Transformation

van den Brand, M., Klint, P., & Vinju, J. (2001). Term rewriting with traversal functions. Software Engineering [SEN]. CWI.