Learning to Represent Programs with Property Signatures
Authors: Augustus Odena
Charles Sutton
Venue:  (2020)
Keywords: Program Synthesis

Abstract: We introduce the notion of property signatures, a representation for programs and
program specifications meant for consumption by machine learning algorithms.
Given a function with input type τ_in and output type τ_out, a property is a function
of type: (τ_in, τ_out) → Bool that (informally) describes some simple property
of the function under consideration. For instance, if τ_in and τ_out are both lists
of the same type, one property might ask ‘is the input list the same length as the
output list?’. If we have a list of such properties, we can evaluate them all for our
function to get a list of outputs that we will call the property signature. Crucially,
we can ‘guess’ the property signature for a function given only a set of input/output
pairs meant to specify that function. We discuss several potential applications of
property signatures and show experimentally that they can be used to improve
over a baseline synthesizer so that it emits twice as many programs in less than
one-tenth of the time.

Published as a conference paper at ICLR 2020
LEARNING TO REPRESENT PROGRAMS WITH PROPERTY SIGNATURES
Augustus Odena, Charles Sutton Google Research
(august charlessuttor @googl com
ABSTRACT
We introduce the notion of property signatures, a representation for programs and program specifications meant for consumption by machine learning algorithms. Given a function with input type Tin and output type Tout. a property is a function of type: (Tin: Tout) - Bool that (informally) describes some simple property of the function under consideration. For instance, if Tin and Tout are both lists of the same type, one property might ask 'is the input list the same length the output list?". If we have list of such properties, we can evaluate them all for our function to get list of outputs that we will call the property signature. Crucially, we can 'guess' the property signature for a function given only set of input/output pairs meant to specify that function. We discuss several potential applications of property signatures and show experimentally that they can be used to improve over baseline synthesizer so that it emits twice as many programs in less than one-tenth of the time.
INTRODUCTION
Program synthesis is longstanding goal of computer science research (Manna & Waldinger 1971
Waldinger al.] 1969. Summers 1977 [Sha Pnueli Rosner [989 Manna Waldinger] 1975).
arguably dating the 1940s and 50s (Copeland) 2012 Backus et al. 1957). Deep learning methods have shown promise at automatically generating programs from a small set of input-output examples (Balog et al. 2016 Devlin et al. 2017 Ellis et al. 2018b 2019b). In order to deliver on this promise, we believe it is important to represent programs and specifications in a way that supports learning. Just as computer vision methods benefit from the inductive bias inherent to convolutional neural networks (LeC'n et al. (989), and likewise with LSTMs for natural language and other sequence data (Hochreiter Schmidhuber 1997), it stands reason that ML techniques for computer programs will benefit from architectures with a suitable inductive bias.
We introduce new representation for programs and their specifications, based on the principle that to represent program, we can use set of simpler programs. This leads us to introduce the concept of property. which is a program that computes a boolean function of the input and output of another program. For example, consider the problem of synthesizing a program from small set of input-output examples. Perhaps the synthesizer is given a few pairs of lists of integers, and the user hopes that the synthesizer will produce a sorting function. Then useful properties might include functions that check the input and output lists have the same length, if the input list a subset of the output, if element 0 of the output list is less than element 42, and so on.
The outputs of set of properties can be concatenated into a vector, yielding a representation that we call property signature. Property signatures can then be used for consumption by machine learning algorithms, essentially serving as the first layer of a neural network. In this paper, we demonstrate the utility of property signatures for program synthesis, using them perform a type of premise selection as in [Balog et al. (2016). More broadly. however, we envision that property signatures could be useful across a broad range of problems. including algorithm induction (Devlin et al. (017). improving code readability (Allamanis et al. 2014), and program analysis (Heo et al. 2019))
More specifically, contributions are:

---

Published as a conference paper at ICLR 2020
We introduce the notion of property signatures, which a general purpose way of featurizing both programs and program specifications (Section
We demonstrate how use property signatures within machine-learning based synthesizer for general-purpose programming language. This allows us to automatically learn a useful set of property signatures, rather than choosing them manually (Sections 3.2 and
We show that machine learning model can predict the signatures of individual functions given the signature of their composition, and describe several ways this could used to improve existing synthesizers (Section 5).
We perform experiments on a new test set of 185 functional programs of varying difficulty, designed to be the sort of algorithmic problems that one would ask undergraduate computer science examination. We find that the use of property signatures leads to a dramatic improvement in the performance of the synthesizer, allowing it to synthesize one-tenth of the time (Section 4). An example of a complex program that was synthesized only by the property signatures method shown in Listing
twice as many programs in less than
For our experiments, we created a specialized programming language, called Searchd (Section 2). based on strongly-typed functional languages such as Standard ML and Haskell. Searcho designed so that many similar programs can be executed rapidly, is needed during large-scale distributed search during synthesis. We release" the programming language, runtime environment, distributed search infrastructure, machine learning models, and training data from our experiments so that they can be used for future research.
Fun muncju_justseen (xs :List<Int>) -> List<Int> { let triple = list_ fes__foldl________ (List<Int>, Int, Bool)> xS, (nil<Int>, 0, -,,
5
(list_elt, (ace, last_elt, first))
(ordsserr (List__ last_elt)), [1icons_[iist_ek acc), list_elts elt, _01,, {((ace
list_elt, _011]
});
10
1ist_ Dist_reverse__tO (triple))
1;
Listing 1: program synthesized by our system, reformatted and with variables renamed for readability. This program returns the sub-list of all of the elements in list that are distinct from their previous value in the list.
PROGRAMMING BY EXAMPLE AND THE SEARCHO LANGUAGE
In Inductive Program Synthesis, a program meeting that specification. Inductive Synthesis is generally divided into Programming by Example (PBE) and Programming by Demonstration (PBD). This work is focused on PBE. In PBE, we are given a set of input/output pairs such that for each pair, the target program takes the input to the corresponding output. Existing PBE systems include Winston (1970). Menon al. 2013). and Gulwani (20IT) A PBE specification might look like Listing 10 paipaii
given specification of program and goal is to synthesize
(1, 1), (2, 4), (6, 36), (10, 100) Listing 2: An example PBE specification.
for which satisfying solution would be the function squaring its input. Arbitrarily many functions satisfy this specification. It is interesting but out of scopa" to think about ways to ensure that the synthesis procedure recovers the 'best' or 'simplest" program satisfying the specification.
Much (though not all) work on program synthesis is focused domain specific languages that
less than maximally expressive (Gulwani 201 Balog et al. 2016 Wang et al. 2017 Alur et al.
Searcho is heavily based on code written by Niklas Een, which is available at htttps:: http//gttttut.c//eeeeeeteeg. com/
tensor f1 ow/ http://eeemattttttetecceet monsorflo//deepmahh..
ree httt:///eeeemeeeeeeettett//////e
AAvailable at http:::tts//.mmm.mmmm g thub. hoaaa////o/aaaaaaeeaaaaaaacaaaaa
'Though note that in this work and in prior work. the search procedure used will tend to emit 'shorter' programs first, and so there Occam's Raazorrty argument (Spade & Panaccio 2019) to be made that you should get this for free.
2

---

Published as a conference paper at ICLR 2020
2013). We would like focus on the synthesis of programs in a Turing complete language, but this presents techmical challenges: First, general purpose languages such as C++ or Python are typically quite complicated and sometimes not fully specified: this makes it challenge to search over partial programs in those languages. Second, sandboxing and executing code written in these languages is nontrivial. Finally, searching over and executing many programs in these languages be quite slow, since this is not what they were designed for.
For these reasons, we have created a general-puposse Turing complete programming language and runtime. The programming language is called Searcho and it and its runtime have been designed specifically with program synthesis mind. The language can roughly be thought of as a more complicated version of the simply typed lambda calculus or as less complicated version of Standard MI. or OCaml Searcho code is compiled to bytecode and run on the Searcho Virtual Machine. Code is incrementally compiled, which means that the standard library and specification can be compiled once and then many programs can be pushed on and popped off from the stack in order to check them against the specification. Searcho is strongly typed with algebraic datatypes (Pierce & Benjamin 2002 Searcho includes a library of 86 functions, all which are supported by our synthesizer. This a significantly larger language and library than have been used in previous work neural program synthesis.
We have also implemented baseline enumerative synthesizer. The main experiments in this paper will involve plugging the outputs of a machine learning model into the configuration for our baseline synthesizer to improve its performance on of human-constructed PBE tasks.
PROPERTY SIGNATURES
Consider the PBE specification in Listing 3
io_ to_pairs =
(I1, 2345, 345671, ([True, Falsel, (["Batman"), (111,2,3,,
[1, 2345, 34567, 34567, 2345, 11), [Truc, False, False, Truel), ["Batman", "Batman"]), [[1,2,3], [4,5, 6], [4,5, 61, [1]2,3]])
Listing 3: An example PBE Specification.
We can see that the function concatenating the input list to its reverse will satisfy the specification, but how can we teach this to a computer? Following Balog et al. (2016) we take the approach of training machine learning model to do premise selection for symbolic search procedure. But how do we get a representation of the specification to feed to the model? In [Balog et al. (2016), the model acts only on integers and lists of integers, constrains all integers to hie in 256, 256]. has special-case handling of lists, and does not deal with polymorphic functions. It would be hard to apply this technique the above specification, since the first example contains unbounded integers, the second example contains a different type than the firs and the third and fourth examples contain recursive data structures (lists of characters and lists of integers respectively).
Thankfully, we can instead learn a representation that is composed of the outputs of multiple other programs running on each input/output pair. We will call these other programs properties. Consider the three properties in Listing
all inputs in outputs
outs has mas_ddupicaates (outs)
(map (Ax
in outs) ins)
ouputs_has_duve ins outs
ins outs (len ins) == (len outs)
Listing 4: Three function projections that can act the specification from Listing
Each of these three programs can be run on all 4 of the input output pairs to yield a Boolean. The first always returns True for our spec, as does the second. The third always returns False the given examples, although note that it would return True if the examples had contained the implicit base case of the empty list. Thus, we can write that our spec has the 'property signature" [True, True, False).
*In this paper, we will present illustrative programs in Haskell syntax to make them more broadly readable. Searcho programs will be presented in Scarcho syntax, which similar.
'Types have been shown to substantially speed up synthesis. See c.g. Figure 6 of Feser et al, 2015 "So any function satisfying the spec will be parametrically polymorphic.
3

---

Published as a conference paper at ICLR 2020
How is this useful? From the first property of the input list. From the third we might guess that we have to add or remove elements from the input list. Finally, the second might imply that need create copies of the input elements somehow. This does not narrow our search down all the way, but it narrows down quite a lot. expressed in the same language as the programs we synthesizing, emit them using the same synthesizer. Later on, we will describe how we enumerate many random properties and prune them to keep only the useful ones. The property signatures that we consider in our experiments contain thousands of values.
infer that should not throw away any elements
Since the properties
can
Since the output of these properties is either always True, always False, or sometimes True and sometimes False, neural network can learn embeddings for those three values and it can be fed vector of such values, one for each applicable property, as the representation of program specification.
3.1 ABSTRACTING PROPERTIES INTO SIGNATURES
Now we describe our representation for a program f Tix + Tout. Each property is a program p (Tin: Tout) + Bool that represents single "feature" of the program's 's inputs and outputs which might be useful for its representation In this section, we assume that we have determined a sequence P= = ... Pr]] of properties that useful for describing and we wish combine them into a single representation of f. Later, we will describe a learning principle for choosing relevant properties.
We want the property signature to summarize the output of all the properties in P over all valid set of inputs in the natural
inputs to f. To do this, we first extend the notion of property way. If S is set of values of type Tin and E P. we define p(S) = {p(r, f(r)) x E S}. set of booleans, it can have only three possible values, either p(S) = { (True), or p(S) = (False), or p(S) = {True, False). corresponding respectively to the cases where is always true, always false, or neither. To simplify notation slightly, we define the function as [ AllTrue, II((False)) = AllFalse. and [I( ([Te, False)) = Mixed. Finally, we can define the property signature sig P.f) for a program f and property sequence P Pas
Because p(S)
sig(P, (S(P./) [[1] (Vp.(V
where (T is the possibly infinite set of all values of type Tix-
Computing the property signature for f could be intractable or undecidable, as it might require proving difficult facts about the program. Instead, in practice, we will compute an estimated property signature for small set of onput-output pairs Sio. The estimated property signature summarizes the actions of P on Sio rather than on the full set of inputs V(T..). Formally, the estimated property signature is
sig( (P, St.)
[[(p, Tous) I (Fing (Sto))-
(1)
This estimate gives us an under-approximation of the true signature of f in the following sense: If we have sig (P, 8) Mixed, we must also have sig( (P, f) Mixed. If sig S) AllTrue, then either sig(P, [) = AllTrue or (P, = Mixed, and similarly with AllFalse. Estimated property signatures particularly useful for synthesis using PBE, because can compute them from the onput- pairs that specify the synthesis task, without having the definition of f. Thus we can use estimated property signatures 'featurize' PBE specifications for use in synthesis.
3.2 LEARNING USEFUL. PROPERTIES
How do we choose a set of properties that will be useful for synthesis? Given a training set of random programs with random input/output examples, we generate many random properties. We then prune the random properties based on whether they distinguish between any of the programs. Then, given a test suite of programs, we do an additional pruning step: among all properties that give the same value for every element of the test suite, we keep the shortest property, because of Occam's 's razor considerations. Given these 'useful' properties, we can train a premise selector (Balog et al. 2016) to predict library function usage given properties. Specifically, from the remaining properties, we
lthough we write f a function, that is, as returning output, it is easy to handle procedures that do not. return value by defining Tour be special void type.
4

---

Published as a conference paper at ICLR 2020
compute estimated property signatures for each function in the training set, based on its input output examples. Then we use the property signature as the imput to a feedforward network that predicts the will give more details
number of times each library function appears in the program. In Section about the architecture of this premise selector, and evaluate it for synthesis. For now, we point out that this premise selector could itself be used to find useful properties, by examining which properties are most useful for the model's predictions.
3.3 WHY ARE PROPERTY SIGNATURES USEFUL?
Experiments in the next section will establish that property signatures our baseline synthesizer emit programs it previously could not, but we think that they can have broader utility:
They allow represent more types of functions. Property signatures can automatically deal with unbounded data types, recursive data types, and polymorphic functions.
They reduce dependency on the distribution from which examples are drawn. If the user of synthesizer gives example inputs distributed differently than the training data, the 'estimated" properties might not change much
They can be used wherever we want to search for functions by semantics. Imagine a search engine where users give specification, the system guesses property signature, and this signature guess is used to find all the pre-computed functions with similar semantics.
Synthesized programs can themselves become new properties. For example, once learn a program for primality checking, can use primality checking in my library of properties.
4 PROGRAM SYNTHESIS WITH PROPERTY SIGNATURES
We design experiment to answer the following question: Can property signatures help us synthesize programs that we otherwise could not have synthesized? As we will show, the answer yes!
4.1 EXPERIMENTAL SETUP
How Does the Baseline Synthesizer Work? Our baseline synthesizer is very similar to that in Feser et al. (2015) and works by filling in typed holes") That is, we infer a program type Tin - Tout from the specification and the synthesizer starts with empty 'hole' of type Tin + Tout and then fills it in all possible ways allowed by the type system. Many of these ways of filling-in will yield new holes, which can in turn be filled by the same technique. When a program has no holes, we check if satisfies the spec. We order the programs to expand by their cost, where the cost is essentially sum of the costs of the individual operations used in the program.
At the beginning of the procedure, the synthesizer is given configuration, which is essentially weighted set of pool elements that it allowed use to fill in the holes. A pool element a rewrite rule that replaces a hole with a type-correct Searcho program, which may itself contain its own, new holes. In our synthesizer, there is one possible pool element for each of the 86 library functions in Searcho, which calls the library function, with correctly- prreetly-typed holes for each of its arguments. The configuration will specify a small subset these pool elements to use during search. It is through the configuration that will use machine learning inform the search procedure, See Appendix A. for further details on this baseline system.
describe later.
How is the Training Data Generated? Our test corpus contains programs with 14 different types. For each of those 14 types, we randomly sample configurations and then randomly generate training programs for each configuration, pruning for observational equivalence. We generate up 10,000
*This argument does rely on properties being somehow simple. For instance, if the property does not compute whether list contains the value 777, it cannot fail to generalize with respect to the presence or absence of 777. Since search for properties in shortest-firs fashion. the properties simplicity, though certainly this hypothesis merits more experimental validation.
find should be biased toward
"I the synthesis literature, this approach of first discovering the high-level structure and then filling it in is sometimes called 'top-down' synthesis [Solar-Lezzamal 'bottom-up' synthesis, in which low-level components incrementally combined into larger programs.
eezama 2018). Top-down synthesis is to be contrasted with
5

---

Published as a conference paper at ICLR 2020
semantically distinct programs for each type, though of course some function types admit less distinct programs than this c.g. Bool + Bool). We also generate and prune random properties as described in Section 3.2 See Listing 5 examples of useful properties that were generated. (input, output) {
A: (List<Int>> <ist<Int>>>>>BB
1ist_ for for_alllllllllllll all <Int> (input, \x
fist_<<nt>> <Int> (x, output) 1
A (List<int>, List<Int>)~>Boo (input, output) {
not_ (is_even_ (list_len_<Int> cutput))]
A: (List<int>, List<Int>) (input, output) {
not_equal_<Int> ( ((ints_sum input), dints_sum, output))
7 A: (List<Int>, List<Int>)->Bod (input, output) { gt_
_en__Inn>>>>>> input), (list_len_kInd
output))
Listing 5: of the Properties with the highest discriminative power on functions of type List<Int> + List<Int>, The first checks if every element of the input list is in the output list. The second checks if the length the output list even. The third checks if sum of the input and the output list is the same, and the fourth checks if the input list is longer than the output list.
How was the Test Set Constructed? We've constructed test set of 185 human generated pro- grams ranging in complexity from one single line to many nested function calls with recursion. Programs in the test set include computing the GCD of two integers, computing the n-th fibonacei number, computing the intersection of two sets, and computing the sum of all pairs in two lists. We ensure that none of the test functions appear in the training set. See the open source code for more details this.
What the Architecture of the Model? As mentioned above, we train neural network to predict the number of times each pool element will appear in the output. This neural network is fully connected, with learned embeddings for each of the values AllTrue, AllFalse and Mixed.
How does the Model Output Inform the Search Procedure? Since have large number of pool elements (86), we can't run the synthesizer with all pool elements we want to find programs of reasonable length. This is both because will run out of memory and because it will take too long. Thus, we randomly sample configurations with less pool elements. We then send multiple such configurations to distributed synthesis server that tries them in parallel.
When we use the model predictions, we sample pool elements in proportion to the model's predicted number of times that pool element appears. The baseline samples pool elements in proportion their rate of appearance in the training set.
4.2 USING PROPERTY SIGNATURES LETS US SYNTHESIZE NEW FUNCTIONS
We 3 different of our distributed synthesizer for 100,000 seconds with and without the aid of property signatures. The baseline synthesizer solved 28 test programs on average. With property signatures, the synthesizer solved an average of 73 test programs. See Figure [ for more discussion. Indeed, it can be seen from the figure that not only did the synthesizer solve many more test programs using property signatures, but did so much faster, synthesizing over twice as many programs in one-tenth of the time as the baseline.
4.3 COMPARISON WITH DEEPCODER
We have conducted an experiment to compare premise selection using Property Signatures to the premise selection algorithm from (Balog et al. 2016). This required considerable modifications to the experimental procedure.
First, since the premise-selectio part of DeepCoder can only handle Integers and lists of Integers. we restricted the types of our training and test functions. In particular, we read through (Balog et 2016) and found four function types in use:
[int] -> [[nt]
g :: [int] -> Int
h :: ([Int], [Int]) -> Int
k (IInt), Int) -> Int
Listing 6: The four function types used in DeepCoder.

---

Published as a conference paper at ICLR 2020
120
baseline
baseline 2/3
baseline 3/3
100
signatures 1/3
test programs synthesized
signatures 2/3
signatures 3/3
80
60
40
0
20000
40000
60000
80000
100000
time elapsed (seconds)
Figure I: Comparison of synthesis with property signatures and without property signatures. The r-axis denotes time clapsed in seconds. Roughly speaking, we let the distributed synthesizer run for 1 day. The y-axis represenets the cumulative number of programs synthesized. On average, the baseline solved 28 of the test programs, while the baseline enhanced with property signatures solved 73 test programs (around 2.6 times many programs). Both the baseline and the run with property signatures were run with three different random seeds. Altogether, this experiment provides strong evidence that property signatures can be useful.
The types of and g aree taken directly from (Balog et al. 2016). The types of and are inferred from examples given in the appendix of (Balog et al. 2016). Their DSL does not technically have tuples, but we have wrapped the inputs their "tw-tinpttfuunttions in tuples for convienence.
Second, since DeepCoder can only handle integers betwen -55 and 255, we first re-generated all of our random inputs (used for 'hashing' of generated training data) to lie in that range. We then generated random training functions of the above four types. We then made data set of training functions associated with 5 input-output pairs, throwing out pairs where any of the outputs were outside the aforementioned range, and throwing out functions where all outputs contained some number outside that range.
Third, of the examples in our similar way. We filtered out functions that could not be so modified. After doing so, we were left with remaining test suite of 32 functions.
with the right types, we modified their input output pairs in
Finally, we trained a model to predict functions-to- to-use from learned embeddings of the onput-output pairs, in DeepCoder. We didn't see a description of how functions with multiple inputs had their inputs embedded, so we elected to separate them with special character, distinct from the null characters that are used pad lists.
Compared with the Property Signatures method, this technique results in far fewer synthesized test set programs. We did 3 random restarts for each of DeepCoder, Property Signatures, and the Random Baseline (recall that the random baseline itself is already a relatively sophisticated synthesis algorithm it's just the configurations that are random). The DeepCoder runs synthesized an average of 3.33 test programs, while the Property Signature runs (trained the same modified training data and tested on the same modified test data) synthesized 16.33. The random baseline synthesized programs average.
priori, this seems like a surprisingly large gap, but actually fits with what we know from existing literature. Shin et al. (2018) observe something similar: which is that DeepCoder-esque techniques tend to generalize poorly to a test set where the input-output pairs come from a different distribution than they do in training. This is the in our experiment, and it will be the case in any realistic
7

---

Published as a conference paper at ICLR 2020
setting, since the test set will be provided by users. Property Signatures are (according experiments) much less sensitive to such shift. This makes intuitive sense: whether an input list is half the length of an output list (for instance) is invariant to the particular distribution of members of the list.
Note that even if Property Signatures did not outperform DeepCoder on this subset of our test set, they would still constitute an improvement due to their allowing us to operate on arbitrary programs and inputs types.
5 PREDICTING PROPERTY SIGNATURES OF FUNCTION COMPOSITIONS
Most programs involve composing functions with other functions. Suppose that we are trying to solve a synthesis problem from set of input/output examples, and during the search we create partial program of the form (g())) for some unknown Since we know f. we know its property signature. Since have the program specification, we also have the estimated property signature for fog- == f()())). If we could somehow guess the signature for we could look it up in a cache of previously computed functions keyed by signature. If we found a function matching the desired signature, we would be done. If no matching function exists in the cache, we could start a smaller search with only the signature of g as the target, then use that result in our original search. We could attempt to encode the relationship between f and g into a set of formal constraints and pass that to a solver of some kind (De Moura Bjørnr 2008), and while that potentially an effective approach, it may be difficult to scale to language like Searcho. Instead, we can simply train machine learning model to predict the signature of g from the signature f and the signature of f / g.
Here we present an experiment to establish proof of concept of this idea. First, we generated data set of 10,000 random functions taking lists of integers to lists of integers. Then we randomly chose 50,000 pairs of functions from this list, arbitrarily designating one as f and one g. We then computed the signatures of f. g and f o g for each pair, divided the data into a training set 45,000 elements and test set of 5,000 elements, and trained small fully connected neural network to predict the signature of g from the other two signatures.
On the test set, this model had 87.5% accuracy, which is substantially better than chance. We inspected the predictions made on the test set and found interesting examples like the one in Listing 7 where the model has learned do something you might (cautiously) refer to as logical deduction on properties. This result is suggestive of the expressive power of property signatures. It also points toward exciting future directions for research into neurally guided program synthesis.
f: N:List<Int>> Litt>>>>>issInnt inputs {
consume_ (inputs, g: (ilastt(in>>>iisttiiln fo__ffodd_<IIn_ Int> (inputs, int_min, mod_)))
inputs {
1ist map___ap____ <Int, Int> (inputs, neg_) prop: \: (Iist<Int>, List<Int>)-sBeek (inputs, outputs) {
1ist for
(outputs, \x (in lin__istt__e <Int> (x, inputs) })
Listing 7: Example of successful prediction made by our composition predictor model. The property in question checks whether all the elements of the output list are members of the input list. For the value is AllTrue, and for of o g the value is Mixed. The model doesn't know g or its signature, but correctly predicts that the value of this property for g must be Mixed.
6 RELATED WORK
There substantial prior work on program synthesis in general. We can hardly do justice here, but see some Gottschlic al. (2018); Solar-Lezamal (2018); Gulwani et al. (2017): Allamanis et al. (2018) for more detailed surveys.
Property Based Testing: Function properties are similar to the properties from Property Based Testing, a software testing methodology popularized by the QuickCheck library (Claessen & Hughes 2011) that has now spread to many contexts (Gallant 2018 Holser 2018 Hypothesis] 2018 Luu 2015; Elhage 20177; Maclver (017).. Quickcheck properties are human -umann-peeiffid and operate on functions, while our properties operate input/output pairs.
8

---

Published as a conference paper at ICLR 2020
Automated Theorem Proving: Synthesizing programs using machine learning is related to the idea of proving theorems using machine learning (Irving et al. 2016). Synthesis and theorem proving are formally related as well (Howard 1980).
Program Synthesis from Programming Languages Perspective: Most existing work on syn- thesis approaches is from the perspective of programming language design. Our baseline synthesizer borrows many ideas from Feser et al. (201)). Polikarpova et al. (2016) use refinement types (Freeman 1994) (roughly, decidable version of dependent types see Pierce Benjamin (2002) to give program specifications, allowing the type-checker to discard many candidate programs. Property signatures can be thought of as a compromise between refinemett types and dependent types: we can write down specifications with them that would be impossible to express in refinement types, but we can only check those specifications empirically.
ML--Guided Program Synthesis: More recently, researchers have used machine learning syn- thesize and understand programs. We have mentioned [Bllo et al. 2016), but see all of: Nye et al. (2019; Ellis et al. (2018a): Zohar& & Wolf (2018): Kalyan al. (2018) 8 Ellis al. (2019a Liang et al. (2010) Alon et al. (2019) as well. Menon et al. (2013) intrdduces the idea of features: a predecessor to the idea of properties. Features differ from properties in that they are hand-crafted rather than
learned, and that they were applied only on limited string processing domain.
The relationship between this work and Balog et al. (2016) merits special discussion. Aside from the inclusion of property signatures, they differ in the following ways:
Deepcoder:
We use a more expressive DSL. Their DSL only allows linear control flow with a small set of functions, whereas our language is Turing complete (it has looping, recursion, etc). We also have larger set of allowed component functions: 86 vs. 34.
Their machine learning method does not work straightforwardly for arbitrary programs. Their training and test programs only deal with integers and lists of integers, while have 14 different function types. It would thus not be feasible to compare the techniques on anything but a tiny subset of our existing test set.
The cases in Balog al. (2016) are generated from their enumerative synthesizer. is therefore guaranteed that the synthesizer will be able to emit them in a reasonable amount of time during testing, so their demonstrated improvements are 'merely' speed-ups. Our test cases are human generated. and over half of the programs synthesized using property signatures were not synthesized at all given over day of time.
CONCLUSION AND FUTURE WORK
In this work, we have introduced the idea of properties and property signatures. We have shown that property signatures allow us to synthesize programs that baseline otherwise was not able to synthesize, and have sketched out other potential applications as well. Finally, we have open sourced all of our code, which we hope will accelerate future research into ML-guided program synthesis.
ACKNOWLEDGMENTS
We would like to thank Kensen Shi, David Bieber, and the rest of the Program Synthe- sis Team for helpful discussions. We would like thank Colin Raffel for reading a draft of the paper. Most of all, we owe a substantial debt to Niklas Een, on whose Evo pro- www.//tessof.iiiccccccoooooooooe wtt.a////eeeeaeaate/e/eeee/eeeee
gramming language hhttps: /nttps://githu.
deepnatth/zz/Cooereeeede the Searcho language is heavily based.
Of course, barring hugs in the synthesizer, they would be synthesized eventually.
9

---

Published as a conference paper at ICLR 2020
REFERENCES
Miltiadis Allamanis, Earl Barr, Christian Bird, and Charles Sutton. Learning natural coding conventions. In Symposium the Foundations of Software Engineering (FSE), 2014.
Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51 2018.
Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. code2vec: Learning distributed represen- tations of code. Proceedings of the ACM on Programming Languages, 3(POPL):40, 2019.
Rajeev Alur, Pavol Černý, and Arjun Radhakrishna. Synthesis through unification. In Daniel Kroening and Corina S. Pāsäreanu (eds.). Computer Aided Verification, pp. 163-179, Cham, 2015. Springer International Publishing. ISBN 978-3-319-216688 URL http::/t///// //ccee.///eee.eee colorado
@ed.ppavo//ubllee www.oliccciinnso.oo wwatetionnnccllaaa wwt.c//vaaaaaaeaee cawlaaaaalaa... pdf
J. W. Backus, R. J. Beeber, S. Best, R. Goldberg, L. M. Haibt, H. L. Herrick, R. A. Nelson, D. Sayre, P. B. Sheridan, H. Stern, I. Ziller, R. A. Hughes, and R. Nutt. The fortran automatic coding system. In Papers Presented at the February 26-28, 1957, Western Joins Computer Conference: Techniques for Reliability, IRE-AIEE-ACM 57 (Western), pp. 188-198, New York, NY, USA, 1957. ACM. doi: 10.1 T..1145/4455567 05551445556714555999 URL BtRl:ttp://deee acm. http:/10.11411445555555 17..565..11159 1455599
Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv: 1.01989, 2016.
Koen Claessen and John Hughes. Quickcheck: a lightweight tool for random testing of haskell programs. Acm sigplan notices, 46(4):53366 64, 2011.
B.J. Copeland. Alan Turing's 's Electronic Brain: The Struggle Build the ACE, the World's Fastest Computer. OUP Oxford, 2012. ISBN 9780199609154, htt.ltttts///bok.ccoo google. com/
Leonardo De Moura and Nikolaj Bjømer. Z3: An efficient smt solver. In International conference on Tools and Algorithums for the Construction and Analysis Systems, pp. 337-340. Springer, 2008.
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), volume 70 of Proceedings of Machine Learning Research, pp.
990-998, 2017. URL http://ppooeeoonoooooopoopp////p
mlr. wttpss//1//evvll111111
Nelson Elhage. Property-based testing is fuzzing, 2017. URL https://blog...... nelll.g.elllll.. www.ehaae.... com/
fuzzinng/
Kevin Ellis, Lucas Morales, Mathias Sablé-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. Learning libraries of subroutines for neurally-guides bayesian program induction. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. BisacBianchhi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 7805-7815. Curran Associates, Inc., 2018a.
Kevin Ellis, Lucas Morales, Mathias Saylé-Meyer, Armando Solar-Lezama, and Joshua Tenen- baum. Library learning for neurally-guided bayesian program induction. In NeurIPS, 2018b.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with repl. arXiv preprint 7Xiv:1906.04604 2019a.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a REPL.. In NewrIPS, 2019b.
John K Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. In ACM SIGPLAN Notices, volume 50, pp. 229-239, ACM, 2015.
Tim Freeman. Refinement types ml. Technical report, CARNEGIE--ELLOO UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE, 1994.
Andrew Gallant. Quickcheck for rust, 2018. URL https: www.coo.cccccoo Susht
cuickccckk
10

---

Published as a conference paper at ICLR 2020
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. In Proceedings of the 2nd ACM SIGPLAN International Workshop Machine Learning and Programming Languages, pp. 69-80. ACM, 2018.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '11 pp. 317-330, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0490.
0. doi:
URL http::/doo acm. acm org/10 1ttp:///11.11151116399999
1926423
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trendy in Programming Languages, 4(1-2):1-119, 2017.
Kihong Hco, Mukund Raghothaman, Xujie Si, and Mayur Naik. Continuously reasoning about pro- grams using differential bayesian inference. In Programming Language Design and Implementation (PLDI), 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Paul Holser. junit-quickcheck, 2018.
URL ht:p:///gtthab..oo/pholllsss
junit meritt-quicccheck.
William A Howard.
The formulae-as-typer notion of construction. To HB Curry: essays combinatory logic, lambda calculus and formalism, 14:479-490, 1980.
Hypothesis. hypothesis
Hypothesis, 2018.
URL
Geoffrey Irving, Christian Szegedy, Alexander A Alemi, Niklas Eén, François Chollet, and Josef Urban. Deepmath-deep sequence models for premise selection. In Advances in Neural Information Processing Systems, pp. 2235-2243, 2016.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv: OrXiv:/804.01) 186, 2018.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied handwritten zip code recognition. Neural computation, 1(4):541 5514,1151,111 1989.
Percy Liang, Michael I Jordan, and Dan Klein. Learning programs: A hierarchical bayesian approach. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 639 646, 2010.
Dan Luu. Afl quickcheck 2015. URL httaatts//aanlluu.co//eeetttttie
David R. Maclver. What is property based testing, 2017. URL
workss/
articles/whan wwattt/hhtt-te http://hatttissssseee pagpaai----ppppttt--aaa-tttteeee ott.eeaeaaaccaaat-ttpeeeeeeeeeea
Zohar Manna and Richard Waldinger. Knowledge and reasoning in program synthesis. Artificial intelligence, 6(2):175-208, 1975.
Zohar Manna and Richard J Waldinger. Toward automatic program synthesis. Communications of the ACM, 14(3)151 1971.
Aditya Menon, Omer Tamuz, Sumit Gulwani. Butler Lampson, and Adam Kalai. A machine learning framework for programming by example. In International Conference on Machine Learning, pp. 187-195, 2013.
11

---

Published as a conference paper at ICLR 2020
Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama, Learning to infer program sketches. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1861. PMLR, 2019. Utt.htttp://proceeeee ngs. ml wttpgg/........../sees.... wwwpps//w//////p hyt9////y119/ 9a html
Benjamin C Pierce and C Benjamin. Types and programming languages. 2002.
Amir Pnueli and Roni Rosner. On the synthesis of reactive module. In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 179-190, ACM, 1989.
Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. Program synthesis from polymorphic refinement types. In ACM SIGPLAN Notices, volume 51, pp. 522-538. ACM, 2016.
Shaw. Inferring lisp programs from examples.
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program synthesis. 2018.
Armando Solar-Lezama. Introduction to program synthesis. https://people..em .iit aatl//acola/SppttteeicCorrreee..
2018. Accessed: 2018-09-17.
Paul Vincent Spade and Claude Panaccio. William of ockham. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, spring 2019 edition, 2019.
Phillip D Summers. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):111-175, 1977.
R.J. Waldinger, R.C.T. Lee, and SRI International. PROW: Step Toward Automatic Program Writing. SRI International, 1969. URL https::/book: goog le. wwt.boows/s..coooooooocco......a
3BITSQAACAAJ
Chenglong Wang, Alvin Cheung, and Rastislav Bodik. Synthesizing highly expressive sql queries from input-output examples. In Proceedings of the 38th ACM SIGPLAN Conference on Programmingg Language Design and Implementation, PLDI 2017, pp. 452-466, New York, doi: 10. 10.1145/3062341. 33062365. URL
NY, USA, 2017. ACM. ISBN 978-1-4503-4498-8
http://dol. acm. org/10.
/0/1//33622111.06655555 3062365
Patrick H. Winston. Learning structural descriptions from examples. Technical report, Cambridge, MA, USA, 1970.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Dasa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2094-2103. Curran Associates, Inc., 2018
12

---

end Published as a conference paper at ICLR 2020
Data: A PBE spec and synthesizer configuration
Result: program satisfying the specification (hopefully!)
Queue. push(hole Tin Touth;
while Queue is not empry do
partial partial_ +- Gett.owestCostaaattaal (Queue)
HasHoles
then
ExpandOneHole (partial
else
IestAgainst$ppe
end
end
Figure 2: The top-down synthesizer that we use as baseline in this work. In loop until satisfying program is found or we run out of time, we pop the lowest-cost partial program from the queue of all partial programs, then fill in the holes in all ways allowed by the type system, pushing each new partial program back onto the queue. If there are no holes to fill, the program is complete, and we check it against the spec. The cost of partial program is the sum of the costs of its pool elements, plus lower bound on the cost of filling each of its typed holes, plus the sum of the costs of a few special operations such tuple construction and lambda abstraction.
A APPENDIX
A.1 FURTHER DETAILS ON THE BASELINE SYNTHESIZER
This section contains details on the baseline synthesizer that did not fit into the main text. Figure
2 gives more formal description of the basic synthesis algorithm. Listing g shows an example trajectory of partial program expansions.
$1 (Int, Int)-> (Int,> Int) (a2, a3) (?)
$2 \: (Int, Int) -> (Int, Int) (a2, a3) {??, ?)
$2 \: (Int, Int) (Int, Int) (a2, a3) {(a3, ?
$2 \: (Int, Int) (Int, Int) (a2, a3) [(a3, a
Listing 8: The trajectory the synthesizer took to generate the swap function, which just swaps the two elements of a tuple. Since it knows it needs to take a tuple ints as an argument and return tuple of ints, it starts with a hole of type (Int, Int) in line 1. It then converts that hole into tuple of holes, both of type Int in line 2, fills one the holes with a reference to one of the arguments in line 3, and fills in the final hole with reference the other argument in line 4. Note that this listing doesn't show all programs attempted, it just shows the sequence of partial programs that led to the final solution.
13


Reviews:
[{"review_id": "Skxqu-xjcH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "This paper proposed the concept of \"property signatures\" , which are learned to represent programs. The property signatures are essentially some key attributes that one may summarize from a given set of input-output pairs, which the target function has. Then a program can be generated by evaluating these property signatures vectors (which is simply a bag-of-word representation with only 0 or 1 as each element). Much discussions have been given to discuss why and how these properties may be useful and very little real experiments are conducted quantitatively compared with existing works. Although this paper is quite interesting, I think this paper is in its very early stage and there are a lot of serious concerns I have for using this approach to synthesize the real complex programs. \n\n1) First of all, the notion of property signatures are easy to understand and is very natural. Just like human beings, when we write a program, we first think about the possible attributes of this program may have given a set of input-output pairs for both correctness and completeness. However, this is also the hard part of this idea. Potentially it could have an exponential number of possible properties as the program goes more complex and complex. It will quickly become computationally intractable problem. \n\n2) When I read the middle of paper, I would eager to know how authors can effectively find a good set of properties of a target program from a given input-output pairs. However, when I eventually reached the Section 4, I was kindly disappointed since I did not see any effective and principle way to get them. All I saw are \"randomly sample and generate\". This may be Ok for a very simple program given a set of simple input-output pairs. But it is definitely not feasible for any complex function, not to mention project. I think this is the key for the proposed idea since how to construct a good set of property signatures is crucial to treat them as the inputs for any program synthesis task later. \n\n3) There are very little baselines to compare against even though authors listed \"substantial prior work on program synthesis\". I understand the existing works may have their limitation in both what they can do and how well they can do. But it is still important to compare with directly on the same set of benchmarks. Otherwise, it is hard to be convincing that this approach is indeed superior compared to existing ones.  ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJge9Qkx9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "I would like to be able to recommend accepting this paper, but I can't.  It describes two contributions to the community that could be valuable:\n\n1: searcho, a programming language designed for studying program synthesis via search over programs\n2: A method of automatically choosing interesting features for guided program search. \n\nThe paper does not give enough evidence to ascertain the value of either contribution.  There are now a large number of program synthesis works using ML, and a huge literature on program synthesis without ML.   While many of ML works use a DSL as the testbed, surely the authors' feature selection method can be applied in some of these DSLs, allowing comparisons with current art?   On the other hand, many of the ML methods don't require the DSL used in the works that introduce them.  Can searcho + your set of training and test programs distinguish between these methods, and establish a benchmark?  Are there some more realistic tasks/applications that searcho makes reasonable, not readily approached with previous DSLs used for testing these algorithms?   I think this paper could be valuable if it could demonstrate either in what ways the new feature selection algorithm is  an improvement over prior ML methods, or that searcho is valuable as a benchmark or for approaching interesting applications.\n\n\n######################################################################################\nedit after author response:  raising to 6, I think the deepcoder experiments are useful in contextualizing the contribution of the authors' feature selection method.   \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxYtKBlcr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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\nThe paper studies the problem of program synthesis from examples and it proposes the notion of property signature as a set of \"features\" describing the program that can be used to simplify the synthesis by combining together sub-programs with similar features.\n\n** Evaluation\nThe paper is outside my scope of research, so my review is an educated guess.\n\nThe use of properties to summarize some features about the program and the possibility to evaluate them directly from samples seems a very interesting idea. As the authors mentioned, this may help in creating useful features and useful architectures to simplify the learning task. The concept of property signatures is very well introduced and explained. The authors also provide an extensive comparison to related work. The empirical results seem promising in showing how property signatures make the synthesis much faster and better.\n\nThe downsides of the paper are:\n- While it is clear how to build property signatures, it is quite unclear to me how they simplify the generation of programs that combine smaller/simpler programs.\n- Sect 3.2 on how to learn useful properties is rather vague and it would need a much more detail explanation.\n- Although the authors release code for the paper, the description of the experiments seem rather shallow and it requires a much higher level of detail on how the learning process is set up and executed.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose improved techniques for program synthesis by introducing the idea of property signatures. Property signatures help capture the specifications of the program and the authors show that using such property signatures they can synthesise programs more efficiently.

I think it is an interesting work. Unfortunately, one of the reviewers has strong reservations about the work. However, after reading the reviewer's comments and the author's rebuttal to these comments I am convinced that the initial reservations of R1 have been adequately addressed. Similarly, the authors have done a great job of addressing the concerns of the other reviewers and have significantly updated their paper (including more experiments to address some of the concerns). Unfortunately R1 did not participate in subsequent discussions and it is not clear whether he/she read the rebuttal. Given the efforts put in by the authors to address different concerns of all the reviewers and considering the positive ratings given by the other two reviewers I recommend that this paper be accepted. 

Authors,
Please include all the modifications done during the rebuttal period in your final version. Also move the comparison with DeepCoder to the main body of the paper.
Decision: Accept (Poster)