Title: 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 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.

1. INTRODUCTION:

Automated code synthesis is increasingly being studied as a way to lower the entry bar for nonexperts to create computer software, and to aid in generally taming the complexity of large-scale systems by allowing engineers to specify their intentions at a higher level of abstraction. The approach of neural code synthesis in particular has recently gained a lot of attention, applying advances in neural networks to the problem of automated synthesis.

We specifically study the approach of programming by example, in which a small set of input-output examples are presented to the system to serve as a 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. (2017) and Zohar & Wolf (2018) . However, research to date is limited to using domain-specific languages and often linear sequential programs without conditions or loops.

We also take a neural-network-based approach to this problem in an attempt to gain inter-program 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 examples. Unlike existing recent work, however, we target a general-purpose low-level programming language for code synthesis with a much larger search space of possible programs. This presents a major challenge in generating a 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 programs which result in increasingly similar I/O mappings we simultaneously choose programs with similar underlying source code features, until we are able to 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 a 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 or enumerative sampling for training, demonstrating that our discriminator-informed corpus generation approach far exceeds uniform sampling, by a factor of 2, in terms of find-rates. We also compare against a general baseline using genetic programming (GP); this baseline produces a surprising result that GP has a broader range of programs found, although its probability of resolving any given user-provided problem is worse.

Our approach offers an effective way to generate a training corpus for a 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 a 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 a core focus of the code synthesis community'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 methodology 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. 4 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 to 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. (2017; 2018); Feser et al. (2015a; b) ; Solar-Lezama et al. (2006) ; stochastic-search-based Genetic Programming (GP) Koza (2010) ; Haraldsson & 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 domains, 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 (sortedness, evenness, offset from zero mean...); combined with this is the opportunity of inter-program inference within the representational model of the neural network.

Within the subfield of neural synthesis, we focus on programming by example Gulwani & Jain (2017) , which takes a set of inputs and outputs which demonstrate a desired functionality.

One of the core works in this field is DeepCoder Balog et al. (2017) , a system able to recognise subfunctions within a 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) The first of these two domains is string-manipulation functions Gulwani (2011) ; Raza & Gulwani (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. (2017) , or neurally-augmented solver systems Vijayakumar et al. (2018) .

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 a grid environment. This has been studied both in terms of trained neural networks recognising behavioural patterns Sun et al. ( 2018) Bunel et al. (2018) or in reinforcement learning based approaches to program generation Chen et al. (2017) .

Our work differs from these domains' use of random uniform sampling for training sets, as well as from the unscalable enumerative strategy of DeepCoder, in that we introduce a strategy for generating a targeted training corpus without requirement for human-provided labelled data, and we investigate how this generation strategy significantly boosts inference performance.

Finally, the most similar work to our own is Shin et 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 to feed into sampled programs, while we 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 a set of ten input/output (I/O) examples to a 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 is 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 of a neural network's output allows us to gain a set of possible programs to search through up to a given search depth; this basic approach is similar in spirit to DeepCoder Balog et al. (2017) in that it is attempting to guess the probability of each 'feature' of a program -except in our 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 domain-specific languages, it becomes intractable for more general purpose languages. With the aim of achieving code synthesis using a much more general programming language, our methodology focuses on how training data can be effectively drawn from a much larger search space without human input.

Our approach to this uses a novel hybrid solution inspired by genetic programming but using a 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 human-useful functions.

3.1. LANGUAGE USED:

We reuse the programming language used in Wild & Porter (2019) , a 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 restrictions 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 a function to call itself, to allow recursive functions. Our methodology also avoids using any humanprovided hints about the likely features of source code for problem solutions, instead relying only on a set of I/O examples for unsolved problems.

The full set of language operators available and restrictions used is included as an appendix 6.1.

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 an array of any length. The set of problems includes reversing arrays, appending arrays with new values, and summing the values in 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 a total corpus of 200 I/O examples as a guide to the kinds of input-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.

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 a 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 to a new value between 8 and 8, inclusive. The third I/O example for every problem is the same as the first example except that the input variable is also randomised to the same range. The remaining seven I/O examples can be anything, and are randomly generated in our corpus.

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, a synthesiser and a discriminator. The discriminator is discussed later, and is used in generating corpora on which the synthesiser is trained. The synthesiser network is that which receives I/O examples and attempts to build a 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 a given problem, such that each input neuron takes a single bit of each integer. Internally we use of a set of 8 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 one neuron for each way in which a line can be written (all valid operations), including no-op. A labelled program would be represented as an array of one-hot vectors, with the non-zero value mapping to 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 are 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 a beam search technique (detailed in appendix 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 it is then able to 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 discriminator 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 as unique if at least one output value is different from any other program when given the same five randomly-generated 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 if it finds an implementation for a human-useful IO mapping which was not found by an existing accepted lower-ancestry corpus, otherwise it is discarded and cannot be used as a parent. A corpus' ancestry is the number of parentchild 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 successf ul children)/(0.1 + number of children).

3.5. DISCRIMINATOR TRAINING AND USAGE IN SUB-CORPUS INHERITANCE:

After the first corpus, further corpora are generated based on the use 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-useful set from users.

A new corpus is created by selecting programs from a parent corpus which are measured to be most similar to human-useful programs in their input/output mappings (specifically the form of their outputs, and how these outputs seem to relate to corresponding inputs). By doing this, we 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-useful I/O examples.

Our discriminator neural network then works as follows. Architecturally, it consists of 2 dense layers of 16 nodes, with a 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 I/O examples are from our human-useful set, and which are from the generated set. This training continues until a threshold T k is reached. T k is the proportion of programs which would be retained by the discriminator (as described below), if run on the parent corpus. T k is a randomly set value between 0.1 and 1, set as max(0.1, r 2 ) where r is a random real value uniformly distributed between 0 and 1. We use a random value here to increase the diversity in corpora formed, some being highly similar to the parent and some being fairly different, in a bid to maximise coverage. This trained discriminator therefore returns an estimate F d for how human-like a program is, ranging between 0 and 1. A program is said to pass the discriminator if it has an estimate of F d > 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 F q . This value F q is simply how much it exceeded the discrimination threshold (F d -0.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 a 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 a child corpus is sometimes unable to solve some of the problems of its parent, even though it can solve new problems that its parent could not.

These trained neural networks can 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 I/O problem in ∼ 0.25 seconds. We can also collate all corpora into a single combined corpus on which to train a 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 a 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, to allow consistent testing and repeatability. Noise between repeated experiments therefore derives only from the different systems' internal stochasticity.

To evaluate our system we compare it against two baselines: one without using our discriminator, instead using randomly-generated corpora, and one using genetic programming on the same problem set. We then compare our approach to one using uniformly-sampled training data, as is used in 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 we use an identical system to our own but with the discriminator removed as a fitness function, such 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.

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 a population size of 1,000, and a maximum generation count of 10,000. It uses tournament selection, with a tournament size of 6 and a probability of mutation of 0.15. The fitness function is a 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 an extremely negative penalty value.

Our results are shown in Table 1 , demonstrating that the set of networks produced by discriminated sub-corpus generation between them produced the highest resolution rate for the 200 human-useful I/O mappings, returning an average of 81.5(σ = 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 a higher probability of finding a program to match a user-supplied IO mapping, there existed a 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 a phenomenon produced by the nature of the discriminator itself, driving the system towards producing certain types of algorithms predominantly. It seems likely that certain properties of certain programs would be more recognisable by a neural network, and so emphasised by the discriminator's fitness function; this is a key avenue of future work. We then train the same synthesis neural network on these as before.

For the comparative baseline training data we simply sample 5,000 programs uniformly at 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 a 0.9:0.1 split, with validation programs being functionally distinct from those in the training set; the training data is then fed into our 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- inator has driven program generation towards a set of programs which is far more representative of the types of behaviour present within the human-useful programs.

Inspection of the programs within the corpora matches this expectation: there is no drive for a randomly generated program to, say, contain a loop, and if they do there is no drive towards writing to 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 or 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 we explore in more detail of effect of our discriminator design. We first demonstrate the difference-over-time from our first baseline in Sec. 4.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 1 , 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 of unique functionalities found. This clearly demonstrates the value of the discriminator in corpus generation. Unique Human-Useful Programs Found Figure 1 : Find rates of programs satisfying IO specifications, over sub-corpus count, for both our 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 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 a corpus with ancestry of at least 5, and the maximum being a single run which had a sub-corpus of ancestry 12.

In Figure 2 we plot the find rates of each program over ancestry progression. We discover that certain programs are trivial to find, and do not require discriminator use (Array Length; Array to Zero...). These have a find rate of nearly 1.0 before the discriminator is used (black in first cell). Certain programs are found with high reliability past ancestry of 1, for example the identity program. This program was almost never found without use of the discriminator, but a single use lead to it having a nearly 1.0 find rate. This indicates that the discriminator lead to a set of subcorpora which represented the identity function's programmatic behaviour far better. We found that these sub-corpora's programs nearly universally featured loops and sequential array write operations, 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 a non-discriminated sub-corpus, or an ancestry = 1 sub-corpus, but featured regularly at later depths. This reflects the discriminator iterating on its previous selections, attempting to discriminate between programs produced by a first-generation discriminator and the human useful corpus. These programs now found feature more complex loopusing behaviours than simple reproduction of the input array, such as using conditionals and literals.

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 (i) the genetic algorithm doesn't 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 a discriminator-based corpus generation technique, which iteratively seeks to generate training programs drawn from the same distribution as the programs it is 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 to one which does not use a discriminator for selecting training examples.

Once generation has completed, our framework can also return a 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.

Based on our results, we argue that the way in which training corpora are 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 we will further explore the ability of discriminator-style networks to identify specific features of code likely to be involved in solving a particular problem, as well as more advanced architectures for synthesis and discriminator networks.

6.1. LANGUAGE IMPLEMENTATION DETAILS:

Our programs are implemented as a constrained version of C, as in the work of Wild & Porter (2019) . We, however, expand upon their work, increasing the limits on variable count, and introducing 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 2 (the one input and the one ultimately returned), the maximum array length under any condition to 16 and the maximum value ever to between -255 and 255 (inclusive).

The operators available are described in Table 3 , 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

:



Figures and Tables:

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)).

COMPARISON WITH UNIFORMLY GENERATED TRAINING DATA In this set of experiments we evaluate the performance of our iteratively-produced training corpus against a baseline randomly-generated training corpus. To do this we take a subset of 5 of the subcorpora produced, attempting to maximise the number of separate I/O examples found by the set of networks. The collated corpus then discards any duplicated functionalities, giving a training corpus of approximately 4,200 examples. For each of these, we write out a set of training examples, with 5 randomly generated inputs into each function being used to generate the feature I/O examples.

Figure 2: Program find rates over sub-corpus ancestry. From white at 0 find rate, to fully black indicating 1.0 find rate. Border used to indicate a non-zero value. Plot cut off at ancestry = 8 due to low sample size past this point. The way actual program outputs evolve is detailed in appendix 6.3.

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

Table content: <table><tr><td>Approach</td><td colspan="2">I/O examples solved Unique functionalities found</td></tr><tr><td colspan="2">Discriminated sub-corpora 81.5(σ = 8.28)</td><td>20.3(σ = 2.08)</td></tr><tr><td>Random sub-corpora</td><td>43.5(σ = 4.29)</td><td>11.8(σ = 1.20)</td></tr><tr><td>Genetic Programming</td><td>64.6(σ = 3.37)</td><td>22.5(σ = 1.86)</td></tr></table>

Approach I/O examples solved Unique functionalities found

Table content: <table><tr><td colspan="2">Collated discriminated corpus 44.5(σ = 7.5)</td><td>11.3(σ = 2)</td></tr><tr><td>Random corpus</td><td>16.1(σ = 2.5)</td><td>3.85(σ = 0.59)</td></tr></table>

Peer review (iclr2020):
# Summary This paper describes an approach for generating synthetic training corpora for neural program synthesis systems. It assumes a test set of tasks to be solved, and designates a special *discriminator* network to force a distribution of I/O examples derived from randomly sampled programs to be as close as possible to the I/O examples supplied for the desired programs. The system first randomly samples a set of programs, then retains only those that are *sufficiently close* to the desired I/O examples, and mutates them to further refine this training corpus. The whole approach is evaluated on a DSL of array-manipulating programs, assuming 40 reasonable test programs and randomly sampled I/O pairs. # Strengths I like the core idea of the paper: assuming some desired distribution of I/O examples, construct the training corpus of random programs in such a way that its associated I/O examples approximate the desired distribution. I can see how it could force the sampling process to discover useful program snippets for training. If evaluated properly, this work might get accepted at a future conference. # Weaknesses I have some issues with the (a) evaluation, and (b) presentation of the work in its current state. First, the evaluation process fixes a set of 40 *useful* programs along with their associated I/O pairs, uses these I/O pairs to build the training corpus as described, and then tests the finally trained synthesizer on the **same** set. While the test programs themselves are not are not used in corpus building, only their I/O pairs are, this is still sufficient to significantly bias the training set toward the test set. To properly test the core idea above, I*d expect _at least_ something like: - Write down or collect a set of *useful* test programs. Ideally make sure they all use different compositions of the language operators but still cover the space of combinatorial operator combinations well. - Split this set into *dev* and *test* randomly. Use the I/O pairs from the *dev* set to build the training corpus. Evaluate the final synthesizer on the test set. - Ideally also evaluate the sensitivity of this process to the chosen dev/test split. Second, the evaluation baselines for corpus generation are straightforward: random sampling and genetic programming. The former is self-evidently strawman. The latter is interesting, but is effectively a different implementation of the same core idea of the paper, with two changes: (a) hardcoded fitness function instead of a trained discriminator, (b) tournament selection for population evolution instead of roulette. In any case, neither of the baselines are truly independent strong alternatives. The authors remarked that they were *unable re-use baselines from ... literature, as for example ... DeepCoder framework caused by the relative generality of our programming language for synthesis*, which is a confusing statement for two reasons: 1. The programming language considered is a simple DSL of array manipulations, not that different in spirit from the DeepCoder DSL, AlgoLisp [Polosukhin & Skidanov, 2018], or the list manipulations DSL of Ellis et al. [2018]. 2. Regardless of the DSL, what is being compared are **corpus generation techniques, not synthesis algorithms**. DeepCoder is not a baseline for that, its corpus generation is not a contribution. The most proper baseline would be the work of Shin et al. [2019], which the authors mention in Section 2. It was evaluated on Karel, which leaves the authors the choice of either (a) additionally evaluate their technique on the Karel DSL, or (b) adapt the method of Shin et al. by designing some salient variables for the DSL of this paper. I would prefer (a), which would significantly strengthen the paper, but (b) is also acceptable assuming honest effort in designing the salient variables to make the baseline strong. Finally, the presentation of the technical sections is informal and often confusing. Section 3 required several passes to understand the corpus generation process. The authors should introduce proper formalism for all the involved concepts such as corpora, train/test programs, their associated I/O pair, both neural networks with their input-output signatures and architecture, and so on. Most of these concepts have established mathematical notation in the literature which would make Section 3 much easier to follow. In addition, Sections 3.3-3.5 need to be formalized in algorithmic pseudocode. # Minor remarks * Please use citet and citep appropriately: citations should be enclosed in parentheticals if they don*t participate in a sentence. * In your synthesizer network architecture, do you know the number of program output lines ahead of time? * In this DSL, how many possibilities are there in total for an output line (including all its arguments)? Given the beam size of 1M (which is a lot!), I want to compare it with the total space (#possibilities × #lines). # References Ellis, K., Morales, L., Sablé-Meyer, M., Solar-Lezama, A., & Tenenbaum, J. (2018). Learning libraries of subroutines for neurally–guided bayesian program induction. In Advances in Neural Information Processing Systems (pp. 7805-7815). Polosukhin, I., & Skidanov, A. (2018). Neural program search: Solving programming tasks from description and examples. arXiv preprint arXiv:1802.04335. Shin, R., Kant, N., Gupta, K., Bender, C., Trabucco, B., Singh, R., & Song, D. (2019). Synthetic Datasets for Neural Program Synthesis. In ICLR.