---
abstract: 'Program synthesis is challenging largely because of the difficulty of search in a large space of programs. Human programmers routinely tackle the task of writing complex programs by writing sub-programs and then analysing their intermediate results to compose them in appropriate ways. Motivated by this intuition, we present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This is a powerful combination because of several emergent properties: First, in bottom-up search, intermediate programs can be executed, providing semantic information to the neural network. Second, given the concrete values from those executions, we can exploit rich features based on recent work on property signatures. Finally, bottom-up search allows the system substantial flexibility in what order to generate the solution, allowing the synthesizer to build up a program from multiple smaller sub-programs. Overall, our empirical evaluation finds that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches. We demonstrate the effectiveness of our technique on a new data set for synthesis of string transformation programs.'
author:
- |
    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 first writing sub-programs and then analysing their intermediate results to compose them in appropriate ways. We propose a new learning-guided system for synthesis, called [<span style="font-variant:small-caps;">Bustle</span>]{}, which follows this intuition in perhaps the simplest way possible. Given a specification of a program’s intended behavior (in this paper given by input-output examples), [<span style="font-variant:small-caps;">Bustle</span>]{} performs bottom-up enumerative search for a satisfying program, following [@TRANSIT]. Each program explored during the bottom-up search is an expression that can be executed on the inputs, so we apply a machine learning model to the resulting value to guide the search. The model is simply a classifier trained to predict whether the intermediate value produced by a partial program is part of an eventual solution. This combination of learning and bottom up search has several key advantages. First, because the input to the model is a value produced by executing a partial program, the model’s predictions can depend on semantic information about the program. Second, because the search is bottom-up, compared to previous work on execution-guided synthesis, the search procedure has flexibility about which order to generate the program in, and this flexibility can be exploited by machine learning.

One big challenge with this approach is that exponentially many intermediate programs are explored during search, so the model needs to be both very fast and very accurate to yield wall-clock time speed-ups. We are allowed to incur some slowdown, because if the model is accurate enough, we can search many fewer values before finding solutions. However, executing a program is still orders of magnitude faster than performing inference on even a small machine learning model, so this problem is severe. We employ two techniques to deal with this: First, we arrange both the synthesizer and the model so that we can batch model prediction across hundreds of intermediate values. Second, we process intermediate expressions using property signatures [@SIGNATURES], which featurize program inputs using another set of programs.

A second big challenge is that neural networks require large amounts of data to train, but there is no available data source of intermediate expressions. We can generate programs at random to train the model following previous work [@DEEPCODER; @ROBUSTFILL], but models trained on random programs do not always transfer to human-written benchmarks [@shin2019-sv]. We show that our use of property signatures helps with this distribution mismatch problem as well.

In summary, this paper makes the following contributions:

-   We present [<span style="font-variant:small-caps;">Bustle</span>]{}, which integrates machine learning into bottom-up program synthesis.

-   We show how to efficiently add machine learning in the synthesis loop using property signatures and batched predictions. With these techniques, adding the model to the synthesizer provides an end-to-end improvement in synthesis time.

-   We present an evaluation on a synthesis task of string transformations. We show that [<span style="font-variant:small-caps;">Bustle</span>]{} leads to improvements in synthesis time compared to a baseline synthesizer without learning, a Deepcoder-style learning-based synthesizer [@DEEPCODER], and a hand-designed set of heuristics. Even though our model is trained on random programs, we show that the model’s performance transfers to a set of human-written synthesis benchmarks.

Background and Setup
====================

Programming by Example
----------------------

In a Programming-by-Example (PBE) task [@PBE; @MLPBE; @FLASHFILL], we are given a set of input/output pairs and the goal is to find a program such that for each pair, the synthesized program when executed on the input generates the corresponding output. To restrict the search space, the programs are typically restricted to a small domain-specific language (DSL). As an example PBE specification, consider the “io\_pairs” given in Listing \[listing:benchmarks\].

Our String Transformation DSL
-----------------------------

Following previous work [@FLASHFILL; @ROBUSTFILL], we deal with string and number transformations commonly used in spreadsheets. Such transformations sit at a nice point on the complexity spectrum as a benchmark task; they are simpler than programs in general purpose languages, but still expressive enough for many common string transformation tasks.

The domain-specific language we use (shown in Figure \[fig:sheets\_dsl\]) is broadly similar to those of [@parisotto2017neuro] and [@ROBUSTFILL], but compared to these, our DSL is expanded in several ways that make the synthesis task more difficult: First, our DSL includes integers and integer arithmetic. Second, our DSL allows for arbitrarily nested expressions, rather than having a maximum size. Finally, and most importantly, our DSL removes the restriction of having [`Concat`]{} at the top-level, as is the case in previous works [@FLASHFILL; @ROBUSTFILL]. Without this constraint, version-space-based and dynamic-programming-based beam search approaches cannot exploit the prefix-output property to prune partial programs during search.

Our DSL allows for nesting and compositions of common string transformation functions. These functions include string concatenation ([`Concat`]{}) and other familiar string operations (see Supplementary Material for a full list). Integer functions include arithmetic, returning the index of the first occurrence of a substring within a string ([`Find`]{}), and string length. Finally, a few commonly useful string and integer constants are included.

$$\begin{aligned}
{2}
\mbox{Expression } E &:= \: && S {\; | \;}I \\
\mbox{String expression } S &:= && {\texttt{Concat}}(S_1, S_2) {\; | \;}{\texttt{Left}}(S, I) {\; | \;}{\texttt{Right}}(S, I) {\; | \;}{\texttt{Substr}}(S, I_1, I_2) \\
& && 
{\; | \;}{\texttt{Replace}}(S_1, I_1, I_2, S_2) {\; | \;}{\texttt{Trim}}(S) {\; | \;}{\texttt{Repeat}}(S, I) {\; | \;}{\texttt{Substitute}}(S_1, S_2, S_3)
\\ & && {\; | \;}{\texttt{Substitute}}(S_1, S_2, S_3, I) {\; | \;}{\texttt{ToText}}(I) {\; | \;}{\texttt{LowerCase}}(S) {\; | \;}{\texttt{UpperCase}}(S)
\\ & && {\; | \;}{\texttt{ProperCase}}(S) {\; | \;}T {\; | \;}X \\
\mbox{Integer expression } I &:= && I_1 + I_2 {\; | \;}I_1 - I_2 {\; | \;}{\texttt{Find}}(S_1, S_2) {\; | \;}{\texttt{Find}}(S_1, S_2, I) {\; | \;}{\texttt{Len}}(S) {\; | \;}J {\; | \;}X  \\
\mbox{String constants } T &:= && \mbox{\textvisiblespace} {\; | \;}{\texttt{,}} {\; | \;}{\texttt{.}} {\; | \;}{\texttt{-}} {\; | \;}{\texttt{/}} \\
\mbox{Integer constants } J &:= &&  0 {\; | \;}1 {\; | \;}2 {\; | \;}3 {\; | \;}99 \\
\mbox{Input } X &:= && x_1 {\; | \;}\ldots {\; | \;}x_k\end{aligned}$$

Bottom-Up Synthesis
-------------------

The baseline synthesizer on top of which we build our approach is a bottom-up enumerative search inspired by [@TRANSIT], which enumerates DSL expressions from smallest to largest. The search follows Algorithm \[alg:search\] if the lines colored in blue (\[alg:bustle\_line\_1\], \[alg:bustle\_line\_2\], and \[alg:bustle\_line\_3\]) are removed. This baseline uses a *value-based* search: during the search, each candidate expression is executed to see if it meets the specification. Then, rather than storing the expressions that have been produced in the search, we store the values produced by executing the expressions. This allows the search to avoid separately extending sub-expressions that are semantically equivalent on the given input examples.

More specifically, every expression has an integer weight, which for the baseline synthesizer is the number of nodes in the AST. The search maintains a table mapping weights to a list of all the values of previously explored sub-expressions of that weight. The search is initialized with a set of input values and constant values given by the user, all of which have weight $1$. The search then proceeds starting from expressions of weight 1, gradually creating all expressions of weight 2, and then of weight 3, and so on. To create all values of weight $n$, we loop over all available functions, calling each function with all combinations of arguments that would yield the desired weight. For example, if we are trying to construct all values of weight 10 of the form [`Concat`]{}$(x, y)$, we iterate over all values where $x$ has weight $1$ and $y$ has weight $8$, and then where $x$ has weight $2$ and $y$ has weight $7$, and so forth. (The [`Concat`]{} function itself contributes weight $1$.) Every time a new expression is constructed, we evaluate it on the given inputs, terminating the search when the expression produces the desired outputs.

Property Signatures {#section:property_signatures}
-------------------

In order to perform machine learning on values encountered during the enumeration, we make use of recent work on Property Signatures [@SIGNATURES]. Consider a function with input type $\tau_{in}$ and output type $\tau_{out}$. In this context, a property is a function of type: $(\tau_{in}, \tau_{out}) \rightarrow \texttt{Bool}$ that describes some aspect of the function under consideration. If we have a list of such properties and some inputs and outputs of the correct type, we can evaluate all the properties on the input-output pairs to get a list of outputs that we will call the property signature. More precisely, given a list of $n$ input-output pairs and a list of $k$ properties, the property signature is a length $k$ vector. The elements of the vector corresponding to a given property will have one of the values [$\mathsf{AllTrue}$]{}, [$\mathsf{AllFalse}$]{}, and [$\mathsf{Mixed}$]{}, depending on whether the property returned ${\ensuremath{\mathsf{True}}}$ for all $n$ pairs, ${\ensuremath{\mathsf{False}}}$ for all $n$ pairs, or ${\ensuremath{\mathsf{True}}}$ for some and ${\ensuremath{\mathsf{False}}}$ for others, respectively. Concretely, then, any property signature can be identified with a trit-vector, and we represent them in computer programs as arrays containing the values $\{-1, 0, 1\}$. An example of property signatures is shown in Listing \[listing:signatures\].

    io_pairs = [
      ("butter",   "butterfly"),
      ("abc",      "abc_"),
      ("xyz",      "XYZ_"),
    ]

    p1 = lambda inp, outp : inp in outp 
    p2 = lambda inp, outp : outp.endswith(inp)
    p3 = lambda inp, outp : inp.lower() in outp.lower()

Input/output examples $(\mathcal{I}, \mathcal{O})$ A program $P$ such that $P(i) = o$ for all inputs $i \in {\mathcal{I}}$ with corresponding output $o \in {\mathcal{O}}$ Supported operations *Ops*, supported Properties *Props*, and a model $M$ trained using *Props* as described in Section \[section:training\_the\_model\]. $E \gets \emptyset $ $C \gets $ $E[1] \gets \mathcal{I} \cup C$ $s_{io} \gets \Call{PropertySignature}{\mathcal{I}, \mathcal{O}, \mathit{Props}}$ \[alg:bustle\_line\_1\] $n \gets op.\mathit{arity}$ $A \gets \emptyset$ $A \gets A \cup \{(a_1, \dots , a_n) \mid a_i.\mathit{weight} = w_i \wedge a_i.type = op.argtypes_i\}$ ${\mathcal{V}}\gets $ $w' \gets w$ $s_{vo} \gets \Call{PropertySignature}{{\mathcal{V}}, \mathcal{O}, \mathit{Props}}$ \[alg:bustle\_line\_2\] $w' \gets \Call{ReweightWithModel}{M, s_{io}, s_{vo}, w}$ \[alg:bustle\_line\_3\] $E[w'] \gets E[w'] \cup \{{\mathcal{V}}\}$

Benchmarks {#section:benchmarks}
----------

We evaluate [<span style="font-variant:small-caps;">Bustle</span>]{} using a suite of 56 human-written benchmarks. These benchmarks were inspired by questions on help forums for spreadsheet programs, and designed to be difficult enough to stress our system; in fact, our best system solves less than half of them. The search space explored by the synthesizers to solve these benchmarks is quite large: on average, [<span style="font-variant:small-caps;">Bustle</span>]{} (orange line in Figure \[fig:progress\_plots\]) searches over 6 million expressions per benchmark attempt, and 1.5 million expressions per successful attempt. Most benchmarks have 2 or 3 input-output pairs, and no benchmark solved by [<span style="font-variant:small-caps;">Bustle</span>]{} has more than 4, though for some unsolved benchmarks we did feel that we needed more than 4 pairs to fully specify the semantics of the desired program. In each case, we gave what we felt was the number of pairs a user of such a system would find reasonable (though of course this is a subjective judgment). Three representative benchmarks are shown in Listing \[listing:benchmarks\]. See the Supplementary Material for a full list.


    # Compute the depth of a path, i.e., count the number of slashes
    expectedProgram = "TO_TEXT(MINUS(LEN(var_0), LEN(SUBSTITUTE(var_0, \"/\", \"\"))))"
    io_pairs = {"/this/is/a/path": "4", "/home": "1", "/a/b": "2"}

    # Change DDMMYYYY date to MM/DD/YYYY
    solution = "CONCATENATE(MID(var_0, 3, 2), \"/\", REPLACE(var_0, 3, 2, \"/\"))"
    io_pairs = {"08092019" : "09/08/2019", "12032020" : "03/12/2020"}

    # Create capitalized acronym from two words in one cell
    solution =
        "UPPER(CONCATENATE(LEFT(var_0, 1), MID(var_0, ADD(FIND(\" \", var_0), 1), 1)))"
    io_pairs = {"product area" : "PA", "Vice president" : "VP"}

[<span style="font-variant:small-caps;">Bustle</span>]{}: Bottom-Up Synthesis with Learning
===========================================================================================

Each intermediate expression we encounter during search can be evaluated to produce concrete results, and we can pass those results into a machine learning model to guide the search. The model is a binary classifier $p(y \mid {\mathcal{I}}, {\mathcal{V}}, {\mathcal{O}})$ that predicts whether a set of values ${\mathcal{V}},$ which result from evaluating an expression on each input example $i \in \cal{I}$, is an intermediate value of a program that maps the inputs ${\mathcal{I}}$ to the outputs ${\mathcal{O}}.$ Given those predictions, we de-prioritize sub-expressions that are unlikely to appear in the final result, which, when done correctly, dramatically speeds up the synthesizer.

Model Architecture and Training {#section:training_the_model}
-------------------------------

Because we want the classifier to learn whether a value is intermediate between an input and an output, the model receives *two* property signatures as input: one from the inputs and one from the intermediate value. Recall from Section \[section:property\_signatures\] that a property signature is computed by applying a list of properties to a list of input-output pairs. So one signature is computed by applying all of the properties to input-output pairs, and the other is applied to intermediate value-output pairs. A few example properties that we use include: (a) if $v$ and $o$ are both strings, is $v$ an initial substring of $o$; (b) do $v$ and $o$ have the same length; (c) does the output contain a space, and so on. (See Supplementary Material for the full list of properties.) Then we concatenate these two vectors to obtain the model’s input. The rest of the model is straightforward. Each element of the property signature is either ${\ensuremath{\mathsf{AllTrue}}}$, ${\ensuremath{\mathsf{AllFalse}}}$ and ${\ensuremath{\mathsf{Mixed}}}$. So we embed the ternary property signature into a higher-dimensional dense vector and then feed it into a fully connected neural network for binary classification.

This model is simple, but we are only able to use such a simple model due to our particular design choices: our form of bottom up search guarantees that all intermediate expressions can yield a value comparable to the inputs and outputs, and Property Signatures can do a lot of the “representational work” that would otherwise require a larger model.

The classifier is trained by behavior cloning on a set of training problems. However, obtaining a training dataset is challenging. Ideally, the training set would contain synthesis tasks that are interesting to humans, but such datasets can be small compared to what is needed to train deep networks. Instead, we train on randomly generated synthetic data (similar to [@ROBUSTFILL]). This choice does come with a risk of poor performance on human-written tasks due to domain mismatch [@shin2019-sv], but we show in Section \[section:results\] that [<span style="font-variant:small-caps;">Bustle</span>]{} can overcome this issue.

Generating the random synthetic data is itself non-trivial: Because different DSL functions have corresponding argument preconditions and invariants (e.g. for [`Substr`]{} the position indices $I_1$ and $I_2$ should be less than the string length $I_1 \le {\texttt{Len(S)}} \land I_2 \le {\texttt{Len(S)}}$), a random sampling of DSL programs and inputs would lead to a large number of training examples where the program cannot be applied to the sampled inputs. Instead, we use the idea of synthesis search-driven data generation from TF-Coder [@TFCODER]: First, we generate a large number of random inputs. For each of those inputs, we run bottom-up search using a dummy output, so that the search will never succeed, but just keeps generating expressions. For each generated expression, we compute all of its sub-expressions. This results in a dataset of triples, which contain an input, a sub-expression, and a larger expression to which the sub-expression belongs. These comprise the positive examples for the classifier. We also create an analogous dataset of negative triples — of the same size as the positive dataset — where the sub-expression in question is not actually a sub-expression of the larger expression. The data set used in our experiments was created by performing searches on 1000 random inputs and keeping 100 positive and 100 negative values at random from each search.

Combining Model with Synthesis {#section:synthesis_algorithm}
------------------------------

Incorporating the model into bottom-up synthesis is straightforward, and can be accomplished by adding the blue lines into Algorithm \[alg:search\]. Lines \[alg:bustle\_line\_1\] and \[alg:bustle\_line\_2\] compute the property signatures required for the model input, as described previously. The main challenge is that the model produces a probability $p(y | {\mathcal{I}}, {\mathcal{V}}, {\mathcal{O}}),$ but the search is organized by integer weights. We resolve this with a simple heuristic: at the time we generate a new value, we have the weight $w$ of the expression that generates it. We discretize the model’s output probability into an integer in $\delta \in 0, \ldots, 5$ by binning it into six bins bounded by $[0.0, 0.1, 0.2, 0.3, 0.4, 0.6, 1.0].$ The new weight is computed from the discretized model output as $w' = w + 5-\delta.$ This function is indicated by [<span style="font-variant:small-caps;">ReweightWithModel</span>]{} in Algorithm \[alg:search\].

A key challenge is making the model fast enough. Evaluating the model for every intermediate value could cause the synthesizer to slow down so much that the overall performance would be worse than with no model at all. However, [<span style="font-variant:small-caps;">Bustle</span>]{} actually outperforms our baselines even when measured strictly in terms of wall-clock time (Section \[section:results\]). There are several reasons for this. First, computing property signatures for the expressions allows us to take some of the work of representing the intermediate state out of the neural network (which is slow) and to do it in the JVM (which is fast). Second, because a property signature is a fixed length representation, it can be fed into a simple feed-forward neural network, rather than requiring a recurrent model, as would be necessary if we passed in e.g. the AST representation. Third, because of this fixed length representation, it is easy to batch many calls to the machine learning model and process them using CPU vector instructions. Inference calls to the machine learning model could, in principle, be done in parallel to the rest of the synthesizer, either on a separate CPU core or on an accelerator, which would further improve wall-clock results. Due to these optimizations, computing property signatures and running the model on them accounts for only roughly 20% of the total time spent; the rest is spent by the symbolic portions of the bottom-up search.

Experiments {#section:results}
===========

We evaluate [<span style="font-variant:small-caps;">Bustle</span>]{} on a suite of human-written benchmarks inspired by string transformation questions asked by users on online help-forums. (See Supplementary Material for the full list of benchmarks.) We measure performance in two ways. First, we consider the number of benchmarks successfully solved as a function of number of candidates considered, which gives insight into how much the machine learning model has been able to reduce the search space. Second, we consider the number of benchmarks solved as a function of wall-clock time, which takes into account the computational cost of calling the model.

We compare [<span style="font-variant:small-caps;">Bustle</span>]{} to three other methods. First we compare to the baseline bottom-up synthesizer without machine learning. Without learning, the synthesizer explores expressions in order of size, which is reasonable in this domain, because the correct programs are fairly small.

Second, we compare to the baseline synthesizer augmented with simple but effective human-written heuristics, to quantify whether the improvement is due to learning or due to having good features. Specifically, we reweight the intermediate string values encountered during the search based on whether they are a substring of the desired output and the edit distance compared to the output, normalized to a fraction.

Finally, we explore whether learning within the synthesis loop provides benefits compared to simply using learning once at the beginning of the search to choose which operations to prioritize, as in @DEEPCODER. Specifically, we train a model similar to the model trained for [<span style="font-variant:small-caps;">Bustle</span>]{}, but larger (since inference time is essentially inconsequential in this context) on the same data set used to train the model for [<span style="font-variant:small-caps;">Bustle</span>]{}, but instead of predicting whether an expression is a sub-expression of a solution, we predict which operations will be used in a solution. Then, for each benchmark attempt, we simply don’t use the 4 operations that the model predicts are least likely to appear (where 4 was chosen using a hyper-parameter search over the values in {1, 2, 3, 4, 5}).

The results as a function of number of candidate expressions considered are shown in Figure \[fig:progress\_plots\] (Left). By this metric, [<span style="font-variant:small-caps;">Bustle</span>]{} (orange) performs very well, solving 24 tasks within 10 million candidate expressions, significantly outperforming the simple synthesizer (blue), for example, which only solves 17 tasks.

As for wall-clock time (Figure \[fig:progress\_plots\], right), for any fixed time budget, [<span style="font-variant:small-caps;">Bustle</span>]{} (orange) solves more tasks than the baselines. Despite the overhead of calling the model, [<span style="font-variant:small-caps;">Bustle</span>]{} (orange) still solves 24 tasks within 10 seconds, outperforming the baseline synthesizer (blue) which only solves 17 tasks. [<span style="font-variant:small-caps;">Bustle</span>]{} also outperforms the domain-specific heuristics, despite the model being slower to execute. Furthermore, when using both the model and heuristics (red), the synthesizer performs the best overall, solving 25 tasks within 10 seconds, while the heuristics-only approach only solves 23 tasks. This indicates that although learning in the loop outperforms domain-specific heuristics, the two approaches can be combined to achieve better performance than either approach alone. Finally, we can see that premise selection (purple) was slightly helpful, leading to 2 more solved tasks within 10 seconds compared to the baseline, but with much less improvement than [<span style="font-variant:small-caps;">Bustle</span>]{}. This is evidence that using learning from partial executions within the synthesis loop is crucial for [<span style="font-variant:small-caps;">Bustle</span>]{}’s success.

![ Plots of human-written benchmarks solved over time. (Left) The number of benchmarks solved as a function of intermediate expressions considered. This metric makes [<span style="font-variant:small-caps;">Bustle</span>]{} look somewhat better than it is, because it ignores slowdowns in wall-clock time, but it is still important to look at. First, it gives us an upper bound on how good we can do in wall-clock terms given by putting more engineering effort into speeding up the model. Second, it gives us a sense of how well the model is generalizing to the test set that is invariant to engineering considerations. (Right) Benchmarks solved per unit of elapsed wall-clock time. [<span style="font-variant:small-caps;">Bustle</span>]{} still outperforms baselines here, but not by quite as much, since inference takes non-zero time.[]{data-label="fig:progress_plots"}](figures/time_and_expressions_plot.png){width="0.8\columnwidth"}

![ Histograms of model predictions for expressions seen while solving benchmarks. (Left) for expressions that were sub-expressions of a solution, the vast majority received predictions close to 1, showing that the model can identify the correct expressions to prioritize during search. (Right) for expressions that were not sub-expressions of a solution, predictions skewed close to 0, although a fraction of predictions were close to 1.[]{data-label="fig:prediction_histograms"}](figures/prediction_histograms.png){width="0.7\columnwidth"}

We conduct two additional analyses to better understand the performance of [<span style="font-variant:small-caps;">Bustle</span>]{}. First, we investigate the predictions of the model when it is run on the intermediate values actually encountered during synthesis of the human-written benchmarks. We compute separate histograms for the model’s predictions on expressions that do appear in the solution and expressions that don’t appear in the solution, for all benchmarks that were solved. Predictions for true sub-expressions skew positive and predictions for negative sub-expressions skew negative. This provides further evidence the our model generalizes well to human benchmarks, despite the domain mismatch to the synthetic data used in training. The detailed results are in Figure \[fig:prediction\_histograms\]. Finally, we evaluated whether all benchmarks solved by the baseline (no model, no heuristics) were also solved by [<span style="font-variant:small-caps;">Bustle</span>]{}. The answer is mostly yes — [<span style="font-variant:small-caps;">Bustle</span>]{} only fails to solve one benchmark that was solved by the baseline synthesizer.

Related Work
============

For surveys on program synthesis and machine learning for software engineering, see @THREEPILLARS [@ARMANDOCOURSE; @RISHABHSURVEY; @BIGCODE]. A well-known synthesizer for spreadsheet programs is FlashFill [@FLASHFILL], a version of which is deployed in Microsoft Excel. FlashFill is based on Version Space Algebras (VSAs), which are powerful and fast, but only apply to restricted DSLs, e.g. the top-most function in the program must be [`Concat`]{}, which allows it to perform efficient divide and conquer style search. Our technique has no such restrictions.

Early work on machine learning for program synthesis includes Deepcoder [@DEEPCODER], which uses ML to select once at the beginning of search. Although this idea is pragmatic, the disadvantage is that once the search has started, the model can give no further feedback. [@SIGNATURES] use property signatures within a Deepcoder-style model for premise selection.

One can also train a machine learning model to emit whole programs token-by-token using an encoder-decoder neural architecture [@bunel2018leveraging; @ROBUSTFILL; @parisotto2017neuro], but when one does this one loses the ability to inspect outputs of intermediate programs. Previous work has also considered using learning within syntax guided search over programs [@Yin2017-my; @EUPHONY], but because these methods are top-down, it is much more difficult to guide them by execution information. Finally, @INFERSKETCHES learns to emit a partial program and fill in the holes with a symbolic search.

The most closely related work to ours is *neural execution-guided synthesis*, which like us, uses values produced by intermediate programs within a neural network. @GARBAGECOLLECTOR process intermediate values of a program using a neural network for a small, straight-line DSL, but they do not use the model to evaluate intermediate programs. Another approach is to rewrite a programming language so that it can be evaluated “left-to-right”, allowing values to be used to prioritize the search in an actor-critic framework [@REPL]. Similarly, @ChenLS19 use intermediate values while synthesizing a program using a neural encoder-decoder model, but again this work proceeds in a variant of left-to-right search that is modified to handle conditionals and loops. None of these approaches exploit our main insight, which is that bottom-up search allows the model to prioritize and combine small programs that solve different subtasks.

*Learning to search* has been an active area in machine learning, especially in imitation learning [@Daume2009-lm; @Ross2011-li; @Chang2015-od]. Combining more sophisticated imitation learning strategies into [<span style="font-variant:small-caps;">Bustle</span>]{} is an interesting direction for future work.

Conclusion
==========

We have introduced [<span style="font-variant:small-caps;">Bustle</span>]{}, a technique for using machine learning to guide bottom-up search for program synthesis. [<span style="font-variant:small-caps;">Bustle</span>]{} exploits the fact that bottom-up search makes it easy to evaluate partial programs and it uses machine learning to predict the likelihood that a given intermediate value is a sub-expression of the desired solution. We have shown that [<span style="font-variant:small-caps;">Bustle</span>]{} improves over various baselines on human-written benchmarks, not only in terms of benchmarks solved per candidate program considered, but also in terms of wall-clock time. In fact, we view showing that learning-in-the loop can be made fast enough for program synthesis as perhaps the major contribution of this work; the idea of learning-in-the-loop, though novel as far as we are aware, is relatively obvious, but we were quite surprised to learn that it can be made efficient enough to provide overall end-to-end speedups.

Listing of Properties Used
==========================

[<span style="font-variant:small-caps;">Bustle</span>]{} computes two types of Property Signatures: the signature involving the inputs and the outputs, and the signature involving the intermediate state and the outputs. In this paper, the inputs and outputs are always strings, but the intermediate state may be either an integer or a string, so we have properties dealing with both inputs and strings. In an abstract sense, a property acts on an input and an output, but some properties will simply ignore the input, and so we implement those as functions with only one argument. Thus, we have four types of properties:

-   properties acting on a single string (Listing \[listing:singlestringproperties\]).

-   properties acting on a single integer (Listing \[listing:singleintegerproperties\]).

-   properties acting on a string and the output string (Listing \[listing:stringstringproperties\]).

-   properties acting on an integer and the output string (Listing \[listing:integerstringproperties\]).

For a program with multiple inputs, we simply loop over all the inputs and the output, computing all of the relevant types of properties for each. For example, a program taking two string inputs and yielding one string output will have single-argument string properties for the output and two sets of double-argument string properties, one for each input. We fix a maximum number of inputs and pad the signatures so that they are all the same size.

    str.isEmpty()               // is empty?
    str.length() == 1           // is single char?
    str.length() <= 5           // is short string?
    str.equals(lower)           // is lowercase?
    str.equals(upper)           // is uppercase?
    str.contains(" ")           // contains space?
    str.contains(",")           // contains comma?
    str.contains(".")           // contains period?
    str.contains("-")           // contains dash?
    str.contains("/")           // contains slash?
    str.matches(".*\\d.*")      // contains digits?
    str.matches("\\d+")         // only digits?
    str.matches(".*[a-zA-Z].*") // contains letters?
    str.matches("[a-zA-Z]+")    // only letters?

    integer == 0                // is zero?
    integer == 1                // is one?
    integer == 2                // is two?
    integer < 0                 // is negative?
    0 < integer && integer <= 3 // is small integer?
    3 < integer && integer <= 9 // is medium integer?
    9 < integer                 // is large integer?

    outputStr.contains(str)            // output contains input?
    outputStr.startsWith(str)          // output starts with input?
    outputStr.endsWith(str)            // output ends with input?
    str.contains(outputStr)            // input contains output?
    str.startsWith(outputStr)          // input starts with output?
    str.endsWith(outputStr)            // input ends with output?
    outputStrLower.contains(lower)     // output contains input ignoring case?
    outputStrLower.startsWith(lower)   // output starts with input ignoring case?
    outputStrLower.endsWith(lower)     // output ends with input ignoring case?
    lower.contains(outputStrLower)     // input contains output ignoring case?
    lower.startsWith(outputStrLower)   // input starts with output ignoring case?
    lower.endsWith(outputStrLower)     // input ends with output ignoring case?
    str.equals(outputStr)              // input equals output?
    lower.equals(outputStrLower)       // input equals output ignoring case?
    str.length() == outputStr.length() // input same length as output?
    str.length() < outputStr.length()  // input shorter than output?
    str.length() > outputStr.length()  // input longer than output?

    integer < outputStr.length()                // is less than output length?
    integer <= outputStr.length()               // is less or equal to output length?
    integer == outputStr.length()               // is equal to output length?
    integer >= outputStr.length()               // is greater or equal to output length?
    integer > outputStr.length()                // is greater than output length?
    Math.abs(integer - outputStr.length()) <= 1 // is very close to output length?
    Math.abs(integer - outputStr.length()) <= 3 // is close to output length?

Expanded Description of DSL
===========================

Our DSL allows for nesting and compositions of common string transformation functions. These functions include string concatenation ([`Concat`]{}) returning a substring at the beginning ([`Left`]{}), middle ([`Substr`]{}), or right ([`Right`]{}) of a string, and other familiar string replacing a substring of one string, indicated by start and end position, with another string ([`Replace`]{}); removing white space from the beginning and ending of a string ([`Trim`]{}); concatenating a string with itself a specified number of times ([`Repeat`]{}); substituting the first $k$ occurrences of a substring with another ([`Substitute`]{}); converting an integer to a string ([`ToText`]{}); and converting a string to [`LowerCase`]{}, [`UpperCase`]{}, or every word capitalized ([`ProperCase`]{}). Integer functions include arithmetic, returning the index of the first occurrence of a substring within a string ([`Find`]{}), and string length. Finally, a few commonly useful string and integer constants are included.

List of Benchmark Programs
==========================

Here we show each of our human-written benchmark problems, and a possible solution written in a DSL that is a superset of the DSL used by our synthesizer. We have separated them into Listing \[listing:benchmarks1\], Listing \[listing:benchmarks2\], and Listing \[listing:benchmarks3\] for space reasons. Note that the synthesizer can and does solve problems with programs different than the programs given here, and that it does not solve all of the problems.

    // abbreviate day of week and month names with capital letters
    CONCATENATE(LEFT(UPPER(var_0), 3), ", ", MID(UPPER(var_0), ADD(FIND(",", var_0), 2), 3), MID(var_0, FIND(" ", var_0, ADD(FIND(",", var_0), 2)), 3))

    // add decimal point if not present
    IF(ISERROR(FIND(".", var_0)), CONCATENATE(var_0, ".0"), var_0)

    // add plus sign to positive integers
    IF(EXACT(LEFT(var_0, 1), "-"), var_0, CONCATENATE("+", var_0))

    // add thousands separator to number
    TEXT(var_0, "#,###")

    // append AM or PM to the hour depending on if it is morning
    CONCATENATE(LEFT(var_0, MINUS(FIND(":", var_0), 1)), IF(EXACT(var_1, "morning"), " AM", " PM"))

    // fix capitalization of city and state
    CONCATENATE(LEFT(PROPER(var_0), MINUS(LEN(var_0), 1)), UPPER(RIGHT(var_0, 1)))

    // capitalize the first word and lowercase the rest
    REPLACE(LOWER(var_0), 1, 1, UPPER(LEFT(var_0, 1)))

    // concatenate 3 strings in alphabetical order
    JOIN(" ", TRANSPOSE(SORT(TRANSPOSE({var_0, var_1, var_2}))))

    // concatenate a variable number of strings
    IFNA(JOIN(", ", FILTER(TRANSPOSE({var_0, var_1, var_2}), NOT(EQ(0, LEN(TRANSPOSE({var_0, var_1, var_2})))))), "")

    // concatenate column values with underscore except when value is empty.
    CONCATENATE(var_0, IF(OR(var_0="", AND(var_1="", var_2="")), "", "_"), var_1, IF(OR(var_1="", var_2=""), "", "_"), var_2)

    // whether the first string contains the second
    TO_TEXT(ISNUMBER(FIND(var_1, var_0)))

    // whether the first string contains the second, ignoring case
    TO_TEXT(ISNUMBER(FIND(LOWER(var_1), LOWER(var_0))))

    // count the number of times the second string appears in the first
    TO_TEXT(DIVIDE(MINUS(LEN(var_0), LEN(SUBSTITUTE(var_0, var_1, ""))), LEN(var_1)))

    // create email address from name and company
    LOWER(CONCATENATE(LEFT(var_0, 1), var_1, "@", var_2, ".com"))

    // change DDMMYYYY date to MM/DD/YYYY
    CONCATENATE(MID(var_0, 3, 2), "/", REPLACE(var_0, 3, 2, "/"))

    // change YYYY-MM-DD date to YYYY/MM/DD
    SUBSTITUTE(var_0, "-", "/")

    // change YYYY-MM-DD date to MM/DD
    SUBSTITUTE(RIGHT(var_0, 5), "-", "/")

    // extract the text between alpha> and <
    REGEXEXTRACT(var_0, ">(.*)<")

    // extract date and time from two different input formats.
    CONCATENATE(REGEXEXTRACT(var_0, "\d+"), REGEXEXTRACT(var_0, " \w+"), REGEXEXTRACT(var_0, ", \d+pm"))

    // extract the single number
    REGEXEXTRACT(var_0, "[0-9]+")

    // extract the number between the second parenthesis
    REGEXEXTRACT(var_0,".*\(.*\).*\((\d+)\).*")

    // extract the number starting with 20 in the input string.
    TRIM(REGEXEXTRACT(var_0,"\s20\d+"))

    // extract the part of a URL between the 2nd and 3rd slash
    MID(var_0, ADD(FIND("//", var_0), 2), MINUS(MINUS(FIND("/", var_0, 9), FIND("/", var_0)), 2))

    // extract the part of a URL starting from the 3rd slash
    RIGHT(var_0, ADD(1, MINUS(LEN(var_0), FIND("/", var_0, ADD(FIND("//", var_0), 2)))))

    // extract the top-level domain of a URL
    REGEXEXTRACT(var_0, "//[^/]*\.(.+?)/")

    // get first name from second column
    LEFT(var_1, MINUS(FIND(" ", var_1), 1))

    // get last name from first column
    RIGHT(var_0, MINUS(LEN(var_0), FIND(" ", var_0)))

    // find the longest common prefix of two words
    LEFT(var_0, ARRAYFORMULA(SUM(IF(EQ(LEFT(var_0, SEQUENCE(MIN(LEN(var_0), LEN(var_1)))), LEFT(var_1, SEQUENCE(MIN(LEN(var_0), LEN(var_1))))), 1, 0))))

    // find the longest common suffix of two words
    RIGHT(var_0, ARRAYFORMULA(SUM(IF(EQ(RIGHT(var_0, SEQUENCE(MIN(LEN(var_0), LEN(var_1)))), RIGHT(var_1, SEQUENCE(MIN(LEN(var_0), LEN(var_1))))), 1, 0))))

    // create acronym from multiple words in one cell
    JOIN("", ARRAYFORMULA(LEFT(SPLIT(var_0, " "), 1)))

    // create capitalized acronym from multiple words in one cell
    UPPER(JOIN("", ARRAYFORMULA(LEFT(SPLIT(var_0, " "), 1))))

    // output "Completed" if 100%, "Not Yet Started" if 0%, and "In Progress" if between 0% and 100%
    IF(var_0="100%", "Completed", IF(var_0="0%", "Not Yet Started", "In Progress"))

    // enclose negative numbers in parentheses
    IF(EXACT(LEFT(var_0, 1), "-"), CONCATENATE(SUBSTITUTE(var_0, "-", "("), ")"), var_0)

    // create currency string
    CONCATENATE("$", TEXT(var_0, "0.00"))

    // determine if the text is a word or a number
    IF(REGEXMATCH(var_0, "^[[:alpha:]]+$"), "word", "number")

    // determine if the text is a word, number, or neither
    IF(REGEXMATCH(var_0, "^[[:alpha:]]+$"), "word", IF(REGEXMATCH(var_0, "^\d+(\.\d+)?$"), "number", "neither"))

    // pad text with spaces to a given width
    CONCATENATE(REPT(" ", MINUS(VALUE(var_1), LEN(var_0))), var_0)

    // pad number with 0 to width 5
    CONCATENATE(REPT("0", MINUS(5, LEN(var_0))), var_0)

    // the depth of a path, i.e., count the number of /
    TO_TEXT(MINUS(LEN(var_0), LEN(SUBSTITUTE(var_0, "/", ""))))

    // extract the rest of a word given a prefix
    RIGHT(var_0, MINUS(LEN(var_0), LEN(var_1)))

    // prepend Mr. to last name
    CONCATENATE("Mr. ", RIGHT(var_0, MINUS(LEN(var_0), FIND(" ", var_0))))

    // prepend Mr. or Ms. to last name depending on gender
    CONCATENATE(IF(EXACT(var_1, "male"), "Mr. ", "Ms. "), RIGHT(var_0, MINUS(LEN(var_0), FIND(" ", var_0))))

    // yes if at least one input string is yes
    IF(OR(ARRAYFORMULA(EXACT("yes", {var_0, var_1, var_2}))), "yes", "no")

    // remove duplicate numbers
    JOIN(" ", UNIQUE(TRANSPOSE(SPLIT(var_0, " "))))


    // remove leading and trailing spaces and tabs, and lowercase
    TRIM(LOWER(var_0))

    // remove zeros at the beginning
    RIGHT(var_0, MINUS(5, SUM(ARRAYFORMULA(IF(EXACT(LEFT(var_0, SEQUENCE(1, 5)), REPT("0", SEQUENCE(1, 5))), 1, 0)))))

    // replace <COMPANY> in a string with a given company name
    SUBSTITUTE(var_0, "<COMPANY>", var_1)

    // replace all numbers with a placeholder {number}
    REGEXREPLACE(var_0, "[0-9]+", "{number}")

    // replace com with org
    SUBSTITUTE(var_0, "com", "org", 1)

    // whether the two strings are exactly equal, yes or no
    IF(EXACT(var_0, var_1), "yes", "no")

    // whether the two strings are exactly equal ignoring case, yes or no
    IF(EXACT(LOWER(var_0), LOWER(var_1)), "yes", "no")

    // length of string
    TO_TEXT(LEN(var_0))

    // extract the rest of a word given a suffix
    LEFT(var_0, MINUS(LEN(var_0), LEN(var_1)))

    // truncate and add ... if longer than 15 characters
    IF(GT(LEN(var_0), 15), CONCATENATE(LEFT(var_0, 15), "..."), var_0)

    // create acronym from two words in one cell
    CONCATENATE(LEFT(var_0, 1), MID(var_0, ADD(FIND(" ", var_0), 1), 1))

    // create capitalized acronym from two words in one cell
    UPPER(CONCATENATE(LEFT(var_0, 1), MID(var_0, ADD(FIND(" ", var_0), 1), 1)))

[^1]: Equal Contribution
