Counting Instead of Permuting: Verifying Higher-Order Programs over Bags via Diophantine Translation into HFL(Z)

Many functional programs handle unordered collections. Examples are message bags in a protocol, multisets of tasks in a scheduler, and the terms of a commutative sum. These programs pass functions over such collections through folds, maps and callbacks. Automated verifiers for higher-order programs, meaning programs that take and return functions, treat every data value as a free tree. In a free tree, insert a (insert b s) and insert b (insert a s) are different objects. A verifier that wants to prove "the total is the same whatever order messages arrive in" must either enumerate orderings or be handed equations that make solvers loop. We propose a different route. The theory of associative-commutative (AC) operators, meaning operators like bag union where grouping and order do not matter, has known for decades that reasoning modulo these laws reduces to linear equations over non-negative integers. The leading higher-order verifier, built on higher-order fixpoint logic with integers (HFL(Z)), already reasons natively about linear integer arithmetic. We therefore compile bags into integer count vectors and let that verifier do the rest.

Two things make this more than a hand encoding. First, a bag fold is only meaningful if the function being folded ignores order. Whether a closure, a function value bundled with its captured variables, respects that law is itself a higher-order verification question. We discharge it with the same engine before trusting the count translation. Second, elements drawn from infinite types such as integers cannot be counted exactly. We count them per abstraction class and refine the classes from spurious counterexamples. The result is a sound, automatic translation that is exact on a characterized fragment, plus an evaluation that tests whether it beats the free-tree pipelines on programs where order should not matter.

Core Claim

AC unification reduces to finding minimal non-negative solutions of homogeneous linear Diophantine systems, as shown by Associative-Commutative Rewriting. A Complete Unification Algorithm for Associative-Commutative Functions builds this directly into a solver by flattening terms into bags of variables and constants. Because of this reduction, AC data does not need a new inference calculus inside a higher-order prover. It needs a translation into the arithmetic that higher-order validity checkers already handle.

For a bag term $t$ and a finite family of element classes $p_1,\dots,p_k$, we write $\#(t)\in\mathbb{N}^k$ for the vector whose $i$-th entry counts the elements of $t$ in class $p_i$. Bag union becomes vector addition:

$$\#(t \uplus s) = \#(t) + \#(s), \qquad \#(\emptyset)=0.$$

Our claim has three parts. The translation of a program into an HFL(Z) formula over these vectors is sound for safety and termination properties. It is exact whenever the property and all control decisions depend only on per-class counts and every folded closure is left-commutative. That condition is $f\,a\,(f\,b\,z) = f\,b\,(f\,a\,z)$ for all $a,b,z$, and it can itself be stated as an HFL(Z) safety obligation on a two-copy product of the program. Finally, a solver run on the translated formula, such as MuHFL from HFL(Z) Validity Checking for Automated Program Verification, will solve order-insensitive verification problems that defunctionalized free-term pipelines cannot.

Disjunctions also become manageable. An AC matching problem has several incomparable solutions, for instance $x \uplus y$ against $a\uplus a\uplus b$. Each solution becomes one disjunct of integer constraints. HFL(Z) has native disjunction and nondeterministic choice. The monotone refinement-type approach of Higher-Order Constrained Horn Clauses and Refinement Types lacks type-level intersection, which already makes it fail on the non-AC benchmark neg. This is the tension the research file flags between branching Diophantine solution sets and refinement types. We resolve it by choosing a target logic that can express branching.

Relation to Prior Work

Three lines of work motivate the gap, and all three treat data as free trees.

Verifying higher-order functional programs with pattern-matching algebraic data types extends recursion schemes with pattern matching over constructors. Its decidability argument relies on those constructors being free. We avoid pattern matching on bags entirely by matching on counts instead.

Higher-order Program Verification as Satisfiability Modulo Theories with Algebraic Data-types encodes closures as first-order data terms solved by SMT Horn solvers, and reports that solvers struggle to find invariants that select leaves inside recursive data. Defunctionalization of Higher-Order Constrained Horn Clauses makes that reduction sound and complete in DefMono. It pays 3.3 s versus 20 ms on max, and Z3 times out on a-max. HoCHC: a Refutationally-complete and Semantically-invariant System of Higher-order Logic Modulo Theories gives a complete calculus whose background theory is a first-order oracle with no equational reasoning. We do not modify any of these calculi. We change what the data becomes before solving.

The method comes from two places. The Diophantine view of AC comes from the papers above and from Universal Unification and Regular Equational ACFM Theories. The target solver is MuHFL, together with the HFL(Z) formulation in Higher-Order Program Verification via HFL Model Checking, where the program is encoded as a formula and the property as a small transition system.

Two negative results constrain the design. A Hierarchical Approach to Theorem-Proving shows that associativity without commutativity can yield infinitely many unifiers. The translation therefore applies only to genuinely AC operators such as bags, never to merely associative ones such as lists or streams. Equational Reasoning using AC Constraints shows that canonical sorting does not work for non-ground terms. We never sort; counts are canonical by construction.

Research Program

The first component is a front end for a small OCaml-like language with a built-in bag type. It provides empty, insert, union, count, a nondeterministic choose, and fold. The front end produces an HFL(Z) formula in which each bag value becomes $k$ integer variables.

Three operations need specific treatment.

  • choose. It becomes a nondeterministic pick of a class with positive count. Under that class, an element value is quantified over all integers satisfying the class predicate. This makes the translation an over-approximation when classes are coarse.
  • fold. It becomes integer recursion that consumes one element per step. This is the kind of recursion MuHFL handles through its bounded least-fixpoint unfoldings.
  • Patterns over bags. A pattern such as "two equal elements plus a rest" is compiled using Stickel-style variable/constant bags. Each minimal Diophantine solution becomes one disjunct. Following Experiments with Associative-Commutative Discrimination Nets, small solution sets (rank up to 5) are precomputed into tables rather than solved at translation time.

The second component is the left-commutativity check. For each closure reaching fold, we build a product program that runs f a (f b z) and f b (f a z) and asserts equal results. This is a safety query to MuHFL. If it succeeds, the bag is translated to counts. If it fails or times out, that bag falls back to an ordered list encoding, which is sound but less precise, and the user is told which closure blocked the translation.

The third component is class refinement. Initial classes come from constants and comparison predicates that appear in the program. When MuHFL returns a counterexample, we replay it against the concrete program. If it is spurious, we split the class responsible using an interpolant-style predicate drawn from the failing branch condition, and then iterate.

On the theory side, we will prove soundness of the translation and exactness on the count-determined, left-commutative fragment. We will also show that the translated formulas stay within the fragment MuHFL already targets, so that no completeness guarantees of the backend are lost.

Baselines

Do-nothing reference. The naive reference is DefMono from Defunctionalization of Higher-Order Constrained Horn Clauses with bags represented as lists. Order-independence properties are stated by running the program on two permuted inputs. This is what a user can do today without changing tools. A variant adds explicit associativity and commutativity axioms for the union symbol to the Z3 query. That is the "just axiomatize it" option, and we expect divergence there.

Strongest existing method. MuHFL from HFL(Z) Validity Checking for Automated Program Verification solves 73 of 87 instances on its own suite, against 53 for a combination of four specialized tools. We run it in two configurations:

  • List encoding. MuHFL on bags encoded as lists, with free terms simulated through its integer encoding of recursion.
  • Expert hand encoding. MuHFL on a hand-written count encoding produced by an author who is not running our tool. This is the real competitor, because it uses the same idea without automation.

On a bag benchmark, no reported result exists on Lacuna for either configuration. The only reported figure for this baseline is the 73/87 on the original suite.

Refinement-type baselines. HORUS from Higher-Order Constrained Horn Clauses and Refinement Types and RType/HoIce from ICE-Based Refinement Type Discovery for Higher-Order Functional Programs run on the list encoding. They represent the inference-of-invariants approach.

Fair-comparison protocol. Every tool receives the same source programs and properties. Each runs on one core with the same 300 s timeout and 8 GB memory per instance. No tool gets per-instance flags beyond its documented defaults. For the hand encoding, a fixed time budget per program is logged.

What counts as beating the baselines. We beat the naive and list baselines if we solve strictly more bag instances. We beat the hand encoding if we match it within a few instances while needing no manual work, and we also catch the unsound hand encodings that occur when the author silently assumes a non-commutative fold is commutative.

Ablations. Three ablations isolate the key ingredients:

  • Removing the left-commutativity check measures how often the count translation would wrongly accept a buggy program.
  • Freezing the initial classes, with no refinement, measures how much class refinement matters.
  • Replacing the Diophantine disjunct tables with an on-the-fly solver measures the cost of solving at translation time.

Why not just…?

Why not just add AC axioms to Z3 or a Horn solver? The file's evidence is that treating these laws as ordinary axioms makes provers swap and regroup terms indefinitely (A Hierarchical Approach to Theorem-Proving, Modal Theorem Proving: An Equational Viewpoint). Z3 already times out on a-max from closure nesting alone, without any AC axioms. We include this as an explicit baseline rather than assuming it fails. If it solves a meaningful fraction of the bag suite, the case for our tool weakens accordingly.

Why not just normalize bags by sorting their elements? Sorting gives canonical forms only for ground terms. With symbolic elements, the order is unknown, as Equational Reasoning using AC Constraints argues for non-ground terms. In higher-order verification nearly every element is symbolic. A sorted-list encoding also forces the solver to reason about sortedness invariants, which is the leaf-selection difficulty reported by Higher-order Program Verification as Satisfiability Modulo Theories with Algebraic Data-types. We test this directly with a sorted-insertion encoding fed to DefMono and MuHFL.

Why not just hand-encode bags as integer counts? This is the serious threat, and it is the same mathematical idea, so we do not argue against counting. A hand encoding has two problems. It is silently unsound when the folded closure is not order-insensitive. It is also brittle when elements come from infinite types, because someone must choose the classes. Our experiments compare against an expert hand encoding on identical programs. If automation solves the same instances and the mutant study shows hand encodings accepting buggy folds, the contribution stands. If hand encodings are as accurate and cheap, the honest conclusion is that the left-commutativity check and the class refinement are the only lasting contributions, and we would report them as such.

Why not just learn invariants with ICE-style refinement types? RType times out when the needed qualifiers are not mined (ICE-Based Refinement Type Discovery for Higher-Order Functional Programs). The needed qualifiers here are permutation invariants over lists, which are not linear predicates. Monotone refinement types also cannot express the disjunctive solution sets that AC matching produces, as the neg failure illustrates. Running RType/HoIce on the list encoding of the same suite settles this empirically.

Proposed Experiments

No existing benchmark targets higher-order programs over AC data, so we will build one and release it.

Bag suite. We aim for about 80 programs from three sources:

  • Ported programs. We port the programs behind the HoCHC suites (max, a-max, mc91, ack, hold, neg) and the MuHFL termination sets to versions that store intermediate data in bags. For example, a-max computes a maximum over a bag through a higher-order fold.
  • Order-independent algorithms. We write message-bag protocols and schedulers whose correctness is independent of order.
  • Equational workloads. We adapt symmetric rewriting workloads in the spirit of the ring problems used by Equational Reasoning using AC Constraints, recast as functional evaluators over commutative sums.

Mutants. Each correct program receives one or more buggy mutants. A typical mutant replaces a commutative folding closure with a non-commutative one such as subtraction or "keep the first element". This gives ground truth for soundness checks.

Regression suite. We also run the original 87 MuHFL instances, which contain no bags, to confirm that the front end adds no regression against the reported 73/87.

Metrics. We report instances proved safe, instances refuted with a genuine counterexample, timeouts, and wall-clock time. The most important metric is the number of mutants wrongly reported safe, which must be zero for our tool.

Decisive checks. Four results would settle the question:

  1. On programs with finite element types, the automatic translation solves every instance the expert hand encoding solves. A gap here would mean the translation loses precision on the fragment where it should be exact.
  2. On the ported a-max and max bag variants, we solve instances where DefMono with free terms times out or exceeds its reported 3.3 s on plain max.
  3. With the left-commutativity check disabled, a nonzero number of mutants are accepted. This shows the check is necessary, not decorative.
  4. On programs with integer elements, refinement converges in a small number of class splits on most instances. Where it diverges, we expect the property to depend on the element values themselves rather than on per-class counts.

A negative outcome on the second or fourth check would tell us exactly where counting stops being enough.