Lune

PLDI2020Top-tier venue

Reconciling enumerative and deductive program synthesis

Kangjing Huang, Xiaokang Qiu, Peiyuan Shen, Yanjun Wang

Abstract

Syntax-guided synthesis (SyGuS) aims to find a program satisfying semantic specification as well as user-provided structural hypotheses. There are two main synthesis approaches: enumerative synthesis, which repeatedly enumerates possible candidate programs and checks their correctness, and deductive synthesis, which leverages a symbolic procedure to construct implementations from specifications. Neither approach is strictly better than the other: automated deductive synthesis is usually very efficient but only works for special grammars or applications; enumerative synthesis is very generally applicable but limited in scalability.

In this paper, we propose a cooperative synthesis technique for SyGuS problems with the conditional linear integer arithmetic (CLIA) background theory, as a novel integration of the two approaches, combining the best of the two worlds. The technique exploits several novel divide-and-conquer strategies to split a large synthesis problem to smaller subproblems. The subproblems are solved separately and their solutions are combined to form a final solution. The technique integrates two synthesis engines: a pure deductive component that can efficiently solve some problems, and a height-based enumeration algorithm that can handle arbitrary grammar. We implemented the cooperative synthesis technique, and evaluated it on a wide range of benchmarks. Experiments showed that our technique can solve many challenging synthesis problems not possible before, and tends to be more scalable than state-of-the-art synthesis algorithms. * The author list has been sorted according to the alphabetical order; this should not be used to determine the extent of authors' contributions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

22 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Bottom-up synthesis of recursive functional programs using angelic execution cites Combining the top-down propagation and bottom-up enumeration for inductive program synthesis
  • FlashFill++: Scaling Programming by Example by Cutting to the Chase cites Combining the top-down propagation and bottom-up enumeration for inductive program synthesis
  • FlashFill++: Scaling Programming by Example by Cutting to the Chase cites Multi-modal program inference: a marriage of pre-trained language models and component-based synthesis
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers22

  1. Bottom-up synthesis of recursive functional programs using angelic executionAnders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri et al.POPL 2022 · 38 citations
  2. Combining the top-down propagation and bottom-up enumeration for inductive program synthesisWoosuk LeePOPL 2021 · 34 citations
  3. Multi-modal program inference: a marriage of pre-trained language models and component-based synthesisKia Rahmani, Mohammad Raza, Sumit Gulwani, Vu Le et al.OOPSLA 2021 · 32 citations
  4. Synthesizing safe and efficient kernel extensions for packet processingQiongwen Xu, Michael D. Wong, Tanvi Wagle, Srinivas Narayana et al.SIGCOMM 2021 · 30 citations
  5. FlashFill++: Scaling Programming by Example by Cutting to the ChaseJosé Cambronero, Sumit Gulwani, Vu Le, Daniel Perelman et al.POPL 2023 · 27 citations

Related papers

  1. Exact and approximate methods for proving unrealizability of syntax-guided synthesis problemsQinheping Hu, John Cyphert, Loris D'Antoni, Thomas W. RepsPLDI 2020 · 22 citations
  2. Inductive Program Synthesis via Iterative Forward-Backward Abstract InterpretationYongho Yoon, Woosuk Lee, Kwangkeun YiPLDI 2023 · 15 citations
  3. Guiding Enumerative Program Synthesis with Large Language ModelsYixuan Li, Julian Parsert, Elizabeth PolgreenCAV 2024 · 19 citations
  4. Just-in-time learning for bottom-up enumerative synthesisShraddha Barke, Hila Peleg, Nadia PolikarpovaOOPSLA 2020 · 33 citations
  5. Enhanced Enumeration Techniques for Syntax-Guided Synthesis of Bit-Vector ManipulationsYuantian Ding, Xiaokang QiuPOPL 2024 · 10 citations
Dusk over the sea between two cliffs drawn in fine vertical lines