Generalising tree traversals to DAGs: exploiting sharing without the pain

Patrick Bahr; Emil Axelsson

doi:10.1145/2678015.2682539

Generalising tree traversals to DAGs: exploiting sharing without the pain

Patrick Bahr, Emil Axelsson

Department of Computer Science

1 Citation (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation
Number of pages	12
Publisher	Association for Computing Machinery
Publication date	13 Jan 2015
Pages	27-38
ISBN (Print)	978-1-4503-3297-2
DOIs	https://doi.org/10.1145/2678015.2682539
Publication status	Published - 13 Jan 2015
Event	Workshop on Partial Evaluation and Program Manipulation - Mumbai, India Duration: 12 Jan 2015 → 18 Jan 2015

Conference

Conference	Workshop on Partial Evaluation and Program Manipulation
Country/Territory	India
City	Mumbai
Period	12/01/2015 → 18/01/2015

Access to Document

10.1145/2678015.2682539

http://doi.acm.org/10.1145/2678015.2682539

Cite this

@inbook{ed7e3c9697a84997b7b5acf0abb81309,

title = "Generalising tree traversals to DAGs: exploiting sharing without the pain",

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.",

keywords = "attribute grammars, graph traversal, haskell, sharing",

author = "Patrick Bahr and Emil Axelsson",

year = "2015",

month = jan,

day = "13",

doi = "10.1145/2678015.2682539",

language = "English",

isbn = "978-1-4503-3297-2",

pages = "27--38",

booktitle = "Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation",

publisher = "Association for Computing Machinery",

note = "Workshop on Partial Evaluation and Program Manipulation ; Conference date: 12-01-2015 Through 18-01-2015",

}

TY - CHAP

T1 - Generalising tree traversals to DAGs

T2 - Workshop on Partial Evaluation and Program Manipulation

AU - Bahr, Patrick

AU - Axelsson, Emil

PY - 2015/1/13

Y1 - 2015/1/13

N2 - 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.

AB - 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.

KW - attribute grammars, graph traversal, haskell, sharing

U2 - 10.1145/2678015.2682539

DO - 10.1145/2678015.2682539

M3 - Book chapter

SN - 978-1-4503-3297-2

SP - 27

EP - 38

BT - Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation

PB - Association for Computing Machinery

Y2 - 12 January 2015 through 18 January 2015

ER -

Generalising tree traversals to DAGs: exploiting sharing without the pain

Abstract

Conference

Access to Document

Fingerprint

Cite this