The Extended Theory of Trees and Algebraic (Co)datatypes

Fabian Zaiser, C.-h. Luke Ong

TL;DR

This paper extends the theory of trees, a foundational concept in computer science for representing data structures, to uniformly handle both finite (datatypes) and infinite (codatatypes) structures. They introduce a novel simplification procedure that not only decides satisfiability of formulas but also provides simplified, human-readable models, making it a powerful tool for reasoning about algebraic datatypes.

What Problem Does This Paper Address?

Representing and reasoning about data structures in programming languages often involves algebraic datatypes (finite structures) and codatatypes (potentially infinite structures). While existing tools like SMT solvers can handle these separately, a unified and expressive framework for reasoning about both simultaneously has been lacking. Specifically, existing theories of trees struggled with the finite number of constructors typical in programming languages, and lacked a mechanism to express properties like non-finiteness or to provide simplified, interpretable models for formulas. This paper addresses this by extending the theory of trees with a finiteness predicate and developing a decision procedure that works for finitely generated sorts, offering a more practical and expressive approach.

Methods

The core of this work is an extension of the first-order theory of trees with a predicate fin(t) to explicitly state that a tree t is finite. This extended theory is then used as a background theory for algebraic datatypes and codatatypes. The authors adapt a previously developed simplification procedure for trees to handle "finitely generated sorts," which are crucial for representing datatypes. This involves:

  • Analyzing Sorts: Developing algorithms to classify sorts based on the number of finite and infinite trees they can generate (e.g., sorts with no finite trees, finitely many finite trees, etc.).
  • Simplification Procedure: Extending an existing algorithm to handle these finitely generated sorts. This procedure transforms formulas into a disjunction of "fully simplified" formulas, which are easy to interpret.
  • Instantiable Variables: A key novelty is the introduction of a mechanism to handle "instantiable variables" – variables that require case splits to determine their possible values. This is crucial for dealing with the finite number of constructors in datatypes.
  • Normal Forms: The procedure relies on transforming formulas into a specific "normal form" that facilitates simplification.

Datasets

The paper evaluates their implementation on instances from the SMT-LIB benchmark suite, specifically the QF_DT (quantifier-free datatypes) suite. These instances were transformed into formulas within the extended theory of trees.

Key Insights and Ideas

  • Unified Representation: The theory of trees, augmented with a finiteness predicate, provides a powerful and uniform way to represent and reason about both finite datatypes and infinite codatatypes.
  • Expressiveness of fin(t): The explicit fin(t) predicate allows for finer-grained reasoning, enabling statements about non-finiteness or conditional properties based on finiteness, which is not directly possible in standard datatype theories.
  • Simplification for Interpretability: The development of a simplification procedure that yields "fully simplified" formulas is a significant contribution. This moves beyond mere satisfiability checking to providing human-readable models, greatly aiding in understanding the solutions.
  • Handling Finitely Generated Sorts: Adapting existing tree theory algorithms to work with finitely generated sorts (common in programming languages) is a crucial practical extension, overcoming limitations of prior work.
  • Instantiable Variables: The concept of "instantiable variables" and the associated case-splitting mechanism is a novel technique for managing the complexity introduced by finite constructors.

Key Results

  • The paper presents a formal framework for the extended theory of trees and its relationship with algebraic (co)datatypes.
  • They provide a decision procedure for this theory that outputs simplified formulas, making models easy to read off.
  • Their prototype implementation successfully processed over 90% of transformed SMT-LIB QF_DT benchmarks in under 1 second, demonstrating practical feasibility.
  • The extended theory of trees is shown to be more expressive than selector-free (co)datatypes.

Limitations and Future Work

  • Non-Elementary Complexity: The authors acknowledge that the original theory of trees already has non-elementary time complexity, and their extension inherits this, meaning worst-case performance can be very high.
  • Prototype Implementation: The current implementation is a prototype and could benefit from optimizations, such as improved normalization and heuristics for variable instantiation.
  • Future Work: The authors suggest investigating Craig interpolation for the theory of trees and exploring its application as a background theory for higher-order constrained Horn clauses. They also mention that handling sorts with a single non-recursive generator would require special casing, which was omitted for brevity.

Summary updated

BibTeX
@inproceedings{zaiser2021extended,
  author = {Fabian Zaiser and C.-H. Luke Ong},
  title = {{The Extended Theory of Trees and Algebraic (Co)datatypes}},
  booktitle = {SMT},
  year = {2021},
}
Figure