Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Update:

The authors have addressed many of my comments below. As such, I am increasing my score.

High-level view:

I’m slightly negative on this paper. The ideas within it seem novel to me, but the experimental examination seems unnecessarily weak / limited. I think if the authors perform a more rigorous analysis of their system, this will result in a strong tier-1 publication. In its current form, I cannot argue for its acceptance at ICLR.


Summary:

This paper introduces an interesting concept of using blended abstract semantics to assist with program synthesis (PS). As I understand it, PS is the field of research interested automatically building software programs using some external guidance, often times in the form of a what could be considered as the intention being conveyed by the human to the machine. Intention here derives from the nomenclature created in the “Three Pillars of Machine Programming” paper, Gottschlich et al. MAPL ‘18. These intentions may be presented many ways. For classical PS, intention tends to be expressed in the form of input / output examples, a specific set of rules, etc.

The “blended” part of the semantics seems to be a fusion of both: (i) neural abstract semantics and (ii) blended abstract semantics.

In this paper, the authors note that the recent prior work in program synthesis using traditional formal methods as well as non-traditional techniques such as machine learning are still in the early stages of exploration and can be improved upon. In particular, the authors attempt to achieve this by using a novel form of neurosymbolic representation (a type of representation that includes both a neural network reasoning as well as more classical symbolic reasoning) with their blended semantics approach. Based on the current knowledge I possess, it seems like this is an interesting and novel way to approach the problem.

The authors evaluate their system in three experimental domains: (i) tower building (think Tetris), (ii) list processing (think numerical list transformation [1, 12, 4] -> [1, 4, 12] (sort)), and (iii) string-editing (think automatic spelling correction or acronymizing things like “programming languages to PL” and “machine learning to ML”).

Overall, they show their blended semantics approach outperforms other neural systems in some cases and not others. 

1.	For the tower building examples, they compare against what I would consider to be a fairly weak baseline of research systems – only two of which are not their variants of their own blended semantics and the results favor the blended semantics variants by upwards of ~29% (just a guess by staring at Figure 4).

2.	For the list processing, they compare blended semantics against an RNN and neural semantics. It seems blended semantics performs slightly better than both other systems by upwards of around 10% or so.

3.	For string editing, they compare against more well-known state-of-the-art synthesizers like RobustFill (ICML 2017) and REPL (NeurIPS 2019). However, they note that REPL outperforms blended semantics, by a fairly large margin for text editing. In the best case, it seems REPL is ~25% more correct than blended semantics; in the worst case, it seems REPL is 60x better. However, it’s a bit hard to tell because the authors have overlaid the legend on *top* of the REPL curve in Figure 7, so one can only speculate about certain aspects there. I’d kindly request that in the next version of the paper, the graph legend in Figure 7 be moved to a place such that it’s not blocking the readers view of the actual performance we are trying to analyze.

Overall, I don’t think this is a bad paper, but I think it has too many weaknesses in its current form for me to give it a positive rating. I discuss some of these below.


High-level concerns:

With respect to the empirical evaluation, I agree that there are likely many important problems in the space of list processing and string editing. Things like sort for list processing is ubiquitous as is string editing for automatic spell checking. So, I have no problems with understanding the validity of these domains and their examination.

However, the tower building experimental domain left me wanting more. More in at least two dimensions. First, I wanted more state-of-the-art systems to consider against. I don’t think a vanilla RNN is really sufficient as a reasonable baseline. Perhaps I’m missing something and the authors can explain to me why I might be wrong? Second, I don’t understand “why I should care” about tower building problems. I don’t feel the problem domain was properly motivated (or maybe I just missed it).

Lastly, these experiments seem shallow to me compared to other program synthesis work I’ve seen at NeurIPS and ICLR. Let’s take Hoppity (ICLR 2020), which looked something like 300k JavaScript bugs and was able to synthesize solutions to around 10,000 of them out of something like 36k. Keep in mind these were real bugs, in a real world programming language.

I realize using an embedded DSL for classic PS has different types of limitations, but just for the sake of comparison I found the experiments (and the motivation of the “hole” example in the tower) a bit underwhelming. And yes, I realize that Armando Solar-Lezama’s sketch system also addressed holes – but if you read his PhD dissertation those holes were with actual code (as I understood it), not necessarily a single instead of a Tetris-like game.

I also was pretty disappointed by the related work section. Armando Solar-Lezama has done incredible work in machine programming for the last 15 years. However, he’s not the only one publishing in the space. Five of the 21 references are of Armando’s work. That’s 24% of the citations coming from one person. The authors also introduce the field of program synthesis from Armando’s PhD dissertation on sketching. Please read the “Three Pillars of Machine Programming” (who Armando also co-authored) and note how those others refer to the space of machine programming by citing an original work in the 1950s by IBM on the future of Fortran. *This* in my opinion, is the paper to cite when you are saying this:
“Synthesizing programs from examples is a classic AI problem which has seen advances from the Pro- gramming Languages community (Solar-Lezama, 2008).”
A citation to a 2008 paper doesn’t demonstrate (at least to me) anything classic about the problem. But a 1950s paper, which means we’ve been working on it for 70 years probably would.

Moreover, in the related work section, there’s a bunch of citations to work in the last 5-10 years, which is great, but most don’t seem to provide any intuition about how these systems work, except those on execution-guided neural program synthesis. I’d recommend this section be rewritten with greater care to provide at least a basic intuition about how each of these related works relate 


Low-level concerns:

Please define all of your acronyms before you use them. I counted at least these: RNN, GRN, MDP, MSE, DSL, REPL. This is especially important because there are three disjoint communities being brought together here: the programming languages community, formal methods community, and the machine learning community. I think it’s unlikely except for experts in all three domains to implicitly know that DSL mean domain specific language and simultaneously knowing GRU means gated recurrent unit.


review_title: (Updated) Review of Representing Partial Programs with Blended Abstract Semantics

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes an embedding mechanism for partial programs for search space exploration in example-driven synthesis. It executes a sub-expression concretely whenever possible and applies neural module networks on vector representations otherwise. The embeddings of partial programs and goal states are used for determining the next step towards expanding an unfilled hole. This method is evaluated on three benchmark sets: tower construction, functional list processing and string editing.

The idea of using module networks to embed partial program states is nice and these embeddings are blended with concrete state representations. This combination is shown to perform better than concrete execution-guided synthesis or embedding program syntax (through an RNN).

I am not clear about the scope of this work, and whether it will generalize beyond these specific domains and bechmarks. The paper presents concrete and abstract denotational semantics. The examples and (some) benchmarks include loops. However, the semantics do not formalize the iterative semantics (in the concrete case) or the fixpoint semantics (in the abstract case). The training proceeds by imitation learning on the syntactic search space. Thus, the proposed method does not seem to address the inductiveness of loop invariants. A 'loop' is probably treated as any other function. How will this method then generalize to different loop bounds? It is possible that the training set contains enough examples for it to memorize patterns necessary for the test set. A more convincing evaluation would be to have benchmarks where training is restricted up to loop bounds, say k, and the test set contains programs with loop bounds m > k.

The functional list processing benchmark uses higher-order functions. The abstract interpretation of such programs requires reasoning about relational semantics. How are these semantics formalized and encoded by neural networks? In what ways can we expect the neural network to generalize?

The other problem is that of potential non-termination. It is easy to synthesis a non-terminating program even with finite loop bounds, for instance, if the loop counter is decremented in the loop body and never hits the loop termination condition. This is a problem that can make the synthesis procedure itself non-terminating, if such a loop is synthesized and is executed concretely. An abstract interpreter can also get into non-termination unless suitable operations (such as widening) are employed. The paper should talk about this issue and how it can be mitigated.

The semantics are not fully formalized. What is the initial state of a program? Are the values undefined or are they initialized to some default constants? This has a bearing on what can be executed concretely and what cannot be. The paper says 'buildColumn(1)' can be executed concretely since all its arguments are concrete. But doesn't it implicitly need the position of the cursor where the column should be built? I suppose the initial state of the cursor is assumed to be set to 0, which makes this a concrete statement.

The discussion about comparison to abstract interpretation needs more clarity. In particular, how the results of abstract interpretation are used should be stated. One might use a Hoare style reasoning to check whether the invariant implies the post-condition (outputs). However, here it is the opposite direction for one wants to check "realizability" of the partial program.

Please cite the original paper on abstract interpretation: "Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints" (POPL'77).

There is a typo in Sec 3. 'y =9' should be 'y = 7'.
review_title: Nice technique but incomplete semantics, and unclear scope and generalizability 

final_score: rating: 7: Good paper, accept
review_content: ### Summary

This paper proposes a novel top-down program synthesis for programming-by-example which combines concrete evaluation with neural embeddings. The authors take inspiration from abstract execution, which can execute partial programs by abstractly representing sets of possible execution states. Instead of hand-designing an abstract execution method, however, they propose a neural equivalent, which instead embeds possible states into a feature vector. While this approach has weaker guarantees than traditional abstract execution, it is much more flexible, and can be used as a powerful guiding function for execution-based top-down program search.

The paper is well written and was a pleasure to read. The method appears to be novel and is motivated well, and it shows strong results on a variety of program synthesis tasks, including tasks that similar previous models cannot handle. I do think that the authors should include some experiments with simpler tasks and more baselines, to give a better sense of how their method compares to prior work in the settings where that prior work is applicable. But overall, I think this paper is good and deserves to be accepted.

### Detailed comments

The paper describes three types of semantics:
- concrete semantics, where subexpressions of a (functional) program are evaluated to their concrete outputs according to the rules of a DSL
- neural semantics, where subexpressions of a program are embedded into feature vectors, and these feature vectors are transformed using DSL-based neural modules (i.e. a learned neural "sum" module is used to convert from embeddings of two integers to an embedding of their sum); this allows processing inputs that have holes in them
- blended semantics, which does a sort of partial execution: any subexpression that can be concretely evaluated is evaluated, then everything else is embedded and neural semantics are used to combine these concrete subexpressions with other partially-specified components.

Both neural and blended semantics make it possible to "execute" programs with holes in them, obtaining either concrete or neurally-embedded outputs. The authors propose using this as input to a policy $\pi$ that is trained to generate programs in the training set when conditioned on the corresponding input-output examples. They then additionally use this policy to train a value function that can be used to guide a search algorithm.

The experimental results cover three different domains: tower construction, list processing, and string editing. For the list processing domain, the authors note that previous approaches such as PCCoder cannot handle arbitrary lambda functions. The proposed blended-semantics model is able to work even in the presence of much more complex lambda functions, and the authors provide strong experimental results on an extended list-processing task with those complex lambdas. However, one thing that I think is missing is a comparison against PCCoder in the more limited domain in which both methods are applicable (the original domain without complex lambdas). Is there still value in using blended semantics in that domain, or is PCCoder better in the cases where it can be applied?

### Questions

During iterative construction of partial programs, do you allow the model to choose which hole to fill, or does the construction process require holes to be filled in some specific order (perhaps left-to-right)?

What does it mean to embed a hole "based on context"? Is the dictionary of bindings passed to a neural network in some way?

It's interesting that neural semantics can still be used even when there are concrete values. Have you considered using the concrete semantics as a regularization method for the neural semantics? For instance, by adding a loss term so that $[[f(x, y)]]^{nn} \approx [[f]]^{nn}([[x]]^{nn}, [[y ]]^{nn})$?

For end-to-end training, is the $Embed$ function trained jointly with the policy, but then fixed when training the value function? Or is there a different $Embed$ function used for the value function?

It's a bit unusual to use logistic loss when training a value function. Is this essentially a binary cross-entropy objective trained with successfull rollouts as positive examples and unsuccessful ones as negative examples?

Using "null" as the embedding of arguments to lambda expressions is an interesting choice. Does that mean that there's no way to tell which argument is which for lambdas with multiple arguments? (I also notice that appendix B.2 seems inconsistent with appendix A in this regard, stating that lambda arguments are embedded by name?)

It would be interesting to see some example programs that the method is able to produce, perhaps as part of the appendix. I'm also curious whether you have any intuition for what the neural semantics "mean" for a program with holes; have you done any analysis of this?

review_title: Interesting and novel program-synthesis technique, could use some additional experiments

final_score: rating: 7: Good paper, accept
review_content: # Positives

* (+1) Blended neural semantics is an elegant and intuitive construct.
* (+2) Performance seems to be good for interesting and non-trivial DSLs.

# Negatives
* (-1) Although the high-level description of the approach is intuitive, it is lacking many details. The experimental evaluation is distressingly vague.
* (-2) Comparison to baselines is poor. Although the main approach is compared to baselines introduced here (remove blended semantics, use just an RNN), it is not compared to most prior approaches on the benchmarks of those prior approaches.

1. I like this work and the main ideas are intuitive and well described. However, I found the paper disturbingly lacking in detail. I see some of that detail in the appendix, but information such as dataset size is essential in understanding results. It can't be in the appendix only.
1. Also, the paper seems to make some off-hand value judgments (pun intended) about prior approaches, without substantiation. For example, it claims that execution-guided synthesis isn't compatible with loop constructs, but no explanation is given for this. Similarly, the paper says that it can't possibly compete with REPL on an I/O synthesis task on the RobustFill DSL, but not explanation is given. This makes for a jarring reading experience.
1. Page 1, paragraph 2. Your introduction would be much more effective if you explained briefly the semantics for your DSL (even though it's relegated to the appendix). Otherwise, your example doesn't make sense. I don't know for instance what, precisely, ` buildColumn(1)`  means. Is `1`  the height from the bottom? Or the height of a column addition? Can I stack columns? Your text, for example, seems to imply that `buildColumn(1)` has no place in a solution to the example problem, because the column has height 1 (sentence right after the sketch example). However, the goal state on Figure 1 shows stacked columns of height 1. It's even more confusing that your appendix description of the DSL implies there are learned functions (presumably including `buildColumn`), which aren't shown here. All in all, this introduction confused me more than it sold me your work.
1. Page 2, paragraph 1. Somehow this text seems to suggest that higher-order functions and control flow are incompatible with approaches that don't know how to evaluate partial programs. That's not true, of course. REPL could do just fine in such a setting (in principle) but it would have to build the program bottom up, with all of the arguments of a higher-order function, before it composed them into an application of the higher-order function. What you haven't motivated yet is *why* we need to write unfinished code, rather than bags of expressions from which to compose the finished program. You haven't given any intuition or evidence of that. I suspect that the intuition comes from the fact that not all execution models can be interpolated (along the lines of string manipulation tasks or shape composition tasks, a la REPL), and therefore you can't just look at the output and expect to get good hints of the building blocks you need to compose greedily. Sometimes you need to choose a code idiom (a loop) before you choose what goes into the loop. It would help your paper if you made an argument why that makes sense in many cases.
1. Page 4. What's the embedding function for concrete expressions? 
1. Page 4. What's a precise definition of context? In the examples, you've shown value assignments to variables, but that doesn't allow for having multiple `HOLE`s in a program. Do you only allow one `HOLE`? The examples show multiple `HOLE`s, which suggests there must be some positional encoding involved, or different `HOLE`s would embed to the same vector given the same context.
1. Page 4. Are neural modules separate for every primitive operation? Even for learned functions? How many are there?
1. Page 6, Section 5.0. Why exactly aren't these domains covered by execution-guided synthesis? This is an oft stated limitation of prior approaches, but no evidence has been given. Why wouldn't REPL, for instance, fit the block world?
1. Page 6, how was test construction exactly? "combinations of motifs seen during training" isn't very precise.
1. Page 6. The policy isn't a cost function. You mean, presumably, the probability associated with the chosen action? Something else? Please explain.
1. Figure 4. Please explain your x axis. What are programs considered? In total? Per problem? After how much training? How big are the datasets?
1. Page 7. It seems a pity that you don't also compare to DeepCoder and FlashFill on the same datasets, rather than only extending the DSLs for your setting. It would be valuable to know how the approach works in those simpler DSLs.
1. Section 5.3, 3rd paragraph. The string DSL is on the right, not on the left in Figure 5.
1. Section 5.3. "We do not expect that our approach would outperform the REPL..." Why not? Explain.


review_title: Neural partial evaluation of sketched code

Meta-review: Four expert reviewers (after much discussion, in which the authors seemed to do a pretty good job addressing a lot of the initial complaints) unanimously voted to accept this paper. 

Everyone seemed to agree that the idea was interesting, and it is indeed interesting.
There were generally complaints about benchmarking; there always are for papers about program synthesis. 

One complaint I have, but that I didn't really see mentioned, is that the system as described is pretty baroque. 
I have a hard time imaging how you'd scale something like this up to more complicated contexts, 
and honestly I'm not sure even in some of the contexts where it was tested if it would really outperform a well-engineered
top-down synthesizer.
Maybe this is just an aesthetic preference that only I have, and maybe ideas need to start out overly complicated
before the most useful bits can be extracted from them and refined. 

At any rate, I do think that this paper gives a cool new research contribution and that people will want to read it, so I am recommending acceptance. 
Decision: Accept (Poster)