Library Learning for Neurally-Guided Bayesian Program Induction
Successful approaches to program induction require a hand-engineered domainspecific language (DSL), constraining the space of allowed programs and imparting prior knowledge of the domain. We contribute a program induction algorithm called EC 2 that learns a DSL while jointly training a neural network to efficiently search for programs in the learned DSL. We use our model to synthesize functions on lists, edit text, and solve symbolic regression problems, showing how the model learns a domain-specific library of program components for expressing solutions to problems in the domain.
= Summary  A method for learning a DSL for program synthesis together with a search algorithm in that DSL is presented. The method proceeds iteratively, trying to solve tasks with the current DSL, and then extracting new DSL components from the solutions. Experiments show that bootstrapping the method with a DSL made up of trivial primitives is sufficient to discover common high-level constructs present in manually constructed DSLs.  The paper tackles an important problem (DSL design) in an elegant and novel way. The clarity of the paper is not perfect, as the details of the idea require more space than the 8 pages available, but it clearly is stepping stone towards a new generation of program synthesis approaches.  = Quality  The paper precisely defines its main algorithm and the core concepts of the approach. There are a few omissions (e.g., Sect. 2.4 does not explain the exact mechanism to extract new constructs; the supplement gives an algorithm, but omits a clear definition of how "fragments" are found), but overall the paper is precise and explains core concepts well. The experiments are very thorough, comparing the method to interesting ablations and baselines. What I am missing is an analysis of the influence of the initial set of primitives. For example, the list processing set starts with a non-minimal set of primitives (as length is "foldr (\lambda (n) -> 1 + n) 0" and index can be implemented using the others as well, though painfully). What happens, for example, if length is removed?  As an additional data point, I would have appreciated a look at the "evolution" of solutions to a fixed task through the iterations of the main algorithm, i.e., show an initial, early and late solution in the style of Table 1.  = Clarity  Many part of the paper are better understood with the supplement in hand (Sect. 2.3 is not discussing details of how q is modeled, but Supplement Sect. 5 makes clear that is is essentially like DeepCoder; Sect. 2.4 is missing details as discussed above). Overall, the paper is easily understood, but not entirely self-contained and not precise enough to allow re-implementation by third parties.  The supplement is very unpolished (there are many grammatical errors and half-finished sentences, e.g. in line 6, line 33, lines 45/46, ...)  = Originality  While drawing on the program synthesis literature of the last few years (e.g., the guided enumerative search), the core contributions of the paper are completely new and are a substantial step forward for the field.  = Significance  Designing a suitable DSL is often one of the hardest tasks in applying program synthesis to a new domain; the promise of automatically learning a DSL (together with a search algorithm) is obvious. I am not entirely convinced by the authors idea of generalizing to other generative programs, but I am looking forward to being proven wrong.