A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> We present a novel strategy for automatically debugging programs given sampled data from thousands of actual user runs. Our goal is to pinpoint those features that are most correlated with crashes. This is accomplished by maximizing an appropriately defined utility function. It has analogies with intuitive debugging heuristics, and, as we demonstrate, is able to deal with various types of bugs that occur in real programs. <s> BIB001 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> We present a statistical debugging algorithm that isolates bugs in programs containing multiple undiagnosed bugs. Earlier statistical algorithms that focus solely on identifying predictors that correlate with program failure perform poorly when there are multiple bugs. Our new technique separates the effects of different bugs and identifies predictors that are associated with individual bugs. These predictors reveal both the circumstances under which bugs occur as well as the frequencies of failure modes, making it easier to prioritize debugging efforts. Our algorithm is validated using several case studies, including examples in which the algorithm identified previously unknown, significant crashing bugs in widely used systems. <s> BIB002 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> We describe a statistical approach to software debugging in the presence of multiple bugs. Due to sparse sampling issues and complex interaction between program predicates, many generic off-the-shelf algorithms fail to select useful bug predictors. Taking inspiration from bi-clustering algorithms, we propose an iterative collective voting scheme for the program runs and predicates. We demonstrate successful debugging results on several real world programs and a large debugging benchmark suite. <s> BIB003 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> The suggestions made by current IDE's code completion features are based exclusively on static type system of the programming language. As a result, often proposals are made which are irrelevant for a particular working context. Also, these suggestions are ordered alphabetically rather than by their relevance in a particular context. In this paper, we present intelligent code completion systems that learn from existing code repositories. We have implemented three such systems, each using the information contained in repositories in a different way. We perform a large-scale quantitative evaluation of these systems, integrate the best performing one into Eclipse, and evaluate the latter also by a user study. Our experiments give evidence that intelligent code completion systems which learn from examples significantly outperform mainstream code completion systems in terms of the relevance of their suggestions and thus have the potential to enhance developers' productivity. <s> BIB004 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <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> BIB005 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <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> BIB006 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> A frustrating aspect of software development is that compiler error messages often fail to locate the actual cause of a syntax error. An errant semicolon or brace can result in many errors reported throughout the file. We seek to find the actual source of these syntax errors by relying on the consistency of software: valid source code is usually repetitive and unsurprising. We exploit this consistency by constructing a simple N-gram language model of lexed source code tokens. We implemented an automatic Java syntax-error locator using the corpus of the project itself and evaluated its performance on mutated source code from several projects. Our tool, trained on the past versions of a project, can effectively augment the syntax error locations produced by the native compiler. Thus we provide a methodology and tool that exploits the naturalness of software source code to detect syntax errors alongside the parser. <s> BIB007 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Links between issue reports and their corresponding commits in version control systems are often missing. However, these links are important for measuring the quality of various parts of a software system, predicting defects, and many other tasks. A number of existing approaches have been designed to solve this problem by automatically linking bug reports to source code commits via comparison of textual information in commit messages with textual contents in the bug reports. Yet, the effectiveness of these techniques is oftentimes sub optimal when commit messages are empty or only contain minimum information, this particular problem makes the process of recovering trace ability links between commits and bug reports particularly challenging. In this work, we aim at improving the effectiveness of existing bug linking techniques by utilizing rich contextual information. We rely on a recently proposed tool, namely Change Scribe, which generates commit messages containing rich contextual information by using a number of code summarization techniques. Our approach then extracts features from these automatically generated commit messages and bug reports and inputs them into a classification technique that creates a discriminative model used to predict if a link exists between a commit message and a bug report. We compared our approach, coined as RCLinker (Rich Context Linker), to MLink, which is an existing state-of-the-art bug linking approach. Our experiment results on bug reports from 6 software projects show that RCLinker can outperform MLink in terms of F-measure by 138.66%. <s> BIB008 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Code completion is an integral part of modern Integrated Development Environments (IDEs). Developers often use it to explore Application Programming Interfaces (APIs). It is also useful to reduce the required amount of typing and to help avoid typos. Traditional code completion systems propose all type-correct methods to the developer. Such a list is often very long with many irrelevant items. More intelligent code completion systems have been proposed in prior work to reduce the list of proposed methods to relevant items. This work extends one of these existing approaches, the Best Matching Neighbor (BMN) algorithm. We introduce Bayesian networks as an alternative underlying model, use additional context information for more precise recommendations, and apply clustering techniques to improve model sizes. We compare our new approach, Pattern-based Bayesian Networks (PBN), to the existing BMN algorithm. We extend previously used evaluation methodologies and, in addition to prediction quality, we also evaluate model size and inference speed. Our results show that the additional context information we collect improves prediction quality, especially for queries that do not contain method calls. We also show that PBN can obtain comparable prediction quality to BMN, while model size and inference speed scale better with large input sizes. <s> BIB009 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Providing feedback, both assessing final work and giving hints to stuck students, is difficult for open-ended assignments in massive online classes which can range from thousands to millions of students. We introduce a neural network method to encode programs as a linear mapping from an embedded precondition space to an embedded postcondition space and propose an algorithm for feedback at scale using these linear maps as features. We apply our algorithm to assessments from the Code.org Hour of Code and Stanford University's CS1 course, where we propagate human comments on student assignments to orders of magnitude more submissions. <s> BIB010 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Software fault localization, the act of identifying the locations of faults in a program, is widely recognized to be one of the most tedious, time consuming, and expensive – yet equally critical – activities in program debugging. Due to the increasing scale and complexity of software today, manually locating faults when failures occur is rapidly becoming infeasible, and consequently, there is a strong demand for techniques that can guide software developers to the locations of faults in a program with minimal human intervention. This demand in turn has fueled the proposal and development of a broad spectrum of fault localization techniques, each of which aims to streamline the fault localization process and make it more effective by attacking the problem in a unique way. In this article, we catalog and provide a comprehensive overview of such techniques and discuss key issues and concerns that are pertinent to software fault localization as a whole. <s> BIB011 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <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> BIB012 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> We present a method for automatically generating repair feedback for syntax errors for introductory programming problems. Syntax errors constitute one of the largest classes of errors (34%) in our dataset of student submissions obtained from a MOOC course on edX. The previous techniques for generating automated feed- back on programming assignments have focused on functional correctness and style considerations of student programs. These techniques analyze the program AST of the program and then perform some dynamic and symbolic analyses to compute repair feedback. Unfortunately, it is not possible to generate ASTs for student pro- grams with syntax errors and therefore the previous feedback techniques are not applicable in repairing syntax errors. ::: We present a technique for providing feedback on syntax errors that uses Recurrent neural networks (RNNs) to model syntactically valid token sequences. Our approach is inspired from the recent work on learning language models from Big Code (large code corpus). For a given programming assignment, we first learn an RNN to model all valid token sequences using the set of syntactically correct student submissions. Then, for a student submission with syntax errors, we query the learnt RNN model with the prefix to- ken sequence to predict token sequences that can fix the error by either replacing or inserting the predicted token sequence at the error location. We evaluate our technique on over 14, 000 student submissions with syntax errors. Our technique can completely re- pair 31.69% (4501/14203) of submissions with syntax errors and in addition partially correct 6.39% (908/14203) of the submissions. <s> BIB013 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Deep Neural Networks have been shown to succeed at a range of natural language tasks such as machine translation and text summarization. While tasks on source code (ie, formal languages) have been considered recently, most work in this area does not attempt to capitalize on the unique opportunities offered by its known syntax and structure. In this work, we introduce SmartPaste, a first task that requires to use such information. The task is a variant of the program repair problem that requires to adapt a given (pasted) snippet of code to surrounding, existing source code. As first solutions, we design a set of deep neural models that learn to represent the context of each variable location and variable usage in a data flow-sensitive way. Our evaluation suggests that our models can learn to solve the SmartPaste task in many cases, achieving 58.6% accuracy, while learning meaningful representation of variable usages. <s> BIB014 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Programming language definitions assign formal meaning to complete programs. Programmers, however, spend a substantial amount of time interacting with incomplete programs - programs with holes, type inconsistencies and binding inconsistencies - using tools like program editors and live programming environments (which interleave editing and evaluation). Semanticists have done comparatively little to formally characterize (1) the static and dynamic semantics of incomplete programs; (2) the actions available to programmers as they edit and inspect incomplete programs; and (3) the behavior of editor services that suggest likely edit actions to the programmer based on semantic information extracted from the incomplete program being edited, and from programs that the system has encountered in the past. ::: ::: This paper serves as a vision statement for a research program that seeks to develop these "missing" semantic foundations. Our hope is that these contributions, which will take the form of a series of simple formal calculi equipped with a tractable metatheory, will guide the design of a variety of current and future interactive programming tools, much as various lambda calculi have guided modern language designs. Our own research will apply these principles in the design of Hazel, an experimental live lab notebook programming environment designed for data science tasks. We plan to co-design the Hazel language with the editor so that we can explore concepts such as edit-time semantic conflict resolution mechanisms and mechanisms that allow library providers to install library-specific editor services. <s> BIB015 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> Modeling a student's knowledge state while she is solving exercises is a crucial stepping stone towards providing better personalized learning experiences at scale. This task, also referred to as "knowledge tracing", has been explored extensively on exercises where student submissions fall into a finite discrete solution space, e.g. a multiple-choice answer. However, we believe that rich information about a student's learning is captured within their responses to open-ended problems with unbounded solution spaces, such as programming exercises. In addition, sequential snapshots of a student's progress while she is solving a single exercise can provide valuable insights into her learning behavior. In this setting, creating representations for a student's knowledge state is a challenging task, but with recent advances in machine learning, there are more promising techniques to learn representations for complex entities. In our work, we feed the embedded program submissions into a recurrent neural network and train it on the task of predicting the student's success on the subsequent programming exercise. By training on this task, the model learns nuanced representations of a student's knowledge, and reliably predicts future student performance. <s> BIB016 </s> A Survey of Machine Learning for Big Code and Naturalness <s> New Domains <s> In most safety-critical domains the need for trace-ability is prescribed by certifying bodies. Trace links are generally created among requirements, design, source code, test cases and other artifacts; however, creating such links manually is time consuming and error prone. Automated solutions use information retrieval and machine learning techniques to generate trace links; however, current techniques fail to understand semantics of the software artifacts or to integrate domain knowledge into the tracing process and therefore tend to deliver imprecise and inaccurate results. In this paper, we present a solution that uses deep learning to incorporate requirements artifact semantics and domain knowledge into the tracing solution. We propose a tracing network architecture that utilizes Word Embedding and Recurrent Neural Network (RNN) models to generate trace links. Word embedding learns word vectors that represent knowledge of the domain corpus and RNN uses these word vectors to learn the sentence semantics of requirements artifacts. We trained 360 different configurations of the tracing network using existing trace links in the Positive Train Control domain and identified the Bidirectional Gated Recurrent Unit (BI-GRU) as the best model for the tracing task. BI-GRU significantly out-performed state-of-the-art tracing methods including the Vector Space Model and Latent Semantic Indexing. <s> BIB017
Here, we visit a number of domains to which machine learning has not yet been systematically applied and yet suffer from uncertainty problems that machine learning is particularly well suited to address, promising new advances. Debugging. Debugging is a common task for software engineers BIB011 . Debugging is like trying to find a needle in the haystack; a developer has to recognize relevant information from the deluge of available information. A multitude of tools exist in this area whose main goal is to visualize a program's state during its execution. Probabilistic models of source code could help developers, such as by filtering highly improbable program states. Statistical debugging models, such as the work of Zheng et al. BIB001 BIB003 and Liblit et al. BIB002 are indicative of the possibilities within this area. Further adding learning within debugging models may allow further advances in statistical debugging. However, progress in this area is impeded by the combination of lack of data at a large scale and the inherent difficulty of pattern recognition in very high-dimensional spaces. Defects4J [100]-a curated corpus of bugs-could further prove useful within machine learning for fault prediction. Furthermore, collecting and filtering execution traces to aid debugging is another challenge for which machine learning is well suited. Collection requires expensive instrumentation, which can introduce Heisenbugs, bugs masked by the overhead of the instrumentation added to localize them. Here the question is "Can machine learning identify probe points or reconstruct more complete traces frompartial traces?" Concerning filtering traces, machine learning may be able to find interesting locations, like the root cause of bugs. Future methods should also be able to generalize across different programs, or even different revisions of the same program, a difficult task for existing machine-learning methods. Traceability. Traceability is the study of links among software engineering artifacts. Examples include links that connect code to its specification, the specification to requirements, and fixes to bug reports. Developers can exploit these links to better understand and maintain their code. Usually, these links must be recovered. Information retrieval has dominated link recovery. The work of Guo et al. BIB017 and Le et al. BIB008 suggests that learning better (semantic) representations of artifacts can successfully, automatically solve important traceability problems. Two major obstacles impede progress: lack of data and a focus on generic text. Tracing discussions in email threads, online chat rooms (e.g., Slack), documents, and source code would be extremely useful, but no publicly available and annotated data exist. Additionally, to date, NLP research has mostly focused on modeling generic text (e.g., from newspapers); technical text in conversational environments (e.g., chatbots) has only begun to be researched. StackOverflow presents one such interesting target. Although there are hundreds of studies that extract useful artifacts (e.g., documentation) from StackOverflow, NLP methods-such as dependency parsing, co-reference analysis and other linguistic phenomena-have not been explored. Code Completion and Synthesis. Code completion and synthesis using machine learning are two heavily researched and interrelated areas. Despite this fact, to our knowledge, there has been no full-scale comparison between LM-based BIB012 BIB005 BIB006 and structured prediction-based autocompletion models BIB004 BIB009 . Although both types of systems target the same task, the lack of a wellaccepted benchmark, evaluation methodology, and metrics has lead to the absence of a quantitative comparison that highlights the strengths and weaknesses of each approach. This highlights the necessity of widely accepted, high-quality benchmarks, shared tasks, and evaluation metrics that can lead to comparable and measurable improvements to tasks of interest. NLP and computer vision follow such a paradigm with great success. BIB014 Omar et al. BIB015 discuss the challenges that arise from the fact that program editors usually deal with incomplete, partial programs. Although they discuss how formal semantics can extend to these cases, inherently any reasoning about partial code requires reasoning about the programmer's intent. Lu et al. [125] used information-retrieval methods for synthesizing code completions showing that simply retrieving snippets from "big code" can be useful when reasoning about code completion, even without a learnable probabilistic component. This suggests a fruitful area for probabilistic models of code that can assist editing tools when reasoning about incomplete code's semantics by modeling how code could be completed. Education. Software engineering education is one area that is already starting to be affected by this field. The work of Campbell et al. BIB007 and Bhatia and Singh BIB013 already provide an automated method for fixing syntax errors in student code, whereas Piech et al. BIB010 and Wang et al. BIB016 suggest advancements towards giving richer feedback to students. Achieving reasonable automation can help provide high-quality computer science education to many more students than is feasible today. However, there are important challenges associated with this area. This includes the availability of highly granular data where machine-learning systems can be trained, difficulty with embedding semantic features of code into machine-learning methods, and the hardness of creating models that can generalize to multiple and new tasks. Student coursework submissions are potentially a ripe application area for machine learning, because here we have available many programs, from different students, which are meant to perform the same tasks. An especially large amount of such data is available in Massive Open Online Courses. This opens exciting possibilities, such as providing granular and detailed feedback, and curriculum customization and other intelligent tutoring systems can significantly change computer science education. Assistive Tools. Probabilistic models have allowed computer systems to handle noisy inputs such as speech and handwritten text input. In the future, probabilistic models of source code may enable novel assistive IDEs, creating inclusive tools that improve on conventional methods of developercomputer interaction and provide inclusive coding experiences.