Program Synthesis as Dependency Quantified Formula Modulo Theory

Priyanka Golia, Subhajit Roy, Kuldeep S. Meel

Abstract

Program synthesis—the automatic generation of code from logical specifications—has traditionally relied on syntax-guided approaches that use grammars to constrain the search space. This paper proposes a paradigm shift by framing "grammar-free" synthesis as a problem of solving Dependency Quantified Formulas (DQF). By reducing synthesis tasks to DQF and leveraging modern solvers, the authors demonstrate that general-purpose logic engines can outperform specialized, domain-specific synthesis tools, particularly in bitvector theory.

Introduction

In the dominant Syntax-Guided Synthesis (SyGuS) paradigm, users provide both a logical specification and a grammar. While grammars help narrow the search space, they often act as a "crutch" for solvers rather than representing true program constraints. This research investigates $\mathbb{T}$-constrained synthesis, aiming to find programs using the entire vocabulary of a background theory (e.g., bitvectors) without restrictive user-defined grammars. The central question is whether powerful, general-purpose logic solvers can handle the resulting search space explosion by skipping the grammar entirely.

Methodology: From Synthesis to DQF

The authors propose a reduction from program synthesis to Dependency Quantified Formula Modulo Theory (DQF($\mathbb{T}$)). The approach involves two primary steps:

  1. Transformation: "Multiple-callsign" instances—where a function is invoked multiple times with different arguments—are handled via an Ackermannization-style transformation.
  2. Logical Mapping: The synthesis specification is mapped to a DQF($\mathbb{T}$) formula. The core of DQF is the use of Henkin quantifiers, which explicitly define that an output variable $y$ depends only on a specific subset of input variables $x$, perfectly mirroring functional dependencies in programming.

For Bitvector theory (BV), the authors "bit-blast" the DQF(BV) formula into a Dependency Quantified Boolean Formula (DQBF). This pipeline is implemented in a tool called DeQuS, which utilizes off-the-shelf DQBF solvers like CADET and Manthan.

Experimental Evaluation

The approach was evaluated on two major benchmark sets:

  • SyGuS Competition (2018, 2019): 645 bitvector theory benchmarks from the general track.
  • QBFEval (17, 18): 609 benchmarks originally for Quantified Boolean Formula solving, converted into SyGuS instances to test versatility.

Results and Key Insights

The empirical results demonstrate that DQBF solvers are reaching a level of maturity where they can serve as a core representation language for synthesis, similar to the "SAT revolution" in planning during the 1990s.

Table 1: Comparison of solved instances across SyGuS and DQBF benchmarks.

As shown in the results table, the DQBF-based approach solved 610 out of 645 SyGuS benchmarks, significantly outperforming standard syntax-guided tools which solved 513. Furthermore, the "native" theory-constrained approach (CVC4's quantifier instantiation) solved 606 instances, confirming that moving away from restrictive grammars is a viable and often superior path.

A more granular breakdown of performance based on problem complexity (Single vs. Multiple Functions and CallSigns) highlights the strengths of different solver types.

Table 2: Performance breakdown by function and callsign complexity.

Surprisingly, specialized synthesis tools often perform worse when given a broad grammar (the full theory vocabulary) compared to how general-purpose DQBF solvers handle the same "grammar-free" problem. Despite DQBF being NEXPTIME-complete, modern heuristics make these solvers remarkably effective on practical synthesis instances.

Conclusion and Future Work

While highly successful for Bitvector theory, the current approach faces limitations. Bit-blasting to DQBF can be computationally expensive due to auxiliary variable overhead. Future work will explore extending these results to other theories like Integers, Strings, or Arrays. A primary goal is the development of native DQF($\mathbb{T}$) solvers that can handle higher-level theories directly, bypassing the need for bit-blasting to the Boolean level.

Summary updated

Abstract

Given a specification $\varphi(X,Y)$ over inputs $X$ and output $Y$, defined over a background theory $\mathbb{T}$, the problem of program synthesis is to design a program $f$ such that $Y=f(X)$ satisfies the specification $\varphi$. Over the past decade, syntax-guided synthesis (SyGuS) has emerged as a dominant approach for program synthesis where in addition to the specification $\varphi$, the end-user also specifies a grammar $L$ to aid the underlying synthesis engine. This paper investigates the feasibility of synthesis techniques without grammar, a sub-class defined as $\mathbb{T}$-constrained synthesis. We show that $\mathbb{T}$-constrained synthesis can be reduced to DQF($\mathbb{T}$), i.e., to the problem of finding a witness of a Dependency Quantified Formula Modulo Theory. When the underlying theory is the theory of bitvectors, the corresponding DQF(BV) problem can be further reduced to Dependency Quantified Boolean Formulas (DQBF). We rely on the progress in DQBF solving to design DQBF-based synthesizers that outperform the domain-specific program synthesis techniques, thereby positioning DQBF as a core representation language for program synthesis. Our empirical analysis shows that $\mathbb{T}$-constrained synthesis can achieve significantly better performance than syntax-guided approaches. Furthermore, the general-purpose DQBF solvers perform on par with domain-specific synthesis techniques.
BibTeX
@inproceedings{golia2021program,
  author = {Priyanka Golia and Subhajit Roy and Kuldeep S. Meel},
  title = {{Program Synthesis as Dependency Quantified Formula Modulo Theory}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/261},
}
Figure