Computer Science students often have to program exercises to practice and gain insights, to be then submitted for grading and feedback by instructors. The submission and grading process may be partly automated, for instance by requiring electronic submission and running automated tests on answers; but is mostly a laborious and manual process. Data collected by such systems can be of significant use for learning analytics, helping teachers to better understand how their students have attempted to solve exercises.
When learning Computer Science, many subjects include practical exercises that involve programming. Often, students submit these exercises using generic VLEs (Virtual Learning Environments), such as Moodle; other times, programming-specific submission environments are used, which may include automated tests to be run on submissions.
In the authors’ institution, several courses make use of the Domjudge1 system to automatically judge submissions by students. Typically, problem statements include only a sample of the full number of test-cases that will be used, so submissions to a problem are often correct for samples, but incorrect for the full set. It is frequent for students to send multiple answers, each time making changes to their source-code in an attempt to fix it account for the hidden test-cases. Figure 1 illustrates the teacher dashboard for a domjudge installation; note that some students have sent the same exercise over 10 times. Teachers will often only look at the last submission for grading purposes. CEUR Workshop Proceedings
Our initial goal was to develop a simple system that could provide insights into how students
learn to program, by analyzing how their answers changed over time. A very simple approach
would be to use something similar to Unix’s dif [
The next section describes our approach to making submission history for a single user easier to understand for teachers, by combining existing similarity-detection code with syntax trees for the specific languages used in these exercises. We then describe results of running a prototype of the tool on actual submissions from a Data Structures course. Finally, conclussions and future work outline how the tool could be adapted to facilitate other learning analytics tasks. 2For example, https://semanticdiff.com (commercial) appears to provide semantic visual difs for several languages
To compare program semantics instead of their textual contents, knowledge of the programming language is required. Programs can be viewed at two very distinct level: at a lower, sintactical level, tokenizing a source-file allows it to be viewed as a sequence of tokens rather than a sequence of characters. At a higher level, programs can be analyzed as trees of related tokens, grouped into declarations, loops, loop conditions, methods, and so on. These trees are often termed abstract syntax trees (ASTs), and the process of converting source-code into trees that retain their semantics is termed parsing. ASTs can be used not only for compiling or interpreting source-code, but also to analyze programs and transform program constructs.
Source-code parsing is a well-understood topic in computer science. Given a suitable grammar
indicating how to parse source-code into ASTs, there are multiple well-known parser-generation
programs that can generate the corresponding parsers for those grammars. One such program
is Antlr 4 [
Software similarity is often used in academic contexts to locate, and thus deter, plagiarism.
Students that know that there is a high chance that plagiarism will get caught will think
twice before presenting work of others as theirs. There is substantial literature on the subject
if plagiarism, with reviews such as Karnalim’s [
A simple and robust technique to detect code similarity, not present in Karnalim’s review,
relies on analyzing the entropy between sources: similar source-code will, when compressed by
a high-quality compressor, compress better than totally unrelated code. For a more in-depth
analysis of NCD (Normalized Compression Distance), see [
We have built the prototype described in this work on top of AC24, an existing open-source
plagiarism detector with robust similarity detection [
In this work, we describe an extension to AC2 which uses parse trees to annotate diferences between subsequent versions of a given submission. After building the ASTs of a submission, it is possible to compare semantically-significant parts of submissions instead of simple concate3As of june 2023, there are over 250 grammars at https://github.com/antlr/grammars-v4. 4AC2 is available at https://github.com/manuel-freire/ac2 nations of files. The smallest segments of program ASTs where changes are located can be used to generate semantically-significant labels for diferent versions of a single submission. For example, if a single conditional has changed, then the label describing that version increment could be
Condition changed in Tree.cpp::find_smallest: - if (i <= size) { + if (i < size) { 2.1. Prototype The prototype first downloads submissions from a Domjudge server, which results in a set of folders, one per problem (columns in Fig. 1). Inside each problem-folder there is another folder for each student that has attempted to solve it; and inside each student folder, there is an additional per-submission folder. The prototype then uses a parse-tree aware version of AC2 to compare, within each student-folder, each submission to the next one. Output describing these diferences is generated to a text-file and placed in the student-folder.
To compare two submissions, both are first parsed into ASTs, which must then be aligned
to locate exactly what each change corresponds to. The problem of matching trees has been
examined, for example, in [
The result of aligning two trees and is therefore, for each subtree of , a corresponding subtree of that is either identical or considered as the most similar available. The last step of the process simply generates a textual descripiton of the diferences between non-identical alignments. Additionally, the annotation process must also describe elements in that have not been matched to as being newly added; and a similar consideration should be made for elements in that have entirely dissapeared from .
The following pseudocode illustrates these steps: let astA = parse(submissionA); let astB = parse(submissionB); let hashesA = recursiveHash(astA); let hashesB = recursiveHash(astB); let alignmentAB = align(astA, astB, hashesA, hashesB); annotate(alignmentAB);
We have tested the prototype annotation tool on a set of submissions by 17 distinct students for 10 problems (partly illustrated in Fig. 1), with a total of 445 submissions from those students attempting to solve the problems, from which a total of 109 were correct and the remainder returned either compiler-error (73), run-time error (83), time-limit exceeded (27), wrong-answer (146), or no-output (7). The students were enrolled in a course on Data Structures in a university in Madrid, Spain.
The prototype annotated the 449 submissions (with 1919 C++ files in total) in under 15
seconds; performance can certainly be improved, for example by caching parse-trees for files
that were part of the problem statements, such as implementations of common abstract data
types. For each set of sequential submissions by a student, the tool generates a file that describes
what changed from each submission to the next. A sample file is included below (student I04,
problem 473):
[
New @BinTree.h::: (10171-char patch)
[
New @Exceptions.h::: (1581-char patch)
[
New @Queue.h::: (4857-char patch) New @List.h::: (11732-char patch)
In the above file, the student forgot to include several dependencies, leading to compiler
errors. In the 4th version, the final 2 dependencies were included, leading to a veredict of correct
by the online judge. Large changes (currently limited to 1024 characters), such as the contents
of new files, are hidden by default. In the next example (student I08, problem 478), each change
describes the method of the class that encompasses the relevant code, providing important
context for a grader familiar with the template used by students:
[
Modified @template.cpp::Bank::transfer(int line, string source, string target, int quantity): @@ -25,5 +25,5 @@ // Iterate map in alphabetical order and output money in non-empty, non-* accounts for (auto it = accounts.cbegin(); it != accounts.end(); it++) { - if ((it.key() != "*") && (it.value() > 0)) { + if (!(it.key() == "*") && (it.value() > 0)) {
cout << it.key() << " " << it.value() << endl; }
While the prototype generates readable descriptions of changes in submissions, it is currently experimental code, and will require significant work before being made available for other teachers in the author’s institution that use Domjudge for exercises. Each year, over 300 students from the author’s institution enroll in subjects that make heavy use Domjudge. Their submissions mostly remain on the server hosting the judge, and we plan to enroll their teachers to test future versions of our tool.
From the point of view of user experience, having to read a large numbers of text files is still work, even if each file manages to quickly describe how several submissions have evolved over time. Additionally, using a fixed cutof-point to hide details, while often useful, can also hide important details – presenting the information interactively on demand, say within a web application, would result in a better user experience than having to look up additional information by pointing an IDE to the actual source files.
The prototype used for the above case-study does provide readable overviews of what has changed in submissions to a given problem over time. This makes it possible for teachers to gain quick overviews of large sets of (similar) submissions from a single author attempting to solve a single problem, opening a large number of collected submissions to potential analysis to better understand how students learn programming. However, the extent to which these overviews are efective at their goal of making it easier for teachers to understand how their students learn can only be measured by further experiments.
Beyond the application presented here, we consider that there is significant potential for
tools that can automatically annotate diferences in code submissions. The following additional
use-cases come to mind:
1. Automated labelling of changes could be used to auto-generate descriptions of changes
for version-control systems. Knowing which functions and data-structures were changed
by a commit can be much more useful than only knowing the files that were modified.
2. Plagiarism detection can greatly benefit from automatic alignment. For example, when
looking at submissions from two students, it is useful to show which code from student
best corresponds to a given fragment of code by student . This could also be used to
describe the steps that could have taken to cover their tracks.
3. If code snapshots are collected periodically while students are solving a coding exercise,
it may be possible to generate interesting insights into how students learn to code. In [
There also remain multiple hurdles to this vision of semantic labelling of code diferences. The general problem of finding the most human-readable description of the diferences between two programs is not solvable by traditional programs. Any approach will have to rely on reasonable heuristics for common cases, which however can be extremely efective if and when their preconditions are met. For example, in this paper we rely on an expectation for small amounts of changes between subsequent versions of submissions. In many cases, this is indeed the case, and short and readable descriptions can be succesfully generated. However developing good heuristics can take time, and heuristics are, by nature, fragile.
Future work will include an improved version of the tool, and larger experiments testing both its efectiveness and usability.
Co-funded by the Ministry of Education (PID2020-119620RB-I00) and by the TelefónicaComplutense Chair on Digital Education and Serious Games.