Add section on patterns

4 files changed, 217 insertions, 4 deletions

diff --git a/aied2017/aied2017.tex b/aied2017/aied2017.tex
index 41bcbb7..673986c 100644
--- a/aied2017/aied2017.tex
+++ b/aied2017/aied2017.tex
@@ -3,9 +3,19 @@
 \usepackage[utf8]{inputenc}
 
 \usepackage{fancyvrb}
-\fvset{commandchars=\\\{\},baselinestretch=0.98,samepage=true,xleftmargin=5mm}
+\fvset{commandchars=\\\{\},baselinestretch=0.98,samepage=true,xleftmargin=2.5mm}
+
+\makeatletter
+\begingroup
+\catcode`\`=\active
+\gdef\FV@fontfamily@sf{%
+  \def\FV@FontScanPrep{\FV@MakeActive\`}%
+  \def\FV@FontFamily{\sffamily\edef`{{\string`}}}}
+\endgroup
+\makeatother
 
 \usepackage{forest}
+\usetikzlibrary{arrows.meta}
 
 \newcommand\code[1]{\texttt{#1}}
 \newcommand\red[1]{{\begingroup\color[rgb]{0.8,0.15,0.15}#1\endgroup}}
@@ -33,7 +43,7 @@ We evaluated our approach on past student programming data for a number of Prolo
 
 \input{introduction}
 \input{background}
-\input{dataset}
+\input{patterns}
 \input{method}
 \input{evaluation}
 \input{conclusion}
diff --git a/aied2017/dataset.tex b/aied2017/dataset.tex
deleted file mode 100644
index e8d168d..0000000
--- a/aied2017/dataset.tex
+++ /dev/null
@@ -1 +0,0 @@
-\section{Dataset}
\ No newline at end of file
diff --git a/aied2017/method.tex b/aied2017/method.tex
index c86af75..9935005 100644
--- a/aied2017/method.tex
+++ b/aied2017/method.tex
@@ -1,5 +1,26 @@
 \section{Method}
 
+The following subsections explain the three main components of our approach: extracting patterns from student submissions, learning classification rules for correct and incorrect programs, and using those rules to generate hints.
+
+\subsection{Extracting patterns}
+\label{sec:extracting-patterns}
+
+We extract patterns from student programs by selecting certain subsets of leaves in a program’s AST, and building up patterns that match nodes in those subsets. For this paper we always select pairs of nodes from the same clause: either two nodes referring to the same variable (like the examples above), or a value (such as \code{0} or the empty list \code{[]}) and another variable or value that occurrs in the same \code{compound} or \code{binop}. For example, in the clause\footnote{Occurrences of the three variables \code{A}, \code{B} and \code{C} are subscripted for disambiguation.}
+
+\begin{Verbatim}
+a(A\textsubscript{1},B\textsubscript{1}):-
+  b(A\textsubscript{2},C\textsubscript{1}),
+  B\textsubscript{2} is C\textsubscript{2} + 18.
+\end{Verbatim}
+
+\noindent
+we would select the following sets of leaf nodes: \{\code{A\textsubscript{1}},\code{A\textsubscript{2}}\}, \{\code{B\textsubscript{1}},\code{B\textsubscript{2}}\}, \{\code{C\textsubscript{1}},\code{C\textsubscript{2}}\}, \{\code{B\textsubscript{2}},\code{18}\}, and \{\code{C\textsubscript{2}},\code{18}\}.
+
+We build a pattern for each set $S$ of selected leaf nodes by walking the AST in depth-first order, and recording nodes that lie on paths to elements of $S$. As explained above, we omit \code{and} nodes, allowing the pattern to generalize to more programs. Patterns also include certain nodes that do not lie on a path to any selected leaf. Specifically, for each included \code{compound} node we also include the corresponding \code{functor} with the predicate name. We also include the operator names (like \code{+} and \code{is}) for all unary and binary (\code{binop}) nodes in the pattern.
+
+Patterns constructed in this way form the set of features for rule learning. To keep this set at a reasonable size, we only use patterns that have appeared in submissions by at least five students.
+
+
 \subsection{Learning rules for correct and incorrect programs}
 \begin{figure}[t]
 \centering
@@ -79,4 +100,7 @@ incorrect.
 \subsection{Generating hints from rules}
 
 
-
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "aied2017"
+%%% End:
\ No newline at end of file
diff --git a/aied2017/patterns.tex b/aied2017/patterns.tex
new file mode 100644
index 0000000..32796ac
--- /dev/null
+++ b/aied2017/patterns.tex
@@ -0,0 +1,180 @@
+\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{Meaning “\code{X} is a sister 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 \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 in the call to \code{female}. In other words, this pattern states that \code{X} must be female to be a sister. We write the 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]] [\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[out=-15,in=-155] (h);
+\path[-{Latex[length=1.5mm,width=1mm]},thick,dotted,relative,blue] (h) edge[transform canvas={xshift=-1.5mm}] (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{Abstract syntax tree for the \code{sister(X,Y)} program, showing two patterns and the leaf nodes that induce them. Solid red pattern relates the first argument to the two calls to \code{parent(X,Y)}. Dotted blue pattern encodes the necessary condition that \code{X} must be female to be a sister.}
+  \label{fig:sister}
+\end{figure}
+
+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$.
+
+We handle syntactic variations in programs by omitting certain nodes from patterns. For example, by not including \code{and} nodes, the above pattern can match predicates with goals in any order (any arrangement of \code{and} nodes in the AST). This way, the same pattern will match any clause containing the “\textsf{sister}-\textsf{female}” relation, regardless of other goals.
+
+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}
+
+All patterns used in this paper have the same basic structure: a union of paths from some \textsf{clause} to a pair of leaf nodes with variables (or values). Some local context is included with each leaf, such as the functor of a compound term. Each pattern only refers to a single variable, so we do not include its name with the \textsf{var} nodes. We regard such patterns as the basic units of meaning in Prolog programs: each pattern encodes an interaction between two parts of the program accessing the same object (variable).
+
+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, and the sum of only the tail elements. The last line fails since Prolog cannot unify \code{Sum} with a (usually) 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=-1mm}] (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[transform canvas={xshift=-1mm}] (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{AST for the \texttt{sum} program.}
+  \label{fig:sum}
+\end{figure}
+
+Several 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{Sum}) \code{is} (binop (var \code{Sum}) \code{+})))
+\end{Verbatim}
+
+The leftmost pattern, drawn with dotted blue arrows in Fig.~\ref{fig:sum}, 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:
\ No newline at end of file