diff options
Diffstat (limited to 'aied2018')
| -rw-r--r-- | aied2018/aied2018.tex | 2 | ||||
| -rw-r--r-- | aied2018/introduction.tex | 4 | ||||
| -rw-r--r-- | aied2018/patterns.tex | 17 | ||||
| -rw-r--r-- | aied2018/rules.tex | 2 |
4 files changed, 12 insertions, 13 deletions
diff --git a/aied2018/aied2018.tex b/aied2018/aied2018.tex index a028852..c26d1a2 100644 --- a/aied2018/aied2018.tex +++ b/aied2018/aied2018.tex @@ -42,7 +42,7 @@ \begin{abstract} % background / problem -Writing programs is essential to learning programming. Most programming courses use lab and homework assignments to encourage students to practice. By analyzing solutions to these exercises teachers can discover mistakes and concepts students are struggling with, in order to improve the content and presentation of the course. Students however tend to submit many different programs even for simple exercises, making such analysis difficult. +Writing programs is essential to learning programming. Most programming courses encourage students to practice with lab and homework assignments. By analyzing solutions to these exercises teachers can discover mistakes and concepts students are struggling with, and use that knowledge to improve the content and presentation of the course. Students however tend to submit many different programs even for simple exercises, making such analysis difficult. % solution We propose using tree regular expressions to encode common patterns in programs. Based on these patterns we induce rules describing common approaches and mistakes for a given assignment. In this paper we describe the rule-learning algorithm and present case studies of rule-based analysis for several introductory Python problems. We show that our rules are easy to interpret, and can be learned from a relatively small set of programs. \\\\ diff --git a/aied2018/introduction.tex b/aied2018/introduction.tex index 9c395a4..ab69147 100644 --- a/aied2018/introduction.tex +++ b/aied2018/introduction.tex @@ -6,11 +6,11 @@ Prompt, specific feedback could however greatly benefit learning. Furthermore, a Several attempts have been made to automatically discover commonalities in a set of programs~\cite{jin2012program,rivers2015data-driven,nguyen2014codewebs,hovemeyer2016control}. This would allow a teacher to annotate a representative subset of submissions with feedback messages, which could then be automatically propagated to similar programs. These techniques are used for instance by the OverCode tool to visualize variations in student programs~\cite{glassman2015overcode}. -This paper presents a new language for describing patterns in student code. Our approach is based on \emph{tree regular expressions} (TREs) used in natural language processing~\cite{levy2006tregex}. TREs are similar to ordinary regular expressions: they allow us to specify important patterns in a program’s abstract syntax tree (AST) while disregarding irrelevant parts. TREs are sufficiently expressive to represent the various concepts and errors in novice programs. +This paper presents a new language for describing patterns in student code. Our approach is based on \emph{tree regular expressions} (TREs) used in natural language processing~\cite{levy2006tregex}. TREs are similar to ordinary regular expressions: they allow us to specify important patterns in a program’s abstract syntax tree (AST) while disregarding irrelevant parts. We found that TREs are sufficiently expressive to represent various concepts and errors in novice programs. We have previously demonstrated this approach with Prolog programs~\cite{lazar2017automatic}. Here we refine the definition of AST patterns, and show that they can be applied to Python -- representing a different programming paradigm -- with only a few language-specific modifications. We also demonstrate that rules learned from such patterns can be easily interpreted. -Our approach is similar to CodeWebs, in which Nguyen et al. discover functionally equivalent program fragments -- subtrees of the AST that perform the same transformation from inputs to outputs~\cite{nguyen2014codewebs}. Piech et al. learn program embeddings to a similar end~\cite{piech2015learning}. Our work differs mainly in that TREs allow us to describe relations in (potentially disjoint) subparts of the program. We induce rules based on binary correct/incorrect labels and do not execute any program more than once. +In CodeWebs, Nguyen et al. look for functionally equivalent AST subtrees that perform the same transformation from inputs to outputs~\cite{nguyen2014codewebs}. Piech et al. learn program embeddings to a similar end~\cite{piech2015learning}. Our work differs from theirs mainly in that TREs allow us to describe relations in (potentially disjoint) subparts of the program. We induce rules based on binary correct/incorrect labels, and do not have to execute any submission more than once. Jin et al. use linkage graphs to represent dependencies between individual program statements based on the variables they contain~\cite{jin2012program}. This allows them to form equivalence classes of programs by ignoring unrelated statements. While TREs can encode such attributes, we use smaller patterns that encode dependencies between pairs of variables. Hovemeyer et al. focus on control structures such as loops and conditionals~\cite{hovemeyer2016control}. Our AST patterns include TREs that describe control flow, expressing the same features. diff --git a/aied2018/patterns.tex b/aied2018/patterns.tex index 4edd981..b273f8d 100644 --- a/aied2018/patterns.tex +++ b/aied2018/patterns.tex @@ -9,7 +9,7 @@ In this work we used TREs to encode (only) child and sibling relations in ASTs. \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{.}}) represents a wildcard that matches any one node. +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 @@ -34,7 +34,7 @@ Figure \ref{fig:tre-example} shows one instance of a matching tree, with arrows \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 with a pattern (in blue besides the edges). An arrow $x→y$ indicates that node $x$ has a child $y$. The shorter line \pattern{b}—\pattern{g} means that the child can be any node. Anchors \texttt{\textbf{\textasciicircum}} and \texttt{\$} mean that the pattern will match only the first or last child.} + \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} @@ -47,10 +47,9 @@ def divisors(n): 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 \cite{hovemeyer2016control}, while the solid pattern was induced from a pair of leaf nodes that represent the same variable. +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}[htbp] +\begin{figure}[htb] \centering \begin{forest} for tree={ @@ -136,22 +135,22 @@ While the pattern encoding control flow is correct, the second pattern describes \subsection{Constructing patterns} -Patterns are extracted automatically from student programs. To construct each pattern, we select a subset of nodes in the AST. Then we walk the tree from each selected node to the root and include all nodes along those paths. +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 patterns based on the first two items. +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. +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. +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} diff --git a/aied2018/rules.tex b/aied2018/rules.tex index 572d261..c60b989 100644 --- a/aied2018/rules.tex +++ b/aied2018/rules.tex @@ -2,7 +2,7 @@ \label{sec:rules} \subsection{The learning algorithm} -The goal of learning rules in this paper is to extract and explain common approaches and mistakes in student programs. We use a rule learner called ABCN2e implemented within the Orange data mining library~\cite{demsar2013orange}. ABCN2e is an improvement of the classical CN2 algorithm~\cite{clarkECML1991} for learning unordered rules. The differences between CN2 and ABCN2e are described in a technical report found at \url{https://ailab.si/abml.} +The goal of learning rules in this paper is to extract and explain common approaches and mistakes in student programs. We use a rule learner called ABCN2e implemented within the Orange data mining library~\cite{demsar2013orange}. ABCN2e is an improvement of the original CN2 algorithm~\cite{clarkECML1991} for learning unordered rules. The differences between CN2 and ABCN2e are described in a technical report found at \url{https://ailab.si/abml.} General rule-learning algorithms, such as CN2, tend to generate large amounts of specific rules, which leads to more accurate results, however this makes them less appropriate for explaining. We will now describe a problem specific configuration of the rule-learning algorithm that extracts relevant and explainable patterns from student programs. |