Code Completion with Statistical Language Models
Veselin Raychev

Martin Vechev

Eran Yahav

ETH Zürichveselin.raychev@inf.ethz.ch

ETH Zürichmartin.vechev@inf.ethz.ch

Technionyahave@cs.technion.ac.il

Abstract
We address the problem of synthesizing code completions for programs using APIs. Given a program with holes, we synthesize completions for holes with the most likely sequences of method calls.
Our main idea is to reduce the problem of code completion toa natural-language processing problem of predicting probabilities
of sentences. We design a simple and scalable static analysis thatextracts sequences of method calls from a large codebase, andindex these into a statistical language model. We then employ
the language model to find the highest ranked sentences, and use
them to synthesize a code completion. Our approach is able tosynthesize sequences of calls across multiple objects together with
their arguments.
Experiments show that our approach is fast and effective. Virtually all computed completions typecheck, and the desired completion appears in the top 3 results in 90% of the cases.
Categories and Subject Descriptors D.2.4 [Software Engineering]: Software/Program Verification—Statistical methods; I.2.2[Artificial Intelligence]: Automatic Programming—Program synthesis

1.

Introduction

To accomplish many common tasks, programmers increasingly relyon the rich functionality provided by numerous libraries and frameworks. Unfortunately, a typical API can involve hundreds of classes
with dozens of methods each, and often requires specific sequencesof operations to be invoked to perform a single task [9, 38, 39].
Even experienced programmers might spend hours trying to understand how to use a simple API [23]. To address this challenge, recent years have seen increasing interest in code search, recommendation and completion systems [7, 15, 19, 23, 25–27, 29, 35, 43].
Despite significant progress, existing techniques cannot synthesize usable code beyond simple sequences required for instantiationof library objects. No existing technique can synthesize code of thecomplexity found in real tutorials and code examples. In fact, mostexisting approaches to code completion target completion based onshallow semantic information, and cannot capture the temporal information required for synthesizing correct code using a library.
Some specification-mining techniques do capture rich temporal information (see Sec. 8), but do not attempt to synthesize usable code.

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.
PLDI ’14, June 09–11, 2014, Edinburgh, United Kingdom.
Copyright c 2014 ACM 978-1-4503-2784-8/14/06. . . $15.00.
http://dx.doi.org/10.1145/2594291.2594321

Our Approach: Synthesis with Statistical Language Models Statistical language models have been successfully used to model
regularities in natural languages and applied to problems such as
speech recognition, optical character recognition, and others [28].
Our main idea is to reduce the problem of code completion toa natural-language processing problem of predicting probabilities
of sentences: we use regularities found in sequences of method
invocations to predict and synthesize a likely method invocation
sequence for code completion.
Big Data, Small Programs To construct the statistical language
model, we use static analysis to extract a large number of histories
of API method calls from a massive number of code snippets obtained from GitHub and other repositories. The extracted histories
are used as training sentences for the statistical language model.
We show that the quality of the synthesized completion depends on
the aliasing information used during the history extraction phase.
Our synthesizer represents a powerful combination of statisticallanguage models with program analysis techniques.
The synthesizer takes as input a partial program with holes andoutputs a program where all of the holes are filled in with (sequences of) method invocations. Computing the “small program”
required for code completion, is based on the language model constructed from “big data”. Specifically, we employ the language
model to find the highest ranked sentences, and use them to synthesize a code completion.
Our synthesizer can: (i) discover sequences of invocations
across multiple types, (ii) complete both invocations and arguments
of invocations, (iii) complete multiple holes as well as each holewith a sequence of invocations, and (iv) infer fused completions
which do not exist in the training set.
Contributions The main contributions of this paper are:
• A new approach to code completion for programs using APIs.

Our approach reduces the problem of code completion to anatural-language processing problem of predicting probabilities
of sentences.
• A scalable static analysis that extracts sequences of method

calls from large codebases, and indexes them into statistical language models such as N-gram and Recurrent Neural Networks.
• A synthesis procedure that takes as input a partial program withholes and leverages probabilities learned in the language model
to discover code completions for the holes. Our approach is able
to synthesize sequences of calls across multiple objects together
with their arguments.
• An implementation of our approach in a tool called SLANG

and an experimental evaluation on a number of real world
programming scenarios expressed with partial programs. Our
results show that SLANG is fast and effective. Virtually allcompletions synthesized by SLANG typecheck, and the desiredcompletion appears in the top 3 results in more than 90% of thecases.

Training Phase
Training
datasetQuery Phase
Partial programwith holes

Abstraction

Abstraction

Constraints

Sentenceswith holes

SentencesTrain LM

Completion
CombineCandidatesentences

LM lookup
Statistical Language Model

Figure 1. The architecture of SLANG.

2.

Overview

The overall flow of SLANG is shown in Fig. 1. During the training
phase, we use program analysis to extract sequences of API callsfrom the entire code base. Then, a statistical language model istrained on this extracted data. In this work we use the N-grammodel, Recurrent Neural Networks and a combination of thesetwo. The result of the training phase is a probability associatedwith each of the extracted sequences of method invocations. To
interact with SLANG, the programmer provides a partial programwith holes. Our program analysis extracts the sequences from thispartial program, and uses the statistical language model to computea set of candidate completion sequences. The final completion for
all the holes is selected based on the highest probability and onwhether the completion satisfies the constraints posed by each hole.
The effectiveness of SLANG is due to a careful combination of
statistical models with program analysis. In particular, we use aform of alias and history analysis to extract relatively precise sequences of method invocations from the code base, which are thenused to train the language model. Training on sequences extracted
without performing program analysis produces poor results andfails to produce completions (let alone desired ones) for many examples. Our combination of program analysis and language models
makes the difference between not obtaining any solution at all versus obtaining the desired solution at the top of the list.
Example To illustrate our approach, consider a representative
Android example shown in Fig. 2. The Android MediaRecorder
API is known to be quite involved. The official documentation forthis API includes a state-machine with 7 different states1 , corresponding to internal states of the media recorder.
Consider a programmer trying to work with the MediaRecorder
API and interested in combining this API with other APIs fromclasses such as Camera and SurfaceHolder. The programmer
may have partial knowledge about MediaRecorder, for instance,
she may know that she needs to set an audio and video source aswell as the exact API calls and parameters for doing so. However,she may still be missing some of the details.
Using SLANG, a programmer can write the partial programof Fig. 2(a), and rely on the synthesizer to complete the missing
details. The partial program uses the statement “?” to denote a“hole”, missing code to be completed by the synthesizer. The program of Fig. 2(a) has four different holes, marked with comments(H1)-(H4). Each hole is a query to the synthesizer asking it to infera sequence of method invocations using (some of) the variables thatare in scope. The hole can be constrained to only use certain variables by specifying a set of variable names. In this example, holes(H1)-(H2) are not bound to specific variables, while (H3)-(H4) arelimited to only infer invocations that use the variable rec (either
1 see http://goo.gl/PZRic

void exampleMediaRecorder() throws IOException {Camera camera = Camera.open();camera.setDisplayOrientation(90);? // (H1)
SurfaceHolder holder = getHolder();holder.addCallback(this);holder.setType(SurfaceHolder.SURFACE_TYPE_PUSH_BUFFERS);MediaRecorder rec = new MediaRecorder();? // (H2)
rec.setAudioSource(MediaRecorder.AudioSource.MIC);
rec.setVideoSource(MediaRecorder.VideoSource.DEFAULT);
rec.setOutputFormat(MediaRecorder.OutputFormat.MPEG_4);? {rec} // (H3)rec.setOutputFile("file.mp4");
rec.setPreviewDisplay(holder.getSurface());
rec.setOrientationHint(90);rec.prepare();? {rec} // (H4)}(a)
void exampleMediaRecorder() throws IOException {Camera camera = Camera.open();camera.setDisplayOrientation(90);camera.unlock();
SurfaceHolder holder = getHolder();holder.addCallback(this);holder.setType(SurfaceHolder.SURFACE_TYPE_PUSH_BUFFERS);
rec = new MediaRecorder();rec.setCamera(camera);rec.setAudioSource(MediaRecorder.AudioSource.MIC);
rec.setVideoSource(MediaRecorder.VideoSource.DEFAULT);
rec.setOutputFormat(MediaRecorder.OutputFormat.MPEG_4);
rec.setAudioEncoder(1);rec.setVideoEncoder(3);rec.setOutputFile("file.mp4");
rec.setPreviewDisplay(holder.getSurface());
rec.setOrientationHint(90);rec.prepare();rec.start();}(b)

Figure 2. (a) A partial program using MediaRecorder and otherAPIs, and (b) its completion as synthesized by SLANG.

passed in as an argument or as the receiver). In Section 5, we describe other forms of queries that can relay additional information
to the synthesizer. Given the partial program of Fig. 2(a), SLANG
automatically synthesizes completions for the holes using the most
likely sequences of method invocations, shown in bold in Fig. 2(b).
Key Aspects This example highlights four key aspects of SLANG:• Completion across multiple types: the completion of (H1)
as camera.unlock() is an invocation on an object of type
Camera, the completions for (H2-H4) are invocations on an object of type MediaRecorder. Further, the completion of (H2)
as rec.setCamera(camera) uses parameter of type Camera
in a completed invocation for MediaRecorder.
• Completion of parameters: the completion of (H3) using the two invocations rec.setAudioEncoder(1) andrec.setVideoEncoder(3) includes not only the invocations,but also the required parameters.
• Holes as sequences: The completion of (H3) uses a sequenceof two invocations to complete a single hole. In general, ourapproach can generate a sequence of invocations to complete ahole (up to some specified length).
• New fused completions: Our system can infer fused sequencesthat did not exist before. Neither of the sequences for Cameraor MediaRecorder were in the training set, yet SLANG suc-cessfully synthesized an invocation that involves both of thesein order to complete the hole (H2).

3.

Model

In this section, we provide basic definitions of an event and asequence of events (history) that we use in the rest of the paper.
In Section 3.1, we provide a simple instrumented semantics for
tracking sequences of events over objects. Because there is no apriori bound on the number of dynamically allocated objects, andno a priori bound on the length of a history, the concrete semantics
is generally non computable. In Section 3.2, we present an abstract
semantics that provides a bounded representation for histories, andtracks a bounded set of bounded histories for each (abstract) object.
3.1

statements updating L\ , ρ\ , and π \ . The his\ component changes
on object allocations and method invocations:• Object Allocation: The statement x = new T() allocates a

fresh object onew ∈ objects\ \ L\ initialized with the empty0
sequence history his\ (onew ) = .
• Method Invocation: For an invocation x0 .m (x1 , . . . , xn ) ofa method with signature m(t1 , . . . , tn ), the history of every

object o = ρ\ (xi ) (where 0 ≤ i ≤ n) is extended with an0
event e = hm(t1 , . . . , tn ), ii, that is: his\ (o) = his\ (o) · e,adding an event to the history to reflect the invocation of m. If
the invocation of m returns an object r, its history his\ (r) is
extended with hm(t1 , . . . , tn ), reti.

Concrete Semantics

We define an instrumented concrete semantics that tracks the concrete sequence of events for each concrete object. We refer to theconcrete sequence of events as the concrete history of the concrete
object. We start with a standard concrete semantics for an imperative object-oriented language, defining a program state and evaluation of an expression in a program state.
Objects and Program State
Restricting attention to reference
types, the semantic domains are defined as follows:
L\
v\
ρ\
π\
state\ = hL\ , ρ\ , π \ i

∈
∈
∈
∈
∈

P(objects\ )Val = objects\ ∪ {null}
Env = VarIds → Val
Heap = objects\ × FieldIds → Val
States = P(objects\ ) × Env × Heap

where objects\ is an unbounded set of dynamically allocated objects, VarIds is a set of local variable identifiers, and FieldIds is aset of field identifiers. A program state tracks the set L\ of allocatedobjects, an environment ρ\ mapping local variables to (reference)values, and a heap π \ mapping fields of allocated objects to values.
Instrumented Semantics: Events and Histories In our instrumented semantics, each concrete object is mapped to a “concrete
history” that records the sequence of events that has occurred forthat object. That is, we employ a form of per-object cartesian abstraction. An event for an object o corresponds to an invocation ofan API method involving the object o: o can either be the receiverobject (this), the return value returned by the API invocation, or
one of the arguments to the method invocation.
More formally, an event is a pair hm(t1 , . . . , tk ), pi, of amethod signature m(t1 , . . . , tk ), and a position argument p denoting the position of the object o in the invocation of m. The position
p can be 0 denoting this, or a value denoting one of the positions
1, . . . , k. We also use a designated position value ret to denote thecase where o is a new object returned from the invocation of m. To
simplify presentation, we assume that an object appears in at mostone position of a given method invocation, and that methods are notinvoked with a null argument. Our implementation deals with themore general case where an object can appear in multiple positions(by replacing the position argument p to be a set of positions), andcorrectly handles invocations with null arguments.
Given an API A with methods m1 , . . . , mn , we use ΣA todenote the set of all events over the API. When the API is clear
from context, we omit the subscript A. We define the notion ofa concrete history for an API simply as a sequence of eventsΣ∗ . We denote the empty concrete history by  and denote theset of all concrete histories by H. The instrumented semantics is
obtained by augmenting every concrete state hL\ , ρ\ , π \ i with anadditional mapping that maps each allocated object to its concrete
history, that is his\ : L\ * H. Given a state hL\ , ρ\ , π \ , his\ i,0000
the semantics generates a new state hL\ , ρ\ , π \ , his\ i whenevaluating each statement. We assume a standard interpretation for

3.2

Abstract Semantics

The instrumented concrete semantics is generally non-computable
as there are no a priori bounds on the number of dynamicallyallocated objects, or on the length of histories. We now present an
abstract semantics that provides a bounded representation.
Heap Abstraction We use a flow-insensitive Steensgaard style [33]points-to analysis to partition the objects\ set into a bounded set of
abstract objects called objects.
History Abstraction Our goal is to extract a set of sentences thatcan be given as input to language models (see Section 4). Towards
that end, we bound the number of loop iterations in our analysis toguarantee that collected histories are of bounded length. We define
the notion of an abstract history as a set of concrete histories ofbounded length, namely an abstract history h ⊆ H. That is, while a
concrete history describes a unique sequence of events, an abstract
history represents potentially many concrete histories capturing thedifferent control flows through the program.
Abstract State The tuple hL, ρ, π, hisi denotes an instrumented
abstract program state consisting of the set of allocated abstract
objects, the local variables which point to abstract objects, theabstract heap and the abstract history for each abstract object. The
definition of the first three components is computed in a standard
way. We next discuss the definition of his which is now lifted toabstract objects and abstract histories as follows: his : L * P(H).
Abstract Semantics of his The abstract semantics for updating
his follow the structure of the concrete semantics except that it islifted to deal with abstract objects, and abstract histories.
• Object Allocation: The statement x = new T() results in an

abstract object anew ∈ objects with a set containing a new
empty history: his(anew ) ∪ = {}.
• Method Invocation: For an invocation x0 .m (x1 , . . . , xn ) of amethod with signature m(t1 , . . . , tn ), the abstract history of

every abstract object o = ρ(xi ) (0 ≤ i ≤ n) is extended withe = hm(t1 , . . . , tn ), ii, that is, his0 (o) = {h · e | h ∈ his(o)},adding an event to each concrete history of the abstract history.
If the invocation returns an object r, the abstract history his(r)is extended with hm(t1 , . . . , tn ), reti.
Joins Whenever a join of the control-flow occurs, the new history
for each abstract object is computed by combining the histories forthat abstract object arriving from each of the branches (by applying
union to the corresponding sets). As long as the domain of abstract
histories is bounded, the analysis is guaranteed to terminate. However, in practice, it can suffer from an exponential blowup due tobranching control flow. To mitigate potential exponential blowup,
we limit the number of collected histories by some threshold. Once
that threshold has been met, we randomly evict older histories tomake room for new ones. In our experiments, we used the threshold 16 which was sufficient for 99.5% of the analyzed methods.

4.

Statistical Language Models

Statistical language models have been used to model the regularities in natural languages and improve the performance of problems
such as speech recognition, statistical machine translation, opticalcharacter recognition, and others [28]. In this work, we use regularities found in sequences of method invocations to predict andsynthesize a likely method invocation sequence in the context ofcode completion. In this section, we first define the necessary statistical language modeling background, and then show how thesecan be leveraged for synthesis of code completions.
Statistical language models are based on the concepts of words
and sentences, where each sentence is an ordered sequence ofwords. Every word w is taken from a set D also called a dictionary.
A language is informally defined as all sentences that are usedin some particular domain. The goal of a language model is tobuild a probabilistic distribution over all possible sentences in alanguage. This is, given a sentence s, the language model estimates
its probability P r(s). For a sentence s = w1 · w2 · ... · wm , many
language modeling approaches estimate its probability as follows:P r(s) =mY

P r(wi | hi−1 )

i=1where we refer to the sequence hi = w1 · w2 · ... · wi as ahistory. That is, the probability of a sentence can be calculated
by generating it word by word using conditional probabilities on
the already generated words. Furthermore, language models areusually constructed on a finite amount of training data that is used
to estimate the actual probabilities of sentences. Because not all
possible sentences in the language or their prefixes will be in the
training data (also referred to as the problem of sparse data [28]),
the model uses other statistical techniques to estimate probabilities.
4.1

N-gram language models

In order to deal with the sparseness of the data, an N-gram data
model estimates the probability of a sentence by modeling a language as a Markov source of order n − 1:
P r(s) =mY

P r(wi | wi−n+1 · ... · wi−1 )i=1That is, the probability of the next word wi depends only on
the previous n − 1 words. In our work we use the trigram language model where the probability of a word depends on a pair ofprevious words.
That is, for the trigram language model, we haveQ
P r(s) = m
Pr(wi | wi−2 · wi−1 ). Such probabilities are esi=1
timated by counting the number of occurrences of trigrams and bigrams in the training data.
Smoothing Even for small n, these models can still suffer fromthe problem of data sparseness. For example, some n-grams may
only occur once or not at all in the training data and yet their probabilities must be estimated. To mitigate this problem, practical ngram language models use counts for n-grams, (n − 1)-grams andfor all lengths down to unigrams. Further, they smooth the probability by using models of lower length [20, 21] when sparsenessproblems in estimating sentence probabilities occur. In our work,
we use Witten-Bell smoothing [40], which is applicable even when
we remove rare words from the training data.
4.2

Recurrent Neural Networks (RNNs)

In recent years, the increased availability of computational resources for training led to wider adoption of neural networks forpredicting probabilities of sentences [22]. These approaches areconceptually interesting in the fact that they do not capture only
regularities between a word and a fixed number of predecessor

input: v icontext: ci

output: y ii= P r(wi+1 | hi )
yw
i+1

wi

context: ci−1
ci - hidden layer

Figure 3. A scheme of a recurrent neural network (RNN). The
input is a word vector for the i-th word in a sentence, the output
is probabilities for different possible words at position i + 1.
words, but may also capture longer distance relations between
words. Initially proposed by Elman [13], recurrent neural networks(RNNs) predict probabilities of the (i + 1)-st word according to thescheme in Fig. 3.
In the schema, v i and y i are vectors of |D| real numbers, where
D is the dictionary such that every possible word x ∈ D has acorresponding index in v i and y i (referred as vxi and yxi ). Let ci(for every i) be a vector of p real numbers. The number p is also
called the size of the hidden layer and the entire network is referred
to as RNN-p. RNN uses two functions f and g and estimates
word probabilities iteratively on a sentence s = w1 · ... · wm by
performing the following actions for every word wi ∈ s : i) set allipositions of v i to zeros, except position vw
to one. ii) Compute
i
i
i i−1
i
i
c = f (v , c ) and y = g(c ). Then the vector y i is used as an
estimator of the probabilities for the next word wi+1 :i
P r(wi+1 | w1 · ... · wi ) ≈ yw
i+1

During training, the functions f and g are learned from data
to minimize the error rate of the estimates y i (details are in [22]).
What is essential for RNNs however is that they can capture long
distance regularities in the language via the hidden layer ci . The
values in ci act as an internal state of an automaton and at every
step i, the previous internal state ci−1 is used for computing ci .
In SLANG, we use RNNME-p – a faster variant of RNN witha hidden layer size of p that combines RNN-p with a class-based
maximum entropy model [24].
Combination models Due to the different natures of the models
based on n-grams and RNNs, it is possible that averaging the probability of two models performs better than each model individually.
Indeed, in our experiments in Section 7, our combined language
model between a 3-gram and a RNNME-40 language model ranks
the correct completion as a first result in more cases that the twobase models individually.
4.3

Sentence Completion with Language Models

In addition to computing probabilities for single sentences, we canleverage a language model to complete missing holes in a sentence(with the most likely completions). As a simple example, consider
the following natural language sentence with a missing word:
The quick brown ? jumped

If the word ? is replaced with an actual natural language wordfrom the dictionary of words D, a statistical language model is useful as a scoring function of the most probable completion. However,certain language models are also useful to suggest very likely completions of the holes. For example, a bigram model keeps all pairsof sequential words that are present in the training data. In our example, these could be the pairs hbrown, foxi, hbrown, dogi, etc.
Then, if the word preceding the hole is a (e.g., a = brown), we cansuggest filling the hole only with words x, such that ha, xi are bigrams in the training data. This procedure significantly reduces theset of words that are candidate completions of the sentence holes
by producing candidates which a language model may score high.
In this work, we use such a bigram model to generate candidate
sentences and later use another language model such as N-gram
and RNN to assign probabilities to these sentences.

SmsManager smsMgr = SmsManager.getDefault();
int length = message.length();if (length > MAX_SMS_MESSAGE_LENGTH) {ArrayList<String> msgList =smsMgr.divideMsg(message);? {smsMgr, msgList} // (H1)
} else {? {smsMgr, message} // (H2)
}

(a)

4.4

Training on Program Data

In this work we propose an approach which connects statistical language models with features extracted via program analysis. In particular, in Section 3, we presented a history abstraction that maps
every (abstract) object to a set of histories (i.e., sentences). These
sentences can be automatically extracted via program analysis andthen fed to a statical language model which can train on this data.
Our abstraction nicely matches the two worlds of program analysis and language models: an event in the semantics corresponds
to a language word and a history sequence h ∈ H corresponds toa language sentence. To train a language model on a large set ofprograms, we: (i) use program analysis to extract the abstract objects and their corresponding (history) sequences; and (ii) discard
the abstract objects, treat the extracted histories as sentences in thelanguage, and train a statistical language model over this data.

5.

Synthesis

So far we discussed the training phase of our system. We next discuss how code completion works. The synthesizer takes as input
a partial program (augmented with holes) and outputs a program
where the holes are filled with (sequences of) method invocations.
To enable programmers to use our approach and specify partial programs, we introduce the following construct for specifying holes:? lvars:l:u

where lvars ∈ P(V arIds) is a set of (reference) local variables
and l and u are natural numbers which constrain the length of thesequence from below and from above. All of these are optional parameters which are provided as a convenience to the programmer
in case she would like to constrain the possible completions. Informally, this construct directs the synthesizer to search for a valid
replacement of ? lvars:l:u with a sequence of method invocations where lvars participates in each invocation and where thelength of the sequence is between l and u. For example, the hole
? directs the synthesizer to look for the most likely sequence of
method invocations of any length. A more restrictive hole wouldbe ?{x} which instructs the synthesizer to find sequences where
variable x participates in the method invocation: either a method
on x was invoked or x is passed in as an argument to some othermethod. That is, in the sequence, for each of the method invocations, the variable x should participate in some form. The meaningof a query such as ?{x,y}:1:1 is that the suggested sequence must
consist of exactly 1 method invocation where both x and y participate in that invocation.
Code Completion: Step-by-Step We now present the procedure
which takes as input a partial program that may contain multiple
holes and infers the most likely completions for the holes. To avoid
clutter, we describe the case where all of the holes require l and u
to be equal to 1, that is, all holes have the shape: ?lvars:1:1. Thismeans that every hole has to be replaced with exactly one method
invocation (there could be multiple variables constraining the hole).
We can translate holes of the more general shape ?lvars:l:u to
u − l + 1 separate queries: for every i ∈ [l, u], perform a querywith i sequentially placed holes where each hole has the shape?lvars:1:1.

SmsManager smsMgr = SmsManager.getDefault();
int length = message.length();if (length > MAX_SMS_MESSAGE_LENGTH) {ArrayList<String> msgList =smsMgr.divideMsg(message);smsMgr.sendMultipartTextMessage(...msgList...);} else {smsMgr.sendTextMessage(...message...);}(b)

Figure 4. (a) A partial program built from an example on StackOverflow [3], and (b) its completion as automatically synthesized
by SLANG (the full list of parameters is omitted for clarity).
Before we explain the steps of our algorithm, let us introduce
some necessary notation. Recall that a concrete history is a sequence of events where each event (see Section 3.1) represents amethod invocation. However, with partial programs, we now havehole statements which are to be replaced with sequences of events.
Therefore, we define a set of histories with holes H ◦ = (Σ ∪ G)∗
where G represents all possible holes.
Next, we explain our algorithm and illustrate each step on theexample in Fig. 4. Here, we have a partial program Fig. 4(a), forwhich SLANG must synthesize the completion in Fig. 4(b). Thatis, the tool must infer that if the message was divided into parts,
the most likely method to call is sendMultipartTextMessage, whileotherwise it is sendTextMessage. The first and the second hole areassigned unique identifiers H1 and H2 respectively.
Step 1: Extract abstract histories with holes Given a partial program, for each abstract object, we automatically extract its abstract
histories with holes (as described in Section 3.2, except that we now
also have holes appearing in abstract histories). The output of thisstep is a function hispt : L * P(H ◦ ). For our running example,
the output of this step will be a map hispt defined as follows:
smsMgr7→ {hgetDefault, reti · hH2i ,hgetDefault, reti · hdivideMsg, 0i · hH1i}

message

7→ {hlength, 0i ,msgList7→ {hdivideMsg, reti · hH1i}

hlength, 0i · hH2i}

Step 2: Compute candidate completions
We next computethe set of candidate completions for all of the abstract histories
obtained from Step 1. For our example, this set of partial histories is shown in the first column of Fig. 5. To aid the subsequent completion, we slightly overload the notation for holes andto each hole, we also add the abstract object for which the partial abstract history was built. For instance, if SLANG suggests
hsendTextMessage, 0i for replacing hH2, smsMgri, then smsMgrwill be placed at position 0, essentially denoting the invocation
smsMgr.sendTextMessage(...).
For each partial abstract history, we compute a sorted list of
possible histories without holes. The way we do that is via a twostep approach. In the first step, we use the bigram model in orderto suggest candidate completions to the holes and obtain histories
without holes (as discussed in Section 4.3). Then, in the second

Partial History
hgetDefault, reti · hH2, smsMgri
hgetDefault, reti · hdivideMsg, 0i · hH1, smsMgri
hlength, 0i · hH2, messagei
hdivideMsg, reti · hH1, msgListi

Id
11
12
21
22
31
32
33
34
41

Candidate Completions
hgetDefault, reti · hsendTextMessage, 0i
hgetDefault, reti · hsendMultipartTextMessage, 0i
hgetDefault, reti · hdivideMsg, 0i · hsendMultipartTextMessage, 0i
hgetDefault, reti · hdivideMsg, 0i · hsendTextMessage, 0ihlength, 0i · hlength, 0ihlength, 0i · hsplit, 0i
hlength, 0i · hsendTextMessage, 3ihlength, 0i · hsendMultipartTextMessage, 1i
hdivideMsg, reti · hsendMultipartTextMessage, 3i

Pr
0.00730.00100.00330.00160.01320.00800.00170.00010.0821Figure 5. The partial sequences extracted from the program in Fig. 4 and their candidate completions (with probabilities).
step, we use an N-gram language model or an RNN model to rankthese completed candidate histories.
Finally, we end up with a map candidates : H ◦ * H∗ where
for a partial abstract history, the list candidates(h) is sorted by theprobability of the sequence (history without holes). That is, more
likely sequences appear ahead of less likely sequences. For our
example, the candidate completions together with the probabilityof each sequence are shown in the last two columns of Fig. 5.
Step 3: Compute an Optimum and Consistent Solution Finally,in this step we compute the map completion : H ◦ * H. That is,for each partial abstract history h ∈ H ◦ , we need to select a history
from candidates(h) which completes h. However, even though
the list candidates(h) is sorted by probability, we may not always
pick the first sequence in that list. The reason we cannot always
pick the first sequence is because we need to make a global decision for all suggested completions, rather than a local per-history
choice. In our algorithm, we iterate over the map candidates (overthe sorted lists in candidates), following the sorted priority orderand build a map completion for each abstract history. In particular,
the completion which we return satisfies two criteria:• Global optimality: Let T = hispt (L) denote all partial abstract

histories. Then, the returned completion should maximize thescore:Ph∈T (P r(completion(h)))|T |• Consistency: A proposed completion should also be consis-

tent: we make sure that the completion satisfies certain constraints imposed by the programming language and by the constraints of the hole. First, if a hole appears multiple times (e.g.,
due to loop unrolling), then we make sure that the hole is always filled in with the same completion in every history ofcompletion’s range (to yield a syntactically valid program).
Second, if we have a hole of type ?{x,y,...}:1:1 which involves more than one variable (which do not alias), we makesure that the variables x, y,..., appear as parameters at different
positions in the corresponding suggestion.
Since our completion algorithm starts with the highest scoring
completion and exhaustively generates candidates in reverse scoreorder until a consistent completion is obtained, our procedure isguaranteed to always find the best scoring completion. Finally,
given a completion, we extract the methods found for each holeand suggest those to the developer.
Completions for our example Back to our example, if we choose
the completions 11, 21, 31, and 41 in Fig. 5, we get the highest probability according to the Global optimality equation above.
However the combination of these sentences is inconsistent because completion 11 suggests that we fill the hole H2 with method
sendTextMessage while 31 suggests that we use sendTextMessage.
This is clearly impossible when the hole is of size one. Thus, we

continue to generate candidate completions in the order of theirprobabilities until we find the first consistent completion – using
sentences 11, 21, 33, and 41. According to this choice of sentences,
H1 is filled with sendMultiPartTextMessage, and H2 is filled with
sendTextMessage. This is the completion returned to the developer,
also shown in Fig. 4 (b).

6.

Implementation

We implemented SLANG as a series of utilities that train statisticallanguage models on massive codebases and perform completions
on partial programs with holes. SLANG is implemented in Java andC++ and depends on a Java compiler for compiling the code, theSoot [36] framework for obtaining an intermediate representation(we work with Jimple) useful for program analysis, SRILM [34] forn-gram language models, and RNNLM [34] for recurrent neuralnetworks. We have designed SLANG to be scalable and efficient:
it can handle most queries in few seconds. Next, we discuss theimplementation of the different components of SLANG.
6.1

Program Analysis: Heap and Sequences

We aimed at a simple, fast and scalable program analysis that canquickly process massive amounts of data. To abstract the heap, we
implemented an intra-procedural Steensgaard-style alias analysis[33] due to its near linear time complexity and the fact that it canprocess classes and methods independently. At the start of every
method, we assume that all reference arguments in the method
do not alias. Generally, an assumption of this (or similar) kind isrequired, because at both training time and query time we do nothave the entire context in which the method will execute. Further,for our problem of suggesting code completions, we are not limited
to only consider over-approximations.
In our implementation of the history abstraction, we bound thenumber of loop iterations L in order to avoid exponential blowup
in space and time (in the number of generated sequences). Further,
we do not consider extracted sequences with more than K words(invocations) per abstract object. We can easily vary both L and K,
though in our experiments we set those to 2 and 16 respectively.
6.2

Language Models: preprocessing

Once the sentences (histories) from the training data are obtained
via the program analysis, we index them into a language model.
As with natural languages, sentences include some commonly occurring words, but there is a heavy long tail of very rare words.
However, the rarely occurring words are of little value for our code
completion problem. The reason is that these words are likely torepresent events that are specific to only a few projects in our index. Thus, we have added a preprocessing step that replaces words
that occur less than a certain number of times in the training corpus
with placeholder unknown words. This replacement has no observable effect on the availability of results other than for very rare API

Phasecalls. However, it enables us to obtain compact n-gram language
models and a small dictionary is essential for RNNs [10].
Once the preprocessing step is complete, SLANG invokes a language modeling system in order to generate an N-gram language
model or an RNN-model of the training data and in addition alsobuilds a bigram model of the training data in order to create candidate completions as described in Section 4.3. These two steps are
independent and can be performed in any order.
6.3

7.

Training Parameters

To evaluate the effect of various parameters on the quality of code
completion, we experimented with three knobs: the size of thedata set, the precision of the program analysis abstraction, and thedifferent choices for the language models.
For the size of the training data set, we considered three choices.
The first data set includes the entire codebase we have collected.
The second (smaller) data set contains 10% of the files of thecodebase. The third (smallest) data set contains 1% of the files.
For the program analysis abstraction, we experimented with both
options: enabling or disabling the alias analysis. Finally, we experimented with the following options for training the statisticallanguage model: (i) A 3-gram language model with Witten-Bellsmoothing, (ii) A RNNME-40 recurrent neural network language
model, (iii) A combination of the previous two language models.
7.2

4.682s
0.352s
5m 46s54.187s2.366s0h 53m9m 3s10.187s
5h 31m3.556s
0.442s
8m 42s

34.846s
3.239s2h 16m

5m 34s
13.510s
9h 34mTable 1. Training phase running times.

Data statistics
training without alias analysis
Sequences (file size as text)
Number of generated sentences
Number of generated words
Average words per sentence
3-gram language model file size
RNNME-40 language model file size
training with alias analysis
Sequences (file size as text)
Number of generated sentences
Number of generated words
Average words per sentence
3-gram language model file size
RNNME-40 language model file size

1%

Dataset10%

all data

7.2MiB
74979
1886682.5163
11.1MiB
19.3MiB

46.5MiB
759434
18644022.454950.9MiB
41.8MiB

597.4MB
6989349
16430269
2.350872.2MiB
29.7MiB

9.3MiB
81477
2410042.9579
14.6MiB
22.2MiB

89.1MiB
80557823583022.9275
69.6MiB
51.1MiB

761MiB
743530720751368
2.7909108.1MiB
36.0MiB

Table 2. Data size statistics.

Evaluation

In this section we discuss an experimental evaluation of SLANG.
Our main objective was to study how effective the combinationof a statistical language model with a history abstraction is forcode completion purposes. Towards that, we collected 3, 090, 194
Android methods and used them as training data. We obtained
Android source code from various source repositories, and thencompiled these sources using a specially modified version of thepartial compiler [12], extended to handle more cases.
7.1

training without alias analysis
Sequence extraction
3-gram language model construction
RNNME-40 model construction
training with alias analysis
Sequence extraction
3-gram language model construction
RNNME-40 model construction

Query Processing

To perform a query in SLANG, the user provides a partial programwith holes which are to be filled-in by the tool. Given a query,
SLANG discovers a mapping from holes to (sequences of) method
invocations. The completions include method names, as well as
non-constant parameters given to the method call. That is, SLANG
can infer both method invocations as well as the reference arguments passed to the invocation. To also infer constants, we train asimple, but effective model that given a method call and a parameter position, returns the most likely constant to pass as a parameter.
Constant model We estimate the probability of a constant value
as a parameter of a method m by counting the number of times
each constant was given as a parameter to m in the training data
and dividing it by the total number of calls to m in the training
data. This simple model assumes that the constant values are independent of the context of the method or other parameters, yet
the approach is fast, feasible and enables our completion to include
complete method invocations.

Running time on dataset
1%
10%
all data

Training phase

We ran our experiments on a standard desktop workstation witha 3.5GHz Core i7 2600K processor, 16GB RAM, a solid statedrive storage, and running 64-bit Ubuntu 12.04 with OpenJDK 1.7.
Our system takes the Jimple input data and produces a language
model as an output. Our system can parallelize some steps of thecomputation by performing the analysis on multiple cores, however
we report runtimes only using a single thread.
Running times of our training phase are summarized in Table 1.
First, we provide the time to extract the abstract histories (i.e.,sequences) from the training data. Next, we provide running times
for constructing each of the corresponding language models. We
provide two pairs of numbers - without heap abstraction (assumingthat no two pointers alias), and with a Steensgaard style alias
analysis. In all cases, the training phase processes more than 5000
methods per second on average and the main slowdown occurs
when we train the neural network. In our experiments, performing
the alias analysis did not significantly affect the training time.
Table 2 provides statistics for the precomputation phase. As
seen, by using alias analysis, the data size of the produced sentences
increases by around 20%, and average sentence length increases
by around 0.45 words. Importantly, the alias analysis enables extraction of more precise histories. All of this reduces noise in the
training data and helps the language model learn longer and more
precise event sequences from the training data.
In terms of language models, the RNNME-40 language model
is significantly slower to train than the 3-gram model (the reason isthat the time complexity per processed word in 3-gram is constant,while in RNN, it is linear to the size of the dictionary), but on theother hand the RNN index with all the data is smaller in size.
7.3

Code Completion

We designed three different kinds of code completion tasks forevaluating our system:
1. Single object single-method completion: this task is characterized by a single hole of type ?{x}:1:1 placed at the end ofa method, meaning that given a local reference variable x, thetask of the synthesizer is to discover exactly one method invocation which uses x. That is, the tool predicts the next method
call to be performed involving x.
2. General completion: this task is characterized by multiple holes
and includes examples like Fig. 2 and Fig. 4.
3. Random completion: this task completes methods from large
programs where one or more holes were introduced at random.

Column (1)Analysis
Language model type
Training dataset
Task 1 (20 examples)
Desired completion in top 16
Desired completion in top 3
Desired completion at position 1
Task 2 (14 examples)
Desired completion in top 16
Desired completion in top 3
Desired completion at position 1
Task 3 (50 random examples)
Desired completion in top 16
Desired completion in top 3
Desired completion at position 1

(2)
(3)
(4)
No alias analysis
3-gram
1% 10% all data

(5)
(6)
(7)
With alias analysis
3-gram
1% 10% all data

(8)
(9)
With alias analysis
RNNME-40 RNNME-40 + 3-gramall data
all data

11
10
7

16
12
8

18
16
12

12
11
7

18
15
10

20
18
15

20
18
14

20
18
15

3
3
3

5
4
3

7
6
5

10
8
6

10
8
6

13
13
11

13
12
11

13
13
12

13
13
13

27
23
16

36
32
25

21
18
14

43
34
25

48
44
31

48
40
27

48
45
31

Table 4. Accuracy of SLANG on the test datasets depending on the amount of training data, the analysis and the language model.
Id
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Description
Registering a event listener to read the accelerometer
Add an accountTake a picture with the camera
Disable the lock screen
Get Battery Level
Get free memory card space
Get the name of the currently running task
Get the ringer volume
Get the SSID of the current WiFi network
Read GPS location
Record a video using MediaRecorder
Create a notification
Set display brightness
Change the current wallpaper
Display the onscreen keyboard
Register an SMS receiver
Send SMS
Load a sound resource to play in SoundPool
Display a web page in a WebView control
Toggle WiFi enabled/disabled

Source
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[3]
[4]
[1]
[3]
[3]
[3]
[6]
[2]
[5]

Table 3. Description on the examples from task 1 on which we
perform prediction.

The first task is similar to functionality provided by many IDEs
where when dot is pressed, the IDE displays a complete list of all
methods associated with the object on the left of the dot. In ourcase however, we only display a partial list of methods for which
we have confidence given the training data.
Evaluation data To evaluate task 1, we came up with 20 tasks
that a programmer may want to accomplish. Solving these tasks
requires usage of various Android API’s. We then inspected someof the popular solutions available on the Web, typically provided in
the form of a code snippet. We summarized this set of examples inTable 3. To evaluate task 2, we selected 14 code snippets from task
1 where we believed it makes sense to extend the snippet to containmore than one hole and with more complex constraints. For bothtasks, we introduced holes in the code snippets accordingly. We
made sure to not include the evaluation data into the training datain order to avoid statistical problems such as overfitting.
For task 3, we took code from open source projects and randomly introduced holes in 50 methods with objects interacting withmultiple Android APIs. For 23 of the random tests, multiple holes
need to be completed. We ensured that the projects we evaluate on
were not included in the training data.
Experiments We studied how the different knobs in our systemaffect the quality of code completion. We considered three accuracy

metrics, based on the number of examples for which the: (i) desired
method invocation is found in the list of results (we limit the size ofthe list to 16), (ii) desired method invocation was found in the top
3 results, and (iii) desired method invocation was ranked first in thesuggested candidates list.
We evaluated a number of parameter choices and summarized
the results in Table 4. Columns 2-7 contain the effect of the abstraction and the training data size. The system trained on the complete
dataset with alias analysis is able to predict all examples in our firsttask, and the correct completion is in the first 3 results for 90% of
the examples. Without alias analysis and with decrease of the training data, the accuracy significantly decreases and we can roughly
quantify that using a better program analysis component has thesame effect as adding an order of magnitude more data.
For our second task, one example could not be solved even by
our best system, because SLANG was unable to collect sufficient
information for the Notification.Builder class during training.
The reason for this is that developers may use the class via achain of calls builder.setSmallIcon(_).setAutoCancel(_) thatmake it difficult for an intra-procedural analysis to discover callson the same object. We believe that adding a more advanced (interprocedural) analysis could lead to further improvements of SLANG.
Two tests from the random tests task could not be solved byour best system. We believe one of them is due to a limitation of
the partial compiler that prevented us to collect data for a class at
training time, while the other is a completion that scores below the
top 16 results.
Language model types Columns 7, 8 and 9 of Table 4 summarize
the effect of the language models (we compare the models with thefull data size and with alias analysis). As discussed in Section 4, ngram and RNN differ significantly in the way they express histories
of sequences. While n-gram discover regularities between the lastn − 1 method calls, RNN is capable of discovering longer distance
relations.
In our experiments, the two models differ in how they ranked
the completions for some tests: while RNNME-40 was better inexamples with long distance relations similar to the one in Fig. 2,
it occasionally misses some short distance relations. On the other
hand, the 3-gram language model consistently found all short distance relations. Both, RNNME-40 and the 3-gram model, were outperformed by a combined model that averages their probabilities.
Type checking accuracy
To evaluate how many completions
typechecked, we took our best combined system and manuallyinspected all of the 1032 possible completions that SLANG returned(for all of our examples). In this experiment, we found only 5

completions which did not typecheck and they were always among
the worst ranked completions for the examples. We believe one of
the reasons for such outlier completions to appear in the results isimprecision of the alias analysis at training time, which leads toimpossible sequences in the model. To guarantee no type errors,
we plan to implement a typechecker on the results of SLANG that
discards the bad solutions.
Constant model Our constant model worked reasonably well. Outof the 41 constants that needed to be inferred in the first two tasks,
25 were produced by SLANG as the first result and 3 as the second
result. However, we believe that prediction of certain constants canbe difficult: e.g., guessing URLs, passwords, etc.
Performance
Our query time performance was dominated by
the time necessary to load the language model files. For our bestsystem which combines the two language models, we observed
average time per example of 2.78 seconds. To allow for interactive
completions within an IDE, we plan to load language models only
once at startup.
Summary We have shown that SLANG is effective in completing
partial programs with holes. Our experiments show that using alias
analysis is important and has the effect of an order of magnitude
more training data. Combining language models has positive effecton the ranking of the completions in our tests and with our bestsystem, we return the correct completion as a first result in 58 outof 84 test cases.

8.

Related work

The work of Hindle et al. [17] outlines a vision which suggeststhat techniques from natural language processing (e.g., n-gram language model) may be useful in various programming tasks suchas code completion, code search, property computation, etc. We
wholeheartedly agree with the authors that this is a direction worth
studying in depth. Their paper also presents a simple code completion scheme built on top of Eclipse which uses an n-gram language
model to predict the next tokens, and compares the advantages anddisadvantages of this scheme versus the traditional code completion already provided by Eclipse.
Our work investigates the potential of these high-level ideas ingreater depth. We study the effectiveness of several language models (i.e., n-gram and recurrent neural networks) in the context of a
specific application: predicting the sequence of API calls. Further,
we show that language models alone are sub-optimal for consistently producing quality sequences of completions and show how to
combine these ideas with classic programming languages concepts
such as alias analysis. This combination significantly improves thequality of the result. We believe that such combinations of statistical methods with programming language techniques hold a great
promise and are worth further exploration.
Code completion and Synthesis The last few years have seen arenewed interest in various synthesis techniques which promise tosimplify various software development tasks. Many of these techniques deal with some form of program “completion”, typically by
combining a predefined set of building blocks (e.g., expressionsof some kind). For a broader survey in recent program synthesis techniques, see Gulwani [14]. Below, we briefly discuss theapproaches that deal with completion of general user-level code.
Prospector [23] is an approach which automatically discovers a sequence of API calls that transform an object of a given input type
into an object of a given output type. PARSEWeb [35] also suggests a sequence of API calls but this time the search for the sequence is guided by the source code available on the Web, thus
helping to eliminate many otherwise undesirable sequences. Morerecent work [15, 16, 26] focuses on code completion by (stati-

cally) synthesizing expressions of a given type at a particular program point (these works examine the program context around thatpoint). To find the most likely expressions desired by the programmer, these approaches also rely on ranking algorithms to handle thelarge numbers of potential candidates. As opposed to these (static)
approaches, MatchMaker [42] synthesizes code based on observed
API usage in dynamic executions of real-world programs.
Code Search and Specification Mining There has been a lot ofwork on dynamic specification mining (e.g., [8, 11, 41]), most of it
for extracting various forms of temporal specifications. As always
with dynamic analyses, the barrier to wide application of these approaches is the ability to execute code samples, and to obtain workloads that provide reasonable coverage. However, when they areapplicable, our approach can benefit from such dynamic methods
as an additional source of sentences provided to the learning phase.
MAPO [43] uses static analysis to extract common API usage
patterns. MAPO employs a simple static analysis followed by analgorithm for finding common sequences, which are later used forrecommending code snippets to users. In contrast, our goal is tosynthesize code completions, and we do so directly based on probability of sequences. The Strathcona [18] code recommendation
system matches the structure of the code under development to thecode in the examples. The query in this case is implicit and consistsof the prefix of the currently written code. The search is performed
over a sample repository (e.g., the existing project). Temporal information such as the order of method invocations is not considered.
Recently, [25] presented a typestate-based code search technique that is able to perform limited code completion. Their approach is based on an inherently expensive and limited abstract representation of automata. For instance, on 1% of the training data,
it took [25] about 3 hours to complete (our system takes 5 seconds
with a 3-gram model and 9 minutes with RNN). Further, SLANG
can complete parameters of method calls whereas [25] can only
produce completions of method names. Upon manual inspection of
the resulting automata mined by [25], 10 of the 20 examples in ourset 1 were not even accepted by their automata, let alone ranked.
Technically, a key shortcoming of these clustering approaches
is their limited ability to generalize to sequences that did not exist
in the training data.
Synthesis with Partial Programs The concept of a partial program has proven effective in various synthesis contexts. Partial programs allow users to naturally express the parts about the programthat they know, while leaving parts they are not sure about, empty.
The synthesizer then automatically figures out how to complete theholes in a way that some property of the resulting program holds.
Examples where partial programs are used heavily include thesketching approach [30] to program synthesis. In this line of work,
the partial program is referred to as a “sketch”, where typically, theprogrammer specifies a space of possible expressions which can beused to fill in the holes. The synthesizer then searches for completions that satisfy a given property. Partial programs, or templates,
have also been effectively used for synthesis of various problems
including classic sequential algorithms [32], bit-ciphers [31], andconcurrent algorithms [37].
In our work, we also leverage partial programs as we believe
they are an effective mechanism for capturing programmer’s intent. However, fundamentally, unlike all of these works, we learn
the candidate completions of a hole in the partial program by examining and leveraging the vast amount of data available on the Web(in our case, in the form of API usage). In the future, we believe that
it will be fruitful to combine these two approaches: for instance, byleveraging the power of SMT solvers to infer fine-grained numerical expressions with our approach which can predict likely API
completions and their parameters.

9.

Conclusion

In this paper we presented a new approach to code completion
based on a novel combination of program analysis with statisticallanguage models, and implemented that approach in a tool called
SLANG . Given a massive codebase, using program analysis, SLANG
first extracts abstract histories from the data. Then, these histories
are fed to a language model such as an n-gram model or recurrent
neural network model, which treats the histories as sentences in anatural language and learns probabilities for each sentence.
The way a developer interacts with our system is via partial programs with holes. The developer produces a partial program leaving unknowns which are to be completed by the synthesizer. The
synthesizer then completes the holes with suggested sequences ofmethod invocations computed based on the probabilities of the language model. Our system can synthesize complete method invocation sequences, including the arguments for each invocation.
Our experimental results indicate that the approach is fast andeffective: on a set of real-world programming scenarios expressedwith partial programs, virtually all of the completions suggested by
SLANG typecheck and in 90% of the cases the desired completionappears in the top 3 candidates.

[17] H INDLE , A., BARR , E. T., S U , Z., G ABEL , M., AND D EVANBU , P.
On the naturalness of software. In ICSE 2012 (2012).
[18] H OLMES , R., AND M URPHY, G. C. Using structural context torecommend source code examples. In ICSE ’05.
[19] H OLMES , R., WALKER , R. J., AND M URPHY, G. C. Strathcona
example recommendation tool. In FSE’05, pp. 237–240.
[20] K ATZ , S. M. Estimation of probabilities from sparse data for the
language model component of a speech recognizer. In IEEE Trans. on
Acoustics, Speech and Singal processing (March 1987), vol. ASSP-35.
[21] K NESER , R., AND N EY, H. Improved backing-off for m-gram language modeling. In Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing (May 1995), vol. I.
[22] KOMBRINK , S., M IKOLOV, T., K ARAFIÁT, M., AND B URGET, L.
Recurrent neural network based language modeling in meeting recognition. In INTERSPEECH (2011), pp. 2877–2880.
[23] M ANDELIN , D., X U , L., B ODÍK , R., AND K IMELMAN , D. Jungloid
mining: Helping to navigate the api jungle. In PLDI ’05 (2005).
[24] M IKOLOV, T., D EORAS , A., P OVEY, D., B URGET, L., AND C ER NOCKY, J. Strategies for training large scale neural network language
models. In ASRU 2011 (2011), IEEE Signal Processing Society.
[25] M ISHNE , A., S HOHAM , S., AND YAHAV, E. Typestate-based semantic code search over partial programs. In OOPSLA ’12 (2012).

[26] P ERELMAN , D., G ULWANI , S., BALL , T., AND G ROSSMAN , D.
Type-directed completion of partial expressions. In PLDI (2012).
We thank the anonymous reviewers for their helpful suggestions[27] R EISS , S. P. Semantics-based code search. In ICSE’09.
which made the paper better. We also thank Codota for providing[28] ROSENFELD , R. Two decades of statistical language modeling: Where
the code snippets on which we trained the statistical models. Fido we go from here. In Proceedings of the IEEE (2000), p. 2000.
nally, we thank David F. Bacon for suggesting the idea of code
[29]
S HOHAM , S., YAHAV, E., F INK , S., AND P ISTOIA , M. Static specificompletion in the statistical context.
cation mining using automata-based abstractions. In ISSTA ’07 (2007).
[30] S OLAR -L EZAMA , A. The sketching approach to program synthesis.
References
In APLAS ’09 (2009).
[1] Android-er.
http://android-er.blogspot.ch/2011/03/set-wallpaper[31] S OLAR -L EZAMA , A., TANCAU , L., B ODÍK , R., S ESHIA , S. A., AND
using-wallpapermanager.html.
S ARASWAT, V. A. Combinatorial sketching for finite programs. In
ASPLOS (2006), pp. 404–415.
[2] Android how-to’s. https://sites.google.com/site/androidhowto/how-to1/display-a-web-page.
[32] S RIVASTAVA , S., G ULWANI , S., AND F OSTER , J. S. From program
verification to program synthesis. In POPL ’10 (2010).
[3] Stack overflow. http://www.stackoverflow.com/.
[33]
S TEENSGAARD , B. Points-to analysis in almost linear time. In Pro[4] Tutorial for android. http://www.tutorialforandroid.com/2009/01/changingceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Princiscreen-brightness.html.
ples of programming languages (1996), POPL ’96, pp. 32–41.
[5] Tutorial for android. http://www.tutorialforandroid.com/2009/10/turn[34] S TOLCKE , A. SRILM-an Extensible Language Modeling Toolkit.
off-turn-on-wifi-in-android-using.html.
International Conference on Spoken Language Processing (2002).
[6] Vogella tutorials. http://www.vogella.com/articles/AndroidMedia/article.html.
[35] T HUMMALAPENTA , S., AND X IE , T. Parseweb: a programmer assis[7] A LNUSAIR , A., Z HAO , T., AND B ODDEN , E. Effective API navigatant for reusing open source code on the web. In ASE ’07 (2007).
tion and reuse. In IRI (aug. 2010), pp. 7 –12.
[36] VALLÉE -R AI , R., ET AL . Soot - a Java Optimization Framework. In[8] A MMONS , G., B ODÍK , R., AND L ARUS , J. R. Mining specifications.
Proceedings of CASCON 1999 (1999), pp. 125–135.
In POPL ’02 (2002).
[37] V ECHEV, M., AND YAHAV, E. Deriving linearizable fine-grained[9] B ECKMAN , N., K IM , D., AND A LDRICH , J. An empirical study of
concurrent objects. In PLDI ’08 (2008).
object protocols in the wild. In ECOOP’11.
[38] WASYLKOWSKI , A., AND Z ELLER , A. Mining temporal specifica[10] B ENGIO , Y., D UCHARME , R., V INCENT, P., AND JANVIN , C. A
tions from object usage. In Autom. Softw. Eng. (2011), vol. 18.
neural probabilistic language model. J. Mach. Learn. Res. 3 (Mar.
[39] W EIMER , W., AND N ECULA , G. Mining temporal specifications for2003), 1137–1155.
error detection. In TACAS’05, vol. 3440 of LNCS. 2005, pp. 461–476.
[11] C OOK , J. E., AND W OLF, A. L. Discovering models of software[40]
W ITTEN , I. H., AND B ELL , T. C. The zero-frequency problem: Estiprocesses from event-based data. ACM Trans. Softw. Eng. Methodol.
mating the probabilities of novel events in adaptive text compression.
7, 3 (1998), 215–249.
IEEE Transactions on Information Theory 37, 4 (1991), 1085–1094.
[12] DAGENAIS , B., AND H ENDREN , L. J. Enabling static analysis for[41]
YANG , J., E VANS , D., B HARDWAJ , D., B HAT, T., AND DAS , M.
partial Java programs. In OOPSLA’08, pp. 313–328.
Perracotta: mining temporal API rules from imperfect traces. In ICSE
[13] E LMAN , J. L. Finding structure in time. Cognitive Science 14, 2’06, pp. 282–291.
(1990), 179–211.
[42] Y ESSENOV, K., X U , Z., AND S OLAR -L EZAMA , A. Data-driven[14] G ULWANI , S. Dimensions in program synthesis. In symp. on Princisynthesis for object-oriented frameworks. In OOPSLA ’11 (2011).
ples and practice of declarative programming (2010), PPDP ’10.
[43] Z HONG , H., X IE , T., Z HANG , L., P EI , J., AND M EI , H. MAPO:[15] G VERO , T., K UNCAK , V., K URAJ , I., AND P ISKAC , R. Complete
Mining and recommending API usage patterns. In ECOOP’09.
completion using types and weights. In PLDI ’13 (2013).

Acknowledgements[16] G VERO , T., K UNCAK , V., AND P ISKAC , R. Interactive synthesis ofcode snippets. In CAV’11, vol. 6806 of LNCS. 2011.