Learning Programs from Noisy Data
Veselin Raychev

Pavol Bielik

Martin Vechev

Andreas Krause

Department of Computer Science
ETH Zurich, Switzerland{veselin.raychev, pavol.bielik, martin.vechev, krausea}@inf.ethz.ch

Abstract
We present a new approach for learning programs from noisy
datasets. Our approach is based on two new concepts: a regularized
program generator which produces a candidate program based on asmall sample of the entire dataset while avoiding overfitting, and adataset sampler which carefully samples the dataset by leveraging
the candidate program’s score on that dataset. The two components
are connected in a continuous feedback-directed loop.
We show how to apply this approach to two settings: one where
the dataset has a bound on the noise, and another without a noisebound. The second setting leads to a new way of performing
approximate empirical risk minimization on hypotheses classes
formed by a discrete search space.
We then present two new kinds of program synthesizers whichtarget the two noise settings. First, we introduce a novel regularized
bitstream synthesizer that successfully generates programs even in
the presence of incorrect examples. We show that the synthesizer
can detect errors in the examples while combating overfitting –a major problem in existing synthesis techniques. We also show
how the approach can be used in a setting where the dataset grows
dynamically via new examples (e.g., provided by a human).
Second, we present a novel technique for constructing statisticalcode completion systems. These are systems trained on massive
datasets of open source programs, also known as “Big Code”. The
key idea is to introduce a domain specific language (DSL) overtrees and to learn functions in that DSL directly from the dataset.
These learned functions then condition the predictions made by thesystem. This is a flexible and powerful technique which generalizes
several existing works as we no longer need to decide a priori on
what the prediction should be conditioned (another benefit is thatthe learned functions are a natural mechanism for explaining theprediction). As a result, our code completion system surpasses theprediction capabilities of existing, hard-wired systems.
Categories and Subject Descriptors I.2.5 [Artificial Intelligence]:
Programming Languages and Software; I.2.2 [Artificial Intelligence]: Automatic Programming; D.2.3 [Software Engineering]:
Coding Tools and Techniques
Keywords Program Synthesis, Big Code, Statistical Code Completion, Anomaly Detection, Regularization, Noisy Data

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
POPL’ 16, January 20-22, 2016, St. Petersburg, FL, USA.
Copyright c 2016 ACM 978-1-4503-3549-2/16/01. . . $15.00.
http://dx.doi.org/10.1145/2837614.2837671

Data set D
with noise
Datasetsampler

regularizer λsample di ⊆ D
Programgenerator
candidate program pi

Program pk

confidence or error bound 
representative sample dk

Figure 1. Learning programs from noisy data.

1.

Introduction

This paper presents a new approach for learning programs fromnoisy datasets. While there has been substantial work over the lastfew decades on learning programs from examples (e.g., [18, 19]),
these approaches cannot adequately deal with incorrect input asthey attempt to satisfy all examples, thus overfitting to the data.
This means that when the dataset is noisy, they either fail to return aprogram or produce the wrong program. Post-mortem ranking techniques do not help as they simply end up ranking incorrect solutions. Other synthesizers have limited support to discover incorrect
examples when the synthesis procedure on all examples fails [12],but are specific to a particular domain of programs. The field of machine learning (ML) has extensively studied the problem of learning functions from noisy data. However, the space of programs (hypotheses in ML terms) is vastly more complex than the usual parametric models (e.g., linear separators, neural networks) typicallyconsidered in machine learning. When the hypothesis space is simpler, one can afford to perform optimization over the (continuous,and potentially convex) parameter space and the entire dataset, an
optimization task that is computationally infeasible in the (discrete)setting of complex program predictions.
Our work The approach presented in this work, illustrated inFig. 1, enables learning of programs from a noisy dataset D of arbitrary size. The technique is based on several new concepts. First,
a dataset sampler carefully selects (small) samples with specificproperties from D. Second, a regularized program generator produces a program given the selected sample in a way which controls the complexity of the solution and avoids over-fitting. The
two components are linked together in a feedback directed way,
iterating until the desired solution pk is found. As we show in thepaper, this approach can serve as a basis for constructing a range ofprediction engines given a noisy dataset D.
Quantifying noise To systematically instantiate our approach, we
consider both cases for quantifying the noise in the dataset: the casewhere we have a bound on the noise and the case where the noise isarbitrary. In the first case, we also provide optimality guarantees on
the learned program. In the second case, we approach the learningproblem with a fast, scalable algorithm for performing approximate
empirical risk minimization (ERM) [21], bridging the fields ofapplied program synthesis and machine learning. Our setting in factraises new challenges from a machine learning perspective as here,
ERM is performed not on the whole data at once as in traditionalML, but on carefully selected (small) samples of it.
Synthesis with noise To illustrate how our concepts apply, we
present two new kinds of synthesizers targeting the different noise
settings. First, we present a synthesizer for bit-stream programs,
called B IT S YN, where we dynamically add examples, possiblywith some errors, until we produce the desired program. Second,
for the case of large datasets, we present D EEP S YN, a new kind of
statistical synthesizer that learns probabilistic models from “BigCode” (a dataset of programs available in repositories such as
GitHub [10]) and makes predictions (i.e., code completion) basedon this model. Our prediction engine generalizes several existing
efforts (e.g., [16, 30]) and is able to make predictions beyond thecapability of these systems. Importantly, as our predictions areconditioned on program elements, they are easy to understand andjustify to a programmer using D EEP S YN, a capability missing inapproaches where the prediction is based on weights and featurefunctions, and is not human understandable.
Detecting noise While not the primary goal, we believe this work
represents a new way for performing anomaly detection: besides
the learned program, the algorithm in Fig. 1 can return the set ofexamples dk the program does not satisfy (these represent the potential anomalies). Our approach is unlike prior work which either
assumes the program is already provided [5] or require statisticalassumptions on the data [6].
Main contributions Our main contributions are:
• A new approach for learning programs from noisy datasets ofarbitrary size. The key concepts are a dataset sampler which
carefully samples the dataset, and a regularized program generator which avoids overfitting, with both components linked in a
feedback directed loop.
• An instantiation of the approach to two settings: one where weplace a bound on the noise in the dataset, and another where theerror bound is unknown.
• Our second instantiation leads to a new way of performing ap-

proximate ERM on hypotheses classes consisting of a discrete
search space (traditionally, ML considers hypotheses classes
defined via a continuous parameterization).
• Two variants of a bit-stream synthesizer, illustrating how to

use our techniques in an interactive programming-by-example
setting as well as anomaly detection.
• A new method for constructing statistical code completion en-gines from “Big Code” (which deal with the unbounded noise
setting). This method introduces a DSL over trees and learns
loop-free functions in the DSL. The learned functions control
the predictions (and thus, can explain a prediction), generalizing much prior work where the prediction is “hard-wired”.
• A complete implementation and evaluation of B IT S YN and

D EEP S YN, showing their effectiveness in handling a variety ofnoise settings, a capability beyond that of existing approaches.
We believe this is the first comprehensive work that deals withthe problem of learning programs from noisy datasets, and represents an important step in understanding the trade-offs arising whentrying to build program synthesis engines that deal with noise.
Based on the techniques presented here, one can investigate how
to adapt and extend many of the existing programming-by-example
and synthesis engines to deal with noise.

Paper outline The rest of the paper is structured as follows. In
Section 2 we introduce our synthesis algorithm and show someof its important properties. Then, the paper continues with two
possible settings for the noise: (i) sections 3 and 4 apply our approach to synthesis with bounded noise on bit-stream programs and(ii) sections 5, 6 and 7 apply our approach to synthesis with unbounded noise for constructing statistical code completion enginesfrom “Big Code”. In Section 8 we discuss related work. The paper
concludes with Section 9.
We provide additional resources such as source code and test
data online at http://www.srl.inf.ethz.ch/noise.php.

2.

General Approach

In this section we present our general approach for learning programs from datasets with incorrect (noisy) examples. We show how
to instantiate this approach in later sections.
2.1

Problem Formulation

Let D be a dataset consisting of a set of examples and P be the set of
all possible programs. The objective is to discover a program in P
which satisfies the examples in D. In practice however, the dataset
D may be imperfect and contain errors, that is, contain examples
which the program should not attempt to satisfy. These errors
can arise for various reasons, for instance, the user inadvertently
provided an incorrect example in the dataset D, or the dataset
already came with noise (of which the user may be unaware of).
Fundamentally, because we are not dealing with the binarycase of correct/incorrect programs and need to deal with errors,
we introduce a form of a cost (risk) function associated with theprogram to be learned from the noisy dataset.
Let r : P(D) × P → R be a cost function that given a dataset
and a program, returns a non-negative real value that determines theinferiority of the program on the dataset. In machine learning terms,
we can think of this function as a generalized form of empirical risk(e.g., error rate) associated with the data and the function. In thespecial case typically addressed by PBE systems (e.g., [18, 19]), thefunction returns either 0 or 1, that is, the program either produces
the desired output for all inputs in the given dataset, or it does not.
Later in the paper, we discuss several possibilities for the r function
depending on the particular application.
Problem statement The learning problem is the following:
find a program pbest = arg min r(D, p)p∈P

That is, the goal of learning is to find a program whose cost on
the entire dataset is lowest (e.g., makes the least number of errors,
or minimizes empirical risk as in Section 5). We note that whilein general there could be many programs with an equal (lowest)
cost, for our purposes it suffices to find one of these. It is easy toinstantiate this problem formulation to the specific, binary case ofsynthesis from examples, where r returns 1 if some example in D
is not satisfied and 0 otherwise. A challenge which arises in solving
the above problem is that the dataset D may be prohibitively large,or simply infinite (e.g., may need to continually ask a user for
samples of the dataset) and thus trying to directly learn the optimal
program pbest that satisfies the dataset D may be infeasible.
2.2

Our Solution: Iterative Synthesis Algorithm

The key idea of our solution is to start with a small sample ofthe dataset D and to iteratively and carefully grow this sample
in a way which allows finding a good solution with a few, smallsized samples. Our solution consists of two separate components:
a program generator and a dataset sampler. We continually iterate
between these two components until we reach a fixed point and thedesired program is found.

Input: Dataset D, initial (e.g. random) dataset ∅ ⊂ d1 ⊆ D
Output: Program p
begin
progs ← ∅i←0repeati←i+1// Dataset sampling step
if i > 1 thendi ← ds(progs, |di−1 | + 1)
end// Program generation steppi ← gen(di )if found program(pi ) thenreturn pi
endprogs ← progs ∪ {pi }until di = D;return ”No such program exists”
end
Algorithm 1: Program Synthesis with Noise

Program generator For a finite dataset d ⊆ D, a program generator is a function gen : P(D) → P defined as follows:gen(d) = arg min r(d, p)p∈P

To reduce the (expensive) invocation of gen(d), in our prediction algorithm, we aim for a size of the dataset d that is as small as
possible.
Dataset sampler The second component of our approach is what
we refer to as the dataset sampler ds : P(P) × N → P(D):ds(progs, n) = d0 with |d0 | ≥ nThat is, a dataset sampler takes as input a set of programs (and abound on the minimum size of the returned sample) and produces aset of examples which are then fed back into the generator. We will
see several instantiations of the data sampler later in the paper.
Iterative sampling We connect the program generator and data
sampler components in an iterative loop. The resulting algorithm
is shown in Algorithm 1. At every iteration of the loop, the algorithm checks if the current program pi is a satisfactory solution
and can be returned (in later sections, we discuss instantiations offound program). If the current program pi is not the right one, we
sample from the dataset D using the current set of explored programs progs, obtaining the next dataset di . Note that while thesize of the sample di is greater than the size of the previous sample
di−1 , there is no requirement that di is a superset of di−1 (i.e., thesets may be non-comparable). Once we have obtained our new sample di , we use the sample to generate the new candidate programpi . In case the program pi is not the desired one, the algorithm
continues and adds pi to the progs set and continues iterating.
2.3

Reduction of Search SpaceFirst, note that Algorithm 1 always terminates if the dataset D is
finite. This is because the size of the dataset di increases at every
step until it eventually reaches the full dataset. However, our goal
is to discover a good program using only a small dataset di .
To achieve this, we leverage the dataset sampler to carefully
pick small datasets. Consider the first dataset d1 . Since this dataset
may be random, let us assume that any possible program p1 canbe returned as a result. If p1 was not the desired program, we
would like to select the next dataset d2 to be such that p1 cannot be

cut by p3

p3

cut by p3

cut by p2

p3

search space

pbest
cut by p1

p2
p1

cut by p2

pbest
search space
cut by p1

(a)

p2

p1
(b)

Figure 2. Trimming the space of programs (a) for noise-freesynthesis and (b) for synthesis with noise.

returned at the next step by gen(d2 ). In general, we would like thatat step i, gen(di ) ∈/ {pj }i−1
j=1 . We illustrate this scenario in Fig. 2(a). Here, we have three explored programs p1 , p2 and p3 which
are pruned away by the current dataset. The figure also shows thespace of remaining candidate programs (in ) that can possibly begenerated by gen. This space excludes all three generated programs
as well as any programs removed as a result of pruning these three.
Indeed, existing synthesis approaches that do not deal with noise(e.g., [18]) typically prune the search space as shown in Fig. 2(a).
Unlike the noise-free setting where a binary criteria for pruninga generated program p exists, when the data contains noise, wecannot immediately decide whether to prune p. The reason is thateven though p may make a mistake on a given example, at anintermediate point in the algorithm we may not know whether
another, even better program on D exists. What this uncertainty
means is that we may need to keep p in the candidate program
space for longer than a single algorithmic iteration. This raises thefollowing question: which programs are kept and which ones are
removed from the candidate set?
Reduction of search space To address this question, at every
iteration of the synthesis algorithm, we aim to prune some of thegenerated programs (and conversely, keep the remaining ones). In
particular, we keep a generated program p if it is within  distanceof pbest , that is, r(D, p) ≤ r(D, pbest ) + . In Fig. 2(b), the area
shaded with around pbest denotes the set of programs within
distance  of pbest . The space reduction process is illustrated inFig. 2(b). Here, the first two explored programs p1 and p2 falloutside the accepted area and are thus permanently pruned fromthe candidate space. The score of the latest generated program p3 ,however, is within  of pbest and is thus kept as a viable candidate
to be returned. At this point, the algorithm can return p3 or keep
searching further, hoping to find better scoring programs than p3 .
We also require that  ≥ 0 ensuring completeness: we always keep
the best program pbest in the candidate space of programs.
In what follows, we describe dataset samplers which enablepruning of the search space in the manner described above.
2.4

Hard Dataset Sampler (dsH )We introduce an instance of the dataset sampler ds used in Algorithm 1 as follows:
Definition 2.1 (Hard dataset sampler). A hard dataset sampler isa function dsH such that for Q ⊆ P, d0 = dsH (Q, min size), it
holds that ∀p ∈ Q. r(D, p) ≤ r(d0 , p) and |d0 | ≥ min size.
Note that the hard dataset sampler always exists as we cantrivially set d0 = D. For our synthesizer, we always invoke thehard dataset sampler with Q = progs (the current set of generated
programs). The meaning of the hard dataset sampler is that for all
programs in Q, the cost on the returned dataset d is higher or equal
than on the full dataset D.

In principle, this definition generalizes the concept of providing
more examples in noise-free synthesizers. Without noise, r(d, p)
simply returns 0 if the program p satisfies all examples in d and 1
if p does not satisfy some example in d. The hard dataset sampler
in the noise-free case generates (e.g., by asking questions to theuser) a dataset d0 such that for all explored programs progs, anunsatisfied example is in d0 if an unsatisfied example exists in D.
Using the hard dataset sampler, we now state a theorem which
ensures that the generated program pi at step i does not appear in a
subset of the explored programs outside certain range beyond pbest .
That is, pi cannot be the same as any previously generated pj thatis outside of the area in Fig. 2(b).
Theorem 2.2. Let E = {p1 , . . . , pi−1 } be the set of programs
generated up to iteration i of Algorithm 1, where the dataset sampler ds satisfies Definition 2.1.
If  ≥ r(di , pbest ) − r(D, pbest ), then pi = gen(di ) ∈/ E 0 where0
E = { p ∈ E | r(D, p) > r(D, pbest ) +  }Proof: Let p ∈ E 0 . Because r(D, p) > r(D, pbest ) +  and fromthe definition of  :  + r(D, pbest ) ≥ r(di , pbest ), we knowthat r(D, p) > r(di , pbest ). Now, because di = ds(E, ) andds satisfies Definition 2.1, r(di , p) ≥ r(D, p). Then, we haveshown that r(di , p) > r(di , pbest ). Because pi = gen(di ) andgen(di ) = arg minp0 ∈P r(di , p0 ), it follows that pi 6= p. Thus, we
prove that pi ∈/ E0.
The above theorem is useful when we know the bound  on thebest program pbest . If we can show a smaller value of , the areas
around pbest will also be smaller and we canmarked in andthen provably trim the search space further. Using this theorem, we
can stop the synthesis algorithm as soon as we generate a programpi that is already in the explored set. As a result of the theorem, we
will know that such a pi is within a distance of at most  from pbest .
In Section 3 we consider a case where  = 0 and then Theorem 2.2 provides even stronger guarantees at every step of Algorithm 1: all previously generated candidate programs that are notpbest are eliminated from future consideration. For cases where wecannot obtain bounds on the best program pbest , we next define a
different dataset sampler.
2.5

Representative Dataset Sampler (dsR )First, we define a measure of representativeness for dataset d withrespect to the full dataset D on a set of programs Q ⊆ P.
Definition 2.3 (Representativeness measure).
repr(Q, D, d) = max |r(D, p) − r(d, p)|p∈Q

The measure of representativeness says how close are the costsof the programs in Q on the dataset d with respect to their costs on
the full dataset D. The metric is set to the maximum difference incosts since our goal for the dataset d is to be a representative of D
for all programs. Then, we define a dataset sampler as follows:
Definition 2.4 (Representative dataset sampler).
Rds (Q, size) =arg minrepr(Q, D, d)d⊆D,|d|=size

Similar to the hard dataset sampler (Definition 2.1), in step i of
Algorithm 1 we always use the set of programs Q = progs.
Analysis Note that the repr measure is a non-negative functionthat is minimized by dsR . If d0 = dsR (Q, size) is such thatrepr(Q, D, d0 ) = 0 then the produced dataset is perfectly representative. In this case dsR is a hard dataset sampler, because∀p ∈ Q. r(D, p) = r(d0 , p).
The question then is: why do we attempt to achieve r(D, p) =r(d0 , p) instead of r(D, p) ≤ r(d0 , p) as in Definition 2.1? If we

perform our analysis using Theorem 2.2, then we must find as small
as possible value  ≥ 0 such that  ≥ r(di , pbest ) − r(D, pbest ).
However, instead of minimizing r(di , pbest ) − r(D, pbest ), in dsR
we minimize |r(di , pj ) − r(D, pj )| for programs pj already explored up to step i (i.e. j ∈ 1..i − 1). Arguably, the incorrect examples may behave similarly on all programs, but in the general case
we cannot find a bound  for Theorem 2.2.
Instead, we give a different argument about eliminating some,
but not all of the already explored programs.
Theorem 2.5. Let E = {p1 , . . . , pi−1 } be the set of programs
generated up to iteration i of Algorithm 1.
Let pk = arg minp∈E r(D, p) be the best program explored so far.
Let δ = repr(Q, D, di ) be the representativeness measure of di .
Then pi = gen(di ) ∈/ E 0 where:0
E = { p ∈ E | r(D, p) > r(D, pk ) + 2δ }Proof: Let p ∈ E 0 . From Definition 2.3, |r(di , p) − r(D, p)| ≤ δand thus r(di , p) ≥ r(D, p) − δ. Using a similar argument for pk ,we obtain that r(di , pk ) ≤ r(D, pk )+δ. Then r(di , pk ) < r(di , p)
and thus p 6= arg minp0 ∈P r(di , p0 ) and p 6= pi = gen(di ).
Note that the set E 0 has the same shape as in Theorem 2.2 exceptthat here we consider pk (best program so far) instead of pbest (bestprogram globally), and instead of  we have 2δ.
What this theorem says is that the programs E 0 ⊆ E thatwere already generated and are worse than pk ∈ E by more than
twice the representativeness measure δ of the dataset di cannot
be generated at step i of Algorithm 1. We can also instantiate
the condition for cutting the space discussed earlier: r(D, p) ≤r(D, pbest ) +  and visualize Theorem 2.5 in Fig. 2(b) as follows:
take p3 = pk and let x = r(p3 , D) − r(pbest , D) be the distance
between pk and pbest . Then take  = x + 2δ. Thus, programs p1
and p2 are worse than pbest by more than  and are permanently
removed from the program search space.
In case δ = 0, we can see that all programs in E worse thanthe (locally) best program pk ∈ E will be eliminated. Still, this isa weaker guarantee than for the case where  = 0 in Theorem 2.2.
Later we will show that dsR works well in practice, but in general
it is theoretically possible that Algorithm 1 with dsR makes noprogress until a dataset of a certain size is accumulated.
2.6

Cost Functions and Regularization

So far, we have placed few restrictions on the cost function r and we
defined the synthesis problem to be such that lower cost is better.
We now list concrete cost functions considered later in the paper:• num errors(d, p) returns the number of errors a program p

does on a dataset of examples d.
• error rate(d, p) = num errors(d,p)
is the fraction of the ex|d|amples with an error. A related metric used in machine learningis the accuracy, which is 1 − error rate.
• Other measures weigh the errors done by the program p on thedataset d according to their kind (e.g., perplexity is one possible
such measure).
Regularization We also use a class of cost functions known as
regularized cost metrics. If r is a cost metric, its regularized version
is rreg (d, p) = r(d, p) + λ · Ω(p). Here, λ is a real-valued constantand Ω(p) is a function referred to as a regularizer. The goal of theregularizer is to penalize programs which are too complex. Notethat the regularizer does not have access to the dataset d, but only
to the given program p. In practice, using regularization means wemay not necessarily return the program with the least number of
errors if a much simpler program with slightly more errors exists.
In Section 5.1, we justify the use of regularization in the context of
empirical risk minimization.

3.

The Case of Bounded NoiseIn this section, we show how to instantiate Algorithm 1 for the casewhere we can define a bound on the noise that the best program
pbest exhibits.
Definition 3.1 (Noise Bound). We say that k is a noise bound forsamples of size k if for the program pbest :∀d ⊆ D.|d| = k ⇒ k ≥ r(d, pbest ) − r(D, pbest )For example, if r , error rate and D contains at most one
incorrect example, then 10 = 0.1 is a noise bound, because for any
sample d ⊆ D of size |d| = 10, the error rate is at most 0.1, but theerror rate on the entire dataset D may be lower. Another interestingcase is if r , num errors and pbest has at most K errors on theexamples in D. Then a noise bound for any k is k = 0 because nodataset d ⊆ D has more errors than the full dataset D. Note thatusing regularization is an orthogonal issue and does not affect thenoise bound, because the regularizer Ω(pbest ) cancels out in theinequality of Definition 3.1.
We can easily instantiate Theorem 2.2 when a noise boundk is available by setting  = k in the theorem’s precondition ≥ r(di , pbest ) − r(D, pbest ) (here, k = |di |).
Derived termination criterion Using Theorem 2.2 and the hard
dataset sampler allows us to derive a possible termination criterion
for Algorithm 1. In particular, if our desired program pdesired issuch that r(D, pdesired ) ≤ r(D, pbest ) + desired (i.e., it is worse
than the best program by at most desired ), then if the following
stopping criterion triggers:
found program(pi ) , (pi ∈ progs) ∧ |di | ≤ desired
the algorithm will produce pdesired .
This criterion follows from Theorem 2.2 because if a programpi ∈ progs (i.e., it was already explored previously), then pi
was not excluded from the search space and thus it must be thatr(D, pi ) ≤ r(D, pbest ) + |di | (i.e., pi ∈ ).
Bound on the number of errors We next consider an interesting
special case where we know that for the best program pbest , there
are at most K incorrect examples in D that it does not satisfy.
Note that we only need to know a bound, not the exact numberof errors the best program makes. In this case, we propose to use
the following cost function:rK (d, p) = min(num errors(d, p), K + 1)
That is, we count the number of unsatisfied examples and cap
the cost at K + 1, thus we do not distinguish programs or datasetswith more than K errors. Since we know that the best program has
at most K errors, in Definition 3.1, we can show that k = 0 (forany k) is a valid bound. In this case, we can also obtain a stopping
criterion with desired = 0 by using:found program(pi ) , pi ∈ progs
Thus, we get the stronger guarantees as in Fig. 2 (a) and ensurethat upon termination the algorithm produces the program pbest .
Discussion We note the meaning of the hard dataset sampler
when r , num errors. Then, the requirement for a program pof r(d, p) ≥ r(D, p) from Definition 2.1 means that sample dimust contain all errors in D – naturally, this may lead to a datasetthat is too big.
By knowing the cap K and using a cost function r , rK , werestrict the sampler to always include exactly K + 1 unsatisfied
examples in order to eliminate pi as a candidate for the next step,
because we know that pbest has at most K errors. In this setting,knowing a bound K in advance allows the dataset sampler to insert
only the necessary number of samples in the small datasets di .

In the next section, we present an implementation of a synthesizer for bitstream programs with a bound on the number of errors
as considered here.

4.

B IT S YN: Bitstream Programs from Noisy Data

In this section we show how to instantiate the approach presented
earlier to the problem of building a programming-by-example(PBE) engine able to deal with up to K incorrect input/output examples in its input data set for the best program pbest . To illustrate
the process, we chose the domain of bitstream programs as they
are well understood and easy to implement, allowing us to focus on
studying the behavior of Algorithm 1 in a clean manner. We believe
many synthesis engines are good candidates for being extended todeal with noise (e.g., synthesis of floating point functions [28] ordata extraction [20]).
The setting We consider two scenarios: (1) the dataset D is obtained dynamically and the noise is bounded (i.e., up to K errors),and (2) the dataset D is present in advance and may contain an unknown number of errors. Interestingly, the second scenario is useful
beyond synthesizing programs, in this case, for anomaly detection.
We created a synthesizer called B IT S YN that generates loopfree bit manipulating code from input/output examples. The programs generated by B IT S YN are similar to those produced in Jha etal [18]. We use a library of instructions for addition, bitwise logicaloperations, equality, less than comparison and combine them into
a program that takes 32-bit integers as input and outputs one 32-bit
integer. The program may use registers to store intermediate values. The goal of the synthesizer is to take a number of input/output
examples and generate a program.
4.1 Program Generator with Errors
A key quality of B IT S YN is that it includes a program generator that
may not satisfy all provided input/output examples. This may serve
multiple purposes as we discuss later. Let us consider the following
example input/output pairs:
d1 = {{2 → 3}, {5 → 6}, {10 → 11}, {15 → 16}, {−2 → −2}}All examples except for {−2 → −2} describe a function that
increments its input. A problem with existing PBE engines in thiscase is that they succeed in generating a program even if it was not
the desired one, e.g. by producing the following code:
pa = return input + 1 + (input >> 8)
Note that providing more examples would not necessarily help
discover or solve this problem. The user may in fact get lucky bygetting into a situation where the synthesizer fails to produce a program, however if the hypothesis space of programs (e.g., which
operators is the engine allowed to use) is not very constrained,
this program can overfit to the incorrect examples. Later we quantify this problem. The problem of overfitting to the data (i.e., input/output examples) occurs in multiple mathematical and machinelearning problems where the provided specification does not permit
exactly one solution, for example when dealing with noise.
We combat overfitting by introducing regularization to the cost.
We define a function Ω : P → R+ that punishes overly complex
programs p by returning the number of instructions used. For our
example, Ω(pa ) = 3 since pa has three instructions (two + and one>>). Then, we create a program generator that minimizes:
rreg (d, p) = error rate(d, p) + λ · Ω(p).
The value λ ∈ R is a regularization constant that we choosein evaluation. The higher the regularization constant is, the more
importance we place on producing small programs. In our example,
if λ > 0.1, the cost rreg of the following pb program will be lower

Number of
instructions

0

Program
P1
P2
P3
P4
P5
P6
P7
P8
P9

1

2

3

4

5

6

7

Number of errors (K)8901Number of input/output examples needed
2
2
3
2
2
2
3
3
3

4
5
4
2
3
4
5
5
3

4
6
4
4
3
5
5
5

10
6
9
7
9
10
7
10

7
7
10
8
9
9
9
10

9
11
8
9
10
10
11
8

11
12
13
10
10
11
12
12

14
15
15
13
14
13
15
13

16
19
16
15
16
17
19
16

17
20
17
17
20
20
20
20

2

3

4

5

9

Synthesis time (seconds)
22
22
21
19
22
22
22
19

timeout

1.11
1.21
1.75
1.05
1.08
1.18
1.80
1.90
2.58

1.17
1.48
1.81
1.19
1.10
1.51
2.20
2.44

1.98
1.79
4.42
1.56
1.84
2.70
2.77
4.41

1.51
2.70
8.63
3.07
3.45
3.50
5.15
4.47

1.80
2.45
9.20
4.01
9.38
10.60
12.65
5.15

7.33
12.96
40.62
11.34
11.64
12.44
21.62
26.62

102.7672.37
156.0912.30
139.7591.49
117.16
41.46

timeout

timeout

timeout

timeout

timeout

timeout

Table 1. Number of input/output examples needed by BitSyn to synthesize the correct program (program taken from [18, 35])
depending on the number of errors in the examples as well as the synthesis time with the respective number of errors.
than the cost of pa on the dataset d1 :pb = return input + 1
Implementation We implemented B IT S YN using the Z3 SMT
solver [9]. At each query to the SMT solver, we encode the setof input/output examples d = {xi }ni=1 in a formula based on thetechniques described in [18]. In each formula given to the SMT
solver, we encode the length of the output program (called Ω later)
and we additionally encode a constraint for the number of allowed
errors. Let χi be a formula that is true iff example xi ∈ d issatisfied. Then, to encode a constraint that allows up to T errors,
we must satisfy the following formula:Υ ≡ T ≥nX

if χi then 0 else 1

i=1

To find the best scoring solution, we make multiple calls to the
SMT solver to satisfy Υ by iterating over the lengths of programsand the number of allowed incorrect input/output examples T ordered according to the cost of the solution and then return the firstobtained satisfiable assignment of instructions.
4.2

Case 1: Examples in D Are Provided Dynamically

A common scenario for programming-by-example engines is when
the input/output examples are obtained dynamically, either by interactively asking the user or by querying an automated reasoning
engine. Ultimately, this means that the entire dataset D is not directly observable by the program generator (in fact, the dataset may
be infinite). In this case, the synthesizer starts with a space of candidate programs and narrows that space by dynamically obtaining
more examples.
For this setting, we designed a hard dataset sampler using thecost function rK as described in Section 3. Our dataset sampler
attempts to create a dataset di+1 with K + 1 unsatisfied examples
for each program in the set of candidate programs explored so far
progs = {pj }i−1
j=1 . Generally, incorrect examples can be readily
obtained automatically from an SMT solver (or another tool). Whenthe tool is used interactively, the user needs to answer questions
until the desired number of errors is reached (that is, here, the user
takes an active part in the work of the dataset sampler).
Evaluation Our goal was to check if B IT S YN can synthesize
the correct program in the presence of errors. Towards this, we
implemented a simulated user that provides examples using a hard
dataset sampler with a known bound on the incorrect examples.
We aimed to answer the following research questions: (1) up to
how many errors does B IT S YN scale for synthesizing solutions?,and (2) how many (more) examples does B IT S YN need in order tocompensate for the incorrect examples? For our evaluation, we took

a number of programs from [18], on which an existing synthesizer
without noise could generate solutions within a few seconds. These
are the programs P1-P9 from the Hacker’s Delight book [35], also
evaluated in previous works [13, 18].
We summarize our results in Table 1. For each program, we
tried settings with different numbers of incorrect examples. We firstsupplied the incorrect examples and then started supplying correct
examples. In each cell in the left part of Table 1, we list the total number of input/output examples needed to obtain the correct
result. In the right part of Table 1, we list the time needed to complete each synthesis task. Our results can be summarized in twoareas: (1) overall, adding incorrect input/output examples complicates the program synthesis task. For tasks P 1−P 8, each synthesis
task completes within our timeout of 300 seconds. Task P 9 did notscale since it needs bit-shift operations and their presence leads todifficult formulas for the Z3 solver, and (2) the number of necessary
input/output examples overall increases with an increased numberof errors, but only slightly. Further, in some cases, the number ofneeded examples stays constant when introducing more errors. This
motivated us to ask the question explored next, which is whether
the tool is useful beyond synthesis, but also for detecting incorrect
examples (i.e., anomaly detection).
4.3

Case 2: All Examples in D Are Given in AdvanceAs a side question not directly related to Algorithm 1, we wanted
to understand how well the regularized program generator in B ITS YN detects incorrect examples in the setting where the dataset D is
fully available. Here, we provide all our examples to a regularized
generator and ask if the unsatisfied examples are exactly the incorrect ones. Such a setting of finding a model that describes data andthen detects outliers in the model is called anomaly detection [6].
Note that our approach is very different from recent work [5] which
considers a more restricted case where the program is already fully
available before the process of anomaly detection starts.
Evaluation We evaluate the anomaly detection capability of B ITS YN depending on the regularization constant λ and the number ofsamples present in D. For this experiment, we created data sets
D of various sizes and introduced an incorrect example in each ofthem. Then, we looked at how often the synthesized program did
not satisfy exactly the incorrect examples. We summarize the results in Fig. 3. The figure visualizes the conditions under which
the anomaly detection is effective on our test programs (P1-P9).
Every cell in the diagram of Fig. 3 says how often a given output
denote that the synthesizer successfully
occurs. The cells withsatisfied the provided examples, including the incorrect one. Thiscase typically occurs with no or low regularization. This means thatsynthesizers that fail to take noise into account will easily overfit to
the incorrect example and return valid, but incorrect programs.

0.22
0.16
λ
0.1
0.04
1

4

7
10
13
16
19
22
Total number of input/output examples

25

28

No example removed (overfitting to incorrect example)
Too many examples removed (overregularizing for simple programs)

program is generally intractable. To address these concerns, we
make two assumptions. First, we assume we are given a sample
D of examples drawn i.i.d. from S. We can approximate the riskR(p) by the empirical risk, i.e.,
1 X`(p, w)
remp (d, p) =|d|w∈dThen, we assume (for now) that we have an “oracle”, an algorithm
that can solve the empirical risk minimization (ERM) problem
pbest = arg min remp (D, p).

Noisy example correctly detected

Figure 3. Ability of BitSyn to detect an incorrect example forprograms (P1-P9) depending on total number of examples andregularization constant λ.
On the other hand, using too much regularization may bias B ITS YN towards producing too simple programs that do not satisfy
even some of the correct examples. We denote this with the pattern . The darker a pattern, the more often the corresponding issue occurs. In the white areas of the graph, B IT S YN reliably discovers the incorrect input/output example. For this to happen reliably,
our results show that we need a dataset with more than 10 examples
and a regularization constant λ between 0.05 and 0.1.

5.

Handling Unbounded NoiseIn this section, we investigate the case where we have no boundon the amount of noise in the dataset D. The key idea is to view
the problem of learning a program from a noisy dataset as anempirical risk minimization (ERM) task over a discrete search
space of programs. In fact, our approach can be seen as a new wayof performing approximate ERM on a discrete search space.
Next, we first review the concept of ERM and the guarantees
provided by statistical learning theory. In this case, we restrict D to
be a set obtained from a probability distribution S over examples
W, that is, D ⊆ W. In what follows, our cost function r is set to be
the empirical risk function (discussed below). Then, in Section 5.2,
we present our (novel) approach to performing approximate ERM.
5.1

Empirical Risk Minimization

Let ` : P × W → R≥0 be a function, such that for p ∈ P andw ∈ W, `(p, w) quantifies the loss (amount of inaccuracy) when
applying program p to example w. Later in Section 6.4 we show an
example of a loss function. Our task is to synthesize a programp∗ ∈ P that minimizes the expected loss on example w drawn
i.i.d. from distribution S (we assume w.l.o.g. S(w) > 0 for allw ∈ W). I.e., we seek to minimize the risk (defined in terms of the
expectation of the function):R(p) = Ew∼S [`(p, w)],i.e. find the program:p∗ = arg min R(p)p∈P

As a concrete example, `(p, w) could be 0 if p produces the “correct” output for w and 1 if it is incorrect. In this setting, R(p) corresponds to the expected number of mistakes that p makes on random
example w. Moreover, R(p) = 0 iff it is “correct” (i.e., produces
the correct behavior on all examples in S). As another example, p
could produce real-valued outputs, and `(p, w) could measure thesquared error between the correct output and the actual output.
There are two problems with computing p∗ using the above
approach. First, since S is unknown, the risk R(p) cannot even be
evaluated. Second, even if we could evaluate it, finding the bestp∈P

The above equation is in fact an instance of the problem stated in
Section 2.1.
Guarantees Standard arguments from statistical learning theory[21] now guarantee that, for any ε, δ > 0, if our dataset of examples D is big enough with respect to the space of programs([23, Chapters 7.3,7.4]), then it holds for the solution pbest thatR(pbest ) ≤ R(p∗ ) + ε, with probability at least 1 − δ (over the
random sampling of the dataset) [23]. Hence, the best-performing
program on the dataset is close (in risk) to the best program over
all of S. This is because under the above conditions, the empiricalrisk approximates the true risk uniformly well, i.e., for all p ∈ P it
holds that |R(p) − remp (D, p)| ≤ ε.
Regularization ERM solution can overfit if the dataset is notlarge enough [21]. Overfitting means that R(p∗ )  R(pbest ), i.e.,the ERM solution has much higher risk than the optimal program.
This often happens when the space of programs P under consideration is very complex, i.e., the solution could overfit by “memorizing” the training data and fail on other examples. As a remedy, acommon approach is to apply regularization: i.e., instead of minimizing the empirical risk, one modifies the objective function by:rreg (d, p) = remp (d, p) + λΩ(p)Hereby, Ω : P → R≥0 is a function (called regularizer), which
prefers “simple” programs. For example, Ω(p) could count the
number of instructions in p, i.e., a program is “simpler” if it contains fewer instructions. Note that the regularizer does not dependon the data set, it only depends on the program. The regularization
parameter λ, which controls the strength of our simplicity bias, isusually optimized over using a process called cross-validation. In
the following, we use the notation remp and refer to minimizing it
as ERM, whether or not we are applying regularization.
5.2

Using Representative Dataset Sampler

The complexity of solving ERM is heavily dependent on the sizeof the dataset D. This is due to the fact that evaluating remp or rreg
gets more expensive (since we need to sum over more examples).
To enable ERM on the large dataset D, we use Algorithm 1 witha representative dataset sampler dsR and a program generator thatsolves ERM on small datasets. Our goal here is to sample subsets
d1 , d2 , . . . dm ⊆ D, with the property that solving ERM on these
subsets leads to good solutions in terms of the (intractably large)
dataset D. Our goal upon termination of the synthesis procedure isto obtain a program pm for which:remp (D, pm ) ∈ [remp (D, pbest ), remp (D, pbest ) + ε]Then, recall that R(pbest ) ≤ R(p∗ ) + ε to obtain that the resulting
solution pm will have risk at most 2ε more than p∗ . On the other
hand, by exploiting the fact that we can solve ERM much faster on
small datasets di , we can find such a solution much more efficiently
than solving the ERM problem on the full dataset D (which canalso be practically infeasible). This instantiation is a new approachof performing approximate ERM over discrete search spaces.

6.

D EEP S YN: Learning Statistical CodeCompletion Systems

In this section we present a new approach for constructing statistical code completion systems. Such statistical code completion systems are typically trained on a large corpus of programs (i.e., “BigCode”) and are used to generate a (probabilistically) likely completion of a given input program. Currently, the predictions madeby existing systems (e.g., [16, 24, 30]) are “hard-wired” (see Section 8 for further discussion), limiting their expressiveness and precision and requiring changes to this hard-wired strategy for different kinds of predictions. The approach presented here cleanly
generalizes these existing approaches.
While not obvious, we will see that the problem of synthesizing
a program from noisy data appears in this setting as well, and thus
the general framework of synthesis with noise discussed so far also
applies here. However, unlike the first-order setting described in
Section 4 where the data is simply a set of input-output examples
and the learned program tries to explain these examples and predict
new examples, the learned program in this section is second-order.
This means that the learned program does not predict its output
directly from the input, but instead is used as part of a probabilistic
model that performs the final prediction seen by the developer.
6.1

Preliminaries

To fix terminology, we will refer to the program that is to be completed as a tree (a shortcut for Abstract Syntax Trees). The reason we choose trees as a representation of the program is because
trees provide a reasonable way to navigate over the program elements. We begin with a standard definition of context-free grammars (CFGs), trees and parse trees.
Definition 6.1 (CFG). A context-free grammar (CFG) is thequadruple (N, Σ, s, R) where N is a set of non-terminal symbols,Σ is a set of terminal symbols, s ∈ N is a start symbol, R is a finite
set of production rules of the form α → β1 ...βn with α ∈ N andβi ∈ N ∪ Σ for i ∈ [1..n].
In the whole exposition, we will assume that we are given a fixed
CFG: G = (N, Σ, s, R).
Definition 6.2 (Tree). A tree T is a tuple (X, x0 , ξ) where X is a
finite set of nodes, x0 ∈ X is the root node and ξ : X → X ∗ isa function that given a node returns a list of its children. A tree isacyclic and connected graph: every node except the root appears
exactly once in all the lists of children. Finally, no node has the root
as a child.
Definition 6.3 (Partial parse tree). A parse tree is a triple (T, G, σ)where T = (X, x0 , ξ) is a tree, G = (N, Σ, s, R) is a CFG, andσ : X → Σ ∪ N attaches a terminal or non-terminal symbol toevery node of the tree such that: if ξ(x) = xa1 ...xan (n > 1), then∃(α → β1 ...βn ) ∈ R with σ(x) = α and ∀i ∈ 1..n.σ(xai ) = βi .
Note that the condition for a partial parse tree requires that thetree follows the grammar production rules, but does not require allleaves to be terminal symbols. Let the set of all partial parse trees
be P T . Next, we define what is a tree completion query.
Definition 6.4 (Tree completion query). A tree completion queryis a triple (ptree, xcomp , rules) where ptree = (T, G, σ) isa partial tree (with T = (X, x0 , ξ)), xcomp ∈ X is a node labeledwith a non-terminal symbol where a completion will be performed,
and rules = {σ(xcomp ) → β i }ni=1 is the set of available rulesthat one can apply at the node xcomp .
Using the above definitions, we can now state the precise problem that is solved by this section.

ptree =

GetP rop
Objectrules:

P roperty

V ar
xcomp
consoleP roperty → x
P roperty → y
P roperty → log
P roperty → info...

Figure 4. A tree completion query (ptree, xcomp , rules) corresponding to completion for the code: ”console”.
Problem statement The code completion problem we are solving
can now be stated as follows:
Given a query, select the most likely rule from the set of available rules and complete the partial tree ptree with it.
For the completions we consider, the right hand side β of eachrule is a terminal symbol (e.g., a single API). In principle, one canmake longer completions by iteratively chaining smaller ones.
Example: Field/API completion Consider the following partial
JavaScript code ”console.” which the user is interested in completing. The goal of a completion system is to predict the API calllog, which is probably the most likely one for console. Now consider a simplified CFG that can parse such programs (to avoid clutter, we only list the grammar rules):GetP rop
ObjectV ar
P roperty→→→→

Object P roperty
V ar | GetP rop
console | document | ... (other variables)
info | log | ... (other properties incl. APIs)

The tree completion query for this example is illustrated in Fig. 4.
6.2

Our Method: Second-order learning

The key idea of our solution is to synthesize a program which
conditions the prediction. That is, rather than statically hard-wiring
the context on which the prediction depends on as in prior work
(e.g., [16, 30]), we use the program to dynamically determine thecontext for the particular query. For our example, given a partial
tree ptree and a position xcomp , the program determines that theprediction of the API call should depend on the context console.
In our setting, a context c ∈ Context is a sequence ranging
over terminal and non-terminal symbols seen in the tree, as well as
integers. That is, Context = (N ∪ Σ ∪ N)∗ . We next describe ourmethod in a step-by-step manner and then elaborate on some of thesteps in more detail.
Step 1: Learn a conditioning program p≈best As a first step,
we will begin by learning the best (conditioning) program p≈best .
Indeed, it is in this first step of learning where the key concepts ofdataset sampling and program generation discussed earlier, arise.
Let d = {X i , Y i }ni=1 be the training dataset of queriesi
X = (ptreei , xicomp , rules) along with their corresponding completions Y i ∈ rules. We assume that all examples in d solve thesame task (e.g., API completion) and thus they share rules. The
goal of this step is to synthesize the (approximately) best conditioning program p≈best ∈ P T × X → Context that given aquery returns the context on which to condition the prediction. For
instance, for the example in Fig. 4, a possible program p could produce p(ptree, xcomp ) = [console]. In Section 6.3, we present a
domain-specific language from which the conditioning program isdrawn while in Section 6.4 we elaborate on this step in detail.
Step 2: Learn a probabilistic model P (rule | context) Afterp≈best is learned, we use the resulting program to train a probabilistic model. Given our training dataset d as described above, we

(a)

(c)

GetP rop

ObjectP roperty

V ar

1.Left2.WriteValue

consoleComplete

GetP rop
Object P ropertyHPM
LE (rule|console)

V ar

(b)

Rule

H
PM
LE

P roperty → log
P roperty → info

0.5
0.4

log

consoleFigure 5. (a) TCond program pa = Left WriteValue executedon a partial tree producing [console], (b) rules with theirprobabilities conditioned on [console], (c) the final completion.

Ops ::=

 | Op Ops

Op ::= WriteOp | MoveOp
WriteOp ::= WriteValue | WritePos | WriteAction
MoveOp ::= Up | Left | DownFirst | DownLast | PrevDFS |PrevLeaf | PrevNodeType | PrevActor

Figure 6. The TCond language for extracting context fromtrees.
next apply p≈best to every query in the training data, obtaining a
new data set (here Qi = (ptreei , xicomp )):H(d, p≈best ) = {(p≈best (Qi ), Y i ) | ((Qi , rules), Y i ) ∈ d}
The derived data set consists of a number of pairs where eachpair {(ci , ri )} indicates that rule ri is triggered by context ci ∈Context. Based on this derived set, we can now train a probabilistic model using MLE training (maximum likelihood estimation) which estimates the true probability P (r | c). The MLE
estimation is standard and is computed as follows:H
PM
LE (r | c) =|{i | (ci , ri ) ∈ H, ci = c, ri = r}||{i | (ci , ri ) ∈ H, ci = c}|

The MLE simply counts the number of times rule r appears incontext c and divides it by the number of times context c appears.
As we will see later in Section 6.4, MLE learning as describedabove is also used in step 1.
Step 3: Dynamic prediction Once we have learned the conditioning program p≈best and the probabilistic model P (rule | context),
we use both components to perform prediction. That is, given aquery (ptree, xcomp , rules), we first compute the context ctx =p≈best (ptree, xcomp ). Once the context is obtained, we can use
the trained probabilistic model to select the best completion (i.e.,the most likely rule) from the set of available rules:H
rule = arg max PM
LE (r | ctx)r∈rules

To illustrate the prediction on an example, consider the query
shown in Fig. 5 (a) (this is the same query as in Fig. 4, repeated here
for convenience). In this example, the program p≈best consists of
two instructions: one moves left in the tree and the other one writes
the element at the current position (we will see exact semantics ofthese instructions in Section 6.3). When applied to the given query,the program produces the context ctx consisting of the sole symbol
console. Once the context is obtained, we can simply look up theHprobabilistic model PM
LE to find the most likely rule given thecontext (we list some of the rules and their probability in Fig. 5(b)). Finally, we complete the query as shown in Fig. 5 (c).

6.3

TC OND: Domain Specific Language for Tree Contexts

We now present a domain specific language, called TC OND, forexpressing the conditioning function p. The language is loop-free
and is summarized in Fig. 6. We next provide an informal introduction to TC OND. Every statement of the language transforms a stateυ ∈ P T × X × Context. The state contains a partial tree, a position in the partial tree and the (currently) accumulated context. The
partial tree is not modified during program execution but position
and the context may be.
The language has two types of instructions: movement (MoveOp)
and write instructions (WriteOp). The program is executed until
the last instruction and the accumulated context is returned as theresult of the program.
Move instructions change the node in a state as follows:
MoveOp(ptree, node, ctx) −−−−→ (ptree, node0 , ctx). Depending on the0operation, node is set to either the node on the left of node (forLeft), to the parent of node (for Up), to the first child of node(for DownFirst), to the last child of node (for DownLast), tothe last leaf node in the tree on the left of node (for PrevLeaf),to the previous node in depth-first search traversal order of thetree (for PrevDFS). When node is a non-terminal symbol, thePrevNodeType instruction moves to the previous non-terminal
symbol of the same type that is left of node.
Write instructions update the context of a state as follows:
WriteOp(ptree, node, ctx) −−−−→ (ptree, node, ctx · x), where depending on the instruction, different value x is appended to the context.
For the WriteValue instruction, the value of the terminal symbol
below node is written (if there is one, otherwise x = −1). For the
WritePos instruction, if parent is the parent node of node, thenx is set to the index of node in the list of the children of parent.
The PrevActor and WriteAction instructions use a simple
lightweight static analysis. If node denotes a memory location(field, local or global variable, that we call actor), PrevActor
moves to the previous mention of the same memory location in thetree. Our static analysis ignores loops, branches and function calls
thus previous here refers to the occurrence of the memory locationon the left of node in the tree. WriteAction writes the name ofthe operation performed on the object referred by node. In case theobject referred by node is used for a field access, WriteAction
will write the field name being read from the object. In case theobject node is used with another operation (e.g., +), the operation
will be recorded in the context. An example of a program execution
was already discussed for the example in shown in Fig. 5 (moreexamples can be seen in Fig. 9 (c), discussed later).
For a program p ∈ Ops, we write p(ptree, xcomp ) = ctx topdenote that (ptree, xcomp , ) −→ (ptree, node0 , ctx).
6.4

Learning p≈best

We next describe step 1 of our method in greater detail. The key objective of this step is to synthesize a conditioning program p≈best .
In fact, as we will see in Section 7.4, several existing code completion systems [16, 30] can be seen as hard-wired programs p for
specific tasks. We now define what it means for a synthesized program p to perform well (i.e. we define our cost function r) and thenwe describe the program generator and the representative dataset
sampler dsR that we use for Algorithm 1.
Building a probabilistic model As described earlier, we areiigiven a dataset d = {X i , Y i }n=i=1 of queries X where Xii(ptree , xcomp , rules), along with their corresponding completions Y i ∈ rules. For a program p and a dataset d we can thenderive a new data set by applying the program to every query ind, obtaining the resulting context, and storing that context and thegiven prediction together as a tuple, i.e., Qi = (ptreei , xicomp ):iTraining data DiH(d, p) = {(p(Qi ), Y ) | ((Qi , rules), Y ) ∈ d}
Let us partition the given dataset d into two non-overlapping
parts – dtrain and deval . We then obtain the derived (training)set H t (d, p) = H(dtrain , p) from which we build a probability
H t (d,p)
distribution PM LE as outlined earlier.
Scoring the probabilistic model To evaluate the probabilistic
model, we use the measure of perplexity of the derived (evaluaH t (d,p)tion) set H e (d, p) = H(deval , p) on the learned model PM LE .
Log-perplexity is a measure of how many bits we need to encode
the evaluation data with the model from the training data and provides insight not only on the error rate, but also how often a result
is at a high rank and is produced with high confidence. In an empirical risk minimization setting, we use the log-perplexity to define
the loss function on a single example (ctx, rule):H t (d,p)`perp (p, (ctx, rule)) = − log2 PM LE(rule | ctx)

Based on this loss function, we now define regularized empiricalrisk rregperp as in Section 5.1:
X1
rregperp (d, p) =`perp (p, w) + λ · Ω(p),|H e (d, p)|ew∈H (d,p)where Ω is a regularizer function that returns the number of instructions in p. For all our experiments, we use λ = 0.05.
Program generators and dataset samplers Using the cost function rregperp (d, p), we can now define the rest of the components
and plug them into Algorithm 1. For our implementation, we use
approximate versions of a program generator and a representative
dataset sampler realized with random mutations and genetic programming.
An approximate program generator gen≈ takes a dataset di andan initial program pi−1 . Then, the program generator keeps a list of
candidate programs and iteratively updates the list in the following
manner. First, gen≈ takes one candidate program, then performs
random mutations on the instructions of the program, scores themodified program on the given dataset di and then it adds it to thelist. Using a genetic-programming like procedure, gen≈ randomly
removes from the list candidate programs that score worse than another candidate program. After a fixed number of iterations, gen≈returns the best scoring program pi ≈ arg minp∈P rregperp (di , p).
Our approximate dataset sampler dsR≈ keeps tracks of thecosts on the full dataset D for all programs {pj }i−1
j=1 generated
by gen≈ . Once a new program pj is generated, dsR≈ computes
rregperp (D, pj ). Then, using a genetic-programming like procedure dsR≈ keeps a like of candidate dataset samples and iteratively
updates the list. At each iteration, dsR≈ takes a dataset and randomly resamples its elements (such that the mutated dataset is⊆ D), scores the dataset and adds it to the list. Then dsR≈ randomly
removes from the list candidate datasets that are less representative
than another candidate dataset. After a fixed number of iterations
dsR≈ returns the dataset di ⊆ D which is approximately the mostrepresentative for progs = {pj }i−1
j=1 according to Definition 2.4.
Termination condition We have chosen a time-based termination
condition. After some fixed time limit for training expires, wereturn the (approximately) best learned program p≈best obtained
up to that moment. This is, from the programs p1 , ..., pm produced
up to the time limit by Algorithm 1, we return as p≈best the onethat has the best cost on the full dataset D.
Smoothing An important detail for increasing the precision of thesystem is using smoothing when computing the maximum likelihood estimate at any stage of the system. In our implementation,DD

sample di ⊆ D

dsR≈

Algorithm 1p≈bestgen≈

candidate program pi

Train full system

Figure 7. Overall diagram of learning a statistical code completion system using DeepSyn.
we use Witten-Bell interpolation smoothing [36]. Smoothing ensures our system performs well even in cases when a context was
not seen in the training data. Consider for example looking for the
probability of PM LE (rule | c1 c2 c3 ) which is a complex context
of three observations in the tree. If such a context was not seenin the training data, to estimate reasonable probabilities we backoff to a simpler context with only c1 c2 in it. Then, we expect to see
more dense data in estimating PM LE (rule | c1 c2 ). To enable suchbackoff in PM LE (rule | c1 c2 ), at training time PM LE counts theevents conditioned on the full context and conditioned on all theprefixes of the full context.
6.5

Summary of Approach

To summarize, our approach to learning consists of two steps summarized in Fig. 7. In the first step, we learn the conditioning
program p≈best . That is, given a dataset D, we first use Algorithm 1, gen≈ and dsR≈ to find a program p≈best for which the cost
rregperp (D, p) is minimized. Then, in the second step, we a learn
H(D,p)
a probabilistic model PM LE ≈best over the full dataset D and theprogram p≈best (discussed earlier).
This model, together with p≈best can then be used to answer
field/API completion queries from the programmer. We show in
Section 7.1 that the speed-up from Algorithm 1 equipped with arepresentative dataset sampler lead to high accuracy of the resulting
statistical synthesizer.

7.

Evaluation of D EEP S YN

Based on Section 6, we created a statistical code completion system
for JavaScript programs. This is a particularly hard setting forcode completion systems as unlike in other languages (e.g., Java)
where type information is easily available and is of significant help
(e.g., as in [30]), in JavaScript, obtaining precise aliasing and type
information is a difficult task (stressing the prediction capabilitiesof the system in the presence of noise, even further). The concretetask we consider is “dot” completion: given a receiver object, thecompletion should predict the field name or the API name thatshould be used on the object. All our experiments were performed
on a 2.13 GHz Intel Xeon E7-4830 32-core machine with 256 GB
of RAM, running 64-bit Ubuntu 14.04. To benefit from the amountof cores, we implemented the gen≈ and dsR≈ procedures to evaluate
multiple candidate programs or datasets in parallel.
To train and evaluate our system, we collected JavaScript
programs from GitHub, removed duplicate files or project forks(copy of another existing repository) and kept only programs thatparse and are not obfuscated. As a result, we obtained 150, 000
JavaScript files. We used two thirds of the data for learning, and thelast one third only for evaluation.
7.1

Learning p≈best

We now discuss our training procedure. The first question we may
ask is if using Algorithm 1 with a representative dataset sampler

log2 (Perplexity) + Regularization
16

gen≈ on full datagen≈ with randomly increasing sample

12.8

gen≈ on fixed sample

10.3
8.2
6.6

DeepSyn(gen≈ with dsR
≈)

5.3
0

10

20

30
40
Time in minutes

50

60

Figure 8. Effect of various data sampling policies used to findTCond programs.
(dsR≈ ) is of any benefit to the speed or precision of the system. To

Task

Size of training data (files)
1K
10K
100K

DOM APIs on document object
correct completion at position 1
correct completion in top 3
correct completion in top 8

63.2%
90.1%
83.5%

69.2%
84.6%
88.6%

77.0%
89.9%
92.9%

Unrestricted API completion
correct completion at position 1
correct completion in top 3
correct completion in top 8

22.6%
30.8%
33.6%

34.2%
44.5%
47.7%

50.4%
61.9%
64.9%

Field (non-API) completion
correct completion at position 1
correct completion in top 3
correct completion in top 8

21.0%
26.3%
28.0%

29.7%
37.0%
38.8%

38.9%
48.9%
51.4%

Table 2. Accuracy of API method and object field completion
depending on the task and the amount of training data.

answer this question, we designed a number of system variants:• D EEP S YN(gen≈ with dsR≈ ) is our system as described Fig. 7.

For this system, we start with a random sample of 100 programsand then through the loop of Algorithm 1, we modify the sample to be more representative.
• gen≈ on full data is a system that directly optimizes the pro-gram on the full dataset D. Because each evaluation takes along time, this system can only try a smaller number of candidate programs and finds only very imprecise programs.
• gen≈ on fixed sample is a system that starts with a random

sample of 100 programs and optimizes the program only on
the small sample. This policy has the time budget to explore alarge number of programs, but is unable to provide reasonable
score for them. It quickly reaches a cap on what can be learnedon the small dataset.
• gen≈ with randomly increasing sample is a system that starts

with a small random sample and iteratively increases its size. It
performs no optimization of the sample for representativeness,just adds more elements to it.
The results summarized in Fig. 8 illustrate the effectiveness ofeach of the four approaches. Each plot gives the rregperp of thecandidate program p≈best found by a system at a given time. Notethat lower values of log-perplexity are better and in fact are exponentially better. The graph shows that our full D EEP S YN system
initially spends time to find the best sample, but then reaches thebest program of all systems. If provided with infinite time, gen≈on full data will approach the optimal program, but in practice it isprohibitively slow and has far worse performance.
We note that the synthesizer with randomly increasing sample
appears to find a reasonable program faster than when using dsR≈.
The reason for this is that this procedure did not evaluate its result on the full dataset dataset (we evaluated the programs after
the procedure completed). If we include the time to evaluate thecandidate programs, this setting would not be as fast as it appears.
Next, we take the best program obtained after one hour ofcomputation by D EEP S YN and analyze it in detail.
7.2

Precision of D EEP S YN

Once we obtain the best TC OND program, we create a completion
system based on it, train it on our learning dataset and evaluate
it on the evaluation dataset. For each file in the evaluation dataset
we randomly selected 100 method calls and queried our system topredict the correct completion one at a time. Given the evaluation
dataset of 50, 000 programs, this resulted in invoking the predictionof 2, 537, 415 methods for any API and 48, 390 methods when
predicting method calls on DOM document object.
The accuracy results are summarized in Table 2. The columnsof the table represent systems trained on different amounts of training data. The right-most column trains on all 100, 000 JavaScript
programs in the training set and the columns on the left use a subsetof this data. Different rows on Table 2 include information for different tasks. On the task of predicting DOM APIs on the document
object, the APIs are shared across all projects and the accuracy ishigher – the correct completion is the first suggestion in 77% of
the cases. When we extend the completion to any APIs, including
APIs local to each project that the model may not know about, theaccuracy drops to 50.4%. Finally, when used on non-API property
completions, our completion system predicts the correct field nameas a first suggestion in 38.9% of the cases.
7.3

Interpreting p≈best

A key aspect of TC OND programs is that they are easily readable
by a human. The best program is listed with its instructions in Fig. 9(a). Let us illustrate what this program does on a JavaScript code
completion query from Fig. 9 (b). Going instruction by instruction,
Fig. 9 (c) shows the execution. First, the program moves to the leftof the completion position in the tree (i.e., to the receiver object of
the completion). Then, it moves to the previous usage of the same
object (PrevActor), writes the action being done on the project(i.e., the name of the field of API invoked). Next, it writes the nameof the variable (if any) and moves to the previous usage of the same
object, etc. Finally, at instruction 9, it cannot move anymore andthe program stops and returns the accumulated sequence so far. For
our example, the program accumulates the following context:
querySelectorAll document querySelectorAll show
7.4

Comparison to Existing Systems

We note that previous works essentially use a hard-coded tree conditioning program. In some of the works immediate context isused – the non-terminals directly preceding the completion location [1, 16]. Other works hardcode the move to the previous API
on the receiver object and condition on the API. Such knowledge
is key in [30] and [24]. In fact, we mimic the behavior of [30] witha TC OND program and show that our best synthesized program issuperior. The context in [24] is more complex than a sequence (it isa graph), but in their experiments, even in a simpler setting within
one project they report lower accuracy than our system.
Note that these statistical code completion systems target Java,
which makes it much easier to perform static program analysis(e.g., type analysis, alias analysis). Despite these differences, weIf

9.PrevLeafp≈best =Left PrevActor WriteAction WriteValue
PrevActor WriteAction PrevLeaf
WriteValue PrevLeaf WriteValueV ar

7.PrevLeaf

show
8.WriteValue(a) TCond program

BlockStatement(b) JavaScript code snippet

GetP rop

CallExpression

CallExpression

CallExpression
if (show) {var cws = document.querySelectorAll(...);for (var i = 0, slide; slide = cws[i]; i++) {slide.classList.add("hidden");}var iap = document.querySelectorAll(...);for (var i = 0, slide; slide = iap[i]; i++) {slide.classList.add("hidden");}var dart = document.
Completion position...
}

5.PrevActor

GetP rop

2.PrevActor

GetP rop

ObjectP roperty

ObjectP roperty

ObjectV arquerySelectorAll

V arquerySelectorAll

V ar

6.WriteAction

1.Left3.WriteAction
document

document

P roperty

document

4.WriteValue(c) Execution of p≈best on the AST representation of the code snippet from (b)Figure 9. The (a) p≈best TCond program describing which parts of the code to condition on for an API method completion task,(b) a JavaScript code snippet on which we want to perform API completion, and (c) a relevant part of the AST representation of(b) where the execution of the TCond program from (a) is illustrated.
created TC OND programs that mimic the behavior of some ofthese for JavaScript API completions. Next, we review these programs and compare their accuracy to D EEP S YN using the best program p≈best in Fig. 9 (a). Recall that the accuracy on predicting
JavaScript APIs for this program is 50.4%.
Hindle et al. [16] use an 3-gram language model on the tokenizedprogram without doing any semantic analysis. This results in a
predictor for JavaScript APIs with accuracy of 22.2%. The programthat corresponds to this model is:
PrevDFS WriteValue PrevDFS WriteValue
Raychev et al. [30] perform a more complicated conditioning that
depends on the previous APIs of the same object as well as whether
the object was used as a receiver or as a method parameter. Thisconditioning is captured in the following program:
Left PrevActor WriteAction WritePos
PrevActor WriteAction WritePos
The accuracy of this program for JavaScript APIs is 30.4%.
Variants of D EEP S YN In addition to the best possible programp≈best , we include the programs generated by our tool with different data sampling procedures.
• gen≈ on full data operates on the full data and within one hour

it could not learn to condition on previous APIs. The program
learned by this synthesis procedure is
Left DownLast WriteValue PrevNodeType DownLast
PrevDFS PrevLeaf WriteValue DownLast PrevLeaf
Left WriteAction PrevNodeType WriteValueand results in 46.3% accuracy.
• gen≈ on fixed sample only learns a program from a small sam-ple of 100 programs and results in a simple conditioning that
only depends on a single previous API. The resulting accuracy
for JavaScript API completion is 18.8% with the program
PrevDFS PrevActor WriteAction• gen≈ with randomly increasing sample iteratively increases

the sample and results in a program that has accuracy of 47.5%
which is lower than our best accuracy of 50.4%. The program
generated by randomly increasing the sample size conditions
on one previous API, but the rest of the program is not optimal

Left PrevActor WriteAction
DownLast PrevActor PrevNodeType WriteAction
WriteValue Left PrevLeaf WriteValue
Summary Overall, we have shown that our approach of learning atree conditioning program in a domain specific language (TC OND)
exceeds the accuracy of systems where an expert hard-wired theprediction, as used in previous systems. The accuracy is achieved
thanks to our general approach – a program generator that predicts
a program from a small dataset (gen≈ ) and a representative dataset
sampler that makes the small set behave similarly to the large
training data (dsR
≈ ).

8.

Related WorkAs our work touches on several areas, below we survey some of theexisting results that are most closely related to ours.
Boolean program synthesis Over the last few years, there has
been an increased interest in various forms of synthesis. Examplesof recent techniques include synthesis from examples [18], partial
programs [32] and synchronization [34]. A more detailed survey ofthe various approaches can be found here [11]. Generally, however,these are approaches which attempt to satisfy all provided examples and constraints. Thus, they typically over-fit to the data, and as
a result, incorrect examples in the data set will lead to incorrectly
learned programs (or no programs at all). Some approaches comewith various fine-tuned ranking functions which assign preference
to the (potentially many) synthesized programs. However, regardless of how good the ranking function is, if the data set contains
even one wrong example, then the ranking function will be of little use, as it will simply rank incorrect programs. In contrast, ourapproach deals with noise and is able to synthesize desirable programs even in the presence of incorrect examples. It achieves thatvia both, the usage of regularizers which combat over-fitting, andsmart, iterative sampling of the entire data set. As we showed in thepaper, a standard all-or-nothing synthesis approach can be extended
to incorporate and benefit from our techniques.
The work of Menon et al. [22] proposes to speed-up the synthesis process by using machine learning features that guide the searchover candidate programs. This approach enables a faster decisionprocedure for synthesizing a program, but fundamentally requires
all provided input/examples to be satisfied.
Quantitative program synthesis Another line of work is that ofsynthesis with quantitative objectives [7, 33]. Here, it is possible tospecify a quantitative specification (e.g., a probabilistic assertion)and to synthesize a program that satisfies that weaker specification
while maximizing some quantitative objective. In our setting, one
can think of the dataset D as being the specification, however, weessentially learn how to relax the spec, and do not require the user
to provide it (which can be difficult). Further, our entire setting isvery different, from the iterative sampling loop, to the fact that even
if the specification can be fully satisfied, our approach need notsatisfy it (e.g., due to regularization constraints). In the future, it
may be useful to think of ways to bridge these directions.
Statistical code completion An emerging research area and one
related to our work is that of learning probabilistic models from alarge set of programs (i.e., “Big Code”) and using those models to
make statistical predictions for how a partial code fragment should
be completed. Existing systems are typically hard-wired to workwith a specific prediction strategy and are based on a simple token
completion via the n-gram language model [16], on tokens withadded annotations [25], other API calls [24, 30], expressions [14],or tree substitutions in the AST [2]. Unfortunately, these systems
either have very low precision (e.g., [16]) or target restricted scenarios (e.g., APIs in [30]). Unlike these techniques, in our approach
the prediction can be conditioned on functions that are expressedin a DSL and are learned from data, leading to better precision,and better support for different kinds of completions (as we sharethe same learning mechanism for any function in the DSL). Further, because the predictions are conditioned on the context built
from evaluating a function, the justification behind a prediction isunderstandable to a programmer using the system. Thus, our approach generalizes some of the existing works, is experimentallymore precise and the predictions are explainable to end users.
Discriminative learning In contrast to the generative learning
performed in this work, some applications may enjoy a much better
speed and precision with a discriminative model that performs classification without the need to build a probability distribution. One
such case is a model tailored specifically to predicting annotations
or variable names [29]. However, [29] cannot explain its predictions in terms of a program and requires manually provided feature functions in advance whose weights it learns. Despite not performing discriminative training, our approach essentially learns one
class of feature functions (or one model). A possible way to extend
our work is to enable learning a model that is a linear combinationof several of the best models that we currently learn. The weights ofsuch a linear combination can be then trained using structured support vector machine or another discriminative training procedure.
We note that using such a linear combinations of models was applied in machine translation and is part of the current state-of-theart systems [27]. We believe that extending this work to generate alinear combination of programs is an interesting future work item.
Core sets A core set is a concept in machine learning used tosummarize a large data set into a smaller data set that preserves
its properties. Core sets were successfully applied in the context ofclustering such as k-means [15]. Obtaining core sets from a data set
is a procedure that is manually tailored to the particular problem
at hand (e.g., k-means), that is, there are currently no universal
techniques for constructing core sets for arbitrary programs. In
contrast, our work is not based on a specific algorithm or property
such as k-means. In fact, an ideal outcome of our sampling stepis to compute or approximate a core set of the training data. Aninteresting question for future work is to explore the connection
between core sets and our iterative sampling algorithm.

Genetic algorithms Genetic programming has been proposed asa general approach to explore a large set of candidates in order todiscover a solution that maximizes an objective function [4, 31].
The following work [8] discusses the language design decisions to
encode a program synthesis problem from input/output examples
into genetic programming. Some of the problems studied here interms of selecting subset of the evaluation data to score instanceswere considered in the context of genetic programming. A technique known as stochastic sampling [3] reduces the number of evaluations by only considering random subsets of the training data. In
our experiments, however, we show that using our strategy of representative sampling is superior than using random sampling.
Dataset cleaning A different approach for dealing with noisy
data is to clean up the data beforehand either with a statisticalmodel [6], or with an already given program [5]. These approaches,
however need additional statistical assumptions about the data or
specification of another program. In contrast, in this work, we
simultaneously build the cleaned dataset and the program.
Probabilistic programs A recent synthesizer PSketch [26] performs synthesis of probabilistic programs by approximating the
program by a mixture of Gaussians. Fundamentally, probabilistic
programs interpret program executions as distributions and then forthe synthesis task is fits parameters to these distributions. Instead,with our approach we learn deterministic programs that approximate a dataset well. In general, our idea of a dataset sampler should
be applicable also to learning probabilistic programs from data, but
we leave this as a future work.
Automatic configuration of algorithms ParamILS [17] picks aconfiguration of an algorithm based on its performance on a dataset.
Similar to our approach, ParamILS attempts to speed-up the evaluation of a configuration by running on a small subset of the full
dataset, but only does so by picking a random sample.

9.

Conclusion

We presented a new approach for learning programs from noisy
datasets of arbitrary size. We instantiated our approach to two important noise settings: the setting where we can place a bound on
the noise and the setting where the dataset contains unbounded
noise. We showed that the second setting leads to a new way of performing approximate empirical risk minimization over hypotheses
classes formed by discrete search spaces. We then illustrated how
to instantiate the different noise settings for building practical synthesizers that are able to deal with noisy datasets.
We first presented a synthesizer for bit-stream programs, called
B IT S YN. Our experimental results with B IT S YN indicate that in thesetting of bounded noise, our system returns the correct program
even in the presence of incorrect examples (and with only a small
increase in the number of necessary examples compared to thesetting without noise). We also showed that B IT S YN is usefulfor automatically detecting anomalies, without requiring an input
program or statistical assumptions on the data.
Second, we presented a new technique for constructing statistical code completion engines based on “Big Code” which generalizes several existing works. The core idea is to define a DSL overtrees and to learn functions in this DSL from the dataset. These
learned functions then control the prediction made by the statisticalsynthesizer. We implemented our technique in a code completion
system for JavaScript, called D EEP S YN, and showed that its predictions are more precise than existing works.
We believe this is the first comprehensive work that deals withthe problem of learning programs from noisy datasets, and canserve as a basis for building new kinds of prediction engines thatcan deal with uncertainty.

Acknowledgements
The research leading to these results was partially supported by an
ERC Starting Grant 680358.

References[1] A LLAMANIS , M., AND S UTTON , C. Mining source code repositories
at massive scale using language modeling. In MSR (2013).
[2] A LLAMANIS , M., AND S UTTON , C. Mining idioms from sourcecode. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (New York, NY,
USA, 2014), FSE 2014, ACM, pp. 472–483.
[3] BAKER , J. E. Reducing bias and inefficiency in the selection algorithm. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application (Hillsdale, NJ, USA, 1987), L. Erlbaum Associates Inc., pp. 14–21.
[4] BANZHAF, W., F RANCONE , F. D., K ELLER , R. E., AND N ORDIN , P.
Genetic Programming: An Introduction: on the Automatic Evolutionof Computer Programs and Its Applications. Morgan Kaufmann
Publishers Inc., San Francisco, CA, USA, 1998.
[5] BAROWY, D. W., G OCHEV, D., AND B ERGER , E. D. Checkcell:
Data debugging for spreadsheets. In Proceedings of the 2014 ACM
International Conference on Object Oriented Programming Systems
Languages &#38; Applications (New York, NY, USA, 2014), OOPSLA ’14, ACM, pp. 507–523.
[6] C HANDOLA , V., BANERJEE , A., AND K UMAR , V. Anomaly detection: A survey. ACM Comput. Surv. 41, 3 (July 2009), 15:1–15:58.
[7] C HAUDHURI , S., C LOCHARD , M., AND S OLAR -L EZAMA , A.
Bridging boolean and quantitative synthesis using smoothed proof
search. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New York, NY, USA,2014), POPL ’14, ACM, pp. 207–220.
[8] C RAMER , N. L. A representation for the adaptive generation of
simple sequential programs. In Proceedings of the 1st International
Conference on Genetic Algorithms (Hillsdale, NJ, USA, 1985), L.
Erlbaum Associates Inc., pp. 183–187.
[9] D E M OURA , L., AND B JØRNER , N.
Z3: An efficient smt
solver. In Proceedings of the Theory and Practice of Software,
14th International Conference on Tools and Algorithms for theConstruction and Analysis of Systems (Berlin, Heidelberg, 2008),
TACAS’08/ETAPS’08, Springer-Verlag, pp. 337–340.
[10] Github code search. https://github.com/search.
[11] G ULWANI , S. Dimensions in program synthesis. In Proceedings ofthe 12th International ACM SIGPLAN Symposium on Principles andPractice of Declarative Programming (New York, NY, USA, 2010),
PPDP ’10, ACM, pp. 13–24.
[12] G ULWANI , S. Automating string processing in spreadsheets using
input-output examples. In Proceedings of the 38th Annual ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New York, NY, USA, 2011), POPL ’11, ACM, pp. 317–330.
[13] G ULWANI , S., J HA , S., T IWARI , A., AND V ENKATESAN , R. Synthesis of loop-free programs. In Proceedings of the 32Nd ACM SIGPLAN
Conference on Programming Language Design and Implementation(New York, NY, USA, 2011), PLDI ’11, ACM, pp. 62–73.
[14] G VERO , T., K UNCAK , V., K URAJ , I., AND P ISKAC , R. Complete
completion using types and weights. In Proceedings of the 34th
ACM SIGPLAN Conference on Programming Language Design and
Implementation (2013), PLDI ’13, ACM, pp. 27–38.
[15] H AR -P ELED , S., AND M AZUMDAR , S. On coresets for k-means andk-median clustering. In Proceedings of the Thirty-sixth Annual ACM
Symposium on Theory of Computing (New York, NY, USA, 2004),
STOC ’04, ACM, pp. 291–300.
[16] H INDLE , A., BARR , E. T., S U , Z., G ABEL , M., AND D EVANBU ,P. On the naturalness of software. In Proceedings of the 34th
International Conference on Software Engineering (Piscataway, NJ,
USA, 2012), ICSE ’12, IEEE Press, pp. 837–847.

[17] H UTTER , F., H OOS , H. H., L EYTON -B ROWN , K., AND S T ÜTZLE ,T. Paramils: An automatic algorithm configuration framework. J.
Artif. Int. Res. 36, 1 (Sept. 2009), 267–306.
[18] J HA , S., G ULWANI , S., S ESHIA , S. A., AND T IWARI , A. Oracleguided component-based program synthesis. In Proceedings of the
32nd ACM/IEEE International Conference on Software Engineering Volume 1 (New York, NY, USA, 2010), ICSE ’10, ACM, pp. 215–224.
[19] L AU , T. A. Programming by Demonstration: A Machine Learning
Approach. PhD thesis, 2001. AAI3013992.
[20] L E , V., AND G ULWANI , S. Flashextract: A framework for data
extraction by examples. In Proceedings of the 35th ACM SIGPLAN
Conference on Programming Language Design and Implementation(New York, NY, USA, 2014), PLDI ’14, ACM, pp. 542–553.
[21] L UXBURG , U. V., AND S CHOELKOPF, B. Statistical learning theory:
Models, concepts, and results. In Inductive Logic. 2011, pp. 651–706.
[22] M ENON , A. K., TAMUZ , O., G ULWANI , S., L AMPSON , B. W.,
AND K ALAI , A. A machine learning framework for programmingby example. In Proceedings of the 30th International Conference on
Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013(2013), pp. 187–195.
[23] M ITCHELL , T. M. Machine Learning, 1 ed. McGraw-Hill, Inc., New
York, NY, USA, 1997.
[24] N GUYEN , A. T., AND N GUYEN , T. N. Graph-based statistical language model for code. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (Piscataway, NJ, USA,2015), ICSE ’15, IEEE Press, pp. 858–868.
[25] N GUYEN , T. T., N GUYEN , A. T., N GUYEN , H. A., AND N GUYEN ,T. N. A statistical semantic language model for source code. In
Proceedings of the 2013 9th Joint Meeting on Foundations of Software
Engineering (New York, NY, USA, 2013), ESEC/FSE 2013, ACM,
pp. 532–542.
[26] N ORI , A. V., O ZAIR , S., R AJAMANI , S. K., AND V IJAYKEERTHY,
D. Efficient synthesis of probabilistic programs. In Proceedings of the36th ACM SIGPLAN Conference on Programming Language Design
and Implementation (New York, NY, USA, 2015), PLDI 2015, ACM,
pp. 208–217.
[27] O CH , F. J. Minimum error rate training in statistical machine translation. In Proceedings of the 41st Annual Meeting on Association for
Computational Linguistics - Volume 1 (Stroudsburg, PA, USA, 2003),
ACL ’03, Association for Computational Linguistics, pp. 160–167.
[28] PANCHEKHA , P., S ANCHEZ -S TERN , A., W ILCOX , J. R., AND TATLOCK , Z. Automatically improving accuracy for floating point expressions. In Proceedings of the 36th ACM SIGPLAN Conference on
Programming Language Design and Implementation, Portland, OR,
USA, June 15-17, 2015 (2015), pp. 1–11.
[29] R AYCHEV, V., V ECHEV, M., AND K RAUSE , A. Predicting program
properties from ”big code”. In Proceedings of the 42nd Annual
ACM SIGPLAN-SIGACT Symposium on Principles of Programming
Languages (2015), POPL ’15, ACM, pp. 111–124.
[30] R AYCHEV, V., V ECHEV, M., AND YAHAV, E. Code completion withstatistical language models. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (New York, NY, USA, 2014), PLDI ’14, ACM, pp. 419–428.
[31] S MITH , S. F. A Learning System Based on Genetic Adaptive Algorithms. PhD thesis, Pittsburgh, PA, USA, 1980. AAI8112638.
[32] S OLAR -L EZAMA , A., TANCAU , L., B OD ÍK , R., S ESHIA , S. A., AND
S ARASWAT, V. A. Combinatorial sketching for finite programs. In
ASPLOS (2006), pp. 404–415.
[33] Č ERN Ý , P., AND H ENZINGER , T. A. From boolean to quantitativesynthesis. In Proceedings of the Ninth ACM International Conferenceon Embedded Software (New York, NY, USA, 2011), EMSOFT ’11,
ACM, pp. 149–154.
[34] V ECHEV, M., YAHAV, E., AND YORSH , G. Abstraction-guided
synthesis of synchronization. In Proceedings of the 37th Annual
ACM SIGPLAN-SIGACT Symposium on Principles of Programming
Languages (New York, NY, USA, 2010), POPL ’10, ACM, pp. 327–
338.

[35] WARREN , H. S. Hacker’s Delight. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002.
[36] W ITTEN , I. H., AND B ELL , T. C. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression.

IEEE Transactions on Information Theory 37, 4 (1991), 1085–1094.