\section{AST patterns}

In this section we describe AST patterns through examples, while Sect.~\ref{sec:extracting-patterns} explains how patterns are extracted from student programs. Consider the following Prolog program implementing the relation \code{sister(X,Y)}\footnote{Binary relations like this one should be read as “\code{X} is a sister/parent/… of \code{Y}”.}:

\begin{Verbatim}
sister(X,Y):-     % X is Y’s sister when:
  parent(P,X),
  parent(P,Y),    % X and Y share a common parent P,
  female(X),      % X is female, and
  X \textrm{\textbackslash{}}= Y.         % X and Y are not the same person.
\end{Verbatim}

Figure~\ref{fig:sister} shows the program’s AST with two patterns. The pattern drawn with blue dotted arrows encodes the fact that the first argument to the \code{sister} predicate also appears as the first argument in the call to \code{female}. In other words, this pattern states that \code{X} must be female to be a sister. We write this pattern as the s-expression

\begin{Verbatim}[fontfamily=sf]
(clause (head (compound (functor ‘\code{sister}’) (args var)))
    (compound (functor ‘\code{female}’) (args var)))
\end{Verbatim}

\begin{figure}[htbp]
  \centering
  \begin{forest}
    for tree={
      font=\sf,
      edge=gray,
      s sep=0.05cm,
    }
[text
  [clause,name=top
    [head,name=h
      [compound,name=hc [functor,name=hf [sister,name=hfl]]
        [args,name=ha [var,name=hav [X,name=havl,draw,rectangle,thick,blue,dotted,line width=0.4mm]] [args [var [Y]]]]]]
    [and
      [compound,name=g1 [functor,name=g1f [parent,name=g1fl]]
        [args,name=g1a [var,name=g1av [P,name=g1avl,draw,rectangle,thick,red]] [args [var [X]]]]]
      [and
        [compound,name=g2 [functor,name=g2f [parent,name=g2fl]]
          [args,name=g2a [var,name=g2av [P,name=g2avl,draw,rectangle,thick,red]] [args [var [Y]]]]]
        [and
          [compound,name=g3 [functor,name=g3f [female,name=g3fl]]
            [args,name=g3a [var,name=g3av [X,name=g3avl,draw,rectangle,thick,blue,dotted,line width=0.4mm]]]]
	  [binop [var [X]] [\textrm{\textbackslash{}}{=}] [var [Y]]]]]]]]
% first pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (top) edge[out=-10,in=-170] (g1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g1) edge[transform canvas={xshift=-1.5mm}] (g1f);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g1f) edge[transform canvas={xshift=-1.1mm}] (g1fl);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g1) edge[transform canvas={xshift=1.5mm}] (g1a);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g1a) edge[transform canvas={xshift=-1.2mm}] (g1av);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (top) edge[out=-10,in=-170,transform canvas={xshift=-2mm}] (g2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g2) edge[transform canvas={xshift=-1.5mm}] (g2f);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g2f) edge[transform canvas={xshift=-1.1mm}] (g2fl);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g2) edge[transform canvas={xshift=1.5mm}] (g2a);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (g2a) edge[transform canvas={xshift=-1.2mm}] (g2av);
% second pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (top) edge[transform canvas={xshift=-0.8mm,yshift=0.8mm}] (h);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (h) edge[transform canvas={xshift=-1mm}] (hc);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (hc) edge[transform canvas={xshift=-1.5mm}] (hf);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (hf) edge[transform canvas={xshift=-1.1mm}] (hfl);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (hc) edge[transform canvas={xshift=1.5mm}] (ha);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (ha) edge[transform canvas={xshift=-1.2mm}] (hav);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (top) edge[out=-5,in=160] (g3);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (g3) edge[transform canvas={xshift=-1.5mm}] (g3f);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (g3f) edge[transform canvas={xshift=-1.1mm}] (g3fl);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (g3) edge[transform canvas={xshift=1.5mm}] (g3a);
\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (g3a) edge[transform canvas={xshift=-1.2mm}] (g3av);
  \end{forest}
  \caption{The AST for the \code{sister} program, showing two patterns and the leaf nodes inducing them. Solid red arrows equate the first arguments in the two calls to \code{parent}. Dotted blue arrows encode the necessary condition that \code{X} must be female to be a sister.}
  \label{fig:sister}
\end{figure}

Every pattern used in this paper has the same basic structure, and describes paths from a \textsf{clause} node to one or two leaf nodes containing variables or values. All patterns in Figs.~\ref{fig:sister} and~\ref{fig:sum} are induced from such pairs of nodes. For each leaf we also include some local context, such as the name of the predicate (e.g. \texttt{parent}) and the operators used in \textsf{unop} and \textsf{binop} nodes.

We regard these patterns as the smallest units of meaning in Prolog programs: each pattern encodes some interaction between two objects (variable or value) in the program. Including more than two leaf nodes in a pattern could make it difficult to pinpoint the exact error when generating hints. Each pattern contains at most two \textsf{var} nodes, so we require they both refer to the same variable -- relating two nodes with different variables would not tell us much about the program. We can thus omit actual variable names from patterns.

We handle syntactic variations in programs by omitting certain nodes from patterns. For example, by not including \textsf{and} nodes, the above pattern can match a clause regardless of the presence (or order) of other goals in its body (i.e., with any arrangement of \textsf{and} nodes in the AST). Order \emph{is} important for the nodes specified in the pattern; this is explained below.

The second pattern in Fig.~\ref{fig:sister}, drawn with solid red arrows, encodes the fact that the two calls to \code{parent} share the first argument. In other words, \code{X}~and~\code{Y} must have the same parent~\code{P}.

\begin{Verbatim}[fontfamily=sf]
(clause (compound (functor ‘\code{parent}’) (args var))
    (compound (functor ‘\code{parent}’) (args var)))
\end{Verbatim}

Patterns describe relations between nodes in a program’s AST. Specifically, the pattern ($a$ $b$ $c$) means that the nodes $b$ and $c$ are descended from $a$, and that $b$ precedes $c$ in a depth-first tree walk. In general, an AST matches the pattern (\textsf{name} $p_1$ … $p_k$) if it contains a node $n$ labeled \textsf{name}; the subtree rooted at $n$ must also contain, in depth-first order, distinct nodes $n_1$ to $n_k$ matching subpatterns $p_1$ to $p_k$. The above pattern, for example, matches only the last of the following programs (the first program is missing one call to \code{parent}, and the second has different variables in positions encoded by the pattern):

\begin{Verbatim}
\textit{\red{% nonmatching}}          \textit{\red{% nonmatching}}          \textit{\green{% matching}}
sister(X,Y):-          sister(X,Y):-          sister(X,Y):-
  female(X),             female(X),             parent(A,X),
  parent(P,X),           parent(A,X),           female(X),
  X \textrm{\textbackslash{}}= Y.                parent(B,Y),           parent(A,Y),
			 X \textrm{\textbackslash{}}= Y.                X \textrm{\textbackslash{}}= Y.
\end{Verbatim}

A relation between any two objects in a program is insufficient to reason about the program’s behavior on the whole. In the tutoring context, however, there are patterns that strongly indicate the presence of certain bugs. Take for example the following incorrect program to sum a list:

\begin{Verbatim}
sum([],0).          % \textit{base case:} the empty list sums to zero
sum([H|T],Sum):-    % \textit{recursive case:}
  sum(T,Sum),       %  sum the tail and
  Sum is Sum + H.   %  add first element (\textit{bug:} reused variable)
\end{Verbatim}

This error is fairly common with Prolog novices: the variable \code{Sum} is used to represent both the sum of the whole list (line 2), and the sum of only the tail elements (line 3). The last line fails since Prolog cannot unify \code{Sum} with a (generally) different value of \code{Sum\,+\,H}. The program’s AST is displayed in Fig.~\ref{fig:sum}.

\begin{figure}[htbp]
  \centering
  \begin{forest}
for tree={
    font=\sf,
    edge=gray,
    s sep=0.05cm,
}
[text
  [clause,name=c1
    [head,name=c1h
      [compound,name=c1hc [functor,name=c1hf [sum,name=c1hfv]]
        [args,name=c1ha1 [\code{[\,]},name=c1ha1v,draw,rectangle,thick,dotted,line width=0.4mm,blue]
          [args,name=c1ha2 [\code{0},name=c1ha2v,draw,rectangle,thick,dotted,line width=0.4mm,blue]]]]]]
  [clause,name=c2
    [head,name=c2h
      [compound,name=c2hc [functor,name=c2hf [sum,name=c2hfv]]
        [args,name=c2ha1 [list [var [H]] [var [T]]] [args,name=c2ha2 [var,name=c2ha2v [Sum,draw,rectangle,thick,red]]]]]]
    [and
      [compound,name=c2c [functor,name=c2cf [sum,name=c2cfv]]
        [args,name=c2ca1 [var [T]] [args,name=c2ca2 [var,name=c2ca2v [Sum,draw,rectangle,thick,red]]]]]
      [binop,name=c2b [var,name=c2bv [Sum,draw,rectangle,thick,dashed,orange]] [is,name=c2bo]
        [binop,name=c2bb [var,name=c2bbv [Sum,draw,rectangle,thick,dashed,orange]] [+,name=c2bbo] [var [H]]]]]]]
% first pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1) edge[transform canvas={xshift=-1mm}] (c1h);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1h) edge[transform canvas={xshift=-1mm}] (c1hc);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1hc) edge[transform canvas={xshift=-1.2mm}] (c1hf);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1hf) edge[transform canvas={xshift=-1mm}] (c1hfv);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1hc) edge[transform canvas={xshift=1.2mm}] (c1ha1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1ha1) edge[transform canvas={xshift=-1.2mm}] (c1ha1v);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1ha1) edge[transform canvas={xshift=1.2mm}] (c1ha2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dotted,line width=0.4mm,blue] (c1ha2) edge[transform canvas={xshift=1mm}] (c1ha2v);
% second pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2) edge[transform canvas={xshift=-0.8mm,yshift=0.8mm}] (c2h);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2h) edge[transform canvas={xshift=-1mm}] (c2hc);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2hc) edge[transform canvas={xshift=-1.2mm}] (c2hf);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2hf) edge[transform canvas={xshift=-0.8mm,yshift=0.8mm}] (c2hfv);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2hc) edge[transform canvas={xshift=1.2mm}] (c2ha1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2ha1) edge[transform canvas={xshift=1.2mm}] (c2ha2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2ha2) edge[transform canvas={xshift=1mm}] (c2ha2v);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2) edge[out=-15,in=-170] (c2c);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2c) edge[transform canvas={xshift=-1.2mm}] (c2cf);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2cf) edge[transform canvas={xshift=-1mm}] (c2cfv);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2c) edge[transform canvas={xshift=1.2mm}] (c2ca1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2ca1) edge[transform canvas={xshift=1.2mm}] (c2ca2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red] (c2ca2) edge[transform canvas={xshift=1mm}] (c2ca2v);
% third pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2) edge[out=20,in=150] (c2b);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2b) edge[transform canvas={xshift=-1.1mm}] (c2bv);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2b) edge[transform canvas={xshift=0.8mm}] (c2bo);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2b) edge[transform canvas={xshift=1mm}] (c2bb);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2bb) edge[transform canvas={xshift=-1mm}] (c2bbv);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,dashed,orange] (c2bb) edge[transform canvas={xshift=0.9mm}] (c2bbo);
  \end{forest}
  \caption{The AST for the buggy \texttt{sum} program. Dotted arrows relate the correct values in the base case. Solid and dashed arrows denote two patterns describing incorrect reuse of the \code{Sum} variable in the recursive case.}
  \label{fig:sum}
\end{figure}

Various patterns capture this mistake. Solid red arrows in Fig.~\ref{fig:sum} show one example -- \code{Sum} returned by the predicate should not be the same as the \code{Sum} from the recursive call:

\begin{Verbatim}[fontfamily=sf]
(clause (head (compound (functor ‘\code{sum}’) (args (args var))))
    (compound (functor ‘\code{sum}’) (args (args var))))
\end{Verbatim}

\noindent
The second pattern, drawn with dashed orange arrows in the figure, indicates the likely error in the arithmetic expression:

\begin{Verbatim}[fontfamily=sf]
(clause (binop var ‘\code{is}’ (binop var ‘\code{+}’)))
\end{Verbatim}

The leftmost pattern in Fig.~\ref{fig:sum}, drawn with dotted blue arrows, describes the correct relation between the two constants in the base-case rule:

\begin{Verbatim}[fontfamily=sf]
(clause (head (compound (functor ‘\code{sum}’) (args \code{[]} (args \code{0})))))
\end{Verbatim}

\noindent
We include such patterns in our feature set to cover the base-case clauses in recursive programs, which often include no variables.


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "aied2017"
%%% End: