Recognizing Algorithms Using Language Constructs, Software Metrics and Roles of Variables: An Experiment with Sorting Algorithms

摘要

Program comprehension (PC) is a research field that has been extensively studied from different points of view, including human program understanding and mental models, automated program understanding, etc. In this paper, we discuss algorithm recognition (AR) as a subfleld of PC and explain their relationship. We present a method for automatic AR from Java source code. The method is based on static analysis of program code including various statistics of language constructs, software metrics, as well as analysis of roles of variables in the target program. In the first phase of the method, a number of different implementations of the supported algorithms are analyzed and stored in the knowledge base of the system as learning data, and in the second phase, previously unseen algorithms are recognized using this information. We have developed a prototype and successfully applied the method for recognition of sorting algorithms. This process is explained in the paper along with the experiment we have conducted to evaluate the performance of the method. Although the method, at its current state, is still sensitive to changes made to target algorithms, the encouraging results of the experiment demonstrate that it can be further developed to be used as a PC method in various applications, as an example, in automatic assessment tools to check the algorithms used by students, the functionality that is currently missing from these tools.