Analysis of Program Representations Based on Abstract Syntax Trees and Higher-Order Markov Chains for Source Code Classification Task  
[PERSON]  
1  
[PERSON]  
1  
[PERSON]  
1  
Footnote 1: email: {[EMAIL_ADDRESS]}  
Footnote 2: email: {[EMAIL_ADDRESS]}  
Footnote 3: email: {[EMAIL_ADDRESS]}  
Footnote 4: email: {[EMAIL_ADDRESS]}  
Footnote 5: email: {[EMAIL_ADDRESS]}  
Footnote 6: email: {[EMAIL_ADDRESS]}  
Footnote 7: email  
consider the publicly available dataset [19] containing source codes of 13,881 small Python programs solving unique programming exercises of 11 different types; the unique exercises were automatically generated by the Digital Teaching Assistant (DTA) system [20]. The solutions to the exercises were submitted to DTA by Python programming course students, and the students were allowed to use any algorithm to solve a task of a given type. The programs from the dataset were successfully checked and accepted by the DTA system, and the classifiers were trained to predict the task type solved by a program based on its source code. Prior to the application of a classification algorithm to the task detection problem, a feature extraction technique has to be applied to the source code dataset, with the aim of extracting only those source code features that are relevant in the considered problem domain. Source code transformation into vector-based representations is a widely applied feature extraction technique [7; 9; 18; 21] that makes it possible to statically analyze software using machine learning algorithms such as multilayer perceptron [22], complex neural networks such as convolutional neural networks (CNN) [23], support vector machines [24], and other algorithms that require vectors at their input. In this study we compare different approaches to source code transformation into vector-based representations, such as word2 vec [21; 25], code2 vec [9; 26; 27], histograms of CPython assembly language instruction opcodes [18; 28], histograms of abstract syntax tree (AST) node types, inspired by [28], and AST-based Markov chain models [15; 16]. Additionally, we propose a general algorithm for source code transformation into vectors based on higher-order Markov chains, and include AST-based Markov chains of order 1 and 2 into the comparative study. We aim to find answers to the following research questions (RQs):  
* RQ1: How does the size of the dataset and the selected approach to source code transformation into vector-based representation affect the quality of different classification algorithms in the task detection problem? * RQ2: Which of the considered approaches to source code transformation into vector-based representation is least sensitive to the used classification algorithm in the task detection problem? After obtaining vector-based representations of programs, we train and evaluate widely applied classification algorithms such as the k-nearest neighbor (KNN) algorithm [29; 30], support vector machine (SVM) [24], random forest (RF) [31], and multilayer perceptron (MLP) [22], using five-fold cross-validation to verify classifier quality. We assess classifier quality using multiclass classification quality metrics such as accuracy, recall, precision, and F1-score [32]. The results of the conducted research indicate that AST-based and opcode-based vectors outperform token-based vectors on small-sized and medium-sized source code datasets. The use of histograms of assembly language instruction opcodes, AST-based histograms, and Markov chains leads to high classifier quality, despite the simplicity of these approaches to transforming source code into vectors. Representations based on first-order Markov chain models are least sensitive to the used classification algorithm, and an RF-based classifier used with Markov chains leads to the best classification quality. The obtained results are verified using null hypothesis significance testing. The rest of the paper is structured as follows.