Generalising Tree Traversals and Tree Transformations to DAGs
This repository contains the source code associated with the paper "Generalising Tree Traversals and Tree Transformations to DAGs: Exploiting Sharing without the Pain" submitted to Science of Computer Programming.
The technical report containing full proofs of all theorems in the paper is found here.
Note: the associated material for the PEPM 2015 paper "Generalising Tree Traversals to DAGs" is found in the PEPM branch.
- The library implementation is in the src subdirectory.
- (Parametric) attribute grammars on trees are defined in the modules AG and PAG.
- (Parametric) attribute grammars on DAGs are defined in the modules Dag.AG and Dag.PAG.
- bench/Bench.hs has benchmarks for evaluating the performance.
- Use the command
cabal benchto run the benchmarks. The benchmark reports are written into the
- Examples from the paper can be found in the examples subdirectory.