@InProceedings{dagtraversals,
  Title = {Generalising Tree Traversals to DAGs: Exploiting Sharing without the Pain},
  Author = {Patrick Bahr and Emil Axelsson},
  Booktitle = {Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation},
  Year = {2015},
  Address = {New York, NY, USA},
  Month = jan,
  Date = {2015-01-13},
  Pages = {27--38},
  Publisher = {ACM},
  Abstract = {We present a recursion scheme based on attribute grammars that can
 be transparently applied to trees and acyclic graphs. Our recursion
 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
 representation. 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
 complementing theory with a number of examples.},
  Acmid = {2682539},
  Doi = {10.1145/2678015.2682539},
  ISBN = {978-1-4503-3297-2},
  Keywords = {attribute grammar, tree automata, graph automata, sharing, rewriting, EDSLs, graph traversals},
  Location = {Mumbai, India},
  Numpages = {12},
  Url = {http://doi.acm.org/10.1145/2678015.2682539}
}