A Decision Procedure for (Co)datatypes in SMT Solvers

1 Introduction

In the past decade, satisfiability modulo theories (SMT) solvers [Nieuwenhuis et al., 2006] have emerged as useful tools in a number of applications [De Moura and Bjørner, 2011]. These solvers are one of the most powerful ways to prove theorems in classical first-order logic, and are also useful for constraint solving, or model finding: Given some constraints, they can be used to find an assignment, or model, that satisfies them.

A great benefit of the SMT approach is that it provides a flexible framework for composing dedicated decision procedures and other solvers for various theories, including equality, linear arithmetic on Z and R, bit vectors (for representing n-bit machine words), and first-order quantifiers (8, 9). In this context, recurrent scientific questions include:

• Which theories would be useful to applications?
• Which theories could be implemented efficiently in SMT solvers?

This paper offers the following partial answer: freely generated algebraic and coalgebraic datatypes-also called datatypes and codatatypes. Datatypes are ubiquitous in functional programming and formal specifications. They are useful to represent finite data structures in computer science but also arise in formalized mathematics. And to represent infinite objects, a natural choice is to turn to codatatypes, their nonwell-founded dual. Despite their reputation for esotericism, codatatypes have a role to play in computer science. For example, Leroy's verified C compiler [2009] and Lochbihler's

⇤ In memoriam Morgan Deters 1979-2015

Jasmin Christian Blanchette

Inria Nancy - Grand Est & LORIA Villers-lès-Nancy, France

formalized Java memory model [2014] both depend on codatatypes to express infinite processes.

Codatatypes are freely generated by their constructors, but in contrast with datatypes, infinite constructor terms are also legitimate values for codatatypes (Section 2). The values of a codatatype consist of all well-typed finite and infinite variable-free constructor terms, and only those. As a simple example, the codatatype specification

(using an ML- or Haskell-like syntax) introduces a type that captures the natural numbers Z, S(Z), S(S(Z)), . . . , in unary notation, extended with an infinite value · = S(S(S(. . .))). The equation S(·) ⇡ · holds as expected, because both sides expand to the infinite term S(S(S(. . .))), i.e., ·.

Datatypes and codatatypes are an integral part of many proof assistants, including Coq, Isabelle, and PVS. In recent years, datatypes have emerged in a few automatic theorem provers as well. In this paper, we present a unified decision procedure for universal problems involving datatypes and codatatypes in combination (Section 3). The procedure is described abstractly as a calculus and can be composed with other theories in an SMT solver. It generalizes the procedure by Barrett et al. [2007], which covers only datatypes.

Datatypes and codatatypes share many properties, so it makes sense to consider them together. There are, however, at least three important differences. First, codatatypes need not be well-founded. For example, the type

of infinite sequences or streams over an element type ⌧ is allowed, even though it has no base case. Second, a uniqueness rule takes the place of the acyclicity rule of datatypes. Cyclic constraints such as x ⇡ S(x) are unsatisfiable for datatypes, thanks to an acyclicity rule, but satisfiable for codatatypes. For the latter, a uniqueness rule ensures that two values having the same infinite expansion are equal; from x ⇡ S(x) and y ⇡ S(y), it deduces x ⇡ y. These two rules cannot be finitely axiomatized, so they naturally belong in a decision procedure. Third, it must be possible to express cyclic values as closed terms. For this, we use the µ-binder notation to give a name to a repeated subterm. Thus, the µ-term SCons(1, µs. SCons(0, SCons(9, s))) stands for the sequence 1,0,9,0,9,0,9, . . . .

Our procedure is implemented in the SMT solver CVC4 [Barrett et al., 2011]. It consists of about 2000 lines of C++.

An evaluation on problems generated from Isabelle formalizations demonstrates its usefulness (Section 4).

The original version of this paper was presented at the 25th Conference on Automated Deduction (CADE-25) in Berlin, Germany [Reynolds and Blanchette, 2015]. An more comprehensive article will appear in a special issue of the J. Autom. Reasoning. We refer to these for a description of related work.

2 (Co)datatypes

Our setting is a monomorphic (many-sorted) first-order logic. We fix a signature consisting of a set of types and a set of function symbols. The types are partitioned into the datatypes Ydt, the codatatypes Ycodt, and the are the remaining ordinary types Yord. The function symbols are partitioned into the constructors Fctr and the selectors Fsel. There is no need to consider further function symbols because they can be abstracted away as variables when combining theories.

In an SMT problem, the signature is typically given by specifying first the uninterpreted types in any order, then the (co)datatypes with their constructors and selectors in groups of ` mutually recursive datatypes or corecursive codatatypes, and finally any other function symbols.

Each (co)datatype δ is equipped with m ≥ 1 constructors, and each constructor takes zero or more arguments and returns a δ value. To every argument corresponds a selector. The names for the (co)datatypes, the constructors, and the selectors must be fresh. Schematically:

Datatypes and codatatypes share many basic properties. All properties below are implicitly universally quantified and range over all i, j, j 0, and k within bounds:

with Cij : ⌧ 1 ij ⇥· · ·⇥⌧ nij ij !δi and s k ij : δi !⌧ k ij . The δ constructors and selectors are denoted by F δ ctr and F δ sel. For types with several constructors, it is useful to provide discriminators dij : δi ! bool. We let dij(t) be an abbreviation for t ⇡ Cij(s 1 ij (t), . . . , s nij ij (t)).

Datatypes are additionally characterized by an induction principle. For the natural numbers constructed from Z and S, induction prohibits infinite values S(S(. . .)). For codatatypes, the dual notion is called coinduction: Two values that yield the same observations must be equal, where the observations are made through selectors and discriminators. Codatatypes are also guaranteed to contain all values corresponding to infinite variable-free constructor terms.

3 The Decision Procedure

Given a fixed signature, the decision procedure for the universal theory of (co)datatypes determines the satisfiability of finite sets E of constraints: equalities (⇡) and disequalities (6⇡) between first-order terms, whose variables are interpreted existentially. The decision procedure is formulated as an abstract calculus. Proving a universal quantifier-free conjecture is reduced to showing that its negation is unsatisfiable.

To simplify the presentation, we make a few assumptions about the signature. First, all codatatypes are corecursive. This is reasonable because noncorecursive codatatypes can be seen as nonrecursive datatypes. Second, all ordinary types have infinite cardinality. Without quantifiers, the constraints E cannot entail an upper bound on the cardinality of any uninterpreted type, so it is safe to consider these types infinite. As for ordinary types interpreted finitely by other theories (e.g., bit vectors), each interpreted type having finite cardinality n can be viewed as a datatype with n nullary constructors.

Our calculus for the theory of (co)datatypes consists of derivation rules. A derivation rule can be applied to E if its premises are met. The conclusion either specifies an equality to be added to E or is ? (contradiction). One of the rules has multiple conclusions separated by ♣♣, denoting branching. An application of a rule is redundant if one of its non-? conclusions leaves E unchanged. A derivation tree is a tree whose nodes are finite sets of equalities, such that child nodes are obtained by a nonredundant application of a derivation rule to the parent. A derivation tree is closed if all of its leaf nodes are ?. A node is saturated if no nonredundant instance of a rule can be applied to it.

The derivation rules are partitioned into three phases, given in Figures 1, 2, and 3. The first phase computes the bidirectional closure of E. The second phase makes inferences based on acyclicity (for datatypes) and uniqueness (for codatatypes). The third phase performs case distinctions on constructors for various terms occurring in E. The rules belonging to a phase have priority over those of subsequent phases. The rules are applied until the derivation tree is closed or all leaf nodes are saturated.

3.1 Phase 1: Computing the Bidirectional Closure

In conjunction with Refl, Sym, and Trans, the Cong rule computes the congruence (upward) closure, whereas the Inject and Clash rules compute the unification (downward) closure. For unification, equalities are inferred based on the injectivity of constructors by Inject, and failures to unify equated terms are recognized by Clash. Conflict recognizes when an equality and

Figure 1: Derivation rules for bidirectional closure

its negation both occur in E, in which case E is unsatisfiable.

Let T (E) denote the set of terms occurring in E. At the end of the first phase, E induces an equivalence relation over T (E) such that two terms t and u are equivalent if and only if t ⇡ u 2 E. Thus, we can regard E as a set of equivalence classes of terms. For a term t 2 T (E), we write [t] to denote the equivalence class of t in E. Moreover, at the end of this phase, each equivalence class [t] contains at most one constructor term that is unique up to congruence. Thus, in the subsequent phases, when considering the case that [t] contains constructor terms, it is enough to select an arbitrary constructor term from [t] among these.

3.2 Phase 2: Applying Acyclicity and Uniqueness

The rules in this phase are described in terms of a mapping A that assigns to each equivalence class a µ-term.

Formally, µ-terms are defined recursively as being either a variable x or an applied constructor µx.C(¯ t ) for some C 2 Fctr and µ-terms ¯ t of the expected types. The variable x need not occur free in the µ-binder's body, in which case the binder can be omitted. FV(t) denotes the set of free variables occurring in the µ-term t. A µ-term is closed if it contains no free variables. It is cyclic if it contains a bound variable. The ↵-equivalence relation t =↵ u indicates that the µ-terms t and u are syntactically equivalent for some capture-avoiding renaming of µ-bound variables-e.g., µx. D(y, x) =↵ µz. D(y, z), but µx. C(x), µx. D(y, x), µx. D(z, x), and µy. D(y, x) are all ↵- disequivalent. Two µ-terms can denote the same value despite being ↵-disequivalent-e.g., µx. S(x) 6=↵ µy. S(S(y)).

The mapping A is constructed as follows. With each equivalence class [u], we associate a fresh variable eu of the same type as u. For a term t 2 T (E), we write et to denote the variable associated with the equivalence class [t]. Initially, we set A[u] := eu for each equivalence class [u]. Because eu is unconstrained, this indicates that there are initially no constraints on the values for any equivalence class [u]. The mapping A is refined by applying the following unfolding rule exhaustively:

A :=A[eu 7!µeu. C(e t1 , . . . , e FV(A) denotes the set of free variables occurring in A's range, and A[x 7! t] denotes the variable-capturing substitution of t for x in A's range. It is easy to see that the height of terms produced as a result of the unfolding is bounded by the number of equivalence classes of E, and thus the construction of A will terminate.

The µ-term A[t] describes a class of values that t and other members of t's equivalence class can take in models of E. When ⌧ is a datatype, a cyclic µ-term describes an infeasible class of values.

Figure 2: Derivation rules for acyclicity and uniqueness

Example 1. Suppose that E contains four distinct equivalence classes [w], [x], [y], and [z] such that C(w,y) 2 [x] and C(z, x) 2 [y] for some C 2 Fctr. A possible sequence of un-

[y] 7!µey. C(ez, µex. C(ew, ey))♦ The resulting A indicates that the values for x and y in models of E must be of the forms C(ew,C(ez,C(ew,C(ez, . . .)))) and ⌅

C(ez,C(ew,C(ez,C(ew, . . .)))), respectively. Given the mapping A, the Acyclic and Unique rules work as follows. For acyclicity, if [t] is a datatype equivalence class whose values A[t] = µx. u are cyclic (expressed by x 2 FV(u)), then E is unsatisfiable. For uniqueness, if [t], [u] are two codatatype equivalence classes whose values A [t], A[u] are ↵-equivalent, then t is equal to u. Comparison for ↵-equivalence may seem too restrictive, since µx. S(x) and µy. S(S(y)) specify the same value despite being ↵- disequivalent, but the rule will make progress by discovering that the subterm S(y) of µy. S(S(y)) must be equal to the entire term, as demonstrated next.

Example 2. Let E = ¶x ⇡ S(x), y ⇡ S(S(y))♦. After phase 1, the equivalence classes are ¶x, S(x)♦, ¶y, S(S(y))♦, and ¶S(y)♦. Constructing A yields

A[S(y)] = µg S(y). S(µey. S(g Since A[y] =↵ A[S(y)], the Unique rule applies to derive y ⇡ S(y). At this point, phase 1 is activated again, yielding the equivalence classes ¶x, S(x)♦ and ¶y, S(y), S(S(y))♦. The mapping A is updated accordingly:

3.3 Phase 3: Branching

If a selector is applied to a term t, or if t's type is a finite datatype, t's equivalence class must contain a constructor term. This is enforced in the third phase by the Split rule. Another rule, Single, focuses on the degenerate case where two terms are of a singleton type (one for which there exists only one value), and are therefore equal. Notice that corecursive singleton types may have infinite values. A simple example is

Figure 3: Derivation rules for branching

codata a = A(a), which is corecursive and yet has a cardinality of one; its unique value is µa. A(a). Both Split's finiteness assumption and Single's singleton constraint can be evaluated statically based on a recursive computation of the cardinalities of the constructors' argument types.

3.4 Termination and Correctness

We proved the following properties of derivation trees generated by the calculus [Reynolds and Blanchette, 2015].

Theorem 1 (Termination). All derivation trees are finite.

Theorem 2 (Refutation Soundness). If there exists a closed derivation tree with root node E, then E is unsatisfiable.

Theorem 3 (Solution Soundness). If there exists a derivation tree with root node E containing a saturated node, then E is satisfiable.

By Theorems 1, 2, and 3, the calculus is sound and complete for the universal theory of (co)datatypes. We may rightly call it a decision procedure for that theory. The proof of solution soundness provides a method for constructing a model for a saturated configuration.

4 Evaluation

The decision procedure for (co)datatypes is useful both for proving (via negation, in the refutational style) and for model finding [Ge and de Moura, 2009; Reynolds et al., 2013]. It is in fact vital for finite model finding, because the acyclicity and uniqueness rules are necessary for solution soundness, without which the generated models would often be spurious. For example, given the constraints

zeros ⇡SCons(0, zeros) repeat(n) ⇡SCons(n, repeat(n))

the conjecture zeros ⇡ repeat(0) would be "refuted" by a spurious countermodel that interprets zero and repeat(0) by two distinct values µs. SCons(0, s), violating uniqueness.

By contrast, the contributions of the decision procedure to proving are less obvious; they depend on how often acyclicity and uniqueness are necessary for a proof. To evaluate this, we generated benchmark problems from existing interactive proof goals arising in existing Isabelle formalizations, using Sledgehammer [Blanchette et al., 2013] as translator. We included all the formalizations from the Isabelle distribution (Distro, 1179 goals) and the Archive of Formal Proofs (AFP, 3014 goals) that define codatatypes falling within the supported fragment. We also included formalizations about Bird and Stern-Brocot trees (SBT, 265 goals). To exercise the datatype support, formalizations about finite lists and trees were added to the first two benchmark sets.

For each proof goal in each formalization, we used Sledgehammer to select either 16 or 256 lemmas, which were monomorphized and translated to SMT-LIB along with the goal. The resulting problem was given to the development version of CVC4 (from 15 September 2015) and to Z3 4.3.2 for comparison, each running for up to 60 s. Problems not involving any (co)datatypes were left out.

CVC4 was run on each problem several times, with the support for datatypes and codatatypes either enabled or disabled. The contributions of the acyclicity and uniqueness rules were also measured, by selectively enabling or disabling the rules. Even when the decision procedure is disabled, the problems may contain basic lemmas about constructors and selectors, allowing some (co)datatype reasoning. This is especially true for problems generated using 256 lemmas. The problems with 16 lemmas put more stress on the decision procedure but are less typical of Sledgehammer problems.

The results are summarized in Table 4. For the 16-lemma problems, it accounts for an overall success rate increase of over 5%. Moreover, every aspect of the procedure, including the more expensive rules, makes a contribution. For the 256lemma problems, the difference is much smaller, at 0.5%. The table indicates that the theoretically stronger instances of the decision procedure do not always subsume the weaker ones in practice. The raw data reveal that the full procedure proved 27 goals that could not be proved without it, but failed for 17 goals that could be proved without it.

5 Conclusion

We presented a decision procedure for the universal theory of datatypes and codatatypes. Our approach relies on µ-terms to represent cyclic values. Although this aspect is primarily motivated by codatatypes, it makes a uniform account of datatypes and codatatypes possible-in particular, the acyclicity rule for datatypes exploits µ-terms to detect cycles. The empirical results on Isabelle benchmarks confirm that CVC4's new capabilities improve the state of the art.

This work is part of a wider program that aims at enriching automatic provers with high-level features and at reducing the gap between automatic and interactive theorem proving. We are currently interfacing CVC4's finite model finding capabilities for generating counterexamples in proof assistants [Reynolds et al., 2016]. The acyclicity and uniqueness rules are crucial to exclude spurious counterexamples.

Acknowledgment

We owe a great debt to the development team of CVC4, including Clark Barrett and Cesare Tinelli, and in particular Morgan Deters, who jointly with the first author developed the initial version of the decision procedure for datatypes in CVC4. We also want to thank everyone who helped us with the longer versions of this paper. The second author's work was partially supported by the Deutsche Forschungsgemeinschaft project "Den Hammer härten" (grant NI 491/14-1) and the Inria technological development action "Contre-exemples utilisables par Isabelle et Coq" (CUIC).