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

Datalogisk Institut

1 Citationer (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.

Originalsprog	Engelsk
Titel	Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation
Antal sider	12
Forlag	Association for Computing Machinery
Publikationsdato	13 jan. 2015
Sider	27-38
ISBN (Trykt)	978-1-4503-3297-2
DOI	https://doi.org/10.1145/2678015.2682539
Status	Udgivet - 13 jan. 2015
Begivenhed	Workshop on Partial Evaluation and Program Manipulation - Mumbai, Indien Varighed: 12 jan. 2015 → 18 jan. 2015

Konference

Konference	Workshop on Partial Evaluation and Program Manipulation
Land/Område	Indien
By	Mumbai
Periode	12/01/2015 → 18/01/2015

Emneord

attribute grammars, graph traversal, haskell, sharing

Adgang til dokumentet

10.1145/2678015.2682539

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

Citationsformater

@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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater