Year: 2021

Abstract:
Aiming to find a program satisfying the user intent given input-output examples, program synthesis has attracted increasing interest in the area of machine learning. Despite the promising performance of existing methods, most of their success comes from the privileged information of well-designed input-output examples. However, providing such input-output examples is unrealistic because it requires the users have the ability to describe the underlying program with several inputoutput examples under the training distribution. In this work, we propose a querybased framework that trains a query neural network to generate informative inputoutput examples automatically and interactively. To optimize the framework, we propose the functional space (F-space) to represent input-output examples and the programs and model the similarity between them in a continuous and differentiable way. We evaluate the effectiveness and generalization of the proposed query-based framework on the Karel task and the list processing task. Experimental results show that the query-based framework can generate informative inputoutput examples which achieve and even outperform well-designed input-output examples of state-of-the-art methods.

heading: 1 INTRODUCTION
text: Program synthesis is the task of automatically finding a program that satisfies the user intent expressed in the form of some specifications like input-output examples (Gulwani et al., 2017). Recently, there has been an increasing interest in tackling it using neural networks in various domains, including string manipulation (Gulwani, 2011; Gulwani et al., 2012; Devlin et al., 2017b), list processing (Balog et al., 2017; Zohar & Wolf, 2018) and graphic applications (Ellis et al., 2018; 2019).
Despite their promising performance, most of their success relies on the well-designed input-output examples, without which the performance of the program synthesis model drops heavily. Traditionally, the input-output examples are selected elaborately. For example, in Karel (Devlin et al., 2017b; Bunel et al., 2018), the given input-output examples are required to have a high branch coverage ratio on the test program; In list processing, the given input-output examples are guided by constraint propagation (Balog et al., 2017) to ensure their effectiveness on the unknown program. However, providing such input-output examples is unrealistic because it requires the users to be experienced programmers to describe the underlying program with several input-output examples. Worse, the users must be familiar with the distribution of the training dataset to avoid input-output examples that are out-of-distribution (Shin et al., 2019). Some researchers have tried to solve this problem by search or random selection to find counter examples iteratively (Jha et al., 2010; Laich et al., 2020; Hajipour et al., 2020). However, they do not model the similarity between the input-output examples and programs accurately, and thus the quality of the examples cannot be guaranteed. In summary, how to generate informative input-output examples without expert experience is still an important problem that remains a challenge.
In this paper, we propose a query-based framework that can tackle the above-mentioned problems efficiently. Inspired by the interactive program synthesis, the query-based framework trains a query neural network to generate informative input-output examples by querying the underlying program iteratively. Specifically, we firstly train a query network with programs and then use it to generate informative input-output examples. After that, we use these generated examples to train the program synthesis network. This framework has three advantages: (1) There is no need for well-designed input-output examples in both training and testing, which leads to a good generalization. (2) The query network works in a generative manner, which can essentially reduce the computation cost
Predicted programIOs Generate SynthesizeInteract Embed
Query network Synthesis networkUser intent (program)
Figure 1: The query-based framework. The query network generates informative input-output examples by interacting with the user, and then the generated examples are sent to the synthesis network to synthesize the underlying program.
while facing problems with large input-output space. (3) The query network serves as a plug-andplay module with high scalability, for it is separate from the program synthesis process entirely.
To train the query network, we model the similarity between input-output examples and programs by introducing the functional space (F-space) and defining the distance between programs in it. Each program can be projected into a vector in F-space. The distance between two vectors indicates the functional difference between these two programs, so if two programs are projected into the same vector in the F-space, they are supposed to be functionally equivalent. Each input-output example corresponds to a set of programs that satisfy it, and thus it can be represented by a set of vectors in F-space. Furthermore, we project this set of vectors to a distribution (Sun & Nielsen, 2019) to make the representation continuous and differentiable, and thus can be optimized by the back-propagation algorithm. With the concept of information theory, we train the query network to generate queried input-output examples that maximize the probability of the corresponding program and minimize the probability of the others, resulting in the maximization of the mutual information between the queries and the corresponding programs. In this way, the query network can generate informative queried input-output examples efficiently.
We evaluate our method on the Karel task and the list processing task. Without utilizing the welldesigned input-output examples both in training and testing, we achieve and even outperform the state-of-the-art performance on the Karel task and list processing task, which shows the effectiveness and generalization of our query-based framework.

heading: 2 OVERVIEW
text: In this section, we give the statement of the query problem and then formalize it.

heading: 2.1 PROBLEM STATEMENT
text: To give an intuition of the query problem, consider an oracle that contains some kind of symbolic rules (e.g.programs) and our goal is to discover the symbolic rules inside this oracle. To do this, the traditional program synthesis assumes that the oracle can provide some informative signals automatically, based on which a well-designed synthesizer can find the rules. However, this is a strong assumption on the oracle and cannot cover every situation.
In this work, we consider a more general problem called the query problem, that the informative signals are gained actively by querying the oracle, and the only requirement for the oracle is that it can respond to all kinds of queries (including meaningless ones). The crux of this query problem is, how to generate queries that can help us to identify the underlying rules in the oracle efficiently?
For the sake of illustration, consider the program synthesis task, the oracle corresponds to the underlying program p∗ that satisfies the user intent, and the (query, response) pairs correspond to the input-output examples JeK = {(xk, yk)}K . To measure different queries, we borrow the terminology ”acquisition function” from Bayesian optimization. The acquisition function scores all possible queries and the query algorithm chooses the one with the highest score as the next query. We set the acquisition function to be the mutual information between the queries and the oracle I(JeK; p∗), maximizing which brings more information gain. Specifically, given input-output examples queried so far JeKt−1 = {(x1, y1), (x2, y2), · · · (xt−1, yt−1)}, we train the query network to pick the query xt which obtains the response yt and can maximize I(JeK ∪ {(xt, yt)}; p∗). The mutual information is hard to calculate analytically. Thus, to approximate the I(JeK ∪ {(xt, yt)}; p∗), we adopt the
InfoNCE (van den Oord et al., 2018) and propose a novel way to model the relationship between programs and input-output examples called functional space (F-space). Before dive into the specific method, we will give a problem formulation to make our problem description more accurate.

heading: 2.2 PROBLEM FORMULATION
text: To lay a theoretical foundation of our query method, we give out the problem formulation as follows.
First, we define the functional equivalence, which is consistent with the definition of equivalence of functions in mathematics.
Definition 2.1 (Functional equivalence). Let I be the input example domain containing all valid input examples, O be the output example domain containing all possible output examples, and P be the program domain containing all valid programs under the domain specific language (DSL), each program p ∈ P can be seen as a function p : I → O. For two programs pi ∈ P and pj ∈ P, pi and pj are functional equivalent if and only if ∀x ∈ I, pi(x) = pj(x).
Using the concept of functional equivalence, we can formulate the program synthesis task:
Definition 2.2 (Program synthesis). Suppose there is an underlying program p ∈ P and K inputoutput examples JeK = {(xk, yk)|(xk, yk) ∈ I × O}K generated by it, the program synthesis task aims to find a program p̂ which is functional equivalent to p using JeK.
Following the definitions above, we can define the task of query.
Definition 2.3 (Query). The process of query is a map fq . Given a program p ∈ P and a set of history K input-output examples JeK = {(xk, yk)|(xk, yk) ∈ I × O}K , the process of query generates a query xk+1 = fq(JeK) ∈ I, and then get a response yk+1 = p(xk+1) ∈ O. The query and response are added to history input-output examples: JeK ← JeK ∪ {(xk+1, yk+1)} and this process repeats.
The query process aims to distinguish the underlying program with as few queries as possible, which is consistent with the acquisition function that each query should contain as much information as possible.

heading: 3 METHODS
text: The query network and the synthesis network are trained separately. The query network is trained to find the query contains that is most informative, and after that, the synthesis network is trained to predict the corresponding program using the queried input-output examples. In the following, first, we introduce the F-space to model the similarity between the input-output examples and programs, and then, we illustrate how to train the query network with F-space.

heading: 3.1 F-SPACE
text: To model the query process with a neural network, we propose the functional space (F-space).
Definition 3.1 (F-space and functional distance). F-space is a |I| dimensional space which consists of all valid programs that can be implemented by program domain P. Each program is represented
by |I| different output examples v = (y1, y2, . . . , y|I|). The distance in F-space can be measured by the number of different output examples: d(vi,vj) = |diff(vi,vj)|.
Intuitively, F-space (P, d) measures the functional differences between programs. Each program can be represented by a vector in F-space, and if different programs are represented by the same vector v = (y1, y2, . . . , y|I|) in F-space, it indicates that these two programs get the same result for all inputs, and they are considered functional equivalent which is consistent with Definition 2.1. In practice, a space with dimension |I| is too large to compute. To solve this problem, we utilize the sparsity of F-space and learn an approximate space with dimension reduction by neural networks.
Regarding input-output examples, representing them by vectors is not appropriate. Consider a set of input-output examples JeK = {(xk, yk)}K , we cannot find a vector that represents it when K < |I| because there are more than one programs which satisfies these K input-output examples. For example, when there is only one input-output example JeK = {(2, 4)}, we cannot distinguish the underlying program y = 2x from y = x2. Thus, when K < |I|, the input-output examples JeK = {(xk, yk)}K should be modeled as a set of vectors in F-space, projected by the set of programs that satisfy them.
We summarize the properties of the representation of input-output examples in F-space as follows:
• Each set of input-output examples JeK = {(xk, yk)}K should be represented by a set of F-space vectors JrK = {vn}N .
• For two sets of input-output examples JeKi and JeKj , if JeKi ⊆ JeKj , then their F-space representations JrKi and JrKj have the relationship JrKi ⊇ JrKj .
• For two sets of input-output examples JeKi and JeKj , suppose JeK′ = JeKi ∩ JeKj , then in F-space, their corresponding representations have the relationship JrK′ = JrKi ∪ JrKj
• Following the property above, if JeK′ = JeKi ∪ JeKj , then in F-space, their corresponding representations have the relationship JrK′ = JrKi ∩ JrKj
Representing input-output examples by sets satisfies all these properties already. However, to optimize the representation using neural networks, we need to make it continuous and differentiable. Thus, we model the representation of JeK in F-space as a Normal distribution (Ren & Leskovec, 2020; Sun & Nielsen, 2019), and the probability of the distribution indicates the possibility that it is the underlying program to be synthesized given input-output examples JeK. We illustrate the projection, the subset relationship, and the union/intersection operation of distributions in Figure 2.
Under this representation, the query process becomes the process of reducing the uncertainty of the distribution. As described in Section 2, the query process aims to distinguish the underlying program with as few queries as possible. In F-space, the equivalent description is, the training of the query network aims to find F-space using as few queries as possible. To train the query network, we define several neural operators for the neural network training as follows.
Program projection. To project a program p to a vector v, we traditionally use a sequence model as our encoder:
v = Encoderp(p). (1)
Note that the program synthesis model differs largely on different datasets, so we choose to vary our program encoder according to the specific program synthesis models on different datasets. Mostly, our program encoder is the reverse of the program synthesis decoder.
Input-output example projection. Given one input-output example JeK = {(x, y)}, we can project it into a Normal distribution using the same architecture of the corresponding program synthesis model, except that we add a MLP to output the two parameters of the Normal distribution: µ and log(σ2).
[µ, log(σ2)] = MLPe(Encodere(JeK)), (2) where MLP means a multi-layer perceptron. Using this projection, we can model JeK as N (µ, log(σ2)) in F-space.
Input-output examples intersection. Given K input-output examples JeK = {(xk, yk)}K , each example {(xk, yk)} is represented by a Normal distribution N (µk,σk) using the projector above. The purpose of the intersection is to aggregate these Normal distributions into a new one, which represents JeK in F-space. Under the assumption of independence, the probability of the intersection distribution should be:
Printersection = K∏ i=1 Pri. (3)
Fortunately, the product of independent Normal distributions is still a Normal distribution, which means that we can represent it in [µ′, log(σ′2)]. In practice, we utilize the attention mechanism with another MLP to let the neural network learn the new Normal distribution (Ren & Leskovec, 2020):
[µ′, log(σ′2)] = K∑ i=1 wi[µi, log(σ 2 i )], (4)
wi = exp(MLPattention([µi, log(σ 2 i )]))∑K
j=1 exp(MLPattention(µj , log(σ 2 j )))
. (5)
This formulation not only keeps the form of distributions closed but also approximates the mode of the effective support of Normal distributions, which satisfies our requirement on the intersection of distribution (Sun & Nielsen, 2019).
Inverse projection to query. Finally, we need to generate the query from the representation of input-output examples in F-space. Using the projection and the intersection operation mentioned above, we can project the K input-output examples to the representation [µ, log(σ2)]. To generate query xnew from this representation, we introduce a decoder which has a similar architecture to Encodere but reversed:
xnew = Decoder([µ, log(σ 2)]). (6)
Next, we will introduce how to train the neural network.

heading: 3.2 TRAINING
text: As mentioned above, we design the query network to fit into an encoder-decoder manner. The encoder learns to encode the input-output examples and the programs into F-space, and then the decoder decodes the representations into a new query. Furthermore, to generate queries successively, a Recurrent Neural Network (RNN) style architecture is used to generate queries progressively. As definition 2.3 says, each time when a query is generated, we feed it into the underlying program and get a response. Then, we add the query and response to the input-output examples and send it to the query network to get the next query. This process are shown in Figure 3 and Algorithm 1 (Appendix A.1).
To optimize the query network, we utilize the technique in information theory to maximize the mutual information between the input-output examples JeK and the corresponding program p. Specifically, for a batch of data {(JeKn, pn), pn}N , we construct positive pairs {(JeKi, pi)} and negative pairs {(JeKi, pj)|i ̸= j}. Then, we use the InfoNCE loss (van den Oord et al., 2018) to maximize the lower bound of the mutual information between the input-output examples JeK and the corresponding program.
L = −log( exp(f(JeKi, pi)) exp(f(JeKi, pi) + ∑ i̸=j exp(fJeKi, pj) ), (7)
where f(·, ·) denotes a relevance function. Intuitively, InfoNCE maximizes the relevance between positive pairs and minimizes the relevance between negative pairs. In F-space, we choose f(JeKi, pj) to be the possibility of pj in the JeKi’s distribution. That is, suppose the neural network project JeKi to N (µ, log(σ2)) and pj to v, then f(JeKi, pj) = N (v;µ,σ)), which denotes the probability of v under the Normal distribution with parameters µ and log(σ2).
Additionally, like the task of sequence generation, we need an input-output example to act as the start signal < sos >. Datasets differ largely in program synthesis, so we design specific start signals for each dataset. We make our signal as simple as possible. For example, in Karel, the signal is designed to be an empty map with the robot at the center of the map; In list processing, the signal is just three lists full of NULL. More training details can be seen in Appendix A.

heading: 4 EXPERIMENTS
text: We studied three problems in our experiment. (1) The metric that is reasonable in our query-based framework. (2) The performance of the query-based framework. (3) The generalization ability of the query-based framework. To do this, first, we demonstrate a comparison among several program synthesis metrics. Then, we present our results of the query on the Karel dataset and the list processing dataset to show our methods’ performance and generalization ability.

heading: 4.1 METRICS
text: There are three metrics in neural program synthesis.
• Semantics: Given 5 input-output examples, if the predicted program satisfies all these examples, then it is semantically correct.
• Generalization: Given 5 input-output examples and a held-out input-output example, if the predicted program satisfies all 6 examples, then it is generally correct.
• Exact match: If the predicted program is the same as the ground-truth program, it matches the ground truth exactly.
Among them, exact match is the most strict metric, and generalization is more strict than semantics. Exact match has its drawback in that the predicted program may be different from the ground-truth program, but they are functionally equivalent. Thus, the performance is measured by generalization on Karel and semantics on list processing traditionally. However, generalization is not appropriate here for two reasons: (1) It can only measure the performance of the program synthesis process instead of the query process. In the query process, the network chooses input-output examples independently, and judging them by the held-out example is meaningless. (2) Even for the program synthesis process, generalization is not strict enough. The program that satisfies a small set of input-output examples may fail on a larger set of input-output examples. Thus, the best choice is to use functional equivalence as our metric. Unfortunately, the judgment of functional equivalent is a notoriously difficult problem which makes it hard to be applied in evaluation. To alleviate this problem, we generate 95 held-out input-output examples randomly to achieve a higher branch coverage than 1 held-out example, and make the generalization on these examples a proxy of the functional equivalence:
• Functional equivalence (proxy): Given 5 input-output examples and 95 held-out inputoutput examples, if the predicted program satisfies all 100 examples, then it is functional equivalent to the ground-truth program.

heading: Metric Bunel et al. (2018) Chen et al. (2019)Random Well-designed Query Random Well-designed Query
text: To illustrate the difference between functional equivalence and generalization further, we measured the average branch coverage of these two metrics on Karel’s validation set. Given a set of inputoutput examples, branch coverage evaluates what is the percentage of program branches that are covered by the examples.
The result is shown in Table 1. Functional equivalence outperforms generalization by nearly 10%, which indicates that functional equivalence can represent the correctness of the predicted program much better than generalization.

heading: 4.2 KAREL TASK
text: Karel is an educational programming language used to control a robot living in a 2D grid world (Pattis et al., 1981). The domain specific language (DSL) and other details are included in Appendix B.1.
Settings. Following Section 3, we split the training process into the training of the query network and the training of the synthesis network. For the query network, we set the Encodere the same as the one of Bunel et al. (2018) except for the output layer (see Appendix A.2), and the Encoderp a two-layer LSTM. For the synthesis network, all settings stay unchanged as in Bunel et al. (2018). For all results, we use greedy decoding instead of beam search. As in Section 4.1, exact match and functional equivalence are more appropriate than other metrics in the query task, so we save the model based on them instead of the generalization metric, and this may cause differences in our baseline reproduction.
We generate the dataset with 5 input-output examples using three different methods: randomly selected, baseline models (well-designed), and our method (query). Then, we train the synthesis network on these datasets with two state-of-the-art methods: Bunel et al. (2018) and Chen et al. (2019). Note that there is a slight difference between the program simulators of them, and we choose the one of Bunel et al. (2018) as ours.
Performance. Table 2 presents the performance of the trained synthesis networks, from which we can conclude that (1) The Query dataset performs well on both two training methods, indicating that the query process is totally decoupled with the synthesis process and has a high scalability. (2) Our query method gets comparable results with both baseline methods and largely outperforms the random selection method with more than 10%, which shows its effectiveness.
Comparison with others. We also compared our method with query by committee (QBC) Seung et al. (1992) as another baseline, shown in Figure 4. In QBC, we sample queries based on their diversity. That is, we generate program candidates by beam search, and then select the query that can result in the most diverse outputs on these program candidates. The diversity is simply measured by the output equivalence. Algorithm details can be
seen in Appendix B.4. There are two strategies based on QBC: Crash-aware, where if the query crashes then repeat the algorithm to sample another one; And crash-unaware, which samples queries regardless of the crash problem (see Appendix B.1 and B.2 for a detailed explanation of crashes). QBC-crash-unaware performs worse than Random because Random is chosen by filtering crashed IOs while QBC-crash-unaware may contain crashes. QBC-crash-aware performs much better than QBC-crash-unaware because it queries the underlying program multiple times to make sure that the query will not result in a crash, which is unfair. Even though, out method still outperforms QBC-crash-aware, which shows its advantage.
Training process. To do a further study, we plot the training curve in Figure 5. It is shown that the Query dataset always has a quick start, which indicates that the query method can extract the features of the distinguishable programs effectively and makes them easier to be synthesized.

heading: 4.3 LIST PROCESSING TASK
text: To show the generalization ability of the query method, we conduct another experiment on the list processing task. The list processing task takes 1-3 lists or integers as input examples, and then produces a list or an integer as the output example. More details can be seen in Appendix B.2.
Settings. Following PCCoder (Zohar & Wolf, 2018), we generate two datasets with program length 4 as dataset D1 and program length up to 12 as dataset D2. We set the Encodere of the query network similar to PCCoder with the output layer changed (see Appendix A.2), and use a single layer LSTM as the Encoderp. The synthesis network and the parameters of complete anytime beam search (CAB) (Zhang, 1998) stay the same as PCCoder, except that the maximum time is set to 5 seconds instead of 5,000 seconds for reality.
Similar to the Karel task, we generate the dataset with 5 input-output examples with three different methods. Furthermore, we use two end conditions of CAB: The searching ends when all inputoutput examples are satisfied (searching for semantics), and the searching ends when all statements are true (searching for exact match).
Performance. The results are presented in Table 3, from which we can conclude that: (1) Our query method results higher than well-designed input-output examples in searching for exact match, and consistently outperforms the random. (2) When the length of programs increases, the performance decreases largely. This is resulted from the original algorithm of PCCoder that the intermediate variables are difficult to be saved when the ground-truth program is long. However, the query method decreases slower than others, and the gap between the well-designed and the query is closed largely.

heading: 5 RELATED WORK
text: Programming by examples. Synthesizing a program that satisfies the user intent using the provided input-output examples is a challenging problem that has been studied for years (Manna & Waldinger, 1971; Lieberman, 2001; Solar-Lezama et al., 2006; Gulwani, 2011; Gulwani et al., 2012). Recently, with the development of Deep Learning, more researchers tend to tackle this problem with neural networks in a variety of tasks, including string transformation (Devlin et al., 2017b), list processing (Balog et al., 2017; Zohar & Wolf, 2018), graphic generation (Ellis et al., 2018; Tian et al., 2019), Karel (Devlin et al., 2017a; Bunel et al., 2018), policy abstraction (Sun et al., 2018; Verma et al., 2018) and so on. Additionally, techniques like program debugger (Balog et al., 2020; Gupta et al., 2020), traces (Chen et al., 2019; Shin et al., 2018; Ellis et al., 2019), property signatures (Odena & Sutton, 2020; Odena et al., 2021) are also used to improve the performance of program synthesis. However, their promising performance relies on the well-designed input-output examples which is a high requirement for users. If examples with poor quality are provided, the performance will be affected severely. Worse, if the input-output examples that are out-of-distribution are provided, the program synthesis model cannot finish the task as expected (Shin et al., 2019).
Interactive program synthesis. Considering the high requirement of input-output examples, Le et al. (2017) build an abstract framework in which the program synthesis system can interact with users to guide the process of synthesis. Following this framework, multiple interactive synthesis systems are studied. Among them, Mayer et al. (2015), Wang et al. (2017), and Laich et al. (2020) tend to find counter-examples as queries to the users in a random manner. Although they get rid of the restrictions on the users, the quantity of the input-output examples is not guaranteed, which may get the synthesis process into trouble. Padhi et al. (2018) select more than one query each time and let the users choose which one to answer. This brings an additional burden on the users, and the users are unaware of which query will improve the program synthesized most. Most recently, Ji et al. (2020) utilizes the minimax branch to select the question where the worst answer gives the best reduction of the program domain. Theoretically, the performance of the selection is guaranteed. However, this method is based on search and hardly be applied to tasks with large input-output space. Worse, the query process and the synthesis process are bound, which results in its poor scalability. In contrast, our method split the process of query and the process of synthesis, and thus making their combination more flexible.
Learning to acquire information. Similar to our work, Pu et al. (2018) and Pu et al. (2017) also study the query problem from an information-theoretic perspective. They show that maximizing the mutual information between the input-output examples and the corresponding program greedily is 1 − 1e as good as the optimal solution that considers all examples globally. However, they assume that the space of queries can be enumerated, which limits the application of their query algorithm on complex datasets like Karel. By comparison, our work proposes a more general algorithm that can generate queries in a nearly infinite space. Other related work including active learning and black-box testing can be seen in Appendix D.

heading: 6 CONCLUSION
text: In this work, we propose a query-based framework to finish the program synthesis task more realistically. Moreover, to model the relationship between the input-output examples and programs, we establish a theoretical foundation by formulating the query problem and introducing the F-space. In F-space, we represent input-output examples and the programs and model their similarity in a continuous and differentiable way. Using these techniques, we conduct a series of experiments that shows the effectiveness, generalization, and scalability of our query-based framework. We believe that our methods work not only on the program synthesis tasks, but also on any task that aims to simulate an underlying oracle, including reverse engineering, symbolic regression, scientific discovery, and so on.

heading: A TRAINING DETAILS

heading: A.1 TRAINING ALGORITHM
text: Algorithm 1 Training process 1: function TRAIN( ) 2: Initialize max iterations N and max query times T 3: for i ∈ {1 . . . N} do 4: p← Underlying programs 5: (x0, y0)←< sos > 6: JeK← {(x0, y0)} 7: L← 0 8: for t ∈ {1 . . . T} do 9: v ← Encoderp(p) ▷ Encode program, Equation (1) 10: µ, log(σ2)← IO-ENCODER(JeK) ▷ Encode input-output examples 11: xt ← Decoder(µ, log(σ2)) ▷ Query next input 12: yt ← p(xt) ▷ Get next output from the oracle 13: JeK← JeK ∪ {(xt, yt)} 14: µ′, log(σ′2)← IO-ENCODER(JeK) 15: L← Loss(v,µ′, log(σ′2)) + L ▷ InfoNCE loss, Equation (7) 16: end for 17: Update parameters w.r.t. L 18: end for 19: end function
1: function IO-ENCODER({xk, yk}K) 2: for i ∈ {1 . . .K} do 3: [µi, log(σ2i )]←MLPe(Encodere({xi, yi}) ▷ Encode single example, Equation (2) 4: end for 5: for i ∈ {1 . . .K} do 6: wi ← exp(MLPattention([µi,log(σ 2 i )]))∑K
j=1 exp(MLPattention(µj ,log(σ 2 j )))
▷ Calculate attentions, Equation (5)
7: end for 8: [µ, log(σ2)] = ∑K i=1 wi[µi, log(σ 2 i )] ▷ Intersection, Equation (4)
9: return µ, log(σ2) 10: end function

heading: A.2 MODEL DETAILS AND HYPER PARAMETERS
text: Karel. The query encoder is the same as the one used by Bunel et al. (2018) composed of a Convolutional Neural Network (CNN) with the residual link. After the query encoder, there is an MLP to project the embedding into µ, log(σ2). The dimension of µ and σ is set to 256, and thus the hidden size of MLP is 512. The query decoder is similar to the query encoder except that the number of channels is reversed, and additional batch normalization is added to keep the generation more stable. The program encoder is a two-layer LSTM with a hidden size of 256.
Note that in the well-designed dataset, the size of the grid world can be changed from 2 to 16. However, for the convenience of training, we set the size of the query world fixed to 16. Moreover, to guarantee that all queries can be recognized by the program simulator, we split the query into three parts: boundaries (the map size, set to 16×16), agent position (where the agent is and towards), and map state (the placement of markers and obstacles), and generate them as follows:
• Boundaries: The boundaries indicate the map size, fixed to 16× 16. • Agent position: generate a 4 × 16 × 16 one-hot vector where 4 indicates four directions
and 16× 16 indicates the position. • Map state: generate a 12 one-hot vector on the 16× 16 map, where 12 indicates obstacle,
1-10 markers, and empty grid.
Input-examples
Output-examples
Conv
Conv
ResBlocks Linear IO embeddings
IO embeddings MLP Linear
Linear
𝜇
log (𝜎 )
Activation Conv ReLU
Conv ReLU Conv ReLU
Next layers Activation Conv BN
LReLU
Conv BN
LReLU
Conv BN
LReLU Next layers
(c) IO Encoder (d) Distribution encoder (MLPe)
(a) ResBlock (b) ResBNBlock
Input-output examples × N IO Encoder
MLPe
𝜇
log (𝜎 )
𝜇, log (𝜎 ), latent code ResBNBlocks Representation
(e) Encoder (f) Decoder
The architecture details are shown in figure 6.
For training, the learning rate of the query network is set to 10−4 while the learning rate of the synthesis network stays the same with the original methods. The batch size is 128, and the random seed is set to 100.
List processing. The query encoder is the same as the one in PCCoder. The dimension of µ and σ is set to 256 for dataset D1 and 128 for dataset D2 without much tuning. The query decoder is a single-layer linear network with dimension 256 for dataset D1 and 128 for dataset D2. The program encoder is a single layer LSTM with hidden size 256 for dataset D1 and 128 for dataset D2.
The inputs of list processing consist of three types: INT, LIST, and NULL. Thus, each query is NULL or an integer or a list consisting of integers in the range of [−256, 255]. Each integer is represented in a 512 one-hot vector. For the well-designed input-output examples, the length of a LIST is sampled stochastically with the maximum length of 20. However, to make the query network simpler, we fix the length of queries to 20. The query network generates all three types
separately by different networks and chooses among them according to the type of inputs using a type filter.
The details of the query network for list processing are shown in figure 7.
For training, the learning rate of the query network is set to 10−4 with a 0.1 decay every 40 epochs. The learning rate of the synthesis network is 10−3, which stays the same with the original methods with 0.1 decay every 4 epochs. The batch size of the query process is 64, the batch size of synthesis is 32 for D1 and 100 for D2. The random seed is set to 100.

heading: A.3 OTHER TRAINING TECHNIQUES
text: Latent code. The subsequent queries are easy to fail in a mode collapse, generating similar queries repetitively. To tackle this, we introduce a latent code like InfoGAN (Chen et al., 2016) indicating the query step as another input and ask the encoder in the next query step to decode it accurately. Specifically, given a latent code c which indicates the current query step, the query network is supposed to maximize the mutual information between c and the output query x to alleviate the mode collapse problem. To generate x under the condition of c, we concatenate c with the encoded representation µ and log(σ2), and then send it to the decoder (Equation (6)), shown in Figure 6(g) and Figure 7(e). To maximize the mutual information I(c;x), we design a network aiming to classify c from x, which models the distribution Q(c|x) (details can be seen in Chen et al. (2016)). This network shares its parameters with the Encodere (Equation (2)) except for the last layer, and it is optimized with the cross-entropy loss.
Gumbel-Softmax. Note that the queries are discrete, which makes the query network cannot be optimized by back-propagation. Thus, we take advantage of the Gumbel-Softmax distribution (Maddison et al., 2017; Jang et al., 2017) and make the query process differentiable.
Curriculum learning. The query network is trained progressively. At the beginning of the training, the query network generates one query only. As the training goes on, the limit of the number of queries increases until it achieves five. Specifically, this limit increases every two epochs.
Kullback-Leibler (KL) divergence. Similar to the latent code, we add the reciprocal of the KL divergence between different queries on the same program as another loss to make the queries more diverse. However, this loss does not have a significant impact on training most of the time and makes the training process unstable. Thus it is abandoned in our final version.

heading: B EXPERIMENT DETAILS

heading: B.1 THE KAREL TASK
text: Karel is an educational programming language, which can be used to control a robot to move in a 2D grid world (Pattis et al., 1981). Figure 8 presents the domain language specification (DSL) of
Karel. Figure 9 shows a Karel program example. Each cell of the grid world is represented as a 16-dimensional vector corresponding to the features described in Table 4 (Bunel et al., 2018).
Handling of crashes. The executor of Karel will get a ”CRASH” result and then terminates if the agent:
• Picks a marker while no marker is presented. • Puts a marker down while the number of the markers in the cell exceeds the limit (the limit
is set to 10). • Walks up an obstacle or out of boundaries. • Falls into an infinite loop (the loop with more than 105 API calls).
In the early stage of training, the query network generates the queries randomly, and thus the programs run into these crashed states easily, making the queries cannot be applied to training. To avoid these situations, we modify the executor so that when crashes happen, the state stays still without change and the program keeps executing.

heading: B.2 THE LIST PROCESSING TASK
text: The list processing task takes 1-3 lists or integers as input examples and produces a list or an integer as the output example. An example is shown in Figure 11. Figure 10 shows the DSL of list processing. Following Zohar & Wolf (2018), we generate two datasets: D1 with program length 4 and D2 with program length up to 12.
Handling of the out of range problem. Constraint propagation guarantees that the execution of programs never obtains intermediate values that are out of range [−256, 255]. However, when we query randomly in the early stage of training, the out-of-range problem can easily occur. To handle this problem, we truncate the range of values to [−256, 255] while querying to ensure that all queries can yield legal responses.

heading: B.3 THE EVOLUTION OF DISTRIBUTION ENTROPY
text: To make a sanity check of the F-space formulation, we study how the entropy of the distribution changes over the step of the query.
The entropy of the multivariate Normal distribution N (x;µ,Σ)) is given by
H(x) = 1 2 ln|Σ|+ D 2 (1 + ln(2π)), (8)
where Σ denotes the covariance matrix, D denotes the dimension of x. In our case, we have assumed the independence of each dimension of x which means that Σ is a diagonal matrix. Hence
1 2 ln(|Σ|) = ln( ∏ i σ2i ) = 1 2 ∑ i ln(σ2i ), (9)
where σ2i is the diagonal element of Σ, indicating the variance of each dimension. D is a constant during querying, so we calculate the mean of log(σ2) as an equivalent substitute to show the change of the entropy. Results are shown in Figure 12. In our experiments, Karel performs best and this is also revealed by the entropy that Karel decreases much faster than list processing. On the contrary, the entropy of list processing decreases slowly and has worse performance in our experiment. This performance may be increased by tuning the query network more carefully.

heading: B.4 QUERY BY COMMITTEE
text: In this section, we present the details of our baseline algorithm: query by committee (Seung et al., 1992). Algorithm 2 shows the crash-aware version of the QBC algorithm, which selects the query that can result in the most diverse outputs. The crash-unaware version can be obtained simply by
Algorithm 2 Query by committee (QBC): crash-aware 1: function QUERY( ) 2: Initialize trained model M , query pool Q and max query times T 3: p← Underlying program (oracle) 4: repeat 5: x1 ← samplefromQ 6: y1 ← p(x1) 7: until y1 not CRASH 8: JeK← {(x1, y1)} 9: for t ∈ {2 . . . T} do 10: program candidates Jp̂K←M(JeK) ▷ Get top K predictions by beam search 11: xt ← SELECT-QUERY(Q, p, Jp̂K) 12: yt ← p(xt) 13: JeK← JeK ∪ {(xt, yt)} 14: end for 15: return JeK 16: end function
1: function SELECT-QUERY(Q, p, Jp̂K) 2: repeat 3: queries← sample 100 times from Q 4: score list← [] ▷ Acquisition scores of queries 5: for q ∈ queries do 6: sq ← 0 7: for p̂ ∈ Jp̂K do 8: ŷ ← p̂(q) 9: if ŷ is unique then 10: sq ← sq + 1 ▷ The more diversity the output, the better the query 11: end if 12: end for 13: score list.append((q, sq)) 14: end for 15: Sort score list in a descending order with sq 16: for q ∈ score list do ▷ Select the query with the highest score and without CRASH 17: y ← p(q) 18: if y not CRASH then 19: return q 20: end if 21: end for 22: until a query is found ▷ If all 100 queries result in CRASH, repeat this process. 23: end function
removing all CRASH judgements. Note that, compared with the crash-unaware version, the crashaware version queries the underlying program more times for CRASH judgement, and thus results in a much better performance.

heading: C THE PRODUCT OF TWO NORMAL DISTRIBUTIONS
text: In this section, we will show that the product of two normal distributions is a scaled normal distribution. Suppose we have two normal distributions pa and pb:
pa(x) = 1√ 2πσa e − (x−µa)
2
2σ2a ,
pb(x) = 1√ 2πσb
e − (x−µb)
2
2σ2 b .
(10)
The product of pa and pb:
pa(x)pb(x) = 1√ 2πσa e − (x−µa)
2
2σ2a · 1√ 2πσb
e − (x−µb)
2
2σ2 b
= 1 2πσaσb e −( (x−µa)
2
2σ2a +
(x−µb) 2
2σ2 b ) .
(11)
Consider the index part
(x− µa)2
2σ2a +
(x− µb)2
2σ2b =
(σ2a + σ 2 b )x 2 − 2(µbσ2a + µaσ2b )x+ (µ2aσ2b + µ2bσ2a) 2σ2a2σ 2 b
= x2 − 2µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
x+ µ2bσ 2 a+µ 2 aσ 2 b
σ2a+σ 2 b
2σ2aσ 2 b σ2a+σ 2 b
= (x− µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
)2
2σ2aσ 2 b σ2a+σ 2 b
+
µ2bσ 2 a+µ 2 aσ 2 b
σ2a+σ 2 b − (µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
)2
2σ2aσ 2 b σ2a+σ 2 b
= γ + λ,
(12)
where
γ = (x− µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
)2
2σ2aσ 2 b σ2a+σ 2 b
,
λ =
µ2bσ 2 a+µ 2 aσ 2 b
σ2a+σ 2 b − (µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
)2
2σ2aσ 2 b σ2a+σ 2 b
.
(13)
Up to now, γ is in the format of normal distribution. Simplify λ to make it cleaner:
λ =
µ2bσ 2 a+µ 2 aσ 2 b
σ2a+σ 2 b − (µbσ
2 a+µaσ 2 b
σ2a+σ 2 b
)2
2σ2aσ 2 b σ2a+σ 2 b
= (µ2bσ 2 a + µ 2 aσ 2 b )(σ 2 a + σ 2 b )− (µbσ2a + µaσ2b )2
2σ2aσ 2 b (σ 2 a + σ 2 b )
= σ2aσ 2 b (µ 2 a + µ 2 b − 2µaµb)
2σ2aσ 2 b (σ 2 a + σ 2 b )
= (µa − µb)2
2(σ2a + σ 2 b ) .
(14)
Finally, we get
pa(x)pb(x) = 1
2πσaσb e−λe−γ
= α · 1√ 2πσ′ e− (x−µ′)2
2σ′2 , (15)
where
µ′ = µbσ
2 a + µaσ 2 b
σ2a + σ 2 b
,
σ′ =
√ σ2aσ 2 b
σ2a + σ 2 b
,
α = 1√
2π(σ2a + σ 2 b ) e − (µa−µb)
2
2(σ2a+σ 2 b ) ,
(16)
α is a scale factor.
Next, we will show that approximating the new µ′ and log(σ′2) with the weighted sum of the [µa, µb] and [log(σ2a), log(σ 2 b )] is reasonable.
For µ′, it is obvious that it can be seen as
µ′ = µbσ
2 a + µaσ 2 b
σ2a + σ 2 b
,
= σ2b
σ2a + σ 2 b
· µa + σ2a
σ2a + σ 2 b
· µb, (17)
which is a weighted sum. For log(σ′2), we can rewrite it as follows
log(σ′2) = log( σ2aσ 2 b
σ2a + σ 2 b
),
= log(σ2a) + log(σ 2 b )− log(σ2a + σ2b )
= log(σ2a) + log(σ 2 b )− (hlog(σ2a) + klog(σ2b ) + log(
1
σ2kb σ 2(h−1) a
+ 1
σ2ha σ 2(k−1) b
))
= (1− h)log(σ2a) + (1− k)log(σ2b )− log( 1
σ2kb σ 2(h−1) a
+ 1
σ2ha σ 2(k−1) b
),
(18) where h and k are two coefficients. With suitable h and k learned, the last term can be ignored ( 1 σ2kb σ 2(h−1) a + 1 σ2ha σ 2(k−1) b
≈ 1) and thus log(σ′2) can be approximate by the weighted sum of [log(σ2a), log(σ 2 b )].

heading: D ADDITIONAL RELATED WORK

heading: D.1 ACTIVE LEARNING
text: Active learning is a research domain that aims to reduce the cost of labeling by selecting the most representative samples iteratively from the unlabeled dataset, and then asking them to an oracle for labeling while training. According to Shui et al. (2020), active learning can be divided into pool-based sampling (Angluin, 1988; King et al., 2004), which judges whether a sample should be selected for query-based on the evaluation of the entire dataset; steam-based sampling (Dagan & Argamon, 1995; Krishnamurthy, 2002), which judges each sample independently compared to pool-based sampling; and membership query synthesis (Lewis & Gale, 1994), which means that the unlabeled sample can be generated by the learner instead of selecting from the dataset only. Although active learning involves querying an oracle iteratively, which is similar to our framework, there are still two main differences between them. (1) For the final purpose, active learning aims to finish the training stage at a low cost, and the inference stage remains the same as other deep learning tasks without the query process, while our framework aims to find the oracle (i.e.the underlying program) in a symbolic form, and the query process is retained during inference. (2) For the query process, active learning assumes only one oracle (i.e.the same query always gets the same label). In contrast, our framework assumes multiple oracles (i.e.the same query will get different responses if the underlying programs are different).

heading: D.2 AUTOMATED BLOCK-BOX TESTING
text: Black-box testing is a method of software testing aiming to examine the functionality of a blackbox (such as a piece of a program) by a large number of test cases without perceiving its internal structures. The most famous automated test cases generation method is learning-based testing (LBT) (Meinke, 2004; Meinke & Niu, 2010; Meinke & Sindhu, 2011). LBT is an iterative approach to generate test cases by interacting with the black-box, which sounds similar to the query problem mentioned in this paper. However, the settings and the purpose of the black-box testing are totally different from ours. In detail, the black-box testing assumes the existence of a target requirement (or target function) and a black-box implementation of this requirement (such as a piece of program which is unknown). The purpose is to check the black-box implementation to ensure that there is no bug or difference between the target requirement and the black-box by generating test cases (i.e.input-output examples). In a contrast, in our settings, the target function does not exist, and what we have is only a black-box (or called oracle / underlying program in our paper). Our goal is to query this black-box and guess which program is inside based on the experience learned on the training set.

heading: E TWO QUERY EXAMPLES
text: In this section, we show two query examples that cover all branches of the program while the welldesigned dataset fails to do this. Each example consists of the underlying program and the corresponding queries that can cover all its branches. See Figure 13 and Figure 14.

Review summaries:
This paper considers an active diagnostic setup for program synthesis as follows: There is an oracle function/program p* belonging to a space of functions, and at inference time, one would like to uncover p*. To do so, a querying algorithm iteratively/adaptively query the oracle with inputs x1, x2, ... xk, receiving outcomes y1, y2, ... yk in return. A synthesizer (or any inverse model capable mapping observations to hypothesis, doesn't really matter) then proposes a guess p' based on the collected query-observation pairs (called examples) {(x1,y1)...(xk,yk)}. One "wins the game" if p* and p` behave the same way (functional equivalent) on all inputs, using as few queries (i.e. small k) as possible.  To do this, the paper introduce a learned F-space, which both functions f and sets of examples e can map into. While functions map (using a learned embedding) to single points in F-space (each point in F-space represent a unique function), examples map (using yet another learned embedding) to distributions in F-space (each example set represent a _distribution of_ functions that are consistent with it). The querying network is trained to generate the next observation x conditioned on the existing observations {(x1,y1)...(xk,yk)} in such a way that maximally reduce the uncertainty of the F-space once the new example, (x, p*(x)) is augmented to the existing observations.  Results are convincing to me.

The authors propose a framework to generate unit tests by generating candidate inputs for which labels are queried from an oracle. The idea is to have a vector space where each point represents a function (different programs that are functionally equivalent map to the same point) and a unit test is represented as a set of points that correspond to functions that would pass that unit test.   They project a unit test onto a normal distribution on the function space where the probability of the distribution is whether a point is the underlying function to be synthesized given the unit test.   They merge multiple unit tests using an attention mechanism into a single point in the function space and then train the unit test generator such that the mutual information between the probability distribution on the merged unit test and the probability distribution on the programs is maximized using InfoNCE loss.  A synthesizer network is used to synthesize the program from generated unit tests. They test on Karel and list processing task.

In neural program synthesis from input-output examples, the goal is to generate a program which, when executed on the inputs, produces the corresponding outouts. Typically, the set of input-output examples is taken as given by the program synthesis method. In this work, the authors propose to instead have the program synthesizer interact with an oracle to determine the set of input-output examples. The synthesizer proposes a potential input for the program, the oracle produces the output, and the process repeats. Under this paradigm, the program synthesizer can query the oracle for the inputs which would be most helpful in determining the correct program. This direction has been explored in prior work as "interactive program synthesis", but largely with constraint-based methods.  The paper represents each input-output example pair as a normal distribution (with a mean and variance parameter). A set of input-output example pairs is also represented as a normal distribution, with its parameters a weighted sum of each pair's parameters. A neural decoder module takes the mean/variance of this combined distribution as input to produce a new input; we can query the oracle with the input to get the output, resulting in a new input-output example pair.