Representing Partial Programs with Blended Abstract Semantics
Authors: Maxwell Nye
Yewen Pu
Matthew Bowers
Jacob Andreas
Joshua B. Tenenbaum
Armando Solar-Lezama
Venue: ICLR 2021 Poster (2021)
Keywords: program synthesis
representation learning
abstract interpretation
modular neural networks

Abstract: Synthesizing programs from examples requires searching over a vast, combinatorial space of possible programs. In this search process, a key challenge is representing the behavior of a partially written program before it can be executed, to judge if it is on the right track and predict where to search next. We introduce a general technique for representing partially written programs in a program synthesis engine. We take inspiration from the technique of abstract interpretation, in which an approximate execution model is used to determine if an unfinished program will eventually satisfy a goal specification. Here we learn an approximate execution model implemented as a modular neural network. By constructing compositional program representations that implicitly encode the interpretation semantics of the underlying programming language, we can represent partial programs using a flexible combination of concrete execution state and learned neural representations, using the learned approximate semantics when concrete semantics are not known (in unfinished parts of the program). We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs, such as loops and higher-order functions, and can be used to synthesize programs more accurately for a given search budget than pure neural approaches in several domains.

Published as a conference paper at ICLR 2021
REPRESENTING PARTIAL PROGRAMS WITH BLENDED ABSTRACT SEMANTICS
Maxwell Nye
Yewen Pu
Matthew Bowers Armando Solar-L.ezama
Jacob Andreas
Joshua B. Tenenbaum
Massachusetts Institute of Technology
ABSTRACT
Synthesizing programs from examples requires searching over a vast, combinato- rial space of possible programs. In this search process, key challenge is repre- senting the behavior of a partially written program before it can be executed, to judge if it is the right track and predict where to search next. We introduce general technique for representing partially written programs a program syn- thesis engine. We take inspiration from the technique of abstract interpretation, in which an approximate execution model is used to determine if an unfinished program will eventually satisfy goal specification. Here we learn an approxi- mate execution model implemented as modular neural network. By constructing compositional program representations that implicitly encode the interpretation semantics of the underlying programming language, we can represent partial pro- grams using a flexible combination of concrete execution state and learned neural representations, using the learned approximate semantics when concrete seman- tics are not known (in unfinished parts of the program). We show that these hybrid neuro-symbolic representations enable execution-guide synthesizers to use more powerful language constructs, such as loops and higher-order functions, and can be used to synthesize programs more accurately for given search budget than pure neural approaches in several domains.
INTRODUCTION
Inductive program synthesis - the problem of inferring programs from examples - offers the promise of building machine learning systems that are interpretable, generalize quickly, and allow auto- mate software engineering tasks. In recent years, neurally-guided program synthesis, which uses deep learning to guide search over the space of possible programs, has emerged as a promising ap- proach (Balog et al. 2016 Devlin et al. 2017). In this framework, partially-construct are judged determine if they are on the right track and to predict where to search next. key challenge in neural program synthesis is representing the behavior of partially written programs, in order to make these judgments. In this work, we present novel method for representing the seman- tic content of partially written code, which can be used to guide search to solve program synthesis tasks.
programs
Consider tower construction domain in which a hand drops blocks, Tetris-style, onto vertical 2D scene (Figure l). In this domain, a function bui buildCo: 1 umn (n) stacks n vertically-oriented blocks at the current cursor location, and moveHand (n) moves the cursor π spaces to the right. Given an image X' of scene, our task is to write a program which builds a tower matching the image X. To do this, model can perform search in the space of programs, iteratively adding code until the program is complete. While attempting to synthesize program, imagine arriving at a partially-constructed program (short for sketch), where HOLE signifies unfinished code:
loop (4, [buildColume umn (1), moveHand (<HOLE>) })
Note that this partial program cannot reach the goal state, because the target image has columns of height 2, but this program can only build columns of height 1. For an algorithm to determine it should expand or explore another part of the search space, it needs to determine whether is
"oorrespnndence nolmye@@i t.edu

---

Published as a conference paper at ICLR 2021
SEARCH SPACE
RNN representation
lospés, s woo.1ddCouum HEL H0L )
Toop
bui Idblumm
soratfurd
HOLE
1oaa(4, (abllaala)
Noural abstract semantics
ENDED
Jumu
Loop
DPEED
Blended abstract semantics
1oop(4, seq
EMSED
g
movelland
HOLE
novelland
GOAL X'
search state representation
EMBED
Value V(s,
X)
Pulicy mie; X3
Figure 1: Schematic overview of the search procedure and representational scheme. We charac- terize program synthesis as coal-conditioned search through the space of partial programs (left), and propose a novel representational scheme (blended abstract semantics) to facilitate this search process. Left: a particular trajectory through the space of partial programs, where the goal is to find a program satisfying the target image. Right: three encoding schemes for partial programs, which can each be used as the basis of code-writing search policy and code-assessing value function.
on track to satisfy the goal. Answering this question requires an effective representation of partial programs.
Existing neural program synthesis techniques differ in how they represent programs. Some represent programs by their syntax (Devlin et al. 2017 Allamanis et al. 2018 producing vector represen- tations of program structure using sequence or graph neural networks. Recently, approaches which instead represent partial programs via their semantic state have been shown be particularly effec- tive. In these exeuutionguuided neural synthesis approaches (Chen et al.) 2018 Ellis et al., 2019 Zohar& & Wolf. 2018), partial programs are executed and represented with their return values. (To see why this is helpful, consider two distinct syntactic expressions 2 1 and 6/2; syntax-based model might assign them different representations, whereas a model using a semantic representation will represent both as equivalent to 3.) However, execution is not always possible for a partial program. In our running example, before the HOLE is filled with an integer value, we cannot meaningfully exe- cute the partially-writ written loop in This is common problem for languages containing higher-order functions and control flow, where execution of partially written code is often ill-defined] Thus, a key question is: How might we represent the semanties of unfinished code?
A classic method for representing program state, known as abstract interpretation (Cousot & Cousot, 1977), can be used to reason about the set of states that a partial program could reach, given the possible instantiations of the unfinished parts of the program. Using abstract interpretation, an approximate execution model can determine if an unfinished program will eventually satisfy a goal specification. For example, in the tower- bewirrbildinng domain, an abstract interpreter could be designed to track, for every horizontal location, the minimum tower height that all continuations are guaranteed to exceeded. However, this technique is often cow-precision models greatly overapproximate the set of possible execution states, and do not automatically adapt themselves to the strengths or weaknesses of specific search algorithms.
hand-designed abstract execution
We hypothesize that, by mimicking the compositional structure of abstract interpretation, learned components can be used to effectively represent ambiguous program state. In this work, we make two contributions: we introduce neural abstract semanties, in which a compositional, approxi- mate execution model is used to represent partially written code. This approach can be extended to blended abstract semantics, which aims to represent the state of unfinished programs as faith- fully as possible by concretely executing program components whenever possible, and otherwise, approximating program state with a learned abstract execution model.
See Peleg et al. 2020 for discussion the context of hottom-up synthesis.
2

---

Published as a conference paper at ICLR 2021
Consider again the partial program and the blended abstract semantics encoding in Figure | The sub-expression buildColmmg umn (1) is fully concrete, and can thus be concretely executed to ren- der image. On the other hand, for functions whose arguments are not fully defined, such as moveHand, we instead employ abstract neural modules to represent the execution state. For this example, blended neural execution makes it easy recognize that s is not suitable partial program, because no integer argument to moveHand- which controls the spacing between the columns- would make the state match the goal X.
This combination of learned execution and concrete execution allows robust representation of partial programs, which can be used for downstream synthesis tasks. Our approach can effectively learn to represent partial program states for languages where previous execution- isecuttio-guided guided synthesis techniques are not applicable. summary,
We introduce blended neural semantics, novel method for representing the semantic state of partially written programs inspired by abstract interpretation.
We describe how to integrate our program representations into existing approaches for learning search policies and search heuristics.
We validate our new approach with program synthesis experiments in three domains: tower construction, list processing, and string editing. We show that our approach outperforms neural synthesis baselines, solving at least 5% more programs in each domain.
2 RELATED WORK
Synthesizing programs from examples is classic Al problem (Backus et al. 1957) which has advances from the Programming Languages community (Gulwani et al. 2017]] Gottschlich et al.] 2018 Solar-Lezama 2008).
Neurally-guided search Recently, much progress has been made using neural methods to aid search. Enumerative approaches (Balog al., 2016; Shi et al. (020)) use neural methods to guide an enumerative synthesizer, and can be quite suitable for small-scale domains, but can scale poorly to larger programs and domains. Translation- synthesis as a sequence-to te-queenc problem, and employ state-of-the-ee neural sequence modeling techniques, such as recurrent neural networks (RNNs) with attention. Hybrid approaches which use sketches (Murali et al. 2017, Nye et al., 2019 Dong & Lapata 2018) trade off computation be- tween translation and enumeration components. These techniques can exhibit better generalization than translation-based approaches but more precise predictions than enumerative approaches (Nyc) ctt al. 2019). To combine neural learning and search, our approach follows the framework laid out in Ellis et al. (2019), where neural networks are used guide search over the space of possible partial programs defining a Markov decision process (MDP).
techniques (Devlin et al. 2017) treat program
Program representation Prior work has studied neural representation of programs. Odena & Sutton (2019) propose property signatures to represent input-output examples, and use property signatures guide enumerative search. Graph neural networks have also been used encode the syntax of programs (Allamanis et al. 2018 Brockschmidt et al. 2018 Dinella et al., 2019) for bug fixing, variable naming, and synthesis. This work has mostly focused on performing small edits programs from real datasets. Our objective is to synthesize entire programs from specifications.
Execution-guided synthesis Recent work has introduced the notion of "execution-guided neural program synthesis" (Ellis et al. 2019 Chen et al. 2018 Zohar & Wolf 2018). In this framework, the neural representations used for search are conditioned on the executed program state instead of the program syntax. These techniques have been shown to solve difficult search problems outside the scope of enumerate or syntax-based neural synthesis alone. However, such execution-guiie guided approaches have several limitations. be applicable to a wider range of domains, search techniques, and programming language constructs.
We aim to generalize execution guided synthesis, that it can
Abstract Interpretation Our work is directly inspired by abstract interpretation-basse synthesis (Singh & Solar-Lezama 2011 Wang et al.) 2017, Hu et al.) 2020). These approaches use abstract interpretation (Cousot & Cousot 1977) to determine if candidate partial program is realizable under the given specification, thereby pruning the search space of programs. We see our approach as learning-based extension to this line of work.
3

---

Published as a conference paper at ICLR 2021
Neural Modules We employ neural module networks (Andreas et al. 2016 Johnson et al. 2017) to implement blended abstract semantics, which aims to provide a learned execution scheme inspired by abstract interpretation. This approach is also related to other tree-structured encoders (Socher
et al. 2011 Dyer et al. 2016).
3 BLENDED ABSTRACT SEMANTICS
Consider the problem of synthesizing arithmetic expressions from onput-output pairs. Suppose we have the following context-free grammar for expressions:
1
2 3
1
and a specification X' consisting of the ontutt pairs {(x 3,y 7), = 5.y= 11)}.
Suppose further that we have a candidate program (2 x) + 1 E G. To check that this pro- gram consistent with the specification, we can evaluate on the inputs x the specification according to the concrete semantics of the language: to evaluate (2 x)
1 on the example (r=3) 3, = 7), we observe that the expression (2 * x) evaluates to the integer 6, and the expres- sion evaluates to the integer 1; thus the whole expression evaluates to as desired. Repeating this process with x = returns the value 11.
Formally: Let C denote context (c.g. (x=3))) The concrete value of an expression E in context is
[k]]c- = k
constant k:
[E] [=]c= =
variable æ is evaluated to its value in the context [f(E) ... lc ([[ilee)( recursively evaluate the arguments, then run f
The goal of synthesis is to find an expression
[E] = under concrete semantics.
Iterative construction of partial programs Where did the expression (2 x) 1 come from? Neurally-guided synthesis techniques generally employ discrete search procedures. In this work, we top-down search: starting with the top-level (incomplete) expression HOLE, we con- sider all possible expansions, (HOLE + HOLE HOLE, HOLE - 1, HOLE + 2, 2....) and select the one we believe most likely to succeed (Figure leftt. Concrete semanties cannot be used for this selection, because expressions such as x + HOLE are incomplete and cannot be executed. Thus, we need a different mechanism to guide search. The more effectively we can filter the set of incomplete candidate programs, the faster our synthesis algorithm will be.
Conventional abstract interpretation solves this problem by defining an alternative semantics for which even incomplete expressions can be evaluated. Consider the candidate expression HOLE 2. No matter how the HOLE filled, the expression returns an even number, so it cannot be consistent with the specification above. In many problems, values" (like even integer) and abstract semantics so that the abstract value of a partial program can be determined. This allows to rule out partial programs the basis of the abstraction alone (Wang et al. (017). However, constructing appropriate abstractions is difficult and requires domain- specific engineering; ideal procedure would automatically discover effective space of abstract interpretations.
define space of "abstract
Neural abstract semanties [|]an As first step. we implement the abstract interpretation pro- cedure with a neural network. This is natural choice: neural networks excel at representation learning, and the goal of abstract interpretation is to encode an informative representation of the set of values that could be returned by a partial program. For the program 1 + HOLE, we can encode the expression to a learned representation (Figure 2p, top), likewise encode HOLE (Figure and finally employ learned abstract implementation of the operation (Figure
For concrete leaf nodes, such as constants or variables bound constants, neural semantics are given using state embedding function EMBED(-), which maps any concrete state in the programming language into a vector representation: EMBED : (State IR4) - Rd. If the input to EMBED is already vector-valued, EMBED performs the identity operation. Neural placeholders provide
Domains with lambdas have slightly more complicated semantics. See Appendix for details.
4

---

Published as a conference paper at ICLR 2021
(8)
h
(d)
EMBED
EMBED
(c)
HOLE
EMBED
HOLE
CONTERT
Figure 2: (a) Example applications of the EMBED function. (b) Neural abstract module for +. (c) Neural placeholder module encoding a HOLE with the context {ar = 3). (d) Neural abstract semantic encoding of the partial program 1 HOLE with the context < 3/.
a method for computing vector representation of unwritten code, denoted by the HOLE token. To compute the representation for HOLE, define neural embedding function h which takes a context C and outputs vector. For each built-in function f (including higher-order functions), the neural abstract semantics of are given by a separate neural module learned vector-valued Therefore, computing the neural
function as in Andreas et al. (2016)) [ with the same arity semantics means applying the neural function [ to its arguments, which returns a vector. Since the neural semantics mirrors the concrete semantics, its implementation does not require changes to the underlying programming language. Formally, neural semantics involve a slightly larger set of cases than concrete semantics:
[+ = EMBED(K)
a constant k is embedded embed the value of the variable a neural placeholder based on context using neural module [f]mm
c EMBED(U)
[E
[HOLE]E = h(C)
[f(EE IE = [f] ([E,lE
This encoding is only one way define neural semantics, adopting a relatively simple and generic representation for all program components. For discussion of its limitations and other, more so- phisticated representations that could be explored in future work, see Appendix C.
Blended abstract semantics Ie] Notice that for expression such (2 x) + HOLE, the concrete value of the sub-expression (2 x) is known, since it contains no holes. The neural semantics above don't 't't make use of this knowledge. To improve upon this, we extend neural seman- tics and introduce blended semantics, which alternates between neural and concrete interpretation appropriate for given expression:
If the expression a constant or a variable, use the concrete semanties.
If the expression a HOLE, use the neural semantics.
If the expression is function call, recursively evaluate the expressions that are the argu- ments to the function. If all arguments evaluate to concrete values, execute the function concretely. If any argument evaluates to a vector representation, transform all concrete values to vectors using EMBED and apply the neural semantics of the function.
Formally, can write:
[ blend
[k]
constant
Ix: [aleepasp
variable x in context
[ETblend
[HOLE] biend [HOLL h(C) [S(E ... M[ennd = [[ Mendd ...)
neural placeholder based on context
if all arguments are concrete
[f(E) J..lledd [ (EMBED( blnnd).... if any arguments are vectors
Because blended abstract semantics replaces concrete sub- sub-components with their concrete values, we expect blended semantics to result more robust representations, especially for long or complex programs where large portions can be concretely executed.
5

---

Published as a conference paper at ICLR 2021
4 PROGRAM SYNTHESIS WITH BLENDED ABSTRACT SEMANTICS
To perform synthesis, we experiment with methods to guide search introduced in Ellis et al. 2019 In this work, the search over partial programs is formulated as an MDP, in which each state is pair (s) consisting of a of HOLES under rules under the grammar. We assume reward of for programs which satisfy X. In this framework, we learn to search by training a policy T[as,, X) that proposes expansions to s, and optionally value function (s,, X¹) that predicts the probability that X is solvable via any expansion of s.
and a specification, and actions a E g are expansions
Let X' {( 34), where (Ig, y1) are input-output pairs. Let [s]blend denote the blended abstract semantic representation of s with input Ti. The representation of state rep(s, is:
rep(s, 1
Σ ReLu(W ([[>)
([I=); EMBED()))))
Here, W is a learnable weight matrix, and the representation is averaged across all input- pairs of X. Given this state representation. the policy and value function are:
<(a 8. = so softmax(MLP a(rep(s,
(ss, X) a (MLL V(rep(s,
Here, MLP is multi-layer perceptron. Note the value function outputs a value between and 1; this allows for probabilistic interpretation (see below).
End-to-end training We train our policy æ using imitation learning. Starting from the empty partial program So HCLE, generate sequence of partial programs 82, by sampling sequence of expansions ag, 01. ... from the grammar G. Let = sT be the completed program. We obtain specifications X { (x,, }:)} by sampling set of inputs 21 TI and obtaining outputs using concrete semantics 3/1 = [p].. Thus, from a sequence
expansions ag; Ø1 ".,, we can collect set of triplets {(X', 8;, a training data. This process is repeated to generate the training set D. We can then perform supervised training, maximizing the log likelihood of the following:
((T) <xx,, [log nogg(ee X))
We train the value function by sampling rollouts of partial programs so s. from fully-trained π, minimizing the error in Monte-Carlo estimate of the expected reward (i.e., the probability of success under the policy).
RL (V) = E (.))) (o.))
Σ (s,,
IST
For our error function, we use logistic loss rather than the more common mean squared error (MSE).
Search We explore variety of code-writing search algorithms. Using only a policy, can employ sample-based search and best-first search (where the log probability of generating under is used as the scoring function). With the addition of learned value function, can perform A based search with - log V (s) as heuristic (see Ellis et al. (2019) for details).
EXPERIMENTS
We evaluate our model in two domains containing language con- structs not handled by concrete execution-guided synthesis ap- proaches: a tower-building domain with looping constructs, and a list- prtcersccsing domain with higher order functions. We additionally test on a string-editing domain for which execution-guided synthe- sis is possible, but requires language modification; there, exam- ine how our approach fares without these modifications.
Figure 3: Example tower- building constructions.
We briefly review these methods here, but see Ellis et al. (019) for more details.
*Ottnn PCFG is used sample these expansions. See Appendix B for details.

---

Published as a conference paper at ICLR 2021
Tower Building
Tower Building comparison abstract interpretation
120
polccy
Bianded semartics policy ony (ours)
semantic palicy only
AhN policy only
Burel
Percent correct
Preciston
Blended semantics (ours)
0.4
Hand coded abstract merpretation
70-
2500 5000
7500
10000
12500
15000 17500
0.2
0.4
1.0
Number partial programs considered
Figure 4: Left: Overall synthesis results in the tower-building domain. We plot the percentage of test problems solved as function of the number of partial programs considered per synthesis problem. Right: Comparing the value function to a hand-coded abstract interpretation. Blended abstract semantics outperforms baselines in synthesis tasks, and obtains higher classification precision than hand-coded abstract interpretation.
5.1 LOOPING CONSTRUCTS: TOWER CONSTRUCTION
We begin by investigating how our model performs in generative programming domains with higher- level control flow such as loops. Looping programs are an essential part sophisticated program- ming languages, and aren't naturally handled by previous execution-guii -uriiedd synthesis approaches. Our experiments the lower-building domain employ a domain specific language (DSL) similar to the language depicted in the introduction construct towers in 2D world, adapted from Ellis eet al. (2020). This domain is inspired by classic Al tasks (Winston) 1972). It is also related to im- portant problems the AI literature, such as generalized planning, where plans can be represented as programs, and often require looping constructs (Jiménez et al. 2019 Srivastava et al. 2015).
As above, the goal is construct program which successfully renders target image (exam- ples in Figure 3) Language details can be found in Appendix B. We compared against two abla- tion models (see Figure I (1) Neural abstract semanties (defined Section 3 which does not apply concrete execution to concrete subtrees, and (2) RNN encoding, which encodes partial pro- grams using a gated recurrent unit (GRU): x(a GRU enc(s), We also consider an additional encoder-decoder baseline. This baseline uses convolutional neural network (CNN) to encode the specification image, and then employs an LSTM decoder to decode the tokens of the target program, while attending over the image representation via Spatial Transformer Network attention (Jaderberg et al. 2013). This baseline is inspired by the architecture used for the Karel domain in [unel et al. (2018), , with the addition of spatial attention. We train all models on 480,000 programs sampled from the DSL. More details can be found in Appendix B.
To evaluate model, constructed test set of tower-building problems involving combinations of tower-building motifs seen during training. Tower objects seen during training were composed in previously unseen ways, by stacking towers top of each other, placing them side-by-side We evaluate our models by performing best-first search from the learned policy. We also evaluate value-guided heuristic search using the A algorithm with the negative log likelihood of the policy as the prior cost and the value function as the future cost estimate.
Synthesis results Figure shows our overall synthesis results in the tower-building domain, measuring the percentage test problems solved as a function of the number of search nodes (partial programs) considered per problem. The sequence encoding performs poorly and is unable solve majority of test problems. The neural abstract semantics model achieves better performance, solving about half of the test problems within the allotted search budget. Blended execution outperforms each baseline. We also observe that adding a value function as a search heuristic further increases performance of our blended model, which consistent with the findings in Ellis al. (2019).

---

Published as a conference paper at ICLR 2021
Comparison to abstract interpretation How does the learned value function compare to hand- coded abstract interpretation? During synthesis, we can use abstract interpretation to prune the search space by rejecting candidate partial program candidates for which the desired output state is not within the abstract state achieved by executing the partial program (Singh & Solar-Lezama 2011 Wang al. 2017 Hu et al. 2020). Used in this way, classic abstract interpretation con- servative; it can be thought of as a classifier with perfect recall, but poor precision, only rejecting the partial programs it knows for sure to be unsuitable. Can our value function also detect these clearly bad partial programs, but ascribe low value to less obviously bad candidates? To test this, we conditioned the model on tasks from our test corpus, and sampled 15 search trajectories from our blended semantics policy for each task. For each partial program encountered during search, we compute the model's i value judgment, and recorded whether each rollout was successful. Treating rollout success as a noisy label of partial program quality, and using the value function as a classifier, we plot precision vs recall of the value judgements as we vary the classification threshold. Figure 4 rright shows our results for this experiment. As the classification threshold is varied, our learned value maintains comparable recall compared to the hand-coded abstraction, while achieving better precision. For high classification thresholds, hand-coded abstract interpretation, and additional precision is gained by lowering the classification threshold. The RNN value performs worse on this test, achieving lower precision and recall.
model achieves performance comparable to the
5.2
HIGLERR-RRERR FUNCTIONS: FUNCTIONAL LIST PROCESSING
List Processing
String Editing
Examples
Program
Examplas
Program
[-4,9,4,6] [18.12] [35,3,3, 6,0,6,6)
(Xx.xf2) (filter
769 858 (763)
Const('(') GatToken(Nurberr, 1) Const(')))
0od xx3--00) input)
+63 099-824-351 (099)
[1,24,-1] [0.6.6.0]
[1,2,3,4]
[5,5.5.5]
zipwith (x.y.xtt))
(input) (reverse iipuu))
vartya Sergienko Nartya Andrew Cencict or. Andrew
Const('o') Const('r')
Conse ") const(" ")
GetToken(Koro, 0)
Figure 5: Example programs from the list processing (left) and string editing (right) domains.
In our second experimental domain, we seek to answer two questions: How well does our model per- form on input-output synthesis? How effectively can it synthesize programs containing higher-order functions? Although previous work (Zohar& & Woll 2018) has successfully applied execution-guider approaches to list processing (using the DeepCoder language), the use of higher-order functions was severely limited: only a small, predefined used as arguments for higher-order functions. For example, synthesizing program which "filters all elements divisible by 3 from a list" not possible with this DSL. However, in real programming lan- guages, higher-order functions must be able accept combinatorially large set of possible lambda functions as input. This presents a challenge for execution- guided synthesis approaches such as
of "lambdas," " (such as (+2) is even, (>0) ) were
String Editing
Processing
102
100
RCFL lupper bourd)
Blended semannics (ound)
Stunced sementi Jours)
Neura semrartics
Noural semantics
Robustni
60-
RAN
Percent correct
60
Percent
40-
20-
3003 of partial programs considered
2000
4000
5000
2003
L0000
12000
Number of partial programs cons dered
Synthesis results for string edit- ing. Blended semantics outperforms all base- lines, except for the execution- -uiiddd REPL model, which relies domain-specific lan- guage modifications.
Figure 7:
Figure 6: Synthesis results for list process- ing. Models were trained and tested on pro- grams each containing 2-3 higher order func- tions with lambdas of depth 3.
8

---

Published as a conference paper at ICLR 2021
Zohar & Wolf (2018). for which the assumption of small set of lambda functions is key. To this end, we modified the Deepcoder DSL to allow a richer set of possible programs. We replaced the predefined set of lambda functions with grammar allowing for the combinatorial combination of grammar elements (examples Figure left). The modified grammar is given in Appendix B. All models trained on 500,000 training programs.
Results Figure shows the results of synthesis using best-first search from policy on test prob- lems sampled the same distribution as the training problems. Our blended model and our neural se- mantics model both outperform the RNN baseline, achieving 5- 10% higher accuracy given the same search budget. We additionally implemented the DeepCoder model (Balog al. 2016). which con- ditions the search only on input-output examples and not partially constructed programs. This model achieves considerably lower accuracy for given search budget. The blended model also yielded superior results on numerous variations of these tasks (increasing number of higher order functions, varying integer ranges, performing sample-based search, etc). In the sample-based search condition, we also compare against a RobustFill baseline, which is outperformed by blended semantics. See Figure in Appendix B for details.
5.3 I0 PROGRAMMING: STRING EDITING
In our final experiment, we examine how our model performs on domains for which execution- guided synthesis is possible, but requires extensive changes to the underlying DSL.
For example, in the RobustFill DSL,, function getSubStr r (i, j) slices a string from index to index j. This function not executable until both and j are known. In order to perform execution- guided synthesis, EElis et al. 2019) needed to replace get SubString with two separate functions: getSubSt rStart_i and getSubstrEnde
where each half can be executed in the read-eval- print loop (REPL). This process must be performed manually for every language construct which takes multiple arguments.
Here we seek determine whether model synthesize programs using the language is. To this end, we implement the code-writing policy using the DSL presented Devlin et al. (211)) without modification (example programs in Figure right). Because the REPL system in Ellis et al. (2019) uses domain-specifte hand-designed partial program executor in-the-loop, we do not expect our approach (which must learn to approximate the semanties) to outperform the REPL system; however, it can recover some of the REPL system's improvement over ordinary (syntax-based) synthesis. We additionally compare against another relevant baseline: RobustFill (Devlin et al. 2017). In contrast to the original paper, we train the RobustFill model using the same "unmodified" version of DSL as our model, whose syntax has not been modified to aid with prediction. We train all models on 2 million programs sampled from the DSL. At test time, used a sample-basee based search procedure, because the branching factor is prohibitively large for breadth first search procedures explored above. While the blended encoding does not achieve the accuracy of the execution guided REPL system, it outperforms the other baselines, including the RobustFill model, neural abstract semantics and the RNN baseline.
6 CONCLUSION
We introduced blended abstract semantics, a method for representing partially written code based on concrete execution and learned approximate semanties. We demonstrated how our approach, which combines abstract interpretation with representation learning, can be trained end-to-end as the basis for search policies and search heuristics. In program synthesis tasks, models equipped with blended abstract semantics outperformed neural baselines in several domains. Immediate future directions include exploring the use of blended abstract semantics for other synthesis tasks, including programming from language instruction and bug fixing. More generally, we hope that approaches which integrate learning and symbolic methods can be used to build systems which can write code more effectively and robustly.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
The authors gratefully acknowledge Kevin Ellis and Eric Lu for productive conversations. We addi- tionally thank anonymous reviewers for helpful comments. M. Nye is supported by an NSF Graduate Fellowship and an MIT BCS Hilibrand Graduate Fellowship.
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018.
Rajeev Alur, Dana Fisman, Rishabh Singh, and Armando Solar-Lezama. Sygus-comp 2016: Results and analysis. arXiv preprint arXiv:1611.0762. 2016.
Jacob Andreas, Mareus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 39-48, 2016.
John W Backus, Robert J Beeber, Sheldon Best, Richard Goldberg, L Mitchell Haibt, Harlan Herrick, Robert A Nelson, David Sayre, Peter B Sheridan, H Stem, et al. The fortran automatic coding system. Papers presented at the February 26-28, 1957, western joint computer confer- ence: Techniques for reliability, pp. 188-198, 1957.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv:/611.01999 2016.
Marc Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint wrXiv:1805.084/ 2018.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. arXiv preprint arXiv:1805.04276, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. ICLR, 2018.
Patrick Cousot and Radhia Cousot. Abstract interpretation: a unified lattice model for static anal- ysis of programs by construction approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPIAN symposium on Principles of programming languages, pp. 238-252, 1977.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. arXiv preprint 2017.
Elizabeth Dinella, Hanjun Dai, Ziyang Li, Mayur Naik, Le Song, and Ke Wang. Hoppity: Learn- ing graph transformations to detect and fix bugs in programs. In International Conference on Learning Representations, 2019.
Li Dong and Mirella Lapata. Coarse-to-fi decoding for neural semantic parsing. arXiv preprint 1oXiv:800500470 2018.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. Recurrent neural network grammars. arXiv preprint urXiv:1602.07771 2016.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Pro- cessing Systems, pp. 9165-9174, 2019.
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Growing gen- eralizable, interpretable knowledge with wake-sleep bayesian program learning, arXiv preprint arXiv:2006.08330 08381, 2020.
10

---

Published as a conference paper at ICLR 2021
Justin Gottschlich, Armando Solar-Lezama, Nesime Tatbul, Michael Carbin, Martin Rinard, Regina Barzilay, Saman Amarasinghe, Joshua B Tenenbaum, and Tim Mattson. The three pillars of machine programming. In Proceedings of the 2nd ACM SIGPLAN International Workshop Machine Learning and Programming Languages, pp. 69-80, 2018. 2018.
S. Gulwani, O. Polozov, and R. Singh. Program Synthesis. Foundations and Trends(r) in Pro- gramming Languages Series. Now Publishers, 2017. ISBN 9781680832921. URL https:
htwooks.
Qinheping Hu, John Cyphert, Loris D' D'Antoni, and Thomas Reps. Exact and approximate methods for proving unrealizability of syntax-guided synthesis problems. arXiv preprint 000887, 2020.
Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al. Spatial transformer networks. In Ad- vances in neural information processing systems, pp. 2017-2025, 2015.
Sergio Jiménez, Javier Segovia-Aguas, and Anders Jonsson. A review of generalized planning. 2019.
Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Judy Hoffman, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Inferring and executing programs for visual reason- ing. Proceedings of the IEEE International Conference on Computer Vision, pp. 2989-2998, 2017.
Vijayaraghavan Murali, Letao Qi, Swarat Chaudhuri, and Chris Jermaine. Neural sketch learning for conditional program generation. arXiv preprint arXiv:1703.05698, 2017.
Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. arXiv preprint vrXiv:/902.000 2019.
Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference Learning Representations, 2019.
Hila Peleg, Roi Gabay, Shachar Itzhaky, and Eran Yahav. Programming with read-eval-synth loop. Proc. ACM Program. Lang, (OOPSLA), 2020. URL htttps://cswweb. ucsd. edu/
hheeeeg/ resl 1.0.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018.
Kensen Shi, David Bieber, and Rishabh Singh. Tf-coder: Program synthesis for tensor manipula- tions. arXiv preprint arXiv:2003.09040, 2020.
Rishabh Singh and Armando Solar-Lezama. Synthesizing data structure manipulations from story- boards. In Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering, pp. 289-299, 2011.
Richard Socher, Cliff Chiung Yu Lin, Andrew Y Ng. and Christopher D Manning. Parsing natural scenes and natural language with recursive neural networks. ICML, 2011.
Armando Solar-Lezama. Program synthesis by sketching. PhD thesis, University of California, Berkeley, 2008
Siddharth Srivastava, Shlomo Zilberstein, Abhishek Gupta, Pieter Abbeel, and Stuart Russell. Tractability of planning with loops. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Xinyu Wang, Isil Dillig, and Rishabh Singh. Program synthesis using abstraction refinement. Pro- ceedings of the ACM on Programming Languages, 2(POPL):1-30, 2017.
Patrick Winston. The mit robot. Machine Intelligence, 1972.
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. In Advances in Neural Information Processing Systems, pp. 2098-2107, 2018.

---

Published as a conference paper at ICLR 2021
A
SEMANTICS
Here we fully define the semantics for concrete, neural, and blended semantics, covering details that omitted in the main paper, namely, the semantics of lambda expressions.
Concrete semantics In this work, we consider domains where the underlying programming lan- guage functional. Let Ar.F be lambda expression of one argument, and let v be assignment of the variable z to the value v. Lambda application is defined as follows:
(Az.E)(o) [==0)
That is, evaluate the function body E, replacing all instances of the function variable with the value v. For example, + I + x (z=5) = 5+5 10, where + denotes the execution semantics of the built-in function + The concrete semantics [+]] is defined:
[ =
a constant
[=]c=o=v=]] =
[E]c
[s(E) le f([Elee...) [(Ax1 EEI, .. En)lc [oooc=[lleuurrra [ (E..le
executing built-in
[E,]e)
lambda application
Neural semanties For built-in functions we use f neural module function of l vector inputs, where l is the arity of f. We note that our treatment of functions discussed here applies to both first-order and higher-order functions.
In our domains, lambda expressions are only used as arguments to higher-order functions. Therefore, since we will never apply lambda expression directly under neural semanties, we only require vec- tor representation of lambdas. However, we still require a mechanism to represent arbitrary lambda expressions built combinatorially from primitive functions. This representation constructed in modular fashion by encoding the body E of the lambda expression.
[ nm C
EMBED(K)
a constant & is embedded embed the variable when the value is null embed the value of the variable x neural placeholder for hole based context using neural module encode the body of lambda
[x mM
EMBED "x")
null mull
Telep EMBED(")
[E]
[HOLE]E" h(C)
[s(Ei .... 11 mm (E
[A (
Note that representing lambda expression, we used the context with the assignment x null. This is used to account for the fact that, at the time of the lambda function's 's definition (as an argu- ment to a higher-order function), its argument is still unknown under neural execution. Likewise, to represent variable whose value has been assigned to null, we return vector representing the variable.
The definition for blended semantics proceeds in analogous fashion, with concrete subtrees exe- cuted concretely.
B EXPERIMENTAL DETAILS
All models are trained with the AMSGrad (Reddi et al. 2018 variant of the Adam optimizer with a learning rate of 0.001. All RNNs are I-layer and bidirectional GRUs, where the final hidden state used as the output representation. Unless otherwise stated, holes are encoded by applying the EMBED function to the context, and then applying type-specific neural module to the resulting vector. For the tower and string-editing domains, which use inniiuuttion-pasiine style, holes are filled in left-to-right. For the list editing domain, holes are filled in right-to-left.
B. TOWERS
We employ the tower-building domain and DSL introduced Ellis et al. (000). which consists of the basic commands: slaceHorizontalla all PlaceVert: i ca B Booc, MoveHand,
12

---

Published as a conference paper at ICLR 2021
ReverseHand, Embed, Loop and integers from to 8. (The higher-order Embed function takes an expression as input, executes it, and then returns the hand to its initial location.)
Formally, the syntax of the tower-building domain is given as follows:
P [S]
embed moveHand (n) reverseHand () loop (n, P) placeHorizontalBllcch () | placeVerticalBlock ()
1..8
A program is executed sequentially one statement (S) at a time, with each statement modifying the state of the tower construction. In tower construction, state is defined follows:
state: (handLoc, handOrientation, history) history: [1ooc, blockType)]
Loc: (x:int, y:int)
We assume the initial tower state is: (0, (1)
The semantics of applying each statement S applied to a state s is as follows:
placelorriootalBllock placeBlock (3, 1)
placeHoriizontalBlock placeBlock (1,
placeBlock (w:int, h:int) s:state ->
hs.handloc, s. handOrientation,, s.history h/s.handloc.x,
topy (s .hsstory, s.handLoc.x, s.handLoc. x-w) ) w, h)
topY (history, xlow, xhigh) max y y y'th
where ((',y'', w, in history
and [x, xt#] intersect [xlow, xhigh])
movelland (diis:int) sistate handooo s. w.anndriientaiionddis.. s. s.handOrientation, s. s.history)
reversefland :): s:state -> handooo, s. s.hand0rientationn-11 s.history)
1cop (n:int, fn): s:state -> fs"n(s)
embed (fn) s:state ->
1et s' (s) in (s handdoc, s.handOrientation s .history)
In order to test the compatibility of our approach with library-learning techniques, we additionally use library functions learned by the DreamCoder system by combining the above functions. Follow- ing Ellli et al. (2020), the grammar is implemented in continuation paaauaaatoo--sssinnggg style. Our training data consisted tower programs randomly sampled from a PCFG generative model (Ellis al. 2020).
We trained policy networks on 480000 programs. We trained value functions on 240000 rollouts from policy. We perform search for up to 300 seconds per problem.
For the blended semantics and neural semantics models, all neural modules consist of a single linear layer (input dimension 512 margs and output dimension 512) followed by ReI.U activation. Tower images embedded with simple CNN-R&LU-MaxPood architecture, in Ellis et al. (2020).
For the tower-building domain, we also include a baseline inspired by Bunel et al. (2018). This model uses a CNN image encoder to encode the spec tower image. The image representation is passed through an MLP layer and initializes an LSTM decoder, which sequentially decodes the program tokens. As additional modification the original model from Bunel et al. (2018), at each decoding step we perform spatial attention over the image encoding via a Spatial Transformer Network (Jaderberg et al. 2015). Our CNN image encoder consists of 4 convolutional layers (Conv
13

---

Published as a conference paper at ICLR 2021
ReLUU with kernel size 3, and single max- max-pool of size after the first convolution. Our LSTM decoder has hidden size 512 and embedding size 128.
Hand-coded abstract interpretation We implemented an abstract domain which tracked, a) the range of possible locations of the "hand" and b) for each horizontal location, the minimum height which must be achieved by the partially constructed tower. This representation allows us to elim- inate invalid partial programs because once block is dropped, it cannot be removed through any subsequent commands.
B.2
LIST PROCESSING
Data for this domain was generated by modifying the DeepCoder dataset (Balog et al. 2016). Specif- ically, DeepCoder training programs of size 2 (containing 2-3 higher order functions, such map (map 9 input) (map h input) ) were mod-
(filter 9 input. ) or 2 zipwith ified by changing the lambdas in the program (f, 9, and h in the above examples) from small set of constant lambdas such as (* to depth-3 lambdas sampled from our modified grammar (see below). For example: (Ax. sampled, each with length 10 and values in the range [-64, 64). The program was then executed to yield the corresponding outputs. Programs with output or intermediate values outside of the range [-64, 64) were discarded. Programs producing the identity function or constant functions were also discarded. We trained and tested only on functions type [int] - [int]. At test time when running search, we similarly reject programs with intermediate values outside of the desired integer range.
x/22))/2) For each program, 5 example input lists were
All policy networks were trained on 500000 programs. We perform search for 180 seconds per problem.
All neural modules consist of single linear layer (input dimension 64 narge and output dimension 64) followed by ReLU activation. Integers are encoded digit-wise via a GRU. Lists are encoded via GRU encoding over the representations of the integers they contain.
Unbound variables within lambda function are embedded via learned representation parameter- ized by the variable name (one vector representing and one representing y). When encoding holes within lambda functions, we ignore context, and instead embed holes only as a function of the hole type.
The DeepCoder baseline is based on Balog et al. (0066) but uses the same input-output example en- coding architecture the other methods implemented here. Our implementation uses MLP with 64-dimensional hidden layer with a tanh activation to produce the production rule probabilities from the input-output encodings.
In the sample-based search condition in Figure g we additionally compare against a RobustFill model. Our RobustFill implementation is equivalent the "Attention-A" model from Devlin et al. 2017). We use GRUs of hidden size 64 and embedding size 64, in keeping with the models above.
Modified lambda grammar Below is the grammar used for lambda functions:
+
(Xx, y.S)
()x.S)
S +
B
I+I
I+I
I/I
min (I, I) max (I, 1 T8I==0
B + T
I
or
(B, B)
and (B, B)
+ y 1
N + -2
-11
0 111
Variations on training and testing conditions Many variations the training and testing condi- tions achieve similar results to those shown in the main paper (i.e., blended semantics consistently achieves the highest performance). Several of these variations shown in Figure
14

---

Published as a conference paper at ICLR 2021
B.3 STRING EDITING
For the string editing tasks, we use the DSL from Devlin et al. (017)) We train on randomly sampled programs, sampling I/O pairs and propagating constraints from programs inputs to ensure that input strings are relevant for the target program (see Devlin et al. (2117)) We condition on 1/O examples for each program. We used string editing problems from the SyGuS (Alur et al. 2016) program synthesis competition as our test corpus. We trained all models on 2 million training programs. At test time, we sample programs from the model for a maximum timeout of 30 seconds.
Input and output strings are encoded by embedding each character via a 20-dimensional character embedding and concatenating the resulting vectors to form a representation for each string. Repre- sentations of "expressions" e (as defined in the RobustFill DSL) are concatenated together using an "aappedd" module. Following Ellis al. (2019), neural modules consist of a single dense block with 5 layers and growth rate of 128 (input dimension 256 argg and output dimension 256).
Processing Vari Range [-32,32]
Processing Variation: Sample-B Search
1.00
Reuural temantice
semount
Percent correct
Percent correct.
60-
60-
20200
2000 Number partial programs considered
500
Number of partial pro considered
List Processing Variation: Integer Return Values
List Processing Variation: More Higher Order Functions
100
Bunded ssmariia bara
Slensed sament a (cata) Wears seantics
Kruzi remartice
20
Percent correct
Percent
40-
20-
20
5002
30000
25000
20100
25200
5000
12000
25000
20020 25:00
Number of partial programs considerad
Number of partial programs considered
Figure 8: Variations on the list processing task. Top Left: using integer values in the range [-32, 32] instead of [-64, 64]. Top Right: using sample-based search instead best-first search, including a comparison to RobustFill. Bottom Left: extending the training and testing data to allow for [int] + int functions and with [-32,32] as the range. Bottom Right: the original model tested on deeper DeepCoder programs with 3-6 higher-order functions.
C LIMITATIONS OF OUR NEURAL SEMANTICS
Our approach neural semantics differs conceptually in several ways from abstract interpretation (Cousot & Cousot 1977). and the way it has previously been used to constrain symbolic search for program synthesis (Singh & Solar-Lezamal 2011 Wang et al., 2017 Hu et al., 2020). Two main differences stand out as potential limitations of our approach, and avenues to be explored further in future work. Firstly, our method treats loops generically, identically to other higher-order functions. This means neural modules must compute representation of looping program using fixed, feed- forward computation, without an iterative fixpoint computation. It is possible that a more rigorous treatment of loops could lead to improved accuracy, though it would introduce additional complexity to the method. We believe that this may be an interesting direction for future work. Secondly, our handling of lambda functions also differs from abstract interpretation. As discussed in Appendix A,
15

---

Published as a conference paper at ICLR 2021
when using lambda argument higher-order function, method represents the lambda expression as a vector, without encoding the values of its arguments. A method which can treat lambdas more generically would also be interesting direction for future work. We thank an anonymous reviewer for highlighting these two points.
16


Reviews:
[{"review_id": "aIkLZZ_uWWy", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis 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.\n\nThe 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.\n\n### Detailed comments\n\nThe paper describes three types of semantics:\n- concrete semantics, where subexpressions of a (functional) program are evaluated to their concrete outputs according to the rules of a DSL\n- 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\n- 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.\n\nBoth 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.\n\nThe 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?\n\n### Questions\n\nDuring 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)?\n\nWhat does it mean to embed a hole \"based on context\"? Is the dictionary of bindings passed to a neural network in some way?\n\nIt'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})$?\n\nFor 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?\n\nIt'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?\n\nUsing \"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?)\n\nIt 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?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "K1Vudd4O73K", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Positives\n\n* (+1) Blended neural semantics is an elegant and intuitive construct.\n* (+2) Performance seems to be good for interesting and non-trivial DSLs.\n\n# Negatives\n* (-1) Although the high-level description of the approach is intuitive, it is lacking many details. The experimental evaluation is distressingly vague.\n* (-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.\n\n1. 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.\n1. 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.\n1. 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.\n1. 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.\n1. Page 4. What's the embedding function for concrete expressions? \n1. 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.\n1. Page 4. Are neural modules separate for every primitive operation? Even for learned functions? How many are there?\n1. 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?\n1. Page 6, how was test construction exactly? \"combinations of motifs seen during training\" isn't very precise.\n1. Page 6. The policy isn't a cost function. You mean, presumably, the probability associated with the chosen action? Something else? Please explain.\n1. Figure 4. Please explain your x axis. What are programs considered? In total? Per problem? After how much training? How big are the datasets?\n1. 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.\n1. Section 5.3, 3rd paragraph. The string DSL is on the right, not on the left in Figure 5.\n1. Section 5.3. \"We do not expect that our approach would outperform the REPL...\" Why not? Explain.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AdP_Udj2tCk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update:\n\nThe authors have addressed many of my comments below. As such, I am increasing my score.\n\nHigh-level view:\n\nI’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.\n\n\nSummary:\n\nThis 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.\n\nThe “blended” part of the semantics seems to be a fusion of both: (i) neural abstract semantics and (ii) blended abstract semantics.\n\nIn 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.\n\nThe 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”).\n\nOverall, they show their blended semantics approach outperforms other neural systems in some cases and not others. \n\n1.\tFor 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).\n\n2.\tFor 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.\n\n3.\tFor 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.\n\nOverall, 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.\n\n\nHigh-level concerns:\n\nWith 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.\n\nHowever, 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).\n\nLastly, 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.\n\nI 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.\n\nI 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:\n“Synthesizing programs from examples is a classic AI problem which has seen advances from the Pro- gramming Languages community (Solar-Lezama, 2008).”\nA 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.\n\nMoreover, 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 \n\n\nLow-level concerns:\n\nPlease 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5DyqmgA5jIg", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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).\n\nI 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.\n\nThe 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?\n\nThe 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.\n\nThe 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.\n\nThe 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.\n\nPlease 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).\n\nThere is a typo in Sec 3. 'y =9' should be 'y = 7'.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)