1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
\begin{figure}[tbp]
\centering
\begin{forest}
for tree={
font=\sf,
edge=darkgray,
l sep=0,
l=0.9cm,
}
[a,name=a
[f]
[b,name=b
[d,name=d] [g,name=g] [e,name=e]]
[c,name=c [j] [k]]
[h]
]
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (a) edge[transform canvas={xshift=0.8mm,yshift=-0.2mm}] (b);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (a) edge[transform canvas={xshift=-0.9mm,yshift=-0.3mm}] (c);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (b) edge[transform canvas={xshift=-1.1mm,yshift=0.2mm}] (d);
\draw[opacity=0] (b) -- node[anchor=east,thick,blue,opacity=1,font=\large] {\texttt{\textasciicircum}} (d);
\path[draw,thick,relative,blue,transform canvas={xshift=-0.7mm}] (b) -- ($ (b)!0.6!(g) $);
\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 matching a pattern (blue arrows besides the edges). In the pattern, each arrow $x→y$ means that node $x$ has a child $y$. A shorter line without an arrowhead (e.g. \pattern{b}$\boldsymbol{-}$ \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}
With TREs we encode interesting patterns in a program while disregarding irrelevant parts. Take for example the following, nearly correct Python function that prints the divisors of its argument $n$:
\begin{figure}[htb]
\centering
\begin{forest}
for tree={
font=\sf,
edge=darkgray,
l sep=0,
l=0.9cm,
}
[Function, name=def, draw,rectangle,red,dashed
[name, name=name1 [divisors, name=divisors, font=\bfseries\sffamily]]
[args, name=args1
[Var, name=args1-1, draw,rectangle,blue [n, font=\bfseries\sffamily, l=0.7cm]]]
[body, name=body1, before computing xy={s=2cm}
[For, name=for, l=1.2cm, draw,rectangle,red,dashed
[target
[Var, l=0.9cm [d, font=\bfseries\sffamily, l=0.7cm]]]
[iter, name=iter
[Call, name=call, l=0.9cm
[func, name=func, l=0.8cm [range, name=range, font=\bfseries\sffamily, l=0.7cm]]
[args, name=args2, l=0.8cm
[Num, name=args2-1, l=1cm [1, font=\bfseries\sffamily, l=0.7cm]]
[Var, name=args2-2, l=1cm,draw,rectangle,blue [n, font=\bfseries\sffamily, l=0.7cm]]]]]
[body, name=body2
[If, name=if, draw,rectangle,red,dashed
[test, l=0.7cm [Compare, l=0.8cm
[BinOp
[Var [n, font=\bfseries\sffamily, l=0.6cm]]
[\%, font=\bfseries\sffamily]
[Var [d, font=\bfseries\sffamily, l=0.6cm]]]
[{==}, font=\bfseries\sffamily, l=0.7cm]
[Num [0, font=\bfseries\sffamily, l=0.7cm]]]]
[body, l=0.7cm [Call, l=0.8cm
[func [print, font=\bfseries\sffamily, l=0.7cm]]
[args [Var, l=0.7cm [d, font=\bfseries\sffamily, l=0.6cm]]]]]]]]]]
% first pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (def) edge[transform canvas={xshift=1.1mm,yshift=0.2mm}] (body1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (body1) edge[transform canvas={xshift=0.8mm}] (for);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (for) edge[transform canvas={xshift=1.1mm,yshift=0.5mm}] (body2);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,red,dashed] (body2) edge[transform canvas={xshift=0.8mm}] (if);
% second pattern
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-1.1mm,yshift=0.2mm}] (name1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-0.8mm}] (args1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (args1) edge[transform canvas={xshift=-0.8mm}] (args1-1);
\draw[opacity=0] (args1) -- node[anchor=east,thick,blue,opacity=1,font=\large] {\texttt{\textasciicircum}} (args1-1);
\draw[opacity=0] (args1) -- node[anchor=west,thick,blue,opacity=1,font=\scriptsize,transform canvas={xshift=-0.5mm,yshift=0.6mm}] {\texttt{\$}} (args1-1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (def) edge[transform canvas={xshift=-1mm,yshift=-0.3mm}] (body1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (body1) edge[transform canvas={xshift=-0.8mm}] (for);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (for) edge[transform canvas={xshift=1mm,yshift=-0.5mm}] (iter);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (iter) edge[transform canvas={xshift=0.8mm}] (call);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (call) edge[transform canvas={xshift=-1.2mm}] (func);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (call) edge[transform canvas={xshift=1.2mm}] (args2);
\path[draw,thick,relative,blue,transform canvas={xshift=-0.7mm}] (args2) -- ($ (args2)!0.55!(args2-1) $);
\draw[opacity=0] (args2) -- node[anchor=east,thick,blue,opacity=1,font=\large,transform canvas={xshift=0.6mm,yshift=0.4mm}] {\texttt{\textasciicircum}} (args2-1);
\path[-{Latex[length=1.5mm,width=1mm]},thick,relative,blue] (args2) edge[transform canvas={xshift=1mm}] (args2-2);
\draw[opacity=0] (args2) -- node[anchor=west,thick,blue,opacity=1,font=\scriptsize,transform canvas={xshift=0mm,yshift=1mm}] {\texttt{\$}} (args2-2);
\end{forest}
\caption{The AST for the \code{divisors} program with two patterns. Leaf nodes (in bold) correspond to terminals in the program, i.e. names and values. Dashed red arrows represent the pattern describing the control structure of the program. Solid blue arrows encode the incorrect second argument to the \code{range} function.}
\label{fig:patterns-example}
\end{figure}
|
