Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Jinpa, Tenzin
Master of Science - MSc
University of British Columbia
An effective and efficient code representation is critical to the success of sequence-to-sequence deep neural network models for a variety of tasks in code understanding, such as code summarization and documentations, improving productivity, and reducing software development costs. Unlike the natural language, which is unstructured and noisy, programming codes are intrinsically structured, and the learning model can leverage this property of the code. A significant challenge is to find a sequence representation that captures the structural information in the program code and facilitates the training of the models. In this study, we propose to use the Prüfer sequence of the Abstract Syntax Tree (AST) of a computer program to design a sequential representation scheme that preserves the structural information in an AST. Our representation makes it possible to develop deep-learning models in which signals carried by lexical tokens in the training examples can be exploited automatically and selectively based on their syntactic role and importance. Unlike other recently-proposed approaches, our representation is concise and lossless in terms of the structural information of the AST. To test the efficacy of Prüfer-sequence-based representation, we designed a code summarization using a sequence-to-sequence learning model on real-world benchmark datasets. The results from the empirical studies show that Prüfer-sequence-based representation is indeed highly effective and efficient, outperforming significantly all the recently-proposed deep-learning models we used as the baseline models.
CODE REPRESENTATIONLEARNING WITH PRU¨FERSEQUENCESbyTenzin JinpaB. Tech, Guru Gobind Singh Indraprastha University, 2013M. Tech, Guru Gobind Singh Indraprastha University, 2015A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)October 2021© Tenzin Jinpa , 2021The following individuals certify that they have read, and recommend to the Collegeof Graduate Studies for acceptance, a thesis/dissertation entitled:CODE REPRESENTATION LEARNING WITH PRU¨FER SEQUENCESsubmitted by Tenzin Jinpa in partial fulfilment of the requirements of the degree ofMaster of ScienceYong Gao, Irving K. Barber Faculty of ScienceSupervisorPramjeet Gill, Irving K. Barber Faculty of ScienceSupervisory Committee MemberFatemeh Hendijani Fard, Irving K. Barber Faculty of ScienceSupervisory Committee MemberXiaoping Shi, Irving K. Barber Faculty of ScienceUniversity ExaminerWarren Hare, Irving K. Barber Faculty of ScienceNeutral ChairiiAbstractAn effective and efficient code representation is critical to the success ofsequence-to-sequence deep neural network models for a variety of tasks in codeunderstanding, such as code summarization and documentations, improvingproductivity, and reducing software development costs. Unlike the natural language,which is unstructured and noisy, programming codes are intrinsically structured, andthe learning model can leverage this property of the code. A significant challenge is tofind a sequence representation that captures the structural information in the programcode and facilitates the training of the models.In this study, we propose to use the Pru¨fer sequence of the Abstract Syntax Tree(AST) of a computer program to design a sequential representation scheme thatpreserves the structural information in an AST. Our representation makes it possibleto develop deep-learning models in which signals carried by lexical tokens in thetraining examples can be exploited automatically and selectively based on theirsyntactic role and importance. Unlike other recently-proposed approaches, ourrepresentation is concise and lossless in terms of the structural information of the AST.To test the efficacy of Pru¨fer-sequence-based representation, we designed a codesummarization using a sequence-to-sequence learning model on real-world benchmarkdatasets. The results from the empirical studies show that Pru¨fer-sequence-basedrepresentation is indeed highly effective and efficient, outperforming significantly allthe recently-proposed deep-learning models we used as the baseline models.iiiLay SummaryThe application of the deep learning models in Natural Language Processing (NLP)enabled us to solve many complex NLP tasks. The success of the deep learning modelin NLP inspired many researchers to apply deep learning in Software Engineering,specifically code representation learning. One key research area is how we represent acomputer code used as input to train the deep learning models in code representationlearning.In this thesis, we explore the idea of lossless linear encoding of the computer codeusing the Pru¨fer-Sequence of abstract syntax tree of a code, which helps the model tolearn the syntactic information of the code. We also provide a context of the code thatenabled the model to learn the lexical information of the code.To demonstrate the efficiency and the efficacy of our representation of the code, wedeveloped a Pru¨fer-Sequence based learning model for code summarization (attentionbased Encode Decoder model with dual encoder) and compared the results with otherbaseline models..ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Abstract Syntax Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1.1 Abstract Syntax Tree and Code Representation . . . . . . . . . . . 42.2 Linear Encoding Methods of the Code . . . . . . . . . . . . . . . . . . . . 62.2.1 Flat Sequence of Tokens . . . . . . . . . . . . . . . . . . . . . . . . 72.2.2 Classical Traversal Method . . . . . . . . . . . . . . . . . . . . . . 82.2.3 Structure Base Traversal Method . . . . . . . . . . . . . . . . . . . 82.2.4 Paths Between the Terminals Nodes . . . . . . . . . . . . . . . . . 102.3 Pru¨fer Sequence of Tree and its Properties . . . . . . . . . . . . . . . . . . 122.3.1 Generation of Pru¨fer Sequences . . . . . . . . . . . . . . . . . . . . 132.3.2 Tree Generation from the Pru¨fer Sequence . . . . . . . . . . . . . 142.4 Core Deep Learning Technique . . . . . . . . . . . . . . . . . . . . . . . . 152.4.1 Long Short Term Memory . . . . . . . . . . . . . . . . . . . . . . . 172.4.2 Gated Recurrent Unit . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.3 Attention Based Encoder-Decoder Model . . . . . . . . . . . . . . 202.5 Deep Learning for Code Comprehension . . . . . . . . . . . . . . . . . . . 232.5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24Chapter 3: Pru¨fer Sequence Generation . . . . . . . . . . . . . . . . . . 26vTABLE OF CONTENTS3.0.1 Pru¨fer Sequence Generation of a Code . . . . . . . . . . . . . . . . 263.0.2 Properties of the Pru¨fer sequence . . . . . . . . . . . . . . . . . . . 34Chapter 4: Pru¨fer-Sequence-Based Learning Model For CodeSummarization . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.0.1 Pru¨fer Sequence Encoder . . . . . . . . . . . . . . . . . . . . . . . 434.0.2 Context Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.0.3 Attention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.0.4 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.1.1 Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1.2 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.2.1 Performance over Source Code of Different Lengths . . . . . . . . 544.2.2 Flexibility of Pru¨fer Sequence . . . . . . . . . . . . . . . . . . . . 554.2.3 Efficiency of the Pru¨fer Sequence in encoding the AST of the code 564.2.4 Comment Generation Using Different AST RepresentationMethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57Chapter 5: Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Appendices 71Appenidx A : Abstract Syntax Tree Table Generation . . . . . . . . . . . 71Appenidx B : Pru¨fer-Sequence Generation . . . . . . . . . . . . . . . . . . 73Appenidx C: Context of Code Generation . . . . . . . . . . . . . . . . . . 76viList of TablesTable 4.1 Statistics of the Java Methods . . . . . . . . . . . . . . . . . . . . . 47Table 4.2 Statistics of the Java comments . . . . . . . . . . . . . . . . . . . . 47Table 4.3 Effectiveness of Models based on Machine Translation metrics forDataset-1 and value inside the bracket shows the performanceimprovements in percentage compare to the baseline models . . . . 52Table 4.4 Effectiveness of Models based on Machine Translation metrics ForDataset-2 and value inside the bracket shows the performanceimprovements in percentage compare to the baseline models . . . . 52Table 4.5 Flexibility of Pru¨fer sequence for Dataset-1 . . . . . . . . . . . . . 56Table 4.6 Statistics of the AST Representation Methods for Dataset-1 . . . . 56viiList of FiguresFigure 2.1 The Abstract Syntax Tree and Concrete Syntax Tree of theexpression 7 + (2 + 3) . . . . . . . . . . . . . . . . . . . . . . . . 5Figure 2.2 The Abstract Syntax Tree of the Code . . . . . . . . . . . . . . . 6Figure 2.3 The Abstract Syntax Tree of the Code . . . . . . . . . . . . . . . 7Figure 2.4 SBT and DFS generated Sequence . . . . . . . . . . . . . . . . . 9Figure 2.5 Paths Between the terminal Nodes of the AST . . . . . . . . . . 11Figure 2.6 Pru¨fer sequence Generation . . . . . . . . . . . . . . . . . . . . . 13Figure 2.7 Reconstruction of Tree from Pru¨fer Sequence . . . . . . . . . . . 15Figure 2.8 Recurrent Neural Network . . . . . . . . . . . . . . . . . . . . . . 17Figure 2.9 Long Short Term Memory . . . . . . . . . . . . . . . . . . . . . . 18Figure 2.10 Gated Recurrent Unit . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 2.11 Encoder Decoder Model . . . . . . . . . . . . . . . . . . . . . . . 21Figure 3.1 Pru¨fer sequence and context generation of a code . . . . . . . . . 27Figure 3.2 The Abstract Syntax Tree of the Code . . . . . . . . . . . . . . . 28Figure 3.3 Abstract Syntax Tree Table . . . . . . . . . . . . . . . . . . . . . 29Figure 3.4 Numerically labelled Tree structure for AST in Fig.4.2 . . . . . . 30Figure 3.5 Generate Syntactic Pru¨fer Sequence . . . . . . . . . . . . . . . . . 31Figure 3.6 Pru¨fer sequence of the AST . . . . . . . . . . . . . . . . . . . . . 37Figure 3.7 Context Generation of the Code . . . . . . . . . . . . . . . . . . . 38Figure 4.1 Pru¨fer Based Learning Model for Code Summarization Task . . . 42Figure 4.2 Distribution of Code Length . . . . . . . . . . . . . . . . . . . . . 45Figure 4.3 Distribution of Comment Length . . . . . . . . . . . . . . . . . . 46Figure 4.4 Frequency Distribution of Code Length . . . . . . . . . . . . . . . 54Figure 4.5 BLEU score for different method lengths . . . . . . . . . . . . . . 55Figure 4.6 Time required to train Pru¨fer Based Learning Model for 60 epochusing different AST representation. . . . . . . . . . . . . . . . . . 57viiiAcknowledgementsWith great pleasure, I would like to thank The University of British ColumbiaOkanagan for two years of support and for providing the opportunity of teachingundergraduate students as a Teaching Assistant. My journey in a master’s programwas enriching and satisfying, with opportunities to learn and expand my researchunderstanding and technical skills.I would like to thank Dr. Yong Gao for his constant support and mentorship forthe last two years. I had benefited immensely from his deep understanding of computerscience and research ideas, without which I would not be able to complete this work.Finally, I would like to thank my committee members for their support andunderstanding. I am grateful for all of your advice.ixDedicationFirst and foremost, I would like to thank my family for their unconditional love andsupport, which helped me overcome all the challenges of my life and fulfill my dreams.I also like to thank Tibetan Children Village (TCV) Dharamsala and the Dalai LamaTrust for supporting my undergraduate and graduate education. I would like to thankall my friends, faculty, and other people I’ve met during my master’s program at UBCOkanagan.I would like to dedicate this thesis to my mom, a constant source of inspiration andsupport throughout my life. Whatever I had achieved in my life is due to her sacrificesand hard work.xChapter 1IntroductionThe genesis of the natural language could be traced to the early human civilizationwith the ability of the human species to express an idea using pictures. The modernlanguages developed over centuries become more structured and diverse, enablinghumans to process the natural language to express complex ideas. However, the earlystages of natural language processing depend on manual annotation with little or noautomation limiting its applications. This changes with the evolution of moderntechnology, enabling us to process a massive quantity of information in a shortduration. The early work on Natural Language Processing (NLP) is inspired by thework of Alan Turing [Tur50] in 1950, which demonstrates that a machine could becapable of ”Thinking” through the Turing test and Hodgkin-Huxley model in 1952,which shows that the brain uses neurons in forming an electrical network. However,the progress on NLP in the following years remained stagnated, and by 1966, theNational Research Council (NRC) and Automatic Language Processing AdvisoryCommittee (ALPAC) initiated the first AI and NLP stoppage. The major paradigmshift started with developing deep learning models [TSK+20], and the availability ofhigh computing power results in an impressive performance on various NLP tasks.The evolution of NLP is broadly categorized into three phases, i.e., Symbolic NLP(the 1950s – early 1990s), Machine Learning NLP (1990s–2010s), and Neural NLP(present). The premise of the Symbolic NLP can be surmised by John Searle’s Chineseroom experiment: Given pre-defined rules, a machine can emulate the natural languageunderstanding by applying the rules to the data. The models based on the SymbolicNLP were constraints with pre-defined rules and domain knowledge requirements, thusfailing to produce significant results. In the case of the Machine Learning models, wetrain the model using the large corpus of text such that during the training, the modellearns the inherent association between the input and output text. Most of theclassical machine learning models required hand-crafted features from the corpus asinput for good performance, this constraint the models as it required domainknowledge and limited its applications to new tasks. The Neural NLP produces themost promising results in NLP tasks, it uses deep learning techniques such that itmaps the input text to a low dimensional continuous feature vector rendering therequirements of hand-crafted features. The versatility of the deep learning model isvalidated by its applications in various tasks such as1. Sentiment analysisIt analyzes the people’s sentiment in a text (e.g., tweets, customer reviews, andnews articles) and classifies them into different categories. These categories could1Chapter 1. Introductionbe binary (positive or negative labels) or multi-class problems (with multiplelabels). For example, [XMQ+19] uses the semantic information of the text asinput in the recurrent neural network with the Bi-LSTM model to classify textinto binary categories (positive and negative).2. Natural Language Inference (NLI)NLI model predicts whether the semantic meaning of one text can be inferred fromanother text. The model will have a parallel corpus of text such that each pairfrom the corpus is labeled as entailment, contradiction, and neutral. For example,[LSLW16] uses the Bi-LSTM to train the model to classify the pair of text intothree categories: entailment, contradiction, and neutral, with text tokens as input.3. Generative Question AnsweringWe use the deep learning models with limited success to generate natural languageresponses to the question based on the knowledge that the model was trained. Forinstance, [YJL+16] use the deep learning model were train with the parallel corpusof the question and answer such that the model will generate a natural languageresponse to a new question it encounters.4. Text SegmentationA number of the text segmentation problem were resolved by applying deeplearning techniques. For instance, [AA21] uses the deep learning model in theNamed Entity Recognition in the non-segmented text, while [WY18] uses thedeep learning model in segmenting the words in a non-segmented text.With the advancement of the software, the size of the code became significant andthe maintenance of software became expensive. Many researchers work on developingan automated tool to comprehend the code and reduced the software development cost.The use of deep learning techniques and related neural machine translation (NMT)models in code understanding has drawn much recent attention. It has been shownthat methods using NMT models can achieve a much better performance thantraditional Informational Retrieval (IR) techniques in tasks such as automated codesummarization [HIGH16, ZWZ+20] and program property prediction [AZLY18], thusimproving productivity [LVD06] and reducing software development costs [SHM+10].Also, unlike natural languages, which are unstructured and noisy, computer programsare highly structured. It is thus critical to encode as much as possible the structuralinformation in a sequence-to-sequence learning model and to take advantage of theencoded information in training.In this study, we propose to use the Pru¨fer sequence of the Abstract Syntax Tree(AST) of a computer program to design a sequential representation scheme thatpreserves the structural information in an AST. Our representation makes it possibleto develop deep-learning models in which signals carried by lexical tokens in thetraining examples can be exploited automatically and selectively based on their2Chapter 1. Introductionsyntactic role and importance. Unlike other recently-proposed approaches, ourrepresentation is concise and lossless due to the fact that an AST can be uniquelyreconstructed from its Pru¨fer sequence. Empirical studies on real-world benchmarkdatasets, using a sequence-to-sequence learning model we designed for codesummarization, showed that our Pru¨fer-sequence-based representation is indeed highlyeffective and efficient, and our model outperforms significantly all therecently-proposed deep-learning models used as the baselines in the experiments.Chapter 2 will discuss the background knowledge, i.e., we cover a detailed discussionon the current linear code representation methods and their limitations. We will discussthe pru¨fer sequence and its properties and covered the Recurrent Neural Networks (RNN)like Long Short-Term Memory (LSTM) and Gated Recurrent Units (GRU). We alsodiscussed the working of the attention-based sequence-to-sequence model.Chapter 3 presents our main idea to produce a lossless linear representation of ASTof code using the pru¨fer sequence. We explain the detail mechanism of generatingpru¨fer sequence from an AST and the context of the code from the pru¨fer sequence.Furthermore, we explain the various properties of our representation compared to otherrepresentation methods.In chapter 4, we discuss the application of our representation. While ourrepresentation is a programming language and task-independent, we focus itsapplication on code summarization in the current work to study and demonstrate itseffectiveness and efficiency in code representation learning. We discuss the results fromthe series of empirical studies on widely used benchmark datasets, i.e., a) parallelcorpus of Java code and comment by Hu [HLX+20] and b) CodeXGlue dataset(code-to-text) by Microsoft [HLX+20].3Chapter 2Background2.1 Abstract Syntax TreeThe Abstract Syntax Tree (AST) evolution is rooted in the compiler design toprocess the computer code. We use syntax-directed interpreters for simple instructions,which directly execute the code without building the intermediate representation, andfor complex code from a high-level language like java or Pascal required intermediaterepresentation. A tree data structure is used to represent the intermediate coderepresentation for the interpreter in the compiler. The parser will generate theintermediate representation, and the interpreter uses this to interpret the code.The Abstract Syntax Tree (AST) is an intermediate representation of the code in atree data structure such that not every detail of the code is represented in the AST. Themotivation of the AST is realized by comparing it to the Concrete Syntax Tree (CST).The CST is a syntax structure of a programming language constructed according togrammar definition. Fig. 2.1 shows the AST and CST for the instruction 7 + (2 + 3).We see that AST representation (Fig. 2.1) is more concise than the CST while preservingthe essential information of the code.We can define the Abstract Syntax Tree (AST) as the tree data structure of the codeconstructs according to the grammar definition of the language and provide an abstractrepresentation (i.e., not every detail of the code is represented in the structure).An AST will have the following properties1. An AST can be edited or enhanced by adding information to the nodes.2. An AST will not include all elements of the code, i.e., it skips the nonessentialelement of the code.3. In the compiler design, the AST contains more information about the program asthe compiler will analyze the AST in consecutive stages.2.1.1 Abstract Syntax Tree and Code RepresentationIn our AST, the leaves (or terminal nodes) are labeled by tokens that containuser-defined values or reference types such as variable names, whereas internal nodes(or non-terminal nodes) are labeled by tokens that summarize the purpose of codeblocks such as conditions, loops, and other flow-control statements. We note that atoken labeling an internal node does not have to be from the source code orspecification of the particular programming language. By slightly abusing the notion,42.1. Abstract Syntax TreeFigure 2.1: The Abstract Syntax Tree and Concrete Syntax Tree of the expression7 + (2 + 3)we call a token labeling a leave node a “lexical token” as it contains program-specificinformation in the source code and call a token labeling a non-terminal node a“syntactic token” as it contains generic information about the structure and thepurpose of a code block. Shown in Fig.2.2 is a function in Java and its AST where thetoken set {Override, Int, String, mergeErrorIntoOutput, Boolean, Commands} are usedto label the terminal nodes and the token set {BasicType, FormalParameter,MethodInvocation, ReturnStatement, ClassCreator, ReferenceType} are used in labelthe internal nodes.In a sequence-to-sequence model for code representation learning, tokens (or theirword embedding) from the source code of a computer program have to be represented as alinear sequence and are used as the input of the model. As has been shown by [HLX+18a]and [ABLY19], a linear sequence representation that makes use of structural informationencoded in the AST has a great advantage over a simple flat sequence representationwhere tokens appear in the same order as they appear in the source code [IKCZ16]. SinceAST is inherently abstract and its structure depend on the implementation, we followthe AST implementation provided by the Hu [HLX+18a] and code can be accessed by52.2. Linear Encoding Methods of the CodeFigure 2.2: The Abstract Syntax Tree of the CodeGithub link12.2 Linear Encoding Methods of the CodeIn recent years significant milestones were achieved in code representation learningusing the deep learning models. One of the critical components of a deep learning modelis the representation of the code (which is input into the model). To train a sequence-to-sequence model for code representation learning, we need to pass the tokens of the codein a linear sequence. We can treat the code as a flat sequence of code or use the abstractsyntax tree to capture the syntactic and lexical information of the code. In the followingsubsections, we will discuss the four standard linear representations of the code.1https// : github.com/xing − hu/EMSE −DeepCom/blob/master/data− utils/get− ast.py62.2. Linear Encoding Methods of the CodeFigure 2.3: The Abstract Syntax Tree of the Code2.2.1 Flat Sequence of TokensMany code representation learning models with deep learning were proposed withthe code tokens as input to the model. Like Iyers [IKCZ16] uses the actual code as inputto the deep learning model to generate summaries to the code. For example, the javamethod in Fig 2.3 is represented as< public int run Command ( boolean merge Error Into Output , String commands) throws IOException , Interrupted Exception return runCommand ( merge Error IntoOutput , new Array List < String > ( Arrays . asList ( commands ) ) ) ;>This representation is straightforward, and by sending the program’s actual code asinput, the model will learn the lexical information. The drawbacks of this representationare that sending the code as a flat sequence of tokens fails to capture the syntacticinformation of the code, and performance relies on the type of tokens used for the72.2. Linear Encoding Methods of the Codetraining and testing, as wide deviations between the two ( i.e., training and testingcorpus) may degrade the performance.To overcome the limitation of the above representation, we need to represent the codein a data structure that can preserve the code’s syntactic information. We represent thecode as the abstract syntax tree to preserve the syntactic information of the code andgenerate the linear representation of the AST (Fig. 2.3), which is input to the deeplearning model.2.2.2 Classical Traversal MethodTo preserve the syntactic information of the code, we represent the code as anabstract syntax tree. To use the abstract syntax tree with the deep learning modelrequires a linear representation of the abstract syntax tree. We can use the classicaltraversal methods like Breadth-First Search (BFS) or Depth First Search (DFS). Thismethod will generate a linear representation of the AST. For example, DFS and BFSof the AST (Fig.2.3) is< Annotation BasicType BasicType FormalParameter ReferenceTypeFormalParameter MemberReference MethodInvocation ReferenceType TypeArgumentMemberReference MethodInvocation ClassCreator ReturnStatementMethodDeclaration >< MethodDeclaration Annotation BasicType FormalParameter FormalParameterReturnStatement BasicType ReferenceType MethodInvocation ClassCreatorMemberReference ReferenceType MethodInvocation ArgumentType MemberReferenceReferenceType >The classical traversal methods generate a linear representation of the AST, whichis input to the deep learning model. However, this representation of the abstractsyntax tree fails to preserve the structural information of the code as suchrepresentation is lossless representation. This representation is lossy since there is noone-to-one correspondence between the tree and the sequence generated by theclassical traversal methods (BFS or DFS) since we cannot reconstruct the tree from thesequence generated by the classical traversal methods. Another fundamental limitationis that sequences generated by the classical traversal methods are not unique sincesequences generated by the classical traversal methods for two different codes maygenerate identical syntactic sequences. This result in one syntactic sequence (input tothe neural network) mapping to two different comments (output to the neuralnetwork), thus confusing the neural network.2.2.3 Structure Base Traversal MethodOne of the modern methods of linear representation of the abstract syntax tree isthe Structure Base Traversal (SBT) method by Hu [HLX+18a]. The steps in the SBTsequence generation are defined in Algorithm-1. Hu [HLX+18a] uses the SBT generatedsequence to learn the syntactic information of the code to generate the comments for82.2. Linear Encoding Methods of the CodeFigure 2.4: SBT and DFS generated Sequencethe java code. The SBT generated sequence of a tree uses the parenthesis to capture thesub-tree information of the code. Also, the SBT generated sequence of a tree producedsimilar syntactic tokens sequences as that of a DFS generated sequence if we printed allthe visited nodes of the tree in the DFS traversal method (Fig. 2.4).Algorithm-1 shows that the SBT method will generate the syntactic token each timeit visited a node in the tree. For each node, we have a two-bracket, i.e., the openingbracket ”(”, token itself n′, closing bracket ”)”, For a tree with n nodes, the maximumlength of the SBT generated sequence is of the order of 3 ∗ n. For example, the lengthof the SBT generated sequence of the AST in Fig. 2.3 is 62 tokens.< ( MethodDeclaration ( Annotation ) Annotation ( BasicType ) BasicType (FormalParameter ( BasicType ) BasicType ) FormalParameter ( FormalParameter (ReferenceType ) ReferenceType ) FormalParameter ( ReturnStatement (MethodInvocation ( MemberReference ) MemberReference ( ClassCreator (ReferenceType ( TypeArgument ( ReferenceType ) ReferenceType ) TypeArgument )ReferenceType ( MethodInvocation ( MemberReference ) MemberReference )MethodInvocation ) ClassCreator ) MethodInvocation ) ReturnStatement )92.2. Linear Encoding Methods of the CodeAlgorithm 1: Structure-Based Traversal1 procedure SBT(r) B Traverse a tree from root2 seq ← Ø B seq is the sequence of a tree after traversal3 if !r.hasChild then4 seq ← (r)r B Add brackets for terminal nodes5 else6 seq ← (r B Add left bracket for non-terminal nodes7 for c in childs do8 seq ← seq + SBT(c)9 seq ← seq + ) r B Add right bracket for non-terminal nodes after traversingall their children10 return seqMethodDeclaration >The SBT generated sequence of an AST is a lossy representation as we cannotreconstruct the tree from the sequence since there is no one-to-one correspondencebetween the SBT generated sequence and the tree. The lossy nature of the SBTgenerated sequence implied that it fails to preserve the syntactic information of thecode.2.2.4 Paths Between the Terminals NodesAnother modern approach of the linear representation of the AST is proposed byAlon [ABLY19], here we represent the AST as the composition of paths between thepairs of terminal nodes in the AST. In this method, a code snippet C is representedas the paths between the K pairs of terminal nodes of the AST. During decoding, theattention mechanism will choose the most relevant paths to generate the model’s output.The sequence generated from this method is a lossy encoding as we cannot reproducea tree from a sequence of paths between the terminal nodes of the AST as there is noone-to-one correspondence between the sequence and the tree. Fig 2.5 show the pathsbetween the four pairs of terminal nodes of AST of Java code (the four different colorsof edges represent paths) from Fig.2.3< Override runCommand return runCommand mergeErrorIntoOutput ,mergeErrorIntoOutput runCommand return ArrayList None String , String None102.2. Linear Encoding Methods of the CodeFigure 2.5: Four Paths Between the terminal Nodes of the AST represented by the fourdifferent coloured edgesArrayList return Arrays.asList commands , mergeErrorIntoOutput runCommandreturn ArrayList Arrays.asList commands , boolean mergeErrorIntoOutputrunCommand commands String >Alon [ABLY19] representation uses the lexical tokens instead of the syntactictokens of the AST to generate paths between the terminal nodes. The efficacy of suchrepresentation heavily relies on the identifiers in the dataset as any significantdeviation of identifiers in the code may impact the model’s performance. Furthermore,another limitation of Alon [ABLY19] representation is that it is a lossy encoding of anAST of code as we cannot reconstruct the AST from the paths between the terminalnodes proposed by Alon [ABLY19]; thus model losses certain structural information ofthe code during training.112.3. Pru¨fer Sequence of Tree and its Properties2.3 Pru¨fer Sequence of Tree and its PropertiesThe previous section shows that an effective and efficient linear representation ofthe AST needs to be a lossless representation. In this section, we will discuss a uniquerepresentation called Pru¨fer sequence, which is a lossless representation of a tree. Wewill examine the properties and the generation of the Pru¨fer sequence.The Pru¨fer sequence is proposed by Heinz Pru¨fer( [Pru¨18, Wes00]) while solvingthe famous proof of Caley’s formula for trees. The proof is based on the one-to-onecorrespondence between the set of labeled trees and the set of such sequences. ThePru¨fer sequence is a unique and lossless encoding of a tree such that we can uniquelyreconstruct the tree from the sequence. Formally, We can define the Pru¨fer sequence asThe Pru¨fer sequence of a tree T with labelled node from 0 to n is asequence of nodes of size n − 2 such that each node {a1, a2, a3, ........an−1} islabelled 0 to n (where the repetition of the label is allowed).Lemma 2.1. For a tree T with n nodes Pru¨fer sequence will have the length of sizen− 2Let T be a tree with n node and m edgesTotal number of edges in an undirected tree m = n− 1Length of the Pru¨fer sequence =∑n∈N(T )(deg(n)− 1)=∑n∈N(T ) deg(n) −∑n∈N(T ) 1= 2 m − n= 2 (n− 1)− n= n− 2Lemma 2.2. There are nn−2 Pru¨fer sequence of length n− 2By definition there are n ways to choose each element of a Pru¨fer sequence oflength n− 2. Since there are n− 2 elements to be determined, so in total, we have nn−2ways to choose the whole sequence.For example let say we have Pru¨fer sequence of length 2 then there are 44−2 = 16sequences of length n− 2 i.e. {(1, 1), (1, 2), (1, 3)..........(4, 3), (4, 4)}Lemma 2.3. For a tree T with n nodes, there is a one-to-one correspondence betweenPru¨fer sequence of length n− 2 and the Tree T122.3. Pru¨fer Sequence of Tree and its PropertiesTo prove that there exists a one to one correspondence between Pru¨fer sequence oflength n − 2 and the Tree T , we need a deterministic algorithm ( Algorithm-3 ) thattakes a Pru¨fer sequence and reconstruct a tree TIn the following section, we will discuss the Pru¨fer sequences generation steps froma tree T with labels {0 1 2 3.....n} (Algorithm 2) . And a deterministic algorithm(Algorithm-3) to reconstruct the tree from the pru¨fer sequences.2.3.1 Generation of Pru¨fer SequencesFigure 2.6: Pru¨fer sequence GenerationFig. 2.6 demonstrates the process of Pru¨fer sequence generation from a tree labeledfrom 0 to 7 node. Initially the Pru¨fer sequence (represented by P is empty) . Removethe terminal node 1 and include the node 0 in Pru¨fer sequence so P = {0}. Now removethe terminal node 4 and add the node 2 to Pru¨fer sequence so P = {0 2}. Next removethe terminal node 2 and add 0 to Pru¨fer sequence so P = {0 2 0}. Now remove node132.3. Pru¨fer Sequence of Tree and its PropertiesAlgorithm 2: Pru¨fer sequence generation from tree TLet us consider a Tree T with N nodes such that tree is label as {0, 1, 2, ...N}Step 1 Removed the smallest terminal node x from the tree TStep 2 Add node y connected to x as the next node in the pru¨fer sequenceStep 3 Repeat Step 2 and 3 until only two nodes is left in the tree T0 and add 3 to Pru¨fer sequence so P = {0 2 0 3}. Next node 3 is removed and node 5is added to Pru¨fer sequence so P = {0 2 0 3 5}. Now remove the terminal node 6 andadd 5 to Pru¨fer sequence so P = {0 2 0 3 5 5}. We stop the process as tree has onlytwo nodes and the final Pru¨fer sequence isP = {0 2 0 3 5 5}2.3.2 Tree Generation from the Pru¨fer SequencePru¨fer sequence inherently possesses a unique property that it is a lossless encodingof the tree. This implied that the Pru¨fer sequence preserved the structural information ofthe tree such that we can reconstruct the tree from the given Pru¨fer sequence. Algorithm-3 show the steps in reproducing a tree from a given Pru¨fer sequence S such that eachelement in the Pru¨fer sequence can take 1, 2, 3....n labels.For example Fig. 2.7 demonstrate the tree generation from the initial Pru¨fer sequenceP = {0 2 0 3 5 5}. Here P represent the Pru¨fer sequence and L is the set of all possiblesequence labels.Find the smallest node in L, i.e., 1 such that 1 is not present in the Pru¨fer sequenceP . Remove the node 1 and leading node 0 in Pru¨fer sequence from the set L andsequence P respectively. Join the node 1 and 0. Now remove the node 4 (result from thefind function in set L) from the set L and node 2 (leading node in the sequence) fromsequence P . Join node 4 and 2. Next, remove the node 2 (result from the find functionin set L) from the set L and node 0 (leading node in the sequence) from sequence P .Join the node 0 and 2.Next, remove the node 0 (result from the find function in set L)from the set L and node 3 (leading node in the sequence) from sequence P . Join thenode 0 and 3. Next, remove the node 3 (result from the find function in set L) fromthe set L and node 5 (leading node in the sequence) from sequence P . Join node 3 and5. Next, remove the node 6 (result from the find function in set L) from the set L andnode 5 (leading node in the sequence) from sequence S. Join the node 6 and 5. At thisstage, we are left with two nodes in L, i.e., node 5 and node 6 and no nodes in Pru¨fersequence P . Remove the nodes 5 and 6 from L and join the node 5 and 6.142.4. Core Deep Learning TechniqueFigure 2.7: Reconstruction of Tree from Pru¨fer Sequence2.4 Core Deep Learning TechniqueA Recurrent Neural Network (RNN) is a class of neural networks where the output ofthe previous node is input to the next node and performs well for tasks having sequentialinformation. For example, RNN models design weather forecasting (time-series data) andtext sentiment classification (sequence of natural language words). The RNN is called“recurrent” as every node in the RNN performs the same task with output depends onthe previous computations. In principle, an RNN model can have any length of inputand can preserve the long-term dependencies. For example, Fig. 2.8 shows the vanillaarchitecture of an RNN model such that x1 to xn represents the model’s input. AndU, V, and W are the weight of the model. For each node xt at time step t in RNN,multiply the input xt with weight wx and hidden state ht−1 with wh and take the sum ofthe products and add a bise (i.e. b). Apply the sigmoid function on the sum, and outputis the node’s current hidden state ht. To generate the output yt, take the product of the152.4. Core Deep Learning TechniqueAlgorithm 3: Reconstruction of Tree from the pru¨fer sequenceLet us consider a pru¨fer sequence S of length n-2 and such that each element aiin the pru¨fer sequence can take any label from {1, 2, 3, .....n}P = {a1, a2, a3, .....an}L = {1, 2, 3............n}Step 1 Find the smallest value x in set L such that x is not in Sequence PFind(x ∈ L : x 6∈ S)Step 2 Join the node label x and leading node ai in the sequence PStep 3 Delete node x in L and leading node ai in sequence PP = {a1, a2, a3, .....an} − aiL = {1, 2, 3............n} − xStep 4 Repeat the step 1 to 3 until only two elements is left in the set LStep 5 Join the last two elementht and V and add bise c. Apply the output function like the softmax function.ht = σ(Uxi +Wht−1 + b)yt = O(V ht + c)where for each each input x, we defined a sigmoid function asσ(x) =11 + e−xsuch that the output of the sigmoid function is between 0 and 1. The output functionO is a softmax function and we defined the softmax function asO(x)i =exi∑Kj=1 exjwhere softmax function map a vector of real values to the probability vector of samedimension such that the sum of the probability vector value is 1.We use backward propagation to update the weights of the network. In general, RNNcan preserve the long-term dependencies to have any length input series, but in practice,162.4. Core Deep Learning TechniqueFigure 2.8: Recurrent Neural Networkit loses its long-term dependencies due to the vanishing or exploding gradient problem.To resolved the vanishing gradient problem in the RNN models and thus preserved thelong-term dependencies, many variants of the RNN were proposed, like Long Short TermMemory (LSTM) by [HS97] or Gated Recurrent Unit (GRU) by [CGCB14].2.4.1 Long Short Term MemoryIn theory, any Recurrent Neural Network (RNN) can preserve long-termdependencies. However, in practice, due to the vanishing or exploding gradientproblem, an RNN cannot preserve the long-term dependencies. This conundrum wasresolved by [HS97] proposing a new model called LSTM (Long Short Term Memory),which prevents the vanishing gradient, thus preserving the long-term dependencies.The central idea of an LSTM is the memory cell, which preserved the states for a longtime using the number of gates, i.e., Forget gate, Input gate, and Output gate.Forget GateThis gate helps us to identifies the values in the cell state Ct−1, which could beforgotten. This is achieved by passing the input value xt and hidden state ht−1 to asigmoid function, which generates value from 0 to 1 for each of the cell state Ct−1. Forinstance, any value in the cell state whose sigmoid value is 0 could be forgotten.172.4. Core Deep Learning TechniqueFigure 2.9: Long Short Term Memory [Phi20]ft = σ(Wf ∗ [ht−1, xt] + bf )Input GateThe input gate helps to decide what new information needs to be kept in the cellstate. For this, the input is passed through the sigmoid layer, which decides what valueto be updated, and then the tanh layer (it is also like logistic sigmoid with range of thetanh function between -1 to 1) creates a vector of new candidate values,Cˆt. Finally, theprevious cell state Ct is updated using Cˆt.it = σ(Wi ∗ [ht−1, xt] + bi)Cˆt = tanh(Wc ∗ [ht−1, xt] + bc)Ct = ft ∗ Ct−1 + it ∗ CˆtOutput GateThis gate decides what information needs to go out of the cell. Initially, a sigmoidlayer will decide what information needs to go out, and then a new updated cell stateCt passes through the tanh function multiplied by the sigmoid layer’s output, ensuringthat only those value that we have decided goes to the output.182.4. Core Deep Learning TechniqueOt = σ(WO ∗ [ht−1, xt] + bo)ht = Ot ∗ tanh(Ct)2.4.2 Gated Recurrent UnitFigure 2.10: Gated Recurrent Unit [And19]In this subsection, we will discuss another recurrent neural network called GatedRecurrent Unit (GRU) proposed by [CGCB14] that helps prevent vanishing gradientor exploding gradient problems in RNN models. The GRU has a structural similaritywith that of the LSTM as it uses gates to avoid the gradient problem, i.e., Update Gateand Reset Gate deciding what information should be passed to the output. The GRUis computationally less expensive than the LSTM as it requires fewer gates than theLSTM.Update GateThe update gate helps the model decide how much information from the past (i.e.,from previous time steps) needs to be passed to the future. we calculate the update gatezt at time step t aszt = σ(Wzxt + Uzht−1)192.4. Core Deep Learning Techniquewhere xt is the input to the network unit at time step t and is multiplied by weightWz and the ht−1 is the hidden state (from the previous state) and is multiplied by theweight Uz. We summed the two products and applied a sigmoid function, ensuring thatthe output of the zt is between 0 and 1.Reset GateThe reset gate will decide how much information from the past needs to be forgotten.The functionality of the reset gate is similar to that of the forget gate of the LSTM. Foran input xt at timestep t, rt is computed asrt = σ(Wrxt + Urht−1)The formula for the forget gate is identical to that of the update gate as we appliedthe sigmoid function on the summed of the product of xt and hidden state ht−1 withtheir respective weights. The difference between the update gate and the reset gate isits weight and usage.The reset gate is used to generate a temporary memory content h‘t, which holds therelevant information from the past. We calculate the h‘t ash‘t = tanh(Whxt + Uh(rt ht−1))multiply the input xt with Wh and element-wise product of rt and ht−1, whichdetermine what needs to be removed from the previous time step, with Uh. Take thesum of the product and apply a nonlinear activation function tanh on it.Update gate help to calculate the ht, which holds the current unit t information,and this information is passed to the next unit in RNN. Update gate decides whatinformation from the previous state ht−1 and h‘t need to be kept. The ht is calculated asht = zt h′t + ((1− zt) ht−1)We apply the element-wise multiplication of (1− zt) and ht−1 and (zt) and h′t. Afterthe multiplication, we add the results. Thus ensuring that we only get the relevantinformation, for instance, let say if zt is close to 1, then 1 − zt will be close to zero,ensuring that most information came from the zt.2.4.3 Attention Based Encoder-Decoder ModelThe traditional Deep Neural Networks (DNN) are powerful models used in speechand image recognition with excellent performance. However, such a model required largelabeled datasets to encode inputs and outputs with vectors of fixed dimensionality. Thesemodels cannot be used to map sequences to sequences as we would encode our input toa fixed-length vector using a technique like Word2Vec. In such encoding, the order ofthe words is not preserved; so when we feed our vector to model, it fails to recognize theorder of the words, thus losing important information about the input. This problem wasresolved by [SVL14], which proposed an encoder-decoder sequence-to-sequence model.202.4. Core Deep Learning TechniqueFigure 2.11: Encoder Decoder Model [Kos19]In the following subsection, we describe the working of the encoder-decoder model andits limitations, which encourages the development of an attention based encoder-decodermodel.An encoder-decoder model at a high level can be summarised with two blocks, i.e.,an encoder block and a decoder block connected by a fixed-length context vector, whichrepresents a summary of the input sequence.EncoderAn encoder is responsible for processing each input token such that it encodes theentire input sequence into a fixed-length context vector. The final hidden state of theencoder encapsulates (in theory) all the input information and feeds this as input to thedecoder. The encoder part could be an LSTM or GRU, and the output at each timestepof the encoder is discarded. Formally for an input sequence (x1. . . xn), the encoder readsthe input sequence and encode them, here the ht is the hidden state of the encoder attime step t and c is the context vector. Here RNN could be a LSTM or a GRU while c isa vector generated from the sequence of the hidden states and q is a nonlinear function.ht = RNN(ht−1, xt)c = q(h1, ....hn)212.4. Core Deep Learning TechniqueDecoderThe final hidden state of the encoder is passed to the decoder as its initial input statecalled the context vector. With the help of the context vector c and all the previouspredicted words < y1, ...., yt−1 >, the decoder tries to predict the model’s output ytatthat timestep t.p(y) =n∏t=1p(yt|y1, ..., yt−1, c)where y = (y1, ...yt) and each conditional probability is modeled asp(yt|y1, ..., yt−1, c) = g(yt−1, st, c)where g is a nonlinear function that compute the yt and st is the hidden state of thedecoder.Unlike the encoder, the decoder training and the testing have different working. Weadd < start > and < end > tokens at the beginning and the end of the input fed to thedecoder, indicating the start and the end of the sentence. During the training, we feedthe actual output yt−1 tokens from the previous time-step as input to the model at time-step t (feeding the actual input instead to predicted is called the “Teacher Forcing”).The output of the decoder at time-step t (y′t) is the highest probability distributionover the entire vocabulary in the output dataset computed by the Softmax activationfunction. Finally, losses are calculated for each time step using the categorical cross-entropy loss function between the predicted (y′t) and actual output (yt). The errorsare then backpropagated through time to update the parameters of the model. Duringthe testing, we will feed the predicted output from the previous time-step t − 1 to thecurrent time step t to generate the current output prediction while the rest of the workingremains the same.AttentionIn an Encoder-Decoder model, final hidden state (which encoded all the inputsequence information) will act as an initial input to the decoder. However, encoding allthe input to a single vector has some drawbacks. Firstly, when an encoder is forced toencode all the information into a single vector, it may forget some of the encodedinformation. Secondly, during the decoding, the decoder will treat every encodedinformation with equal importance and focus on the entire context vector c during thedecoding at time step t, which is inefficient as only a subset of encoded information isrelevant at time step t of decoding.The attention model by [BCB15] proposed that at each decoder step, the decoderwill decide which part of the input is more relevant. This is determined by designing222.5. Deep Learning for Code Comprehensiona decoder that learns to align and translate jointly. Each time the model generates anoutput word, it searches for a set of positions in source sentences where the most relevantinformation is concentrated. The model then predicts output based on the context vectorassociated with the source positions and the previously generated outputs. We definethe conditional probability for decoder as:p(yt|y1, ..., yt−1, X) = g(yt−1, st, ct)where st is the hidden state at time-step t and computed as :st = f(st−1, yt−1, ct)here the probability is conditioned over distinct context vector ct for each target wordyt. The context vector ct is the weighted sum of the annotation of ht(encoded by theencoder) and we compute the context ct asc(t) =m∑k=1αkthkThe weight αkt of each annotation hk is computed by a softmax function asαkt =exp(ekt)∑nl=1 exp(elt)whereekt = a(st−1, hk)where a is the alignment model which scores how much a input around position k andthe output at position t match. This alignment model depend on the decoder hiddenstate st−1 and k − th annotation hk of the input sequence.2.5 Deep Learning for Code ComprehensionIn the past few decades, rapid technological growth resulted in significant codedocumentation and the high cost of its maintenance. For example, according tostudy [XBL+18], developers spend around 59% of their time in program comprehensionin a software development life cycle. This results in the need to automate the programcomprehension to reduce the software development cost and increase productivity.232.5. Deep Learning for Code ComprehensionEarly approaches to program comprehension are grouped into manually crafted codegeneration or information retrieval (IR). For instance, Moreno [MAS+13] uses theheuristic and stereotyped to select the information which will be included in thecomments generated for the Java class. Haiduc [HAM10] uses the IR approaches togenerate summaries for classes and methods. Though promising, IR approaches such asVector Space Model (VSM) and Latent Semantic Indexing (LSI) have two significantlimitations: firstly, when the identifiers and methods are poorly named, they fail toextract accurate keywords to identify the code snippet. Secondly, they rely on thedegree of the similarity of code snippets and whether such code snippets can beretrieved.The recent year saw much attention in applying deep learning techniques andrelated neural machine translation (NMT) models in code representation learning. Forexample the use of NMT models in tasks such as code summarization[HIGH16, LJM19, ZWZ+20] and program property prediction [AZLY18] providebetter performance than the traditional Information Retrieval (IR) techniques thusimproving productivity [KMCA06, LVD06] and reducing software development costs[SHM+10, XBL+18]. Unlike natural languages like English, which are highlyunstructured and noisy, program codes are highly structured. To take advantage ofthis intrinsic property of the code and enhance the model’s performance, it is criticalthat we encode as much as possible the structural information of the code in thesequence-to-sequence learning model.Several methods have been proposed to incorporate the structural information inthe Abstract Syntax Tree (AST) of a computer program in a sequence-to-sequencemodel. For example, the structure Based Traversal (SBT) method proposed byHu [HLX+18a], where the sequence is generated by depth-first search traversal of theAST and augmented by the parentheses pairs to retain the sub-tree information. Also,Alon [AZLY18] proposed the used of the paths between pairs of terminal nodes in theAST to represent the program code. While these methods are effective compared tothe most straightforward representation, the choices of the traversal method and theordering of the tokens appear to be arbitrary.2.5.1 Related WorkThe use of deep learning models to learn a code representation has attracted muchrecent attention. Iyer [IKCZ16] showed that the attention-based sequence to sequencemodel provides better results in code representation learning than the classicalInformation Retrieval (IR) methods. Many successful deep learning models weredeveloped in recent years for various tasks such as codesummarization [WZY+18, HLWM20, ACRC20], code generation [BGB+17], and coderetrieval [ATGW15].Several approaches have been investigated to making use of syntactic and structuralinformation, explicitly or implicitly, in representation learning from the source code ofcomputer programs. Rayche [RBVK16] used the relations in the abstract syntax tree asa feature for training the model, and Bielik [BRV16], and Raychev [RBV16] used the242.5. Deep Learning for Code Comprehensionpaths in an AST for identifying the context node. Hu [HLX+18a] proposed a Structure-Based Traversal (SBT) method to represent the AST for the code summarization task.Hu [HLX+20] used the tokens of code and the SBT generated sequence as an input to themodel. SBT captures the code’s structural information, while the code tokens will helpin learning the code’s lexical information. On close inspection of the SBT sequence, wecan observe the structural similarity between the SBT and depth-first search traversalmethod. Alon [ABLY19] used the paths between the AST’s terminal nodes for codesummarization and code captioning. The main idea was to represent the code snippetC with paths between k pairs of terminal nodes. A new set of paths are sampled duringevery training iteration to avoid bias. In addition to these efforts of directly usingthe structural information in the ASTs in a sequence-to-sequence model, [ACRC20]explored the possibility of exploiting structural information implicitly with a transformermodel enhanced by pairwise semantic relationships of tokens in the model’s attentionmechanism. A significant downside of a transformer-based approach is the increase inmodel complexity (quadratic in the code length) and thus the sample complexity andthe computational complexity.Another approach in code representation learning is the tree-based or graph-basedlearning methods of the source code. For example, Tree-Based Convolutional NeuralNetwork (TBCNN) by [ZWZ+19] is a convolutional-based supervised learning modelsuch as source code classification using the AST of the code. It uses the bottom-up(i.e., from leaf to root ) encoding of the tree such that it incorporates some globalinformation and improves its localness. Similarly, Tree-based Long Short-TermMemory models (Tree-LSTM) like Child-Sum Tree-LSTM [TSM15] uses the recursiveencoding of the current inputs with its children states to update the state across thetree. Alexander [LHWM20] used the graph neural network on AST for the codesummarization task. While the use of these general-purpose graph neural networks incode understanding has its merit, we believe that using state-of-the-artsequence-to-sequence models enhanced by domain-specific structural informationprovides the best trade-offs and opportunities.25Chapter 3Pru¨fer Sequence GenerationThe previous discussion shows that the Abstract Syntax Tree representation of acode plays a vital role in learning the code representation. In chapter 2, we discussedvarious methods like classical traversal methods such as Breadth-First Search (BFS), andDepth First Search (DFS) and modern methods like Structure Base Traversal (SBT) byHu [HLX+18a] and paths between the terminal nodes of the abstract syntax tree byAlon [ABLY19]. We also discussed the unique representation of a tree called Pru¨fersequence, which is a lossless encoding of the tree as there is a one-to-one correspondencebetween the Pru¨fer sequence and the tree. Thence, we can apply the Pru¨fer sequence torepresent the abstract syntax tree of the program code. We also use the Pru¨fer sequenceto construct a context of the code that helps in learning the lexical information of thecode.Algorithm 4: Pseudocode for Pru¨fer Sequence Generation from a AbstractSyntax Tree of codeStep 1 Given an AST of the code that is labeled by program tokensStep 2 Use a fixed mapping to map each token in the given token set to a unique integerandStep 3 Use it as the integer label of the AST-node that is labeled by the token togenerate integer-labeled ASTStep 4 Construct Pru¨fer sequence from this integer-labeled ASTStep 5 Mapped the Pru¨fer sequence in step 4 to sequence of syntactic tokens, which wecall the “Syntactic Pru¨fer Sequence”3.0.1 Pru¨fer Sequence Generation of a CodeIn this subsection, we discuss the mechanism for generating the Pru¨fer sequence ofthe program code. Fig 3.1 shows the overall architecture of the Pru¨fer sequence andcontext generation of a java code and algorithm-4 provide the Pseudocode for Pru¨fersequence generation from an AST of code.26Chapter 3. Pru¨fer Sequence GenerationFigure 3.1: Pru¨fer sequence and context generation of a codeStep 1. Given a Computer Code Generate the ASTAs discussed in chapter 2, given a code, we generate an AST such that the internalnodes of the AST hold the syntactic information of the code. And the terminal nodesof the AST hold the user-defined value of the AST like identifiers. For example, Fig.3.2 shows a java method and corresponding AST, such that internal nodes are <BasicType FormalParameter MethodInvocation ReturnStatement ClassCreatorReferenceType > and the terminal nodes are < Override Int StringmergeErrorIntoOutput Boolean Commands >27Chapter 3. Pru¨fer Sequence GenerationFigure 3.2: The Abstract Syntax Tree of the CodeStep 2. Map each token in the given token set to a unique integerWe use a fixed mapping to map each token in the given token set to a uniqueinteger and use it as the integer label of the AST-node that is labeled by the token.We hold the mapping information of an AST in an AST-Table with four attributes,i.e., < parent, children, type, value >. The parent and children are the integers thathold the edge information of the AST and “type” shows the syntactic type of the node,for example, IfStatement, Block, WhileStatement, and “value” shows the lexical tokenoccurring in the code, for example, identifiers like the variable name or the method nameof the code. Fig 3.3 shows an instance of the AST-Table.28Chapter 3. Pru¨fer Sequence GenerationFigure 3.3: Abstract Syntax Tree TableStep 3. Generating Syntactic Pru¨fer Sequence of the CodeGiven an integer-labeled AST of the code (Fig. 3.4), we generate the Pru¨fer sequenceof the tree using Algorithm-2 (Chapter 2), i.e., Given a tree T with n nodes labeled bythe integers {1, · · · , n}, its Pru¨fer sequence is a sequence of (n − 2) node labels (i.e.,integers) and can be formed by successively removing the leave with the smallest labeland including the label of its parent as the next node label in the Pru¨fer sequence. Theprocess stopped when only two nodes were left in the tree. The pru¨fer sequence of thetree in Fig. 3.4 is{0 0 3 0 5 0 7 8 7 10 12 11 10 14 }29Chapter 3. Pru¨fer Sequence GenerationFigure 3.4: Numerically labelled Tree structure for AST in Fig.4.2Step 5. Generate Syntactic Pru¨fer SequenceThe Pru¨fer sequence constructed from this integer-labeled AST is then mappedback to a sequence of syntactic tokens (Fig.3.5), which we call the “syntactic Pru¨fersequence” and is used as part of the input sequence to our learning model. Thesyntactic Pru¨fer sequence for the Java method in Fig. 3.1 is{MethodDeclaration, MethodDeclaration, FormalParameter, MethodDeclaration,FormalParameter, MethodDeclaration, ReturnStatement, MethodInvocation,MethodInvocation, ClassCreator, TypeArgument, ReferenceType, ClassCreator,MethodInvocation}Note that in the above sequence, a syntactic token may appear multiple times andat different positions. Also, note that the terminal nodes never appear in the sequence.The significance and relevance of such properties of the syntactic Pru¨fer sequence will bediscussed below and further explored in the next chapter on the design of our learningmodel and our empirical studies.30Chapter 3. Pru¨fer Sequence GenerationFigure 3.5: Generate Syntactic Pru¨fer SequenceFollowing are the examples of Pru¨fer sequence for java codes1 public static < T > T requireNonNull ( T object,String message)2 {3 if ( object == null )4 {5 throw new NullPointerException(message);6 }7 return object;89 }1. Pru¨fer-Sequence : MethodDeclaration MethodDeclaration FormalParameterMethodDeclaration FormalParameter MethodDeclaration BinaryOperationBinaryOperation IfStatement ClassCreator ClassCreator ThrowStatementBlockStatement IfStatement MethodDeclaration ReturnStatement1 public static < T > Callable < T > justCallable ( T value )2 {3 return new JustValue< Object , T >( value );4 }2. Pru¨fer-Sequence : MethodDeclaration TypeArgument ReferenceTypeMethodDeclaration FormalParameter MethodDeclaration ReturnStatement31Chapter 3. Pru¨fer Sequence GenerationClassCreator TypeArgument ReferenceType TypeArgument ReferenceTypeClassCreator1 public Throwable blockingGetError(long timeout, TimeUnit unit)2 {3 if(getCount( ) != NUM_)4 {5 try{6 BlockingHelper.verifyNonBlocking ( );7 if(!await(timeout,unit))8 {9 dispose ( );10 throw ExceptionHelper.wrapOrThrow(new TimeoutException( timeoutMessage(timeout,unit)));11 } }12 catch ( InterruptedException ex )13 {14 dispose ( ) ;15 throw ExceptionHelper.wrapOrThrow(ex);}}16 return error;17 }3. Pru¨fer-Sequence : MethodDeclaration FormalParameter MethodDeclarationFormalParameter MethodDeclaration BinaryOperation BinaryOperationIfStatement StatementExpression TryStatement MethodInvocationMethodInvocation IfStatement StatementExpression BlockStatementClassCreator MethodInvocation MethodInvocation ClassCreatorMethodInvocation ThrowStatement BlockStatement IfStatement TryStatementCatchClause StatementExpression CatchClause MethodInvocationThrowStatement CatchClause TryStatement BlockStatement IfStatementMethodDeclaration ReturnStatement1 public Throwable getError()2 {3 Object o = value;4 if(NotificationLite.isError(o))5 {6 return NotificationLite.getError(o);7 }8 return null;9 }32Chapter 3. Pru¨fer Sequence Generation4. Pru¨fer-Sequence : MethodDeclaration MethodDeclaration VariableDeclaratorLocalVariableDeclaration LocalVariableDeclaration MethodDeclarationMethodInvocation IfStatement MethodInvocation ReturnStatementBlockStatement IfStatement MethodDeclaration ReturnStatement1 public void startUnbounded( )2 {3 if(SubscriptionHelper.setOnce( upstream, EmptySubscription.INSTANCE ))4 {5 queue = new SpscLinkedArrayQueue<T>(bufferSize);6 }7 }5. Pru¨fer-Sequence : IfStatement MethodInvocation MethodInvocationIfStatement BlockStatement StatementExpression Assignment AssignmentClassCreator TypeArgument ReferenceType ClassCreator MethodDeclaration1 public long calculateDelay(TimeUnit unit)2 {3 float delta = variancePercent/NUM_;4 float lowerBound = NUM_ - delta;5 float upperBound = NUM_ + delta;6 float bound = upperBound - lowerBound;7 float delayPercent = lowerBound + ( random.nextFloat( ).bound );8 long callDelayMs = ( long ) ( delayMs.delayPercent );910 return MILLISECONDS.convert(callDelayMs,unit);1112 }6. Pru¨fer-Sequence : MethodDeclaration FormalParameter MethodDeclarationLocalVariableDeclaration BinaryOperation BinaryOperation VariableDeclaratorLocalVariableDeclaration MethodDeclaration LocalVariableDeclarationBinaryOperation BinaryOperation VariableDeclarator LocalVariableDeclarationMethodDeclaration LocalVariableDeclaration BinaryOperation BinaryOperationVariableDeclarator LocalVariableDeclaration MethodDeclarationLocalVariableDeclaration BinaryOperation BinaryOperation VariableDeclaratorLocalVariableDeclaration MethodDeclaration LocalVariableDeclarationBinaryOperation BinaryOperation VariableDeclarator LocalVariableDeclarationMethodDeclaration33Chapter 3. Pru¨fer Sequence Generation1 public OAuth2ClientConfigurer< HttpSecurity > oauth2Client ( ) throws Exception2 {34 OAuth2ClientConfigurer <HttpSecurity> configurer = getOrApply(new OAuth2ClientConfigurer< >( ));56 this.postProcess(configurer);78 return configurer;910 }7. Pru¨fer-Sequence : TypeArgument ReferenceType MethodDeclarationTypeArgument ReferenceType LocalVariableDeclaration ClassCreatorMethodInvocation VariableDeclarator LocalVariableDeclarationMethodDeclaration MethodInvocation This StatementExpressionMethodDeclaration ReturnStatement3.0.2 Properties of the Pru¨fer sequenceThe syntactic Pru¨fer sequence can be regarded as a “transformed” and “quantified”version of an AST and the corresponding source code where1. the frequency with which a syntax token appears is decided by the degree of thecorresponding AST node it labels and quantifies the “importance” of the token(measured the size of the code block it controls);2. the positions of the appearances of syntactic tokens in the Pru¨fer sequence aredecided by the position of the corresponding node in the tree; and3. a lexical token labeling a leave node of an AST never appears in the Pru¨fersequence, but its “significance” can be measured by the syntactic importance ofthe parent of the leave node.This is in sharp contrast with all other recently proposed sequential representations ofa source code and its AST, where all tokens are treated equally, and their positionspartially capture their roles in the AST.Supported by observations from our empirical studies (discussed in the next chapter),we believe that these are the properties that make it possible (or much easier) for ourlearning models to exploit information in the training examples that are hard, if notimpossible, for other recently-proposed learning models to detect.As we observed in our experiments(Chapter 4), other properties that distinguish ourPru¨fer-sequence representation from exiting representations and play important roles inthe performance of our learning model are as follows.34Chapter 3. Pru¨fer Sequence Generation1. Uniqueness and Lossless RepresentationTo our best knowledge, all existing sequential representations of source code andit’s AST [AZLY18, HLX+18a] are lossy encoding in the sense that the originalAST cannot be uniquely reconstructed. Our Pru¨fer-sequence representation is alossless encoding because, given a fixed syntactic-token-to-integer mapping, thereis a one-to-one correspondence between the set of ASTs and their syntactic Pru¨fersequences. For example, in chapter 2, we show the lossless encoding of the pru¨fersequences using the lemma 2.3, as we can reconstruct the original tree from thepru¨fer sequences. We note that none of the previous representations, such asclassical traversal methods like Breadth-First Search or Depth-First search or moremodern techniques like Structure Base Traversal [HLX+18a] or paths between theterminals [ABLY19] has such unique properties. The lossless representation of theAST ensures that the pru¨fer sequences preserved syntactic information of the code,and this property may help improve the ability of a learning method to distinguishor detect subtle differences in training examples.2. Shorter Input Length (or Lower Dimension)For an AST of length of n nodes, the length of our representation is in the worstcase is (n − 2) + (n − 1) = 2n − 3. In comparison, the length of representationproposed by Hu [HLX+18a] is 3n while the length of the representation proposedby Alon [IKCZ16] is in Ω (n3) in the worst case. A shorter representation of anAST required a lower dimension of the model, which helped in faster training ofthe model and reduced the long-term dependencies in the sequence. For example,let us consider an AST of a java method with 17 nodes (shown in Fig. 3.2), thelength of each representation is(a) For our representation, the length of the AST is 28 tokens i.e,{MethodDeclaration MethodDeclaration FormalParameterMethodDeclaration FormalParameter MethodDeclaration ReturnStatementMethodInvocation MethodInvocation ClassCreator TypeArgumentReferenceType ClassCreator MethodInvocation Annotation OverrideBasicType int BasicType boolean ReferenceType String MemberReferencemergeErrorIntoOutput ReferenceType String MemberReference commands}(b) For structure based traversal (SBT) method by Hu [HLX+18a], the lengthof the AST representation is 53 tokens i.e,{ ( MethodDeclaration ( Annotation ) Annotation ( BasicType ) BasicType( FormalParameter ( BasicType ) BasicType ) FormalParameter (FormalParameter ( ReferenceType ) ReferenceType ) FormalParameter (ReturnStatement ( MethodInvocation ( MemberReference )MemberReference ( ClassCreator ( ReferenceType ( TypeArgument (35Chapter 3. Pru¨fer Sequence GenerationReferenceType ) ReferenceType ) TypeArgument ) ReferenceType (MethodInvocation ( MemberReference ) }(c) For Alon [IKCZ16], the length of the AST when K is set to 5 is 28 nodes{ Override runCommand return runCommand mergeErrorIntoOutput ,mergeErrorIntoOutput runCommand return ArrayList None String , StringNone ArrayList return Arrays.asList commands , mergeErrorIntoOutputrunCommand return ArrayList Arrays.asList commands , booleanmergeErrorIntoOutput runCommand commands String }In our experiment, we observed that the Pru¨fer sequence representation has anaverage length of 100.81 tokens while the representation based on SBT [HLX+18a]has the 193.71 tokens to represent the same AST corpus(Table 4.6). This resultsin the faster training of the model, and we will discuss the empirical results inchapter 4.3. Natural Separation of Terminal and Non-Terminal NodesAs we pointed noted in chapter 2 of Pru¨fer sequence generation that the terminalnode of a tree does not appear in the Pru¨fer sequence. This provides a natural wayto separate the terminal nodes (which hold the user-defined value) and the non-terminal nodes (which contain the language-defined types). For our representationof the abstract syntax tree, we concatenate the Pru¨fer sequence of the AST and listof terminal nodes. For the particular case of two-node AST, the Pru¨fer-sequencepart of our representation is an empty list. Fig. 3.7 shows the Pru¨fer sequence ofthe AST. The Blue part of the sequence represents the internal nodes of the AST,while the green part of the sequence represents the terminal of the AST.4. To Define a Context of the CodeTo train a sequence-to-sequence model for tasks such as code summarization, atraining example consists of a sequence of tokens of the code and the developer’scomment on the code. Since code comments are usually extracted (by humandevelopers) from the lexical information of the source code, such as the methodor variable names, it is important for a learning model to take advantage of suchinformation. For example, Hu [HLX+20] in the Hybrid-DeepCom model proposedan attention-based dual encoder (Code Token encoder and SBT encoder) and adecoder model to generate comments of the code. Here the SBT will capturethe syntactical information of the code while the code token will help capture thelexical information of the code. An AST (Fig. 3.2) representation in the Hybrid-DeepCom model is< public int run Command ( boolean merge Error Into Output , String commands) throws IOException , Interrupted Exception return runCommand ( merge ErrorInto Output , new Array List < String > ( Arrays . asList ( commands ) ) ) ;>36Chapter 3. Pru¨fer Sequence GenerationFigure 3.6: Pru¨fer sequence of the AST(Non-Terminal nodes represented by Blue nodesand the Terminal nodes are represented by Green Nodes){ ( MethodDeclaration ( Annotation ) Annotation ( BasicType ) BasicType (FormalParameter ( BasicType ) BasicType ) FormalParameter (FormalParameter ( ReferenceType ) ReferenceType ) FormalParameter (ReturnStatement ( MethodInvocation ( MemberReference ) MemberReference (ClassCreator ( ReferenceType ( TypeArgument ( ReferenceType ) ReferenceType) TypeArgument ) ReferenceType ( MethodInvocation ( MemberReference ) }To encode the entire code to learn the lexical information of the code is not efficientas many of the tokens in the code does not contribute to the lexical informationof the code.The pru¨fer sequence of an AST provides a natural way for us to model the contextof a code. We define the context of a node in an AST to be the subset of itschildren that are terminal nodes, and we generate the set of the children usingthe Pru¨fer sequence. The context generated through the Pru¨fer sequence focuseson those tokens that are more significant in defining the context of the code. Forexample, the context of the tree (Fig 3.7) based on the Pru¨fer sequence (0 0 3 0 50 7 8 7 10 12 11 10 14) is {1 2 1 2 4 1 2 6 1 2 9 13 15} . We mapped this numericalsequence of context to the AST labeled sequence using the information stored atAST-Table. Context of the AST (Fig 3.2) after mapping is37Chapter 3. Pru¨fer Sequence GenerationFigure 3.7: Context Generation of the Code{ override int override int boolean override int commands override int StringArrays.as List commands}Following are the examples of context generated for java codes using Pru¨fersequence.1 private Socket getSocket(WebSocket conn)2 {3 WebSocketImpl impl =(WebSocketImpl) conn;4 return ((SocketChannel)impl.getSelectionKey( ).channel( )).socket();5 }(a) Comment Getter to return the socket used by this specificconnection@param conn The specific connection@return The socket used bythis connection(b) Context Generated get Socket Web Socket get Socket Web Socket Implconn Web Socket Impl conn Web Socket Impl Web Socket Impl get Socket38Chapter 3. Pru¨fer Sequence GenerationSocket Channel Socket Channel1 protected CompletionStage <Result> onForbidden (RequestHeader request,String message)2 {3 return CompletableFuture.completedFuture(Results.forbidden(views.html.defaultpages4 .unauthorized.render(request.asScala( ) ) ) ) ;5 }(a) Comment Invoked when a client makes a request that was forbidden(b) Context Generated Result on Forbidden Request Header on ForbiddenString on Forbidden request as Scala1 public void broadcast ( String text,Collection <WebSocket> clients)2 {3 if ( text == null || clients == null )4 {5 throw new IllegalArgumentException( );6 }7 doBroadcast(text,clients); }(a) Comment Send a text to a specific collection of websocketconnections@param text the text to send to the endpoints@param clients acollection of endpoints to whom the text has to be send(b) Context Generated String broadcast Web Socket broadcast text text clientsclients Illegal Argument Exception broadcast do Broadcast text clients textclients1 public void withTransaction( Consumer<EntityManager> block )2 {3 withTransaction( em ->{ block.accept(em); return null;});4 }(a) Comment Run a block of code with a newly created Entity Manager for thedefault Persistence Unit(b) Context Generated Entity Manager with Transaction block accept em emem block accept em39Chapter 3. Pru¨fer Sequence Generation1 public final Self overrides(GuiceableModule ... modules )2 {3 return newBuilder(delegate.overrides(Scala.varargs(modules)));4 }(a) Comment Override bindings using guiceable modules(b) Context Generated overrides Guiceable Module overrides modules1 public static Result status(int status, byte [ ]content)2 {3 if(content==null)4 { throw new NullPointerException(STR_); }5 return new Result(status,new HttpEntity.Strict( ByteString. fromArray(content),6 Optional.empty( ))); }(a) Comment Generates a simple result with byte-array content(b) Context Generated status int status byte status content content NullPointer Exception Null Pointer Exception status Result status Result statusResult status Optional empty Strict Optional empty content Optionalempty1 protected String removeLastOrderBy ( String sql )2 {3 int ndx = StringUtil.lastIndexOfIgnoreCase(sql,STR_);4 if(ndx != - NUM_)5 {6 int ndx2 = sql.lastIndexOf(sql,STR_);7 if(ndx > ndx2)8 {9 sql = sql.substring( NUM_,ndx);10 } }11 return sql; }(a) Comment Removes everything from last “order by”(b) Context Generated remove Last Order By String remove Last Order Byint sql sql int remove Last Order By ndx ndx int sql sql int sql ndx ndx sqlsql remove Last Order By sql40Chapter 3. Pru¨fer Sequence Generation1 protected String removeLastOrderBy ( String sql )2 {3 int ndx = StringUtil.lastIndexOfIgnoreCase(sql,STR_);4 if(ndx != - NUM_)5 {6 int ndx2 = sql.lastIndexOf(sql,STR_);7 if(ndx > ndx2)8 {9 sql = sql.substring( NUM_,ndx);10 } }11 return sql; }(a) Comment Removes everything from last “order by”(b) Context Generated remove Last Order By String remove Last Order Byint sql sql int remove Last Order By ndx ndx int sql sql int sql ndx ndx sqlsql remove Last Order By sql1 protected String removeSelect(String sql)2 {int ndx = StringUtil.indexOfIgnoreCase(sql,STR_);3 if(ndx != - NUM_)4 { sql=sql.substring(ndx+NUM_); }5 return sql; }(a) Comment Removes the first ’select’ from the sql query(b) Context Generated remove Select String remove Select int sql sql intremove Select ndx ndx sql ndx ndx sql sql remove Select sqlWe also point out that no special assumptions were made regarding AST orprogramming language, ensuring the same mechanism hold for other programminglanguages.41Chapter 4Pru¨fer-Sequence-Based LearningModel For Code SummarizationTo study the effectiveness of the Pru¨fer-sequence-based representation, we developeda deep-learning model for code summarization. The model maps a Java method to asummary of the method’s purpose in English. The training data are pairs of source codeof the Java method and developers’ comments. The high-level structure of our model isdepicted in Fig.4.1. It is a sequence-to-sequence (seq2seq) model [SVL14] in the encoder-decoder paradigm, where two separate encoders are used to learn from the structuralinformation of an AST and from a structure-aware representation of the lexical tokensfrom the source code. An attention module, similar to the one used by [HLX+20], is usedto combine the output of the two encoders into a context vector which is then used as theinput to a standard decoder described in [SVL14] to output a code summary/commentin English.Figure 4.1: Pru¨fer Based Learning Model for Code Summarization Task42Chapter 4. Pru¨fer-Sequence-Based Learning Model For Code Summarization4.0.1 Pru¨fer Sequence EncoderThe Pru¨fer Sequence Encoder is designed to learn from the structural informationof the ASTs that are losslessly encoded in their syntactic Pru¨fer sequences. GatedRecurrent Units (GRUs), as discussed by [CvM14], are used to map the syntactic Pru¨fersequence (X = x1, ...., xn) of a computer program to a sequence of hidden states asfollows:st = GRU(xt, st−1)In our implementation, lexical tokens labeling the terminal nodes are appended tothe syntactic Pru¨fer sequence as part of the input to the encoder, resulting in an inputlength of at most 2n − 3. We observed in our initial experiments that the modelHybrid-DeepCom [HLX+20] with its SBT-based encoder replaced by our Pru¨ferSequence Encoder already outperformed notably the original Hybrid-DeepCom Modeland other baseline models. It turned out that the bottleneck to further improvement ofsuch models is the design of the second encoder, the Source Encoder [HLX+20], thatlearns from source code tokens directly. This observation in our early investigationmotivated us to design our own second encoder, which we call the Context Encoder,that exploits lexical information in a structure-aware way.4.0.2 Context EncoderThe context encoder, also consisting of GRUs, is designed to learn from thecollection of lexical tokens (i.e., user-defined and program-specific values in the sourcecode) organized in a way that reflects the structural information of the AST.For each node in an AST, we define its context to be the set of lexical tokens thatlabel the node’s leaf child/children. A node with no leaf child has an empty context. Thecontext of an AST is defined to be the union of the contexts of the AST nodes ordered inthe same order as they appear in the syntactic Pru¨fer sequence. The context of an ASTcan be calculated from the AST’s Pru¨fer sequence (See Fig. 3.1). The context encodermaps the context (X′= x′1, ...., x′n) defined in the above to a sequence of hidden states.s′t = GRU(x′t, s′t−1)The context of an AST defined in this way is a structure-aware sequence of lexicaltokens because (1) the frequency of a lexical token is decided by the degree of the parentof the node the token labels; and (2) the order in which these tokens appear in the contextis the same as the order of the parent nodes in the Pru¨fer sequence. As observed in ourexperiments, the use of the context encoder helps boost the performance of our learningmodel significantly. This is because, we believe, that the context we have designed helpsamplify the learning-relevant lexical signals in the source code in a way that other models(such as those in [HLX+20]) cannot detect that by simply using the collection of entiretokens as they appear in the source code.43Chapter 4. Pru¨fer-Sequence-Based Learning Model For Code Summarization4.0.3 AttentionThe attention model incorporated in an encoder decoder model will assist in focusingthose input words that are more relevant at time step t. The generation of each wordis based on the classical attention method proposed by Bahdanau [BCB15]. In ourmodel, the attention mechanism is designed to focus both the encoder, i.e., the ContextEncoder, and the Pru¨fer Sequence Encoder, which is similar to the attention mechanismused by Hu [HLX+20]. For each target word yi we define an individual ci as the weightedsum of all the hidden states of both the encodersci =∑mj=1 αij sj +∑mj=1 α′ij s′jwhere the α and α′are the attention distribution of Context encoder and Pru¨fersequence encoder respectively. The αij of the hidden sate sj is computed asαij =exp(eij)∑mj=1 exp(eik)andα′ij =exp(e′ij)∑mj=1 exp(e′ik)where eij and e′ij are computed aseij = a(hi−1, sj)ande′ij = a(hi−1, s′j)where a is a alignment models [BCB15] which score how well the inputs around positionj and the output at position i match.4.0.4 DecoderThe decoder will generate the output y (comment of the code ) by sequentiallypredicting the probability of a word yi such that it is conditioned over the contextvector ci and its previous generated y1, y2. . . . . . yi-1p (yi|y1, y2......yi−1, x) = g (yi−1, hi,ci)where g is used to estimate the probability of the word yi .The objective of the model isto reduce the cross-entropy [SVL14]h (y) =−1NN∑i=1n∑j=1logp(yij)where the N is the total number of the training instance and the n is the length ofeach target sequence and our model uses the optimization algorithm such as gradientdescendent for optimizing the objective function.444.1. Experiment Setup4.1 Experiment SetupFigure 4.2: Distribution of Code LengthWe perform the code summarization task on two standard datasets a) the first datasetprovided by the Hu [HLX+18b], we refer to this dataset as Dataset-1. Dataset-1 iscollected from popular repositories in Github, is a parallel collection of Java code andcomments. For dataset-1, we have a corpus of 68469 code and comment pairs for thecode summarization task, and we split the dataset-1 into 8:1:1 for training, testing, andvalidation, respectively. The second dataset is the CodeXglue java dataset provided bythe Microsoft [LGR+21]; we refer to this dataset as dataset-2. It is known for its highquality and complexity and is believed to be one of the most challenging datasets fordeep learning approaches to program understanding and generation. For dataset-2, wehave 163316 pairs of Java code and comments, and we split the dataset-2 into 8:1:1 fortraining, testing, and validation, respectively. And Fig 4.2 and 4.3 show the frequencydistribution of Java code and comment length of the dataset-1 and Dataset-2 such thatthe x-axis shows the code and comment length while the y-axis shows the frequency of454.1. Experiment Setupthe code and comment length. Tables 4.1 and 4.2 show the statistical summary of theJava code and comment for Dataset-1 and Dataset-2.Figure 4.3: Distribution of Comment LengthFor building the vocabulary for the model, we follow the methods used byHu [HLX+18a, SVL14]. For both dataset-1 and dataset-2, java code and comments areparsed into tokens using the Javalang and NLTK2 respectively. The numerical andstring in the java code are replaced by the generic token <NUM > and <STR>respectively. Special tokens <START> and <EOS> are added to the decodersequence during the training such that the <START> represents the start of thesequence and the <EOS> represents the end of the sequence. The out-of-vocabulary isrepresented by especial token <UNK>. The vocabulary size is set to 30000 tokens forcode, comment, and code’s contex [HLX+18a, SVL14]. From Table 4.1 and 4.2, weobserved that 88.42 % of the comments have less than 30 tokens and 89.48 % of thecode has less than 200 tokens, so we set the maximum length of the code and comment2https://www.nltk.org/464.1. Experiment Setupfor our experiment be 30 and 200 tokens respectively. For the AST sequence, we keptthe maximum length of the sequence to be 500 tokens [HLX+18a, SVL14].Table 4.1: Statistics of the Java MethodsDataset Type Mean Mode Median SD <200 TokensDataset-1 97.05 16 64 119.77 89.48%Dataset-2 98.35 42 69 83.64 89.29%Table 4.2: Statistics of the Java commentsDataset Type Mean Mode Median SD <30 TokensDataset-1 16.1 7 11 16.91 88.42%Dataset-2 11.02 7 9 7.34 97.33%Our model uses one layered GRU with 256 dimensions of hidden state and 256-dimensional word embedding. The maximum iterations are 60 epochs and the beamwidth is set to 5. The learning rate is set to 0.5, and we clip the gradients norm by 5.The learning rate is decayed using the rate 0.99. The model uses the TensorFlow version1.15, and we train our model on a single GPU of Tesla P100-PCIE-16GB with 25 GBRAM and 110GB disk.4.1.1 BaselineIn our experiments, we compared the performance of our learning model with thefollowing baseline models to empirically analyze the power, effectiveness, and efficiencyof the proposed Pru¨fer-sequence-based representation.1. TL-CodeSum Model [HLX+18b]. This is an NMT based code summarizationmethod that uses API knowledge and source code tokens as the input in a sequence-to-sequence model.2. Hybrid-DeepCom Model [HLX+20]. This sequence-to-sequence model for codesummarization is one of the recent models that is designed to exploit structuralinformation in the AST of a computer program. It uses two encoders: a source-token encoder and an SBT encoder. The SBT encoder uses a depth-first-traversalsequence representation of an AST as its input, and the code-token encoder is usedto learn from the lexical information of the source code.3. Code2Seq Model [ABLY19]. This is a deep-learning model for general coderepresentation learning. Code2Seq uses the concatenation of the token sequences474.1. Experiment Setupalong the paths between pairs of terminal nodes in an AST as its inputrepresentation to generate comments.4. BFS-Hybrid-DeepCom. This model is based on the Hybrid-DeepCom Model[HLX+20] with the SBT representation of an AST replaced by a sequencerepresentation constructed from a breadth-first-search (BFS) traversal of theAST. We included this model to help verify our claim that all therecently-proposed sequence representations are more or less arbitrary. Asobserved from our experiments (see next Section), this BFS-based modelperforms equally well (or even slightly better) than those recently proposedmodels.5. Lexical-Token-Only Model. This basic attention-based seq2seq model has onlyone encoder that learns from the lexical information in the source code. We usedthis model to understand the importance of incorporating syntactic information(in the AST) in deep-learning approaches for code summarization. The parametersetting of the model is similar to that of the Hybrid-DeepCom model.4.1.2 MetricsTo evaluate the effectiveness of different approaches, we use four widely-used machinetranslation metrics: two BLEU scores, the METEOR score, and ROUGE-L.1. BLEU ScoreThe Bilingual Evaluation Understudy (BLEU) [PRWZ02] is a metric to checkthe quality of the machine-translated (candidate) text against that of the human-written (reference). The BLEU score is in the range of 0 to 100 such that the higherthe value closer is the machine-generated text to that of human-written text. Theprimary task of a BLEU implementor is to compare n-grams of the candidate withn-grams of the reference translation and count the number of the matches. Here n-gram refers to the number of the words from the sequence matching the candidateand reference. For instance, a uni-gram will have one word from a sequence, and abi-gram will have two words while matching between sentences. The BLEU scoreis computed as:BLEU = BP.exp(∑Nn=1wn log pn)where pn is the ratio of length n subsequences in the candidate that is also in thereference, and we set N to 4 (which is the maximum number of a gram). wn is apositive weight such that wn = 1/N . BP is the brevity penalty, ensuring that ahigh-scoring candidate translation must match the reference translations in length,word choice, and word order. We compute the BP as :484.1. Experiment SetupBP ={1 if c > re(1− r/c) if c ≤ rwhere c is the length of the candidate translation and r is the effective referencesequence length. In this study, we evaluate the approaches by Sentence-LevelBLEU (S-BLEU) score computed by the NLTK3(evaluating a candidate sentenceagainst reference sentences) with a smoothing-4 method and Corpus-level BLEU(C-BLEU) calculated by “multi-bleu.perl”4( Calculate a single corpus-level BLEUscore for all the hypotheses and their respective references).2. ROUGE-L ROUGE (Recall-Oriented Understudy for Gisting Evaluation) is aMachine Translation metric proposed by Chin [Lin04]. It measures the quality of asummary generated by the machine by comparing the number of overlapping unitssuch as n-gram, word sequences, and word pairs between the computer-generatedsummary and the ideals summary created by humans. ROUGE-L is one of thefour measures of the ROUGE where L stands for Longest Common Subsequence,and it computes the F-score, where F-score is calculated as the harmonic mean ofthe recall and precision value obtain from finding the longest common sequence ofthe texts.Let us consider two summary sentences of X with m length and Y with n lengthsuch that X is a reference summary and Y is a candidate/Predicted summarysentencesRLCS =LCS(X,Y )mPLCS =LCS(X,Y )nFLCS =(1+β)2∗RLCS∗PLCSRLCS+β2∗PLCSwhere LCS(X,Y) is the length of the longest common subsequence of X and Y andβ = PLCSRLCSand the LCS-based F-measure is called the ROUGEL-L.3. METEOR Metric for Evaluation of Translation with Explicit ORdering(METEOR) [DL14] is a recall-oriented evaluation method. It evaluatestranslation hypotheses by aligning them to reference translations and calculatingsentence-level similarity scores3https://www.nltk.org4http://www.statmt.org/moses/?n=Moses.SupportTools494.2. ResultsScore = (1− Pen)Fmeanwhere penalty (Pen) is the ratio number of chunks(ch), where a chunk is definedas a series of matches that is contiguous and identically ordered in both sentencesand number of matches (m, averaged over hypothesis and reference) andcalculated asPen = γ ∗ ( chm )βFmean =P∗Rα∗P+(1−α)Rwhere F-mean measures the parameterized harmonic mean of Precision andRecall. The parameters α, β and γ are tuned are tuned to maximize correlationwith human judgments. For English Denkowski [DL14] set the value of α to0.85, β to 0.20 and γ to 0.60.Precision The classical definition of precision is that it is the ratio of correctlypredicted positive observation to the total predicted positive observation. Wecalculate the precision using the method proposed by Denkowski [DL14]. Thismethod gives different weights for content and function words. Context wordsprovide the most important words in the sentences, while the function words arethe grammar that stitches the context words. The content and function words inthe generated comment and reference are (hc, hf ) and (rc, rf ) respectively. Foreach of the matches mi, count the number of content and function words coveredby matches of this type in the hypothesis (mi(hc), mi(hf )) and reference (mi(rc), mi (rf ))P =∑i wi(δ∗mi(hc)+(1−δ)∗mi(hf ))δ∗|hc|+(1−δ)∗|hf |where δ is word weight of the content-function and is set to 0.75 according toDenkowski [DL14].Recall Following the precision, we choose a weighted Recall to measure modelsR =∑i wi(δ∗mi(rc)+(1−δ)∗mi(rf ))δ∗|rc|+(1−δ)∗|rf |4.2 ResultsIn Tables 4.3 and 4.4, we summarize the experiment results on the effectiveness ofour Pru¨fer-based learning model and the baseline models for code summarization task504.2. Resultson two public Java datasets: a) Dataset-1 [HLX+18b] and b) Dataset-2 [LGR+21] . Wenote that the performance scores for Dataset-2 is much lower, but this is not asurprise—as we mentioned in the previous section, this dataset is believed to be one ofthe most challenging dataset for deep learning approaches to program understandingand generation. A detailed discussion can be found on CodeXGlue’s project webpage(https://microsoft.github.io/CodeXGLUE/). Also, note that in Table 4.4 (forDataset-2), we do not have a row for the model TL-CodeSum because Dataset-2 doesnot provide the API knowledge required to train the model. As we can see, the modelthat uses our Pru¨fer Sequence Encoder and Hu’s Source Encoder (second last rows inboth Tables 4.3 and 4.4) has already had notable improvement over the baselinemodels. The improvement by our complete Pru¨fer-sequence-based model (using ourPru¨fer Sequence Encoder and our Context Encoder) is even more significant, especiallyon Dataset-2 (last rows in both Tables 4.3 and 4.4.)514.2. ResultsTable 4.3: Effectiveness of Models based on Machine Translation metrics for Dataset-1and value inside the bracket shows the performance improvements in percentage compareto the baseline modelsModel S-BLEU C-BLEU METEOR ROUGE-LLexical-Token-Only Model 36.21 27.30 19.01 40.78Code2Seq 20.72 4.56 10.21 20.63TL-CodeSum 37.20 28.43 19.64 41.29BFS-Hybrid-DeepCom 37.98 29.08 19.72 41.03Hybrid-DeepCom 38.19 29.28 19.87 41.15Our Model (Pru¨fer Encoder + Hu’s Source Encoder) 38.38 (0.5%) 29.43 (0.5%) 20.13 (1.3%) 41.82 (1.3%)Our Model (Pru¨fer Encoder + Context Encoder) 39.67 (3.3%) 31.01 (5.7%) 21.01 (5.6%) 43.45 (5.1%)Table 4.4: Effectiveness of Models based on Machine Translation metrics For Dataset-2and value inside the bracket shows the performance improvements in percentage compareto the baseline modelsModel S-BLEU C-BLEU METEOR ROUGE-LLexical-Token-Only Model 9.21 3.07 7.96 19.84Code2Seq 2.27 0.30 3.5 12.23BFS-Hybrid-DeepCom 13.41 3.47 7.29 20.42Hybrid-DeepCom 15.02 3.7 8.27 18.01Our Model (Pru¨fer Encoder + Hu’s Source Encoder) 15.50 (3.15%) 3.85 (3.97%) 8.9 (6.925%) 20.79 (1.8%)Our Model (Pru¨fer Encoder + Context Encoder) 16.15(7.02%) 4.49 (19.29%) 9.72 (15.05%) 24.73 (19.09%)52524.2. ResultsIn the rest of this section, we discuss our observations from the experiments andanalyze the results to understand the power, effectiveness, efficiency, and therobustness (against the code length) of our Pru¨fer-sequence-based representation.These observations and their analyses are solid evidence, supporting our belief that ourPru¨fer-sequence-based representation makes it possible (or much easier) for learningmodels to exploit information in the training examples that are hard, if not impossible,for other recently-proposed learning models to detect.Power and Effectiveness of Pru¨fer-Sequence Representation of AST.As shown in the second last rows in Tables 4.3 and 4.4, our Pru¨fer SequenceEncoder and Hu’s Source Encoder [HLX+20], used to learn the lexical information ofcode by taking the entire code as input to the Source Encoder (second last rows inboth Tables 4.3 and 4.4) has already had notable improvement over the baselinemodels, with the average performance improvement being 0.9% for Dataset-1 and3.96% for Dataset-2. We attribute the performance improvement to the properties ofthe Pru¨fer sequence representation discussed in the previous Section (Abstract SyntaxTrees and Pru¨fer Sequences): a concise and lossless encoding that quantifies the“importance” of syntactic tokens and preserves their structural roles in describing thesource code. This is further supported by the relatively poor performance of therecently-proposed general model, Code2Seq, that uses a lossy encoding with the inputlength cubic to the size of the AST in the worst case. Note that the performance of theCode2Seq Model is worse than the model that does not make use of any structuralinformation of the AST (first rows in both tables).We can also see that the performance of the two versions of the Hybrid-DeepComModel based on respectively the BFS sequence and the SBT sequence are comparableon both datasets, justifying our claim in the introduction that in such traversal-basedsequence representation recently proposed, the order of the tokens in a sequence is largelyarbitrary and only partially captures the structure of an AST.Importance of Structure-Aware Context Sequence of Lexical Tokens.As shown in the last row in both Tables 4.3 and 4.4, the use of the Context Encoderboosted the performance of our model. The average performance improvement overbaseline models is increased from 0.9% to 5% for Dataset-1 and 3.96% to 15.11% forDataset-2.Considering that both of the two recently-proposed deep-learning models (Code2Seqand Hybrid-DeepCom, the second rows and the third last rows in both tables) are alsodesigned to make use of structural information of an AST as well as lexical tokens fromthe source code, the significant performance gain of our model is best interpreted bythe fact that the “context” sequence defined in our model as the input to the ContextEncoder is structure-aware. The difference between our context sequence and the thoseused in the Hybrid-DeepCom model and the Code2Seq model is that in our contextsequence, the frequency of a lexical token from the source code is decided by the degree534.2. Resultsof its parent node in the AST, whereas Hybrid-DeepCom and Code2Seq treat tokensfrom the source code equally regardless of their role and significance in the program.4.2.1 Performance over Source Code of Different LengthsThe histogram in Fig. 4.4 shows the frequency distribution of the code length (tokencount). From Fig. 4.4, we can say that more than 90% of the java method has alength of 25 to 250 tokens. Therefore we will consider the code length between 25to 250 tokens while measuring the performance of three learning models: Our Model,Hybrid-DeepCom, BFS-Hybrid-DeepCom.Figure 4.4: Frequency Distribution of Code LengthWe observe (Fig.4.5) that for all the three models, the performance decreases as thecode length increases. When the code length is between 25 to 50 tokens, the modelachieves optimal performance. We note that our Pru¨fer-sequence-based model performsbetter than the other two baseline models regardless of the code lengths. For the Javamethod with 150 or more tokens, the Pru¨fer sequence-based model had a clear edge overthe other two methods, suggesting that it is more robust against the increase of codelength. To test the statistical significance of the result, we conduct a t-test (Independent544.2. Resultst-test) between the Pru¨fer-sequence-based model and SBT model, and we get a p-valueof 0.0004, showing results are significant. Also for Pru¨fer-sequence-based model and BFSmodel we get a a p-value of 0 (as value is very low) showing a significant result.The correlation coefficient between the BLEU score and code length is the smallest forthe Pru¨fer-sequence-based model (-0.037), while for BFS and SBT, it is -0.16 and -0.19,respectively. This indicates that the (negative) correlation between the performance ofmodels and the code length is much weaker for our model than the other two models.Figure 4.5: BLEU score for different method lengths4.2.2 Flexibility of Pru¨fer SequenceWe incorporate the Pru¨fer sequence into two existing models a) Hybrid-DeepComModel by Hu [HLX+20] where we replace the SBT with Pru¨fer sequence and b) TL-CodeSum [HLX+18b] where we replace the code itself with that of the Pru¨fer sequence.1. In the Hybrid DeepCom model, the empirical result from Table 4.5 shows that theperformance of the Hybrid DeepCom model with the Pru¨fer sequence is similarto that of the Hybrid DeepCom model with SBT (slight improvement across allmetrics). This result can be attributed to the fact that both SBT and the Pru¨fersequence use the syntactic type of tokens to represent the sequence.2. In the TL-CodeSum model, the empirical result from Table 4.5 shows that theperformance of the Hybrid DeepCom model decreases as we replace the code554.2. Resultswith the Pru¨fer sequence. Since the TL-CodeSum model [HLX+18b] relied on thesemantic value (actual code as input to model) for the comment generation, thusreplacing the semantic value with the syntactic tokens of the Pru¨fer sequenceresult in the drop in the performance.Table 4.5: Flexibility of Pru¨fer sequence for Dataset-1Model S-BLEU C-BLEU METEORTL-CodeSum 37.20 28.43 19.64Hybrid-DeepCom 38.19 29.28 19.87TL-CodeSum(Prufer) 29.58 20.78 15.54Hybrid-DeepCom (Prufer) 38.38 29.43 20.13From these two observations, we can see that the Pru¨fer sequence is flexible and canbe used with those existing models where the input to the model is the syntactic typeof tokens.4.2.3 Efficiency of the Pru¨fer Sequence in encoding the AST of thecodeThe input dimension to the seq-to-seq deep learning model depends on the encodingscheme of the code. The lower the dimension is, the faster it is to complete one epochof training. There is, of course, a tradeoff among the effectiveness/ability of a model, itsinput dimension, and the training time. An ideal encoding is the one that preserves asmuch as possible the structural information and has a short length.Table 4.6: Statistics of the AST Representation Methods for Dataset-1Method Mean Mode Median <100 Tokens <150 Tokens <200 TokensPrufer Sequence 100.81 8 82 67.74% 81.11% 88.06 %SBT 193.71 24 124 41.42% 58.01% 68.77%BFS 70.21 8 44 80.02% 89.6% 94.16%Our experiments confirm that our Pru¨fer sequence representation encodes thestructure of an AST losslessly and is more concise than other representations indeedrequires less time to train. Fig. 4.6 summarizes our observation on the time required tocomplete different training epochs for three learning models: Our Model,564.2. ResultsHybrid-DeepCom, BFS-Hybrid-DeepCom. Among the models, BFS-Hybrid-DeepComuses the shortest sequence representation (70.21 on average over the training data),and Hybrid-DeepCom has the longest representation (193.91 on average). The averagelength of our Pru¨fer sequence representation is 100.81. It is a surprise to observe thatBFS-Hybrid-DeepCom (a model we customized from Hybrid-DeepCom using astraightforward and much shorter breadth-first-search-based representation) requiresless training time but has a comparable performance with Hybrid-DeepCom that isbased on a carefully designed and more sophisticated representation. While our modelrequires more time to train than BFS-Hybrid-DeepCom (as expected but not bymuch), the performance gain of our model is significant.Figure 4.6: Time required to train Pru¨fer Based Learning Model for 60 epoch usingdifferent AST representation.4.2.4 Comment Generation Using Different AST RepresentationMethodsOne advantage of the Pru¨fer based code representation learning model is that itgenerates the comment based on the context of the code. The code’s context ensuresthat tokens relevant to the comments are sent as input to the model and generate qualitycomments.The general approach of the comments relied either on the manually crafted templates(which is time-consuming, and the quality of keywords depends on the quality of a givenJava method) or the IR-based approach (relying on finding similar code snippets). Hu574.2. Results[HLX+20] uses the flat sequence of tokens to learn the lexical information to generatethe comments, which is inefficient as most of the tokens in the code are not part of thecomment generation.In our approach, the Pru¨fer sequence ensures that the context of the code focuses onthose terminal tokens relevant in generating the comments. The model learns the lexicalinformation of the code through the context of the code, and the attention mechanismhelps to align the context of the code and natural language words. Following are theexamples of the quality of comments generated by the Pru¨fer sequence-based learningmodel.1 public void print ( final int width , @ Nonnull final PrintStream aPS ) {2 final SystemOutAlignRight ar = new SystemOutAlignRight ( aPS ) ;3 for ( int r = NUM_ ; r < m_nRows ; ++ r )4 { ar.print( STR_, NUM_ );5 ar.print(r+NUM_, NUM_ );6 ar.print(STR_,NUM_);7 for(int c=NUM_;c<m_nCols;++c) {8 ar.print(m_aValues [ r ] [ c ] , width );9 }10 ar.println ( ) ; } }1. Reference Print the matrix values2. Pru¨fer Sequences Print the contents of the given 2D column to the givenPrintStream3. SBT Print the contents of the given at the beginning at the end4. BFS Prints the size of the space5. Code2Seq a contact from set to default to as from1 final void signalWork ( WorkQueue [ ] ws , WorkQueue q ) {2 long c ;3 int sp , i ;4 WorkQueue v ;5 Thread p ;6 while ( ( c = ctl ) < NUM_ ) {7 if ( ( sp = ( int ) c ) == NUM_ )8 {9 if ( ( c & ADD_WORKER ) != NUM_ ) tryAddWorker ( c ) ;10 break ;11 } if ( ws == null )12 break ;584.2. Results13 if ( ws.length <= ( i = sp & SMASK ) )14 break ;15 if ( ( v = ws [ i ] ) == null )16 break ;17 int vs = ( sp + SS_SEQ ) & ~ INACTIVE ;18 int d = sp - v.scanState;19 long nc = ( UC_MASK & ( c + AC_UNIT ) ) | ( SP_MASK & v . stackPred ) ;20 if ( d == NUM_ && U.compareAndSwapLong( this , CTL , c , nc ) ) { v.scanState = vs ;21 if ( ( p = v . parker ) != null ) U.unpark ( p ) ; break ;22 }23 if ( q != null && q.base == q.top ) break ;24 }2526 }1. Reference Tries to create or activate a worker if too few are active2. Pru¨fer Sequences Tries to try and enter a worker if it is available and if so3. SBT Final external auth in avoid cleaning up in queue4. BFS Uses to create worker heartbeat a worker and wait for too much5. Code2Seq to a has and a task of to1 public void registerDefaultProcessor ( RemotingProcessor < ? > processor )2 {3 if ( this.defaultProcessor == null )4 {5 this.defaultProcessor = processor;6 } else7 {8 throw new IllegalStateException ( STR_ + this.defaultProcessor.getClass ( ) );9 }10 }1. Reference Register the default processor to process command with no specificprocessor registered2. Pru¨fer Sequences Sets the default constructor to be used when creating a newprocessor3. SBT Sets the thread pool used by this parser4. BFS Sets the processor processor the processor processor fallback processor594.2. Results5. Code2Seq is is and1 public < T > List < T > getList ( String path , Class < T > genericType ) {2 if ( genericType == null ) {3 throw new IllegalArgumentException ( STR_ ) ; }4 final List < T > original = get ( path );5 final List < T > newList = new LinkedList < T > ( );6 if ( original != null )7 { for ( T t : original ) {8 T e ;9 if ( t instanceof Map &&10 !genericType.isAssignableFrom ( Map . class ) )11 {12 String str = objectToString ( t );13 e = ( T ) jsonStringToObject ( str , genericType );14 } else15 {16 e = ObjectConverter.convertObjectTo ( t , genericType ) ;17 } newList.add ( e );18 }19 }20 return Collections.unmodifiableList( newList );21 }1. Reference Get the result of an Object path expression as a list2. Pru¨fer Sequences Returns a list of objects from the given path3. SBT Returns a list of values from the generic class with the given generic class4. BFS Get a list of values from the given generic path5. Code2Seq list and object object value1 public static ServerWebExchangeMatcher pathMatchers ( HttpMethod method , String ... patterns )2 {3 List < ServerWebExchangeMatcher > matchers = new ArrayList < > ( patterns.length );4 for ( String pattern : patterns )5 {6 matchers.add(7 new PathPatternParserServerWebExchangeMatcher ( pattern , method ) ) ; }8 return new OrServerWebExchangeMatcher ( matchers );9 }604.2. Results1. Reference Creates a matcher that matches on the specific method and any of theprovided patterns2. Pru¨fer Sequences Creates a set of matcher classes from the given methods3. SBT Create a set of predicates from the given method@param method@param4. BFS Creates a filter from the given list of parameter types5. Code2Seq creates a new instance of method to for in and and and and1 public Buffer append ( final Buffer buffer )2 {3 if ( buffer.list.isEmpty ( ) )4 {5 return buffer;6 }78 list.addAll( buffer.list);910 last = buffer.last;1112 size += buffer.size;1314 return this;1516 }1. Reference Appends other buffer to this one2. Pru¨fer Sequences Appends the record to the buffer3. SBT Appends the buffer to the buffer4. BFS Appends the contents of the buffer to the given buffer5. Code2Seq buffer value the1 public void setGastgewTyp ( Gastgewerbe . GastgewTyp value )2 {34 this . gastgewTyp = value ;56 }614.2. Results1. Reference Sets the value of the gastgewTyp property2. Pru¨fer Sequences Sets the value of the property3. SBT Sets the value of the attribute4. BFS Gets the value of the property5. Code2Seq set for and value1 public void setGastgewTyp ( Gastgewerbe . GastgewTyp value )2 {34 this . gastgewTyp = value ;56 }1. Reference Sets the value of the gastgewTyp property2. Pru¨fer Sequences Sets the value of the property3. SBT Sets the value of the attribute4. BFS Gets the value of the property5. Code2Seq set for and value1 public GeoPackageGeometryData getGeometry ( )2 {3 GeoPackageGeometryData geometry = null ;4 int columnIndex = getTable ( ).getGeometryColumnIndex ( );5 int type = getType ( columnIndex );6 if( type != FIELD_TYPE_NULL )7 {8 byte [ ] geometryBytes = getBlob ( columnIndex );9 if ( geometryBytes != null )10 {11 geometry = new GeoPackageGeometryData ( geometryBytes );12 }13 }14 return geometry;1516 }1. Reference Get the geometry@return geometry data624.2. Results2. Pru¨fer Sequences This method returns all of the items in the database that areread from the file3. SBT Gets the value of the property4. BFS Load the feature geometry5. Code2Seq name name and to to63Chapter 5ConclusionsAutomated code comprehensions increasingly rely on deep learning models such asneural machine translation(NMT) for tasks such as code summarization, programproperty predictions, and code classification. Earlier models treat the code as a flatsequence of tokens and pass it as input to the code. However, studies[HLX+18a, ABLY19] show that such straightforward representation fails to capture thesyntactic information of the code, which plays a vital role in defining the functionalityof the code. Several methods were proposed to capture the syntactic information of thecode using the abstract syntax tree, for instance, classical traversal methods(Breadth-First Search and Depth First Search), Structure-Based Traversal(SBT) [HLX+18a], and paths between the terminals nodes of the AST [ABLY19].These representations are lossy, and the choice of the tokens is arbitrary in somemethods.In this work, we proposed a concise and effective representation scheme that can beused in sequence-to-sequence models for code representation learning. By encodingstructural information of abstract syntax trees of computer programs, ourPru¨fer-sequence-based representation makes it possible (or much easier) to developsequence-to-sequence learning models to exploit automatically and selectively lexicaland syntactic signals that are hard, if not impossible, for other recently-proposedsequence-to-sequence learning models to detect. The context of the code generatedfrom the Pru¨fer-sequence has a natural advantage over the flat sequence of code as thefrequency of the tokens in Pru¨fer-sequence is one less than the degree of the node inthe tree. Thus a context based on the Pru¨fer-sequence ensures that the contextsequence focuses on those tokens which are more important in understanding thelexical information of the code, which improved the performance of the model.[ACRC20] investigated the possibility of incorporating AST information in theirtransformer-based model and concluded that AST information does not provide anyhelp. Our studies in this paper suggest that it depends on how the (hierarchical) ASTinformation is encoded and used in a learning model. It is a very interesting futurework to study how our Pru¨fer-sequence-based encoding of ASTs can be used in atransformer-based model (such as the one in [ACRC20]) to decrease the model’scomplexity and improve its effectiveness.While the model we developed and the experiments conducted are on the task of codesummarization for a particular program language, no assumptions were made about theprogramming language and the specification and the format of the abstract syntax trees,making our approach language independent and potentially applicable to other tasks inprogram comprehension and in any application domains of sequence-to-sequence learning64Chapter 5. Conclusionsmodels where sequential and hierarchical signals both exist in the training data.Thence, the Pru¨fer-sequence is a lossless, concise and effective encodingrepresentation of the code. And from our empirical study, we provide a proof ofconcept that Pru¨fer-sequence can be used for the linear encoding of the AST of thecode for learning the code representation.65Bibliography[AA21] Norah Alsaaran and Maha Alrabiah. Classical arabic named entityrecognition using variant deep neural network architectures and bert. IEEEAccess, 9:91537–91547, 2021. → pages 2[ABLY19] Uri Alon, Shaked Brody, Omer Levy, and Eran Yahav. code2seq: Generatingsequences from structured representations of code. In InternationalConference on Learning Representations, 2019. → pages 5, 10, 11, 25, 26,35, 47, 64[ACRC20] Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-WeiChang. A transformer-based approach for source code summarization.In Proceedings of the 58th Annual Meeting of the Association forComputational Linguistics, pages 4998–5007. Association for ComputationalLinguistics, 2020. → pages 24, 25, 64[And19] Rick Anderson. Rnn,talking about gated recurrent unit - dlbt: Deep learningbenchmark tool. DLBT — Deep learning benchmark tool, Aug 2019. →pages 19[ATGW15] Miltos Allamanis, Daniel Tarlow, Andrew Gordon, and Yi Wei. Bimodalmodelling of source code and natural language. In Proceedings of the 32ndInternational Conference on Machine Learning, volume 37, pages 2123–2132. Proceedings of Machine Learning Research, 2015. → pages 24[AZLY18] Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav. A general path-based representation for predicting program properties. In Proceedings ofthe 39th ACM SIGPLAN Conference on Programming Language Design andImplementation, page 404–419. Association for Computing Machinery, 2018.→ pages 2, 24, 35[BCB15] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machinetranslation by jointly learning to align and translate. In 3rd InternationalConference on Learning Representations, 2015. → pages 22, 44[BGB+17] Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin,and Daniel Tarlow. Deepcoder: Learning to write programs. InProceedings International Conference on Learning Representations 2017.OpenReviews.net, 2017. → pages 2466Bibliography[BRV16] Pavol Bielik, Veselin Raychev, and Martin Vechev. Phog: Probabilisticmodel for code. In Proceedings of The 33rd International Conference onMachine Learning, volume 48, pages 2933–2942. Proceedings of MachineLearning Research, 2016. → pages 24[CGCB14] Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio.Empirical evaluation of gated recurrent neural networks on sequencemodeling. In NIPS 2014 Workshop on Deep Learning, December 2014, 2014.→ pages 17, 19[CvM14] Kyunghyun Cho and Bart van Merrienboer. Learning phrase representationsusing rnn encoder-decoder for statistical machine translation. In Proceedingsof the 2014 Conference on Empirical Methods in Natural LanguageProcessing (EMNLP), pages 1724–1734, 2014. → pages 43[DL14] Michael Denkowski and Alon Lavie. Meteor universal: Language specifictranslation evaluation for any target language. In Proceedings of the NinthWorkshop on Statistical Machine Translation, pages 376–380. Associationfor Computational Linguistics, 2014. → pages 49, 50[HAM10] Sonia Haiduc, Jairo Aponte, and Andrian Marcus. Supporting programcomprehension with source code summarization. In Proceedings of the 32ndACM/IEEE International Conference on Software Engineering - Volume 2,page 223–226. Association for Computing Machinery, 2010. → pages 24[HIGH16] Tjalling Haije, Bachelor Opleiding Kunstmatige Intelligentie, E Gavves, andH Heuer. Automatic comment generation using a neural translation model.Inf. Softw. Technol, 55(3):258–268, 2016. → pages 2, 24[HLWM20] Sakib Haque, Alexander LeClair, Lingfei Wu, and Collin McMillan.Improved automatic summarization of subroutines via attention to filecontext. ACM, 2020. → pages 24[HLX+18a] Xing Hu, Ge Li, Xin Xia, David Lo, and Zhi Jin. Deep codecomment generation. In Proceedings of the 26th Conference on ProgramComprehension, ICPC ’18, page 200–210. Association for ComputingMachinery, 2018. → pages 5, 8, 24, 25, 26, 35, 36, 46, 47, 64[HLX+18b] Xing Hu, Ge Li, Xin Xia, David Lo, Shuai Lu, and Zhi Jin. Summarizingsource code with transferred api knowledge. In Proceedings of the 27thInternational Joint Conference on Artificial Intelligence, IJCAI’18, page2269–2275. AAAI Press, 2018. → pages 45, 47, 51, 55, 56[HLX+20] Xing Hu, Ge Li, Xin Xia, David Lo, and Zhi Jin. Deep code commentgeneration with hybrid lexical and syntactical information. EmpiricalSoftware Engineering, Springer, 25(3):2179–2217, 2020. → pages 3, 25,36, 42, 43, 44, 47, 48, 53, 55, 5867Bibliography[HS97] Sepp Hochreiter and Ju¨rgen Schmidhuber. Long short-term memory. Neuralcomputation, 9(8):1735–1780, 1997. → pages 17[IKCZ16] Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer.Summarizing source code using a neural attention model. In Proceedings ofthe 54th Annual Meeting of the Association for Computational Linguistics(Volume 1: Long Papers), pages 2073–2083. Association for ComputationalLinguistics, 2016. → pages 5, 7, 24, 35, 36[KMCA06] Andrew J Ko, Brad A Myers, Michael J Coblenz, and Htet Htet Aung.An exploratory study of how developers seek, relate, and collect relevantinformation during software maintenance tasks. IEEE Transactions onsoftware engineering, 32(12):971–987, 2006. → pages 24[Kos19] Simeon Kostadinov. Understanding encoder-decoder sequence to sequencemodel. Towards Data Science Article, Nov 2019. → pages 21[LGR+21] Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy,Ambrosio Blanco, Colin B. Clement, Dawn Drain, Daxin Jiang, Duyu Tang,Ge Li, Lidong Zhou, Linjun Shou, Long Zhou, Michele Tufano, Ming Gong,Ming Zhou, Nan Duan, Neel Sundaresan, Shao Kun Deng, Shengyu Fu, andShujie Liu. Codexglue: A machine learning benchmark dataset for codeunderstanding and generation. CoRR, abs/2102.04664, 2021. → pages 45,51[LHWM20] Alexander LeClair, Sakib Haque, Lingfei Wu, and Collin McMillan.Improved code summarization via a graph neural network. In Proceedings ofthe 28th International Conference on Program Comprehension, pages 184–195, 2020. → pages 25[Lin04] Chin-Yew Lin. ROUGE: A package for automatic evaluation of summaries.In Text Summarization Branches Out, pages 74–81, Barcelona, Spain, 2004.Association for Computational Linguistics. → pages 49[LJM19] Alexander LeClair, Siyuan Jiang, and Collin McMillan. A neural modelfor generating natural language summaries of program subroutines. InProceedings of the 41st International Conference on Software Engineering,ICSE ’19, page 795–806, 2019. → pages 24[LSLW16] Yang Liu, Chengjie Sun, Lei Lin, and Xiaolong Wang. Learning naturallanguage inference using bidirectional lstm model and inner-attention. arXivpreprint arXiv:1605.09090, 2016. → pages 2[LVD06] Thomas D LaToza, Gina Venolia, and Robert DeLine. Maintaining mentalmodels: a study of developer work habits. In Proceedings of the 28thinternational conference on Software engineering, pages 492–501, 2006. →pages 2, 2468Bibliography[MAS+13] Laura Moreno, Jairo Aponte, Giriprasad Sridhara, Andrian Marcus, LoriPollock, and K. Vijay-Shanker. Automatic generation of natural languagesummaries for java classes. In 2013 21st International Conference onProgram Comprehension (ICPC), pages 23–32, 2013. → pages 24[Phi20] Michael Phi. Illustrated guide to lstm’s and gru’s: A step by stepexplanation. Medium, Jun 2020. → pages 18[Pru¨18] Heinz Pru¨fer. Neuer beweis eines satzes u¨ber permutationen (a new prof.of a theorem on permutations). Archiv der mathematik und Physik, 3:27,1918. → pages 12[PRWZ02] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: amethod for automatic evaluation of machine translation. In Proceedings ofthe 40th Annual Meeting of the Association for Computational Linguistics,pages 311–318. Association for Computational Linguistics, 2002. → pages48[RBV16] Veselin Raychev, Pavol Bielik, and Martin Vechev. Probabilisticmodel for code with decision trees. In Proceedings of the 2016 ACMSIGPLAN International Conference on Object-Oriented Programming,Systems, Languages, and Applications, page 731–747. Association forComputing Machinery, 2016. → pages 24[RBVK16] Veselin Raychev, Pavol Bielik, Martin Vechev, and Andreas Krause.Learning programs from noisy data. In Proceedings of the 43rd Annual ACMSIGPLAN-SIGACT Symposium on Principles of Programming Languages,page 761–774. Association for Computing Machinery, 2016. → pages 24[SHM+10] Giriprasad Sridhara, Emily Hill, Divya Muppaneni, Lori Pollock, andK Vijay-Shanker. Towards automatically generating summary comments forjava methods. In Proceedings of the IEEE/ACM international conferenceon Automated software engineering, pages 43–52, 2010. → pages 2, 24[SVL14] Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence to sequencelearning with neural networks. In Proceedings of the 27th InternationalConference on Neural Information Processing Systems - Volume 2, NIPS’14,page 3104–3112. MIT Press, 2014. → pages 20, 42, 44, 46, 47[TSK+20] Amirsina Torfi, Rouzbeh A Shirvani, Yaser Keneshloo, Nader Tavaf, andEdward A Fox. Natural language processing advancements by deep learning:A survey. Turkish Journal of Computer and Mathematics Education, 2020.→ pages 1[TSM15] Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improvedsemantic representations from tree-structured long short-term memorynetworks. In Proceedings of the 53rd Annual Meeting of the Association69Bibliographyfor Computational Linguistics and the 7th International Joint Conferenceon Natural Language Processing (Volume 1: Long Papers), pages 1556–1566.Association for Computational Linguistics, 2015. → pages 25[Tur50] A. M. Turing. Computing machinery and intelligence. Mind, 59(236):433–460, 1950. → pages 1[Wes00] Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2000. →pages 12[WY18] Lili Wang and Hongwu Yang. Tibetan word segmentation method basedon bilstm crf model. In 2018 International Conference on Asian LanguageProcessing (IALP), pages 297–302. IEEE, 2018. → pages 2[WZY+18] Yao Wan, Zhou Zhao, Min Yang, Guandong Xu, Haochao Ying, Jian Wu,and Philip S. Yu. Improving automatic source code summarization via deepreinforcement learning. pages 397–407, 2018. → pages 24[XBL+18] Xin Xia, Lingfeng Bao, David Lo, Zhenchang Xing, Ahmed E. Hassan,and Shanping Li. Measuring program comprehension: A large-scale fieldstudy with professionals. In Proceedings of the 40th International Conferenceon Software Engineering, page 584. Association for Computing Machinery,2018. → pages 23, 24[XMQ+19] Guixian Xu, Yueting Meng, Xiaoyu Qiu, Ziheng Yu, and Xu Wu. Sentimentanalysis of comment texts based on bilstm. IEEE Access, 7:51522–51532,2019. → pages 2[YJL+16] Jun Yin, Xin Jiang, Zhengdong Lu, Lifeng Shang, Hang Li, and XiaomingLi. Neural generative question answering. In Proceedings of the Workshopon Human-Computer Question Answering, pages 36–42. Association forComputational Linguistics, 2016. → pages 2[ZWZ+19] Jian Zhang, Xu Wang, Hongyu Zhang, Hailong Sun, Kaixuan Wang, andXudong Liu. A novel neural source code representation based on abstractsyntax tree. In Proceedings of the 41st International Conference on SoftwareEngineering, page 783–794. IEEE Press, 2019. → pages 25[ZWZ+20] Jian Zhang, Xu Wang, Hongyu Zhang, Hailong Sun, and Xudong Liu.Retrieval-based neural source code summarization. In Proceedings of theACM/IEEE 42nd International Conference on Software Engineering, page1385–1397. Association for Computing Machinery, 2020. → pages 2, 2470. Appenidx A : Abstract Syntax Tree Table GenerationAppendicesAppenidx A : Abstract Syntax Tree Table Generation1 import json2 import csv34 def Prufer_(cur_root_id, node_list):5 cur_root = node_list[cur_root_id]6 list1=[]7 list2=[]8 tmp_list = []9 tmp_list.append("(")10 val=" "1112 if 'children' in cur_root:13 str1 = cur_root['type']14 elif 'children' not in cur_root:15 str1 = cur_root['type']+" "+cur_root['value']1617 tmp_list.append(str1)18 if 'children' in cur_root:19 if 'value' in cur_root:20 val=cur_root["value"]21 #print(val)22 elif 'value' not in cur_root:23 val="XXX"24 #print(val)25 chs = cur_root['children']26 with open("train-prufer.csv", "a") as f:27 writer = csv.writer(f)28 for x in chs:29 writer.writerow((cur_root['id'],x,cur_root['type'],val))3031 for ch in chs:32 tmp_list.extend(Prufer_(ch, node_list))33 elif 'children' not in cur_root:34 with open("train-prufer.csv", "a") as f1:35 writer1 = csv.writer(f1)36 writer1.writerow((cur_root['id'],cur_root['id'],cur_root['type']+" "+cur_root['value'],37 cur_root['value']))38 tmp_list.append(")")39 tmp_list.append(str1)71. Appenidx A : Abstract Syntax Tree Table Generation40 return tmp_list4142 def get_prufer_structure(ast_file, out_file):43 count=144 with open(ast_file, 'r') as ast_file:45 with open(out_file, 'w+') as out:46 asts = ast_file.readlines()47 for a in asts:48 #count=count+149 #print(count)50 check1=[]51 check2=set()52 a = json.loads(a)53 #print(set(range(0,len(a))))54 for i1 in a:55 if 'children' in i1:56 check1.append(i1["children"])57 ko=i1["children"]58 for i in ko:59 check2.add(i)60 #print(set(check1))61 check2.add(0)62 if set(check2) == set(range(0,len(a))):63 count=count+164 tmp_list=Prufer_(0,a)65 out.write(' '.join(tmp_list) + '\n')66 print(count)67 if set(check2) != set(range(0,len(a))):68 print("not equal")69 val=input("value ")7071 get_Prufer_structure("train_code", "train.token.ast2640.txt")72. Appenidx B : Pru¨fer-Sequence GenerationAppenidx B : Pru¨fer-Sequence Generation1 import networkx as nx2 import re345 def prufercode(list1,list2,list3,count):678 try:9 if(len(list1)>0):10 list4=[]11 T = nx.Graph()12 T.add_nodes_from(list1)13 T.add_nodes_from(list2)14 edgeList = list(zip(list1,list2))15 edgeList1 = list(zip(list1,list2,list3))16 T.add_edges_from(edgeList,label = 1)17 T.remove_edges_from(nx.selfloop_edges(T))18 #degrees = [val for (node, val) in T.degree()]192021 list5=[]22 list6=[]2324 for (node, val) in T.degree():25 if val == 1:26 list5.append(node)2728 #print(T.number_of_nodes())293031 if T.number_of_nodes() <= 2:32 #k=nx.bfs_tree(T, 0)# for bfs33 #print(k)34 k=[1,0,0,1] #for prufer code3536 elif T.number_of_nodes() > 2:37 #k=nx.bfs_tree(T, 0)# for bfs38 k=nx.to_prufer_sequence(T) #for prufer code3940 n=len(T)4142 #print(count,set(T),set(range(n)))73. Appenidx B : Pru¨fer-Sequence Generation43 fruit_dictionary = dict(zip(list1, list3))444546 #print(fruit_dictionary)4748 for j in list5:49 finalstring=[]50 j1=fruit_dictionary[j]51 temp_trminal=j1.split()5253 if (len(temp_trminal)>1):54 temp_first=temp_trminal[0]55 finalstring.append(temp_first)5657 temp_second=temp_trminal[1]58 if (temp_second != "STR_" and temp_second != "NUM_" and temp_second != "BOOL_"59 and temp_second != "XXX" ):60 if (temp_second.isupper() != True):61 #temp_second=' '.join(re.sub( r"([A-Z])", r" \1", temp_second).split())62 temp_second=' '.join(re.split(',|\.',temp_second))63 temp_second= re.split('_+', temp_second)64 for count26400 in range(len(temp_second)):65 if (temp_second[count26400].isupper() != True):66 finalstring.append(' '.join(re.sub( r"([A-Z])", r" \1",67 temp_second[count26400]).split()))686970 #print(finalstring)7172 list6.append(' '.join(finalstring))7374 # list6.append(j1)7576 for i in k:77 z1=fruit_dictionary[i]78 list4.append(z1)7980 #print(list4)81 list4.extend(list6)# join the prufer code and termial code82 #print(list4)838485868774. Appenidx B : Pru¨fer-Sequence Generation8889 #print(list4)90 print(count)91 with open("train-prufer-sequence-26NOV","a")as outfile:92 outfile.write(' '.join(map(str,list4))+'\n')9394 except Exception as e:95 n=len(T)96 print(count,set(T),set(range(n)))97 print(e)98 val=input("enter the value ")99100101 import pandas as pd102103 list1=[]104 list2=[]105 list3=[]106 mid=[]107 fd=pd.read_csv("train-prufer.csv",header=None)108109110 pre=0111 count=0112113 for i,j,k in zip(fd[0],fd[1],fd[2]):114 if(pre <= i):115 list1.append(i)116 list2.append(j)117 list3.append(k)118 pre=i119 elif(pre > i ):120 prufercode(list1,list2,list3,count)121 count=count+1122 list1=[]123 list2=[]124 list3=[]125 list1.append(i)126 list2.append(j)127 list3.append(k)128 pre=0129130 prufercode(list1,list2,list3,count)75. Appenidx C: Context of Code GenerationAppenidx C: Context of Code Generation1 import networkx as nx2 import re3 from networkx.algorithms.traversal.depth_first_search import dfs_tree45 def neighbourt(T,item,st1,list1,list2):6789 for n1 in T.neighbors(item):10 if n1 > item and T.degree(n1)> 1:11 #print(n1)12 st1=st1+neighbourt(T,n1,st1,list1,list2)13141516 elif n1 > item and T.degree(n1)==1:17 fruit_dictionary1 = dict(zip(list1,list2))18 ab=fruit_dictionary1[n1]19 st1=st1+str(ab)+"_"20 #return st121222324 return st1252627 def prufercode_context(parent_node_list,child_node_list,explanation_node,context_node,count):2829 List_of_Item=[MethodInvocation,StatementExpression,30 ForStatement, SwitchStatementCase,31 WhileStatement,IfStatement,32 TryStatement,ReturnStatement,33 LambdaExpression]3435 try:36 t=""37 tj=""38 if(len(list1)>1):39 list4=[]40 T = nx.Graph()41 T.add_nodes_from(parent_node_list)42 T.add_nodes_from(child_node_list)76. Appenidx C: Context of Code Generation43 edgeList = list(zip(parent_node_list,child_node_list))44 edgeList1 = list(zip(parent_node_list,child_node_list,explanation_node))45 edgeList2 = list(zip(parent_node_list,child_node_list,explanation_node,context_node))46 T.add_edges_from(edgeList,label = 1)47 T.remove_edges_from(nx.selfloop_edges(T))4849 nei=[]50 list5=[]51 list6=[]5253 for (node, val) in T.degree():54 if val == 1:55 list5.append(node) # collect all terminal nodes5657 if T.number_of_nodes() <= 2:58 k=[1,0,0,1]5960 elif T.number_of_nodes() > 2:61 k=nx.to_prufer_sequence(T)6263 #print("hello0",count)6465 ######---------########6667 list_of_neighbour=[]68 finallist_of_neighbour=[]69 for eachitem in k:70 if eachitem != 0:71 st12=""72 fruit_dictionary23 = dict(zip(parent_node_list, explanation_node))73 ab23=fruit_dictionary23[eachitem]74 #print(ab23)75 if ab23 in List_of_Item:76 list_of_neighbour.append(ab23+"_")77 else:78 k1=neighbourt(T,eachitem,st12,list1, list2)79 list_of_neighbour.append(k1)808182 elif eachitem == 0:83 list_of_neighbour.append("0"+"_")8485 #print(count)86 #print(fruit_dictionary23)87 #print(list_of_neighbour)77. Appenidx C: Context of Code Generation888990 set1={}91 set2={}929394 #print(list_of_neighbour)95 Context_from_dictionary=""96 context_string=" "97 context_list=[]98 for obs in list_of_neighbour:99 #print(len(list_of_neighbour))100 set1=obs.split("_")101 #print("hello1",count)102 finallist_of_neighbour.append(set(set1))# after removing the duplicates103104105106 #print(finallist_of_neighbour)107108109110111112 fruit_dictionary66 = dict(zip(parent_node_list,context_node))113 fruit_dictionary77 = dict(zip(explanation_node,context_node))114 for each_neighbour_list in finallist_of_neighbour:115 for each_item in each_neighbour_list:116 if each_item !='':117 if each_item in List_of_Item:118 Context_from_dictionary=fruit_dictionary77[each_item]119 if Context_from_dictionary != 'XXX':120 Context_from_dictionary=each_item+" "+Context_from_dictionary121 elif Context_from_dictionary == 'XXX':122 Context_from_dictionary=each_item123124 #print(each_item,"\n",fruit_dictionary77)125 else:126 Context_from_dictionary=fruit_dictionary66[int(each_item)]127 try:128 context_string=context_string+Context_from_dictionary+" "129130 except:131 context_string=context_string+"nan1"+" "132 #val=input("error of NAN ")78. Appenidx C: Context of Code Generation133134 context_string=context_string+" "135 pos_of_context=context_string.split()136 for i in range(len(pos_of_context)):137 temp1=pos_of_context[i]138 temp1=' '.join(re.split(',|\.',temp1))139 temp1= re.split('_+',temp1)140 for j in range(len(temp1)):141 temp2=temp1[j]142 if temp2 in context_list_constant:143 context_list.append(temp2)144145 elif temp2 not in context_list_constant:146 if (temp2.isupper() != True):147 temp2=' '.join(re.sub( r"([A-Z])", r" \1", temp2).split())148 context_list.append(temp2)149150151152153 print(len(context_list))154 #val=input("next ")155 context_string=""156 #print(context_list)157 #val=input("enter the value ")158 print("hello1",count)159 with open("context_of_program_for_train_TLCodeSum","a")as outfile:160 outfile.write(' '.join(map(str,context_list))+'\n')161 with open("prufer_of_program_for_train_TLCodeSum","a")as outfile:162 outfile.write(' '.join(map(str,k))+'\n')163164165166 except Exception as e:167 #n=len(T)168 #print(count,set(T),set(range(n)))169 #print(t,"\n",tj,fruit_dictionary66)170 print("ekllo",e)171 val=input("enter the value ")172173174175 import pandas as pd176177 list1=[]79. Appenidx C: Context of Code Generation178 list2=[]179 list3=[]180 list4=[]181 mid=[]182183 # put this part above the Context geertation part and download the XC part184185 context_list_constant=[]186187 with open("xc","r",encoding="utf-8")as r1:188 t1=r1.readlines() #vocab.code189 for i in range(len(t1)):190 context_list_constant.append(t1[i].replace('\n',''))191192 print(context_list_constant)193194 #--------------------------------------------------------------------------195196197 fd=pd.read_csv("train-prufer.csv",header=None)198199200 pre=0201 count=0202203 for i,j,k,l in zip(fd[0],fd[1],fd[2],fd[3]):204 if(pre <= i):205 list1.append(i)206207 list2.append(j)208209 list3.append(k)210211 list4.append(l)212 pre=i213 elif(pre > i ):214 prufercode_context(list1,list2,list3,list4,count)215 count=count+1216 list1=[]217 list2=[]218 list3=[]219 list4=[]220 list1.append(i)221222 list2.append(j)80. Appenidx C: Context of Code Generation223224 list3.append(k)225226 list4.append(l)227228 pre=0229230 prufercode_context(list1,list2,list3,list4,count)81
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Gao, Yong
Code representation learning with Prüfer sequences
Text