Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages
Authors: Xinyun Chen
Dawn Song
Yuandong Tian
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural program synthesis
program execution

Abstract: Program synthesis from input-output (IO) examples has been a long-standing challenge. While recent works demonstrated limited success on domain-specific languages (DSL), it remains highly challenging to apply them to real-world programming languages, such as C. Due to complicated syntax and token variation, there are three major challenges: (1) unlike many DSLs, programs in languages like C need to compile first and are not executed via interpreters; (2) the program search space grows exponentially when the syntax and semantics of the programming language become more complex; and (3) collecting a large-scale dataset of real-world programs is non-trivial. As a first step to address these challenges, we propose LaSynth and show its efficacy in a restricted-C domain (i.e., C code with tens of tokens, with sequential, branching, loop and simple arithmetic operations but no library call). More specifically, LaSynth learns the latent representation to approximate the execution of partially generated programs, even if they are incomplete in syntax (addressing (1)). The learned execution significantly improves the performance of next token prediction over existing approaches, facilitating search (addressing (2)). Finally, once trained with randomly generated ground-truth programs and their IO pairs, LaSynth can synthesize more concise programs that resemble human-written code. Furthermore, retraining our model with these synthesized programs yields better performance with fewer samples for both Karel and C program synthesis, indicating the promise of leveraging the learned program synthesizer to improve the dataset quality for input-output program synthesis (addressing (3)). When evaluating on whether the program execution outputs match the IO pairs, LaSynth achieves 55.2% accuracy on generating simple C code with tens of tokens including loops and branches, outperforming existing approaches without executors by around 20%.

Latent Execution for Neural Program Synthesis
Xinyun Chen
Dawn Song UC Berkeley dawnsong@cs berkeegeee..bbkkeee..........eee edu
Yuandong Tian Facebook Al Research yuandong@fb. com
UC Berkeley xinyun. chen@berkeley.co edu
Abstract
Program synthesis from input-output (IO) examples has been a long-standing challenge. While recent works demonstrated limited success on nomain-speciife languages (DSL), it remains highly challenging to apply them to real-world pro- gramming languages, such as C. Due to complicated syntax and token variation, there are three major challenges: (1) unlike many DSLs, programs in languages like C need to compile first and are not executed via interpreters; (2) the program search space grows exponentially when the syntax and semantics of the program- ming language become more complex; and (3) collecting a large-scale dataset real-world programs is non-trivial. As a first step address these challenges, we propose LaSynth and show its efficacy in a restricted-C C domain (i.e., code with tens of tokens, with sequential, branching, loop and simple arithmetic operations but no library call). More specifically, LaSynth learns the latent representation approximate the execution of partially generated programs, even if they are in- complete in syntax (addressing
(1)). The learned execution significantly improves the performance of next token prediction over existing approaches, facilitating search (addressing (2)). Finally, once trained with randomly generated ground- truth programs and their IO pairs, LaSynth can synthesize more concise programs that resemble human--witter code. Furthermore, retraining our model with these synthesized programs yields better performance with fewer samples for both Karel and C program synthesis, indicating the promise of leveraging the learned program synthesizer improve the dataset quality for input-output program synthesis (ad- dressing (3)). When evaluating on whether the program execution outputs match the IO pairs, LaSynth achieves 55.2% accuracy on generating simple code with tens of tokens including loops and branches, outperforming existing approaches without executors by around 20%.
1 Introduction
Program synthesis from input-output (IO) pairs, also called programming by example (PBE), requires high-level reasoning and remains challenging problem for deep models. Unlike Natural Language Processing (NLP) [5, 16) and perceptual tasks such as Computer Vision (CV) [14, 22], mapping from I0 pairs to the program itself is hard to model. Many works attempt learn direct mapping from training samples, but often found that generalization to new problems is even harder. Alternatively, synthesis as a search problem: to find the program that satisfies 10 pairs. Unfortunately. the search space of programs is often vast and highly non-smooth, i.c., small perturbation of the program often leads to a complete change of the output.
already difficult to achieve a low training error, and might choose formulate program
While there are many previous works on programming by example tasks [6, 17, 91, they mainly focus on Domain Specific Languages (DSLs), and cannot be easily applied to popular general-purpose programming languages. For example, to synthesize C programs, we need to deal with both high-level
The code is available httts:// http:///tuuu.ccoo///ggggg/////// http:////..ftlllaco/m/mmm/aaaaat
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

control flows (e.g., branching and loop) and low-level operations (e.g., which variable is the target of assignment). Moreover, unlike DSLs (e.g,, Karel) for which it is feasible to implement a per-line interpreter, C programs need compilation and a partial C program cannot execute. On the other hand, some recent works investigate natural language descriptions as the auxiliary information of the program specification, and they evaluate neural program synthesis models on constrained or simplified competitive programming problems [27, 3, 23, 11, 4]. Although some of these works demonstrate promising results for synthesizing Python or C code, they require manual annotations of natural language specifications [27] or large-scale pre-training on human--ritter programs [11, 4], and the performance significantly degrades when only input-output examples are fed into the synthesizer [3].
To synthesize C programs from input-output examples only, we propose LaSynth. which generates the program in a recurrent and token-by-tor by-token manner. As the first contribution on model architectures for program synthesis, we propose to use two latent parallel representations in the recurrent model. One representation is learned from regular recurrent models as in autoregressive language models [24], with the double attention mechanism over I0 pairs proposed in RobustFill [17] and an operation predictor that models the arithmetic relationship between the program input and output. The second representation, named Latent Execution Trace (LæET), models the hypothetical input signal for the remaining partial program to execute to get to the desired output. Motivated by the line of work on dxecution-guided program synthesis [47, 18, 57, 12], we learn a latent representation for C programs which not executed via interpreters, and train the model given only IO pairs without the intermediate program execution states. The two parallel representations are trained end-to-end.
As the second contribution on dataset construction, we demonstrate that it is possible to automatically construct C codebase that is of high quality, controllable and concise through our proposed program synthesis procedure. Specifically, starting from randomly generated C programs that might contain a lot of redundant statements, we show that via iterative retraining, the subsequent generated code from our learned model becomes more concise and similar to human-written ones. Moreover, learning directly from the generated code leads to better performance given the same amount of samples, and improves the sample efficiency. We observe similar results when applying our iterative retraining technique to Karel [9], another programming by example benchmark consisting of randomly generated programs. Although the initial Karel dataset includes large proportion of complicated programs with different control flow constructs, we demonstrate that nearly half of the problems can be solved by straight-line programs, which again confirms that randomly generated programs tend to be unnecessarily complicated. We envision that the iterative retraining procedure could greatly reduce laborious efforts in human codebase collection in future research.
As the third contribution, we show for the first time that short C code in a restricted domain (tens of tokens, no library call) with sequential, branching. loop and simple arithmetic operations can be effectively synthesized from 10 pairs only. In particular, while LaSynth tends to generate more concise programs (and does not have exact token match with random generated ground truth code), when measuring whether the program exccution outputs match the 10 pairs, LaSynth achieves 55.2% accuracy, and outperforms existing neural program synthesis models by around 20%. These results demonstrate the effectiveness of learning latent execution traces.
2 Neural Program Synthesis from Input-Output Examples
In programming by example tasks, the program specification is set of input-outpur examples [17, 9]. Specifically, we provide the synthesizer with set of K input-output pairs {(1(4) O(+)) (110)k in short). These onput-output pairs annotated with ground truth program P that P* (*))()))=
(() for any k E 21. K}. To measure the program correctness, we include another set of held- out test cases {IO) Kiest Jest" that differs from [10]*. The goal of the program synthesizer is predict
Keert a program P from {10}K, so that P(I) = (1) = O for any (1, (10}* + [10] (tsst
C Program Synthesis. In this work, we make the first attempt of synthesizing C code in a restricted domain from outptt examples only, and we focus programs for list processing. List processing tasks have been studied in some prior works on input-output program synthesis, but they synthesize programs in restricted domain-specifie languages instead of full-fledged popular programming languages [6. 39, 38).
Our C code synthesis problem brings new challenges for programming by example. Compared to domain- sppeiif languages, the syntax and semantics of C are much more complicated, which signifi- cantly enlarges the program search space. Mcanwhile, learning good representations for partially
2

---

finc
Random Input Generator
Random Program
1.7
1.8
int runc Cunc__(iint afl)
1:
1-4,
3, 2
at1.7] afp.03;
1,84
01:1-4,
p.o
B.
wEI_04]
D 1,
(p_0
<e PLDH1)
12.
1. 4,
Soz (p.0
4; p.0 >0 2: p.0-)
3.
Program 9ynthesizer
4, 1,11
=[p_0]
4,
a(p_0)
Figure Illustration of the program synthesis pipeline. For dataset construction, develop a random program generator to sample random C programs, then execute the program over randomly generated inputs and obtain the outputs. The input-oulput pairs are fed into the neural program synthesizer to predict the programs. Note that the synthesized program can be more concise than the original random program.
(a) Model Overview
Program Decoder
Program Context
Pt-1
Pt
Pc+1
Por Pb
Pt-1
Program Decodler
Program Decoder
h
LSTM
ftg
Softmax
R
hgg
h++1
Latent Execuioor
Latent Ewecutor
le+1
10
Pool
67:
(c) Latent Executor
(d)
Operation Predictor
h
O
Op
Training
2
4
O=2+1
Target
EXEC,
2
0
O=2-1
Retrieve
76-1
LSTM
Saftmax
(K))
op.
Figure 2: (a) An overview of LaSynth model architecture. (b), (c), and (d) present the details of the program decoder, latent executor, and the operation predictor. Note that the operation predictor specialized for numerical calculation, and thus is not used for the Karel domain.
decoded programs also becomes more difficult. particular, prior neural program synthesizers that utilize per-line interpreters for the programming language to guide the synthesis and representation learning [12, 44, 37, 18, 38) are not directly applicable to C. Although intermediate variable states during C code execution [10], since partial C programs are not executable, we are able to obtain all the execution states only until a full C code is generated, which is too late to include them in the program decoding process. In particular, the intermediate execution state is not available when the partial program syntactically invalid, and this happens more frequently for due to its syntax design.
possible to dump some
3 Program Synthesis with Learned Execution
In this section, present LaSynth which learns represent the execution of partial programs guide the synthesis process. Fig. 2(a) provides an overview of LaSynth model architecture which consists two components, the program decoder and the latent executor. We present the core design below, and defer more details to Appendix B and Appendix C.
3.1 Model Overview
At a high level, the program decoder (Fig. 2(b)) takes a latent vector f that represents the generated partial program, the previous (generated) program token Pt-1, and outputs the latent vector h and the next program token Pt to be generated at time step t:
(he. Pt) Program DrngrramDeodder/h-1ii....
Here the recurrent model is conditioned on the IO pair IO,-1- When 10, = 10 == (I,O) for every I, i.e., 1O; remains constant over the entire recurrent generation process, Eqn. represents the standard recurrent architecture used most autoregressive natural language models [24, 49], and also used in prior works program synthesis from input-output examples [17, 9].

---

For program decoding, the decoder first takes two attention vectors of and do computed from 10 pairs and latent vector h via double attention [17], and utilizes max pooling layer compute an aggregated embedding m, for all IO pairs (Fig. 2(b)):
m = e1 (tanh(W (1, (()
(2) Here the superscript (j) indicates that the representation is for the j-th IO pair, (a; b] is vector concatenation of and b, and W is trainable matrix. To facilitate the prediction of long programs, we compute an attention vector d, over previously generated program tokens using the standard attention mechanism [5, 30]:
de Attention(mm: (po. (P0....,,P..........
(3)
Finally, the next token pr is sampled from P(pr] Softmax(Vd (Vee) where V is trainable matrix.
3.2 Latent Executor Design
As shown in our experiments (Sec. 5), the standard program decoder architecture may not be able to achieve strong performance in program synthesis when the program complexity increases. One main reason is that the standard program decoder only takes the initial IO pairs as the input without considering the program execution, thus the learned representation for the partial program does not effectively guide the synthesis process. Motivated by prior works that utilize execution traces for Karel program synthesis [12, 44, 47], in this paper, introduce latent executor (Fig. 2(c)) which maintains second representation I, during program decoding. Intuitively, f, models the hypothetical impul of the partial program Pt...T so that its output becomes O. Given the estimated input f and the latent vector he, the latent executor returns I, at the next time step t:
i, Latent Executor(f-11,,
(4)
The collection of {feTT is the latent execution trace (LaET). With the help of latent executor, we now use the 10 pairs 10,-1 == (f,11, 0) instead of (I, O) for the program decoder (Eqn. 1).
3.3 End-to-end Training We train our model with supervised learning, by minimizing the sum of token prediction loss Proog- and the latent executor loss LE
C= + L
(5)
Specifically, Prog == Ei= (oss(p:, pī) is the step-by-step cross-entropy loss between the pre- dicted programs Pı..r and the ground truth programs pi....-
For latent executor, since the semantics of partial programs (e.g.. partial C programs) are not always well-defined, there is no step-by step-by-ster by-step training supervision. However, the output of the executor should be consistent with the program specification after taking the annotated ground truth program as the input. Therefore, we set lo = (true input) and minimize the distance between Ir and O (true output) after the program finishes:
LE Loss(Er, 0)
(6)
Note that LEzee does not rely on any assumptions of the partial program semantics, and thus is applicable to both domain specific languages and general-purpose programming languages such as C. In our evaluation, equipping with the latent executor significantly improves the program prediction performance, where each program could include up to 256 tokens.
3.4 Data Regeneration and Iterative Retraining
Interestingly, once our model is trained on the initial random generated programs Dp. the predicted program becomes more concise and resembles human-writ wnitten code. While the exact token match accuracy is low even on the training set, the model still satisfies the 10 pairs for many problems. We leverage such phenomenon to construct a new dataset D2 with higher-quality programs from Dg- Specifically, we run beam search the trained model to predict program Po..T given input-output pairs the training set. If model prediction Po...r satisfies the input-output examples and held-out cases, replace the original program Ph...T with Po... in Dj, and keep Pi... otherwise. Afterward, we re- re-train the model on Dj. In Sec. 5, we will demonstrate that the retraining process further improves the model performance, especially with smaller training datasets.

---

Table 1: The comparison between our restricted C domain and existing programming by example tasks.
Control flow
Variables
Arithmetics
No helper functions
Restricted C (Ours)
Karel [9]
DeepCoder [6]
FlashFill [19]
4 Restricted C Program Synthesis Domain
In this section, we discuss our restricted C program synthesis domain, and our operation predictor design for improving the numerical reasoning ability of program synthesis models.
4.1 Data Generation
Collecting large-scale high-quality datasets for program synthesis requires a lot of human efforts, and we aim reduce the manual work for dataset construction.
Our data generator is built upon Csmith [54], a random code generation tool originally designed for finding bugs in compilers. Following the common practice of generating input-output pairs, for each program, we randomly sample 5 numerical lists as the program inputs, and execute the program to obtain the corresponding output lists. This is similar to existing works on PBE problems that sample programs based on probabilistic context-free grammar, randomly generate valid inputs for the programs and obtain the outputs [40, 15, 6]. This creates infinite samples for synthesizing programs in Nomain-specifee languages. While the programs sampled in this way differ from human- written code, Sec. 3.4 shows that they can be converted be more concise and human-like like.
The subset of language features used. Our generated program has variable declaration, variable assignment, and expressions with addition or subtraction operations. The programs also have non- sequential statements, including If statements, For loops, Continus and Break statements. Except for the input argument which list, all variables declared are integers, and all program statements are integer manipulation. Each expression has at most 2 mathematical operations, and chaining the full C program could perform multi-step numerical calculation (e.g.. pO pO p1 p2; p0 po 1;). Looping statements other than For (i.e., While or Do-While loops) are not supported. Note that we only constrain the final program length (S 256 tokens) and the program can have nested for-loops and complicated if-conditions.
Post-processing. We perform few post-processing steps obtain our final programs from programs generated by Csmith (see Fig. for an example). We resample different components of the program, that (1) each constant numerical value lies in [-4, 4), (2) mathematical operators only contain addition and subtraction, and (3) upper/lower limits of For loops are positive and within the length of the list. Programs are discarded if they are trivial (e.g., constant or identity mappings), or the input-output examples include values out of the range [-4,
Final dataset. We reweight the program distribution that at least half of them include For loops. Our full dataset includes 500K samples in the training set, 1K samples in the validation set, and 1K samples in the test set. As shown in Fig. 1, the randomly sampled program may contain redundant statements, which can be easily avoided by human programmers. We compare our restricted C domain to prior datasets of programming by example in Table 1.
4.2 Program Decoding with the Operation Predictor
For program decoder, predicting the next program token p. is non-trivial, especially when mathe- matical reasoning is required [43, 29]. To improve the program synthesis performance for domains involving numerical calculation, such as our restricted C domain, we design an associative memory structure named operation predictor (Fig. 2(d)), based on the following intuition: given the input I = 2 and output O 4. human would infer that "O /+ 2" might be the desired operation and write down the code accordingly.
materialize such an intuition, we create a pre-computed table that covers all possible integer addition and subtraction operations for valid input and output list values. We defer the details of the model architecture to Appendix B.2. The program decoding process remains similar to the one described in Sec. 3, and we highlight the key differences follows.
5

---

Table 2: comparison between LaSynth and baseline neural program synthesis models in our evaluation.
Exec
Shin et al.
Bunel et al.
RobustFill
Property Signatures
LaSynth
[12]
[44]
[9]
[17]
[39]
Program execution No interpreter needed
/
>
The operation predictor takes two attention vectors sf and s as the representations of input-output examples, and yields operator embedding op,- To compute the aggregated embedding vector for all onput-output examples, we modify Eqn. 2 to also take op, as an input the max pooling layer:
m MaxPoolje (1.2.....k) (W 16); ;s
00), op!
To train the operation predictor, we add additional loss Lop:
L = Prog + Ezeec + Lop
(8)
Cop is designed ensure that the operation predictor predicts operations related IO pairs, and we defer the details to Appendix B.2.
Limitations. In our current implementation of the operation predictor, the operation table is only able to enumerate the arithmetic operations over pre-defined constant set, thus it requires that the set of possible numerical values in input-output pairs is finite. One way of extending our operation predictor to support potentially unbounded numerical calculation is to combine with the subword tokenizer, which has been commonly used in recent language models [16, 11, 4]. We consider designing general-purpos. number representation for better mathematical reasoning as future work.
5 Experiments
In this section, we discuss our results on synthesizing programs in Karel and C languages. We first show that LaSynth achieves competitive performance on Karel benchmark. Then we present the results on our restricted C benchmark, and demonstrate that our approach significantly outperforms existing neural program synthesis models. Finally, we discuss the effect of iterative retraining.
5.1
Karel Program Synthesis
5.1.1
Evaluation Setup
Karel domain. Karel an educational programming language [41], and has been studied recent works on neural program synthesis from input-output examples [15, 9, 12, 44). A Karel program controls a robot in 2D grid world. There are instructions that control the robot, e.g., move, turnLeft and PutMarker, as well as conditionals and loops, i.c., if, repeat and while. See Appendix A for grammar specification and the state representation.
We train and evaluate all models on the Karel dataset introduced in [9]. The dataset contains randomly sampled programs from the Karel DSL (1.1M training samples, 2.5K samples in the validation set and 2.5K samples in the test set). Each program includes 5 input-ouiput pairs as the specification, and the sixth pair as the held-out test case. Following the prior work, we evaluate two metrics: (1) Exact Match: the predicted program is the same the ground truth; (2) Generalization: the predicted program satisfies both the input-output pairs and the held-out input-output test case.
Baselines. Bunel et al. [9] designed the first program synthesis model for the Karel benchmark with a similar high-level design as RobustFill, but they use convolutional neural networks (CNN) encode the Karel grid maps. Compared to LaSynth, this model does not utilize any program execution information, and does not include our latent executor. Instead of directly synthesizing the program from input-output examples, the model in Shin et al. [44] first predicts the execution traces containing the robot actions from the input-output pairs, then decodes the program based on the execution traces. This model improves the prediction performance over Bunel et al., but it requires the full execution traces for model training and an interpreter for execution. Exec [12] leverages the execution states of partial generated programs to guide the subsequent synthesis process, but the execution states are obtained from the Karel interpreter rather than learned by the model, thus this approach represents the ideal scenario where the partial programs could be executable.

---

90.0
87.5
Generalizatiinn accuracy
85.0
82.5
Table 3: Results on Karel dataset. Gen and Exact
80.0
denote generalization and exact match accuracies.
77.5
Approach
Gen
Exact
75.0
Random
Retrain-1
LaSynth
83.68%
41.12%
Retrain-2
Exec [12]
86.04%
39.40%
Bunel et al. [9]
77.12%
32.17%
Proportion of training data
Shin et al. [44]
81.30%
42.80%
Figure 3: Generalization accuracies with different train- ing data sizes on Karel. With accuracies are 86.04%, 89 28% and 89.36% for train- ing random programs, retraining for I and iterations.
training set, the
60.79
Randam R Pacrran
60.25
8
Percertage (%)
Percentage
24
35.0
18.05
16:30
20
22-72
20-
10
12:42
4:20
8.08
Program ony
(US, Program token
(a)
(b)
Figure 4: Program distributions after iterative retraining on Karcl. (a) The distributions of different program types. Seq-only: control flows. If-oyly: the program includes If statements but loops. Repeat/While- the program includes Repeat/While loops, but no other control flow constructs. Mixture: program includes least two types control flow constructs. (b) The distributions programs with different token lengths.
Our model architecture for Karel is largely similar to the model for C code synthesis, except that we employ the CNN encoder in Bunel et al. [9] in our program decoder and latent executor. The comparison with baseline models is shown in the middle block of Table 2. All models use the beam search for decoding programs, with the beam size 64.
5.1.2 Results
We present the results of LaSynth and baseline model architectures in Table First, LaSynth outperforms all baselines that do not incorporate the partial program execution information, and achieves competitive performance compared with the Exec algorithm that requires an interpreter to obtain the partial program execution states. In particular, LaSynth achieves higher generalization accuracy than Shin et al. with lower exact match accuracy, showing that decoded programs by LaSynth are more different from randomly generated programs. Although Shin et al. also model the program execution by predicting the robot actions, the prediction of the action traces does not take the program structure into account, resulting in the inferior performance.
5.2
C Code Synthesis
5.2.1
Evaluation Setup
Given the variety of C programs, we observe that the exact match accuracies models are mostly nearly 0. Therefore, we focus on evaluating the generalization accuracy, and we consider the predicted program be correct when it satisfies both the input-output examples and 5 held-out test cases.
Baselines. We compare the full LaSynth with its multiple ablated versions:
NoExecutor. The program decoder (Eqn. 1) always takes the initial input-output pairs as the input; i.c.. I, Ln for every t.
7

---

int runc_ (int a[]
{
int func_ (iint a03)
int p_o 0;
int 1_7 3;
int Tunc_1 1 (int aO)
int 1_8 1;
int = 2:
a[_8]] [a[1_7] a(p_0]);
int p_0 0;
int 1.12 3;;
for (p_0 3; p_0 <- 4; p_0ne)
(p_0 p_o 2; p_0++)
int 1.25 4;
a[p_0] 1;
for (int p.1 1: p_1 2; p_1+.)
a[p_0]--;
--a --a[1_26];
return }
a[1_12]
a[p_1] a[p_1] a[pp.0;; a alp_1] +
return
return a;
Sample programs that could be correctly predicted by LaSynth, but wrongly predicted by models without the latent exccutor. These programs require multiple different operations for different input list elements.
Figure 5:
NoPartialExecutor. i, = In / for every l and additionally hr is regularized so that Latent Executooe)) hyr) matches the output O under loss L Therefore, no partial latent execution.
NoOpPredictor The max pooling layer only takes the vectors computed by the double attention as the input (Eqn. 2).
NoAttention InDecodin. There is no attention over decoded program tokens, and the output of the max pooling layer directly fed into the output softmax layer; i.e., P(pe] Softmax(V Mm)p,. (compared to Eqn. 3).
We also compare with existing neural program synthesis models with good performance on related tasks, as shown in the rightmost block of Table 2. RobustFill [17] is the state-of-the-art neural network architecture domain-speciff language. As described in Sec. 3, the input-output encoder and the program decoder architectures RobustFill are similar LaSynth, except that does not include the latent executor, operation predictor, and the attention on the decoded program sequence.
FlashFill benchmark, which synthesizes string manipulation programs in
Property Signatures [39] was designed for synthesizing list manipulation programs in domain-specific languages, but instead of taking the raw input and output lists as the neural network input, they design some properties that distinguish different programs, then take the values of these properties as the model input. A sample property could be whether the program output is the same as the input, and the property values could be "All True", "All False", "Mixed", indicating that the property always holds for any input-output pair in the specification, never holds, and holds for some pairs but not others. respectively. We customize the original design [39] for our setting. First, our property set takes the format of O = C I? and O = C - 1?, where C' E [-4,4] 4J. For example, O = + I? means whether the output O could be calculated by adding to the input L. These properties focus more on numerical calculation, similar to our operation predictor. Second, different from the task in [39], our C programs sometimes manipulate only subset of the input lists, thus encoding the list with single property value is inappropriate. Instead, we compute the property value per element in input-output pairs, use bi-directional LSTM to encode the property values as a sequence, then take the outputs of the bi-LSTM for program prediction.
5.2.2 Results
Table 4 presents the results, where all models are trained on the initial random programs. The full LaSynth outperforms other variants, and improves the performance of RobustFill and Property Signatures by around 20%. We also increase the model size of RobustFill to see if the improvement comes from larger model size, but the results are not better. In particular, the latent executor significantly increases the prediction accuracy, and achieves better results than which shows that learning latent execution traces leads to better partial program representations. In Fig. 5, we present sample programs that could be correctly synthesized by LaSynth, but models without the latent executor provide the wrong prediction. We observe that the latent executor is beneficial when the program involves different manipulations for different list elements, e.g., more than one For loop and different mathematical calculations. Our breakdown results on programs of different complexity also justify this observation. We first present the results on programs with different control flow constructs in Fig. 6. Specifically, Seq-only includes programs with no control
8

---

Lewethoo (Random))
Letentivee (Betrain
00.33
00.31
LatentEvec (hetrain 2]
Table 4: Results on C dataset.
Mabusont
8
Prsperty Signatures
Approach
Accuracy
8
LaSynth
55.2%
Recuran
41.50
NolttentionnnDecoodin
53.5%
8
30.00
39.2
12.85
NoOpPredictor
53.7%
29-15
NoPartialExecuton
42.9%
22.70
NoExecutor
38.6%
RobustFill [17]
37.6%
Program bype
Property Signatures [39]
34.5%
Figure 6: Accuracies of different program types on C dataset.
Rancom
42.75 42.50
Accuracy
Percentage
20-
Random Retrain-1
6:50
0.90
Retrain-2
10
0.1
0.2
0.3
0.4
0.5
1.0
Segunty
Forony
Manue
Proportion of training data
Program type
(a)
(b)
Figure 7: Results iterative retraining the C dataset. Accuracics with diffcrent training data sizes. With the full training set, the accuracies are 55.2%, 56.0% and 56.5% for training on random programs, retraining for and iterations, respectively. (b) The program distributions after each retraining iteration.
flow constructs, For-only includes programs with For loops but no If statements, and Mixture includes programs with both For loops and statements. Then we demonstrate the results on different program lengths in Fig. Sb. We show that LaSynth achieves decent performance long and complicated programs, while the accuracies baseline models drop dramatically.
5.3 Discussion of Iterative Retraining
In Fig. 3, we show the effectiveness of retraining on decoded Karel programs (Sec. 3.4). We observe that retraining for one iteration sufficient, and it significantly improves the generalization accuracy by over 3%. To understand the differences between predicted programs and randomly generated programs, we demonstrate the changes of dataset distributions after each retraining iteration in Fig. 4a and 4b. We observe that the model learns to predict more concise programs than the ground truth for a large proportion of input-output examples, and considerably alters the dataset distribution so that it becomes more concentrated on short programs with simplified control flow structures. Specifically, from Fig. 4a, although the initial Karel dataset seems to include large proportion of complicated programs with different control flow constructs, our model synthesizes straight-line programs for nearly half of the samples, which means that many loops and branches in the annotated ground truth programs are unnecessary. This distribution shift also explains match and generalization accuracies. The program distribution after the second retraining iteration is largely similar to the first iteration, thus retraining for more itcrations does not considcrably improve the performance. Note that in the second iteration, the synthesizer tends to generate slightly more complicated programs than the first iteration, in order to deal with the cases when the input-output examples oversimplify the intended program functionality. For example, sometimes the onput-output examples do not cover the edge cases that the robot may encounter, thus adding additional If branches could avoid the crashes when testing on held-out cases.
gap between exact
Fig. 7a presents the results of retraining on decoded C programs. Similarly, retraining improves the prediction accuracy, especially when the training set is small. From Fig. 7b and 8a, we again observe that the model tends to predict shorter programs than the random code, and eliminates unnecessary control flows to simplify the programs. We present more examples in Appendix D.

---

70.30
Rancom
54.07
Latentswoorer (Random))
Rersih
Litentbxecuor thet ai
R
LatentExecurr (Retriin 21
Percentage 19
51.19
8
0:30
10.09
Progerty Signatires
RobustFill
43.40
Macurecy
64.03
40
30-
70
22.60
22.66
10
5.00
5.00
20
34.
15.54
XXXXX00
>120
128)
Program taken length
Program taken length
(a)
(b)
Figure Results on programs of different token lengths on the dataset. (a) The program token length
distributions after each retraining iteration. (b) The accuracies on programs of different token lengths.
6 Related Work
Programming by example. Programming by example problems have been widely studied with various applications, and recent works have developed deep neural networks as program synthesiz- ers [20, 40, 17, 9]. Most prior works focus synthesizing programs in domain-specifi languages, such as FlashFill [40, 17, 51] for string transformation, Karel [9, 44, 12, 21] for simulated robot navigation, and LISP-style languages for list manipulation [6, 25, 57, 36). In this work, we make the first attempt of synthesizing C code in a restricted domain from input-output examples only, and we focus on the list manipulation domain.
Some recent works investigate the limitations of synthetic datasets and the ambiguity in program specifications for neural program synthesis [45, 13, 46, 28]. These works focus on reducing the bias of data distributions and generating more diverse input-output pairs, while our data regeneration aims to improve the quality of programs. We consider incorporating both lines of work to further improve the dataset quality as future work. In addition, drawing the inspiration from self-training and bootstrapping techniques developed for other applications [35, 1, 32, 52] to extend our iterative retraining scheme is also another future direction.
Execution-guided program synthesis. To learn better program representations, some recent works incorporate the execution information to guide the synthesis process [47, 57, 44, 12, 18, 48, 7, 21, 38, 37, 37]. In particular, leveraging partial program execution states improves the performance for several program synthesis tasks [12, 18, 37]. However, existing approaches rely on program interpreters to provide the intermediate execution results whenever applicable. In contrast, we demonstrate that our latent executor learns the latent execution traces (LaET) without such a requirement. Besides program synthesis, execution traces have also been utilized for other software engineering applications [2, 33).
Neural execution. Our latent executor related to prior works learning to execute algorithms [55, 50, 53] and programs [8]. They focus on predicting execution results for full algorithms and programs, but do utilize them for program synthesis. Latent state prediction has also been studied in other applications such as task-oriented dialogue systems [34, 56] and robotics [42].
Conclusion
In this work, we propose LaSynth, which learns the latent representation approximate the execution of partial programs, even if their semantics are not well-defined. We demonstrate the possibility of synthesizing elementary C code from input-output examples only, and leveraging learned execution significantly improves the prediction performance by around 20%. Meanwhile, compared to the randomly generated programs, LaSynth synthesizes more concise programs that resemble human- written code, and training on these synthesized programs further improves the prediction performance for both Karel and C' program synthesis. Our results indicate the promise of leveraging the learned program synthesizer to improve the dataset quality for programming by example tasks.
We consider extending our approach to synthesize more complicated real-world code as future work. For example, we will integrate our latent executor into large-scale pre-trained language models, which could further improve the performance of those program synthesis models taking natural language specifications. We will also study program synthesis problems with unbounded input ranges and different type signatures, which could be approached with the usage of subword tokenizers.
10

---

References
[1] Abney. Bootstrapping. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 360-367, 2002.
[2] M. Alam, J. Gottschlich, N. Tatbul, S. Turek, T. Mattson, and A. Muzahid. zero-positive learning approach for diagnosing software performance regressions. Advances in Neural Information Processing Systems, 32: 12211667-11639, 2019.
[3] Alet, J. Lopez-Contreeas, Koppel, M. Nye, Solar-Lezama, T. Lozzao-Perezz Kaelbling, and J. Tenenbaum. A large-scale benchmark for few-shot program induction and synthesis. In International Conference on Machine Learning, pages 175-186. PMLR, 2021.
[4] J. Austin, A. Odena, M. Nye, M. Bosma, H. Michalewski, D. Dohan, E. Jiang, C. Cai, M. Terry, Q Le, et al. Program synthesis with large language models. arXiv preprint vrXiv:2108.0777 2021.
[5] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
[6] M. Balog, L. Gaunt, M. Brockschmidt, S. Nowozin, and D. Tarlow. Deepcoder: Learning to
write programs. In International Conference on Learning Representations, 2017.
[7] M. Balog, R. Singh, P. Maniatis, and C. Sutton. Neural program synthesis with differentiable
fixer. arXiv preprint arXiv:2006. 2020.
[8] D. Bieber, C. Sutton, H. Larochelle, and D. Tarlow. Learning to execute programs with instruc- tion pointer attention graph neural networks. In Advances in Neural Information Processing Systems, 2020.
[9] R. Bunel, M. Hausknecht, J. Devlin, R. Singh, and P. Kohli. Leveraging grammar and rein- forcement learning for neural program synthesis. International Conference on Learning Representationss 2018.
[10] B. Campbell. An executable semantics for compcert c. In International Conference on Certified Programs and Proofs, pages 60-75. Springer, 2012.
[11] M. Chen, J. Tworek, H. Jun, Q. Yuan, H. Ponde, J. Kaplan, H. Edwards, Y. Burda, N. Joseph,
G. Brockman, et al. Evaluating large language models trained code. arXiv preprint 1rXiv:2107.03374, 2021.
[12] X. Chen, C. Liu, and D. Song. Exccution-guided neural program synthesis. In International Conference on Learning Representations, 2019.
[13] Clymo, H. Manukian, N. Fijalkow, Gaseón, and B. Paige. Data generation for neural programming by example. In International Conference Artificial Intelligence and Statistics, pages 3450-3459, PMLR, 2020.
[14] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pages 248-255. IEFF, 2009.
[15] J. Devlin, R. Bunel. R. Singh, M. Hausknecht, and P. Kohli. Neural program meta-induction. In Advances in Neural Information Processing Systems, 2017.
[16] Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
[17] J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A. Mohamed, and P. Kohli. Robustfill: Neural program learning under noisy I/O. In International Conference on Machine Learning, 2017.
[18] K. Ellis, M. I. Nye, Y. Pu, F. Sosa, J. B. Tenenbaum, and A. Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Processing Systems, 2019.
[19] S. Gulwani. Automating string processing in spreadsheets using input-output examples. In ACM SIGPLAN Notices, volume 46, pages 317-330. ACM, 2011.
[20] S. Gulwani, W. R. Harris, and R. Singh. Spreadsheet data manipulation using examples. Communications of the ACM, 55(8):97-105, 2012.

---

[21] K. Gupta, P. E. Christensen, X. Chen, and D. Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. In Advances in Neural Information Processing Systems, 2020.
[22] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-
778, 2016.
[23] D. Hendrycks, S. Basart, S. Kadavath, M. Mazeika, A. Arora, E. Guo, C. Burns, Puranik, H. He. D. Song, et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105,0 099999 2021.
[24] Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation. 188):1735- 1780, 1997.
[25] A. S. Illia Polosukhin. Neural program search: Solving data processing tasks from description and examples, 2018.
[26] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[27] S. Kulal, P. Pasupat, K. Chandra, M. Lee, O. Padon, A. Aiken, and Liang. Spoc: Search-based pseudocode to code. In Advances in Neural Information Processing Systems, 2019.
[28] L. Laich, P. Bielik, and M. Vechev. Guiding program synthesis by learning to generate examples. In International Conference on Learning Representations, 2019.
[29] G. Lample and F. Charton. Deep learning for symbolic mathematics. In International Conference on Learning Representations, 2020.
[30] M.-T. Luong, H. Pham, and C. D. Manning. Effective approaches to attention-based neural machine translation. arXiv preprint 1508. 2015.
[31] S. Mandal, T. Anderson, J. Turek, Gottschlich, Zhou, and A. Muzahid. Learning fitness functions for machine programming. Proceedings of Machine Learning and Systems, 3, 2021.
[32] D. McClosky, E. Charniak, and M. Johnson. Effective self- trainiriinn for parsing, In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 159, 2006.
[33] C. Mendis, A. Renda, S. Amarasinghe, and M. Carbin. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. In International Conference on machine learning, pages 4505-4515. PMLR, 2019.
[34] Q Min, L. Qin, Z. Teng, X. Liu, and Y. Zhang. Dialogue state induction using neural latent variable models. In International Joint Conferences Artificial Intelligence, 2020.
[35] C. Z. Mooney, C. F. Mooney, C. L. Mooney, R. D. Duval, and R. Duvall. Bootstrapping: A nonparametric approach statistical inference. Number 95, sage, 1993.
[36] M. Nye, L. Hewitt, J. Tenenbaum, and A. Solar-Lezama. Learning to infer program sketches. In International Conference on Machine Learning, pages 4861-4870. PMLR, 2019.
[37] M. Nye, Y. Pu, M. Bowers, Andreas. B. Tenenbaum, and A. Solar-Lezama. Representing partial programs with blended abstract semantics. In International Conference on Learning Representations, 2021.
[38] A. Odena, K. Shi, D. Bieber, R. Singh, and C. Sutton. Bustle: Bottom-up program-ssnthesis through learning-guide guided exploration. In International Conference on Learning Representations, 2021.
[39] A. Odena and C. Sutton. Learning to represent programs with property signatures. In Interna- tional Conference on Learning Representations, 2020.
[40] E. Parisotto, A.-r. Mohamed, R. Singh, L. Li, Zhou, and P. Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Representations, 2017.
[41] R. F. Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, Inc., 1981.
[42] C. Paxton, Y. Bisk, J. Thomason, A. Byravan, and D. Foxl. Prospection: Interpretable plans from language by predicting the future. In 2019 International Conference on Robotics and Automation (ICRA), pages 6942-6948. IEEE, 2019.
12

---

[43] D. Saxton, E. Grefenstette, F. Hill, and P. Kohli. Analysing mathematical reasoning abilities of neural models. 2019.
[44] E. C. Shin, I. Polosukhin, and D. Song. Improving neural program synthesis with inferred execution traces. In Advances in Neural Information Processing Systems, pages 8917-8926, 2018.
[45] R. Shin, N. Kant, K. Gupta, C. Bender, B. Trabucco, R. Singh, and D. Song. Synthetic datasets for neural program synthesis. In International Conference on Learning Representations, 2019.
[46] A. Suh and Y. Timen. Creating synthetic datasets via evolution for neural program synthesis. arXiv preprini arXiv:2003. 10485, 2020.
[47] S.-H. Sun, H. Noh, S. Somasundaram, and J. Lim. Neural program synthesis from diverse demonstration videos. In Proceedings of the 35th International Conference on Machine Learn- ing. 2018.
[48] Y. Tian, A. Luo, X. Sun, K. Ellis, W. T. Freeman, J. B. Tenenbaum, and J. Wu. Learning to infer and exccute 3d shape programs. In International Conference on Learning Representations, 2019.
[49] A. Vaswani, Shazeer, N. Parmar, Uszkoreit, L. Jones, N. Gomez, Kaiser, and
I. Polosukhin. Attention is all you need. arXiv preprint arXiv: /tfiv:7706.000 176.03376. 2017.
[50] P. Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. International Conference on Learning Representations, 2020.
[51] A. J. Vijayakumar, A. Mohta, O. Polozov, D. Batra, P. Jain, and S. Gulwani. Neural-guide
deductive search for real-time program synthesis from examples. In International Conference on Learning Representations, 2018.
[52] Q. Xie, M.-T. Luong, E. Hovy, and Q. V. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10687-10698, 2020.
[53] Y. Yan, K. Swersky, D. Koutra, P. Ranganathan, and M. Heshemi. Neural execution engines: Learning to execute subroutines. Advances Neural Information Processing Systems, 2020.
[54] X. Yang, Y. Chen, E. Eide, and Regehr. Finding and understanding bugs in compilers. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, pages 283-294, 2011.
[55] W. Zaremba and I. Sutskever. Learning to execute. arXiv preprint arXiv:1410.4615, 2014.
[56) Y. Zhang. Z. Ou, M. Hu, and J. Feng. A probabilistic end-to-end task-oriented dialog model with latent belief states towards semi-supervised learning. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
[57] A. Zohar and L. Wolf. Automatic program synthesis of long programs with learned garbage collector. In Advances in Neural Information Processing Systems, 2018
13


Reviews:
[{"review_id": "wZE8vUKyiyX", "reviewer": "Reviewer_KoBE", "summary": "The goal of this paper is to perform program synthesis, taking inspiration from recent advances in execution-guided neural program synthesis in situations where execution of partial programs is not immediately possible.\n\nAs stated by the paper, the main contributions are\n1) combining two types of representations - one which models the mapping from spec to program tokens, as in RobustFill (and other neural synthesis work), and the other which models the “hypothetical input signal for the remaining partial program to execute to get the desired output”\n\n2) demonstrating that iterative retraining can lead to better modeling of code and improve sample efficiency.\n\n3) showing that short C code can be synthesized from IO examples through the above two techniques.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality & significance:  The technique is original. This work addresses important questions in neural program synthesis; namely, how to adapt the successful execution-guided neural program synthesis to domains where intermediate execution is impossible or infeasible.\nThis work provides further relaxations from Nye et al. (2021), gaining from an approach inspired by execution-guided synthesis, but without learning neural functions for each DSL element.\n\nAblations are good, and seem to show that the partial executor is important for performance on the C dataset. \n\nIterative retraining seems to have a large effect at small dataset sizes; this effect diminishes at larger dataset sizes. For this reason, I do think the claim about iterative retraining would be stronger if it were evaluated on datasets build from real data, where extending the dataset automatically is not feasible. (See below — the dataset from Alet et al 2021 might be a good candidate). It seems that iterative retraining works because randomly generated programs are often more complicated than they need to be to solve the input-output examples (lines 226-230), but figure 3 and figure 7a seem to show that this mismatch can largely be solved by simply training on more synthetic data (which is always available for synthetic datasets). What would we see if we trained on real programs, where a) there isn’t always more data available but b) there may be less of a mismatch between the training data and the optimal programs?\n\nClarity:\n- The paper is decently written, although there were some places where I was a little confused. In particular, I’m confused about how the latent execution setup works in the Karel domain. An explanation of this seems to be missing from both the main text and the supplement. In the C domain, $\\hat{I}_{t,l}$ seems to be defined by a sum over embeddings of possible states. In the Karel domain, you don’t perform a sum over all possible Karel states, correct? Similarly, what is the Karel analog of the precomputed operation table?\n\n\n- The hand-designed nature of the operation table of possible operations seems like a limitation. How would it scale to a larger set of values and operations? To me this seems to be the biggest limitation of the approach. The paper doesn’t contain much discussion of these limitations; I think adding a limitations section would greatly increase clarity\n For example, here are some other questions that it would be helpful to see answered:\n\t- I don’t have a clear sense of when this technique is easily applicable vs not applicable. Is the system as implemented only applicable to C programs with a type signature of List —> List, or could other type signature be easily supported? For example, how much engineering would be required to include programs of type (Int, List) —> List or List —> Int?\n\t- Is the approach computationally tractable when the set of possible intermediate states is too large to enumerate over? What happens when the range of integers is increased from [-4, 4] to [-256, 256] (or even [-2^32, 2^32])? Is that a limitation of this approach, or is there an easy fix? If it’s a limitation, I think that’s fine, but it would be helpful if it were clearly stated.\n\nOverall, I do believe that this is an interesting contribution to neural program synthesis which extends the applicability of the promising line of neural execution-guided synthesis work. I felt like I learned something new reading this paper, although I don’t have a clear sense why this technique works. I would recommend acceptance, but I do think that improving the clarity about the Karel domain and a more clear discussion of limitations is important.\n\n\nComments/Questions:  \nHere are questions that are not necessary for my vote of acceptance, but things I think would be interesting to explore:\n\n- Is there evidence that the latent execution representations $\\hat{I}$ actually predict execution well? Can you accurately predict the actual intermediate state from $\\hat{I}$?\n\n- How do these models compare against transformer models pre-trained on language? I’ve seen that pre-trained transformers can achieve good performance when fine-tuned on synthesis tasks. \n\n  - I’d be very interested to see the results of this system on the new C++ dataset from “A large-scale benchmark for few-shot program induction and synthesis” (Alet et al, ICML 2021). That would be an interesting test of this system on real-world code written by humans. As discussed above, I also think that it would be very useful to test iterative retraining here, to see if the approach has a benefit when the training dataset is derived from real code as opposed to synthetically generated.\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See discussion of limitations above in main review, which I think do need to be more clearly addressed.\n\nNo negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "KrrydTD2iM", "reviewer": "Reviewer_iKX1", "summary": "This work improves neural program synthesis of imperative programs with limited control-flow (conditionals and loops)\nfrom input-output examples. It extends the established pipelines for the Karel task – recurrent program decoder with\nattention over partial output and example encodings – with modeling of a latent variable that represents a possible\nexecution state of the program at that location. The latent variable is supervised at the end to match the desired\noutput state. The authors test the approach on Karel (with mixed results), and on a randomly generated dataset of C\nprograms of similar complexity (where it substantially outperforms the baselines).", "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": "\nThe key motivation of this work is to generalize execution-guided neural program synthesis to settings where step-wise\ninterpretation to retrieve actual program state is hard. Modeling expected program state as a latent variable,\npredicting it with a recurrent model, and supervising to match the real state when known (in case of synthesis, the\ndesired output) is a promising and natural step towards that goal. However, the way the work presents its argument,\nevaluates it, and compares against baselines falls short of its stated goal.\n\n## Dataset\nThe key dataset that demonstrates the strength of LaSynth \"beyond domain-specific languages\" is a new dataset of\nrandomly-generated C programs. Its strengths include:\n- A clever generation technique that leverages Csmith, a well-known random program generator for compiler fuzzing;\n- Focus on challenging control flow, including for loops over integer lists, local variables, and arithmetic conditionals.\n\nHowever, the sole fact that the generated programs are in C does not make it \"unlike DSLs\". The generated programs are\nin a limited subset of C, de-facto unifying features of two existing DSLs: Karel and DeepCoder. They take loops and\nconditionals from Karel, and variables, lists, and arithmetic from DeepCoder. As a result, the programs really do not\nhighlight the challenges by which the work is motivated. While C is compiled rather than interpreted, tracing partial\nprograms in this subset (to implement e.g. [6] or [22]) only requires one to close all outstanding blocks (to make the\nprogram complete) and dump variable states at the location of interest.\n\nSome challenging program synthesis datasets already satisfy the authors' requirements of (a) real programming language,\n(b) input-output examples, (c) complex control flow. For instance:\n- SPoC: https://sumith1896.github.io/spoc/\n- APPS: https://github.com/hendrycks/apps\n\nWhat is the reasonable upper bound of performance on the C dataset? For instance, how often is it the case that example\ninputs have less that 100% coverage of the ground-truth program, and thus do not fully specify the intent?\n\n\n## Baselines\n\nThe most natural baseline for this work would be [22], motivated by the similar goal of representing semantics of\npartial programs as a latent variables. However, the authors do not provide any experimental evaluation, stating that\n\"per-line execution of partial C programs is infeasible\" (L81). While generally true, this is definitely untrue for the\nauthors' dataset (e.g., via [CompCert Interpreter](https://compcert.org/man/manual004.html) or an ad-hoc one – see\nabove). As such, _conceptual_ comparison of two approaches is feasible. It is also warranted, given that LaSynth does\nnot compare nearly as favorably to explicit execution-guided synthesizers [28] and [6] on Karel.\n\nGeneralizing the point above, the fact that no baseline is shared between Karel and C evaluations makes it difficult to\nappreciate the contribution of LaSynth. It clearly outperforms syntax-only synthesizers, but its comparison to the space\nof execution-guided synthesizers (latent or explicit) is yet unclear.\n\nWhat are the standard errors in Tables 2 and 3? How many runs were trained?\n\n## Arithmetic modeling\n\nThe operation predictor is, in short, a lookup table for arithmetic operations that relies on the fact that only small\nintegers are used in the C dataset. Its inclusion is puzzling for many reasons:\n- It is a domain-specific optimization that only works for small-number arithmetic, yet presented as part of the generic\n  program architecture (Section 3.2). What is its instantiation for Karel?\n- Table 1 claims that LaSynth has \"no domain-specific features\", yet operation predictor for arithmetic between -4 and 4\n  that works because the dataset only contains these numbers is _most assuredly_ a domain-specific feature.\n- It boosts accuracy on the C dataset by less than 2% – likely statistically significant but clearly orthogonal to the\n  main contribution of the paper.\n\n## Miscellaneous\n\nMore related work:\n- Some research on task-oriented dialog requires the learned conversational system to model the latent \"state\" of the\n  dialog, see e.g. [Min et al. 2020; Zhang et al. 2020]. (Usually the belief state is non-latent and labeled with some\n  logical forms., thus more analogous to [6]).\n- Predicting the next state after execution of the next instruction has also appeared in robotics [Paxton et al. 2019].\n\nThe \"Iterative Retraining\" trick is neat in the context of program synthesis. More broadly it can be likened to classic\n_bootstrapping_ of ML models, where previous-iteration model is used to produce labels for an unsupervised dataset to\ntrain the next-iteration model. Here the model is generative yet multiple \"correct\" labels for the same instance exist,\nso this version of bootstrapping can re-label existing data instead. Worth exploring the connection in Related Work.  \nThe fact that this bootstrapping brings to light that many Karel programs permit equivalent simpler implementations is a\nvery interesting discovery, worthy of preview in the Introduction.\n\nPlease clarify whether Equation 6 is computed in symbolic space or (as $\\hat{I}_T$ might suggest) in representation\nspace and consequently, what exactly is the used loss.\n\n$\\mathit{EXEC}_t$ in Figure 2c is only defined in the Appendix.\n\nL302: \"we make the first attempt of synthesizing C code from input-output examples for list manipulation\" is unfair. It\nis obvious untrue for non-neural synthesizers, but even for neural synthesis it neglects e.g. SPoC [Kulal et al. 2019]\nand very recently (for Python rather than C) Codex [Chen et al. 2021]. \n\n\n## References\n1. Min, Qingkai, et al. \"Dialogue State Induction Using Neural Latent Variable Models.\" IJCAI 2020.\n2. Zhang, Yichi, et al. \"A Probabilistic End-To-End Task-Oriented Dialog Model with Latent Belief States towards Semi-Supervised Learning.\" EMNLP 2020.\n3. Paxton, Chris, et al. \"Prospection: Interpretable plans from language by predicting the future.\" ICRA 2019.\n4. Kulal, Sumith, et al. \"SPoC: Search-based Pseudocode to Code.\" NeurIPS 2019.\n5. Chen, Mark, et al. \"Evaluating Large Language Models Trained on Code.\" arXiv preprint arXiv:2107.03374 (2021).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No explicit limitations considered. The authors might consider discussing:\n- what are the limits of \"non-domain-specific\" language constructs that latent execution might model successfully;\n- the applicability of operation predictors;\n- how might one generalize state embedding to settings where the state \"type signature\" is not uniform.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "GVJo-9gwnhT", "reviewer": "Reviewer_WZjE", "summary": "This paper presents a neural program synthesis system, called LaSynth, that aims to generate programs in non-domain specific languages (DSLs) unlike much of the prior work. In particular, this paper focuses on using LaSynth for the C programming language. A core reason prior work in program synthesis has been generally restricted to DSLs is, as the authors note (and I agree with), because of the linguistic complexity of general-purpose languages and the computational intractability that is often associated with synthesizing programs in such languages.\n\nA core novelty of LaSynth is that it uses two forms of conjoined/parallel representations, one of which uses a hypothetical input to help determine the remaining partial program to execute to get the desired output. This somewhat resembles BUSTLE’s approach of breaking down components into small pieces and then assembling them for a larger program (ICLR ’21), but the actual system-level approach in LaSynth, in my mind, is notably different from BUSTLE and other prior works that I’m familiar (some of which the authors seem to have missed in the prior work – NetSyn (Mandal et al., MLSys ’21), REPL (Ellis et al., NeurIPS ’20), etc.), but we'll get to that later.\n", "questions": "", "limitations": "", "rating": 7, "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": "Overall, I’m positive about this paper, even though I think it has some weaknesses (most are simple things that can be addressed in revising the paper). What I like the most about this paper is the authors intentionally move away from DSLs and toy languages (like Karel) and instead targeting program synthesis for real-world programming languages, like C, which is the primary target language for this paper. By migrating to such real-world languages, many challenges emerge (e.g., syntax correctness, computational complexity, multiple correct synthesized programs for the same problem, etc.). This complexity has historically been a major restriction in program synthesis research. A core reason for this is that each additional language token can result in upwards of an order of magnitude increase in the computational search space for the program synthesizer, amongst many other core challenges.\n\nThe authors address this computational tractability problem by using partial programs and hypothesized intermediate state IO representations to help the synthesizer (the Latest Execution Trace (LaET)). In my opinion, the core novelty of the work is in the LaET. An additional novelty is in the construction of the synthesizer system design, which uses parallel representations and iterative retraining to help prune unnecessary instructions and reduce the synthesized programs to programs that “work” to programs that “a human might write” (see Figure 1’s code transformation from the top left to the top right).\n\nA weakness in the paper is they only seem to compare their results to two other systems (outside of variants of their own): Property Signatures and RobustFill. Both systems are fairly relevant and new-ish. However, newer systems include REPL (NeurIPS ’20), BUSTLE (ICLR ’21), and NetSyn (MLSys ’21). I don’t think it’s a showstopper for that this paper doesn’t include these systems as perhaps there wasn’t enough time to get access to them. However, there should probably be at least some footnote somewhere explaining why these systems weren’t include (e.g., code not available, published after the submission, generally different approach, etc.). I hope the authors update the paper accordingly here.\n\nPlease fix this: there is a *plethora* of work that utilize execution traces for ML outside of that being used in Karel, which is a toy programming language and are the only three papers you cite for this space, all of which come from Dawn Song’s research group at Berkeley. Examples of others that use execution traces for machine programming, just off the top of my head: NetSyn (MLSys ’21), REPL (NeurIPS ’20), AutoPerf (NeurIPS ’19), Ithemal (ICML ‘19). When I saw that the only works cited for program traces was all came from the same group at Berkeley, I was rather disappointed (especially seeing that the authors seem to be well-versed in the literature). I strongly recommend you not singularly cite *one* researcher’s group in an area as broad as program traces for ML that being covered by dozens of research groups. By doing this – citing three papers (and only three) all from the same group all around the same (toy) language – it creates a perception that either you are from this group and you are self-citing or you are not informed about the state-of-the-art. Either case is poor research acumen, unbefitting of a tier-1 venue like NeurIPS, in my opinion.\n\nMinor nit: the citations are not properly capitalized (e.g., “Deepcoder: Learning to write programs” -> “DeepCoder: Learning to Write Programs”, “Imagenet: A large-scale hierarchical image database” -> “ImageNet: a Large-Scale Hierarchical Image Database”, “Bustle: …” -> “BUSTLE: …”, etc.). Please fix these minor grammatical errors for subsequent revisions of the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "90B-r9Z3GLy", "reviewer": "Reviewer_BQk7", "summary": "This paper introduces LaSynth, a novel neural architecture that jointly learns to synthesize programs and perform a kind of targeted latent program execution. LaSynth is applied to synthesize Karel programs and list processing programs in the C programming language. The paper also finds that one to two iterations of dataset refinement and iterative retraining can improve the dataset quality and model performance. The LaSynth approach, with iterative retraining, is found to outperform baselines both in the Karel and C domains.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work draws inspiration from and combines ideas from prior works using execution traces for program synthesis, and performing neural execution in latent space. It combines the core ideas of RobustFill for program generation with latent program execution to learn a latent program trace. This novel combination of ideas allows LaSynth to achieve strong results in two domains and outperform RobustFill and a Property Signature-based approach.\n\nBeyond being a novel combination of ideas, the use of this kind of latent program execution from program synthesis is novel too. The latent states in the latent executor represent an abstraction both of (1) the result of the execution so far and (2) what the remainder of the program would need to be in order to achieve the target output.\n\nThe paper builds on a rich body of work on execution-guided program synthesis. Overall, it frames itself well within this literature. However, for the part of the paper on dataset refinement, this is lacking. I encourage the authors to put their dataset refinement contribution in the context of existing literature. Data augmentation is a rich field and has been used for program synthesis [1], and noisy student training [2] bears resemblance to your iterative approach.\n\nThe paper backs up its claims about the newly proposed approach LaSynth and about iterative dataset refinement through clear experimental evidence. It finds in the Karel domain that LaSynth (both with and without dataset refinement) outperforms the baselines considered, which do an adequate job of covering the space of modern approaches to the tasks.\n\nHow are the approaches made comparable? Are they given equal total compute or wall clock time, or are an equal number of samples drawn from each? How would an enumerative search approach compare?\n\nThe paper further finds that one (sometimes two) iterations of dataset refinement improve performance further. There is a rich body of existing work on data augmentation and self-training methods, which this paper does not mention. I suggest investigating his line of work and placing your dataset refinement contributions (which, to my knowledge, are novel for program synthesis) in the context of this body of existing work. See e.g. \"noisy student training\" [2].\n\nThe paper is overall clear in is explanation of its contributions, the method details, and the experiments. The paper states the latent executor hidden states represent the hypothetical input to the remaining program to produce the target output. This intuition bears elaboration. A concern I have is that the remaining partial program during latent execution could be the second half of a loop body, which in traditional code does not have a single input, nor can it be executed in isolation. Explaining the intuition of the hidden states more clearly would benefit the paper.\n\nProgram synthesis is an important problem lately of increasing interest to the NeurIPS community. Increasing the complexity of the languages in which synthesis is applicable is important, and the approach in this paper does just that. I do find the importance of the claim that this is the first time C code to be less significant than it likely sounds, however. Though technically a correct claim, this paper is looking at a narrow domain of programs, such that the complexity of working with C programs is comparable to working in a DSL for the domain. Particularly the significance is diminished (relative to the broader language of the claim) because of the restricted space of values considered, which includes only lists of the integers in $[-4, 4]$.\n\nThis limitation in the C domain manifests in the method with the following concern. The operation predictor uses a pre-computed table of all integer and subtraction operations. This is only possible due to the restricted domain of values, and prohibits the method as is from being used for even modestly broader domains.\n\nCould you clarify what is meant by \"we compute the property value per element in input-output pairs\" at line 273?\n\n---\n\nTypo: \"an associate memory structure\" should be \"associative\"\n\n---\n\n[1] Guiding Program Synthesis by Learning to Generate Examples https://openreview.net/pdf?id=BJl07ySKvS\n\n[2] Self-training with Noisy Student improves ImageNet classification https://arxiv.org/abs/1911.04252\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors describe the main technical limitation of the work, the limited scope of the C language that it can handle. The authors do not discuss potential societal impact, indicating in the checklist they don't anticipate any such negative impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: OK, the situation with this paper is a bit unusual, owing to the fact that NeurIPS doesn't allow revisions during the reviewing period.
Basically all of the reviewers agreed that the core idea is good, but many of them had serious concerns with scoping and clarity. 
I am going to recommend acceptance here, but I want to really strongly urge the authors to address the issues brought up by the reviewers in the final version of the paper. I don't actually have any authority to compel that outcome, so I'm relying on trust here - please do make these changes!
Decision: Accept (Poster)