A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Speech-recognition systems must often decide between competing ways of breaking up the acoustic input into strings of words. Since the possible strings may be acoustically similar, a language model is required; given a word string, the model returns its linguistic probability. Several Markov language models are discussed. A novel kind of language model which reflects short-term patterns of word use by means of a cache component (analogous to cache memory in hardware terminology) is presented. The model also contains a 3g-gram component of the traditional type. The combined model and a pure 3g-gram model were tested on samples drawn from the Lancaster-Oslo/Bergen (LOB) corpus of English text. The relative performance of the two models is examined, and suggestions for the future improvements are made. > <s> BIB001 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> In stochastic language modeling, backing-off is a widely used method to cope with the sparse data problem. In case of unseen events this method backs off to a less specific distribution. In this paper we propose to use distributions which are especially optimized for the task of backing-off. Two different theoretical derivations lead to distributions which are quite different from the probability distributions that are usually used for backing-off. Experiments show an improvement of about 10% in terms of perplexity and 5% in terms of word error rate. <s> BIB002 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Learning to store information over extended time intervals by recurrent backpropagation takes a very long time, mostly because of insufficient, decaying error backflow. We briefly review Hochreiter's (1991) analysis of this problem, then address it by introducing a novel, efficient, gradient based method called long short-term memory (LSTM). Truncating the gradient where this does not do harm, LSTM can learn to bridge minimal time lags in excess of 1000 discrete-time steps by enforcing constant error flow through constant error carousels within special units. Multiplicative gate units learn to open and close access to the constant error flow. LSTM is local in space and time; its computational complexity per time step and weight is O. 1. Our experiments with artificial data involve local, distributed, real-valued, and noisy pattern representations. In comparisons with real-time recurrent learning, back propagation through time, recurrent cascade correlation, Elman nets, and neural sequence chunking, LSTM leads to many more successful runs, and learns much faster. LSTM also solves complex, artificial long-time-lag tasks that have never been solved by previous recurrent network algorithms. <s> BIB003 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Tree substitution grammars (TSGs) offer many advantages over context-free grammars (CFGs), but are hard to learn. Past approaches have resorted to heuristics. In this paper, we learn a TSG using Gibbs sampling with a nonparametric prior to control subtree size. The learned grammars perform significantly better than heuristically extracted ones on parsing accuracy. <s> BIB004 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Inducing a grammar from text has proven to be a notoriously challenging learning task despite decades of research. The primary reason for its difficulty is that in order to induce plausible grammars, the underlying model must be capable of representing the intricacies of language while also ensuring that it can be readily learned from data. The majority of existing work on grammar induction has favoured model simplicity (and thus learnability) over representational capacity by using context free grammars and first order dependency grammars, which are not sufficiently expressive to model many common linguistic constructions. We propose a novel compromise by inferring a probabilistic tree substitution grammar, a formalism which allows for arbitrarily large tree fragments and thereby better represent complex linguistic structures. To limit the model's complexity we employ a Bayesian non-parametric prior which biases the model towards a sparse grammar with shallow productions. We demonstrate the model's efficacy on supervised phrase-structure parsing, where we induce a latent segmentation of the training treebank, and on unsupervised dependency grammar induction. In both cases the model uncovers interesting latent linguistic structures while producing competitive results. <s> BIB005 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Natural languages like English are rich, complex, and powerful. The highly creative and graceful use of languages like English and Tamil, by masters like Shakespeare and Avvaiyar, can certainly delight and inspire. But in practice, given cognitive constraints and the exigencies of daily life, most human utterances are far simpler and much more repetitive and predictable. In fact, these utterances can be very usefully modeled using modern statistical methods. This fact has led to the phenomenal success of statistical approaches to speech recognition, natural language translation, question-answering, and text mining and comprehension. We begin with the conjecture that most software is also natural, in the sense that it is created by humans at work, with all the attendant constraints and limitations — and thus, like natural language, it is also likely to be repetitive and predictable. We then proceed to ask whether a) code can be usefully modeled by statistical language models and b) such models can be leveraged to support software engineers. Using the widely adopted n-gram model, we provide empirical evidence supportive of a positive answer to both these questions. We show that code is also very repetitive, and in fact even more so than natural languages. As an example use of the model, we have developed a simple code completion engine for Java that, despite its simplicity, already improves Eclipse's built-in completion capability. We conclude the paper by laying out a vision for future research in this area. <s> BIB006 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Recent research has successfully applied the statistical n-gram language model to show that source code exhibits a good level of repetition. The n-gram model is shown to have good predictability in supporting code suggestion and completion. However, the state-of-the-art n-gram approach to capture source code regularities/patterns is based only on the lexical information in a local context of the code units. To improve predictability, we introduce SLAMC, a novel statistical semantic language model for source code. It incorporates semantic information into code tokens and models the regularities/patterns of such semantic annotations, called sememes, rather than their lexemes. It combines the local context in semantic n-grams with the global technical concerns/functionality into an n-gram topic model, together with pairwise associations of program elements. Based on SLAMC, we developed a new code suggestion method, which is empirically evaluated on several projects to have relatively 18-68% higher accuracy than the state-of-the-art approach. <s> BIB007 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> The tens of thousands of high-quality open source software projects on the Internet raise the exciting possibility of studying software development by finding patterns across truly large source code repositories. This could enable new tools for developing code, encouraging reuse, and navigating large projects. In this paper, we build the first giga-token probabilistic language model of source code, based on 352 million lines of Java. This is 100 times the scale of the pioneering work by Hindle et al. The giga-token model is significantly better at the code suggestion task than previous models. More broadly, our approach provides a new “lens” for analyzing software projects, enabling new complexity metrics based on statistical analysis of large corpora. We call these metrics data-driven complexity metrics. We propose new metrics that measure the complexity of a code module and the topical centrality of a module to a software project. In particular, it is possible to distinguish reusable utility classes from classes that are part of a program's core logic based solely on general information theoretic criteria. <s> BIB008 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> 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 to a natural-language processing problem of predicting probabilities of sentences. We design a simple and scalable static analysis that extracts sequences of method calls from a large codebase, and index 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 to synthesize 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. <s> BIB009 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> The n-gram language model, which has its roots in statistical natural language processing, has been shown to successfully capture the repetitive and predictable regularities (“naturalness") of source code, and help with tasks such as code suggestion, porting, and designing assistive coding devices. However, we show in this paper that this natural-language-based model fails to exploit a special property of source code: localness. We find that human-written programs are localized: they have useful local regularities that can be captured and exploited. We introduce a novel cache language model that consists of both an n-gram and an added “cache" component to exploit localness. We show empirically that the additional cache component greatly improves the n-gram approach by capturing the localness of software, as measured by both cross-entropy and suggestion accuracy. Our model’s suggestion accuracy is actually comparable to a state-of-the-art, semantically augmented language model; but it is simpler and easier to implement. Our cache language model requires nothing beyond lexicalization, and thus is applicable to all programming languages. <s> BIB010 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> We study the problem of building generative models of natural source code (NSC); that is, source code written and understood by humans. Our primary contribution is to describe a family of generative models for NSC that have three key properties: First, they incorporate both sequential and hierarchical structure. Second, we learn a distributed representation of source code elements. Finally, they integrate closely with a compiler, which allows leveraging compiler logic and abstractions when building structure into the model. We also develop an extension that includes more complex structure, refining how the model generates identifier tokens based on what variables are currently in scope. Our models can be learned efficiently, and we show empirically that including appropriate structure greatly improves the models, measured by the probability of generating test programs. <s> BIB011 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Every programmer has a characteristic style, ranging from preferences about identifier naming to preferences about object relationships and design patterns. Coding conventions define a consistent syntactic style, fostering readability and hence maintainability. When collaborating, programmers strive to obey a project’s coding conventions. However, one third of reviews of changes contain feedback about coding conventions, indicating that programmers do not always follow them and that project members care deeply about adherence. Unfortunately, programmers are often unaware of coding conventions because inferring them requires a global view, one that aggregates the many local decisions programmers make and identifies emergent consensus on style. We present NATURALIZE, a framework that learns the style of a codebase, and suggests revisions to improve stylistic consistency. NATURALIZE builds on recent work in applying statistical natural language processing to source code. We apply NATURALIZE to suggest natural identifier names and formatting conventions. We present four tools focused on ensuring natural code during development and release management, including code review. NATURALIZE achieves 94 % accuracy in its top suggestions for identifier names. We used NATURALIZE to generate 18 patches for 5 open source projects: 14 were accepted. <s> BIB012 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> We present the first method for automatically mining code idioms from a corpus of previously written, idiomatic software projects. We take the view that a code idiom is a syntactic fragment that recurs across projects and has a single semantic purpose. Idioms may have metavariables, such as the body of a for loop. Modern IDEs commonly provide facilities for manually defining idioms and inserting them on demand, but this does not help programmers to write idiomatic code in languages or using libraries with which they are unfamiliar. We present Haggis, a system for mining code idioms that builds on recent advanced techniques from statistical natural language processing, namely, nonparametric Bayesian probabilistic tree substitution grammars. We apply Haggis to several of the most popular open source projects from GitHub. We present a wide range of evidence that the resulting idioms are semantically meaningful, demonstrating that they do indeed recur across software projects and that they occur more frequently in illustrative code examples collected from a Q&A site. Manual examination of the most common idioms indicate that they describe important program concepts, including object creation, exception handling, and resource management. <s> BIB013 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Descriptive names are a vital part of readable, and hence maintainable, code. Recent progress on automatically suggesting names for local variables tantalizes with the prospect of replicating that success with method and class names. However, suggesting names for methods and classes is much more difficult. This is because good method and class names need to be functionally descriptive, but suggesting such names requires that the model goes beyond local context. We introduce a neural probabilistic language model for source code that is specifically designed for the method naming problem. Our model learns which names are semantically similar by assigning them to locations, called embeddings, in a high-dimensional continuous space, in such a way that names with similar embeddings tend to be used in similar contexts. These embeddings seem to contain semantic information about tokens, even though they are learned only from statistical co-occurrences of tokens. Furthermore, we introduce a variant of our model that is, to our knowledge, the first that can propose neologisms, names that have not appeared in the training corpus. We obtain state of the art results on the method, class, and even the simpler variable naming tasks. More broadly, the continuous embeddings that are learned by our model have the potential for wide application within software engineering. <s> BIB014 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Neural machine translation (NMT) models typically operate with a fixed vocabulary, but translation is an open-vocabulary problem. Previous work addresses the translation of out-of-vocabulary words by backing off to a dictionary. In this paper, we introduce a simpler and more effective approach, making the NMT model capable of open-vocabulary translation by encoding rare and unknown words as sequences of subword units. This is based on the intuition that various word classes are translatable via smaller units than words, for instance names (via character copying or transliteration), compounds (via compositional translation), and cognates and loanwords (via phonological and morphological transformations). We discuss the suitability of different word segmentation techniques, including simple character ngram models and a segmentation based on the byte pair encoding compression algorithm, and empirically show that subword models improve over a back-off dictionary baseline for the WMT 15 translation tasks English!German and English!Russian by up to 1.1 and 1.3 BLEU, respectively. <s> BIB015 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Recurrent Neural Networks (RNNs), and specifically a variant with Long Short-Term Memory (LSTM), are enjoying renewed interest as a result of successful applications in a wide range of machine learning problems that involve sequential data. However, while LSTMs provide exceptional results in practice, the source of their performance and their limitations remain rather poorly understood. Using character-level language models as an interpretable testbed, we aim to bridge this gap by providing an analysis of their representations, predictions and error types. In particular, our experiments reveal the existence of interpretable cells that keep track of long-range dependencies such as line lengths, quotes and brackets. Moreover, our comparative analysis with finite horizon n-gram models traces the source of the LSTM improvements to long-range structural dependencies. Finally, we provide analysis of the remaining errors and suggests areas for further study. <s> BIB016 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Deep learning subsumes algorithms that automatically learn compositional representations. The ability of these models to generalize well has ushered in tremendous advances in many fields such as natural language processing (NLP). Recent research in the software engineering (SE) community has demonstrated the usefulness of applying NLP techniques to software corpora. Hence, we motivate deep learning for software language modeling, highlighting fundamental differences between state-of-the-practice software language models and connectionist models. Our deep learning models are applicable to source code files (since they only require lexically analyzed source code written in any programming language) and other types of artifacts. We show how a particular deep learning model can remember its state to effectively model sequential data, e.g., Streaming software tokens, and the state is shown to be much more expressive than discrete tokens in a prefix. Then we instantiate deep learning models and show that deep learning induces high-quality models compared to n-grams and cache-based n-grams on a corpus of Java projects. We experiment with two of the models' hyper parameters, which govern their capacity and the amount of context they use to inform predictions, before building several committees of software language models to aid generalization. Then we apply the deep learning models to code suggestion and demonstrate their effectiveness at a real SE task compared to state-of-the-practice models. Finally, we propose avenues for future work, where deep learning can be brought to bear to support model-based testing, improve software lexicons, and conceptualize software artifacts. Thus, our work serves as the first step toward deep learning software repositories. <s> BIB017 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> We consider the problem of building probabilistic models that jointly model short natural language utterances and source code snippets. The aim is to bring together recent work on statistical modelling of source code and work on bimodal models of images and natural language. The resulting models are useful for a variety of tasks that involve natural language and source code. We demonstrate their performance on two retrieval tasks: retrieving source code snippets given a natural language query, and retrieving natural language descriptions given a source code query (i.e., source code captioning). Experiments show there to be promise in this direction, and that modelling the structure of source code improves performance. <s> BIB018 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> n-gram statistical language model has been successfully applied to capture programming patterns to support code completion and suggestion. However, the approaches using n-gram face challenges in capturing the patterns at higher levels of abstraction due to the mismatch between the sequence nature in n-grams and the structure nature of syntax and semantics in source code. This paper presents GraLan, a graph-based statistical language model and its application in code suggestion. GraLan can learn from a source code corpus and compute the appearance probabilities of any graphs given the observed (sub)graphs. We use GraLan to develop an API suggestion engine and an AST-based language model, ASTLan. ASTLan supports the suggestion of the next valid syntactic template and the detection of common syntactic templates. Our empirical evaluation on a large corpus of open-source projects has shown that our engine is more accurate in API code suggestion than the state-of-the-art approaches, and in 75% of the cases, it can correctly suggest the API with only five candidates. ASTLan also has high accuracy in suggesting the next syntactic template and is able to detect many useful and common syntactic templates. <s> BIB019 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> We introduce a new generative model for code called probabilistic higher order grammar (PHOG). PHOG generalizes probabilistic context free grammars (PCFGs) by allowing conditioning of a production rule beyond the parent non-terminal, thus capturing rich contexts relevant to programs. Even though PHOG is more powerful than a PCFG, it can be learned from data just as efficiently. We trained a PHOG model on a large JavaScript code corpus and show that it is more precise than existing models, while similarly fast. As a result, PHOG can immediately benefit existing programming tools based on probabilistic models of code. <s> BIB020 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Existing language models such as n-grams for software code often fail to capture a long context where dependent code elements scatter far apart. In this paper, we propose a novel approach to build a language model for software code to address this particular issue. Our language model, partly inspired by human memory, is built upon the powerful deep learning-based Long Short Term Memory architecture that is capable of learning long-term dependencies which occur frequently in software code. Results from our intrinsic evaluation on a corpus of Java projects have demonstrated the effectiveness of our language model. This work contributes to realizing our vision for DeepSoft, an end-to-end, generic deep learning-based framework for modeling software and its development process. <s> BIB021 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> To enhance developer productivity, all modern integrated development environments (IDEs) include code suggestion functionality that proposes likely next tokens at the cursor. While current IDEs work well for statically-typed languages, their reliance on type annotations means that they do not provide the same level of support for dynamic programming languages as for statically-typed languages. Moreover, suggestion engines in modern IDEs do not propose expressions or multi-statement idiomatic code. Recent work has shown that language models can improve code suggestion systems by learning from software repositories. This paper introduces a neural language model with a sparse pointer network aimed at capturing very long range dependencies. We release a large-scale code suggestion corpus of 41M lines of Python code crawled from GitHub. On this corpus, we found standard neural language models to perform well at suggesting local phenomena, but struggle to refer to identifiers that are introduced many tokens in the past. By augmenting a neural language model with a pointer network specialized in referring to predefined classes of identifiers, we obtain a much lower perplexity and a 5 percentage points increase in accuracy for code suggestion compared to an LSTM baseline. In fact, this increase in code suggestion accuracy is due to a 13 times more accurate prediction of identifiers. Furthermore, a qualitative analysis shows this model indeed captures interesting long-range dependencies, like referring to a class member defined over 60 tokens in the past. <s> BIB022 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> 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 a small sample of the entire dataset while avoiding overfitting, and a dataset 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 noise bound. 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 which target 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 statistical code 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) over trees and to learn functions in that DSL directly from the dataset. These learned functions then condition the predictions made by the system. 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 that the learned functions are a natural mechanism for explaining the prediction). As a result, our code completion system surpasses the prediction capabilities of existing, hard-wired systems. <s> BIB023 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Current statistical language modeling techniques, including deep-learning based models, have proven to be quite effective for source code. We argue here that the special properties of source code can be exploited for further improvements. In this work, we enhance established language modeling approaches to handle the special challenges of modeling source code, such as: frequent changes, larger, changing vocabularies, deeply nested scopes, etc. We present a fast, nested language modeling toolkit specifically designed for software, with the ability to add & remove text, and mix & swap out many models. Specifically, we improve upon prior cache-modeling work and present a model with a much more expansive, multi-level notion of locality that we show to be well-suited for modeling software. We present results on varying corpora in comparison with traditional N-gram, as well as RNN, and LSTM deep-learning language models, and release all our source code for public use. Our evaluations suggest that carefully adapting N-gram models for source code can yield performance that surpasses even RNN and LSTM based deep-learning models. <s> BIB024 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Recurrent neural networks have achieved remarkable success at generating sequences with complex structures, thanks to advances that include richer embeddings of input and cures for vanishing gradients. Trained only on sequences from a known grammar, though, they can still struggle to learn rules and constraints of the grammar. ::: Neural Attribute Machines (NAMs) are equipped with a logical machine that represents the underlying grammar, which is used to teach the constraints to the neural machine by (i) augmenting the input sequence, and (ii) optimizing a custom loss function. Unlike traditional RNNs, NAMs are exposed to the grammar, as well as samples from the language of the grammar. During generation, NAMs make significantly fewer violations of the constraints of the underlying grammar than RNNs trained only on samples from the language of the grammar. <s> BIB025 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Code completion, an essential part of modern software development, yet can bechallenging for dynamically typed programming languages. In this paper we ex-plore the use of neural network techniques to automatically learn code completionfrom a large corpus of dynamically typed JavaScript code. We show differentneural networks that leverage not only token level information but also structuralinformation, and evaluate their performance on different prediction tasks. Wedemonstrate that our models can outperform the state-of-the-art approach, whichis based on decision tree techniques, on both next non-terminal and next terminalprediction tasks by 3.8 points and 0.5 points respectively. We believe that neuralnetwork techniques can play a transformative role in helping software developersmanage the growing complexity of software systems, and we see this work as afirst step in that direction. <s> BIB026 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> We consider the problem of parsing natural language descriptions into source code written in a general-purpose programming language like Python. Existing data-driven methods treat this problem as a language generation task without considering the underlying syntax of the target programming language. Informed by previous work in semantic parsing, in this paper we propose a novel neural architecture powered by a grammar model to explicitly capture the target syntax as prior knowledge. Experiments find this an effective way to scale up to generation of complex programs from natural language descriptions, achieving state-of-the-art results that well outperform previous code generation and semantic parsing approaches. <s> BIB027 </s> A Survey of Machine Learning for Big Code and Naturalness <s> Representing Code in Code-generating Models. <s> Graph-structured data is important in modeling relationships between multiple entities, and can be used to represent states of the world as well as many data structures. Li et al. (2016) describe a model known as a Gated Graph Sequence Neural Network (GGS-NN) that produces sequences from graph-structured input. In this work I introduce the Gated Graph Transformer Neural Network (GGT-NN), an extension of GGS-NNs that uses graph-structured data as an intermediate representation. The model can learn to construct and modify graphs in sophisticated ways based on textual input, and also to use the graphs to produce a variety of outputs. For example, the model successfully learns to solve almost all of the bAbI tasks (Weston et al., 2016), and also discovers the rules governing graphical formulations of a simple cellular automaton and a family of Turing machines. <s> BIB028
Probabilistic models for generating structured objects are widely in use in machine learning and natural language processing with a wide range of applications. Machine-learning research is considering a wide range of structures from natural language sentences to chemical structures and images. Within the source code domain, we can broadly find three categories of models based on the way they generate code's structure: token-level models that generate code as a sequence of tokens, syntactic models that generate code as a tree, and semantic models that generate graph structures. Note that this distinction is about the generative process and not about the information used within this process. For example, Nguyen et al. BIB007 uses syntactic context but is classified as a token-level model that generates tokens. Token-level Models (Sequences). Sequence-based models are commonly used because of their simplicity. They view code as a sequence of elements, usually code tokens or characters, i.e., c = t 1 . . . t M . Predicting a large sequence in a single step is infeasible due to the exponential number of possible sequences; for a set of V elements, there are |V | N sequences of length N . Therefore, most sequence-based models predict sequences by sequentially generating each element, i.e., they model the probability distribution P (t m |t 1 . . . t m−1 , C(c)). However, directly modeling this distribution is impractical and all models make different simplifying assumptions. The n-gram model has been a widely used sequence-based model, most commonly used as a language model. It is an effective and practical LM for capturing local and simple statistical dependencies in sequences. n-gram models assume that tokens are generated sequentially, left to right, and that the next token can be predicted using only the previous n − 1 tokens. The consequence of capturing a short context is that n-gram models cannot handle long-range dependencies, notably scoping information. Formally, the probability of a token t m , is conditioned on the context C(c) (if any) and the generated sequence so far t 1 . . . t m−1 , which is assumed to depend on only the previous n − 1 tokens. Under this assumption, we write To use this equation, we need to know the conditional probabilities P (t m |t m−1 . . . t m−n+1 , C(c)) for each possible n-gram and context. This is a table of |V | n numbers for each context C(c). These are the parameters of the model that we learn from the training corpus. The simplest way to estimate the model parameters is to set P (t m |t m−1 . . . t m−n+1 ) to the proportion of times that t m follows t m−1 . . . t m−n+1 . In practice, this simple estimator does not work well, because it assigns zero probability to n-grams that do not occur in the training corpus. Instead, n-gram models use smoothing methods  as a principled way for assigning probability to unseen n-grams by extrapolating information from m-grams (m < n). Furthermore, considering n-gram models with non-empty contexts C(c) exacerbates sparsity rendering these models impractical. Because of this, n-grams are predominantly used as language models. The use of n-gram LMs in software engineering originated with the pioneering work of Hindle et al. BIB006 , who used an n-gram LM with Kneser-Ney BIB002 smoothing. Most subsequent research has followed this practice. In contrast to text, code tends to be more verbose BIB006 , and much information is lost within the n − 1 tokens of the context. To tackle this problem, Nguyen et al. BIB007 extended the standard n-gram model by annotating the code tokens with parse information that can be extracted from the currently generated sequence. This increases the available context information allowing the n-gram model to achieve better predictive performance. Following this trend, but using concrete and abstract semantics of code, Raychev et al. BIB009 create a token-level model that treats code generation as a combined synthesis and probabilistic modeling task. Tu et al. BIB010 and, later, Hellendoorn and Devanbu BIB024 noticed that code has a high degree of localness, where identifiers (e.g., variable names) are repeated often within close distance. In their work, they adapted work in speech and natural language processing BIB001 adding a cache mechanism that assigns higher probability to tokens that have been observed most recently, achieving significantly better performance compared to other n-gram models. Modeling identifiers in code is challenging BIB014 BIB008 BIB020 BIB011 . The agglutinations of multiple subtokens (e.g., in getFinalResults) when creating identifiers is one reason. Following recent NLP work that models subword structure (e.g., morphology) BIB015 , explicitly modeling subtoken in identifiers may improve the performance of generative models. Existing token-level code-generating models do not produce syntactically valid code. Raychev et al. BIB009 added additional context in the form of constraints-derived from program analysis-to avoid generating some incorrect code. More recently, sequence-based code models have turned to deep recurrent neural network (RNN) models to outperform n-grams. These models predict each token sequentially but loosen the fixed-context-size assumption, instead representing the context using a distributed vector representation (Section 4.2). Following this trend, Karpathy et al. BIB016 and Cummins et al.  use character-level LSTMs BIB003 . Similarly, White et al. BIB017 and Dam et al. BIB021 use token-level RNNs. Recently, Bhoopchand et al. BIB022 used a token sparse pointer-based neural model of Python that learns to copy recently declared identifiers to capture very long-range dependencies of identifiers, outperforming standard LSTM models. BIB012 Although neural models usually have superior predictive performance, training them is significantly more costly compared to n-gram models usually requiring orders of magnitude more data. Intuitively, there are two reasons why deep-learning methods have proven successful for language models. First, the hidden state in an RNN can encode longer-range dependencies of variable-length beyond the short context of n-gram models. Second, RNN language models can learn a much richer notion of similarity across contexts. For example, consider a 13-gram model over code, in which we are trying to estimate the distribution following the context for(int i=N; i>=0; i--). In a corpus, few examples of this pattern may exist, because such long contexts occur rarely. A simple ngram model cannot exploit the fact that this context is very similar to for(int j=M; j>=0; j--). But a neural network can exploit it by learning to assign these two sequences similar vectors. Syntactic Models (Trees). Syntactic (or structural) code-generating models model code at the level of abstract syntax trees (ASTs). Thus, in contrast to sequence-based models, they describe a stochastic process of generating tree structures. Such models make simplifying assumptions about how a tree is generated, usually following generative NLP models of syntactic trees: They start from a root node and then sequentially generate children top to bottom and left to right. Syntactic models generate a tree node conditioned on context defined as the forest of subtrees generated so far. In contrast to sequence models, these models-by construction-generate syntactically correct code. In general, learning models that generate tree structures is harder compared to generating sequences: It is relatively computationally expensive, especially for neural models, given the variable shape and size of the trees that inhibit efficient batching. In contrast to their wide application in NLP, probabilistic context free grammars (PCFG) have been found to be unsuitable as language models of code BIB011 BIB023 . This may seem surprising, because most parsers assume that programming languages are context free. But the problem is that the PCFGs are not a good model of statistical dependencies between code tokens, because nearby tokens may be far away in the AST. So it is not that PCFGs do not capture long-range dependencies (n-gram-based models do not either), but that they do not even capture close-range dependencies that matter BIB020 . Further, ASTs tend to be deeper and wider than text parse trees due to the highly compositional nature of code. Maddison and Tarlow BIB011 and Allamanis et al. BIB018 increase the size of the context considered by creating a non-context-free log-bilinear neural network grammar, using a distributed vector representation for the context. Additionally, Maddison and Tarlow BIB011 restricts the generation to generate variables that have been declared. To achieve this, they use the deterministically known information and filter out invalid output. This simple process always produces correct code, even when the network does not learn to produce it. In contrast, Amodio et al. BIB025 create a significantly more complex model that aims to learn to enforce deterministic constraints of the code generation rather than enforcing them on the directly on the output. We further discuss the issue of embedding constraints and problem structure in models vs. learning the constraints in Section 6. Bielik et al. BIB020 and Raychev et al. BIB023 increase the context by annotating PCFGs with a learned program that uses features from the code. Although the programs can, in principle, be arbitrary, they limit themselves to synthesizing decision tree programs. Similarly, Wang et al. BIB026 and Yin and Neubig BIB027 use an LSTM over AST nodes to achieve the same goal. Allamanis and Sutton BIB013 also create a syntactic model learning Bayesian TSGs BIB005 BIB004 (see Section 4.3). Semantic Models (Graphs). Semantic code-generating models view code as a graph. Graphs are a natural representation of source code that require little abstraction or projection. Therefore, graph model can be thought as generalizations of sequence and tree models. However, generating complex graphs is hard, since there is no natural "starting" point or generative process, as reflected by the limited number of graphs models in the literature. We refer the interested reader to the related work section of Johnson BIB028 for a discussion of recent models in the machine-learning literature. To our knowledge, there are no generative models that directly generate graph representations of realistic code (e.g., dataflow graphs). Nguyen and Nguyen BIB019 propose a generative model, related to graph generative models in NLP, that suggests application programming interface (API) completions. They train their model over API usages. However, they predict entire graphs as completions and perform no smoothing, so their model will assign zero probability to unseen graphs. In this way, their model differs from graph generating models in NLP, which can generate arbitrary graphs.