Generalising tree traversals to DAGs: Exploiting sharing without the pain. Unpublished manuscript, available from the author’s web site

We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recur-sion scheme allows the programmer to implement a tree traversal and then apply it to compact graph representations of trees instead. The resulting graph traversals avoid recomputation of intermediate results for shared nodes – even if intermediate results are used in different contexts. Consequently, this approach leads to asymptotic speedup proportional to the compression provided by the graph rep-resentation. In general, however, this sharing of intermediate results is not sound. Therefore, we complement our implementation of the recursion scheme with a number of correspondence theorems that ensure soundness for various classes of traversals. We illustrate the practical applicability of the implementation as well as the comple-menting theory with a number of examples