Generalising Tree Traversals to DAGs: Exploiting Sharing without the Pain

Patrick Bahr, Emil Axelsson

    Publikation: Konference artikel i Proceeding eller bog/rapport kapitelBidrag til bog/antologiForskningpeer review

    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.
    OriginalsprogEngelsk
    TitelProceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation
    Antal sider12
    UdgivelsesstedNew York, NY, USA
    ForlagAssociation for Computing Machinery
    Publikationsdato1 jan. 2015
    Sider27-38
    ISBN (Trykt)978-1-4503-3297-2
    DOI
    StatusUdgivet - 1 jan. 2015

    Emneord

    • attribute grammar, tree automata, graph automata, sharing, rewriting, EDSLs, graph traversals

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Generalising Tree Traversals to DAGs: Exploiting Sharing without the Pain'. Sammen danner de et unikt fingeraftryk.

    Citationsformater