Program Synthesis as Dependency Quantified Formula Modulo Theory

Priyanka Golia, Subhajit Roy, Kuldeep S. Meel

TL;DR

This paper proposes a new approach to program synthesis by reducing the problem of "T-constrained synthesis" (synthesizing programs within a specific theory without explicit grammar constraints) to Dependency Quantified Formulas Modulo Theory (DQF(T)). For the common case of bitvector theories, this further reduces to Dependency Quantified Boolean Formulas (DQBF), enabling the use of powerful existing DQBF solvers. The authors demonstrate that this DQBF-based approach significantly outperforms traditional syntax-guided synthesis and matches the performance of domain-specific synthesis techniques.

What Problem Does This Paper Address?

Program synthesis aims to automatically generate a program that fulfills a given specification. A popular technique, Syntax-Guided Synthesis (SyGuS), uses a grammar to constrain the search space of possible programs, making synthesis more tractable. However, this approach requires the user to provide a grammar, which might not always be readily available or might be overly restrictive. This paper addresses the challenge of program synthesis without relying on explicit grammar constraints. They introduce "T-constrained synthesis," where the only constraints are the specification and the underlying background theory (e.g., bitvectors). The core problem is to find an efficient and effective way to perform this T-constrained synthesis, especially when dealing with complex theories.

Methods

The paper's main contribution is a reduction from T-constrained synthesis to Dependency Quantified Formulas Modulo Theory (DQF(T)). This reduction is achieved in two main steps:

  1. T-constrained Synthesis to DQF(T): The authors formalize T-constrained synthesis and show how it can be transformed into finding a witness for a DQF(T) formula. This involves carefully constructing Henkin quantifiers to represent the dependencies of the synthesized functions. They handle cases with single and multiple function call signatures, using an "Ackermannization-style technique" to transform multiple-callsign functions into single-callsign ones.
  2. DQF(BV) to DQBF: For the specific and widely used theory of bitvectors (BV), the DQF(BV) problem is further reduced to Dependency Quantified Boolean Formulas (DQBF). This reduction involves a "bit-blasting" process, where bitvector variables are converted into propositional variables. This allows leveraging the significant advancements in state-of-the-art DQBF solvers.

The authors then build DQBF-based synthesizers by plugging these reduced DQBF instances into existing DQBF solvers.

Datasets

The paper uses benchmarks from two sources for evaluation:

  • SyGuS competition: 645 general-track bitvector (BV) theory benchmarks.
  • QBF competition: 609 QBF benchmarks, which were converted to SyGuS instances.

These benchmarks were used to compare the performance of SyGuS tools, BV-constrained synthesis, and DQBF-based synthesis frameworks.

Key Insights and Ideas

  • DQBF as a Unified Representation: The paper strongly advocates for DQBF as a powerful and general representation language for program synthesis, particularly for T-constrained synthesis. They show that by reducing the problem to DQBF, existing, highly optimized DQBF solvers can be directly applied, achieving impressive results.
  • T-constrained Synthesis Outperforms Syntax-Guided Synthesis: Surprisingly, their empirical evaluation shows that T-constrained synthesis (when implemented using DQBF solvers) can outperform traditional syntax-guided synthesis (SyGuS) in terms of the number of instances solved. This suggests that explicit grammar constraints might not always be beneficial and can sometimes hinder performance.
  • Grammar as a Specification Tool, Not Just a Search Aid: The authors propose a shift in thinking about grammars in synthesis. Instead of solely using them to guide the search strategy, they suggest viewing them more as a specification tool, potentially for richer properties like information flow.
  • Leveraging General-Purpose Solvers: The success of their DQBF-based approach highlights the power of general-purpose automated reasoning tools. By reducing a domain-specific problem (program synthesis) to a general one (DQBF), they achieve significant performance gains.

Key Results

The experimental evaluation demonstrated the effectiveness of their DQBF-based approach:

  • SyGuS Instances:
    • Syntax-guided synthesis (SyGuS) tools solved 513 out of 645 instances.
  • BV-constrained synthesis (using CVC4cex) solved 606 instances.
  • DQBF-based synthesis solved 610 instances.
  • QBF Instances:
    • DQBF-based synthesis solved 276 out of 609 instances (with a 900s timeout).
  • Performance Comparison: DQBF-based synthesizers consistently performed as well as or better than domain-specific synthesis techniques, including BV-constrained synthesis and SyGuS tools. For instance, in the BV-constrained category, CVC4cex solved 602 instances, while the DQBF-based approach (represented by CADET, Manthan, DepQBF, DQBDD, DCAQE) solved 610 instances.
  • BV-constrained Synthesis Inefficiency for DQBF: The paper concludes that BV-constrained synthesis is not an efficient approach for DQBF solving, answering RQ3.

Limitations and Future Work

  • Theory Restriction: The primary empirical evaluation focused on the bitvector (BV) theory. The authors acknowledge that evidence for theories beyond bitvectors is needed to fully support their hypothesis that DQBF is a general representation language for T-constrained synthesis.
  • Future Work:
    • General DQF(T) Techniques: Design techniques for DQF(T) beyond the specific case of BV, to explore a wider range of theories.
  • Optimizations in Bit-blasting: The paper mentions that optimizations for Henkin functions during the bit-blasting process were left for future work, suggesting potential performance improvements.
  • Richer Specifications: Motivate the study of synthesis formulations with richer specifications, potentially incorporating hyper-properties, inspired by the idea of using grammars for information flow properties.
  • Theoretical Analysis: A detailed theoretical analysis of the reduction and its implications (e.g., Fixed Parameter Tractability) is suggested for future work.

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},
}

Loading related content...

Figure