💻 computer science

Automated Reasoning with Nested Datatypes

This paper introduces a theory of nested datatypes that restricts the combination of datatypes and arrays to prevent non-standard models, provides a proven correct decision procedure for it, and evaluates an implementation of this procedure on real-world and crafted benchmarks.

Original authors: Tomer Hakak, Yoni Zohar, Andrew Reynolds, Clark Barrett, Cesare Tinelli

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tomer Hakak, Yoni Zohar, Andrew Reynolds, Clark Barrett, Cesare Tinelli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a complex digital city using two different types of Lego bricks: Datatypes and Arrays.

Datatypes are like family trees or organizational charts. They are hierarchical. A "Person" can have a "Child," and that Child can have their own "Child." The rule here is simple: No one can be their own ancestor. You can't have a family tree where a person is their own grandparent; that creates a logical loop (a cycle) that breaks the structure.
Arrays are like mailboxes or lockers. They are flat and allow you to grab any item instantly by its number (index). You can put anything in a mailbox, including a whole family tree.

The Problem: The "Infinite Loop" Trap

The paper starts by pointing out a dangerous glitch that happens when you naively combine these two systems.

Imagine you have a Person (a datatype) who has a field called "Family." In a normal world, "Family" is a list of people. But in this glitchy world, "Family" is an Array (a locker).

You put a specific Person (let's call him Bob) into Locker #5.
Then, you define Bob's "Family" field to be Locker #5.

Now, look at what happens:

To find Bob's family, you open Locker #5.
Inside Locker #5, you find Bob.
To find Bob's family, you open Locker #5 again.
You find Bob again.

You are stuck in an infinite loop. In computer science, this is called a non-standard model. It's like a snake eating its own tail. While a computer might technically allow this, it breaks the intuitive rules of how data structures should work. It creates a "cycle" that shouldn't exist.

The Solution: The "Nested Datatype" Theory

The authors, Tomer Hakak and his team, say: "We need a rulebook that prevents this snake-eating-tail scenario."

They introduce a new theory called Nested Datatypes. Think of this as a strict building code for your digital city.

The Rule: You can put a family tree inside a locker, and you can put a locker inside a family tree, BUT you cannot create a path that leads you back to where you started.
The Goal: If you trace a path from a person, through their family array, to another person, and back through their family array, you must never end up back at the original person.

How They Fixed It: The "Translator" Machine

The hard part is that computers are really good at checking if a family tree is valid, and they are really good at checking if lockers are valid. But they are bad at checking if a combination of the two creates a loop.

The authors built a Translator (a decision procedure). Here is how it works, using a metaphor:

Imagine you have a puzzle with two different types of pieces: Tree pieces and Box pieces. The computer doesn't know how to check for loops when they are mixed.

The Translation: The authors' algorithm takes the mixed puzzle and translates it into a language the computer does understand. It turns the "Box pieces" into special "Tree pieces" that look like boxes but act like trees.
The Safety Net: They add extra "guard rails" (lemmas) to the translation. These guard rails ensure that if a loop would have existed in the original mixed puzzle, the translated tree version will immediately show a contradiction (like trying to build a tower that defies gravity).
The Check: The computer checks the translated puzzle.
- If the translated puzzle is impossible (unsatisfiable), it means the original mixed puzzle had a forbidden loop.
- If the translated puzzle works, the original puzzle is safe.

Why This Matters (According to the Paper)

The authors didn't just write a theory; they built a prototype inside a real-world computer program called cvc5 (a tool used to verify software).

Real-World Test: They tested it on benchmarks from the Move Prover, a tool used to verify smart contracts (digital money agreements). These contracts often use complex nested data.
Synthetic Test: They created fake puzzles specifically designed to trap other solvers in infinite loops.
The Result: Their new method successfully caught the loops that other methods missed. In many cases, it was faster and more accurate than the existing tool (Z3) used for similar tasks.

Summary

In short, this paper is about fixing a bug in how computers understand complex data.

The Bug: Mixing "family trees" and "mailboxes" can accidentally create infinite loops where a person is their own ancestor.
The Fix: A new set of rules (Theory of Nested Datatypes) that strictly forbids these loops.
The Tool: A translator that converts these complex mixed rules into a format computers can easily check for safety, ensuring that your digital data structures remain logical and loop-free.

Technical Summary: Automated Reasoning with Nested Datatypes

1. Problem Statement

The SMT-LIB theory of datatypes provides a convenient encoding for data structures like lists and trees, essential for software verification. However, its expressivity is limited by the lack of update operators and random-access capabilities. To address this, a naive combination of datatypes with the theory of arrays is often attempted.

The core problem identified in this work is that such a naive combination introduces non-standard models. Specifically, the principle of acyclicity—which dictates that a datatype value cannot contain itself—is bypassed when arrays are involved. A datatype value can appear as an element of an array where that array is, in turn, a field of the same datatype value. This creates a cycle that the standard combination of theories (via Nelson-Oppen) fails to detect because the cycle is "split" between the datatype and array components. These non-standard models are undesirable as they do not align with the intuitive semantics of nested data structures intended for verification.

2. Methodology

The authors propose a theory of nested datatypes that explicitly excludes these non-standard models. The methodology involves two main components: a formal definition of the theory and a decision procedure based on reduction.

2.1. Formal Definition

The theory is defined by restricting the standard combination of datatypes and arrays.

Well-foundedness: The authors introduce a new definition of well-founded sorts (Definition 10) that accounts for the presence of array sorts. This ensures that the recursive structure of datatypes remains well-founded even when array elements are involved.
NDT Relation: To exclude non-standard models, the authors define a relation $\mathcal{R}_{\mathcal{A}}$ on the structures (Definition 16). This relation connects terms to their sub-terms and arrays to their elements. A structure is considered a valid NDT structure only if this relation is well-founded. This effectively rules out cycles where a datatype value indirectly references itself through an array.

2.2. Decision Procedure

The paper presents a decision procedure that reduces the satisfiability problem for nested datatypes to the (naive) combination of datatypes, arrays, and uninterpreted functions (EUF). The procedure operates as follows:

Signature Translation: A new signature $\Sigma_{\varphi}$ is constructed.
- Array sorts are split into two components: a datatype sort ( $\sigma^*$ ) used for cycle checking and an array sort ( $\sigma'$ ) used for standard array reasoning.
- Datatype constructors are copied to operate on the new sorts.
- Special constructors are introduced to represent arrays as finite tuples, capturing the elements accessed by indices present in the input formula.
- Uninterpreted functions ( $f_A, g_A$ ) are added to link the array sort representations ( $\sigma'$ ) with the datatype sort representations ( $\sigma^*$ ).
Formula Translation: The input formula $\varphi$ is translated into $\text{trFormula}(\varphi)$ .
- Standard literals (e.g., $x = \text{select}(a, i)$ ) are mapped to their counterparts in the new signature.
- Lemmas: Crucially, the translation is augmented with a set of lemmas ( $L(\varphi)$ ) that enforce the correspondence between the array operations in the original formula and the tuple-based representation in the new signature. These lemmas ensure that the "hidden cycles" are exposed in the translated formula.
Solving: The resulting formula $\text{trFormula}(\varphi)$ is checked for satisfiability using existing SMT solvers capable of handling the combination of datatypes, arrays, and EUF (e.g., via the Nelson-Oppen method).

2.3. Correctness and Decidability

The paper proves that the translation preserves satisfiability (Theorem 31) under the assumption that the datatype theory is stably infinite with respect to the shared sorts. Consequently, the theory of nested datatypes is decidable (Theorem 32).

3. Key Contributions

The paper makes three primary contributions:

Theory Definition: The introduction of a precise theory of nested datatypes that prevents non-standard cyclic models arising from the interaction between datatypes and arrays.
Decision Procedure: A reduction-based decision procedure that transforms nested datatype problems into standard theory combinations augmented with uninterpreted functions.
Implementation and Evaluation: A prototype implementation within the cvc5 SMT solver and an empirical evaluation demonstrating the approach's effectiveness.

4. Experimental Results

The authors evaluated their implementation on two benchmark suites:

Synthetic Benchmarks: Formulas systematically designed to create cycles of varying sizes between datatypes and arrays.
- On unsatisfiable instances (cycles present), cvc5 solved all 500 benchmarks, outperforming Z3 (which solved 299.8 on average, though the table indicates Z3 solved fewer total instances).
- On satisfiable instances (cycles broken), cvc5 solved 25 out of 50, while Z3 solved only 1.
Real-World Benchmarks: Formulas derived from the Move Prover verification tool, which uses nested datatypes to model persistent data structures in smart contracts.
- Both solvers solved all Move Prover benchmarks quickly.
- cvc5 was comparable to or slightly faster than Z3 on satisfiable instances.

5. Significance and Claims

The paper claims that the proposed theory and decision procedure successfully address the issue of non-standard models in the combination of datatypes and arrays, a problem that existing solvers (like Z3) may handle implicitly but without a precise theoretical definition or guaranteed correctness regarding acyclicity.

The authors state that their approach is "promising," showing that it is competitive with existing solutions on real-world benchmarks and superior on synthetic benchmarks designed to stress-test cycle detection. They emphasize that the work was motivated by the needs of the Move Prover, where such nested structures are common.

The paper concludes modestly, noting that while the current work solves the specific case of arrays, the broader problem of undetected cycles exists for other data structures (sequences, sets, etc.). The authors suggest that their solution for arrays may serve as a basis for a more general solution to naive theory combination issues. Future work is identified as expanding support to incremental solving and quantifiers.