A Comparison of Three Program Query Languages to Detect Python Programming Misconceptions

Teachers of programming courses are often aware of frequent mistakes that students make when learning to program, and of the underlying misconceptions that cause those mistakes. However, using just unit tests they may struggle to write program queries to automatically detect such mistakes. Providing a comparison of multiple program query tools could help teachers find the best tool to detect symptoms of misconceptions in their students’ code.

In the context of computer science education, a programming misconception is defined as an incorrect understanding of a programming concept that leads to systematic errors in code comprehension or development. These misconceptions may be affected by, amongst others, learners’ prior knowledge from domains other than programming, such as mathematics or natural language, which they inappropriately transfer to programming contexts. [8, 9] Chiodini et al. [1] further refine this by defining a programming language misconception as “a statement that can be disproved by reasoning entirely based on the syntax and/or semantics of a programming language”. This is also the definition we will adopt in this paper.

A misconception is a cognitive construct, an incorrect or incomplete mental model of how a programming language feature works. Understanding and addressing these misconceptions is crucial, as they can significantly hinder the learning process and the development of accurate programming skills. However, program code reflects only symptoms of these misunderstandings, such as systematic errors or incorrect patterns. While advanced program analysis tools cannot directly access a student’s thought process, they can infer likely misconceptions with some confidence by identifying recurring patterns of mistakes.

An example of a programming misconception, illustrated in Listing 1, is InitShouldReturn²²2This is a variant of the InitReturnsObject misconception documented on https://progmiscon.org/misconceptions/Python/InitReturnsObject/. (ISR) . Students having this misconception incorrectly asume that an __init__ method in a Python class should explicitly return a value using a return statement.

Being able to automatically detect such symptoms would enable teachers to provide more direct and precise feedback to students, helping them to correct their mistakes and misunderstandings, leading to faster and more accurate learning.

The primary objective of this paper is to evaluate and compare different languages and tools for detecting symptoms of programming misconceptions in students’ Python programs, in terms of accuracy, performance, expressiveness, learning curve, and other relevant criteria. Our goal is to identify which tools are most suitable from different perspectives and which languages make it easier to express and detect misconceptions.

To gather a representative set of misconceptions on which to conduct our comparison, we consulted misconceptions from multiple sources:

• $\mathrm{■}$

  Progmiscon [1], a website³³3https://progmiscon.org/ presenting over 200 misconceptions covering many basic programming concepts for Python, Java, Javascript and Scratch.

• $\mathrm{■}$

  Visual Program Simulation in Introductory Programming Education, a PhD dissertation by Juha Sorva [8], of which the Appendix A contains a catalogue of 162 misconceptions from 21 different sources.

• $\mathrm{■}$

  PythonTA [5], an educational code analysis tools building upon professional tools like “Pylint”. While primarily providing novice Python programmers feedback on syntactic and stylistic issues in their code, it can highlight patterns that may suggest consistent misuse of certain constructs, which could be considered symptomatic for certain misconceptions.

From theses sources, we filtered those misconceptions that did not adhere to our adopted definition of “misconception” (cf. Section 2), were not applicable to Python (e.g., the ones concerning primitive types) or were too abstract to be detectable by analysing program code only. We then classified the remaining 113 misconceptions after filtering into seven categories based on their nature and selected a representative subset of 20 misconceptions for which we could implemented detection queries using at least two of the three program querying tools we selected (cf. Section 3). Each of these 20 misconceptions are listed and defined in Table 1. We then analysed the accuracy and performance of these queries on a dataset of student code submissions from an introductory CS1 programming course. Additionally, we compared the tools based on more subjective criteria, including their learning curve and setup complexity, drawing from our own experience. The results of this comparison will be presented in Section 5.

To perform this study, we selected three different program query languages and tools:

Flake8

⁴⁴4https://flake8.pycqa.org/en/latest/

is a widely used Python static analysis tool that leverages the abstract syntax tree (AST) representation of Python code produced by Python’s ast module. It integrates multiple tools: PyFlakes for detecting logical errors, pycodestyle for enforcing PEP 8 style guidelines, and McCabe for measuring code complexity. This combination provides a robust framework for identifying style violations and potential issues in Python code. A key strength of Flake8 is its extensibility, allowing users to define and integrate custom checkers to detect more complex code patterns. While Flake8 is frequently compared to other static analysis tools [2, 7, 6, 3], most studies focus on its built-in rule set rather than its adaptability for domain-specific queries.

Regular Expressions

(Regex) are sequences of characters and symbols used to define search patterns within text, including source code. We include Regex in this comparison because of its key advantage over AST-based tools: it does not require constructing an abstract syntax tree before analysis. This allows it to process any code snippet, including those that contain syntax errors and would otherwise fail to compile. This capability is particularly relevant to our study, as students frequently make syntax errors that prevent AST-based static analysis tools from processing their code.

CodeQL

⁵⁵5https://codeql.github.com/

is a program query language and analysis tool currently developed by GitHub and mainly used for automating security checks and identifying vulnerabilities in code. It allows users to write SQL-like queries that operate on a code database, enabling pattern detection and data flow analysis. CodeQL requires the analysed code to be syntactically valid to construct its code database, making it similar to Flake8 and different from Regex in this regard.

Many other program query languages or tools that rely on static analysis could have been considered for this comparison, but we excluded them for various reasons:

SonarQube

⁶⁶6https://www.sonarsource.com/products/sonarqube/

provides static code analysis for multiple programming languages, identifying bugs, vulnerabilities, technical debt, and code quality metrics. However, its free community version has limitations and lacks customization options.

XPath and XQuery

⁷⁷7https://www.w3.org/TR/xpath-31/⁸⁸8https://www.w3.org/XML/Query/

along with other XML analysers, are designed for querying structured XML documents. They can be applied to Python code if transformed into XML, for example, using the srcML⁹⁹9https://www.srcml.org/ format. We opted against this approach to avoid the additional translation step and the use of non-code-specific XML query languages.

Pyttern [4]

is a program query language for Python that integrates Regex-like wildcards into a Python-like syntax to match coding patterns. Since it remains in a prototypical stage, we decided not to include it in our comparison at this time.

Pylint and astroid.

¹⁰¹⁰10https://www.pylint.org/¹¹¹¹11https://pypi.org/project/astroid/

We chose Flake8 with ast over Pylint with astroid as studies such as the one by Mohialden et al. [6] state that Flake8 analyses code “better and faster” than Pylint. Flake8 also makes plugins easier to write and incorporate to the default installation. The choice of the ast module was clear, as it is the preferred module to use alongside Flake8, in contrast to astroid with Pylint.

PythonTA [5]

is a free, open-source suite of educational code analysis tools aimed at novice Python programmers. We did not include it separately in our comparative study since it primarily builds upon existing tools like pylint, pycodestyle, and mypy.

The four following listings display an example of the ComparisonWithBoolLiteral (CWB) misconception, implemented using each of the three selected tools that we will compare in this study. The CWB misconception occurs when students believe they need to explicitly compare expressions to boolean literals (True/False) in conditions. An example of a student code suffering from this misconception would be the one of Listing 2.

In Listing 3 we use a visitor to walk over the parse tree looking for Compare nodes and checking if either the left-hand side of the comparison or the value being compared is either the Boolean value True or False.

The regular expression in Listing 4 looks for any occurrence of a Boolean literal (True or False) on either side of an (in)equality comparison.

The CodeQL query in Listing 5 looks for a comparison where either the left- or right-hand side is a boolean literal (True or False). We use the “don’t-care” character _ to allow for any comparator and any other value at the other side of the comparison.

Based on our experience of writing and running the various program queries we implemented in each of the three languages, we compared the queries and languages on the following criteria:

Accuracy

through the measure of precision, relative recall, and relative F1-score.

Performance

of executing the program queries; how fast does the tool perform?

Readability

of the program queries; is it easy to understand how they work and what they detect?

Expressiveness

of a language; for a given misconception, how easy is it to write a query that detects symptoms of that misconception?

Additional evaluation criteria, not based on individual program queries but rather on our overall assessment of each of the three languages were:

Scope

Can the language implement all or most of the desired symptoms?

Learning Curve

How much learning does it require before becoming efficient in using the language?

Setup Complexity

How long does it take before being able to start using the language?

Resources

How much and what’s the quality of the resources we can find online regarding the language?

To answer RQ1, the first main criterion for comparing the three languages is the accuracy of program queries written in each language. After applying a program query on a dataset of student submissions, on a maximum of 100 submissions that match the query, we check whether each of these correspond to true positives (TP) or false positives (FP). If a query detects more than 100 submissions containing the misconception, we assess precision using a random sample of 100 from those detected. We do not use the same sample across all three tools for two reasons: first, the intersection of submissions detected by all three tools might contain fewer than 100 submissions, limiting the sample size; second, a tool with higher precision would contribute more correct detections to the shared sample, increasing the perceived precision of the other tools. Furthermore, after applying all three program queries (one in each language) on the same dataset, we look at all submissions matched by at least one program query but not by another, as this may indicate a false negative (FN). We use this to calculate a relative recall, as calculating the actual recall on the entire dataset would require us to manually check every program in the entire dataset as an actual occurrence of the misconception or not. Given that we run the program queries for each misconception on a dataset of 3000 submissions, multiplied by the number of misconceptions we analysed, this would amount to having to manually analyse tens of thousands programs manually, which was not feasible. Once we evaluated the amount of false positives and false negatives as indicated above, we computed each query’s precision, relative recall and relative F1-score using the following formulas:

where $\widehat{FN}$ represents not the total amount of false negatives, but rather the amount of “relative” false negatives, i.e. those that were found by a program query for at least one language but not by a program query for another language.

The results obtained for these metrics for each language and on each misconception query are listed in Table 2. Flake8 seems to provide the best precision, Regex the best (relative) recall, and CodeQL the best (relative) F1 Score. Regex’s highest recall is compensated by its lowest precision, suggesting that it is less accurate by detecting more cases, but more false ones as well. The opposite occurs for Flake8 which has the highest precision but the lowest recall; it may miss more cases but the once it does find seem more accurate. CodeQL seems to provide a good tradeoff between precision and recall, which is confirmed further by the fact that it yields the best F1 Score.

Figure 1 displays the relative F1 Score obtained by each tool for each misconception. We chose not to display those misconceptions for which all languages had a perfect F1-score, to improve the readability of the graph. No obvious trend seems to emerge from this figure. There is no language that seems significantly better than the others for all misconceptions and the different languages seem to compete well. We do observe the phenomenon that for some misconceptions we did not manage to write a query in some of the languages.

To answer RQ2, a second criterion on which to compare the three languages is their performance. To compare their execution times, when applying our program queries to a dataset of students’ submissions, we also computed the time taken to analyse each submission, and summed everything to get the times displayed in Table 3.

Among the three tools, Flake8 seems by far the slowest in terms of performance. Regex appears to be the second slowest, but it is important to note that evaluating CodeQL’s runtime requires considering three distinct operations: the execution of the query, the compilation of the query and the creation of the code database. Table 3 reports the query execution (column *) separately from the query compilation and creation of the code database (column **), the latter being the most computationally intensive step. This process involves parsing the Python code to construct an AST and then generating the corresponding database, which incurs a significant cost if used only once. However, as the number of queries run on the same database increases, the amortized cost per query decreases. The time required to construct the database scales linearly with the number of files, as shown in Figure 2. In contrast, query compilation is considerably faster, as illustrated in Figure 3. Like the database, a query needs to be compiled only once and can then be executed multiple times without additional overhead.

It is worth noting that in this study, most student submissions are very short, rarely exceeding 30 lines. A possible future experiment would be to evaluate each tool on datasets with larger files or complete projects.

We now discuss the remaining evaluation criteria and in particular expressiveness of the language (RQ3), by discussion the strengths and weaknesses of each language separately based on our personal experience with writing queries in that language. In this study, the expressiveness of a language refers to how effectively and intuitively it allows users to define (writability) and read (readability) queries for detecting specific misconceptions. We aimed to be as objective as possible when evaluating this criterion, but individual experiences with a language can vary a lot depending on the developer’s prior knowledge. An interesting future experiment would be to request a panel of teachers to use each of these languages to implement or interpret a set of misconceptions to understand which language’s expressiveness outshines the others.