- |
    Augustus Odena[^1]\
    Google Brain\
    `augustusodena@google.com`\
    Kensen Shi\
    Google Brain\
    `kshi@google.com`\
    David Bieber\
    Google Brain\
    Rishabh Singh\
    Google Brain\
    Charles Sutton\
    Google Brain\
bibliography:
- 'neurips\_2020.bib'
title: 'BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration'
---

Introduction
============

Program synthesis is a longstanding goal of artificial intelligence research  [@mannaw71; @summers1977methodology], but it remains difficult in part because of the challenges of search [@sygus; @now17]. The objective in program synthesis is to automatically write a program given a specification of its intended behaviour, and current state of the art methods typically perform some form of search over a space of possible programs. Many different search methods have been explored in the literature, both with and without learning. These include search within a version-space algebra [@FLASHFILL], bottom-up enumerative search [@TRANSIT], stochastic search [@stoke], genetic programming [@koza1994genetic], reducing the synthesis problem to logical satisfiability [@SKETCH], beam search within a sequence-to-sequence neural network [@ROBUSTFILL], learning to perform premise selection to guide search [@DEEPCODER], learning to prioritize grammar rules within top-down search [@EUPHONY], and learned search based on partial executions [@REPL; @GARBAGECOLLECTOR; @ChenLS19].

While these approaches have yielded significant progress, none of them completely capture the following important intuition: human programmers routinely write complex programs by 