We present a Neural Program Search, an algorithm to generate programs from natural language description and a small number of input / output examples. The algorithm combines methods from Deep Learning and Program Synthesis fields by designing rich domain-specific language (DSL) and defining efficient search algorithm guided by a Seq2Tree model on it. To evaluate the quality of the approach we also present a semi-synthetic dataset of descriptions with test examples and corresponding programs. We show that our algorithm significantly outperforms sequence-to-sequence model with attention baseline.
This paper presents a seq2Tree model to translate a problem statement in natural 
language to the corresponding functional program in a DSL. The model uses
an RNN encoder to encode the problem statement and uses an attention-based
doubly recurrent network for generating tree-structured output. The learnt model is 
then used to perform Tree-beam search using a search algorithm that searches 
for different completion of trees based on node types. The evaluation is performed
on a synthetic dataset and shows improvements over seq2seq baseline approach.
Overall, this paper tackles an important problem of learning programs from 
natural language and input-output example specifications. Unlike previous
neural program synthesis approaches that consider only one of the specification 
mechanisms (examples or natural language), this paper considers both of them 
simultaneously. However, there are several issues both in the approach and the 
current preliminary evaluation, which unfortunately leads me to a reject score,
but the general idea of combining different specifications is quite promising.
First, the paper does not compare against a very similar approach of Parisotto et al.
Neuro-symbolic Program Synthesis (ICLR 2017) that uses a similar R3NN network
for generating the program tree incrementally by decoding one node at a time.
Can the authors comment on the similarity/differences between the approaches?
Would it be possible to empirically evaluate how the R3NN performs on this dataset?
Second, it seems that the current model does not use the input-output examples at 
all for training the model. The examples are only used during the search algorithm.
Several previous neural program synthesis approaches (DeepCoder (ICLR 2017), 
RobustFill (ICML 2017)) have shown that encoding the examples can help guide 
the decoder to perform efficient search. It would be good to possibly add another 
encoder network to see if encoding the examples as well help improve the accuracy.
Similar to the previous point, it would also be good to evaluate the usefulness of
encoding the problem statement by comparing the final model against a model in which
the encoder only encodes the input-output examples.
Finally, there is also an issue with the synthetic evaluation dataset. Since the 
problem descriptions are generated syntactically using a template based approach, 
the improvements in accuracy might come directly from learning the training templates
instead of learning the desired semantics. The paper mentions that it is prohibitively 
expensive to obtain human-annotated set, but can it be possible to at least obtain a 
handful of real tasks to evaluate the learnt model? There are also some recent 
datasets such as WikiSQL (https://github.com/salesforce/WikiSQL) that the authors
might consider in future.
Questions for the authors:
Why was MAX_VISITED only limited to 100? What happens when it is set to 10^4 or 10^6?
The Search algorithm only shows an accuracy of 0.6% with MAX_VISITED=100. What would
the performance be for a simple brute-force algorithm with a timeout of say 10 mins?
Table 3 reports an accuracy of 85.8% whereas the text mentions that the best result
is 90.1% (page 8)?
What all function names are allowed in the DSL (Figure 1)? 
Can you clarify the contributions of the paper in comparison to the R3NN?
Minor typos:
page 2: allows to add constrains --> allows to add constraints
page 5: over MAX_VISITED programs has been --> over MAX_VISITED programs have been