Neural program embeddings have shown much promise recently for a variety of program analysis tasks, including program synthesis, program repair, code completion, and fault localization. However, most existing program embeddings are based on syntactic features of programs, such as token sequences or abstract syntax trees. Unlike images and text, a program has well-deﬁned semantics that can be difﬁcult to capture by only considering its syntax (i.e. syntactically similar programs can exhibit vastly different run-time behavior), which makes syntax-based program embeddings fundamentally limited. We propose a novel semantic program embedding that is learned from program execution traces. Our key insight is that program states expressed as sequential tuples of live variable values not only capture program semantics more precisely, but also offer a more natural ﬁt for Recurrent Neural Networks to model. We evaluate different syntactic and semantic program embeddings on the task of classifying the types of errors that students make in their submissions to an introductory programming class and on the CodeHunt education platform. Our evaluation results show that the semantic program embeddings signiﬁcantly outperform the syntactic program embeddings based on token sequences and abstract syntax trees. In addition, we augment a search-based program repair system with predictions made from our semantic embedding and demonstrate signiﬁcantly improved search efﬁciency.
 Recent breakthroughs in deep learning techniques for computer vision and natural language processing have led to a growing interest in their applications in programming languages and software engineering. Several well-explored areas include program classification, similarity detection, program repair, and program synthesis. One of the key steps in using neural networks for such tasks is to design suitable program representations for the networks to exploit. Most existing approaches in the neural program analysis literature have used syntax-based program representations. BID6 proposed a convolutional neural network over abstract syntax trees (ASTs) as the program representation to classify programs based on their functionalities and detecting different sorting routines. DeepFix BID4 , SynFix BID1 , and sk p BID9 are recent neural program repair techniques for correcting errors in student programs for MOOC assignments, and they all represent programs as sequences of tokens. Even program synthesis techniques that generate programs as output, such as RobustFill BID3 , also adopt a token-based program representation for the output decoder. The only exception is BID8 , which introduces a novel perspective of representing programs using input-output pairs. However, such representations are too coarse-grained to accurately capture program properties -programs with the same input-output behavior may have very different syntactic characteristics. Consequently, the embeddings learned from input-output pairs are not precise enough for many program analysis tasks.Although these pioneering efforts have made significant contributions to bridge the gap between deep learning techniques and program analysis tasks, syntax-based program representations are fundamentally limited due to the enormous gap between program syntax (i.e. static expression) and Bubble Insertion [5,5,1,4,3] [5,5,1,4,3] [5,8,1,4,3] [5,8,1,4,3] [5, 1,1,4,3] [5,1,1,4,3] [5, 1,8,4,3] [5,1,8,4,3] [1, 1,8,4,3] [5,1,4,4,3] [ 1,5,8,4,3] [5,1,4,8,3] [1, 5,4,4,3] [5,1,4,3,3] [1, 5,4,8,3] [5,1,4,3,8] [1, 4, 4, 8, 3] [1, 1, 4, 3, 8] [1, 4, 5, 8, 3] [1, 5, 4, 3, 8] [ 1, 4, 5, 3, 3] [1, 4, 4, 3, 8] [ 1, 4, 5, 3, 8] [1, 4, 5, 3, 8] [ 1, 4, 3, 3, 8] [1, 4, 3, 3, 8] [ 1, 4, 3, 5, 8] [1,4,3,5,8] [1,3,3,5,8] [1,3,3,5,8] [1,3,4,5,8] [1, 3, 4, 5, 8] Figure 1: Bubble sort and insertion sort (code highlighted in shadow box are the only syntactic differences between the two algorithms). Their execution traces for the input vector A = [8, 5, 1, 4, 3] are displayed on the right, where, for brevity, only values for variable A are shown. semantics (i.e. dynamic execution). This gap can be illustrated as follows. First, when a program is executed at runtime, its statements are almost never interpreted in the order in which the corresponding token sequence is presented to the deep learning models (the only exception being straightline programs, i.e., ones without any control-flow statements). For example, a conditional statement only executes one branch each time, but its token sequence is expressed sequentially as multiple branches. Similarly, when iterating over a looping structure at runtime, it is unclear in which order any two tokens are executed when considering different loop iterations. Second, program dependency (i.e. data and control) is not exploited in token sequences and ASTs despite its essential role in defining program semantics. FIG0 shows an example using a simple max function. On line 8, the assignment statement means variable max val is data-dependent on item. In addition, the execution of this statement depends on the evaluation of the if condition on line 7, i.e., max val is also control-dependent on item as well as itself. Third, from a pure program analysis standpoint, the gap between program syntax and semantics is manifested in that similar program syntax may lead to vastly different program semantics. For example, consider the two sorting functions shown in Figure 1 . Both functions sort the array via two nested loops, compare the current element to its successor, and swap them if the order is incorrect. However, the two functions implement different algorithms, namely Bubble Sort and Insertion Sort. Therefore minor syntactic discrepancies can lead to significant semantic differences. This intrinsic weakness will be inherited by any deep learning technique that adopts a syntax-based program representation. We have evaluated our dynamic program embeddings in the context of automated program repair. In particular, we use the program embeddings to classify the type of mistakes students made to their programming assignments based on a set of common error patterns (described in the appendix). The dataset for the experiments consists of the programming submissions made to Module 2 assignment in Microsoft-DEV204.1X and two additional problems from the Microsoft CodeHunt platform. The results show that our dynamic embeddings significantly outperform syntax-based program embeddings, including those trained on token sequences and abstract syntax trees. In addition, we show that our dynamic embeddings can be leveraged to significantly improve the efficiency of a searchbased program corrector SARFGEN 1 BID13 ) (the algorithm is presented in the appendix). More importantly, we believe that our dynamic program embeddings can be useful for many other program analysis tasks, such as program synthesis, fault localization, and similarity detection.To summarize, the main contributions of this paper are: (1) we show the fundamental limitation of representing programs using syntax-level features; (2) we propose dynamic program embeddings learned from runtime execution traces to overcome key issues with syntactic program representations; (3) we evaluate our dynamic program embeddings for predicting common mistake patterns students make in program assignments, and results show that the dynamic program embeddings outperform state-of-the-art syntactic program embeddings; and (4) we show how the dynamic program embeddings can be utilized to improve an existing production program repair system. We have presented a new program embedding that learns program representations from runtime execution traces. We have used the new embeddings to predict error patterns that students make in their online programming submissions. Our evaluation shows that the dynamic program embeddings significantly outperform those learned via program syntax. We also demonstrate, via an additional application, that our dynamic program embeddings yield more than 10x speedups compared to an enumerative baseline for search-based program repair. Beyond neural program repair, we believe that our dynamic program embeddings can be fruitfully utilized for many other neural program analysis tasks such as program induction and synthesis. for Pc ∈ Pcs do // Generates the syntactic discrepencies w.r.t. each Pc 7 C(P , Pc) ← DiscrepenciesGeneration(P , Ps) // Executing P to extract the dynamic execution trace 8 T (P ) ← DynamicTraceExtraction(P ) // Prioritizing subsets of C(P , Pc) through pre-trained model 9 C subs (P , Pc) ← Prioritization(C(P , Pc), T (P ), M) 10 for C sub (P , Pc) ∈ C subs (P , Pc) do
A new way of learning semantic program embedding
{"src": "scitldr-AIC_train", "paper_id": "BJuWrGW0Z"}