A Survey of Machine Learning for Big Code and Naturalness <s> INTRODUCTION <s> A software system interacts with third-party libraries through various APIs. Using these library APIs often needs tofollow certain usage patterns. Furthermore, ordering rules (specifications) exist between APIs, and these rules govern the secure and robust operation of the system using these APIs. But these patterns and rules may not be well documented by the API developers. Previous approaches mine frequent association rules, itemsets, or subsequences that capture API call patterns shared by API client code. However, these frequent API patterns cannot completely capture some useful orderings shared by APIs, especially when multiple APIs are involved across different procedures. In this paper, we present a framework to automatically extract usage scenarios among user-specified APIs as partial orders, directly from the source code (API client code). We adapt a model checker to generate interprocedural control-flow-sensitive static traces related to the APIs of interest. Different API usage scenarios are extracted from the static traces by our scenario extraction algorithm and fed to a miner. The miner summarizes different usage scenarios as compact partial orders. Specifications are extracted from the frequent partial orders using our specification extraction algorithm. Our experience of applying the framework on 72 X11 clients with 200K LOC in total has shown that theextracted API partial orders are useful in assisting effective API reuse and checking. <s> BIB001 </s> A Survey of Machine Learning for Big Code and Naturalness <s> INTRODUCTION <s> This paper presents the results of the first study of the uniqueness of source code. We define the uniqueness of a unit of source code with respect to the entire body of written software, which we approximate with a corpus of 420 million lines of source code. Our high-level methodology consists of examining a collection of 6,000 software projects and measuring the degree to which each project can be `assembled' solely from portions of this corpus, thus providing a precise measure of `uniqueness' that we call syntactic redundancy. We parameterized our study over a variety of variables, the most important of which being the level of granularity at which we view source code. Our suite of experiments together consumed approximately four months of CPU time, providing quantitative answers to the following questions: at what levels of granularity is software unique, and at a given level of granularity, how unique is software? While we believe these questions to be of intrinsic interest, we discuss possible applications to genetic programming and developer productivity tools. <s> BIB002 </s> A Survey of Machine Learning for Big Code and Naturalness <s> INTRODUCTION <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 regular, 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 completion capability. We conclude the paper by laying out a vision for future research in this area. <s> BIB003 </s> A Survey of Machine Learning for Big Code and Naturalness <s> INTRODUCTION <s> We study the effectiveness of neural sequence models for premise selection in automated theorem proving, one of the main bottlenecks in the formalization of mathematics. We propose a two stage approach for this task that yields good results for the premise selection task on the Mizar corpus while avoiding the hand-engineered features of existing state-of-the-art models. To our knowledge, this is the first time deep learning has been applied to theorem proving on a large scale. <s> BIB004
Software is ubiquitous in modern society. Almost every aspect of life, including healthcare, energy, transportation, public safety, and even entertainment, depends on the reliable operation of highquality software. Unfortunately, developing software is a costly process: Software engineers need to tackle the inherent complexity of software while avoiding bugs and still deliver highly functional software products on time. There is therefore an ongoing demand for innovations in software tools that help make software more reliable and maintainable. New methods are constantly sought to reduce the complexity of software and help engineers construct better software. Structure. First, in Section 2, we discuss the basis of this area, which we call the "naturalness hypothesis." We then review recent work on machine-learning methods for analyzing source code, focusing on probabilistic models, such as n-gram language models and deep-learning methods. BIB001 We also touch on other types of machine-learning-based source code models, aiming to give a broad overview of the area, to explain the core methods and techniques, and to discuss applications in programming languages and software engineering. We focus on work that goes beyond handled, or remain open. Although code and text are similar, code written in a general-purpose programming languages, is a relatively new problem domain for existing ML and NLP techniques. Hindle et al. BIB003 showed not only that exploitable similarity exists between the two via an ngram language model but also that code is even less surprising than text. Although it may seem manifestly obvious that code and text have many differences, it is useful to enumerate these differences carefully, as this allows us to gain insight into when techniques from NLP need to be modified to deal with code. Perhaps the most obvious difference is that code is executable and has formal syntax and semantics. We close by discussing how source code bimodality manifests itself as synchronization points between the algorithmic and explanatory channels. Executability. All code is executable; text often is not. So code is often semantically brittlesmall changes (e.g., swapping function arguments) can drastically change the meaning of code; whereas natural language is more robust in that readers can often understand text even if it contains mistakes. Despite the bimodal nature of code and its human-oriented modality, the sensitivity of code semantics to "noise" necessitates the combination of probabilistic and formal methods. For example, existing work builds probabilistic models then applies strict formal constraints to filter their output (Section 4.1) or uses them to guide formal methods (Section 5.8). Nevertheless, further research on bridging formal and probabilistic methods is needed (Section 6.1). Whether it is possible to translate between natural languages in a way that completely preserves meaning is a matter of debate. Programming languages, on the other hand, can be translated between each other exactly, as all mainstream programming languages are Turing-complete. (That said, porting real-world programs to new languages and platforms remains challenging in practice  .) ML techniques have not yet comprehensively tackled such problems and are currently limited to solely translating among languages with very similar characteristics, e.g., Java and C# (Section 6.1). Programming languages differ in their expressivity and intelligibility, ranging from Haskell to Malbolge, 2 with some especially tailored for certain problem domains; in contrast, natural languages are typically used to communicate across a wide variety of domains. Executability of code induces control and data flows within programs, which have only weak analogs in text. Finally, executability gives rise to additional modalities of code-its static and dynamic views (e.g., execution traces), which are not present in text. Learning over traces or flows are promising directions (Section 6.1). Formality. Programming languages are formal languages, whereas formal languages are only mathematical models of natural language. As a consequence, programming languages are designed top-down by a few designers for many users. Natural languages, in contrast, emerge, bottom up, "through social dynamics"  . Natural languages change gradually, while programming languages exhibit punctuated change: New releases, like Python 3, sometimes break backward compatibility. Formatting can also be meaningful in code: Python's whitespace sensitivity is the canonical example. Text has a robust environmental dependence, whereas code suffers from bit rot-the deterioration of software's functionality through time because of changes in its environment (e.g., dependencies)-because all its explicit environmental interactions must be specified upfront and execution environments evolve much more quickly than natural languages. Source code's formality facilities reuse. Solving a problem algorithmically is cognitively expensive, so developers actively try to reuse code  , moving common functionality into libraries to facilitate reuse. As a result, usually functions are semantically unique within a project. Coding competitions or undergraduate projects are obvious exceptions. In contrast, one can find thousands of news articles describing an important global event. On the other hand, Gabel and Su BIB002 have found that, locally, code is more pattern dense than text (Section 4.1). This has led to important performance improvements on some applications, such as code completion (Section 5.1). Because programming languages are automatically translated into machine code, they must be syntactically, even to a first approximation semantically, unambiguous. BIB004 In contrast to NLP models, which must always account for textual ambiguity, probabilistic models of code can and do take advantage of the rich and unambiguous code structure. Although it is less pervasive, ambiguity remains a problem in the analysis of code, because of issues like polymorphism and aliasing. Section 4.2 and Section 5.4 discuss particularly notable approaches to handling them. Co-reference ambiguities can arise when viewing code statically, especially in dynamically typed languages (Section 6.1). The undefined behavior that some programming languages permit can cause semantic ambiguity, and, in the field, syntactic problems can arise due to nonstandard compilers  ; however, the dominance of a handful of compilers/interpreters for most languages ameliorates both problems. Cross-Channel Interaction. Code's two channels, the algorithmic and the explanatory channels, interact through their semantic units, but mapping code units to textual units remains an open problem. Natural semantic units in code are identifiers, statements, blocks, and functions. None of these universally maps to textual semantic units. For example, identifiers, even verbose function names that seek to describe their function, carry less information than words like "Christmas" or "set." In general, statements in code and sentences in text differ in how much background knowledge the reader needs to understand them in isolation; an arbitrary statement is far more likely to use domain-specific, even project-specific, names or neologisms than an arbitrary sentence is. Blocks vary greatly in length and semantics richness and often lack clear boundaries to a human reader. Functions are clearly delimited and semantically rich but long. In text, a sentence is the natural multiword semantic unit and usually contains fewer than 50 words (tokens). Unfortunately, one cannot, however, easily equate them. A function differs from a sentence or a sequence of sentences, i.e., a paragraph, in that it is named and called, while, in general settings, sentences or paragraphs rarely have names or are referred to elsewhere in a text. Further, a single function acts on the world, so it is like a single action sentence, but is usually much longer, often containing hundreds of tokens, and usually performs multiple actions, making a function closer to a sequence of sentences, or a paragraph, but paragraphs are rarely solely composed of action sentences. Additionally, parse trees of sentences in text tend to be diverse, short, and shallow compared to abstract syntax trees of functions, which are usually much deeper with repetitive internal structure. Code bases are multilingual (i.e., contain code in more than one programming language, e.g., Java and SQL), with different tasks described in different languages, more frequently than text corpora; this can drastically change the shape and frequency of its semantic units. Code has a higher neologism rate than text. Almost 70% of all characters are identifiers, and a developer must choose a name for each one  ; when writing text, an author rarely names new things but usually chooses an existing word to use. Existing work handles code's neologism rate by introducing cache mechanisms or decomposing identifiers at a subtoken level (Section 4.1). Determining which semantic code unit is most useful for which task is an open question. Consider the problem of automatically generating comments that describe code, which can be formalized as a machine translation problem from code to text. Statistical machine translation approaches learn from an aligned corpus. Statement-granular alignment yields redundant comments, while function granular alignment has saliency issues (Section 5.5). As another example, consider code search, where search engines must map queries into semantic code units. Perhaps the answer will be in maps from code to text whose units vary by granularity or context (Section 6.1).