Lune

PPoPP2021Top-tier venue

Reasoning about recursive tree traversals

Yanjun Wang, Jinwei Liu, Dalin Zhang, Xiaokang Qiu

Abstract

Traversals are commonly seen in tree data structures, and performance-enhancing transformations between tree traversals are critical for many applications. Existing approaches to reasoning about tree traversals and their transformations are ad hoc, with various limitations on the classes of traversals they can handle, the granularity of dependence analysis, and the types of possible transformations. We propose Retreet, a framework in which one can describe general recursive tree traversals, precisely represent iterations, schedules and dependences, and automatically check data-race-freeness and transformation correctness. The crux of the framework is a stack-based representation for iterations and an encoding to Monadic Second-Order (MSO) logic over trees. Experiments show that Retreet can automatically verify optimizations for complex traversals on real-world data structures, such as CSS and cycletrees, which are not possible before. Our framework is also integrated with other MSO-based analysis techniques to verify even more challenging program transformations.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Superfusion: Eliminating Intermediate Data Structures via Inductive SynthesisRuyi Ji, Yuwei Zhao, Nadia Polikarpova, Yingfei Xiong et al.PLDI 2024 · 4 citations

Related papers

  1. Reasoning About Data Trees Using CHCsMarco Faella, Gennaro ParlatoCAV 2022 · 6 citations
  2. Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
  3. Choice Trees: Representing Nondeterministic, Recursive, and Impure Programs in CoqNicolas Chappe, Paul He, Ludovic Henrio, Yannick Zakowski et al.POPL 2023 · 21 citations
  4. Automated Verification of Monotonic Data Structure Traversals in CMatthew SotoudehCAV 2025 · 1 citation
  5. Tree traversal synthesis using domain-specific symbolic compilationYanju Chen, Junrui Liu, Yu Feng, Rastislav BodíkASPLOS 2022 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines