Discriminator Based Corpus Generation for General Code Synthesis
Authors: Alexander Wild
Barry Porter
Venue:  (2020)
Keywords: Code Synthesis
Neural Code Synthesis

Abstract: Current work on neural code synthesis consists of increasingly sophisticated architectures being trained on highly simplified domain-specific languages, using uniform sampling across program space of those languages for training. By comparison, program space for a C-like language is vast, and extremely sparsely populated in terms of `useful' functionalities; this requires a far more intelligent approach to corpus generation for effective training. We use a genetic programming approach using an iteratively retrained discriminator to produce a population suitable as labelled training data for a neural code synthesis architecture. We demonstrate that use of a discriminator-based training corpus generator, trained using only unlabelled problem specifications in classic Programming-by-Example format, greatly improves network performance compared to current uniform sampling techniques.

Under review as a conference paper at ICLR 2020
DISCRIMINATOR BASED CORPUS GENERATION FOR GENERAL CODE SYNTHESIS
Anonymous authors Paper under double-blind review
ABSTRACT
Current work on neural code synthesis consists of increasingly sophisticated archi- tectures being trained on highly simplified domain-specitn languages, using uni- form sampling across program space of those languages for training. By compari- son, program space for C-like language is vast, and extremely sparsely populated in terms of 'useful" functionalities; this requires a far more intelligent approach to corpus generation for effective training. We use a genetic programming approach using iteratively retrained discriminator to produce population suitable as la- belled training data for a neural code synthesis architecture. We demonstrate that use of discriminator-bun based training corpus generator, trained using only unla- belled problem specifications classic Frogramming-by by-Example format, greatly improves network performance compared to current uniform sampling techniques.
INTRODUCTION
Automated code synthesis is increasingly being studied as way to lower the entry bar for non- experts to create computer software, and aid in generally taming the complexity of large-scale systems by allowing engineers to specify their intentions at higher level of abstraction. The ap- proach of neural code synthesis in particular has recently gained of attention, applying advances in neural networks to the problem of automated synthesis.
We specifically study the approach of programming by example, in which small set input-output examples are presented to the system to serve as guide to the desired functionality of a program. Based on an analysis of these examples the synthesis system returns a source-code program able to replicate that functionality. Recent research in this field demonstrates promising results, including DeepCoder Balog et al.) (017) and Zohar & Wolf (2018). However, research to date is limited to using domain-specific languages and often linear sequential programs without conditions loops.
We also take a neural- weweednettwoo--bee based approach to this problem in an attempt to gain petorrp inference across the training examples given to our system, potentially allowing the system to learn general aspects of programming to help synthesize new programs from unseen input/output exam- ples. Unlike existing recent work, however, we target a general-purpose low-level programming language for code synthesis with much larger search space of possible programs. This presents major challenge in generating training corpus for the neural network. Where related research has used uniform sampling methods through program search space (Sun et al. (2018) Chen et al. (2017), or even enumerative approaches (Balog et al. (2017)) such approaches are wholly inadequate over larger search volumes with sparse sampling producing very poor inference results.
To solve this training corpus generation problem we propose a novel discriminator- based system, in which new sub-corpora are iteratively created, continually measuring their functional properties against those of the problems it is attempting to solve. This process works by learning how similar the I/O mappings of generated programs are to I/O problems requested by users; by selecting pro- grams which result in increasingly similar I/O mappings we simultancously choose programs with similar underlying source code features, until are able solve I/O problems requested by users. We demonstrate that the resultant training corpus is greatly superior to a conventionally generated corpus via uniform sampling, when using more generalised programming language for synthesis.
We measure the performance of our approach by comparing against similar research on neural code synthesis which uses uniform enumerative sampling for training, demonstrating that

---

Under review as a conference paper at ICLR 2020
ietiimiinntoo-nffmmme corpus generation approach far exceeds uniform sampling, by factor of 2, in terms of find-rates. We also compare against a general baseline using genetic programming (GP); this baseline produces surprising result that GP has broader range of programs found, although its probability of resolving any given user-provided problem is worse.
Our approach offers an effective way generate training corpus for high-dimensional program search space, capable of finding a wide range of unseen useful programs based only on input/output examples, without any labelled training data. At high level our research also demonstrates that the structure of the training corpus provided to a neural network greatly affects its performance on general purpose code generation tasks, and we argue that it should therefore represent core focus of the code synthesis community's 's efforts alongside work on neural network and language structures.
In the remainder of this paper we firstly assess the literature in the field, focusing on neural code synthesis and specifically its corpus generation techniques. In Sec. 3 we then present the method- ology we use to build our system, based on both a synthesis network and a discriminator network for corpus generation. We then evaluate our approach in Sec. by comparing it against traditional training corpus generation approaches for neural code synthesis.
[code to reproduce our results will be made open-source should this paper be accepted, and this line will be changed the link to the repository]
2
BACKGROUND
Program synthesis has been studied for nearly as long as machine learning has been considered, having been proposed in 1950 by Alan Turing Turing 1950).
Three main subfields exist: logic-based solvers Feng et al. (0117; 2018): Feser et al. (2015a b); Solar-Lezama et al. (2006); stochastic-searreeeeee based Genetic Programming
(2100;; Har- aldsson & Woodward (2014); and neural network based approaches Kant 2018) While solvers are excellent for restricted domains, they have limited applicability in programs containing loops due to their reliance on predicate logic. Genetic programming has been used to good effect in specific do- mains, but lacks the cross-program inference power that neural networks offer. We hold neural code synthesis to be an interesting area of study following the results of DeepCoder (Balog et al. (2017), which suggests that neural network can identify higher level features of program outputs (sorted- ness, evenness, offset from zero mean...); combined with this is the opportunity of inference within the representational model of the neural network.
Within the subfield of neural synthesis, we focus on programming by example Gulwani & Jain (017), which takes set of inputs and outputs which demonstrate desired functionality.
One of the core works in this field is DeepCoder Balog et al. (2017). a system able to recognise sub- functions within larger program consisting of up to 5 of these sub-functions called sequentially. This was significantly improved in subsequent work Zohar & Wolf (2018). which used a novel partial program execution model with results fed back into the synthesis neural network, to enhance search speed and increase the length of programs that can be found up to 14. Both approaches operated in the same Domain Specific Language, which focused on arrays of integers. In terms of corpus generation, DeepCoder uses a simple enumerative strategy, as its DSL creates a small enough program space to list all possible programs, while Zohar & Wolf (2018) use random sampling.
Two other major domains exist in the field of neural code synthesis; In both of these, we see that synthetic training sets are predominantly generated by uniform sampling (Sun et al. (2018); Chen et al. (2017); Devlin et al. (2017)).
The first of these two domains (2017), as these have immediate and obvious usefulness to non-expert users. While these tasks can be handled by solvers, there are good applications for neural synthesis systems, such as RobustFill Devlin et al. (017), neurally-augmente solver systems Vijayakumar al. (2018).
functions Gulwani (201)) Raza & Gulwani
The second domain is deduction of the behavioural algorithm of an agent in an environment, with the examples being sequences of actions taken by the agent in grid environment. This has been studied both in terms of trained neural networks recognising behavioural patterns [Sun et al. (2018 et al. 2018) or in reinforcement leaming based approaches to program generation ChhoooCChheeeeee al. 2017)
2

---

Under review as a conference paper at ICLR 2020
Our work differs from these domains' use of random uniform sampling for training sets, well as from the unscalable enumerative strategy of DeepCoder, in that we introduce a strategy for gen- erating targeted training corpus without requirement for numan-provide labelled data, and investigate how this generation strategy significantly boosts inference performance.
Finally, the most similar work to own is Shin al. (2019). which investigate the effects of inputs to programs in terms of the produced I/O examples' effect on training success. This differs from our work in that they explore which inputs feed into sampled programs, while are presenting a new program sampling technique. This approach may well be complementary to our own if using as part of our training corpus generation pipeline.
3 METHODOLOGY
Our overall approach to code synthesis is to feed in set of ten input/output (I/O examples to neural network, and have the output layers of that neural network select the most likely operation for each line of code for a function of a given upper length limit (where the number of output layers equivalent to the maximum number of lines of code in the function, each neuron in an output layer is equivalent to selecting one particular operator for that line, and each line of code can be set to 'no-op"), ) The probabilistic nature neural network's output allows us to gain set of possible programs to search through up given search depth; this basic approach is similar in spirit to DeepCoder[Balog Balog et al. (2017) in that it is attempting to guess the probability of each 'feature' of a program except in case these features are relatively low-level instructions.
Neural networks for code synthesis are usually trained on a uniformly sampled set of programs from the total space of all possible programs; while this is viable for simple becomes intractable for more general purpose languages. With the aim of achieving code synthesis using a much more general programming language, our methodology focuses how training data can be effectively drawn from much larger search space without human input.
languages, it
Our approach to this uses novel hybrid solution inspired by genetic programming but using neural network as a fitness function. We term this neural network a discriminator, as it attempts to discriminate between the algorithms the genetic programming element is currently generating, and the likely features needed by requested I/O examples for suman-usefie functions.
3.1 LANGUAGE USED
We reuse the programming language used in Wild & Porter 2019). simplified C-like language, which can be compiled out to C or Java source code. The language features variable assignments, conditional operators, and loop operators. These allow complex flow-control operations, allowing us to study algorithms which go beyond linear concatenation of functions often used in the literature.
We enhance the problem complexity considered by Wild & Porter (2019) by removing the restric- tions on array length, instead implementing an operation which instantiates empty arrays of given length. We also implement operations to allow array length to be determined, and the ability for function to call itself, to allow recursive functions. Our methodology also avoids using any human- provided hints about the likely features of source code for problem solutions, instead relying only on set of I/O examples for unsolved problems.
The full set of language operators available and restrictions used is included as an appendix 6
3.2 HUMAN USEFUL CORPUS
Our human useful corpus is a set of I/O mappings for 40 unique functions, each of which takes one array input parameter (of any length) and one variable, and returns array of any length. The set of problems includes reversing arrays, appending arrays with new values, and summing the values an array (a full list is given in appendix 6.4). We assume that these I/O mappings have been requested by human users, but that none have yet been solved. We further assume that each function has been requested at least five times, with different I/O mappings for each. This gives total corpus of 200 I/O examples as guide to the kinds of input-to-outpe to-output transformations that are considered 'useful'. We stress that at no point is the system ever provided with any source code for these examples.
3

---

Under review as a conference paper at ICLR 2020
During early experimentation we found it beneficial to apply some conventions around these I/O examples, specifically for the first three examples in the set of ten for given problem. The first I/O example for any problem is such that the content of each input array cell is the index of that cell, starting from 0, and the input variable has a random value. The second I/O example has the same properties but the second array cell is randomised third I/O example for every problem is the same as the first example except that the input variable also randomised to the same range. The remaining seven I/O examples can be anything, and are randomly generated in our corpus.
new value between 8 and 8, inclusive. The
Our synthesis pipeline has the challenge of starting from this corpus of unsolved problems, specified by I/O examples, and solving as many of them as possible by synthesising the correct source code which correctly maps the given input to the given output for each problem.
3.3 NEURAL NETWORK ARCHITECTURE AND SEARCH PROCESS
Two neural network architectures are used in our synthesis pipeline, synthesiser and a discrimina- tor. The discriminator discussed later, and used in generating corpora on which the synthesiser is trained. The synthesiser network is that which receives I/O examples and attempts to build source code program to match the required functionality.
This neural network has an input layer which accepts both the input and output values of each pair of 10 examples for given problem, such that each input neuron takes a single bit of each integer. Internally use of set of layers of 256 neurons, each connected to all previous layers, with selu activation, a simplified version of the net used in Zohar & Wolf (2018). For output, we have one output layer per line of the program to synthesise. Each output layer has neuron for each way in which a line can be written (all valid operations), including no-op. A labelled program would be represented as array of one-hot vectors, with the non-zero value mapping the way that particular line should be written. We use crossentropy training loss on each line.
When reading a program out, the activities of all output layers' neurons taken and ranked, giving a confidence for each option for each line. We then search over the top 1,000,000 programs the network returns as 'most confident', using beam search technique (detailed in appendix
6.22). 6.2).
3.4 INITIAL SUB-CORPUS GENERATION
Our synthesiser neural network requires a training corpus comprised of the source code of example programs together with the I/O pairs for each program. Based on this training is then able solve some of the problems in our set of human useful I/O examples.
To generate this training corpus we use an iterative process of genetic programming and discrim- inator training to create a series of increasingly relevant corpora. At the start of this process, we generate an initial corpus of 1,000 functionally unique programs sampled at random from the total space of all possible programs (where we quantify a program unique if at least one output value is different from any other program when given the same five madomly-gennrateee input parameters).
Corpora other than this starting corpus are created by using a parent corpus from the set of accepted corpora (creation process detailed below). A child corpus is accepted it finds an implementation for human-usefuu IO mapping which was not found by an existing accepted lower-ancestry corpus, otherwise is discarded and cannot used as parent. A corpus' ancestry is the number of parent- child relationships it is removed from the initial corpus.
When creating a new child corpus, a parent corpus is selected by roulette selection from all currently accepted potential parents, with each potential parent's weighting being (0.1 + number of success furs children)/ + number- of children).
3.5 DISCRIMINATOR TRAINING AND USAGE IN SUB-CORPUS INHERITANCE
After the first corpus, further corpora are generated based the of our discriminator. This is a neural network designed to classify input/output pairs generated by programs in our generated corpus as being closer to further away from, those of I/O pairs in the human-usefin set from users.
A new corpus is created by selecting programs from a parent corpus which are measured to be most similar human-useful programs in their input/output mappings (specifically the form of
4

---

Under review as a conference paper at ICLR 2020
their outputs, and how these outputs seem to relate to corresponding inputs). By doing this, hypothesise that the kinds of source code features found in these programs will similarly move closer to those needed to synthesise programs solving the human- tuttunn-seuullll I/O examples.
Our discriminator neural network then works as follows. Architecturally, it consists of dense layers of 16 nodes, with single output. The featurisation of programs is identical to our synthesis neural network (as described above). We train this network by providing all of our I/O examples for all unfound human-useful target programs, and generate I/O examples for each of the 1,000 programs in the parent corpus. We train the discriminator network as a classifier to determine which of the 1O examples are from our human-useful set, and which are from the generated set. This training continues until a threshold T3 is reached. Tę is the proportion of programs which would be retained by the discriminator (as described below), run on the parent corpus. T3 is a randomly set value between 0.1 and 1, set 10.1 r²) where r is a random real value uniformly distributed between and We use random value here to increase the diversity in corpora formed, some being highly similar to the parent and some being fairly different, in bid to maximise coverage.
This trained discriminator therefore returns an estimate Fa for how luman-like a program is, ranging between O and 1. A program is said to pass the discriminator if it has estimate of Fa >> 0.1. This second threshold was chosen based on preliminary experiments, particularly based on analysis of the distribution of estimates, which was found to be highly biased towards either end of the spectrum.
These selected programs form the basis of a new child corpus. This child corpus is then expanded to have 1,000 functionally unique programs of its own, by using roulette wheel selection in which we take one of the existing programs in the corpus and mutate it, then accept or reject that mutated program as an additional member of the corpus based on a fitness function Fg. This value F, is simply how much it exceeded the discrimination threshold (.1)..1). During development, roulette selection was found to produce far superior results than tournament selection if the discriminator values are offset by 0.1, due to bias away from programs which only just passed the threshold.
We continue to create new child corpora in this way up to a desired total number. We emphasise that, during this process, we have no access to the human-useful programs, only the I/O examples that users have requested be generated. After multiple rounds of generating self-training data in the above fashion, to reach source code features that are increasingly likely to be involved in solving the requested I/O examples, we then begin to be able to successfully synthesise solutions to the I/O examples of programs requested by users.
3.6 EVALUATION OF OVERALL SYSTEM
Our synthesis pipeline returns a collection of solutions to I/O problems in the human useful set, and also returns set of generated training corpora which were used in finding these solutions. We keep all generated corpora, and their corresponding trained synthesiser networks, which we 'kept' in the above iterative process as either a parent or final child. Note that we keep the intermediate parents along the way because child corpus is sometimes unable solve some of the problems of its parent, even though it can solve new problems that its parent could not.
These trained neural networks then be re-used when given new I/O problems not present in the initial human useful set; each individual trained synthesiser network processes an 1/O problem in 0.25 seconds. We can also collate all corpora into single combined corpus which to train combined synthesiser neural network. We report the results of both alternatives (the set of individual experts and the combined expert) in the following section.
4 RESULTS
Our evaluation compares our approach to training corpus generation against competitive baselines. For all experiments we generate total of 200 sub-corpora using our approach, with each experiment repeated 20 times. The HU corpus was fixed for all experiments, and the I/O examples did not vary, including in baselines, allow consistent testing and repeatability. Noise between repeated experiments therefore derives only from the different systems' internal stochasticity.
To evaluate system compare it against two basclines: corpora, and one using genetic programming on the same problem
without using discriminator,
instead using set. We then compare our approach to one using uniformly-sampled training data, as is used in
5

---

Under review as a conference paper at ICLR 2020
Table 1: Find rates for our human-useful problem set by approach type. The set consists of 200 I/O examples, derived from 40 ground-truth programs
Approach
I/O examples solved
Unique functionalities found
Discriminated sub-corpora
81.5( 8.28)
20.3( 2.08)
Random sub-corpora
43.5(a 4.29)
11.8( = 1.20)
Genetic Programming
64.6(a 3.37)
22.5( 1.86)
related research for simpler domain-specific languages, and lastly we explore the the effects of decisions made by our discriminator in more detail.
4.1 PERFORMANCE COMPARED TO BASELINES
In this experiment we compare the find rates of programs against two baselines. For the first baseline use identical system that successive training corpora are generated only using randomly selected parents and mutations. The remainder of our pipeline is kept the same for this baseline.
but with the discriminator removed as fitness function, such
For our second baseline, we use genetic programming due to the inability to re-use baselines from other work in the literature, as for example seen in the DeepCoder framework, caused by the relative generality of our programming language for synthesis. Our genetic programming technique was designed to require roughly the same total computational time as the full sub-corpus generation pass, to fairly compare the options for user IO mapping resolution. It uses population size of 1,000, and maximum generation count 10,000. uses tournament selection, with a tournament size of 6 and probability of mutation of 0.15. The fitness function is function of the Euclidean distance between the desired output and the target output, unless the outputs differ in length, in which case it is set to extremely negative penalty value.
Our results are shown in Table I demonstrating that the set of networks produced by discriminated sub-corpus generation between them produced the highest resolution rate for the 200 human- 1/O mappings, returning an average of 81.5(a = 8.3).
Interestingly, the genetic programming technique found more unique functionalities. Of the 40 unique ground truth programs, the GP baseline found 22.7, while the sub-corpora found 20.3. This means that while the sub-corpus technique had higher probability of finding program match a user-supplied IO mapping, there existed stronger inequality between the find rates than the GP algorithm, which was more consistent in its probability of finding any given program.
It is highly likely that this is phenomenon produced by the nature of the discriminator itself, driving the system towards producing certain types of algorithms predominantly. seems likely that certain properties of certain programs would be more recognisable by neural network, and so emphasised by the discriminator's fitness function; this is a key avenue of future work.
4.2 COMPARISON WITH UNIFORMLY GENERATED TRAINING DATA
In this set of experiments evaluate the performance of our against a baseline randomly-generated training corpus. To do this we take a subset of 5 of the sub- corpora produced, attempting maximise the number of separate I/O examples found by the set of networks. The collated corpus then discards any duplicated functionalities, giving training corpus of approximately 4,200 examples. For each of these, we write out set of training examples, with randomly generated inputs into each function being used to generate the feature I/O examples. We then train the same synthesis neural network on these as before.
training corpus
For the comparative baseline training data we simply sample 5,000 programs uniformly random from the space of all possible programs, and again generate 5 training I/O examples using each of these programs. In both cases the corpora are then divided between training and validation in 0.9:0.1 split, with validation programs being functionally distinct from those in the training set; the training data is then fed into synthesis neural network and tested.
As can be seen in Table 2 the collated corpus produced by the discriminated sub-corpus generation process more than doubles the performance of the randomly generated training corpus. The discrim-

---

Under review as a conference paper at ICLR 2020
Table 2:
Approach
I/O examples solved
Unique functionalities found
Collated discriminated corpus Random corpus
4 7.5) 16.1 2.5)
11.3( =2)
3.85 = 0.59)
inator has driven program generation towards set of programs which is far more representative of the types of behaviour present within the human-useful programs.
Inspection the programs within the corpora matches this expectation: there no drive for randomly generated program to, say, contain loop, and if they do there is no drive towards writing all/most cells in the output array. While the behaviour of each training program is thus distinct, this is not necessarily in a 'useful' way, relative to the types of problems the user wishes to solve.
The discriminator, however, can drive towards useful training programs, by emphasising programs which write relatively uniformly to output arrays, using loops and with values remaining within sensible ranges; as well as generating programs with outputs dependent on the inputs, rather than fixed-output programs. Without ever receiving training labels information about the nature of useful features, the discriminator learns to maximise their presence in the sampled programs.
4.3 ANALYSIS OF EFFECTS OF ITERATED DISCRIMINATOR USE
In this section explore in more detail of effect of discriminator design. We first demonstrate the difference-over--iing from our first baseline in Sec. [.1 in which we generate successive corpora using either our discriminator or using simple random selection of parent. The results of this are shown in Figure in which we see how many programs from our target human useful set are solved over time as successive corpora are generated. As expected, both the discriminator setup and the random setup start at the same point, as the initial corpus does not use a discriminator. The first discriminated sub-corpus trains a network which finds an additional 6.7 solutions to I/O examples on average, compared to the non-discriminated corpus' increase of only 2.8. This progress continues as new sub-corpora are added, and is also seen on the graph unique functionalities found. This clearly demonstrates the value of the discriminator in corpus generation.
Unique Humana Useun-Usefull Useuul Programs Found
Human-Usar Useful Programs Found
27
80
24
70
21
50
15
12
30
20
50
100
150
200
50
100
150
200
Sub-Corous count
Sub-Corous count
Figure 1: Find rates of programs satisfying I0 specifications, over sub-corpus count, for both approach (blue, higher) and random baseline (red, lower). Find rates for all 200 I/O specifications on left, find rates for unique functionalities on right. First standard deviation shown.
We next examine the find rates over the 'ancestry' of sub-corpora in detail, to give indications as to the behaviour of the system in response to the discriminator's 's iterated use. Each sub-corpus past the first uses another as a parent; the ancestry of a sub-corpus is therefore the number of parents since the starting corpus. This varied by experiment, with all accepting corpus with ancestry of least 5, and the maximum being single run which had a sub-corpus of ancestry 12.
In Figure we plot the find rates of each program certain programs are trivial to find, and do not require discriminator use (Array Length; Array to Zero...). These have find rate of nearly 1.0 before the discriminator is used (black in first cell).
ancestry progression. We discover that

---

Abs
ShifteetZeroPPadee
ArrayL
ShitRight
MrrayTozerg
Cum aliveAbsoluteSum
ChuttieZeros Toack
Cumulativesum
Signum
DivergentSeguuene F firstelementnnly
Sort
SquareValues
dently
Tolterator
nndxP arlyy
Add
ierativeDifference
Append
KeepEvens
ClioMMax
KeepNegatives
ClipToMin
KeepOdds
ConstantAddition
KeepPosilives
FIlAAray
Negalive
GreaterThan
Pop
terateeromStart
RemlveeirssElement
LessThan
Reducee
MultiplesOf
Reverse
Multiply
ShifLeet
Subtract
Figure 2: Program find rates over sub-corpus ancestry. From white at O find rate, to fully black indicating 1.0 find rate. Border used indicate non-zero value. Plot cut off ancestry = 8 due to low sample size past this point. The way actual program outputs evolve detailed in appendix 6.3
Certain programs are found with high reliability past ancestry 1, for example the identity pro- gram. This program was almost never found without use of the discriminator, but single use lead to having a nearly 1.0 find rate. This indicates that the discriminator lead to set sub- corpora which represented the identity function's programmatic behaviour far better. We found that these sub-corpora's 's programs nearly universally featured loops and sequential array write opera- tions, functionalities required to produce the identity function.
The second use of the discriminator showed similar programs, such as Identity Parity and 'Iterate from Start'. These were rarely found in both non-diseriminated sub-corpus, sub-corpus, but featured regularly at later depths. This reflects the discriminator iterating on its previous selections, attempting to discriminate between programs produced by first-generation discriminator and the human useful corpus. These programs now found feature more complex loop- using behaviours than simple reproduction of the input array, such as using conditionals and literals.
ancestry
Past ancestry = 2, however, we no longer see sudden find-rate jumps. This indicates that the discriminator loses its effectiveness and can no longer guide as reliably towards the functionalities of the human-useful corpus. We speculate that the discriminator is unable to force the presence of the required functionalities in the produced training corpus either because the genetic algorithm doesn't I produce any for it to select; (ii) it does not have the capacity to represent the behaviours (due to low layer width or depth); (iii) these functionalities are simply not identifiable from I/O mappings alone. Further study of this is the subject of our future work.
5 CONCLUSION
This paper has presented discriminator corpus generation technique, which iteratively seeks to generate training programs drawn from the same distribution as the programs attempting to solve. It works without the need for labelled training data, generating its own based purely on supplied features of I/O examples and the underlying properties of the language itself. We show that it is greatly superior one which does not a discriminator for selecting training examples.
Once generation has completed, our framework can also return collated training corpus, allowing training of a single large neural network. We show that this collated network is also significantly stronger, in terms of quality of trained network, to one trained using random sampling techniques.
results, argue that the way in which training corpora generated for neural program synthesis deserves significant further study and may be of equal importance to the design of the neural network used for synthesis itself. In future work will further explore the ability of discriminnttr--tylle networks to identify specific features of code likely to be involved in solving a particular problem, as well more advanced architectures for synthesis and discriminator networks.
Based

---

REFERENCES
Matej Balog,
Alexander Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel
Tarlow.
Deepcoder: Learning to write programs. ICLR 2017. March 2017.
URL
cww/ en us wwweaacchpwblicaate...ceeeeeeeee
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis. ICLR 2018, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Towards Synthesizing Complex Programs from Input-
Output Examples. ICLR 2018, 2017.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, 990-998. JMLR.org, 2017. URL hRtL:tt:///aa acm. org aezg/ciiation wtw.eeemmmi.dd..m. 1one2idd-3338888 3305484
Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. Component-based synthesis of table consolidation and transformation tasks from examples. SIGPLAN Not., 52(6): 422 436, June 2017. ISSN 0362-1344 doi: 10.1145//14053370002551 URL http://dol.. acm. Cccm..2c.....11445444557870.0300
Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. Program synthesis using conffict-driven learning. SIGPLAN Nor., 53(4):420 435, June 2018. ISSN 0362-1340. doi: 10.1145/3296979. 3192382. http://:://dot
org. 1111/12999999 311999.1999999 92382
John K. Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. Proceedings of the 36th ACM SIGPLAN Conference on Pro-
gramming Language Design and Implementation PLDI 2015, pp- 229-239, 2015a. ISSN 15232867. doi: 10. 10.1445/2737992427737977 URLhttpp:/ //l:://ll.. aacm. www.moorggciaattto cfm?
do1d-2737924.27333 0717922..73777
John K. Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. SIGPLAN Not., 50(6):229-25) June 2015b. ISSN 0362-1340, doi: 1145/2811385.27379977 URL BRLL:ttp///dae acm. 10. 11111/111111112118888881 27377977777777777
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. ACM SIGPLAN Notices, 46(1):317, 2011. ISSN 03621340. doi: 10.1145/19258444196666
URL
http: acm. http://caaaa..ooccc.ooo.ooaaaa/.
1926423
Sumit Gulwani and Prateek Jain. Programming by examples: PL Meets ML. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lec- ture Notes in Bioinformatics), 10695 LNCS())3-20, 2017. ISSN 16113349. doi: 10.1007/
978-3-319-71237-6 1.
Saemundur O Haraldsson and John R Woodward. Automated Design of Algorithms and Genetic Improvement : Contrast and Commonalities. Proceedings of the 2014 Confer- ence Companion on Genetic and Evooluionary Computation Companion, pp. 1373-1380, 2014. doi: 02.11445/5983942269988 URL htttht/t://ll acm wttp//iaattioonnoo///.o 2609874 ID 2TT.://1111111T.TTTTTTTTE1111110 JCFTOKEN-51520157
Neel Kant, Recent Advances in Neural Program Synthesis. 2018. URL http://arxiv.orgg
abs/1802. 02353
John R. Koza. Human Human-coopetitivve results produced by genetic programming. Genetic Pro- gramming and Evolvable Machines, 11(3-4):251-288 2010. ISSN 13892576. doi: 10.1007/ s10710-010-9112-3
Mohammad Raza and Sumit Gulwani. Automated Data Extraction Using Predictive Program Syn- thesis. 28 AAAI Conference on Artificial Intelligence, pp. 882-890, 2017. doi: 105397.152 15232.

---

Richard Shin, Neel UC Kant Berkeley, Kavi Gupta, Christopher Bender, Brandon UC Trabucco Berkeley, and B Rishabh Singh Google Brain Dawn Song. Synthetic Datasets for Neural Program Synthesis. ICLR2019, pp. 1-16, 2019.
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combi- natorial sketching for finite programs. ACM SIGARCH Computer Architecture News, 34(5):404, 2006. ISSN 01635964. doi: 10. 10.1145/1169919.0 168907. 61889 URL httpttttpor..aaaee acm. org/
Shao Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph J. Lim. Supplementary material of neural program synthesis from diverse demonstration videos. 35th International Conference on Machine Learning, ICML 2018, 11:7624-7626 2018.
A. M. Turing. I.- Computing Machinery and Intelligence. Mind, LIX(236):433 460, 10 1950. ISSN 0026-4423. doi: 10. 10.103//inn//LXXX2564533 URL https:s//cc..orr//11....
mind/LIX. 236 433
Ashwin J. Vijayakumar, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-Guided Deductive Search for Real- Time Program Synthesis from Examples. 2018. ISSN 2176-4573.
doi: 10.150052116-4577200000000000000
URL http://arxiv.
org/abs 1804. 01186
Alexander Wild and Barry Porter. General Program Synthesis Using Guided Corpus Gen- eration and Automatic Refactoring. Springer International Publishing, 2019. ISBN
9783030274559, doi: 10.1007/978-3-000-24445 URthttp://xx wew.dciiooooooo wto./oo../0000000 978-3-030-27455-22
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In Proceedings of 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 2098-2107, USA, 2018. Curran Associates Inc. http:tt: //dl acc.
org/citation on cfm wtw. 3327133

---

APPENDICES
6.1 LANGUAGE IMPLEMENTATION DETAILS
Our programs are implemented as constrained version C. as in the work of Wild & Porter (0119). We, however, expand upon their work, increasing the limits on variable count, and introduc- ing the concepts of runtime-defined array lengths and recursive function calls. We limit the programs to length 14, the maximum number of integer variables to 7, the maximum number of array variables to (the one input and the one ultimately returned), the maximum array length under any condition and the maximum value ever to between -255 and 255 (inclusive).
The operators available are described in Table and represent a superset of the operators used in the work of Wild and Porter.
Table 3: The 16 operators available in implementation of language, with the inputs to the functions and their purpose
Operator
Input
Array: Write Target; Integer: Array Index; Integer: Read Target
Assign from Variable Array
Array: Read Target; Integer: Array Index; Integer: Write Target
Assign from Variable Array
Array: Array to initialise/overrrite;; Integer: Length of Ar- ray
Create Array
Get Array Length Variable to Literal
Array: Array to read length of; Integer: Write Target
Integer: Write Target; Literal: Can be -1, 0
Arithmetic Add Arithmetic Subtract
Integer: Write Target; Integer: Read I; Integer: Read 2
Integer: Write Target; Integer: Read I; Integer: Read 2
Arithmetic Multiply
Integer: Write Target; Integer: Read I; Integer: Read 2
Arithmetic Divide
Integer: Write Target; Integer: Read I; Integer: Read 2
Arithmetic Modulo
Integer: Write Target; Integer: Read I; Integer: Read 2
Assign Variable other Variable
Integer: Write Target; Integer: Read
Flow: Loop
Integer: Iterator; Integer: Loop to
Flow: Condition: Greater than
Integer: Variable to test
Flow: Condition: Integer equality
Integer: Variable to test 1; Integer: Variable to test
Array: Array to set to function return; Array: Input 1; Inte-
Recursive Function Call
ger: Input 2
No-Operation
No Inputs

---

6.2 BEAM SEARCH
Each line is given a "depth" to search, ranging from a single option to up to a maximum of 10 op- tions. The combination of all programs within this space are initially added to set, which therefore has a size equal to the product all the depths. The beam search constructs the initial search volume by iteratively increasing the search depth of single line to maximise the exploration value function. This function is as follows:
[do, d1, an. represents the ranked option confidences from the neural network, now sorted such that is the conffett- option. These are normalised by dividing by dg-
the search volume size, and S is the search volume size if line had its depth increased by one.
D; is the current depth of search of a given line minus one (for example if D, is O, only the first option will be added to the search volume, it the top two ranked options will be added the combinational set of programs (thus doubling the search space size)).
The exploration value for adding increasing the depth of any given line i is (0p )+0.75
This process attempts drive the neural network towards exploring lines in which multiple options are highly confident, and away from lines where single option has been given a high confidence and all others given a low or negative confidence.
Once the iterative addition has produced set of >= 1, 000, 000, the 1,000,000 options with the highest sum confidence are selected and searched exhaustively.
6.3 GENERATED PROGRAM EXAMPLES
In Table 4 outputs from 15 randomly generated programs, from 3 randomly chosen sub- corpora. The first is the starting corpus of the run, which had no discriminator. The second has discriminator trained between the human-useful IO examples and its parent corpus. The third sub-corpus then has a second generation discriminator, which was trained based on a discriminated corpus and the HU IO corpus.
All outputs are responses to the function being run with an input of input array = [0,1,2.3,4.556677 and input_integer=2.
We see that the programs in the starting corpus, ancestry=0,, which were randomly sampled from program space, differ greatly from the style of program we are attempting to train the network to synthesise. The majority of all returned values are O, and the array length varies considerably. There little evidence that the input array being read in, or indeed any use of loops all.
The second generation corpus, ancestry=l, shows little use of the input values, but has outputs in more consistent ranges. The output lengths now appear to always be the length of the input array, and the programs clearly use loops to write to the output array. Despite this, the output patterns are highly uniform, often being the same value repeated for most of the output array.
The third generation corpus, ancestry=2, shows more complex program still. Negative values, which would require arithmetic operations to produce, are present. The values vary across larger ranges, and they show elements of the input array (the last example being the input array changed by single element).
We believe this is fairly illustrative of the behaviour of the discriminator, although more in-depth analysis of the programs produced could form a good direction for future work.
6.4 CORPUS OF TARGET 'HUMAN USEFUL' FUNCTIONS
Functionally, all programs within this corpus receive both an array of length 2 to 16, with values ranging between -8 and 8, and an integer also ranging from -8 to 8, the same as in the rest of the paper. Some functions simply do not use the input variable, but this is accomplished solely by ignoring it. not by changing the function input parameter set.
The human useful programs and their functionalities are listed in table 5

---

Table 4: Examples of outputs of generated programs, randomly chosen from sub-corpora. These sub-corpora are organised based on ancestry, how many parent-child relationships exist between the first sub-corpus (ancestry=0).
Sub-corpus ancestry
Program Output
Ancestry=0
[0]
Ancestry=0
[0.0.0.000.000.00
Ancestry=0
[0,0,0,00088.0..000
Ancestry=0
[2]
Ancestry=0
(000000000000000000000000
Ancestry=l
[7.7,7.8.7.7.7777
Ancestry=1
[0.2.2.2,2.2.2.00
Ancestry=1
[7.888.8,8,888888
Ancestry=1
18.8.8,2.8.8.8888
Ancestry=l
(2,2,2,2,2,2.0.00)
Ancestry=2
[0.8166223322444488566
Ancestry=2
[11,7,66-5,43322-11
Ancestry=2
10.811622::324444885586
Ancestry=2
10,77-11-7.7177.777-11
Ancestry=2
[-2.112.3.4556.77]]

---

Table 5: Human useful programs, specified by user and presented to the system as set of IO mappings only.
Program
Function
Returns an array of equal size the input array, where all values are the absolute values in the input aray
Absolute Values
Returns I-length array, whose value is the length of the input array
Array Length
Returns an array of equal length to the imput array, filled with zeroes
Array to Zero
Returns an array of equal length to the input array, filled with the cumulative absolute values. That is to say cell oulpul; = Em=n linpu/,
Cumulative Absolute Sum
Returns an array of equal length to the input array, filled with the cumulative values. That is to say cell output; Σn=o imput,
Cumulative Sum
Returns an array of equal length to the imput array, filled
Divergent Sequence
with values such that if i is even output; i/2, otherwise output; = - (i/2), e.g. [0.0,1,-1,2,2...]
First Element Only
Returns array of length 1, whose content is inputy
Returns a new array with length and contents matching the input array
Identity
Returns a new array with length equal to that of the input array, filled with alternating Os and 1s, e.g. 10.1.
Index Parity
Returns a new array with length equal to that of the in- put array, filled with the difference between the mapped input array cell and the next, such that oulpud; = inpul, impulç-1, with oulputo impulo
Iterative Difference
Returns an array of equal length to that of the input array. If input, is even, output; input; else output, 0
Keep Evens
Returns an array of equal length to that of the input array. If inpul, O, oulpul, impul, else oulpul, 0
Keep Negatives
Returns an array of equal length to that of the input array. If input, is odd, output, input, else output,
Keep Odds
Returns an array of equal length to that of the input array. If input, O, output, imput, else output, 0
Keep Positives
Returns the input array multiplied by -1. oulpul, -input;
Negative
Returns an array one element shorter than the input. Values are the input array's values without the last.
Pop from Array
Returns an array half the length of the input array. Values in it the first values of the input array.
Reduce Length by Half

---

Table 6: Continuation of table
Program
Function
Returns a copy of the input array, but with the elements in reverse order
Reverse
Returns an array of length one less than the input array. Values are shifted, such that output; (i+1t The first input value is therefore not replicated in the output.
Shift Left
Returns an array of length equal the input array. Values are shifted, such that output; = input(;-1). The last value of the output array is set zero.
Shift Left Zero Padded
Returns array of length one greater than that of the input array. Values are the values in the input array preceded by a zero.
Shift Right
Returns an array of length equal to that of the input array. Values are such that outpul; inpul(s-1)- with the first output value being zero.
Shift Right Lossy
Returns array of length equal to that of the input array. Values are the the same elements as in the input array, with the exception that all zero-values moved to the end of the sequence.
Shuffle Zeros Back
Returns array of length equal to that of the input array. Values in output-1 -1, or 1. If imput, > then output, 1, if imput; < 0 then output; 1, else output, 0
Sign of
Sort
Returns a copy of the input array, sorted in ascending order.
Returns array of length equal to that of the input array. Values are such that outpul; = (inpull;)²
Square Values
Returns array of length equal that of the input array. Values are such that output, = i
To Iterator

---

Table Continuation of table and the input integer.
The programs in this table those which both the input array
Program
Function
Returns array of length equal to that of the input array. Values are such that oulpul; = impul; + impul Ileger
Add
Returns array of length greater than that of the input array. Values are those of the input array, followed by the input integer.
Append
Returns an array of length equal to that of the input ar- ray. Values such that if impul; > inputIntegen then oulpul, = impul, else oulpul, = inpul inpul/nles Illeger
Clip Max
Returns array of length equal to that of the input ray. Values are such that if input, < input then output, input, else output,
Clip to Min
Returns an array of length equal to that of the input array. Values are such that output, imput, (iwinput (ntger))
Constant Addition
Returns an array of length equal to that of the input array. Values are such that output; input/nteger
Fill Array
Returns an array of length equal to that of the input ar- ray. Values are such that if input, > inputInteger then output; = 1 else output, = -1
Greater Than
Returns an array of length equal that of the input array. Values are such that oulpul; = i + impul inpulInteger
Iterate from Start
Returns an array of length equal to that of the input ar- ray. Values are such that if input, < inputInneger then output, = else output, =
Less Than
Returns an array of length equal to that of the input array. Values are such that outpul; = i * InpulTnteger
Multiples of Subtract
Returns an array of length equal to that of the input array. Values are such that output, = input, -inputIntege


Reviews:
[{"review_id": "HyeJX6jkqB", "reviewer": "AnonReviewer3", "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": "# Summary\n\nThis paper describes an approach for generating synthetic training corpora for neural program synthesis systems. It\nassumes a test set of tasks to be solved, and designates a special \"discriminator\" network to force a distribution of\nI/O examples derived from randomly sampled programs to be as close as possible to the I/O examples supplied for the\ndesired programs. The system first randomly samples a set of programs, then retains only those that are \"sufficiently\nclose\" to the desired I/O examples, and mutates them to further refine this training corpus. The whole approach is\nevaluated on a DSL of array-manipulating programs, assuming 40 reasonable test programs and randomly sampled I/O pairs.\n\n# Strengths\n\nI like the core idea of the paper: assuming some desired distribution of I/O examples, construct the training corpus of\nrandom programs in such a way that its associated I/O examples approximate the desired distribution. I can see how it\ncould force the sampling process to discover useful program snippets for training. If evaluated properly, this work\nmight get accepted at a future conference.\n\n# Weaknesses\n\nI have some issues with the (a) evaluation, and (b) presentation of the work in its current state.\n\nFirst, the evaluation process fixes a set of 40 \"useful\" programs along with their associated I/O pairs, uses these I/O\npairs to build the training corpus as described, and then tests the finally trained synthesizer on the **same** set.\nWhile the test programs themselves are not are not used in corpus building, only their I/O pairs are, this is still\nsufficient to significantly bias the training set toward the test set. To properly test the core idea above, I'd expect\n_at least_ something like:\n- Write down or collect a set of \"useful\" test programs. Ideally make sure they all use different compositions of the\n  language operators but still cover the space of combinatorial operator combinations well.\n- Split this set into \"dev\" and \"test\" randomly. Use the I/O pairs from the \"dev\" set to build the training corpus.\n  Evaluate the final synthesizer on the test set.\n- Ideally also evaluate the sensitivity of this process to the chosen dev/test split.\n\nSecond, the evaluation baselines for corpus generation are straightforward: random sampling and genetic programming. The\nformer is self-evidently strawman. The latter is interesting, but is effectively a different implementation of the same\ncore idea of the paper, with two changes: (a) hardcoded fitness function instead of a trained discriminator, (b)\ntournament selection for population evolution instead of roulette.\nIn any case, neither of the baselines are truly independent strong alternatives. The authors remarked that they were\n\"unable re-use baselines from ... literature, as for example ... DeepCoder framework caused by the relative generality\nof our programming language for synthesis\", which is a confusing statement for two reasons:\n1. The programming language considered is a simple DSL of array manipulations, not that different in spirit from the\n   DeepCoder DSL, AlgoLisp [Polosukhin & Skidanov, 2018], or the list manipulations DSL of Ellis et al. [2018].\n2. Regardless of the DSL, what is being compared are **corpus generation techniques, not synthesis algorithms**.\n   DeepCoder is not a baseline for that, its corpus generation is not a contribution.\nThe most proper baseline would be the work of Shin et al. [2019], which the authors mention in Section 2. It was\nevaluated on Karel, which leaves the authors the choice of either (a) additionally evaluate their technique on the\nKarel DSL, or (b) adapt the method of Shin et al. by designing some salient variables for the DSL of this paper.\nI would prefer (a), which would significantly strengthen the paper, but (b) is also acceptable assuming honest effort\nin designing the salient variables to make the baseline strong.\n\nFinally, the presentation of the technical sections is informal and often confusing. Section 3 required several passes\nto understand the corpus generation process. The authors should introduce proper formalism for all the involved concepts\nsuch as corpora, train/test programs, their associated I/O pair, both neural networks with their input-output signatures\nand architecture, and so on. Most of these concepts have established mathematical notation in the literature which would\nmake Section 3 much easier to follow. In addition, Sections 3.3-3.5 need to be formalized in algorithmic pseudocode.\n\n# Minor remarks\n\n* Please use \\citet and \\citep appropriately: citations should be enclosed in parentheticals if they don't participate\n  in a sentence.\n* In your synthesizer network architecture, do you know the number of program output lines ahead of time?\n* In this DSL, how many possibilities are there in total for an output line (including all its arguments)?\n  Given the beam size of 1M (which is a lot!), I want to compare it with the total space (#possibilities × #lines).\n\n\n# References\n\nEllis, K., Morales, L., Sablé-Meyer, M., Solar-Lezama, A., & Tenenbaum, J. (2018). Learning libraries of subroutines for\nneurally–guided bayesian program induction. In Advances in Neural Information Processing Systems (pp. 7805-7815).\n\nPolosukhin, I., & Skidanov, A. (2018). Neural program search: Solving programming tasks from description and examples.\narXiv preprint arXiv:1802.04335.\n\nShin, R., Kant, N., Gupta, K., Bender, C., Trabucco, B., Singh, R., & Song, D. (2019). Synthetic Datasets for Neural\nProgram Synthesis. In ICLR.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkgax9PvKS", "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": "= Summary\nThe submitted paper describes a system for data augmentation and program synthesis given input-output examples. The system consists of (a) a discriminator able to recognise I/O examples that are likely to originate from programs humans are interested in, (b) a method to generate new example corpora using the generator from (a), and (c) a program synthesiser trained on the family of corpora generated in (b).\n\n= Strong/Weak Points\n+ The idea of interpreting the \"human-likeness\" of program behaviors is interesting, and could help substantially with augmenting the traditionally small clean datasets in program synthesis. It's substantially different from the competing idea of using a language model to generate \"natural programs\" from which examples are then extracted.\n- Many important technical details are not discussed in the paper (Sect. 3.5: how are programs mutated?; Sect. 3.6: how are the predictions of networks trained on different corpora combined?)\n- The writing is confusing in many places (see my pre-review clarification questions)\n- The experiments leave important questions uncovered:\n   (i) does the corpus-generation procedure bias the synthesizer towards human-like programs, or towards programs from the initial program corpus? This could be tested by holding out some of the programs from the initial set, and testing on these?\n   (ii) random generation of programs is much cheaper than the presented strategy, but Sect. 4.2 compares based on the number of examples. How long does generating the 5 subcorpora used to generate the \"collated discriminated corpus\" take? How many random examples can you generate in that time? How does a system trained on that larger set perform?\n\n= Recommendation\nIn its current state, I believe that the paper is lacking the technical precision and experiments to be useful to other researchers, and hence recommend rejecting it.\n\n= Minor Comments\n- Please use \\citet/\\citep to make sentences with citations more readable.\n- Please distinguish human-useful \"program behavior\" and \"program\"", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A"}, "extra_text": {}}, {"review_id": "B1lGk2hsFB", "reviewer": "AnonReviewer2", "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 presents a technique based on genetic programming to generate a suitable training corpus of programs and I/O examples using a trained discriminator network. Given a set of human useful programs and the corresponding I/O examples, the main idea of the approach is to use genetic programming to iteratively construct new corpus leveraged by a discriminator that aims to make the I/O examples of the corpus closer to the I/O examples of the human-useful set. This approach is evaluated on 40 human useful corpus of array programs and it is able to synthesize more programs than random corpus or genetic programming based baselines.\n\nOverall, this paper presents an interesting idea of automatically generating corpus for training neural program synthesis architectures, where most previous techniques sample synthetic programs uniformly from the space of DSL programs. (Shin et al. 2019) also point out a similar issue in neural program synthesis approaches, but this paper presents an automated technique to construct a better training corpus of synthetic programs and the corresponding I/O examples. I like the idea and the overall direction, but the current paper looks a bit preliminary both in evaluation as well as presentation.\n\nFirst, the description of the overall method is too high-level. It would be better to formalize exactly the network architectures for both synthesis as well as the discriminator networks. Having precise inputs to the networks as well as equations would help with the description. The description of the genetic programming framework to generate child corpus from parent corpus also seems a bit high-level.\n\nIt wasn’t clear what are the inputs to the discriminator network (in Section 3.5). Does it only take a single I/O example as input or a pair of I/O examples? Does it also take the current corpus program as input? How is the discriminator network used to select programs for the child corpus?\n\nI was trying to better understand the context in which such a dataset generation might be useful. It seems for such a technique, one has to come up with a dataset of human useful corpus of tasks. Doesn’t it mean that one has to possibly identify all possible programs that a user might want to synthesize upfront? It would be interesting to evaluate how well the technique works when synthesizing for programs that are also interesting to users but not provided as a part of the human useful corpus.\n\nIt was surprising to see genetic programming baseline solving more unique programs in the test set. Is it the case that with the discriminator based corpora, the approach is overfitting to one class of problems and not on others? Evaluating the technique on unseen programs not in the human useful set might help better evaluate this point as well.\n\nFor the comparison in 4.2 with uniformly generated data, only 5000 programs were used for training, unlike typical approaches that train on millions of synthetic programs. Why not train the network on larger amount of programs?\n\nIt was also interesting to see that the identity program was difficult to synthesize. Wouldn’t enumeration based approaches first start with that identity program? From the description it was also not clear how big the total search space for programs was in the language. Why wouldn’t enumeration based approaches work here? Also, it would be good to better understand why Sketch (Solar-Lezama 2008) based symbolic approaches won’t be able to synthesize these programs.\n\nIt would also help to provide some examples of synthesized programs and their I/O examples, and maybe also the child corpus that lead to successfully synthesizing them.\n\nThe paper mentions that DeepCoder based baseline isn’t applicable in this setting because of the generality of the language. Is the search space too large? Alternatively, can the presented technique be applied to DeepCoder to train on a generated corpus to improve its performance? Karel (Shin et al. 2019) might be another domain used in previous literature to show the usefulness of such an approach.\n\nOn page 4, the paper mentions that the first 3 examples were provided with a specific form.  Is there any intuition why such examples are useful and whether such constraints are used for all newly generated corpus as well? What happens when only random I/O examples are used?\n\nMinor:\n\nReferences are not formatted correctly in the paper.\npage 4: value between 8 and 8\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": {}}]

Author rebuttal:

Meta-review: This paper proposes a method to automatically generate corpora for training program synthesis systems.

The reviewers did seem to appreciate the core idea of the paper, but pointed out a number of problems with experimental design that preclude the publication of the paper at this time. The reviewers gave a number of good comments, so I hope that the authors can improve the paper for publication at a different venue in the future.
Decision: Reject