BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration
Authors: Augustus Odena
Kensen Shi
David Bieber
Rishabh Singh
Charles Sutton
Hanjun Dai
Venue: ICLR 2021 Spotlight (2021)
Keywords: Program Synthesis

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 analyzing 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 two datasets, one from the SyGuS competition and one of our own creation.

Published as a conference paper at ICLR 2021
BUSTLE: BOTTOM-UP PROGRAM SYNTHESIS THROUGH LEADNING-GUIEED EXPLORATION
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton & Hanjuu Dai Google Research
(augustusodena, kshi, dbi ober, rising, charlessutton hadaí )eooolggoooo.oooooo
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 analyzing 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, train model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This 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 two datasets, one from the SyGuS competition and one of our own creation.
INTRODUCTION
Program synthesis is a longstanding goal of artificial intelligence research (Manna & Waldinger 1971 Summers 1977). but it remains difficult in part because of the challenges of search (Alur 2013 Gulwani et al. 2017). The objective in program synthesis is to automatically write program given specification of its intended behavior, and current state of the art methods typically perform some form of search over space of possible programs. Many different search methods have been explored in the literature, both with and without learning. These include search within version-space algebra (Gulwani 2011), bottom-up enumerative search (Udupa et al.) (013)). stochastic search (Schkufza et al. [dl]]001), genetic programming (Koza) 1994), reducing the synthesis problem to logical satisfiability (Solar-Lezama et al. 2006), beam search with a sequence-to--squeeee neural network (Devlin et al. 2017), learning to perform premise selection to guide search (Balog et
et al.
2017), learning to prioritize grammar rules within top-down search (Lee et al.) 2018 and learned
search based on partial executions (Ellis ct al. 2019 Zohar & Wolf 2018
Chen et al. 2019).
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-progran programgs and then analyzing their intermediate results compose them in appropriate ways. We propose a new learning-guide guided system for synthesis, called BUSTLE which follows this intuition in straightforward manner. Given a specification of program's 's intended behavior (in this paper given by input-output examples), BUSTLE performs bottom-up enumerative search for a satisfying program, following Udupa et al. 2013). 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 predict whether the intermediate value produced by a partial program is part of an eventual solution. This combination of learning and
"Equal Contribution
Bottom-U program Synthesis Through Learning-guide Exploration

---

Published as a conference paper at ICLR 2021
bottom-up search has several key advantages. First, because the input to the model is 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 execution execution-guided guided synthesis, the search procedure has more flexibility about which order to generate the program in, and this flexibility can be exploited by machine learning.
fundamental challenge in this approach is that exponentially many intermediate programs are explored during search, so the model needs be both fast and accurate to yield wall-clock time speedups. We are allowed to incur some slowdown from performing model inference, because if the model accurate enough, we can search many fewer values before finding solutions. However, in the domains we consider, executing a program is still orders of magnitude faster than performing inference on even a small machine learning model, so this challenge cannot be ignored. 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 (Odena & Sutton 2020), which featurize program inputs and outputs using another set of programs.
A second 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 (Balog et al.) 2017 Devlin et al. 2017), but models trained on random programs do not always transfer to human- written benchmarks ks (Shin et al. (201)). We show that of property signatures helps with this distribution mismatch problem well.
In summary, this paper makes the following contributions:
We present BUSTLE, which integrates machine learning into bottom-up up program synthesis. We show how to efficiently add machine learning the synthesis loop using property signatures and batched predictions. With these techniques, adding the model to the synthesizer provides an end-to-end improvement synthesis time.
We evaluate BUSTLE on two string transformation datasets: one our own design and one from the SyGuS competition. We show that BUSTLE leads to improvements in synthesis time compared to a baseline synthesizer without learning, a DeepCoder-style synthesizer (Balog et al.) [2077). and encoder-decoder model (Devlin et al., 2017). Even though model is trained random programs, we show that its performance transfers to set of numan-written synthesis benchmarks.
BACKGROUND AND SETUP
2.1 PROGRAMMING BY EXAMPLE
In Programming- by Example (PBE) task (Winston 1970 Menon et al. 2013 Gulwani 2011
are given a set of input-output pairs and the goal is to find a program such that for each pair, the synthesized program generates the corresponding output when executed on the input. 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
2.2 OUR STRING TRANSFORMATION DSL
Following previous work Gulwani 2011 Devlin et al., 2017), we deal with string and number transformations commonly used in spreadsheets. Such transformations sit a nice point on the complexity spectrum as benchmark task; they are simpler than programs in general purpose languages, but still expressive enough for many common string transformation tasks.
The Coomain-speciff language we use (shown in Figure T is broadly similar to those of Parisotto et al. (017)) and Devlin et al. (2017). but compared to these, our DSL is expanded in several ways that make the synthesis task more difficult. First, in addition to string manipulation, our DSL includes integers, integer arithmetic, booleans, and conditionals. Second, our DSL allows for arbitrarily nested expressions, rather than having maximum size. Finally, and most importantly, previous works (Gulwani 201T; Devlin et al., (017)) impose a restriction of having Concat as the top-level operation. With this constraint, such approaches use version space algebras dynamic programming
2

---

Published as a conference paper at ICLR 2021
Expression E' := S 1 B
String expression == Concat S2) (ef Right((, Substr 41,22
(eplace((Sp) /1 /2, S2) [Tim(() Repeat(S, Subbstiuute(S,,pp Sa)
SubstituteeSI..S 5s. [TText([) LowerCase(S) UpperCase(S)
[roperCase(S) ['' X II
Integer expression 1 + 12 Find(S1, S2) Find(Si, Len(S) J
Boolean expression = Rauual S2) Greater Ihan 1, I2) |
T2)
String constants T' = "" "I"," |".""""" "'""""""'
"!" "?" ["" ")" "[" """ <<"
[ ">"
"}" "-" "4" "_"I"/" "$" "#" ";" "0" "g" "0"
strinng constants extracted from 1/O examples
Integer constants
01
99
Input X == 0/ x
Figure 1: Domain-specificc language (DSL) of expressions considered in this paper.
to exploit the property that partial programs must form substrings of the output. Our DSL lifts this constraint, allowing the synthesizer to handle more kinds of tasks than in those previous works.
Our DSL allows for compositions of common string transformation functions. These functions include string concatenation (Concat) and other familiar string operations (listed in Figure and discussed further in Appendix A). Integer functions include arithmetic, finding the index of substrings (Find), and string length. Finally, commonly useful string and integer constants included. We also use heuristics to extract string constants that appear multiple times in the input-output examples.
2.3 BOTTOM-UP SYNTHESIS
The baseline synthesizer on top of which we build our approach is bottom-up enumerative search inspired by [dupa et al. (0033) which enumerates DSL expressiess from smallest largest, following Algorithm| ii the lines colored in blue T6] [7] are removed. This baseline uses value-based search. During the search each candidate expression 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 the given examples. If there examples for a given task, each value represents one code expression and internally contains the results of executing that expression on inputs from all examples. Hence, two values that represent different code expressions are semantically equivalent on the examples if their n contained results all match each other.
separate onput-output
Every expression has an integer weight, which for the baseline synthesizer is the number of nodes in the abstract syntax tree (AST). The search maintains table mapping weights list of all the values of previously explored sub-expressions of that weight. The search is initialized with the set of input variables as well as any constants extracted with heuristics, all of which have weight Extracted constants include common symbols and delimiters that appear at least once, and long substrings that appear multiple times in the example strings. The search then proceeds to create all expressions of weight 2, and then of weight 3, and so on. To create all values of particular weight, we loop over all available functions, calling each function with all combinations of arguments that would yield the desired weight. For example, if we trying to construct all values of weight 10 of the form Concat (z. y), we iterate over all values where r has weight 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.
3

---

Published as a conference paper at ICLR 2021
so_pairs ("butlez", "butterfly"), ("abe", *abe_"), ("xyx", "xy2_"),
Lambda inp, outp: inp outp
22
lambda inp, outp: outp entpp.dndrithhing
93
Lambda inp, outp: (ap.lower() in outp.iowe:
An example set of input-output pairs, along with three properties that can act on them. The first returns True for the first two pairs and False for the third. The second returns False for all pairs. The third returns True for all pairs. The resulting property signature is (Mixed, AllFalse, AllTrue). These examples are written Python for clarity, but our implementation is in Java.
Listing 1:
Algorithm 1 The BUSTLE Synthesis Algorithm
Input: Input-output examples (Z, O)
Output: A program consistent with the examples (I, O)
Auxiliary Data: Supported operations Ops, supported properties Props, and model M trained
using Props as described in Section 3.1
1: E <-g 9
E maps integer weights terms with that weight
2: C t EXTRACTCONSTANTSS. O)
3: E[] IUC
Inputs and constants have weight
4: Sio < PROPERTYSIGNATUREEE,, O, Props)
5: for w 2.... do
Loop over all possible term weights
6:
for all op E Ops do
7:
T 1 op.arity A
8:
> A holds all argument tuples Make all arg tuples with these weights that type-check
9:
for all W1....., Wm
10:
S.t. Σ wi w 1, w; Z do ag weight we A a, = op.argtypes:
11:
A + (al...., an) )
12:
for all (aI,..., an) E A do
<- EXECUTE(OP, (01,..., kn))
14:
irve E then
The value has not been encountered before
15:
w' + w
16:
8eo PROPERTY O, Props)
17:
w + REWEIGHT
$io, Soay W)
18:
E J < E[w'] U (V)
19:
v O then
20:
return EXPRESSION(()
2.4 PROPERTY SIGNATURES
In order to perform machine learning on values encountered during the enumeration, make use of recent work on property signatures (Odena & Sutton 2020). Consider a function with input type Tin and output type Tout- In this context, a property a function of type: (Tix, Tout) 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 onput-output pairs to get a list of outputs that we will call the property signature. More precisely, given list of n input-output pairs and a list of k properties, the property signature is length A vector. The elements of the vector corresponding to given property will have one of the values AllTrue, AllFalse, and Mixed, depending on whether the property returned True for n pairs, False for all n pairs, or True for some and False for others, respectively. Concretely, then, any property signature can be identified with a vector, and we represent them in computer programs as arrays containing the values {-1,0, 0, 1}. An example of property signatures is shown in Listing] 1
4

---

Published as a conference paper at ICLR 2021
Compute the depth of path, 2.e., count the number of slashes
solut lon TEXT (MINUG (vac__))_ LEN (SUBSTICUTT (var_ o, \"/V, (XD))))
io_pairs <#/chia/ss//ppattt "d", */heme": "1", */a/b": *2*)
Change пOимуYу
/M/ΕD//YY
solution "CONCATENATE IMID 3, 2), 17/ REPLACE (vac__,, 3, 2, (АК"))"
io_pairs ("08092019"; *09/08/2019", "12032020" "03/12/2020";
Create capitalized acronym Ezom two words in one cell
10 solution
11
*OPPER (CONCATENATE (LEFT (var_ 11, (var_ AnD (FIND (s* Vr, vor_o), 11, 1311*
12 jo_paira
("produet "PA", "Vice president":: "VP*)
Listing 2: Three of our benchmark problems (all solved by BUSTLE).
Bottom-up synthesizer
Solution matches O
Inputs
enumerates values (code expressious) order of inemeasing wright
Value
Output O
Trained model
Property signatures
reweights V based likelihood of being a sub-expression
featurizes the transformations O and V
Figure 2: Diagram outlining the BUSTLE approach. The bold arrows show the main feedback loop. The bottom-up synthesizer enumerates values (code expressions), which are featurized along with the I/O example using property signatures. The property signatures are passed to trained model that reweights the value based on whether it appears to be sub-expression of a solution, and the reweighted value given back the bottom-up synthesizer for enumerating larger expressions.
2.5 BENCHMARRS
We evaluate BUSTLE two datasets. The first dataset is suite of 38 human-written written benchmark tasks, which were designed to contain a variety of tasks difficult enough to stress our system. Some tasks involve conditionals, which are not present in other set of benchmark tasks (from SyGuS). The search space explored by the synthesizers to solve these tasks is quite large: on average, BUSTLE searches about million expressions per benchmark attempt, and million expressions per successful attempt. Most tasks have between and 4 input-output pairs, though for some tasks, more than 4 pairs are needed fully specify the semantics of the desired program, especially when conditionals are involved. In each case, we gave what we felt was the number of pairs user of such system would find reasonable (though course this is subjective judgment). Three representative benchmarks are shown in Listing 2
See Appendix B for full list.
The second dataset consists of all SyGuS programs from the 2019 PBE SLIA TRACK and the 2018 PBE Strings Track whose inputs and outputs are only strings. We removed duplicate copies of problems which simply had extra examples. This results in 89 remaining tasks.
BUSTLE: BOTTOM-UP SYNTHESIS WITH LEARNING
BUSTLE uses trained machine learning model to guide the bottom-up search, outlined in Figure 2 Suppose the synthesis task includes n different input-output examples, and there variables (such that the function to synthesize has arity m). Recall that every value in the bottom-up search represents code expression and also contains the n results of evaluating the code expression on the n examples. To guide the bottom-up search, we run machine learning model on the results contained in intermediate values encountered during the search.
separate input
5

---

Published as a conference paper at ICLR 2021
The model is binary classifier ply I, O.) where I is set of m imput values (one for each input variable), O is a single value representing the desired output, and V is an intermediate value encountered during the bottom-up search. We want the model to predict the binary label y 1 if the code expression that produced V is a sub-expression of a solution to the synthesis problem, and y O otherwise. Given these predictions, we de-prioritize sub-expressions that are unlikely to appear in the final result, which, when done correctly, dramatically speeds up the synthesizer.
3.1 MODEL ARCHITECTURE AND TRAINING
Because we want the classifier to learn whether a value is intermediate between an input and an output, the model is conditioned on two property signatures: one from the inputs to the output, and one from the intermediate value to the output. Recall from Section 2.4 that property signature is computed by applying a list of properties to a list of input-output pairs. Thus, one signature computed by applying all of the properties to ipput-ouppt pairs, and the other is applied to intermediate value- output pairs. A few example properties that we use include: (a) if the value v and output o are both strings, is an initial substring of o; (b) do e and have the same length; (c) does the string contain space, and so on. (See Appendix C 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 ArlTrue, AllFalse, or Mixed. We embed the ternary property signature into giges-ndimelioonll dense vector and then feed it into fully connected neural network for binary classification.
This model is simple, but we are only able to use such simple model due to our particular design choices: our form of bottom-up search guarantees that all intermediate expressions can yield a value comparable the inputs and outputs, and property signatures can do much of the "representational work" that would otherwise require larger or more complex 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 needed to train deep neural networks. Instead, we train on randomly generated synthetic data, similar to Devlin et al. (2017). This choice does come with risk of poor performance on human- numan-written tasks due to domain mismatch that (Shin et al. 2019), but we show in Section that BUSTLE can overcome this issue.
Generating the synthetic data is itself nontrivial. Because different DSL functions have corresponding argument preconditions and invariants (e.g., several functions take integer indices which must be in range for a given string), 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 generating data from synthesis searches, as in TF-Coder (Shi et al. 2020). First, we generate some random input strings to form the inputs I (using multiple input variables and multiple examples). From these inputs, we run bottom-up search using a dummy output, so that the search will keep generating expressions. We randomly select some generated expressions and pretend that they are outputs O for a synthesis task. Then, for each selected expression, we randomly select one of its sub-expressions V to form positive training example (I, V. O)). We also randomly select another expression V from the search that is not a sub-expression of O to serve as a negative training example (I, V", O). In our experiments, we perform 1000 searches on random inputs, select 100 values at random from each search to serve as outputs, and create one positive and one negative example for each selected value as described. Considering that dataset of size 200,000 is not large by modern deep learning standards, training the model is a small one-time cost, completing in few hours on CPU.
3.2 COMBINING MODEL WITH SYNTHESIS
Incorporating the model into bottom-up synthesis is straightforward, and can be accomplished by adding the blue lines into Algorithm Lines and [6 compute the property signatures required for the model input, as described previously. The main challenge is that the model produces a probability p(y I, V, O), but the search is organized by integer weights. We resolve this with 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 integer in 8 E (0....,5) by binning it into six bins

---

Published as a conference paper at ICLR 2021
bounded by [0.0, 0.2,,.3,00040066,, 1.0). output as w' = w + This function is indicated by REWEIGHTW WTTMODEL in Algorithm !
The new weight is computed from the discretized model
A key challenge is making the model fast enough. Evaluating the model once for every intermediate value could cause the synthesizer to slow down so much that the overall performance would be worse than with model at all. However, BUSTLE actually outperforms our baselines even when measured strictly in terms of wall-clock time (Section 4 There are several reasons for this. First, computing property signatures for the expressions allows us take some of the work of representing the intermediate state out of the neural network and to do it natively in Java (which is much faster comparatively). Second, because a property signature is fixed-length representation, can be fed into a simple wordafd neural network, rather than requiring a recurrent model, as would be necessary if we passed in a more complex representation such as the AST. 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 separate CPU core or which would further improve wall-clock results, but our experiments are performed entirely on one CPU. Due to these optimizations, computing property signatures and running the model on them accounts for only roughly 20% of the total time spent.
accelerator,
EXPERIMENTS
We evaluate BUSTLE on both datasets described in Section 2.5 To measure performance, we consider the number of benchmarks solved as function of the number of candidates considered, which gives insight into how well the model can guide the search. We additionally consider benchmarks solved as a function of wall-clock time, which takes into account the computational cost of model inference.
We compare BUSTLE to five other methods:
1. A baseline bottom-up synthesizer without machine learning, which explores expressions in order of increasing size, without any model to guide the search toward the desired output.
2. The baseline synthesizer augmented with domain-specific heuristics (substring relationships and edit distance) to reweight intermediate string values during the search.
An encoder-decoder model as in RobustFill (Devlin et al., (017), which predicts a program directly from the input-output examples. We use beam search on the decoder with beam size of S0, 000 programs, enough to exhaust 16 GB of GPU memory. See Appendix for more details.
A premise selection model as in DeepCoder (Balog et al.] 2017). which lets us analyze whether learning within the synthesis loop is better than learning once the beginning of the search. We train a model similar to the model trained for BUSTLE on the same dataset, but instead of predicting whether an expression is a sub-expression of a solution, we predict which operations will be used in solution. The examples are given to the model using character- embeddings. Then, for each benchmark, we exclude the 2 operations that the model predicts are the least likely. A premise selection model that uses property signatures instead of character-Ievel embeddings.
The results on our 38 new benchmarks are shown in Figure 3a Whether comparing by the number of expressions (left) or the wall-clock time (right), BUSTLE (red-dash) performs quite well, solving 31 tasks within 30 million candidate expressions or 30 seconds. It outperforms all other methods besides one that uses both the model and the heuristics (purple). In particular, BUSTLE heuristics, even though the heuristics are much faster to execute
Results
outperforms the domain-specing compared to running model inference. Furthermore, when using both the model and heuristics (purple), the synthesizer performs the best overall. This indicates that although learning in the loop outperforms domain-specific heuristics, the two approaches can be combined achieve better performance than either alone.
Results on SyGuS benchmarks in Figure 3b were broadly similar, with one exception: the handwritten heuristics perform slightly better than (heuristic-free) BUSTLE. There are a few important caveats to this, however. First, the SyGuS problems are slightly different from the kinds of problems in our 38 new benchmark tasks and the training data, e.g., some SyGuS problems have an incredibly large number of examples or use string-manij manipulation functionality outside our DSL. Second, our heuristics substantially outperform all other baselines, which suggests that they are strong heuristics to begin
7

---

Published as a conference paper at ICLR 2021
Successes by Expressions Considered
Successes by Time Elapsed
-0
Progere synthr
25
13
25
Using model and heurisiics
Usig mote on
Using heunstic only
No motel ne heuratics
Property signature promise seloction DeepCoder pramise ection
PabuzzFil
0.0
0.5
-0
29
2.5
30
10
15
30
Number candidate expressions considered
Elepted (X)
(a) Results on our of 38 new benchmarks.
Successes Expressions Considered
Successes Time Elepsed
80
Prog contrrsstod
40
model and nistiss
12
nuld an
Usng heunstics only
20
-22
mozer, no
Propecty signature premise selection
10
DoopCoder promise ecaion
Robustrill
6.5
2.0
(b) Results on 89 benchmarks from SyGuS.
Figure 3: (Left) Benchmarks solved as function of intermediate expressions considered. This metric makes BUSTLE look somewhat better than it is, because it ignores slowdowns in wall-clock time, but is still important to analyze. It is invariant to engineering considerations, providing an upper bound on how well we can do in wall-clock terms through speeding up the model. (Right) Benchmarks solved over elapsed wall-clock time. BUSTLE still outperforms all baselines on our 38 new tasks, but not by quite as much due to time spent on model inference.
with. Third, still see substantial improvement by combining the BUSTLE model with heuristics, so the best performing algorithm does indeed use BUSTLE.
BUSTLE outperforms both DeepCoder-style premise selection methods (green and pink). Premise selection allows some tasks to be solved faster, but it does not lead to more tasks being solved overall compared to the no-model baseline (black). This is evidence that learning in the loop is important to guide the search as happens, and one step of learning at the beginning of search is not as effective. We furthermore observe that using property signatures (green) leads better performance than not (pink), since they can help the models be more robust to train-test distribution shift.
BUSTLE also outperforms RobustFill (orange). Relatively speaking, RobustFill performs better on the SyGuS tasks than our new tasks, which may indicate that some of our new tasks are more difficult due the use of conditionals. Overall, RobustFill does not perform well, possibly because the end-to-end neural approach is less robust to the train-test distribution shift, and because its complex model cannot predict programs as quickly as BUSTLE'S fast combinatorial search.
We conduct two additional analyses to better understand the performance of BUSTLE. First, we investigate the predictions of the model when it run on the intermediate values encountered during synthesis of the human-wrien written benchmarks. We generate histograms for the model's predictions on expressions that do appear in the solution and expressions that do not appear 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 that our model generalizes well to human benchmarks, despite the domain mismatch to the synthetic data used in training. The full results are in Appendix(Ei [E] Finally, we determined that all but one of the benchmarks solved by the baseline (no model, no heuristics) also solved by BUSTI.E, across both sets of benchmarks.
8

---

Published as a conference paper at ICLR 2021
5 RELATED WORK
For surveys on program synthesis and machine learning for software engineering, see Gottschlich et al. (2018): Solar-Lezann (2018); Gulwani et al. (2017); Allmmmns et al. (2018). A well-known synthesizer for spreadsheet programs FlashFill (Gulwani 2011), based Version Space Algebras (VSAs) which are powerful and fast. However, VSAs only apply to restricted DSLs, e.g., the top-most function in the program must be Concat, which allows it perform efficient divide and conquer style search. Our technique has no such restrictions.
Early work on machine learning for program synthesis includes DeepCoder (Balog et al. 2017). which uses a learned model 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. Odena & Sutton (2020) use property signatures within DeepCoder-see
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 (Bunel et al. 2018 Devlin et al., 2017, Parisotto et al. 201 7). but this approach does not have the ability inspect outputs of intermediate programs. Previous work has also considered using learning within syntax guided search over programs (Yin & Neubig
2017 Lee et al. 2018), but because these methods are top-down, is much more difficult to guide them by execution information, since partial programs will have holes. Finally, Nye et al. (2019) learns to emit partial program and fill in the holes with a symbolic search.
The most closely related work to ours is neural execution guiided synthesis, which like BUSTLE uses values produced by intermediate programs within a neural network. Zohar & Wolf (2018) process intermediate values of program using neural network for small, straight-line DSL., but they do not use the model to evaluate intermediate programs. Another approach is to rewrite programming language so that it can be evaluated "left-to-right", allowing values be used to prioritize the search in an actor-critic framework (Ellis et al.) 2019). Similarly, [Chen et al. (2019) use intermediate values while synthesizing program using neural incoder-decode model, but again this work proceeds in 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 (Daumé et al. [209 Ross et al. 2011 Chang et al. 2015)). Combining more sophisticated imitation learning strategies into BUSTLE is an interesting direction for future work.
6 CONCLUSION
We introduced BUSTLE, a technique for using machine learning to guide bottom-up search for program synthesis. BUSTLE 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 sub-expression of the desired solution. We have shown that BUSTLE improves over various baselines, including recent deep-learning based program synthesis approaches (DeepCoder and RobustFill), on two challenging benchmark suites of atring-manipulation tasks, in terms of candidate programs considered as well as wall-clock time. In fact, showing that marning-in-the-lowe enough for program synthesis is perhaps the major contribution of this work. The idea of learning in- too-loop, though novel as far as we are aware, is relatively obvious, but through this work we learned that it can be efficient enough provide time speedups overall.
can be made fast
ACKNOWLEDGMENTS
The authors thank Sam Schoenholz and the anonymous conference reviewers for their helpful reviews and comments on our paper.
REFERENCES
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):81, 2018.

---

Published as a conference paper at ICLR 2021
Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. In Formal Methods in Computer-Aided Design. FMCAD 2013, Portland, OR, USA, October 20-23, 2013, pp- 1-8. IEEE, 2013. URL http::h/tteeteeeeeeeeee (eccumnnt/6673883
feee. org/
Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. DeepCoder: Learning to write programs. In International Conference on Learning Representations (ICLR), 2017.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018.
Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Daume III, and John Langford. Learning to search better than your teacher. In International Conference Machine Learning (ICML), 2015.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In Interna- tional Conference on Learning Representations (ICLR), 2019.
Hal Daumé, III. John Langford, and Daniel Marcu. Search-based structured prediction. Machine Learning Journal, 2009.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-Rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In International Conference on Machine Learning (ICML), 2017.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with REPL. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Justin Gottschlich, Armando Solar-Lezama, Nesime Tatbul, Michael Carbin, Martin Rinard, Regina Barzilay, Saman Amarasinghe, Joshua B Tenenbaum, and Tim Mattson. The three pillars of machine programming. ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pp. 69-80. ACM, 2018.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pp. 317-330. ACM, 2011. doi: 11445/926385.1966222
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends in Programming Languages, 4(1-2):1-119, 2017.
John R Koza. Genetic programming as means for programming computers by natural selection. Statistics and computing, 4(2):87-112, 1994.
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based program synthesis using learned probabilistic models. In Conference on Programming Language Design and Implementation (PLDI), pp. 436 436-449, June 2018.
Zohar Manna and Richard J. Waldinger. Toward automatic program synthesis. Commun. ACM, 14(3): 151-165, 1971. doi: 10.1145/362566.36666 URL httpttt///d.... org/100.145/365555 362568
Aditya Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Kalai. machine learning framework for programming by example. In International Conference on Machine Learning (ICML), pp. 187-195, 2013.
Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama, Learning to infer program sketches. In International Conference Machine Learning (ICML), pp. 4861-4870, 2019. URL http:ttttp/proccednnng. mml. wtt.ll..pprs/////////// 9a. html
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference Learning Representations (ICI.R), 2020. 2020.
10

---

Published as a conference paper at ICLR 2021
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Representa- tions (ICLR), 2017.
Stephane Ross, Geoffrey Gordon, and Drew Bagnell, A reduction of imitation learning and structured prediction to No-Regret online learning. In Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 305-316, 2013. doi: 16.144//455116624511
Kensen Shi, David Bieber, and Rishabh Singh. TF-Coder: Program synthesis for tensor manipulations, 2020.
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program symthesis. In International Conference on Learning Representations (ICLR), 2019. URL httptttpss//ppppeeeeeeeee net. wtwp://wwwwetfoormeecemmm
Eye0SnAqym
Armando Solar-Lezama, Introduction to program synthesis. https://people.csst mit eett///aolar/yyytttiisccoorrrrrp
2018. Accessed: 2018-09-17.
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodík, Sanjit A. Seshia, and Vijay A. Saraswat. Combinatorial sketching for finite programs. In Conference Architectural Support for Program- ming Languages and Operating Systems (ASPLOS), pp. 404-415, ACM, 2006.
Phillip D Summers. A methodology for LISP program construction from examples. Journal of the ACM, 24(1):161-175, 1977.
Abhishek Udupa, Arun Raghavan, Jyotirmoy Deshmukh, Sela Mador-Haim, Milo K Martin, and Rajeev Alur. TRANSIT: Specifying protocols with concolic snippets. In Conference Programming Language Design and Implementation (PLDI), pp. 287-296, 2013.
Patrick H. Winston. Learning structural descriptions from examples. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 1970.
Pengeheng Yin and Graham Neubig. syntactic neural model for General- code generation. In Assocation for Computational Linguistics (ACL), 2017.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2094-2103, 2018.

---

Published as a conference paper at ICLR 2021
A 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), right (Right) of a string; replacing substring of one string, indicated by start and end position, with another string (Replace), removing white space from the beginning and ending of string (Trim); concatenating string with itself specified number of times (Repea substituting the first & occurrences of substring with another (Subst i tute); converting an integer string (ToText); and converting a string LowerCase, UpperCase, or every word capital- ized (P @roperCase). Integer functions include arithmetic, returning the index of the first occurrence of substring within string (F wiind), and string length (Len). We also have some functions either consuming or producing booleans (I Equals, Greater Thann, Finally, few commonly useful string and integer constants are included.
To).
B LIST OF BENCHMARK PROGRAMS
Here show each of our 38 human-written benchmark problems, and possible solution written in a DSL that is a superset of the DSL used by our synthesizer. We have separated them into Listing Listing 4 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.
C LISTING OF PROPERTIES USED
BUSTLE 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 an integer, a string, or a boolean. In an abstract sense, property acts an input and output, but some properties will simply ignore the input, and so we implement those as functions with only one argument. Thus, we have six types of properties in principle:
properties acting on single string (Listing
properties acting single integer (Listing 6
properties acting single boolean (there is only of these).
properties acting on string and the output string (Listing 7
properties acting on an integer and the output string (Listing
properties acting on boolean and the output string (we don't actually use any of these presently).
For 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-argund angleetrggmmet string properties for the output and two sets of doublc-argument string properties, one for each input. We fix maximum number of inputs and pad the signatures that they are all the same size.
D MORE IMPLEMENTATION DETAILS ABOUT ROBUSTFILL BASELINE
To make the vanilla model proposed in Devlin al. (2017) work our benchmarks, we have made the following necessary changes:
As the vanilla model only allows single input per each onput-output pair, here concatenate the variable number of inputs with a special separator token.
Following Devlin et al. (2017), the vocabulary of input-output examples are constructed at the character level, as there are numerous integer and string literals our benchmark and training tasks.
The desired programs may use string constants which may depend on the particular oututt examples. In addition to predicting program tokens, RobustFill may also need to predict the string constants character-by-characde when necessary.
12

---

Published as a conference paper at ICLR 2021
Histogram
Histogram Negatives
35000
30000
20000
20000
15000
10000
3.0 0.2 0.6
0.5
0.0
2.2
0.5
0.0
Figure 4: Histograms of model predictions for expressions seen while solving benchmarks. (Left) for expressions that were sub-expressions a solution, 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-cxpressions solution, predictions skewed close to O.
There could be out-of-vocabulan characters in the input-output examples, as the test benchmarks have a different data distribution than synthetic training examples. In this case, we replace these characters with spaces.
use the same training data to train the RobustFill model. We first retain 10% of the training samples for validation, and identify the best number of training epochs. Then we retrain the model using full data for that many epochs. The batch size we use 1024, with fixed learning rate le-3. When decoding the program,
a 3-layer LSTM with embedding size of 512.
During inference, we use beam search to obtain the most likely programs, following Devlin et al. (017). On single GPU with 16 GB of memory, the maximum beam size we use is M S0, 000, which is already several magnitudes larger than 1000 (the largest beam size used in original paper). It takes roughly 25 seconds perform this beam search, which is conveniently close to the 30 second time limit in our experiments.
E ANALYSIS OF MODEL PREDICTIONS
We investigate the predictions of the model when it is run on the intermediate values actually encountered during synthesis of the human-writter benchmarks. We compute separate histograms for the model's predictions on expressions that do appear in the solution and expressions that do not 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 that our model generalizes well human benchmarks, despite the domain mismatch to the synthetic data used in training. See Figure
13

---

Published as a conference paper at ICLR 2021
// add decinal point 12 not present
(IEIRBOR vai_01), CONCATENATE (vac_ ",0"1, var_
// plus sign to positive insegers
TF (BBACTT117FT//aY__ 12, "-"), var_o, ("" var_o))
// appand
the hour depending if it's morning
CONCATENATE (LEFT (var_o, MINUS (PIN var_0), 11), IF (BXACTTIVa "mocning"), AM", PX")
10 // fix cspitalization of city and state CONCATENATE (LEFT (PROPER D), MENUS (VEN 11), (PPERIRICETTV0=_.. 11))
12
13 // capitalize the fizst word and lowezcase the rest
14 REFLACE (
(PPER 111)
15
string consains second T0_TEXU (ISSUNBER (FIND (ver_i, var_01)]
whether
17
18
19 // whether the flest string contalns the second, ignoring
20
TEXT (ISNUMBER (PIND (LONER(vaE_ LONER (var_0))))
22 // count the number of Limes the second string appeace in the fiest
23
TEXT (DIVLUE (MLNUS (VEN(var_0, LEN (SUBSTILLLE (var_ var_l, "")),, (v)r_11))
24
25 // create enail addreas from name company
26
LOKER LOKER (CONCCTENATEE (LEFT 11, var_i, "3", var_2, *,cem"))
27
// change DENMYYTY date MM/DD/YYYY CONCNERRAEE IMID (var_0, 3, 2), "/", REPLACE(var 3, 2, */"))
29
31 // change WYY-MM-DD, date to VYYY/MM/3D
32 SUBSTITUTE (var_D, *-", */"1
33
34 // change KYYX-MN-DU date to WM/DD
SUBSTTTCTR (RIGHT (VEr_0, *-",
36
37 // extract
batween 38 [var__, (FINN var_Dl, 2), MTNUS (MTNSS (PTSD var_u, 91, FIND var_o)), 231
part
39
40 // extract the of URL starting from the 3rd slash
41 RICHT (var_ ADD AD, MINUS (LEN (var__), FIND("/", var_o, ADD (FIND var_0), 201131
43 // get first name from second column (var__,,, MTNNS ", var_1), 1))
45
16 // whether the string is lowercase
47 (SxAC (ONE((var_0)) "true", "false")
48
//
50 RICHT (var_3, MINUS (var___) FINE ", var_0))1
52 // output "Completed" if 1008, "Not Yet Started" if 03, "In Progcess" othezwise
53 IF (va=_0="100s*, "Completed", IP (var__0="0"", "Hot Yet Started", "In Progress"))
54
58 // encl ose n numbers in parencheses
(LEFT Ivar_D, """), CONCATENATE (SUBST:TUTE (var_0, "* "("), *)",, var_0)
Listing 3: Potential solutions for our benchmarks, along with comments describing the semantics of the solution.
14

---

Published as a conference paper at ICLR 2021
// pad with spaces to given (REAATTATE MINUS (VAGUE LEN 1BN var_
// number with to width CONCATENATE
MENUS (5, 1eN(vo=_0)13 var_c)
// the depth of path, 1.e,, count the number of /
TR_T (MTNUS ITEN (var__), (SN T/", "1)))
10 // extract the rest of a word given a prefix
RICHT (var_), MINUS (LEN (vor_0), (oN(v==_1)))
12
// prepend
14 CONCATEKATE ("ME. ", RIGHT (vaz_0, KINUS ILEN (var_0), FIND ", 11r_
15
16 // prepend Mr. or Ms. last depending gender
17 CORCATERATE (LP (EXACI (var_l, "male"), "Xr. "Ms. "),
18
RIGHT (var_0, MINUS (1aN(s0 FIND ", var_01)))
19
leading trailing spaces tabs, lowercase 21 TRIM (LKKE
22
25 // replace <COMPANт> in string with given company name SUESTICUTS (var_0, "<CUMPANY>", var_ll
24
26 // zeplace com with org SUBSTIZUTH (var_ "com", "ozg",
28
29 // select the first string, or the second the first is HONE (EXACT(var_6, "BONE") var_l, var_0)
30
31
atrings, defaulting to the firat equal length 33 IP (GT (GI (1EN LEN (var_0)), var_l, var_01
// select the longer
35 // whether the two strings are exactly equal,
no
36 (RXACT var_ll, "yas", *na*)
37
38 // whether the two strings are exactly equa" ignoring case, yes or no (OEE IoHBRivar_1)), "yea", "no")
40
// length string
42 TEXT (L8N
43
44 // extract the rast of word given auffix
45 LEFT (var_0, MINUS (LEN (var_o), teN
47 // swap the case of string that is entirely uppercase lowercase (EXACT(var_D, LONER (vor_ UPPER (var_0), (var_O)
49
50 // truncate and add ... if longez than characters CONCATENATE (var_0, 15), "..."), var_0)
(IRM
52
one cel: CURCATERATI (LAET (LEFT (ver_,, 1), MID (var_0, ADU ( ", var_0!, 1), 1))
create acronya
54
56 // create capital ised acronym from two words in one cell
57 JPPER (CONCATENATE (LBFT 11, (var___ ADD (FIND ver_0), 11, 1)1)
Listing 4: Potential solutions for our benchmarks, along with comments describing the semantics of the solution.
15

---

Published as a conference paper at ICLR 2021
str. str.isEmpty(i ()
77 15 empty?
str.length(1
17 single char?
str. str.length() <=
17 18 short string?
str.equals (Lover)
lovercase?
atr.equals (upper)
17 15 uppercase?
str.containg
contains space?
str.contsins
// contains comna?
str.conter..... sir.ccottinn
// contains period?
atr.containg("-1
containg dash?
10 S.r.contains("77
// contains slash?
str.matches
contains digits?
12 str.matches (d="))
1/ only digita?
13 str.matches (".>XE 2A 2]..*
contains letters?
str.matches (a[a-zA-2] =*)
// only letters?
Listing Java code for all Properties acting on single Strings.
Integer 0
/7 18 zero?
integer
integer == 2 integer
// is two?
negative?
9 integer 66 integer <e 3 // 15 small integer?
integer 46 integer // large integer? integer
medium integez?
Listing 6: Java code for all Properties acting on single Integers.
patputStr.containn tatr)
// output contains input?
output
input?
purputtStr.endssktaktttt.
// output ends with imput?
imput contains output?
// Input starts with cutput?
str.endawtch
str.
// input ends with output?
curpputS:rtower.contall flower)
// output contains input ignoring case?
Bot.putti:1oowerstaattte (lower]
// output starts with input ignoring case?
ootpputSizzooeez.endiiii.. llovez)
output
input ignoring
10 cower.contaaa (tw..occcacasttrtttttssseeeeee
// input contains output ignoring case?
lwwer.atartaaiih St
// input starts with cutput ignoring case?
12 lower.endsW:th Su rtoower)))
// input ends with output ignoring case?
13 str.equala
14 (outpptttutt
// imput equals output?
output ignoring 15 str. () =- outputätz. // Imput sane length as output?
(outputttrtt
// input
str.length outputStr length
// input
output?
17 str.length ourputst:.Length
// imput longer than cutput?
Listing 7: Java code for all Properties acting String and the output String.
integer < outputtL::.eegghh.
// less than output length?
integer outputStr.length.)
// less equal to output lengsh?
integer output.Str.length.
// is equal to output length?
Integer autputtstr.lengte
greater equal output length?
integer > OutputSLr.Lengthi
// 1s greater than outpu: length?
(integer (enggh))te.ienghh())
very
output length?
aba (integer outpatttrr.
// 1s close output length?
Listing 8: Java code for all Properties acting Integer and the output String.
16


Reviews:
[{"review_id": "pSdFuuNKS-T", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper proposes an approach to program synthesis which is done in a bottom-up fashion.\nIn order to guide the search more effectively the bottom-up search algorithm is accompanied with a model predicting whether particular sub-expressions of a program are promising directions.\nAs the system for program synthesis needs to be real-time capable, the proposed approach heavily relies on property signatures as introduced in (Odena & Sutton, 2020) for featurizing program inputs.\nThe here proposed system called BUSTLE is shown to perform favorably to a set of baselines including state-of-the-art approaches to program synthesis.\n\n# Resons for Score\nGenerally speaking, I really enjoyed the reading of the paper. The paper is well structured and written as well as easy to follow.\nEverything is explained in sufficient detail, i.e., thorough but concise.\nThe contribution of the paper is significant and the approach is technically sound.\n\n# Pros\n\nAlthough the methods might not be feasible to be used in practice yet, it performs reasonably well with only a few examples for describing the desired behavior of the programs to be synthesized.\nHowever, the programs that are synthesized are still quite smallish. It would be interesting if the authors could also highlight some future directions in order to make a step towards more complex scenarios.\n\nThe paper provides compelling experiments which are set up in a thoughtful and rational manner rather than throwing various methods on some benchmarks.\nThe experiments are conducted in a very systematic way, facilitating insights into the performance of the proposed method as well as how it compares to the baselines.\nHowever, a taxonomy of problems (e.g. how to quantify problem severity etc.) would maybe help to better spot differences in performance.\n\nThe method itself is quite simple. The authors almost seem to apologize or vindicate. I rather consider it an advantage.\n\nThe proposed approach is well placed in the context of the existing literature.\n\n# Cons\n\nSome information about the experiment setup is missing: Are all benchmark tasks of one set (either on the proposed set or SyGuS) run in a row?\nIs the order kept consistent? What hardware is used for conducting the experiments?\n\n# Questions during rebuttal period\n\n- Out of curiosity: If the order is the same for all the benchmarks for all methods, it seems to be the case the method being fastest to find a solution for a benchmark task varies from task to task,\nand the here proposed method does not always seem to be the fastest for any instance. Given the demanding real-time setting, do you think an algorithm selection approach would work here, choosing a method\non a per task basis?\n\n\n\n# Typos\n- p.3: \"during the search, [...]\" => During the search\n- p.6: \"fixed length representation\" => fixed-length representation (this is occurring at least twice)\n- p.8: \"This provides further evidence the our model [...]\" => This provides further evidence that our model [...] (occurs also in the appendix)\n- p.8 last but one paragraph in Section 5: \"[...], while like BUSTLE, uses values produced by intermediate programs [...]\" => The comma after BUSTLE is kind of irritating. Please, consider removing it or adding another comma before \"like\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "dyENazeehj6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to add machine learning component to the bottom-up program synthesis algorithm. Machine learning component uses information from property signatures to prioritize the candidate expressions for further expression space exploration. Authors show that their algorithm outperforms other approaches on the benchmark sets.\n\nPositives:\n- The paper presents incremental improvement to the bottom-up program synthesis algorithm.\n- Authors have considered the efficiency issues of adding machine learning model into the bottom-up search and came up with optimizations that result in model cost being lower than efficiency gains.\n- Authors figured out how to train the NN for their task absent actual training dataset.\n- Algorithm outperforms baseline approaches.\n- All sections of work are well presented, understandable, and easy to follow. The paper was a pleasure to read.\n\nConcerns:\n- My concerns can be summarized in short question: are contributions significant enough?\n- In experiments, the algorithm barely outperforms a baseline with heuristics only. This is the case for both authors' benchmark set and SyGuS benchmark set.\n- Using property signatures is not new. The novel part is adding NN to prioritize search based on property signatures. I would say that the idea to use NN for this is not significantly novel. There is some novelty in setting up training dataset as I observed above. \n\nPossible mitigation of concerns:\n- Choose more complicated problem (benchmark) set. This may show where baseline approaches do not work well. Since authors created first benchmark set themselves, I am surprised this was not done already.\n- Another variation would be a useful problem set that is not more complicated, but where for some reason baseline(s) do not work.\n- Provide results for a baseline that uses property signatures without NN. This is a minor mitigation: it is possible that property signatures without NN will not outperform the baseline with heuristics. It still would be interesting to see the comparison.\n\nIn summary: I am not convinced that contribution is significant enough for acceptance.\n\nReproducibility: It would be nice if authors presented actual NN architecture used for ease of reproducibility.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AcyLvDE5bCI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to combine bottom-up program synthesis from input/output examples with a machine learning model. The machine learning model determines for each candidate intermediate value (coming bottom-up from the inputs) if it may be considered at the next round of candidate expression generation or it will be deferred for at least K rounds (with K up to 5 in the evaluation).\n\nPros:\n\n- The paper is evaluated on a good range of string manipulating programs. The presentation and the evaluation is showing the advantages of the reweighting for the number of solved programs.\n\n- The advantages of the method are not only in the number of candidates explored, but in actual wall-time. This is a relatively rare result - many prior synthesis with machine learning tasks completely actual running time.\n\n- The paper and its implementation address the engineering side of the work - batching the requests for effective machine learning and interestingly, the results are good even when the machine learning model was trained on random data.\n\nCons:\n\n- It makes it difficult to compare based on the numbers, but it looks like the result is not competitive with existing solvers for the CyGuS PBE competitions. The paper should mention where it stands here.\n\n- The actual contribution of the work is mostly in the implementation and combining known techniques.\n\nIn terms of writing, there are some improvements that are possible:\n\n- The algorithm description is not self-contained. It is not completely clear what ExtractConstants does. The inputs I and outputs O should be vectors, but they are used as sets. The algorithm actually is unclear here. Does the set E[1] include the entire input vector for input examples as an element and each constant as a vector of the constants with this length (In this case it should be E[1] = {I} \\cup C)?\n- There is also no intuition for what concrete property signatures make sense.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5OBxRtUyW-j", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Note about NeurIPS ’20 version: \n\nI was on the NeurIPS ’20 program committee and I was assigned an earlier version of this paper. As such, I’m deeply familiar with it. In its NeurIPS form, I felt it wasn’t ready for tier-1 publication. However, my concerns were principally around the lack of experimental results. I strongly supported of the ideas presented in the paper, but I fought to ensure it wasn’t accepted to NeurIPS because I felt it would have been a disservice to both NeurIPS and the authors, resulting in a rather mediocre paper that could have been exceptional if the proper experiments were run. I attempted to make this clear in my review and encouraged the authors to address this weakness.\n\nIt appears the authors have addressed my primary concern. This version of the paper resolves my critical reservation of weak empirical results – the results, I believe, are now satisfactory of tier-1 publication, which include four different synthesis systems and over 100 different synthesized programs of two different domains. As such, I now support its acceptance at ICLR.\n\nSummary:\n\nThis paper appears to be the first work to use program signatures (ICLR ’20, Odena & Sutton) for program synthesis. The high-level concepts the authors present, as I understand them, is that by using program signatures for program synthesis, they can more closely replicate the process of program synthesis the way programmers develop programs. That is, by breaking one large program into many small sub-programs. Once enough of these small sub-programs have been generated, they can be composed together to solve the larger program – the actual goal.\n\nAssuming this hypothesis holds, the end result might be that such an approach would result in a program synthesizer that could generate both (i) more correct programs, (ii) faster than prior systems. For their experimental evaluation, this hypothesis seems to hold and BUSTLE does in fact generate more correct program, more quickly than prior state-of-the-art. The authors compare BUSTLE to three other variant systems: a baseline (less sophisticated BUSTLE system), RobustFill (ICML 2017), and DeepCoder (ICLR 2017). RobustFill and DeepCoder have demonstrated state-of-the-art performance, historically, so I believe these comparisons are sufficient for this paper’s acceptance.\n\nOverall, I think the paper provides a truly novel approach to program synthesis with its fusion of program signatures. I am admittedly biased in favor of program signatures, because I believe the future of machine programming / software 2.0 / neural programming / program synthesis with both stochastic and deterministic approaches (whatever we want to call it) is going to be heavily reliant on our ability to lift concepts from code (the “what”) which is notably more challenging than lifting the implementation (the “how”). This is because the “what” tends to not necessarily be obvious from the code, whereas the “how” almost always is – it’s the implementation. With that in mind, this paper presents what I believe is the first demonstrable evidence that program signatures can be used in this fashion. I suspect this is just the beginning of exploration with program signatures – I expect a flurry of follow-up research to emerge that uses them.\n\nWhen taken holistically, I strongly support accepting this paper, but I do have some minor nits I’d like the authors to address.\n\nMinor suggestions:\n\n1. There appears to be no system diagram of BUSTLE. While an expert in the space of program synthesis and property signatures can likely understand what is going on, non-experts I think will really struggle without some kind of visual diagram showing how BUSTLE works. It should be relatively easy to add this diagram to the paper and I believe it will make the paper more widely accessible. If only one of my recommendations is addressed by the authors, I would request it be this one.\n\n2. There appears to be multiple locations where the authors seem to deem neural network inference is “too slow” without qualification. I think this is a mistake and is a bit of a turn off and it’s a bit of a confusing one given that BUSTLE uses neural network inference. Yes, I do agree with the authors that inference with large neural networks could make the problem of program synthesis slower, but I don’t believe this is a universal truth. I think it’s proportional to the computational complexity of the neural network. I would request the authors find all such “inference is too slow” cases in the paper and properly qualify them. I suspect this will encourage future work to consider other neural network architectures that may be competitive or even outperform BUSTLE.\n\n3. Can you label the different variants of BUSTLE from something like “Using model and heuristics” to just BUSTLE, “Using model only” to BUSTLE (model only), etc. Right now it’s a bit confusing at first glance on Figure 2 to see which is the full BUSTLE system because there isn’t actually any legend item that is called “BUSTLE”. Should be an easy fix and will likely make the figure easier for the audience to understand.\n\n4. Can you please drop the word “very” from the paper everywhere it appears? I do not have a mathematical representation of what that word means (nor does anybody I think) and, as such, I believe it introduces unnecessary ambiguity and also wastes paper space.\n\n5. I couldn’t tell how the BUSTLE training time was factored into the analysis. Can you find a way to explain that more clearly? I realize that it’s a potential one-time only penalty, but it doesn’t come for free (to my understanding) while some traditional program synthesis systems using formal methods can simply generate programs without any learning overhead. I think this needs to be captured somewhere so people don’t forget about this cost.\n\n6. I got a little confused by the comments about removing restrictions of Concat() in the second paragraph in section 2.2. Can you try to explain that more clearly?\n\n7. Can you provide some intuition on the rationale behind keeping “100 positive and 100 negative values” as explained in the last sentence in section 3.1?\n\n8. Can you double check to ensure all of your acronyms are fully spelled out first? I’m familiar with all of them, but others might not. I don’t think I saw the spelled out versions of DSL, AST, JVM, etc. While these terms are generally widely known in the programming languages community, I’m not sure if the machine learning community is as deeply aware of them. Regardless, it seems to me that it’s usually a good idea to spell out all acronyms first.\n\n\nFuture work:\n\nDo you really think an abstract syntax tree (AST) representation is the right representation for this approach? \n\nI’m not so sure. I recommend taking a look at the Aroma’s simplified parse tree in the paper by FAIR, Berkeley, and Riverside (OOPSLA ’19) and, more comprehensively, MISIM’s context-aware semantics structure from Intel, Georgia Tech, MIT (arxiv). I suspect a next iteration of BUSTLE using either of these structures might result in even better performance than what you’ve currently achieved with an AST representation. But, that’s just a guess. :)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have supported the acceptance of this paper (R3 and R5 were particularly excited) so I recommend to accept this paper.
Decision: Accept (Spotlight)