Add section on generating hints

2 files changed, 32 insertions, 3 deletions

diff --git a/aied2017/aied2017.tex b/aied2017/aied2017.tex
index 673986c..b9a9803 100644
--- a/aied2017/aied2017.tex
+++ b/aied2017/aied2017.tex
@@ -2,6 +2,12 @@
 
 \usepackage[utf8]{inputenc}
 
+\usepackage{newunicodechar}
+\newunicodechar{∧}{\ensuremath{\land}}
+\newunicodechar{⇒}{\ensuremath{\Rightarrow}}
+\newunicodechar{⋯}{\ensuremath{\cdots}}
+% latex ∧ unicode ⇒ …
+
 \usepackage{fancyvrb}
 \fvset{commandchars=\\\{\},baselinestretch=0.98,samepage=true,xleftmargin=2.5mm}
 
diff --git a/aied2017/method.tex b/aied2017/method.tex
index 9935005..e70d18a 100644
--- a/aied2017/method.tex
+++ b/aied2017/method.tex
@@ -18,8 +18,7 @@ we would select the following sets of leaf nodes: \{\code{A\textsubscript{1}},\c
 
 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.
-
+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 programs submitted by at least five students.
 
 \subsection{Learning rules for correct and incorrect programs}
 \begin{figure}[t]
@@ -97,7 +96,31 @@ does, classify it as incorrect. Then, check whether a $C-rule$ covers the progra
 it as correct if it does. Otherwise, if none of the induced rules cover this program, classify it as 
 incorrect. 
 
-\subsection{Generating hints from rules}
+\subsection{Generating hints}
+
+Once we have induced the rules for a given problem, we can use them to provide hints based on buggy or missing patterns. To generate a hint for an incorrect program, each rule is considered in turn.
+
+First, all I-rules are checked to find any known incorrect patterns in the program. To find the most likely incorrect patterns, the rules are considered in the order of decreasing quality. If all patterns in the rule “$p_1 ∧ ⋯ ∧ p_k ⇒ \mathsf{incorrect}$” match, we highlight the relevant leaf nodes. As an aside, we found that most I-rules are based on a single pattern. For the incorrect \code{sum} program from the previous section, our method produces the following highlight:
+
+\begin{Verbatim}
+sum([],0).          % \textit{base case:} the empty list sums to zero
+sum([H|T],\red{\underline{Sum}}):-    % \textit{recursive case:}
+  sum(T,\red{\underline{Sum}}),       %  sum the tail and
+  Sum is Sum + H.   %  add first element (\textit{bug:} reused variable)
+\end{Verbatim}
+
+If no I-rule matches the program, we use C-rules to determine the student’s intent. C-rules group patterns that together indicate a high likelihood that the program is correct. Each C-rule thus defines a particular “solution strategy” defined in terms of AST patterns. We reason that a hint alerting the student to a missing pattern could help them complete the program without revealing the whole solution.
+
+When generating a hint from C-rules, we consider all \emph{partially} matching rules “$p_1 ∧ ⋯ ∧ p_k ⇒ \mathsf{correct}$”, where the student’s program matches some (but not all) patterns $p_i$. For each such rule we store the number of matching patterns, and the set of missing patterns. We then return the most common missing pattern among the rules with most matching patterns.
+
+For example, if we find the following missing pattern for an incorrect program implementing the \code{sister} predicate:
+
+\begin{Verbatim}[fontfamily=sf]
+(clause (head (compound (functor "\code{sister}") (args var))) (binop var "\code{\textbackslash{}=}"))\textrm{,}
+\end{Verbatim}
+
+\noindent
+we could display a message to the student saying “you are missing a comparison between \code{X} and some other value, with the form \code{X} \code{\textbackslash{}=} \code{?}”.
 
 
 %%% Local Variables: