Published as a conference paper at ICLR 2018 TOWARDS SYNTHESIZING COMPLEX PROGRAMS FROM INPUT-OUTPUT EXAMPLES
In recent years, deep learning techniques have been developed to improve the performance of program synthesis from input-output examples. Albeit its significant progress, the programs that can be synthesized by state-of-the-art approaches are still simple in terms of their complexity. In this work, we move a significant step forward along this direction by proposing a new class of challenging tasks in the domain of program synthesis from input-output examples: learning a context-free parser from pairs of input programs and their parse trees. We show that this class of tasks are much more challenging than previously studied tasks, and the test accuracy of existing approaches is almost 0%. We tackle the challenges by developing three novel techniques inspired by three novel observations, which reveal the key ingredients of using deep learning to synthesize a complex program. First, the use of a non-differentiable machine is the key to effectively restrict the search space. Thus our proposed approach learns a neural program operating a domain-specific non-differentiable machine. Second, recursion is the key to achieve generalizability. Thus, we bake-in the notion of recursion in the design of our non-differentiable machine. Third, reinforcement learning is the key to learn how to operate the non-differentiable machine, but it is also hard to train the model effectively with existing reinforcement learning algorithms from a cold boot. We develop a novel two-phase reinforcement learningbased search algorithm to overcome this issue. In our evaluation, we show that using our novel approach, neural parsing programs can be learned to achieve 100% test accuracy on test inputs that are 500× longer than the training samples.
This paper presents a reinforcement learning based approach to learn context-free
parsers from pairs of input programs and their corresponding parse trees. The main
idea of the approach is to learn a neural controller that operates over a discrete
space of programmatic actions such that the controller is able to produce the
desired parse trees for the input programs. The neural controller is trained using 
a two-phase reinforcement learning approach where the first phase is used to find
a set of candidate traces for each input-output example and the second phase is 
used to find a satisfiable specification comprising of 1 unique trace per example
such that there exists a program that is consistent with all the traces. The 
approach is evaluated on two datasets comprising of learning parsers for an 
imperative WHILE language and a functional LAMBDA language. The results show that
the proposed approach is able to achieve 100% generalization on test sets with 
programs upto 100x longer than the training programs, while baseline approaches 
such as seq2seq and stack LSTM do not generalize at all.
The idea to decompose the synthesis task into two sub-tasks of first learning
a set of individual traces for each example, and then learning a program consistent
with a satisfiable subset of traces is quite interesting and novel. The use of 
reinforcement learning in the two phases of finding candidate trace sets with 
different reward functions for different operators and searching for a satisfiable 
subset of traces is also interesting. Finally, the results leading to perfect 
generalization on parsing 100x longer input programs is also quite impressive.
While the presented results are impressive, a lot of design decisions such as 
designing specific operators (Call, Reduce,..) and their specific semantics seem
to be quite domain-specific for the parsing task. The comparison with general 
approaches such as seq2seq and stack LSTM might not be that fair as they are 
not restricted to only those operators and this possibly also explains the low 
generalization accuracies. Can the authors comment on the generality of the 
presented approach to some other program synthesis tasks?
For comparison with the baseline networks such as seq2seq and stack-LSTM, what 
happens if the number of training examples is 1M (say programs upto size 100)? 
10k might be too small a number of training examples and these networks can 
easily overfit such a small dataset.
The paper mentions that developing a parser can take upto 2x/3x more time than 
developing the training set. How large were the 150 examples that were used for
training the models and were they hand-designed or automatically generated by a
parsing algorithm? Hand generating parse trees for complex expressions seems to
be more tedious and error-prone that writing a modular parser.
The reason there are only 3 to 5 candidate traces per example is because the training
examples are small? For longer programs, I can imagine there can be thousands of bad
traces as it only needs one small mistake to propagate to full traces. Related to this
question, what happens to the proposed approach if it is trained with 1000 length programs?
What is the intuition behind keeping M1, M2 and M3 constants? Shouldn’t they be adaptive
values with respect to the number of candidate traces found so far? 
For phase-1 of learning candidate traces, what happens if the algorithm was only using the 
outside loop (M2) and performing REINFORCE without the inside loop?
The current paper presentation is a bit too dense to clearly understand the LL machine 
model and the two-phase algorithm. A lot of important details are currently in the
appendix section with several forward references. I would suggest moving Figure 3 
from appendix to the main paper, and also add a concrete example in section 4 to 
better explain the two-phase strategy.