\section{AST patterns}

We encode structural patterns in ASTs using tree regular expressions (TREs). An ordinary regular expression describes the set of strings matching certain constraints; similarly, a TRE describes the set of trees containing certain nodes and relations. Since TREs describe structure, they are themselves represented as trees. More specifically, both ASTs and TREs are ordered rooted trees.

In this work we used TREs to encode (only) child and sibling relations in ASTs. We write them as S-expressions, such as \pattern{(a (b \textbf{\textasciicircum}~d~\textbf{.}~e~\$) c)}. This expression matches any tree satisfying the following constraints:

\begin{itemize}
\item the root node \pattern{a} has at least two children, \pattern{b} and \pattern{c}, in that order; and
\item the node \pattern{b} has three children: \pattern{d}, followed by any node, followed by \pattern{e}.
\end{itemize}

Figure~\ref{fig:tre-example} shows one instance of a matching tree, with arrows indicating the pattern. Analogous to ordinary regular expressions, caret (\texttt{\textbf{\textasciicircum}}) and dollar sign (\texttt{\$}) anchor a node to be respectively the first or last child of its parent. A period (\texttt{\textbf{.}}) is a wildcard that matches any node.

\begin{figure}[htbp]
  \centering
  \begin{forest}
    for tree={
      font=\sf,
      edge=darkgray,
      l sep=0,
      l=0.9cm,
    }
[a,name=a
  [b,name=b
    [d,name=d] [g,name=g] [e,name=e]]
  [f]
  [c,name=c [j] [k]]
]
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (a) edge[transform canvas={xshift=-1.1mm,yshift=0.2mm}] (b);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (a) edge[transform canvas={xshift=1.1mm,yshift=0.2mm}] (c);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (b) edge[transform canvas={xshift=-1.1mm,yshift=0.2mm}] (d);
\draw[opacity=0] (b) -- node[anchor=east,thick,blue,opacity=1,font=\large] {\texttt{\textasciicircum}} (d);
\path[draw,thick,relative,blue,transform canvas={xshift=-0.7mm}] (b) -- ($ (b)!0.6!(g) $);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (b) edge[transform canvas={xshift=1.1mm,yshift=0.2mm}] (e);
\draw[opacity=0] (b) -- node[anchor=west,thick,blue,opacity=1,font=\scriptsize,transform canvas={xshift=0mm,yshift=1mm}] {\texttt{\$}} (e);
  \end{forest}
  \caption{A tree matching a pattern (in blue besides the edges). In the pattern, an arrow $x→y$ means that node $x$ has a child $y$. A shorter line without an arrowhead (e.g. \pattern{b}—\pattern{g}) indicates a wildcard, where the child can be any node. Anchors \texttt{\textbf{\textasciicircum}} and \texttt{\$} mean that the pattern will match only the first or last child.}
  \label{fig:tre-example}
\end{figure}

With TREs we encode interesting patterns in a program while disregarding irrelevant parts. Take for example the following Python function that prints the divisors of its argument $n$:

\begin{Verbatim}
def divisors(n):
    for d in range(1, n):
        if n % d == 0:
            print(d)
\end{Verbatim}

Figure~\ref{fig:patterns-example} shows the simplified AST for this program, with two patterns overlaid. As described below, we construct our TREs automatically from certain subsets of nodes in the AST. The dashed pattern in Fig.~\ref{fig:patterns-example} was induced from the control-flow nodes in the program, while the solid pattern was induced from a pair of leaf nodes that represent the same variable.

\begin{figure}[htb]
  \centering
  \begin{forest}
    for tree={
      font=\sf,
      edge=darkgray,
      %s sep=0.05cm,
      l sep=0,
      l=0.9cm,
      %s sep=0,
      %s=1.5cm,
    }
[Function, name=def, draw,rectangle,red,dashed
  [name, name=name1 [divisors, name=divisors, font=\bfseries\sffamily]]
  [args, name=args1
    [Var, name=args1-1, draw,rectangle,blue [n, font=\bfseries\sffamily, l=0.7cm]]]
  [body, name=body1, before computing xy={s=2cm}
    [For, name=for, l=1.2cm, draw,rectangle,red,dashed
      [target
        [Var, l=0.9cm [d, font=\bfseries\sffamily, l=0.7cm]]]
      [iter, name=iter
        [Call, name=call, l=0.9cm
          [func, name=func, l=0.8cm [range, name=range, font=\bfseries\sffamily, l=0.7cm]]
          [args, name=args2, l=0.8cm
            [Num, name=args2-1, l=1cm [1, font=\bfseries\sffamily, l=0.7cm]]
            [Var, name=args2-2, l=1cm,draw,rectangle,blue [n, font=\bfseries\sffamily, l=0.7cm]]]]]
      [body, name=body2
        [If, name=if, draw,rectangle,red,dashed
          [test, l=0.7cm [Compare, l=0.8cm
            [BinOp
              [Var [n, font=\bfseries\sffamily, l=0.6cm]]
              [\%, font=\bfseries\sffamily]
              [Var [d, font=\bfseries\sffamily, l=0.6cm]]]
            [{==}, font=\bfseries\sffamily, l=0.7cm]
            [Num [0, font=\bfseries\sffamily, l=0.7cm]]]]
          [body, l=0.7cm [Call, l=0.8cm
            [func [print, font=\bfseries\sffamily, l=0.7cm]]
            [args [Var, l=0.7cm [d, font=\bfseries\sffamily, l=0.6cm]]]]]]]]]]
% first pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (def) edge[transform canvas={xshift=1.1mm,yshift=0.2mm}] (body1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (body1) edge[transform canvas={xshift=0.8mm}] (for);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (for) edge[transform canvas={xshift=1.1mm,yshift=0.5mm}] (body2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (body2) edge[transform canvas={xshift=0.8mm}] (if);
% second pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-1.1mm,yshift=0.2mm}] (name1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-0.8mm}] (args1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (args1) edge[transform canvas={xshift=-0.8mm}] (args1-1);
\draw[opacity=0] (args1) -- node[anchor=east,thick,blue,opacity=1,font=\large] {\texttt{\textasciicircum}} (args1-1);
\draw[opacity=0] (args1) -- node[anchor=west,thick,blue,opacity=1,font=\scriptsize,transform canvas={xshift=-0.5mm,yshift=0.6mm}] {\texttt{\$}} (args1-1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-1mm,yshift=-0.3mm}] (body1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (body1) edge[transform canvas={xshift=-0.8mm}] (for);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (for) edge[transform canvas={xshift=1mm,yshift=-0.5mm}] (iter);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (iter) edge[transform canvas={xshift=0.8mm}] (call);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (call) edge[transform canvas={xshift=-1.2mm}] (func);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (call) edge[transform canvas={xshift=1.2mm}] (args2);
\path[draw,thick,relative,blue,transform canvas={xshift=-0.7mm}] (args2) -- ($ (args2)!0.55!(args2-1) $);
\draw[opacity=0] (args2) -- node[anchor=east,thick,blue,opacity=1,font=\large,transform canvas={xshift=0.6mm,yshift=0.4mm}] {\texttt{\textasciicircum}} (args2-1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (args2) edge[transform canvas={xshift=1mm}] (args2-2);
\draw[opacity=0] (args2) -- node[anchor=west,thick,blue,opacity=1,font=\scriptsize,transform canvas={xshift=0mm,yshift=1mm}] {\texttt{\$}} (args2-2);
  \end{forest}
  \caption{The AST for the \code{divisors} program with two patterns. Leaf nodes (in bold) correspond to terminals in the program, i.e. names and values. Dashed red arrows represent the pattern describing the control structure of the program. Solid blue arrows encode the incorrect second argument to the \code{range} function.}
  \label{fig:patterns-example}
\end{figure}

These two patterns are represented by the respective S-expressions

\begin{enumerate}
\item \pattern{(Function (body (For (body If))))} and
\item \pattern{(Function (name divisors) (args \textbf{\textasciicircum}~Var \$)}
\item[] ~~~~\pattern{(body (For (iter (Call (func range) (args \textbf{\textasciicircum}~\textbf{.} Var \$))))))}.
\end{enumerate}

\noindent
Since this representation is not easy to read, we will instead represent TREs by highlighting relevant text in examples of matching programs. For instance

\begin{Verbatim}
\red{\dashuline{\textbf{def}}} divisors(\blue{\underline{\textbf{n}}}):
    \red{\dashuline{\textbf{for}}} d in range(1, \blue{\underline{\textbf{n}}}):
        \red{\dashuline{\textbf{if}}} n % d == 0:
            print(d)
\end{Verbatim}

While the pattern encoding control flow is correct, the second pattern describes a common mistake for this problem: \code{range(1,n)} will only generate values up to $n-1$, so $n$ will not be printed as its own divisor. A correct pattern would include the binary operator \code{+} on the path to $n$, indicating a call to \code{range(1,n+1)}.

\subsection{Constructing patterns}

Patterns are extracted automatically from student programs. We first canonicalize each program~\cite{rivers2015data-driven} using code from ITAP\footnote{Available at \url{https://github.com/krivers/ITAP-django}.}. To construct TREs describing individual patterns, we select a subset of nodes in the AST, and walk the tree from each selected node to the root, including all nodes along those paths.

Depending on node type we also include some nodes adjacent to such paths. For each comparison and unary/binary expression on the path we include the corresponding operator. For function definitions and calls we include the function name. Finally, in all argument lists we include the anchors (\textbf{\texttt{\textasciicircum}}~and~\code{\$}) and a wildcard (\textbf{\texttt{.}}) for each argument not on the path. This allows our TREs to discriminate between e.g. the first and second argument to a function.

While pattern extraction is completely automated, we have manually defined the kinds of node subsets that are selected. After analyzing solutions to several programming problems, we decided to use the following kinds of patterns. Figure~\ref{fig:patterns-example} shows two examples of the first two kinds of patterns.

\begin{enumerate}
\item
We select each pair of leaf nodes referring to the same variable.
\item
For each control-flow node $n$ we construct a pattern from the set $\{n\}$; we do the same for each \textsf{Call} node representing a function call.
\item
For each expression (such as \code{(F-32)*5/9}) we select the different combinations of literal and variable nodes in the expression. In these patterns we include at most one node referring to a variable.
\end{enumerate}

We found that patterns constructed from such nodesets are useful for discriminating between programs. As we show in Sect.~\ref{sec:interpreting-rules}, they are also easily interpreted in terms of bugs and strategies for a given problem. Note that in any pattern constructed in this way, all \textsf{Var} nodes refer to the same variable, simplifying interpretation.

\subsection{Evaluating patterns}

Our primary interest in this paper is finding rules to help manual analysis of student submissions. The accuracy of automatic classification thus plays a secondary role to the interpretability of our model. Here we give only a rudimentary evaluation of patterns as attributes for distinguishing between correct and incorrect programs.

Evaluation was performed on a subset of exercises from an introductory Python course. The course was implemented in the online programming environment CodeQ\footnote{Available at \url{https://codeq.si}. Source under AGPL3+ at \url{https://codeq.si/code}.}, which was used to collect correct and incorrect submissions. Table~\ref{tab:stats} shows the number of users attempting each problem, the number of all and correct submissions, and the performance of majority and random-forest classifiers for predicting the correctness of a program based on the patterns it contains. We tested these classifiers using 10-fold cross validation.

\setlength{\tabcolsep}{6pt}
\def\arraystretch{1.1}
\begin{table}[htb]
\caption{Solving statistics and classification accuracy for several introductory Python problems. The second column shows the number of users attempting the problem. Columns 3 and 4 show the number of all / correct submissions. The last two columns show the classification accuracy for the majority and random-forest classifiers.}
\centering
 \begin{tabular}{r|c|cc|cc}
 & & \multicolumn{2}{c|}{\textbf{Submissions}} & \multicolumn{2}{c}{\textbf{CA}} \\
 \textbf{Problem} & \textbf{Users} & Total & Correct & Majority & RF \\
 \hline
\textsf{fahrenheit\_to\_celsius}& 521 & 1044 & 384 & 0.579 & 0.933 \\
\textsf{pythagorean\_theorem}& 349 & 669 & 317 & 0.499 & 0.809 \\
\textsf{ballistics}& 248 & 833 & 197 & 0.761 & 0.802 \\
\textsf{average}& 209 & 473 & 178 & 0.614 & 0.830 \\
\hline
\textsf{buy\_five}& 294 & 419 & 208 & 0.613 & 0.828 \\
\textsf{competition}& 227 & 316 & 207 & 0.703 & 0.847 \\
\textsf{top\_shop}& 142 & 471 & 129 & 0.721 & 0.758 \\
\textsf{minimax}& 74 & 164 & 57 & 0.650 & 0.644 \\
\textsf{checking\_account}& 132 & 221 & 101 & 0.521 & 0.744 \\
\textsf{consumers\_anonymous}& 65 & 170 & 51 & 0.688 & 0.800 \\
\hline
\textsf{greatest}& 70 & 86 & 25 & 0.585 & 0.859 \\
\textsf{greatest\_absolutist}& 58 & 132 & 32 & 0.632 & 0.845 \\
\textsf{greatest\_negative}& 62 & 154 & 37 & 0.636 & 0.815 \\
\hline
Total / average & 2451 & 5152 & 1923 & 0.631 & 0.809 \\
 \end{tabular}
\label{tab:stats}
\end{table}

We see that AST patterns increase classification accuracy for about 17\% overall. This result indicates that a significant amount of information can be gleaned from simple syntax-oriented analysis. One exception is the \textsf{ballistics} problem, where the improvement was quite small. This is an artifact of our testing framework: the program is expected to read two values from standard input in a certain order, but none of the used patterns could encode this information.

% TODO why worse-than-bad results for minimax?