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:
- Transformation: "Multiple-callsign" instances—where a function is invoked multiple times with different arguments—are handled via an Ackermannization-style transformation.
- 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.
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.
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