Combinatorial sketching for finite programs
By Armando Solar-Lezama, Liviu Tancau, Rastislav Bodík, Sanjit A. Seshia, Vijay A. Saraswat. 2006
889 citations recorded by the source corpus.
Sketching is a software synthesis approach where the programmer develops a partial implementation - a sketch - and a separate specification of the desired functionality. The synthesizer then completes the sketch to behave like the specification. The correctness of the synthesized implementation is guaranteed by the compiler, which allows, among other benefits, rapid development of highly tuned implementations without the fear of introducing bugs.We develop SKETCH, a language for finite programs with linguistic support for sketching. Finite programs include many highperformance kernels, including cryptocodes. In contrast to prior synthesizers, which had to be equipped with domain-specific rules, SKETCH completes sketches by means of a combinatorial search based on generalized boolean satisfiability. Consequently, our combinatorial synthesizer is complete for the class of finite programs: it is guaranteed to complete any sketch in theory, and in practice has scaled to realistic programming problems.Freed from domain rules, we can now write sketches as simpleto-understand partial programs, which are regular programs in which difficult code fragments are replaced with holes to be filled by the synthesizer. Holes may stand for index expressions, lookup tables, or bitmasks, but the programmer can easily define new kinds of holes using a single versatile synthesis operator.We have used SKETCH to synthesize an efficient implementation of the AES cipher standard. The synthesizer produces the most complex part of the implementation and runs in about an hour.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Natural Language Processing, Code Generation & Program Synthesis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- Luke S. Zettlemoyer
- Mohit Bansal
- Graham Neubig
- Quoc V. Le
- Yoshua Bengio
- Jianfeng Gao
- Sergey Levine
In Computational Theory and Mathematics
- Armando Solar-Lezama
- Sumit Gulwani
- Rishabh Singh
- Oleksandr Polozov
- Martin T. Vechev
- Veselin Raychev
- Emina Torlak
- Rastislav Bodík
In Information Systems
- Rishabh Singh
- Miltiadis Allamanis
- Charles Sutton
- Swarat Chaudhuri
- Eran Yahav
- Michael Pradel
- C. Jermaine
- Sumit Gulwani
In Natural Language Processing
- Percy Liang
- Rishabh Singh
- Luke S. Zettlemoyer
- Charles Sutton
- Dawn Song
- Josh Tenenbaum
- Sebastian Riedel
- Graham Neubig
In Code Generation & Program Synthesis
- Rishabh Singh
- Swarat Chaudhuri
- Charles Sutton
- Sumit Gulwani
- Eran Yahav
- C. Jermaine
- Armando Solar-Lezama
- Miltiadis Allamanis
Citations in the corpus
- SPoC: Search-based Pseudocode to Code (2019, methodology): “The most focused and effective method is to formulate synthesis as a constraint satisfaction problem [32, 33], which requires that the synthesis problem can be translated to a theory with effective constraint solvers.”
- InCoder: A Generative Model for Code Infilling and Synthesis (2022, background): “, input-output examples [12, 28, 19, 13], partial implementations [58], or natural language descriptions [74, 73, 72, 42, 18] of the desired program as input.”
- Programming with a Differentiable Forth Interpreter (2016, background): “Whereas a large body of work has focused on using genetic programming (Koza, 1992) to induce programs from the given inputoutput specification (Nordin, 1997), there are also various Inductive Programming approaches (Kitzelmann, 2009) aimed at inducing programs from incomplete specifications of the c”
- Syntax-guided synthesis (2013, methodology): “It is possible that, after some number of iterations of this loop, the learning algorithm may be unable to find a candidate concept consistent with its current set of (positive/negative) examples, in which case the learning step, and hence the overall CEGIS procedure, fails.”
- Data-Driven Program Completion (2017, methodology): “However, none of these methods are comparable, because (1) traditional synthesis methods such as Sketch do not search for or use existing source code, (2) code reuse methods only consider programs at the granularity of functions instead of more ne-grained level such as statements and expressions and”
- A review of generalized planning (2019, background): “a program that expresses the high-level structure of an implementation but that leaves low level details undefined to be determined by the synthesizer [89].”
- Program Synthesis Using Natural Language (2015, background): “Traditional program synthesis, synthesizing programs from complete specifications [18, 35, 51, 52], has not yet seen wide adoption due to the difficultly of writing such specifications and verifying the synthesized program satisfies this specification.”
- Automated Correction for Syntax Errors in Programming Assignments using Recurrent Neural Networks (2016, methodology): “AutoProf uses constraint-based synthesis techniques [19] for finding minimum number of changes (guided by an error model) in the incorrect student submission to make it functionally equivalent to the reference implementation.”
- Program sketching (2012, methodology): “As a case study [19], we used the Sketch synthesizer to create a full implementation of the AES cipher [7] by synthesizing its most difficult fragments.”
- Snuba: Automating Weak Supervision to Label Training Data (2018, methodology): “The design is based loosely on counter-example guided inductive synthesis (CEGIS) in which a synthesizer generates programs, passes it to the verifier that decides whether the candidate program satisfies the given specifications, and passes relevant feedback to the synthesizer [46, 16, 22, 48].”
- Synthesizing coupling proofs of differential privacy (2017, methodology): “Specifically, we use counterexample-guided inductive synthesis (cegis) [40] to discover a strategy f , and predicate abstraction [25] to prove that f is a winning strategy.”
- A large-scale benchmark for few-shot program induction and synthesis (2021, background): “Few-shot program induction and synthesis Program synthesis (Shaw et al., 1975; Solar-Lezama et al., 2006; Gulwani et al., 2017) aims at generating code that satisfies a set of input-output examples.”
- BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration (2020, background): “, 2013), genetic programming (Koza, 1994), reducing the synthesis problem to logical satisfiability (Solar-Lezama et al., 2006), beam search within a sequence-to-sequence neural network (Devlin et al.”
- SQLNet: Generating Structured Queries From Natural Language Without Reinforcement Learning (2017, methodology): “Our approach can be viewed as a neural network alternative to the traditional sketch-based program synthesis approaches (Alur et al., 2013; Solar-Lezama et al., 2006; Bornholt et al., 2016).”
- Synthesis of loop-free programs (2011, methodology): “Sketching Sketching [32, 33, 31] relies on the developer to come up with the algorithmic insight and uses the sketch compiler to fill in missing details using counterexample guided inductive synthesis.”