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

  1. Percy Liang
  2. Luke S. Zettlemoyer
  3. Mohit Bansal
  4. Graham Neubig
  5. Quoc V. Le
  6. Yoshua Bengio
  7. Jianfeng Gao
  8. Sergey Levine

In Computational Theory and Mathematics

  1. Armando Solar-Lezama
  2. Sumit Gulwani
  3. Rishabh Singh
  4. Oleksandr Polozov
  5. Martin T. Vechev
  6. Veselin Raychev
  7. Emina Torlak
  8. Rastislav Bodík

In Information Systems

  1. Rishabh Singh
  2. Miltiadis Allamanis
  3. Charles Sutton
  4. Swarat Chaudhuri
  5. Eran Yahav
  6. Michael Pradel
  7. C. Jermaine
  8. Sumit Gulwani

In Natural Language Processing

  1. Percy Liang
  2. Rishabh Singh
  3. Luke S. Zettlemoyer
  4. Charles Sutton
  5. Dawn Song
  6. Josh Tenenbaum
  7. Sebastian Riedel
  8. Graham Neubig

In Code Generation & Program Synthesis

  1. Rishabh Singh
  2. Swarat Chaudhuri
  3. Charles Sutton
  4. Sumit Gulwani
  5. Eran Yahav
  6. C. Jermaine
  7. Armando Solar-Lezama
  8. Miltiadis Allamanis

Citations in the corpus