The Pyttern Program Query Language

Understanding and analysing the structure of source code is a fundamental task in software engineering, particularly for code comprehension, quality assessment, and code improvement. Existing tools for querying source code often require their users to master complex query languages or formal abstractions, which is a barrier to entry for practitioners without prior experience in such systems.

This paper focuses on Pyttern, a program query language specifically designed to facilitate pattern-based querying of Python code. Unlike many existing program query languages and tools, where queries often correspond to parse tree visitors, Pyttern is a language for expressing structural patterns in Python programs using a syntax that closely resembles that of Python. The language extends Python syntax with expressive, regular-expression-inspired wildcards, enabling intuitive queries that are easy to write and read. By maintaining syntactic similarity with Python, Pyttern minimises the learning curve, making it more accessible to junior developers and non-expert software engineers.

Pyttern is an expressive pattern language, which raises the important question of how to design an efficient algorithm for matching its expressive patterns to program code. Key design criteria for this matching algorithm include the following: (1) it should be sufficiently generic to facilitate adaptation to programming languages other than Python; (2) it should support an easy addition of additional constructs to the pattern language, such as named wildcards; and (3) the algorithm should be sufficiently efficient in practice.

Our initial language prototype [12] did not satisfy all these requirements yet. In this paper, we introduce an extended version that does. It uses a generic parser to construct a parse tree from the program code, thus making the approach applicable to any language with an existing parser. We then define a new matching algorithm that operates on these parse trees. This algorithm is based on a novel pushdown automaton for trees, which describes how the matcher traverses the parse tree of the program being matched. This automaton allows for a generic, efficient and maintainable implementation of the matching algorithm.

This paper has two main objectives: (1) to provide a detailed account of the implementation principles and theoretical foundations underlying a matching algorithm suitable for a language like Pyttern, and (2) to assess the usability of Pyttern through a new validation study involving junior developers. To achieve these objectives, we describe the language syntax, the design decisions that guided its implementation and then discuss its underlying implementation architecture and formalism. We then conduct an empirical evaluation in which 35 master’s students used Pyttern to express queries aimed at detecting seven known programming misconceptions.

The remainder of this paper is structured as follows: Section 2 provides background on related program query languages. Section 3 presents and illustrates the Pyttern language. Section 4 discusses Pyttern’s implementation architecture and underlying formalism. Section 5 presents our empirical validation and results and discusses the implications of our findings. Section 6 summarizes our contributions and outlines directions for future work.

In this section, before presenting our Pyttern language, we present some related languages that served as a source of inspiration for Pyttern’s language design and implementation.

First of all, code search engines and languages like FaCoY [8], Lancer [22], and SLAMPA [23] use code snippets as their query format and attempt to find matching or relevant code based on the given snippet. This philosophy that “code queries code” makes these search tools simpler and more developer-friendly than static analysis tools that require more structured queries. Such snippet-based methods allow natural code input instead of requiring developers to learn a complex query language, thus focussing on developer convenience, rather than deep program analysis with more exhaustive correctness guarantees.

Code with holes takes a more structured approach by supporting “holes” (placeholders) in queries. Instead of relying on a search engine to determine which code fragments match a given code snippet, this approach represents partial programs using variables or wildcards to specify unknown parts [16, 13, 14]. Some approaches extend this idea further by introducing custom query languages that significantly modify or extend an existing programming language [6, 9].

This contrasts with more traditional program query languages (like CodeQL [4, 20, 1] or Datalog-based tools [18]) and static analysis techniques that rely on explicitly structured queries (e.g., “Find all methods with an integer parameter and a return type of float”), graph-based representations of code (like ASTs, control-flow graphs, or program dependence graphs), or even abstract interpretation or other formal methods for deeper semantic reasoning.

De Roover et al.’s [17] program query language tries to achieve the best of both worlds by mixing a powerful logic-based query language with the possibility of including concrete source code templates as part of the queries, and matching these queries against a combination of structural and behavioural program representations, including call-graphs, points-to analysis results and abstract syntax trees. The idea is that the source code excerpts embedded in the logic queries act as prototypical samples of the structure and behaviour they intend to match. To use this approach, however, a developer is still required to be aware of the semantics of the underlying logic-based language and the various analysis techniques that it uses when matching queries, making it harder to use than pure snippet-based query languages.

The technique of regular expressions (RegEx) shares similarities with the concept of “code with holes” in that both allow for pattern-based matching with flexible or unknown components. Like code with holes which uses placeholders, regex wildcards (e.g., “.*”, “$\backslash$w+”) can be used to represent unspecified code fragments, enabling more flexible searches. Regular expressions, however, operate on flat text, whereas code with holes is typically applied at the abstract syntax tree (AST) level, allowing for structure-aware and semantically meaningful queries. This makes code with holes more expressive and precise than regex-based approaches, as it respects the syntactic and semantic rules of programming languages rather than relying solely on textual patterns.

Codegex [21] and many other program query languages and analysis tools [5, 2] leverage regular expressions to query and analyse program code. Many lint tools [7], as well as other program analysis tools, operate by first parsing source code into a tree representation and subsequently traversing this tree to examine the program’s structure.

Pyttern draws significant inspiration from SCRUPLE [16], a tool designed for querying C source code through high-level patterns. SCRUPLE introduces a symbolic representation that allows syntactic entities in C code to be substituted with placeholders (“holes”). The expressiveness of its pattern language stems from four key types of pattern symbols: wildcards representing individual syntactic entities, wildcards for groups of entities, named wildcards, and additional specialized features.

To perform pattern matching, SCRUPLE employs an extended nondeterministic finite state automaton referred to as the Code Pattern Automaton (CPA), which also operates on an input tree. SCRUPLE’s algorithm provided inspiration for the matching algorithm implemented in Pyttern. However, the full theoretical basis underlying SCRUPLE has not been published by its author [16] nor in follow-up work. We found in our earlier work [12] that knowledge of the details of this theoretical basis is crucial in a practical implementation. For instance, when matching labeled wildcards, it is important to define precisely how the automaton would treat such labeled wildcards. With our paper, we aim to provide pattern matching on generic parse trees a firmer theoretical basis that allows for efficient, generic and maintainable implementations of languages such as Pyttern and SCRUPLE, while also allowing for a deeper future theoretical analysis.

Pyttern’s goal is to provide a program query language that balances ease of use and expressiveness. It shares similarities with code snippet-based search engines, “code with holes” approaches, and other query languages that support concrete source code templates. Like these approaches, Pyttern aims to minimise the learning curve by staying close to the syntax of the programming language being analyzed. To make the language easy to learn, Pyttern’s syntax is a mere extension of Python syntax, augmented with dedicated wildcards for pattern matching. Despite its simplicity, Pyttern remains expressive, offering powerful wildcards inspired by regular expressions. It performs matching at the level of parse trees, ensuring robust and flexible pattern recognition beyond mere syntactic similarity.

The list of wildcards supported by Pyttern, our dedicated Python pattern matching query language, can be found in Table 1. We blend those wildcards within the Python language making it easy to learn for any developer that knows a bit of Python.

An example of a typical coding idiom in an imperative language like Python is an accumulator, of which an example is given in Listing 1. In essence, an accumulator pattern refers to a technique where one first initializes an accumulator variable (line 2), and then iterates over a sequence (line 4), updating the accumulator variable with the result of some operation during the iteration (line 6). In the end, the accumulator variable that retains the cumulative result of all these operations is returned as result (line 7).

The structure of this coding idiom can be expressed straightforwardly as a Pyttern pattern, as illustrated in Listing 2. The Pyttern pattern follows the syntax of a Python program, but with wildcards acting as placeholders for matches. For example, the function name, loop variable and sequence, and the value added to the accumulator are abstracted by a single node wildcard ? on lines 1, 4 and 6, respecitively. The accumulator variable is represented by a named wildcard ?accumulator on lines 2, 6 and 7, which ensures that in multiple places the same variable name is matched. The function’s parameter list on line 1 is abstracted by the ?* wildcard matching a list of nodes. And finally the ?:* wildcards on lines 3 and 5 provide the flexibility for the statements nested in the body of that wildcard to appear at any nesting level.

We now provide a more detailed explanation of the current implementation of Pyttern.

To validate our Pyttern language, we asked 35 CS master students to write Pyttern patterns, or pytterns in short, to detect symptoms of 7 distinct misconceptions in a dataset of potential answers to a first year bachelor course. Table 2 lists the different misconceptions for which we asked to write a pyttern. These misconceptions where selected based on a previous study that we made where we detected multiple patterns in student’s code [11]. We tried to make a selection of patterns with different level of complexity regarding the creation of pytterns.

To obtain a controlled test set, we generated 507 code samples containing symptoms of specific misconceptions for the first year bachelor course, using the technique described by Steveny et al. [19], which defines a set of transformations to be applied to a base code set. By iteratively applying these transformations, we produced a series of code samples which contain the various misconceptions to be detected. We also included dummy transformations that did not introduce any misconceptions, ensuring our test set to contain a mix of both relevant and irrelevant variations to the base code set. With this technique, eventually we obtained a validation set containing 132 (26%) programs with no misconceptions, 249 (49%) with one misconception and 123 (25%) with two different misconceptions.

Before starting to implement their “pytterns” we also asked our study participants about their background knowledge on some concepts related to programming and program analysis. We aggregated these results in Figure 4. From this graph, we can observe that our participants considered themselves quite knowledgeable in Python though not experts. They also have some knowledge on design patterns (from a software engineering course which they followed). However, they had little or no experience with using AST visitors or other program query languages to analyse programs for relevant structural patterns. We thus consider our study participants as non expert programmers with very limited background in program analysis.

To understand how non-expert programmers adopt and utilise Pyttern, we analysed the queries they implemented. An example of a pyttern they wrote is shown in Listing 3. This pyttern matches the InitReturnsObject misconception found in Listing 4. We compared their pytterns against a manually validated set of reference pytterns (written by the language designer). This evaluation intended to determine how well our study participants could write Pyttern patterns, comprehend the language’s syntax, and use the different wildcards provided by the language. We analysed their implementations to understand some of the challenges they faced and to get an idea of the learning curve of the language.

From the 35 students who attempted to use Pyttern, (only) 29 were able to write at least one valid pyttern, and 28 successfully matched at least one file (containing a misconception to be detected). We ran each student’s pytterns on our validation set and compared their results with our ground truth. Figure 5 presents a heatmap of F1 scores for the detection rate of each misconception across all files, allowing us to quickly identify which misconceptions students detected most effectively and which posed greater challenges.

From Figure 5 we can observe that certain misconceptions were consistently well-identified across most files, whereas others show lower F1 scores and appear more challenging to capture. In particular, some misconceptions display strong clustering of high scores, indicating that many students managed to write these patterns satisfactorily. These corresponded to patterns that could be defined with a simple Pyttern expression. Not surprisingly, the ones with lower score corresponded to patterns that required more complex pytterns or pytterns with more complex structures.

Meanwhile, Figure 6 displays a stacked bar plot of F1 scores per participant, allowing us to assess how each participant performed across the seven misconceptions to be detected. There seems to be quite some variation in the ability of participants to use Pyttern to write patterns for detecting misconceptions. Whereas some participants (on the left) seem successful at writing patterns for most misconceptions, others (on the right) only manage a few. We can also observe from this figure again that for some misconceptions most participants managed to write valid pytterns, whereas for other misconceptions this was much less the case.

Nevertheless, our results do show that the majority of study participants successfully developed valid pytterns, in spite of their limited prior knowledge about program query languages. Their previous knowledge of Python helped them to understanding and effectively utilise Pyttern, at least for simpler patterns, suggesting that the language design facilitates a gentle learning curve. This result seems to suggest that Pyttern can be adopted by users with basic Python skills without too much difficulty. The limited scope and duration of the experiment unfortunately did not allow us assess whether, with more time and experience, the participants would have been able to write more advanced pytterns successfully.

Although the misconceptions for which we asked our participants to write Pyttern checkers were presented in a certain order, they had the freedom to implement them in any order, within a given time period (4 hours). Nevertheless, we checked whether the order in which the misconception were presented affected the mean F1 score for this misconception. This analysis is summarised in Figure 7. We performed a one-tailed Pearson correlation test between the order of the question and the mean F1 score. Our hypothesis was that later questions could yield a lower F1 score (in other words that students would focus first on the misconceptions that were presented first). This Pearson test gave us an $r$ of $-0.648$ and a $p\text{-}value$ of $0.0577$. This means that we probably have a moderate-to-strong negative relationship between the order of the question and the mean F1 score, even though we cannot claim that the correlation is there with an $\alpha$ of $0.05$.

Obviously there are still many threats to validity of this validation of our new implementation of Pyttern. First, the participant sample used for this evaluation was limited and may not accurately represent the intended population of potential users nor their level of expertise that Pyttern is designed for. Additionally, the version of Pyttern used by our participants was not entirely bugfree during the evaluation. This could have led to participants writing buggy pytterns and missing matches. (It could also explain why 6 participants were not able to write any valid pyttern.) Some (few) participants also had previous experience with Pyttern, as they participated in an earlier experiment with the first prototype of the Pyttern language a year earlier. This may have biased their performance in the positive sense, as the learning curve would have been lower for them. Finally, the set of misconceptions that we selected for this validation might not fully capture the range of possible patterns that we could define with Pyttern. It could also be not representative for the set of all possible misconceptions that we could find in small programs.

In this paper, we introduced a new formalism for Pyttern, a novel approach to pattern matching in Python source code using a modified nondeterministic pushdown automaton. We describe the automaton in detail, along with the foundational principles of this new version of Pyttern, which we believe establishes a robust basis for further improvement. Our formalism presents a general technique for parse tree pattern matching that could be adapted for other programming languages. Pyttern is an implementation of this formalism in Python to investigate whether defining a query language closely aligned with the syntax of the programming language being analyzed (e.g., Python) can assist non-expert developers in writing concise patterns.

Our validation study with master students suggests that the learning curve for Pyttern is generally good, though there is room for improvement. Participants with little or no experience in program query languages were able to implement simple pytterns using their previous Python knowledge. However, the creation of more complex patterns proved challenging, highlighting areas where further improvements in the language’s design could enhance usability. Overall, the successful implementation of different patterns and the constructive feedback received indicate a promising path forward for Pyttern.

While the examples and evaluations presented in this paper are based on single-source files, the underlying approach is not inherently limited to this setting. The current implementation focuses on per-file analysis to simplify parsing and transformation workflows. Extending the system to support multi-file projects primarily requires addressing cross-file symbol resolution and coordinated pattern matching, which are orthogonal to the main contributions of this work. We leave this direction for future work.

Future work will focus on refining the ease of expressiveness of Pyttern, in particular its ability to compose patterns in terms of more simple patterns and combining patterns with logical operators. Also, for now, Pyttern is totally based on Python. We plan to extend the idea to other programming languages and transform the core features of Pyttern (i.e. the PDA and the Matcher) to a pattern matching framework for any language. In fact, we already started this endeavour as we are currently implementing a Java version of Pyttern.