License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SNAPL.2017.16
URN: urn:nbn:de:0030-drops-71284
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7128/
Go to the corresponding LIPIcs Volume Portal


Singh, Rishabh ; Kohli, Pushmeet

AP: Artificial Programming

pdf-format:
LIPIcs-SNAPL-2017-16.pdf (0.9 MB)


Abstract

The ability to automatically discover a program consistent with a given user intent (specification) is the holy grail of Computer Science. While significant progress has been made on the so-called problem of Program Synthesis, a number of challenges remain; particularly for the case of synthesizing richer and larger programs. This is in large part due to the difficulty of search over the space of programs. In this paper, we argue that the above-mentioned challenge can be tackled by learning synthesizers automatically from a large amount of training data. We present a first step in this direction by describing our novel synthesis approach based on two neural architectures for tackling the two key challenges of Learning to understand partial input-output specifications and Learning to search programs. The first neural architecture called the Spec Encoder computes a continuous representation of the specification, whereas the second neural architecture called the Program Generator incrementally constructs programs in a hypothesis space that is conditioned by the specification vector. The key idea of the approach is to train these architectures using a large set of (spec,P) pairs, where P denotes a program sampled from the DSL L and spec denotes the corresponding specification satisfied by P. We demonstrate the effectiveness of our approach on two preliminary instantiations. The first instantiation, called Neural FlashFill, corresponds to the domain of string manipulation programs similar to that of FlashFill. The second domain considers string transformation programs consisting of composition of API functions. We show that a neural system is able to perform quite well in learning a large majority of programs from few input-output examples. We believe this new approach will not only dramatically expand the applicability and effectiveness of Program Synthesis, but also would lead to the coming together of the Program Synthesis and Machine Learning research disciplines.

BibTeX - Entry

@InProceedings{singh_et_al:LIPIcs:2017:7128,
  author =	{Rishabh Singh and Pushmeet Kohli},
  title =	{{AP: Artificial Programming}},
  booktitle =	{2nd Summit on Advances in Programming Languages (SNAPL 2017)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-032-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{71},
  editor =	{Benjamin S. Lerner and Rastislav Bod{\'i}k and Shriram Krishnamurthi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7128},
  URN =		{urn:nbn:de:0030-drops-71284},
  doi =		{10.4230/LIPIcs.SNAPL.2017.16},
  annote =	{Keywords: Neural Program Synthesis, Neural Programming, Neural FlashFill}
}

Keywords: Neural Program Synthesis, Neural Programming, Neural FlashFill
Seminar: 2nd Summit on Advances in Programming Languages (SNAPL 2017)
Issue Date: 2017
Date of publication: 30.04.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI