diff options
Diffstat (limited to 'aied2017/patterns.tex')
| -rw-r--r-- | aied2017/patterns.tex | 11 |
1 files changed, 10 insertions, 1 deletions
diff --git a/aied2017/patterns.tex b/aied2017/patterns.tex index 47fc9e2..11909bf 100644 --- a/aied2017/patterns.tex +++ b/aied2017/patterns.tex @@ -81,7 +81,16 @@ The second pattern in Fig.~\ref{fig:sister}, drawn with solid red arrows, encode (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$. +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 \textbackslash{}= Y. parent(B,Y), parent(A,Y), + X \textbackslash{}= Y. X \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: |