Term rewriting with traversal functions

    Research output: Contribution to journalArticleAcademicpeer-review

    51 Citations (Scopus)


    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 traversal functions that automate tree traversal in a simple and type-safe way. Traversal functions can be bottom-up or top-down traversals and can either traverse all nodes in a tree or can stop the traversal at a certain depth as soon as a matching node is found. They can either define sort-preserving transformations or mappings to a fixed sort. We give small and somewhat larger examples of traversal functions and describe their operational semantics and implementation. An assessment of various applications and a discussion conclude the article.
    Original languageEnglish
    Pages (from-to)152-190
    Number of pages39
    JournalACM Transactions on Software Engineering and Methodology
    Issue number2
    Publication statusPublished - 2003


    Dive into the research topics of 'Term rewriting with traversal functions'. Together they form a unique fingerprint.

    Cite this