Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents a reinforcement learning-based approach for program synthesis. The proposed approach claims two advantages over a baseline maximum likelihood estimation-based approach. MLE-based methods penalize syntactically different but semantically equivalent programs. Further, typical program synthesis approaches don't explicitly learn to produce correct syntax. The proposed approach uses a syntax-checker to limit the next-token distribution to syntactically-valid tokens.

The approach, and its constituent contributions, i.e. of using RL for program synthesis, and limiting to syntactically valid programs, are novel. Although both the contributions are fairly obvious, there is of course merit in empirically validating these ideas.

The paper presents comparisons with baseline methods. The improvements over the baseline methods is small but substantial, and enough experimental details are provided to reproduce the results.  However, there is no comparison with other approaches in the literature. The authors claim to improve the state-of-the-art, but fail to mention and compare with the state-of-the-art, such as [1]. I do find it hard to trust papers which do not compare with results from other papers.

Pros:
1. Well-written paper, with clear contributions.
2. Good empirical evaluation with ablations.

Cons:
1. No SOTA comparison.
2. Only one task / No real-world task, such as Excel Flashfill.

[1]: "Neural Program Meta-Induction", Jacob Devlin, Rudy Bunel, Rishabh Singh, Matthew Hausknecht, Pushmeet Kohli
review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors consider the task of program synthesis in the Karel DSL. Their innovations are to use reinforcement learning to guide sequential generation of tokes towards a high reward output, incorporate syntax checking into the synthesis procedure to prune syntactically invalid programs. Finally they learn a model that predicts correctness of syntax in absence of a syntax checker. 

While the results in this paper look good, I found many aspects of the exposition difficult to follow. In section 4, the authors define objectives, but do not clearly describe how these objectives are optimized, instead relying on the read to infer from context how REINFORCE and beam search are applied. I was not able to understand whether syntactic corrected is enforce by way of the reward introduced in section 4, or by way of the conditioning introduced in section 5.1. Discussion of the experimental results coould similarly be clearer. The best method very clearly depends on the taks and the amount of available data, but I found it difficult to extract an intuition for which method works best in which setting and why. 

On the whole this seems like a promising paper. That said, I think the authors would need to convincingly address issues of clarity in order for this to appear. 

Specific comments 

- Figure 2 is too small 

- Equation 8 is confusing in that it defines a Monte Carlo estimate of the expected reward, rather than an estimator of the gradient of the expected reward (which is what REINFORCE is). 

- It is not clear the how beam search is carried out. In equation (10) there appear to be two problems. The first is that the index i appears twice (once in i=1..N and once in i \in 1..C), the second is that λ_r refers to an index that does not appear. More generally, beam search is normally an algorithm where at each search depth, the set of candidate paths is pruned according to some heuristic. What is the heuristic here? Is syntax checking used at each step of token generation, or something along these lines? 
 
- What is the value of the learned syntax in section 5.2? Presumaly we need a large corpus of syntax-checked training examples to learn this model, which means that, in practice, we still need to have a syntax-checker available, do we not?
review_title: Good paper, could be more clearly written.

final_score: rating: 7: Good paper, accept
review_content: This is a nice paper. It makes novel contributions to neural program synthesis by (a) using RL to tune neural program synthesizers such that they can generate a wider variety of correct programs and (b) using a syntax checker (or a learned approximation thereof) to prevent the synthesizer from outputting any syntactically-invalid programs, thus pruning the search space. In experiments, the proposed method synthesizes correct Karel programs (non-trivial programs involving loops and conditionals) more frequently than synthesizers trained using only maximum likelihood supervised training.

I have a few minor questions and requests for clarification, but overall the paper presents strong results and, I believe, should be accepted.


Specific comments/questions follow:


Figure 2 is too small. It would be much more helpful (and easier to read) if it were enlarged to take the full page width.

Page 7: "In the supervised setting..." This suggests that the syntaxLSTM can be trained without supervision in the form of known valid programs, a possibility which might not have occurred to me without this little aside. If that is indeed the case, that's a surprising and interesting result that deserves having more attention called to it (I appreciated the analysis in the results section to this effect, but you could call attention to this sooner, here on page 7).

Is the "Karel DSL" in your experiments the full Karel language, or a subset designed for the paper?

For the versions of the model that use beam search, what beam width was used? Do the results reported in e.g. Table 1 change as a function of beam width, and if so, how? 

review_title: Good paper, accept

Meta-review: Below is a summary of the pros and cons of the proposed paper:

Pros:
* Proposes a novel method to tune program synthesizers to generate correct programs and prune search space, leading to better and more efficient synthesis
* Shows small but substantial gains on a standard benchmark

Cons:
* Reviewers and commenters cited a few clarity issues, although these have mostly been resolved
* Lack of empirical comparison with relevant previous work (e.g. Parisotto et al.) makes it hard to determine their relative merit

Overall, this seems to be a solid, well-evaluated contribution and seems to me to warrant a poster presentation.

Also, just a few notes from the area chair to potentially make the final version better:

The proposed method is certainly different from the method of Parisotto et al., but it is attempting to solve the same problem: the lack of consideration of the grammar in neural program synthesis models. The relative merit is stated to be that the proposed method can be used when there is no grammar specification, but the model of Parisotto et al. also learns expansion rules from data, so no explicit grammar specification is necessary (as long as a parser exists, which is presumably necessary to perform the syntax checking that is core to the proposed method). It would have been ideal to see an empirical comparison between the two methods, but this is obviously a lot of work. It would be nice to have the method acknowledged more prominently in the description, perhaps in the introduction, however.

It is nice to see a head-nod to Guu et al.'s work on semantic parsing (as semantic parsing from natural language is also highly relevant). There is obviously a lot of work on generating structured representations from natural lanugage, and the following two might be particularly relevant given their focus on grammar-based formalisms for code synthesis from natural language:

* "A Syntactic Neural Model for General-purpose Code Generation" Yin and Neubig ACL 2017.
* "Abstract Syntax Networks for Code Generation and Semantic Parsing" Rabinovich et al. ACL 2017

Decision: Accept (Poster)