Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper introduces a technique for program synthesis involving a restricted grammar of problems that is beam-searched using an attentional encoder-decoder network. This work to my knowledge is the first to use a DSL closer to a full language.

The paper is very clear and easy to follow. One way it could be improved is if it were compared with another system. The results showing that guided search is a potent combination whose contribution would be made only stronger if compared with existing work.
review_title: Paper offers a novel approach to a tricky problem and does really well

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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


review_title: Promising direction, but too preliminary

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper tackles the problem of doing program synthesis when given a problem description and a small number of input-output examples. The approach is to use a sequence-to-tree model along with an adaptation of beam search for generating tree-structured outputs. In addition, the paper assembles a template-based synthetic dataset of task descriptions and programs.  Results show that a Seq2Tree model outperforms a Seq2Seq model, that adding search to Seq2Tree improves results, and that search without any training performs worse, although the experiments assume that only a fixed number of programs are explored at test time regardless of the wall time that it takes a technique.

Strengths:

- Reasonable approach, quality is good

- The DSL is richer than that of previous related work like Balog et al. (2016).

- Results show a reasonable improvement in using a Seq2Tree model over a Seq2Seq model, which is interesting.

Weaknesses:

- There are now several papers on using a trained neural network to guide search, and this approach doesn't add too much on top of previous work. Using beam search on tree outputs is a bit of a minor contribution.

- The baselines are just minor variants of the proposed method. It would be stronger to compare against a range of different approaches to the problem, particularly given that the paper is working with a new dataset.

- Data is synthetic, and it's hard to get a sense for how difficult the presented problem is, as there are just four example problems given.

Questions:

- Why not compare against Seq2Seq + Search?

- How about comparing wall time against a traditional program synthesis technique (i.e., no machine learning), ignoring the descriptions. I would guess that an efficiently-implemented enumerative search technique could quickly explore all programs of depth 3, which makes me skeptical that Figure 4 is a fair representation of how well a non neural network-based search could do.

- Are there plans to release the dataset? Could you provide a large sample of the data at an anonymized link? I'd re-evaluate my rating after looking at the data in more detail.

review_title: Decent execution, but not super new or exciting

Meta-review: the reviewers all found the problem to be important, the proposed approach to be interesting, but the manuscript to be preliminary. i agree with them.
Decision: Invite to Workshop Track