Neurally Guided Genetic Programming for Turing Complete Programming by Example
Authors: Alexander Newton Wild
Barry Porter
Venue:  (2021)
Keywords: Code Synthesis
Neural Code Synthesis
Genetic Programming
Programming By Example

Abstract: The ability to synthesise source code from input/output examples allows nonexperts to generate programs, and experts to abstract away a wide range of simple programming tasks. Current research in this area has explored neural synthesis, SMT solvers, and genetic programming; each of these approaches is limited, however, often using highly specialised target languages for synthesis. In this paper we present a novel hybrid approach using neural networks to guide genetic programming (GP), which allows us to successfully synthesise code from just ten I/O examples in a generalised Turing complete target language, up to and including a sorting algorithm. We show that GP by itself is able to synthesise a set of simple programs, and show which hints (suggested lines of code for inclusion) are of most utility to GP in solving harder problems. Using a form of unstructured curriculum learning, we then demonstrate that neural networks can be used to determine when to make use of these high-utility hints for specific I/O problems and thus enable complex functions to be successfully synthesised. We apply our approach to two different problem sets: common array-to-array programs (including sorting), and a canvas drawing problem set inspired by So & Oh (2018).

Under review as a conference paper at ICLR 2021
NEURALLY GUIDED GENETIC PROGRAMMING FOR TURING COMPLETE PROGRAMMING BY EXAMPLE
Anonymous authors Paper under double-blind review
ABSTRACT
The ability to synthesise source code from input/output examples allows non- experts to generate programs, and experts abstract away wide range of simple programming tasks. Current research in this area has explored neural synthesis, SMT solvers, and genetic programming: each of these approaches is limited, how- ever, often using highly specialised target languages for synthesis. In this paper we present a novel hybrid approach using neural networks to guide genetic pro- gramming (GP), which allows us successfully synthesise code from just ten I/O examples in a generalised Turing complete target language, up to and including a sorting algorithm. We show that GP by itself is able to synthesise set of simple programs, and show which hints (suggested lines of code for inclusion) are of most utility to GP in solving harder problems. Using a form of unstructured curriculum learning, we then demonstrate that neural networks can be used to determine when to make use of these high-utility hints for specific I/O problems and thus enable complex functions to be successfully synthesised. We apply our approach to two different problem sets: common array-to- arraytt--array programs (including sorting), and canvas drawing problem set inspired by [o & Oh (2018).
INTRODUCTION
The ability to synthesise source code from examples, in which a source code implementation of function is created based on one or more demonstrations input-output mapping. is fundamental question in machine learning. We specifically study this question in the form of scenarios where large corpora of existing code are not available (e.g., numan-writted programs in open-source repos- itories). The immediate applications of this would allow non-programmers to generate programs, or experts to abstract away trivial coding tasks. addition, from a machine learning perspective, allows complex functions to be generated in symbolic and human-readable form which can be subjected to a wide range of static analysis tools to model generality or correctness.
To date this challenge has been studied using ceanralnetworr-daee driven synthesis, genetic program- ming, and SMT solvers. However, at present these approaches are significantly constrained in the complexity of the target language in which code is synthesised. Neural synthesis for example, such as the DeepCoder architecture (Balog et al.) 2017 Zohar & Wolf) (018)), shows success on sim- ple Nomain--peccite languages, but the search space more realistic Turing-complete languages is vast by comparison and is unlikely to be representable in a neural network on current or near-future hardware. Genetic programming, meanwhile, is limited by our ability specify a fitness function which can successfully navigate to a solution for particular problem in the highly irregular and often flat fitness landscape of program space (Kinnear 1994 Renzullo al.) 2018). SMT solvers by
comparison lack the analytical power to handle loops without human guidance, constraining their applicability (Srivastava al., 2010a So & Oh 2018 Srivastava et al. 2010b).
In this paper we examine code synthesis from examples for a furing-complete language which can be cross-compiled into C/Java. We use just 10 input/output examples to describe each problem for which we need to synthesise matching function (i.e., providing unsorted and sorted arrays of in- tegers to describe sorting): because our target language yields a total search space size of 19 possible program permutations. scalability of the synthesis technique is crucial. In this context, use a novel combination of genetic programming (GP) and neural networks (NNs): GP is used to navigate within program space from given starting point using general-purpose fitness function,

---

Under review as a conference paper at ICLR 2021
while NN methods are used provide prediction of high-level features which help guide the GP to higher-probabee success areas in which to search. In essence this technique allows the NN to model only highly abstract features of program space, allowing it to scale to vast program search spaces, while the GP can then incremenaally traverse program space from an NN-derived starting point to correct solution. We bootstrap this process by using an unstructured form of curriculum learning, in which successfully-found functions are used as seed programs to generate synthetic corpora on which train new neural networks, leading further high-utility source code feature predictions for new problems. Initially this curriculum learning is based on programs that can be successfully found using GP alone with our generic fitness function, which then allows us syn- thesise more complex programs using NN inference.
Our key results demonstrate that GP able to solve simple synthesis problems unaided, and that synthetic corpora generated from these problems allow popular neural network architectures to iden- tify high-utility search hints on more complex problems to guide the genetic programming search. In one of our problem sets, this has the effect of allowing the framework to successfully synthesise 7 of the 10 programs that had never been found by GP alone, and among other programs moves success rates from 38% to 55%. All of our source code is provided online (pending de amonymisation)..
2 RELATED WORK
Code synthesis from I/O examples has been studied using three major approaches: deductive solvers; neural networks (NNs) with search; and genetic programming (GP). For code synthesis in a Turing- complete language, deductive solvers have yet been shown to operate well with loop-based flow control operators (although frameworks which manually define any non-lineat program flow can yield good performance (So & Ohl 2018)). Neural synthesis, by comparison, is limited by how much of program space for ceneral-purposs target language can be captured in a NN model, while GP is limited by the difficulty of deriving fitness function to navigate to solution (Renzullo al., 2018). In the remainder of this section we focus on NN and GP approaches in more detail.
Neural synthesis Neural synthesis works by training a neural network on a sub-sample of the entirety of program space for the target language (e.g., sampling uniform interval at random). When presented with a new problem as an I/O example, the neural network will then be asked to predict which lines of code (or particular operators) are likely to be present in the solution based on similar I/O transforms observed in the training set from the above sub-sample. The system will then perform an exhaustive search of program space to fill in the remaining (non (onn-predccted) features. Notable examples here include DeepCoder and RobustFill, among others (e.g.. [Balog et al. (2017);
Zohar& & Wolf 20188) Devlin et al. (2017); Chen et al. (0019) Singh & Kohli (2017))
The key limitation to this approach is that it must be able to train on detailed enough sub-sample of program space, and store this sample inside a neural network, to make mcaningful predictions on program features for unseen problems. While this works for highly simplified languages (Deep- Coder, for example, has no loop operators (Balog et al. 2017)), the search space size of a Turing- complete language is astronomical by comparison. If we consider that the capacity of beed-forward ReLu neural network to differentiate between classes (in our case programs), termed its VapnikCher- vonenkis (VC) dimension, best grows linear function of L log(w) where w is the total number of weights and L the number of layers (Bartlett et al., 2019). it is unlikely that a neural network on current hardware would be able to represent a useful sub-sample of possible program permutations yielded by the search space of a general-purpose language.
Genetic programming GP relies on iterative travel through program space from starting point (often an empty program) to the solution, guided by a fitness function (Vanneschi & Poli 2012] Taleby Ahvanoocy et al. 2019). The field has long history (Forsyth) 1981) but still shows sults (Miranda et al., 2019) that are competitive with neural networks (Ain et al. 2020). and an ability to tackle complex problems mixing diverse datatypes (Pantridge & Spector 2020).
Unlike neural synthesis, a GP approach does not need to encode the entirety of program space in a model, and can in theory work in scalable fashion high dimensional search spaces long as a fitness function is provided which can guide the search incrementally towards a solution. The key problem with GP for code synthesis is that large areas of program space are difficult to navigate,
2

---

Under review as a conference paper at ICLR 2021
exhibiting large plateaus of neutrality (no behavioural change despite significant code change) and highly irregular responses to code change (jagged fitness landscape) (Renzullo et al. 2018: Kinnear 1994]. A fitness function may also fail to capture higher level properties, for example "all outputs are even" or "all values from the input are repeated in the output", which may otherwise be identified by neural network.
Combining neural network prediction with genetic programming Given the limitations of both NNs and GP in themselves, we hypothesise that the combination of the two techniques may provide the best features of both while mitigating their respective limitations the context of code synthesis in Turine-complete language with a very large program search space.
While a NN cannot feasibly model all of program space, and so cannot be expected to predict each line to be synthesised, it does have the potential to predicting small number of higher-level features which only require a very limited internal model of program space. This can be combined with a GP search process which fixes these lines in place to constrain the search area, and can this program in combination with one or more generic fitness functions to guide the search to a successful result. We further find that
programs to generate synthetic training sets for a NN focused on that area of program space, which then leads to further high-value predictions of likely features for more complex programs.
successfully-
3 METHODOLOGY
Our system accepts up to ten I/O examples from a user and synthesises the source code of a function which converts those inputs to their corresponding outputs. We use 10 examples number which a user may be willing to input while representing lower effort than writing the function manually. If our system fails to synthesise source code for given problem, the user can specify a simpler but related I/O problem; the successful synthesis of this simpler problem can then lead to subsequent success on the more complex problem. As a target programming language for synthesis, we use a Turing-complete language (previously used by the authors of (Wild & Porter 2019)) which can be cross-compiled directly into C/Java/Python. The language features primitive loop operators, variable declarations, and conditional branch operators; full listing of its operators is given in appendix [ A.
We use a combination of GP guided by NN prediction to approach this problem, and show successful synthesis of a wide range of programs including sorting. In this paper we study three specific parts of the above overall framework: (i) the success rate of GP by itself of finding programs in our problem sets; (ii) the effect of different hints (suggested lines of code) the success rate of GP; (iii) the ability of a NN to predict high-utility hints, after being trained on a synthetic corpus derived from high-success program finds from the GP alone.
In the remainder of this section we describe our problem sets, genetic programming and NN imple- mentations more detail, then present the set of experiments that we conduct.
3.1 SPECIFICATION OF PROBLEM
We use two different problem sets which represent human- useful programs of the kind that may be input into our system. Our first problem set is array-to-array programs such as extract even numbers, append arrays, or sort. Our second problem set is provided with an image to draw on canvas and must synthesise the program which draws that image (this problem set is taken from So & Oh 2018)).
Each problem within each problem set is presented to the system as a set of 10 IO examples. These are generated for each problem by feeding in 10 inputs and corresponding outputs of the form the problem requires (either a randomly generated input array and integer, or a canvas size). These 10 inputs are randomly generated from fixed seed, to reduce internal variability between tests, allowing more accurate evaluation of the changes made by alterations to parameters or by guidance to the GP. This is designed to represent an unbiased input set.
3

---

Under review as a conference paper at ICLR 2021
3.2 GENETIC PROGRAMMING
Our GP algorithm creates population of 2,000 programs, each one the result of crossover and mutation from among the 10 highest-ranked parents of the previous generation (or, for the first generation, mutations of the empty program). Each program in a population is then ranked using general-purpose fitness function which was experimentally found to be good at locating programs from various search space starting points. We integrate novelty search (Lehman & Stanley 2010)) Doncieux et al., 2019) as part of our fitness function to avoid falling into the same local minima repeatedly, which was found to further boost search success. Once all programs have been ranked, a new generation of 2,000 members is then created, repeatedly, until the target program is found or the system reaches a maximum number of generations (3,000) and reports failure.
Our fitness function, in detail, is formulated as error * novelty penalty. The value for error is calculated the number of elements in the output of candidate function which do not match those expected for the corresponding input; this value is normalised into the range [0.0, -1.0j by dividing it by the corresponding error which would have been produced by an empty output for that input.
The value for novelty penalty is calculated by first extracting the highest-fitness member of a population, and removing all lines of code which do not contribute to its behaviour. This program is stored as repulsor which indicates how well-explored a given region of program space is. When calculating the fitness of new program, each repulsor adds a multiplicative value depending on the distance D of that program from the repuisor. D) itself is calculated by examining each line in the first program and calculating how far away (in lines of code) the same line is in second program. Each repulsor adds max (0, D/15) to novelty.penaltyy such that multiple repulsors can exist in the same area program space, leading to stronger avoidance of those areas.
For each new generation during the GP search, parents are chosen using tournament selection with tournament size of 10 (Miller & Goldberg 1995). Crossover occurs by taking the first half of the first parent, and appending the second half of the second parent (syntactically flawed offspring accepted into the population but receive minimal fitness when evaluated). Following crossover, we apply single mutation program with a probability of 0.35. Following each mutation a random boolean value is selected, and true another mutation is applied, to a maximum of 8 mutations.
Each mutation takes of the following forms, selected uniformly random:
1. Insert: this inserts random line from all possible lines available in the language, and will delete last lines of program if program is already at maximum length. automatically adds ENDBLOCK operator if a flow-control operator inserted.
2. Delete: sets a random line to NO-OP.
3. Mutate: changes a random operatorrparameter on a line, ensuring the line remains valid.
4. Swap:
exchanges position of any two lines of the program.
In all of the above, the parameter values relating to D and mutation probabilities were chosen as values found to experimentally work well.
3.3 NEURAL NETWORK DESIGN
While no programs have yet been successfully synthesised by our system, we initially rely on GP as above to locate simpler programs. Once at least one program has been located it is added to our set of successfully found programs Sp. We then augment GP with a neural network which provides hints of one or more likely lines of code for given unsolved problem, which correspond to likely areas of program space in which the GP will search (rather than the GP starting its search from an empty program). Our NN is trained set are generated at random but must exhibit some of the program features present in programs in Sp. The intuition here is that the neural network will thus learn to recognise which program features are likely to be present for unseen I/O examples, based on program features known to be useful in other programs requested by users, which are then useful to guide the GP search.
synthesised training set of programs; the programs in this training
Each synthesised training corpus based on Sp has 20,000 programs for training and 2,000 for test- ing. The 20,000 programs divided into 10,000 which do have particular program fragment
4

---

Under review as a conference paper at ICLR 2021
of interest, and 10,000 which do not have that fragment, with the NN trained to determine whether or not a given 1/O example is likely to have that fragment in the corresponding implementation program. Each program in each set of 10,000 is assured to be distinct in functionality from every other program in the set, tested on its hehaviour with respect to a fixed 10 I/O examples. Each new program in training set is generated by selecting uniformly at random two programs already cepted, applying a crossover, then applying between I and 8 mutations (as described above in the GP section) while assuring that the fragment of interest still exists.
We use a range of NN architectures to study which ones work best in each problem set. Specifically we use a forwaforward NN in both problem sets, as shared baseline; in our array-to-array problem set we then also use an LSTM-basch recurrent network, and in our canvas problem set we use a CNN. The details of all network architectures are described in appendix A.3
3.4 EXPERIMENT SETUP
We use three different experiments to study each element of our approach. The details of each experiment are given below, while the next section presents the results.
Experiment 1: Exhaustive Fragment Evaluation In our first experiment we examine the base- line performance of GP alone on our two problem sets, then study the effect of each possible source code hint that can be given for each problem (in terms of its effect on success rate).
For the latter we examine the set of or 2-line code fragments which can be cleanly isolated (with no dependencies) in the ground truth solution to each problem. We then run a GP pass with the code fragment as a forced requirement, such that any program produced by the GP which does not include them automatically receives a penalty fitness of 10,000. Each experiment in this series is repeated 30 times to account for the inherent stochasticity in the GP process.
These results demonstrate the kinds of problem that can be solved using GP alone, and the extent to which a GP algorithm can have its probability of finding a solution increased by constraining its sampled programs to contain certain lines of code which help identify the highest utility hints that a NN can seek to find.
Experiment 2: Fragment Recognisability by Neural Network Having established that code fragments can be used to improve GP find rates (including from zero to non-zero find rates), our second experiment studies the use of synthetic NN training corpora based around these fragments and the extent which NNs can successfully predict these features in unseen problems to assist GP.
For this experiment we need to assume that some programs have already been found by the GP alone, and useful fragments identified, from which automatically synthesise NN training sets as described above.
For our array-to-array problem set, we select all programs which have find rates of 90% and above using the GP alone from experiment 1. For our canvas problem set, we select the single highest find- rate program using the GP alone for each 'class" of problem identified by So Oh (2018) (such as 'triangles), These programs represent those which are most likely to have been found first without the aid of the NN. From within the source code of these programs we select a set of individual fragments from which to generate our synthetic NN training corpora. These fragments are chosen using high-utility fragments identified from experiment 1, and augmented with further fragments of interest that were manually chosen to gain wider coverage of fragment predictability by a NN.
Altogether, these experiments indicate how well NNs can predict the presence of different program features based on synthetic training sets a mechanism by which the solution to easy (high-find- rate) problems can be used to find solutions to hard (low-find -in-fii--rate) problems.
Experiment 3: Success of chosen fragments In the third experiment we test the success of our GP algorithm when guided by NN-predicted source code fragments using the trained NNs from experiment 2, using all problems in each problem set. To do this we apply a simple selection process, choosing uniformly at random from among all fragments which were estimated by an NN to have a probability of >= 0.5 presence in a program, and provide one such fragment to the GP process. This shows how full neurally-guided GP process would perform in end-to-end system.
5

---

Under review as a conference paper at ICLR 2021
Problem
Baseline
Maximum
Best Operators
Append
0%
27%
Var=Literal 1; Addition
Cumulative Abs Sum
0%
3%
Loop; Read
Keep Evens
0%
7%
Var=Literal 2: Make Array
Retain First Half
0%
13%
Var=I.iteral Divide
Reverse
58%
80%
Var=L.iteral 1: Make Array
Shift Right
0%
13%
Var=I_iteral
Var=Literal Loop
Shift Right Lossy
84%
80%
Sort (Bubblesort)
0%
0%
(None)
Parallclogram
7%
30%
Var=Literal 2: Divide
Mirrored Hollow Parallclogram
13%
60%
Var=Literal Divide
Hollow Right Triangle
87%
90%
Var=I.iteral Subtract
Hollow Mirrored Right Triangle
63%
93%
Var=L.itera 1: Subtract
Inverted Isosceles Triangle
46%
23%
Var=L.itera 2
Trapezoid
7%
10%
Var=Literal 1
Table I: Find rates for guided Genetic Programming Algorithm with forced inclusion of code frag-
ments from ground truth. Baseline is unguided GP. Maximum is single best performing fragments. Best operators are those used in the highest-scoring fragment (first if tied) (n=30 per fragment, per- centage success)
EVALUATION
Our evaluation was conducted Tensorflow 1. 1.14, Python 3.6.9, Java OpenJDK 11.0.6. Our source code will be made available in camera-ready version
4.1 EXPERIMENT 1: GP BASELINE AND ITERATIVE REQUIREMENT SEARCH
In this experiment we first determine the baseline find rate of the GP with no assistance, and also select number problems to study by supplying certain subsets of the lines as guidance to the GP. This is done by fully rumning 30 GP search repeats with each valid (as described above) 2-line fragment from the ground truth. From the first corpus we selected 8 problems, from the second select 6. From the first corpus select mostly low-findrrate problems, to study which form of fragments would be useful to provide to achieve success the GP, while in the second corpus select more representative sample, study how constraint-forcing behaves in general. We select two problems of the same class from the 2nd corpus (right triangles), to ensure that similar fragments provide similar results in similar circumstances (to give confidence in generality of these results). The baseline success, best find rate increase, and best fragment's operators for selected problems are presented Table 4.1
Here we clearly see that forcing the inclusion of even the simplest code elements (one or two lines of the ground truth) into the GP's population allows the GP find previously unsolvable problems. We can also see that fragments containing arithmetic operators (especially literal assignment) appear to have stronger influence on success, possibly as they are harder to find, as their effects are far more subtle and complex than, say presence of loop operator. These should therefore be studied as high-utility candidates for deployment into GP processes we wish to guide in the future.
We also note that some examples show decrease in success rate (c.g. "Shift Right Lossy"). While no fragment reduced find rates to zero, we speculate that in some cases the provision of a fragment places the GP into general-purpott fitness function (for example, meaning that this point in program space has larger regions of neutral landscape around it which are harder traverse over).
of program space from which it is harder reach the solution using
A full breakdown of all bascline GP find rates presented Appendix A.4 with fragments and their successes presented in Appendix A.5

---

I/O example will include Under review as a conference paper at ICLR 2021
Fragment
FENN
FENN Test
RNN
RNN Test
Add
62
62
+1 Offset Loop
74 %
67 %
71 %
66 %
Length Loop
66
65
Literal (2)
76 %
63%
71 %
60 %
Loop
97 %
78%
98 %
79 %
Loop+Conditional
72 %
62%
70 %
59 %
Leop+Read
65 %
61%
62 %
58 %
Nonstandard Array
81 %
68%
80 %
66
Read
76 %
63%
60 %
58 %
Subtract
%
56%
62 %
56
Average
74 %
65 %
71 %
63 %
Fragment
FENN
FENN Test
CNN HU
CNN Test
Add
58 %
67 %
78 %
86 %
Conditional
61 %
57 %
64 %
85 %
Half
61 %
62 %
87 %
87 %
Half Loop
65 %
60
82 %
87
Half Loop Depend
70 %
59 %
82 %
90 %
Loop Conditional
64 %
58
%
85
Loop Draw
65 %
58 %
70 %
85 %
Loop Loop
57
75
Loop Loop Subtract
60 %
55 %
64 %
77 %
Draw Draw
52
52
71
Average
63 %
58 %
74 %
83 %
Table 2: Percentage accuracy of two neural networks two corpora, with regards to ability to recognise presence of code fragment within the source code of the function whose IO mapping they are receiving feature inputs. First NN architecture is common FFNN implementation. Accuracy is only that of the NNs which show success on known-ground-truut seed fragments (as described in methodology, others discarded from results). Testing accuracy is accuracy on the 2,000
synthetic testing programs. Full description of fragments in Appendix Tables 24 and 25 (n=30)
4.2 EXPERIMENT 2: FRAGMENT RECOGNISABILITY
In this experiment we start with selected high-success seed programs from our first experiment. For array-to-array problems, these all programs with 90% find rate better via GP alone, while for our canvas drawing problem set, these are the single highest-find-rate program in each category such 'triangles', We then take 10 source code fragments present in these seed programs which exhibit a positive effect of find rates, and use these fragments to generate completely synthetic training corpora for neural networks trained to predict whether particular fragment in its source code solution.
Table 4.2 shows how effective our different trained neural networks architectures are at then correctly predicting the presence of these fragments in the I/O examples from our two problem sets (which are not part of the synthetic training sets).
This data show significant variance of prediction success (from 58% up to 97%) but overall shows that our neural networks do exhibit the ability to accurately predict that particular source code fragment will exist in the solution to given I/O problem even though these neural networks are trained on entirely synthetic data.
Examining the different neural network architectures, our baseline feed-forward NN shows success both problem sets and so is able to act as viable generalist model. Our recurrent network, used in the array-to-array corpus, shows prediction success that is generally lower than the feed-forward NN. Our CNN meanwhile, used in our canvas drawing corpus, shows some significant gains in prediction success compared the feed-forward NN, though also shows some lower results (for example on predicting the presence of a loop with conditional). This suggests that a mixture-of- experts approach may be desirable here, but also that general feed-forward model is viable.

---

Under review as a conference paper at ICLR 2021
In practice would use these trained networks alongside threshold of prediction when determin- ing which fragments to recommend for inclusion in a GP search; we present this in the following section.
4.3 EXPERIMENT 3: CHOSEN FRAGMENT DEPLOYMENT
In this experiment, the fragments from the above NN experiments were employed to guide the GP process, based the average estimates by the trained neural networks. This demonstrates the efficacy of our end-to-end system in taking successfully-found solutions to easy problems and em- ploying their characteristics, via trained NN predictors, find solutions to more difficult problems.
We report the success rates here using two different approaches to selecting fragments for the GP. We do this either using uniform random choice of fragments which had average presence probability estimate of >= 0.5 (termed Uniform); or using fragment which is predicted for the problem being solved but has the lowest prediction rate across all other problems (which ideally therefore may be the most information bearing fragment). For our array-to-array problem set we use both approaches, while for our canvas problem set see less clarity in lowest prediction rates across all problems and so only use the uniform random style.
Corpus And Approach
Find Rate Baseline)
Gained
Lost
1st (1D Arrays), Uniform
46 % (38%)
5
1st (1D Arrays), Rarest Preferred
55 % (38%)
0
2nd (2D Array), Uniform
39 % (36%)
Table 3: Success of the GP when guided by the fragments selected by the neural network. 'Gained' problems which have 0% find rate which have baseline of 0%, 'Lost' those which previously had 0% but now have 0%. (n=30)
As can be seen in Table 4.3 guiding the GP using this process produces notable improvements to the overall program synthesis success rates. Average find rates were boosted, and crucially a number of problems became solvable which were not before, with only a single problem in each problem failing to be solved. This set of newly-solved problems here includes instance in which the bubblesort algorithm, considered by the authors to be the hardest problem in the set, was successfully found.
This improvement was strongest on the approach which selected the estimated-rares. fragment for use, clearly indicating that the fragments are not equivalent in their usefulness. The ideal way in which to extract the most useful fragments for the GP to use, based on those available from NN predictions, therefore remains topic future work.
The full set of guided GP results is available in detail in Appendix A.7
5 CONCLUSION
In this paper we have presented a novel combination of genetic programming and neural network prediction synthesise code from just 10 I/O examples.
Our framework demonstrates the potential to create a system which searches for solutions to prob- lems within a corpus, finds subset, extracts code fragments from the successes, then trains a neural network to recognise the presence of these fragments and determines which unsolved problems would benefit from NN-guidance thus boosting GP find rates on a subsequent pass. We demon- strate that this process render previously unfindable problems findable, and boost overall find rates, including the successful synthesis of bubble sort.
Our approach is scalable to the search space of ceriingcommllte languages, and has been demon- strated to work successfully in at least two distinct domains using a common target language which can be cross-compiled to C/lava.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Qurrat UI Ain, Harith AI-Sahaf, Bing Xue, and Mengjie Zhang. A genetic programming approach to feature construction for ensemble learning in skin cancer detection. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, pp. 1 11861199 194, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 178145037. doi: 10.1145/ 3377930.3390228. URL URL.http:://boo.cr/// /tt..////.1111137777711171010111 3330222
Matej
Balog, Alexander Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tar- low. Deepcoder: Learning to write programs. In Proceedings of ICLR'17, March
2017. URL htttps:/wwwmmicrossttf. cttp////wor//rreeeeecc///plalaaa baapooaeerllaa.nlng---eeeeeooooo
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning html
Research, 20(63):1-17, 2019. httht:/p///mm http:////iiimroorrppprppssseee/e wttp:o/pppp/e//////1---/------
X. Chen, C. Liu, and D. Song. Execution-guider neural program synthesis. In ICLR, 2019.
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, pp. 990998. JMLR.org, 2017.
Stephane Doncieux, Alban Laflaquière, and Alexandre Coninx. Novelty search: theoretical per- spective. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO $19 pp. 99106, New York, NY, USA, 2019. Association for Computing Machinery. ISBN doi: 10.1445/321100.:3321522 URL https:://oo www.eei....r..eeooeeeo.eoooooeee org/ /Tg//10.115/
7781450361118.
3321707. 3321752
Richard Forsyth. BEAGLE Darwinian approach to pattern recognition. Kybernetes, 10(3):
159-166, 1981. ISSN 0368-492X. doi: d0i: 108/eb005587.
URL. http://www.
r richardsandes httprrssttcneettto////eeeeeeaeee
K. E. Kinnear. Fitness landscapes and difficulty in genetic programming. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress Computational Intelligence, pp. 142-14 147 vol.1, 1994.
Joel Lehman and Kenneth Stanley. Efficiently evolving programs through the search for novelty. pp. 837-844, 01 2010. doi: 10.1145/183048., 1830688.
B. Miller and D. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Syst., 9, 1995.
ícaro Marcelino Miranda, Claus Aranha, and Marcelo Ladeira. Classification of ceg signals using genetic programming for feature construction. In Proceedings of the Genetic and Evolution- ary Computation Conference, GECCO '19, pp. 12751283, New York, NY, USA, 2019. Associ- ation for Computing Machinery. ISBN 978 9781450366118, doi: 10.1145/321177.333217331 URL
https:://doi.org/1.. 1ttp://...1111322111111 3321737
Edward Pantridge and Lee Spector. Code building genetic programming. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, pp. 994-1002, 06 2020. doi: 10.1145/337793003399333
Joseph Renzullo, Westley Weimer, Melanie Moses, and Stephanie Forrest. Neutrality and epista- sis in program space. Proceedings of the 4th International Workshop on Genetic Improve- ment Whrkshop, GI 18, pp. 18, New York, NY. USA, 2018. Association for Computing Machin- ery. ISBN 9781 450357537. doi: 10. 01145/394880031998811 URL htthtt//:///oii.. orgg 0745/31948111 3194812]
Rishabh Singh and Pushmeet Kohli. AP: Artificial Programming. Snapl '17, (16):1 2017. ISSN 18688969. doi: 122300.PPcs.SNNAPP.220111

---

Under review as a conference paper at ICLR 2021
Sunbeom So and Hakjoo Oh. Synthesizing pattern programs from examples. In Proceedings of the Twenty-Seventh Interaational Joint Conference on Artificial Intelligence, JJCAI-18, pp. 1618- 1624. International Joint Conferences Artificial Intelligence Organization. 7 2018. doi: 10. 24963/ijcai. 201ii22211/// 8/224.
URL http:ttt://// /oo. org/ 10. 24963/ jcai. .2018/2211222
Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. From program verification to program synthesis. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium Principles of Progrumming Languages, POPL 10, pp. 313326, New York, NY, USA, 2010a. Association for
Computing Machinery. ISBN 9781605584799, doi: 10.1145/1706299.110 1706337.
URL https:
V/doi. 10. 1145/1706299.1770000
Saurabh Srivastava, Sumit Gulwani, and Jeffrey S. Foster. From program verification to pro-
gram synthesis. SIGPLAN Not., 45(1):313326,, January 2010b. ISSN 0362-1340.
doi: httttps://do..ogg/ii1ie 115.
10.114//107800.1706337
Milad Taleby Abvanooey. Qianmu Li, Ming Wu, and Shuo Wang. A survey of genetic programming and its applications. KSII Transactions Internet and Information Systems, Vol.13:1765-1799
04 2019. doi: 203837/tis.20199.00 2002.04.00.
Leonardo Vanneschi and Riccardo Poli. Genetic cewrramminnn--ttrrdeeeeeee Applicationns Theory and Open Issues, pp. 709-739. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 978-
3-540-92910-9, doi: 10. (0000997--3-4009299911
URL
978 3- 540 92910-9_22
Alexander Wild and Barry Porter. General program synthesis using guided corpus generation and automatic refactoring. In Shiva Nejati and Gregory Gay (eds.). Search-Based Software Engi- neering, Lecture Notes in Computer Science, pp. 89-104. Springer-Verlag August 2019. ISBN 9783030274542. doi: (0007/978-30000-775535
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2094-2103. Curran Asso- ciates, Inc., 2018
A APPENDIX
A.1 OPERATORS OF THE LANGUAGE USED
Tables A.1 and A. provide lists of all the operators used for the corpora used in the language employed in the experiments. Language variants are improved in order to allow effective processing of the two corpora's specific problem domains.
Operator
Assign Variable To Array
Assign Variable From Array
Make Array
Variable To Literal
Add
Subtract
Multiply
Divide
Modulo
Assign Var from Var
Loop
Conditional (var > 0)
Conditional (varl var2)
Conditional (varl > var2)
Table 4: Operators available for GP, when using the 1st (array-to-array) corpus
10

---

Under review as a conference paper at ICLR 2021
Operator
Assign Variable To Array
Assign Variable From Arra
Make Array
Variable To Literal
Add
Subtract
Multiply
Divide
Modulo
Assign Var from Var
Loop
Conditional (var 0)
Conditional (varl = var2)
Create 2D Array
Get 2D Array Size
Var to XY Point from 2D Array
Set 2D Array 0 at XY Point
Set 2D Array to at XY Point
Table Operators available for GP, when using the 2nd (2D pattern) corpus
A.2 PROBLEMS IN CORPORA
Tables and provide a list of all human- provided problems used to test the system across the experiments. These defined by source-code implementation in both the custom language used in this paper, as well as in Java. An example of the behaviour of the array-to-array problems (First corpus), has been given, using fixed sample input, to illustrate the behaviour.
human-provided

---

Under review as a conference paper at ICLR 2021
Problem
Example
Abs
[4,-2,
[4, 2. 0,
ArrayLength
14,-2,1,0,3,-55
1,,0,0,0,0.000
ArrayToZera
[4,-2,1,0,3,-5] - 00.0,0,0.0,01
CumulativeAAboluttSSi
14.-2.1,0.3,-5)
14,6,7,7,10,,,
CumulativeSum
[4,-2,1,0,3,-5
[4.2,3.3.6.1]
DivergentSequence
14.-2.1,0.3,-5] [0, 0. 1,,1,,,)
FinsEElementOnly
[4.-2.1,0.3.-5] - [4]
Identity
14.-2.1,0.3.-55
1,,
IndexParity
[4..2,1,0.3,-5
11,0,
DerfaiveDiiffernce
[4,-2,1,0,3,-5]
14,,6,3,-1,,3-81
KeepEvens
[4..2.1.0.3.-55
[4.-2.0.0.0.0]
KeepNegatives
[4..2,1,0.3,-55 - [0,-2,0,0,0,-55)
KeepOdds
[4.-2,1.0.3.555
10,0,1,0,3,-51
KeepPositives
[4.-2,1,0.3,-5 [4.0,
Negative
[4.-2,1.0.3.55-
[4.22.1..0-33.5]
Pop
[4,-2,1,0,3,-5 - [4,-2,1,0,3]
RemoveFirstElenie
[4.-2,1,0.3,-5
1-,,1,
RetainFirstHalf
[4.-2.1.0.33-5
[4.-2,
Reverse
[4.-2,1.0.3,-5
1,-24.
ShiftLeft
[4.-2,1,0.3,-5] - [-2,1,0,3,-5]
ShiftLeeiZZerrPaadded
[4.-2,1,0.3,-55
[22,1,0.3,-50]]
ShiftRight
[ -0,03,))-000,,,22200 10.4.2.1..333.
Shift
[4,-2,1,0,3,-55 - [0,4,-2,1,0,3]
ShuffleZerosTo ToBack
[4.-2,1,0.3,-55 - (4,-2,1,3,-5.01
Signum
[4.-2.1,0.3,-55 - 11,-1,1,0,1,-11
Sort
[4.-2.1.0.3.-5--
1,3.-2.0,1,3.44
Square
[4.-2, 1 1,,,4.
Tolterator
14.-2,1,0.3,55]-
(0,1,2,3
Add
-4.2,1...33355)44---33 (8,2,,,,777
>
Append
14..2,1.0.3,55,,
14,32.1,0.33.55.4
ClipTToMax
[4,-2,1,0,3,
(4,-2,1,0,3,-55
ClipToMin
14..2,1.0.3,55,.4
[4.4.4.4.4.4]
ConstantAdditton
[4.-2,1.0.3.-5]
12,
FillAray
14.-2,1.0.3,
> [4.4,4.4.4.4)
GreaterThan
[4..2,
[-1.-1.-1.-1,-1.-1
SterateFromStart
14.-2,
(4,5,6,7,8,9)
LessThan
1...3
1,,1,
MultiplesOf
14,-2,
-- [0,
4, 12,
Multiply
[4, 1.033-5
[16,
8,,.0
Subtract
[4, 1,0,3,
60,
Table The first corpus of problems, taking either single array, or an array and an integer. Exam- ple provided of the behaviour of each problem, given standard example input.
12

---

Under review as a conference paper at ICLR 2021
Problem
Square
HollowSSuurr
Parallelogram
Hollow
MirroredParallelogeee
Mirroed/ooloowwarrlleeeooo
RighTTriangle
Hollow Triht
MirroredRighrTTiingg.
Hollow
InvertedRighrTrianglee
Hollow
invertedMiirooredRighhe Triangle
Triangg
Isocelese Triangle
Invertedlsocelese Trinngeeegleeeeee Triangle
Hollow soeee
Rectangle Emth Tiaapeopyy Trapezoid
eneeatedRectanglee
JobuseTTriangle
hollowObtuse TrinseTiggngienn
mirroredObtuse Triangle
mirooredHolloooOOuueeiiiiii
invertedObbuseeTrianggee
inllowwnnerreedbbbuseee Triangle
inverecdMirroredObtuseeiiiingg
VShape
Trapezoid
Table 7: The second corpus, set of 2D image generation tasks, drawing simple geometric shapes.
A.3 NEURAL NETWORK ARCHITECTURES
Feed Forward Neural Network The FFNN is a layer structure with 128 nodes per layer, seLu activation. Each layer is connected to all layers below (dense block). Each layer other than the last has dropout component, with a training dropout rate of pKeep 0.75. The output is a single sigmoidal unit, loss function is mean squared error. Batch size of 32, maximum steps of 512, early stopping after 12 non-progress epochs on validation loss.
Recurrent Neural Network The RNN encodes both the input and output arrays in two architec- turally symmetric branches for every example (so 20 branches). Each branch begins by encoding the values in 2 dense layers with 11 nodes, rel.u activation, with dropout with pKeep eep = 0.75 af- ter each. After this encoding layer, a layer of L.TTM nodes connected. These L.TTM layers represented the end of the two branches. All LSTTM outputs are concatenated, along with the input parameters, into a single representation of the IO examples. These then processed by a of dense layers with 64 nodes, reLu activation. The output is a single sigmoidal unit, loss function is mean squared error. Batch size of 32, maximum steps of 512, early stopping after 12 non non-progress epochs on validation loss.
Convolutional Neural Network Each of the 10 examples of problem output are split into their own branch. Each branch contains a 2D input with width/height equal to the maximum input size, 32. We feed this into 2D convolutional layer, with stride of 2 and kernel size of 3, reLu activation. We then feed this into max pooling layer of by We then feed through second convolutional layer of identical configuration to the first, and second max pooling layer, again identical. Each
13

---

Under review as a conference paper at ICLR 2021
branch then terminates in single dense layer, 64 nodes, reLu activation. All branches then concatenated into a single dense layer, 64 nodes, reLu activation. The output is single sigmoidal unit, loss function is mean squared error. Batch size of 32, maximum steps of 512, early stopping after 12 non-progress epochs on validation loss.
A.4 PROBLEM FIND RATES AND DESCRIPTIONS
The tables are the find rates for the genetic programming algorithm, without any constraints. Note the high degree of variability between problems, with a number from both corpora achieving either a 100% success rate 0%.
One remark is that the "SSuurr" problem, which simply requires the entire canvas to be covered (therefore requiring two loops and a write), did not achieve 100% success. This is believed to be due to the genetic algorithm starting with flawed partial solution, and being unable to move away from this detrimental start due to the nature the fitness landscape (trapped in local maximum).
A.5 FULL BREAKDOWN OF FRAGMENTS EVALUATED IN EXPERIMENT 1
Tables 10 to 23 describe each fragment evaluated by the exhaustive fragment testing process. Each fragment is at most two lines, and has no variables which depend on being set in lines outside the fragment (therefore the fragment stands alone in terms of functionality). The source code of the ground-truth implementation is given, firstly as simply the operator used on that line, and secondly in a C-like fashion (excluding braces). This C-like fashion is programmatically generated translation of the source code of the custom language implementation, provided for ease of readability (due to the difficult-lo-parss structure of the custom language). We then refer to the lines in this source code by line number. Fragments cannot contain end-of-block operators (used to indicate the end point of blocks started by the flow-control operators loop and conditional), nor can they contain the initial definition of the 2D canvas.
A.6 FRAGMENTS EVALUATED FOR NN RECOGNISABILITY IN EXPERIMENT
The table 2425 describe the fragments (some of which contain requirements about variable depen- dencies) used in experiment 2.
A.7 FULL RESULTS OF NN-SELECTED GUIDANCE FOR GP FROM EXPERIMENT 3
Tables 26 shows the success rate of the GP, if provided with hints by the neural network sets. Two sets of experiments are done on the array to array corpus, one on the canvas corpus. Most problems showed success increase, including a number from both corpora which increased in success chance from 0% to non-zero value. Two problems were made unfindable by the less- effective uniform fragment selection process, Iterative Difference and Trapezoid. As the baseline find rate was low, this does not represent a major drop in success, and may potentially simply be due insufficient samples determine the true success probability. We do not however reject the possibility that our approach has negative effect find-rates for certain problems. It was seen in Experiment that some fragments, known be present in the ground-truth implementation, decreased find-rates. It is possible that the neural networks correctly identified fragment presence, but that these degraded the GP's performance. It is, of course, also possible that the NN incorrectly estimated that a fragment was present when it was not, and that this erroneous hint harmed the GP.
14

---

Under review as a conference paper at ICLR 2021
Problem
Baseline Find Rate
Abs
ArrayLength
100 %
ArrayToZers
100
CumulativeAAsoolueSSum
0 %
CumulativeSum
DivergentSequenee
58 %
FirstElementOnly
28 %
Identity
100 %
IndexParity
100 %
ItefativeDiffrrence
%
KeepEvens
%
KeepNNegatives
KeepOdds
0 %
KeepPositives
60 %
Negative
68 %
Pop
30 %
RemoveFirstElemeeee
10 %
RetainFirstHalf
%
Reverse
58 %
ShiftLeft
10 %
ShiftLeeffZZerPPaddedd
40 %
ShiftRight
%
Shitt
84 %
ShufflcZeroo ToBack
100 %
Signum
Sort
0 %
Square
70 %
Tolterator
100 %
Add
24 %
Append
%
Clip'ToMax
18 %
ClipToMMin
ConstantAdditton
0 %
FillArray
100
GreaterThan
10 %
Storate
98 %
LessThan
%
MultiplesOf
90 %
Multiply
20 %
Subtract
18 %
Table 8: Find rates for a Genetic Algorithm as implemented above on the problems of the first corpus, set of functions which take an input array of integers only (functions above dividing line) or an input array of integers and an integer. Both forms return single array. n=30
15

---

Under review as a conference paper at ICLR 2021
Problem
Baseline Find Rate
Square
97 %
Hollow Square
100 %
Parallelogram
0 %
Hollow Parallelogram
0 %
Mirrored Parallelogram
7 %
Mirrored Hollow Parallelogram
13
Right Triangle
97 %
Hollow Right Triangle
87
Mirrored Right Triangle
60 %
Hollow Mirrored Right Triangle
63
Inverted Right Triangle
60 %
Hollow Inverted Right Triangle
83
Inverted Mirrored Right Triangle
100 %
Inverted Hollow Mirrored Right Triangle
100 %
Isocelese Triangle
0 %
Hollow Isocelese Triangle
13 %
Inverted Isocelese Triangle
47
Hollow Inverted Isocelese Triangle
50 %
Rectangle With Empty Trapezoid
3 %
Inverted Rectangle With Empty Trapezoid
3 %
Obtuse Triangle
%
Hollow Obtuse Triangle
27 %
Mirrored Obtuse Triangle
0 %
Mirrored Hollow Obtuse Triangle
0 %
Inverted Obtuse Triangle
0 %
Hollow Inverted Obtuse Triangle
10 %
Inverted Mirrored Obtuse Triangle
0 %
Hollow Mirrored Inverted Obtuse Triangle V Shape Trapezoid
3 %
47 %
7 %
Table 9: Find rates for Genetic Algorithm (implementation described above) the problems of the second corpus, set of functions which take an integer size for the returned canvas, and must return the shape specified. n=30
16

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Literal
variables[6] = 1;
2
Add
variables[7] variables[O] + variables(6):
3
Make Array
arrays[1] new int[vars|7]]
4
Loop
for Vazzbass22eeyiiibsssssssuubbbbaa
5
Read
variables[5] = =araaa]
6
Write
[rrays[][variaalees[]]]] = variables[5];
7
Endloop
8
Write
[rrais[][[ariaablss]]] variables[1]] []];
Fragment
Success Rate
1
3%
1,2
27%
1,4
10%
0%
4,5
0%
4
0%
4,8
0%
Table 10: Fragments assessed from program "Append". Program's 's code listed, in C-like format, with operators listed ahead each line for each of readability. Fragments then described, in reference to lines used followed by success rate using fragment as GP guidance (n=30)
17

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Make Array
arrays[]] new int[vars[0]]
2
Loop
for (uaidbbbee22aooaaaaaaooooooooaoa
3
Literal
variablcs[5] -1;
4
Read
variables[3] = arrays[[[[vvrriaaees(]]]]
5
Condition
if (variables else
6
Else
7
Multiply
variables variables[3] variables[5];
8
Endloop
9
Add
variables[4] 4] variables[4) variables(3);
10
Write
= variables[4];
11
Endloop
Fragment
Success Rate
1
0%
1,2
0%
1,3
0%
1,5
0%
1,6
0%
2
0%
2.3
0%
2,4
3%
2,5
3%
2,6
0%
3
0%
3.5
0%
3,6
0%
3,7
0%
5
0%
5,6
3%
6
0%
Table 11: Fragments assessed from program "Cumulative Absolute Sum". Program's code listed, C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference lines used followed by success rate using fragment GP guidance (n=30)
18

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
Literal
variables[4]
2
Make Array
arrays[]] new int[vars[0]]
3
Loop
for (ww.bbeshe2ayyaaahhee22osssassaa
4
Read
variables[3] aaaas///aaaa|l//////aaaaaaall///
5
Modulo
variables[5]] variables[3] % variables(4]:
6
Condition
if (vatables(5==vrriieee((()
7
Write
= variables[3]:
8
Endloop
9
Endloop
Fragment
Success Rate
1
0%
1,2
6%
1,3
3%
1,5
3%
2
3%
2.3
0%
3
0%
3,4
0%
3,7
0%
Table 12: Fragments assessed from program "Keep Evens". Program's code listed, in C-like for- mat, with operators listed ahead of each line for each of readability. Fragments then described, in reference lines used followed by success rate using fragment as GP guidance (n=30)
Line
Operator
As Code
Literal
variables[6] 2:
2
Divide
variables[3] variables[0] variables(6);
3
Make Array
arrays[1]= new int[vars[3]] for
4
Loop
5
Read
variables[S] = [
6
Write
arrays[]][ \(arabbeee]) variables(5);
7
Endloop
Fragment Success Rate
1
0%
1,2
13%
Table 13: Fragments assessed from program "Retain First Half", Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference lines used followed by success rate using fragment as GP guidance (n=30)
19

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Literal
variables[7]]22 =
2
Make Array
arrays[]] new int[vars[0]]
3
Loop
for
Subtract
variables[6] variables[O] variables[2];
5
Subtract
variables[6] variables[6] variables(7]:
6
Read
variables[S] = aarays[[[[variaales([]]]]
7
Write
arrays[]][variab]]]] = variables[5];
8
Endloop
Fragment
Success Rate
1
63%
1,2
80%
1,3
77%
2
73%
2,3
60%
3 63%
3,4 80%
3,7 77%
Fragments assessed from program "Reverse". Program's code listed, C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in refer- ence lines used followed by success rate using fragment as GP guidance (n=30)
Table 14:
Line
Operator
As Code
1
Literal
variables[6] 1;
2
Add
variables(8) [8] = variables(O] + variables(6):
3
Make Array
arrays[]] new int[vars|8]]
4
Loop
for
5
Add
variables[7] variables/2] + variables[6];
6
Read
variables[5] aarays[[[[[ariiabes[[]]]
7
Write
arrays[][[variable]]]] variables[5];
8
Endloop
Fragment
Success Rate
1
3%
1,2
13%
1,4
20%
4
0%
4, 6
0%
Table 15: Fragments assessed from program "Shift Right". Program's code listed, in C-like for- mat, with operators listed ahead of each line for each readability. Fragments then described, in reference lines used followed by success rate using fragment as GP guidance (n=30)
20

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Literal
variables[6] = 2:
2
Add
variables[8] variables[O] variables(6):
3
Make Array
arrays[]] = new int[ [n[[v]][[0]]
4
Subtract
variables[9] variables[]] variables]]]
5
Loop
for (um.leess2-cuurrbooo//////eeeaaa
6
Add
variables[7] variables[2] + variables(6);
7
Read
variables[5] [
8
Write
[rayss]][vriabbles[] = variables[5];
9
Endloop
Fragment
Success Rate
1
80%
1,2
73%
1,3
63%
1,4
63%
3
67%
Table 16: Fragments assessed from program "Shift Right Lossy". Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference lines used followed by success rate using fragment as GP guidance (n=30)
21

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
Literal
variables[5] -ariablesss]
2
Subtract
variables[1] -ariables[00
3
Loop
for (ww.aass722...aaaa2222222aaassaa
4
Loop
for htt.://lhhaaaaaaatoooooeeooeaaaa
5
Add
variables[6] v variables([
6
Read
variables[4] arrays[[[[[variialles[]]]]]
7
Read
variables[7] [7] arrays[0][[arrialess(]]]]]
8
Subtract
variables[8] variables[4] -varialee)
9
Condition
if (variables(8)>0)
10
Write
(araysl(0[ variables[4];
11
Write
arrays[O][ variables[]] variables[7];
12
Endloop
13
Endloop
14
Endloop
15
Make Array
arrays[1] new int[vars[0]]
16
Loop
for arrays[[[[
17
Read
variables[5] = variables[5];
18
Write
19
Endloop
Fragment
Success Rate
0%
1,2
0%
1,3
0%
1,
0%
1, 15
0%
1, 16
0%
3
0%
3,8
0%
3, 115
0%
16
0%
3,
0%
0%
4,6
0%
8
0%
8,9
0%
8, 15
0%
8, 16
0%
15
0%
15, 16
0%
16
0%
Table 17: Fragments assessed from program "Sort". Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference to lines used followed by success rate using fragment as GP guidance (n=30)
22

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Make 2D Arra
2DArttayssizc-vvariaeee(]])) variables[6] 2;
2
Literal
3
Divide
varaaaaaaaaaeelll///aaaaaleeeoo variables[4]
4
Loop
for hrgpap/eeeaaaaaallonniiiiiiihhhe for VatiibbeellBaaaaaaalaaaaaaaaaaal
5
Loop
6
Add
variables[7] = varaallss]]] + variables(3];
variabless]]]++
7
Write 2D
araayvatiooess//vvabblee{{]]]]]
8
Endloop
Endloop
Fragment Success Rate
2
23%
2,3
30%
Table 18: Fragments assessed from program "Mirrored Parallelogram". Program's code listed, in C-like format, with operators listed ahead of each line for each readability. Fragments then described, in reference lines used followed by success rate using fragment GP guidance (n=30)
Line
Operator
As Code
1
Make 2D Arry
2DAmraysiiz-vvariieees())))
2
Literal
v =;
3
Divide
4
Loop
for (rt.rbooee2ii0yooooooooooeaeoaao
5
Add
6
Write to 2D
7
Write to 2D
8
Subtract
9
Write to 2D
array/varibbles///yrnabbsslllll
10
Write to 2D
11
Endloop
12
Literal
variables[8] =
13
Subtract
variables[7] variables(O) -ariaabess(8
14
Write to 2D
amaayvaariales///yvriieee////// 10]]];
Fragment
Success Rate
2
13%
2,3
60%
12
10%
12
13%
12, 13
40%
Fragments assessed from program "Mirrored Hollow Parallelogram". Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference to lines used followed by success rate using fragment as GP guidance (n=30)
Table 19:
23

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Make 2D Array
new 2DArray(siseevaarineee(())))
2
Literal
variables[1]=11 =
3
Subtract
variables[4]] [
for -ariaaiiioibbbbaa varrabeel]] arany/aaaabbes/////abbbbl///-]-
4
Loop
5
Write to 2D
6
Write to 2D
7
Write 2D Endloop
araaylvariabee(]]]vvriaass
8
Fragment
Success Rate
2
80%
2.3
90%
2, 4
80%
4
90%
4, 6
63%
4,7 87%
Table 20: Fragments assessed from program "Hollow Right Triangle". Program's ' code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, reference to lines used followed by success rate using fragment as GP guidance (n=30)
Line
Operator
As Code
Make 2D Array
new 2DAmray(ize-varraaeee())))
2
Literal
variables[3] = varrablees)
3
Subtract
variables|4] variablessbb -arabbeesss)=aaaaaabls0000----
4
Loop
for amny://aialles////uuibbssss//ll
5
Write to 2D
6
Write to 2D
7
Subtract
variables
= v variabless2)
8
Subtract
variables[5] = variables[5] variables[3]:
9
Write to 2D Endloop
10
Fragment
Success Rate
2
67%
2,
93%
2,
80%
4
67%
4,7
80%
Table 21: Fragments assessed from program "Hollow Mirrored Right Triangle". Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, in reference to lines used followed by success rate using fragment as GP guidance (n=30)
24

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Make 2D Array
new 2DArray<iizzvvariaeee(()))
2
Literal
variables[4] =2
3
Loop
for [wanbbeee2eoooiioooeeeeoouuuuuur
4
Multiply
variables[6] = variables <ar;:bles[[];
5
Subtract
variables[5] = variables(0) variables(];
6
Loop
for htwpaiieee....aalaaeeeeeaaeaeeee
7
Add
variables = variables[[] + variabless(2):
8
Write 2D
araayvaiiaee(///vrialel]]]]11]
9
Endloop
10
Endloop
Fragment
Success Rate
2
23%
2,3
20%
3
20%
Table 22: Fragments assessed from program "Inverted Isoceles Triangle". Program's code listed, in C-like format, with operators listed ahead of each line for each of readability. Fragments then described, reference lines used followed by success rate using fragment as guidance (n=30)
25

---

Under review as a conference paper at ICLR 2021
Line
Operator
As Code
1
Make 2D Arra
2DAmrayssice-vvarillee(()))) v
2
Literal
3
Literal
variables[4] 2;
4
Divide
variables[5] = v
5
Loop
for (untroooce7iiiunnaeeeeoeooauuass
6
Loop
for ounanalleeey.yaaaaleeeeyyyyoueed
7
Subtract
variables[8] = variiablss())
8
Divide
variables[8] = v
Subtract
variables{8| = variables variables[3]:
10
Add
variables[9] = variables variables[7]]:
11
Condition
if (variablcs(9]>00)
12
Subtract
variables[9]] = variables variables[8];
13
Condition
if (variables(9)>>))
14
Subtract
variables[9] variables(0) variables(8]:
15
Subtract
variables[9] - (aariablss9]-vvaiibbees222
16
Condition
if (variablex(9)>-)
17
Write to 2D
array araayyvarbbles///vrbbble/1///
18
Endloop
19
Endloop
20
Endloop
21
Endloop
22
Endloop
Fragment
Success Rate
2
10%
2,3 3
10%
2,5
10%
3 3%
3.4
0%
3,5
10%
5
3%
Table 23: Fragments assessed from program "Trapezoid". Program's code listed, in C-like for- mat, with operators listed ahead of each line for each of readability. Fragments then described, in reference to lines used followed by success rate using fragment as GP guidance (n=30)
26

---

Under review as a conference paper at ICLR 2021
Fragment
Description
Add
Simple addition. Requires the program to at some point contain addition operation
+1 Offset Loop
Three Line Fragment
The first sets Varl to
The second is loop operator
The third requires an addition operator such that Var2 hoop_iterator + Varl
Length Loop
Three Line Fragment
The first sets V arrl to
The second requires an addition operator such that Sarrvullrrrraaaa _iize-seeeeeee Varl
Var2
The third is loop operator bounded to Var2
Literal (2)
Requires a variable be Requires the program to contain a loop Two line fragment. The first line requires loop The second line requires a conditional (var >> 0) Two line fragment. The first line requires loop The second line requires a read operation such that the index read the loop's s iterator One line fragment. Requires the output array to be created, with a size Varl such that Van 1 is not the variable defaulting to input array size Requires the program to read from the input array Simple subtraction. Requires the program to some point contain subtract operation
2
Loop
Loop Conditional
Loop Read
Nonstandard Array
Read Add
Table 24: Fragments used in experiment 2, corpus 1, to determine whether the NN can recognise their presence in program's source code based its behaviour. If multiple lines required they are required to exist in order, but not necessarily consecutively. Variable numbering is not reflective of source-code implementation and for descriptive purposes only.
27

---

Under review as a conference paper at ICLR 2021
Fragment
Description
Add
Simple addition. Requires the program some point contain an addition operation
Conditional
Greater than operator. The program must contain an operator which executes non-empty code block if a variable is greater than zero Two line fragment. The first sets variable Varl to the literal 2, The second assigns variable to sessired_onpuul_siiaa /arl Three line fragment. The first sets a variable Varl to the literal 2, The second assigns variable V arr to desired The third defines loop operator which runs from 0 to Var2 Four line fragment. The first sets variable Varl to the literal 2, The second assigns a variable Var2 to desired perrreddoopuuu...e _izuttssieeeeee size/Vari /Varl The third defines loop operator which from 0 to Var2 The fourth defines an operation setting value on the 2D canvas, with the requirement that the X position of the point be logically dependent on the loop iterator
Half
Half Loop
arrl
Half Loop Depends
Loop Conditional
Two line fragment. The first requires a loop operator
The second requires conditional (var >> 0) operator
Loop Draw
Two line fragment. The first requires a loop operator
The second requires 2D array write operation in which the X position drawn to depends logically on the loop's iterator
Loop Loop
Two line fragment. The program must have two loops (not necessarily nested)
Loop Loop Subtract
Three line fragment. The program must have two loops (not necessarily nested)
It must then have subtract operator
Draw Draw
Two line fragment. The program must have two draw-to-2D-array operators
Fragments used in experiment 2, corpus 2, determine whether the NN recognise their presence a program's 's source code based on its behaviour. multiple lines are required they required to exist in order, but necessarily consecutively. Variable numbering is not reflective of source-code implementation and for descriptive purposes only.
Table 25:
28

---

Under review as a conference paper at ICLR 2021
Problem
Success Rate
Baseline
Abs
73%
7%
ArrayLength
100%
100%
ArrayToZero ToZero
100%
100%
CumulativeAbsoluteSSui
0%
0%
CumulativeSum
33%
3%
DivergentSequence
63%
57%
FinstElementOnly
100%
27%
Identity
100%
100%
IndexParity
100%
100%
IteratieeDiferrncce
3%
3%
KeepEvens
0%
0%
KeepNegatives
27%
0%
KeepOdds
10%
0%
KeepPositives
47%
60%
Negative
67%
67%
Pop
100%
30%
ConoveFirstElenmee
83%
10%
RetainFirstHalf
0%
0%
Reverse
77%
57%
ShiftLeft
80%
10%
ShiftLeefiZeroPaddeed
83%
40%
ShiftRight
17%
0%%
ShiftRightl
77%
83%
ShuffleZerosT
80%
100%
Signum
10%
0%
Sort
3%
0%
Square Values
77%
70%
Tolterator
100%
100%
Add
37%
23%
Append
47%
0%
ClipToMax
43%
17%
ClipToMin
70%
3%
ConstantAddittin
7%
0%
FillAray
100%
100%
GreaterThan
23%
10%
Fromate
100%
97%
LessThan
17%
7%
MultiplesOf
87%
90%
Multiply
30%
20%
Subtract
43%
17%
Table 26: Success rates for problems of the 1st corpus, using the rarest-first guidance strategy, with the aggregate estimates from the feed-forward architecture network (n=30)
29

---

Under review as a conference paper at ICLR 2021
Problem
Success Rate
Baseline
Abs
27%
7%
ArrayLength
100%
100%
ArrayToZero ToZero
100%
100%
CumulativeAbsollutSSSi
0%
0%
CumulativeSum
20%
3%
DivergentSequence
83%
57%
FinstElementOnly
83%
27%
Identity
100%
100%
IndexParity
100%
100%
IteratieeDiffrencce
0%
3%
KeepEvens
0%
0%
KeepNegatives
53%
0%
KeepOdds
10%
0%
KeepPositives
40%
60%
Negative
63%
67%
Pop
73%
30%
ConoveFirstElenmee
57%
10%
RetainFirstHalf
0%
0%
Reverse
53%
57%
ShiftLeft
43%
10%
ShiftLeefiZeroPaddded
63%
40%
ShiftRight
0%
0%%
ShiftRightl
53%
83%
ShuffleZerosToBaa..e
77%
100%
Signum
10%
0%
Sort
0%
0%
Square Values
77%
70%
Tolterator
100%
100%
Add
23%
23%
Append
7%
0%%
ClipToMax
33%
17%
ClipToMin
20%
3%
ConstantAddittin
3%
0%
FillAray
100%
100%
GreaterThan
13%
10%
Fromate
97%
97%
LessThan
30%
7%
MultiplesOf
93%
90%
Multiply
30%
20%
Subtract
17%
17%
Table 27: Success rates for problems the 1st corpus, using the uniform guidance strategy, with the aggregate estimates from the feed-forward architecture network (n=30)
30

---

Under review as a conference paper at ICLR 2021
Square
90%
97%
HollowSquare
100%
100%
Parallelogram
23%
0%
PallowParallehogram
7%
0%
MirrorePParallelogran
43%
7%
MirroredHollow Paralleoowaa
17%
13%
RighTTriangle
93%
97%
Hollow RightTrangge
97%
87%
MirroredRightTrian
50%
60%
Horlo
60%
63%
InveraeeRigh/Trranglc
67%
60%
MolloowInvertedRiin Triangle
57%
83%
InvertedMiirroeeRRiggh Triangle
97%
100%
wwweeeddoooooooWWoeeeeeeeeeddd Triangle
100%
100%
siceleseTrrinnle
10%
0%
Hollow|socelese /ooeleseeTriangl Triangle
43%
13%
Invertedlsocelese Triangle
Trianng
37%
47%
33%
50%
Rectangle With Trapezoid
3%
3%
enctale
10%
3%
obtuse Triangle
23%
3%
hollowObbuseTrinngg
53%
27%
mirroredObuuseTTriaaa
0%
0%
microredHollowOOtuue//iiiie
0%
0%
inveried@Obuuse/Tiinnge
0%
0%
hollow Triangle
17%
10%
invertedMirorreddhhuusseii
7%
0%
7%
3%
VShape Trapezoid
40%
47%
0%
7%
Table 28: Success rates for problems of the 2nd corpus, using the uniform guidance strategy, with the aggregate estimates from the convolutional architecture network (n=30)
31


Reviews:
[{"review_id": "tfHYyEJBtKh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main idea of the paper is using neural networks to provide \"starting hints\" to a program synthesizer that is based on genetic programming. Specifically, the network predicts one or two lines that must be present in the desired program given the I/O examples for the task. These lines are used to initialize the GP process instead of an empty program.\n\nThe core idea resembles DeepCoder, with two (important) differences: (a) the network predicts a code fragment of 1-2 lines instead of a distribution over operators, (b) the subsequent synthesis algorithm is a GP process rather than symbolic search. However, there's no comparison with the DeepCoder approach, either on this paper's DSL/dataset, or on DeepCoder's. I appreciate the authors' argument that the two DSLs significantly differ in expressiveness. However, most programs in this dataset have <10 lines, and comparison with enumerative or neural-guided synthesis approaches would be both feasible and informative for them.\n\nIn fact, the only baseline comparison is with vanilla GP. As such, the paper is definitely valuable for the GP program synthesis community, but less valuable to the ICLR neural program synthesis community at large.\nI also some questions regarding the validity of experimental setup and suggestions on the presentation clarity (see below). All of these prevent me from raising the score above acceptance at this time even though I find the main idea promising and the end-to-end evaluation results impressive.\n\n### Evaluation questions\n\nThe experimental setup is a bit unorthodox. The authors present individual components of their approach simultaneously as both (a) ablation experiments and (b) stages of their end-to-end pipeline. According to this presentation, the end-to-end pipeline operates as follows:\n1. Start with a subset of easy tasks. Identify 10 best code fragments that, if provided, increase the find rate of GP (via brute force enumeration of all fragments).\n2. Generate a synthetic train/test set for the classification problem \"IO -> Fragment Presence\" for each fragment.\n3. Train a classification NN for each fragment.\n4. For all tasks (including the ones from step 1), use the trained NNs to select the code fragments to provide as hints to GP. Measure the find rate of GP.\n\nThe pipeline view would be better appreciated in the beginning of Section 3, as a high-level overview of the whole system. Without it, different experiments now clearly map to different research questions:\n- Experiment 3 is the \"main\" end-to-end performance/generalization evaluation.\n- Experiment 1 is the \"oracle\" version of it where the fragment prediction component is replaced by brute-force enumeration of all valid fragments from ground truth (\"How good we could possibly get?\").\n- Experiment 2 is the evaluation of classification accuracy of that individual component.\n\nAfter this perspective on evaluation is better established, two questions arise.\n\nFirst, the inclusion of Experiment 1 tasks into the final measurement is odd - they are indirectly part of the \"training\" data in this setup because they influence the selection of useful fragments. It's unclear which of the newly-solved problems are \"training\" and which are \"testing\" without inspecting Tables 26-27 line-by-line. If Experiment 3 did not involve any tasks from Experiment 1, the new average find rate would better inform the reader how the hint fragments - and the approach as a whole - generalizes across tasks. Which is the main goal of this end-to-end experiment.\n\nSecond, when comparing Tables 26-27 in the appendix with the corresponding \"oracle\" numbers in Table 1, I get confused. For example, the Append task reaches a maximum of 27% find rate for the best-performing fragment in Table 1. However, the paper's approach predicts a fragment that facilitates a find rate of 47%. If Experiment 1 evaluated every possible valid fragment from the ground truth program, how could the approach find a fragment that's better than the best one? I'm probably misunderstanding something in the experimental setup.\n\n### Presentation questions\n\nIn addition to Section 4 advice above, I suggest restructuring the technical sections of the paper (i) from high-level to low-level, (ii) with motivating examples, (iii) with a system overview figure in the beginning. As written, Section 3 presents a lot of technical detail and high-level motivations are hard to notice and appreciate until one reads the entire paper.\nIn contrast, So & Oh, whose tasks the authors re-use in this work, start with task/program examples and give a much more formal presentation of the entire synthesis system.\n\nSections 3.2-3.3 are quite dense. They describe almost the entire system in prose, with quite a bit of technical detail. Instead, this section would benefit from presenting it as two algorithms in pseudocode - one for the GP synthesis and one for the end-to-end system for training NN for fragment classification and using its predictions to drive GP.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "objH7qR4dVP", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a genetic programming approach for programming-by-example systems, where the genetic search is seeded with fragments that are predicted by a neural network to be relevant to the input-output examples. This is shown to solve more synthesis problems compared to un-aided genetic programming for array-to-array programs and canvas drawing programs.\n\nThe neural network is a classifier that given a set of input-output examples and a program fragment predicts whether the fragment could occur in the solution to the synthesis problem. The fragments above a threshold are used for seeding the genetic search and candidates that do not include them are penalized during the search. An initial genetic search is performed on simpler problems to prepare the training set for the classifier. I found the description of the process for generating the training set quite vague. From what I understand, the useful fragments from candidates generated during the initial genetic search are identified manually and then it is augmented with a further set of manually chosen fragment. Some noisy fragments are then added randomly to prepare negative examples. The extent of the manual efforts here is substantial and requires domain knowledge from the developer. In contrast, many neural models for synthesis work entirely off of randomly sampled programs.\n\nThe experimentation is not explained clearly. The term \"find rates\" is used without defining. It appears from Table 1 that it is some way of measuring the success of genetic search (but what and how it computed is not clear). In Section 4.2, it is said that \"all programs with a 90% find rate or better ...\" are used. What is the find rate of a program and how does it relate to the find rate of the search procedures?\n\nExperiment 3 shows the benefits of using the classifier to seed the search. What is the relation between the problems whose fragments are used for training the classifier and the problems used in this experiment? Is the former a subset of the latter?\n\nFrom the applicability point of view, what is the time take by a successful genetic search across the problems? The rarest preferred fragment assumes existence of other problems to rank order the fragments. This is an impractical requirement to the user, who would be interested in only her problem and cannot be expected to supply related problems for ranking purposes.\n\nFrom the point of view of baselines, there are two types of baselines missing. One is a neural method for straightforward program generation from examples; any suitable one from the cited papers can be used. Another is a non-neural selection method for fragments; a simple mining method can be applied to the data from the correct programs from the initial genetic search. These will help properly understand the benefits of the respective contributions.\n\nPlease label the sub-tables in Table 1 and 2. Can you spell out how the distance D for identifying repulsors is computed, for instance, if some edit distance is used then which one?", "extra_scores": {}, "extra_text": {}}, {"review_id": "FF-xHUMXyk4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis work considers training neural networks to provide \"hints\" (suggested lines of code) as a way of augmenting genetic programming systems. At test time, a neural network conditions on input-output examples and learns to predict 1-2 lines of code which are present in a program satisfying those input-outputs. At train time, the system learns in a self supervised manner by bootstrapping off previously discovered programs, augmenting them to produce a large corpus of similar problems, and then training the network to predict lines of code present in this augmented data set, similar to DeepCoder.\n\nOverall the method is sound, but I have two objections which caused me to lean toward reject:\n\n+ First, the experiments seem small-scale, and even on these small domains the absolute performance gain is modest (for one-dimensional array manipulation, their method solves 55% vs 38% with vanilla genetic programming, as measured on 40 synthesis problems). This is at odds with the claim that the \"approache is scalable to the search space of Turing-complete languages\" - why not try on a standard benchmark, such as SyGuS? The promise of the proposed method hinges on its raw performance as well as its general applicability, and at present the experiments do not highlight these two factors.\n+ Second, there is prior work on using deep learning to accelerate stochastic search over program spaces, indeed even over spaces as rich as arbitrary assembly code, e.g. \"Learning to superoptimize programs\" (ICLR 2017). How does your method compare? This prior work showed compelling results on a challenging standard benchmark - can your method do the same?\n\nTo be clear, not every paper has to beat standard benchmarks --- new good ideas that are carefully investigated are also good, and Experiments 1-2 do a great job of showing experimentally the different elements of the approach in action. But there is enough existing work (see \"missing citations\") in the conceptual neighborhood of this submission that I really think they should compare on some standard-ish benchmarks, because the approach on its own seems too similar to prior works.\n\nminor concerns:\n- page 2: what do you mean by neural synthesis either drawing from the target language by \"sampling at a uniform interval or at random\"?\n- how sensitive is the performance of the algorithm to the small details of the genetic programming set up?\n\nmissing citations:\n- \"Learning to superoptimize programs\" (ICLR 2017 - see above)\n- \"Augmenting Genetic Algorithms with Deep Neural Networks for Exploring the Chemical Space\" (ICLR 2020)\n- \"Learning Fitness Functions for Genetic Algorithms\" (2019 - could this be combined synergistically with your work? where you learn the best fragments to include and they learn the fitness function?)\n- \"Write, Execute, Assess: program synthesis with a REPL\" (NeurIPS 2019 - can this also be combined, whereby a mutation policy and fitness value function are learned through RL?)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are some interesting ideas in this paper, but I agree with reviewers that without a comparison to existing work, it is hard to place this work in its proper context. The authors make several arguments in dismissing the need for side-by-side comparisons, but I do not find these arguments convincing. 
* First, the authors argue that there are no suitable benchmarks for them to compare, and that in particular SyGuS benchmarks would not be suitable because they are dealing with a different problem. I disagree. There are 2 tracks in SyGuS specifically for programming-by-example problems, one for string manipulations and one for bit-vector programs. I think the string manipulation problems would be a good match for this technique. 
* The authors also argue that their technique is so much more general than prior techniques that a side-by-side comparison would be unfair. However, their most complex benchmark, sorting, has been somewhat of a standard benchmark in the program synthesis community for about a decade now. And while a lot of recent synthesis work has focused on domain specific languages, many systems starting with Sketch and continuing with Myrth and Synquid were turning complete. Turing completeness can make a big difference if you are trying to synthesize verified code, but in the context of programming-by-example, turning completeness does not really present any fundamental challenges.

I am willing to believe that this technique is more scalable than existing techniques, so that while existing techniques may do better than this technique when synthesizing for small languages, this technique would surpass them when applied to a bigger language. But if that's the argument that the authors want to make I would like to see some evidence, and ideally some quantitative data as to how big a language would have to be before this technique wins out.
Decision: Reject