Scaling Neural Program Synthesis with Distribution-based Search

Writing software is tedious, error-prone, and accessible only to a small share of the population - yet coding grows increasingly important as the digital world plays larger and larger roles in peoples' lives. Program synthesis seeks to make coding more reliable and accessible by developing methods for automatically constructing programs Gulwani et al. (2017). For example, the FlashFill system Gulwani et al. (2017) in Microsoft Excel makes coding more accessible by allowing nontechnical users to synthesize spreadsheet programs by giving inputoutput examples, while the TF-coder system Shi et al. (2020a) seeks to make coding neural networks more reliable by synthesizing TensorFlow code from input-outputs. Where these systems have been most successful is when they pair a specialized domain-specific language (DSL) to a domain-specific search algorithm for synthesizing programs in that DSL. A recent trend - both in industry Kalyan et al. (2018) and academia Devlin et al. (2017) - is to employ machine learning methods to learn to quickly search for a program in the DSL Balog et al. (2017); Devlin et al. (2017); Lee et al. (2018); Zhang et al.