![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to twigb.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig / doc / manual|
Return to twigb.tex CVS log | Up to [Research Unix] / researchv10no / cmd / twig / doc / manual |
1.1 root 1: \magnification=1200
2: \centerline{\bf Twig: A Brief Description}
3: \bigskip
4: Twig is a language for processing trees. A twig program consists of a set
5: of pattern-action rules together with associated declarations. Patterns
6: describe trees to be matched. Actions calculate costs, perform tree
7: manipulations and other functions such as emitting code.
8: A twig program is translated by the twig
9: preprocessor into subroutines and tables in the host language which is C in
10: the current implementation.
11:
12: There are many ways to represent trees and costs. To give the user more
13: choice in representation, twig treats them as abstract data
14: types (ADT). Its manipulation of trees and costs are strictly performed
15: through calls to subroutines provided by the user.
16: \medskip
17: \line{\bf Rules\hfil}
18: The fundamental unit of a twig program is a rule.
19: \medskip
20: \line{\hfil\vbox{\hsize=3.5truein
21: \noindent$label\_id$ {\bf :} $tree\_pattern$\quad {\bf [} $cost$ {\bf ]}
22: {\bf [=} $action$ {\bf ]}}\hfil}
23: \medskip
24: Intuitively, the pattern is used to match a subtree. The $cost$ code
25: fragment is then evaluated. The resulting cost is recorded by
26: the matcher for use in dynamic programming. The $action$ is executed
27: if the rule is part of the least cost cover of the tree.
28:
29: If the $cost$ part is missing, Twig will insert default code
30: that returns the special value, {\tt DEFAULT\_COST}.
31: A missing $action$ part indicates that nothing will be done when a
32: match is found.
33: \medskip
34: \line{\bf Tree Patterns\hfil}
35: Tree patterns are specified
36: in prefix parenthesized form and can be described by the
37: following BNF:
38: \medskip
39: \line{\hfil\vbox{\hsize=3.5truein\obeylines\parindent=0pt\parskip=0pt
40: $tree\_pattern\to node\_id\;\vert\;label\_id$
41: $tree\_pattern\to node\_id \;{\bf (}\; tree\_list \;{\bf )}$
42: $tree\_list \to tree \;{\bf ,}\; tree\_list \;\vert\; tree$
43: }\hfil}
44:
45: For example, the tree,
46: \midinsert
47: \vskip 1.0truein
48: \endinsert
49: \noindent will be written in twig as
50: \medskip
51: \line{\hfil\vbox{\hsize=3.5truein\tt oper(leftOp, rightOp)}\hfil}
52: \medskip
53: There are two types of symbols: $node\_id$\/s and $label\_id$\/s
54: $Node\_id$\/s are used to denote internal nodes and leaves.
55: $Label\_id$\/s label tree patterns and are analogous to
56: non-terminals in context free grammars.
57: For example, the following twig rules without their action parts describe
58: simple expression trees with the {\tt plus} operator.
59: \medskip
60: \line{\hfil\vbox{
61: \tt\noindent\halign{ #:\quad & #\cr
62: expr & plus(expr, expr)\cr
63: expr & identifier\cr
64: expr & constant\cr
65: }}\hfil}
66: \medskip
67: \noindent Here, {\tt identifier} and {\tt constant} are $node\_id$\/s
68: representing leaves, and
69: {\tt plus} is a $node\_id$\/s representing an internal node whereas
70: {\tt expr} is a
71: $label\_id$. Leaves of patterns that are $label\_id$\/s are called
72: {\sl labelled leaves}.
73: In the first rule, both leaves of the pattern are labelled.
74:
75: Twig assigns an integer to each node symbol and label symbol. These
76: integers are used by the twig pattern matcher as encodings for the
77: symbols.
78: As the matcher traverses the
79: tree, a user supplied subroutine is called to provide an integer
80: corresponding to each node.
81: \medskip
82: \line{\bf Costs\hfil}
83: To increase the flexibility of representing costs, the tree matcher
84: views costs as an ADT.
85: For example, costs may be represented as an integer or
86: as a vector of integers with each element representing the cost of a specific
87: resource.
88: A cost ADT suitable for Twig must have the following four definitions:
89: \medskip
90: \noindent$\bullet$ {\tt COST} is a C type.
91: Although the proper functioning of the tree matcher
92: does not depend on the details of the {\tt COST} type, it must have
93: the type information for storage allocation purposes.
94: \smallskip
95: \noindent$\bullet$
96: {\tt INFINITY} is the maximum attainable cost value. The matcher uses {\tt
97: INFINITY} to initialize its data structures.
98: \smallskip\noindent$\bullet$
99: {\tt DEFAULT\_COST} is the cost
100: value returned by rules without a cost part.
101: \smallskip\noindent$\bullet$
102: {\tt COSTLESS} is a function of
103: two cost values. It must return true if and only if the first argument is
104: less than the second.
105: \medskip
106: \line{\bf Trees\hfil}
107:
108: As with costs, Twig treats trees as an ADT. Here, using an ADT is
109: even more important because trees come in a variety of shapes and
110: representations.
111: Twig would be overly complicated if it had to
112: know any more than the fundamental properties of trees. Thus,
113: twig treats trees as an acyclic directed
114: graph of almost featureless nodes with one
115: distinguished node, the root. Each node has only one feature and that
116: is an integer corresponding to the $node\_id$\/s discussed above.
117: To provide this
118: view to Twig, the user must provide the following definitions and
119: subroutines.
120: \medskip
121: \noindent$\bullet$ {\tt NODE} is the type of a node. The actual
122: details of
123: the NODE are irrelevant and Twig uses this definition only for storage
124: allocation and declaration purposes.
125: \smallskip
126: \noindent$\bullet$ {\tt NONODE} is a constant of type
127: {\tt NODE}. It is a distinguished
128: value returned by the routines defined below to represent a null value.
129: \smallskip
130: \noindent$\bullet$
131: {\tt mtGetNodes$(r,n)$} returns the $n$th child of $r$ where $r$
132: is a {\tt NODE}. The
133: leftmost child is {\tt mtGetNodes}$(r,1)$. If $n > \hbox{degree}(r)$
134: then the function should return {\tt NONODE}. Twig expects the
135: expression {\tt mtGetNodes}$({\tt NONODE}, 0)$
136: to denote the root node of
137: the subject tree.
138: \smallskip
139: \noindent$\bullet$
140: {\tt mtValue$(r)$} returns the integer associated with $r$.
141: \smallskip
142: \noindent$\bullet$
143: {\tt mtSetNodes$(r,n,c)$} replaces the $n$th child of $r$ with
144: $c$. This routine may be used to replace whole subtrees with others.
145: \medskip
146: \line{ \bf Pattern Matcher Operation \hfil}
147:
148: The pattern matcher operates in two phases: the costing phase and the execution
149: phase.
150:
151: In the costing phase, the matcher performs a preorder traversal of
152: a subject tree and discovers matches from the bottom up. At the same time, it
153: builds a skeleton tree that is structurally isomorphic to the subject tree.
154: When a match is discovered the cost clause of the pattern is invoked to
155: calculate the cost. Many patterns with different labels could match at any
156: given node but only the lowest cost pattern for each label is recorded in
157: the skeleton.
158:
159: When a pattern is matched, its label is then used as input to the pattern
160: matcher so that matching of patterns with labelled leaves can begin.
161: This
162: process
163: is analogous to a reduce action in
164: bottom up parsers. In twig, multiple reductions are
165: tracked.
166:
167: The cost part of a rule can also assign a {\sl mode} to a match. The {\sl
168: mode} controls how action parts are to be executed.
169: Actions parts of {\sl defer} mode matches are not executed until the
170: execution phase. {\sl Rewrite} mode matches cause the action part to
171: be executed immediately during the costing phase to transform the
172: matched subtree. Once the rewrite mode action is executed, the costing
173: phase continues by purging all information in the skeleton for the old
174: subtree and then scanning the newly transformed subtree. {\sl
175: Rewrite} actions are similar to actions that are invoked on a reduction in
176: LR parsing.
177:
178: In the case where multiple rewrite actions are possible the one with
179: the lowest cost will be executed. Furthermore, a rewrite action is
180: considered only if its cost is lower than all the defer mode actions.
181: Rewrite mode actions that are not executed are treated in the same
182: manner as defer mode actions in the execution phase.
183:
184: When the root of the subject tree is reached in the preorder
185: traversal, the execution phase begins. The lowest cost match is then
186: chosen at the root and executed. In this context, execution involves
187: executing the actions of the labelled leaves before invoking the code
188: in the current action.
189: \medskip
190: \line{\bf Lexical Issues and Conventions\hfil}
191: Currently the
192: following are keywords of twig in no particular order:
193: \medskip
194: \line{\hfil\vbox{\hsize=3.5truein\tt
195: \halign{ # \hfil & # \hfil & # \hfil \cr
196: label & node & cost \cr
197: action & prologue & insert\cr
198: }}\hfil}
199: \medskip
200: \noindent They have special meanings and may not be used as
201: identifiers.
202: ;:(),= are special characters. All blanks, tabs, formfeeds and
203: newlines are ignored by twig but they may not appear inside
204: identifiers and numbers. Identifiers are nonempty strings
205: made of letters, digits or underscores and starting with a letter.
206: Numbers are nonempty string of digits. Code fragments or action parts
207: are enclosed in braces. Inside code fragments, C lexical rules must
208: be obeyed except that strings of the form $\$...\$$ that are not inside C
209: strings are interpreted by twig. In the following sections, $id$
210: denotes an identifier; $int_1$, $int_2$ denotes numbers; $ccode$
211: denotes C code fragments; $...$ indicates repetition of the previous
212: item; $[...]$ indicates that $...$ is optional.
213:
214: The input to the Twig program will be referred to as the subject tree.
215: \medskip
216: \line{\bf Prologue and Inserts\hfil}
217:
218: \noindent\line{\hfil \vbox{\hsize=3.5truein \tt prologue $ccode$;}\hfil}
219: \medskip
220: \noindent signals to twig that $ccode$ should be inserted at the
221: beginning of the output source file. $Ccode$ should contain
222: definitions relevant to the C code in
223: rules that are defined later in the twig source file.
224: \medskip
225: \noindent\line{\hfil\tt\vbox{\hsize=3.5truein insert $ccode$;}\hfil}
226: \medskip
227: \noindent should cause $ccode$ to be placed into the source file.
228: There can be multiple inserts and they will be placed into the source
229: file
230: in the order that they appear.
231: \medskip
232: \line{\bf Declarations\hfil}
233: All twig identifiers are declared before they are used.
234: \medskip
235: \line{\hfil \tt node $id[(int_1)] [= int_2] ...$;\hfil}
236: \medskip
237: \noindent A node declaration declares one or more identifier to be
238: associated with nodes of the subject tree. The identifiers are
239: assigned numbers by twig but the user can overide the assigned number
240: by specifying $int_2$. The degree of the node identifer, i.e. the
241: number of children, is assumed to be fixed. Normally, twig will
242: deduce the degree when $id$ is used in a rule. However, the user may
243: explicitly give the degree by specifying $int_1$.
244: \medskip
245: \line{\hfil\vbox{\hsize=3.5truein\tt label $id ...$;}\hfil}
246: \medskip
247: A label declaration indicates that the following $id$'s are to be used
248: as labels of rules.
249: \medskip\line{\bf Costs and Action code\hfil}
250:
251: Code fragments such as the $cost$ and $action$ clauses of a rule are
252: specfied by enclosing C code in braces. All legal C constructs are
253: permitted in code fragments. In addition, the following are provided
254: for convenient access to the subject tree and internal data
255: structures of the matcher.
256: \smallskip
257: {\parindent=0pt
258: $\bullet$ $\$\%n\$$ denotes a pointer value to the matcher data
259: structure for the $n$th labelled leaf. Thus to access the cost value
260: associated with that leaf, the notation $\$\%n\$\to${\tt cost} may be used.
261:
262: $\bullet$ $\$\$$ denotes a pointer value to the root of the subject
263: tree.
264:
265: $\bullet$ $\$n_1.n_2.n_3.\, \hbox{...}\,.n_{k-1}.n_k\$$ denotes
266: a pointer value to the $n_k$th child of the $n_{k-1}th$ child of the
267: $n_{k-2}$th child of \hbox{...} of the $n_1$th child of the root of
268: the subject tree. Each $n_i$ is a positive non-zero integer.
269: }
270: \medskip
271:
272: Some special constructs are available to code fragments in the cost
273: part of the specification. The
274: statement ``{\tt ABORT;}'' when encountered during the execution of
275: the cost code, signals to the matcher that this pattern is to be
276: rejected. When a ``{\tt REWRITE;}'' statement is encountered, control
277: is returned to the matcher and the rule will become a {\sl rewrite}
278: mode match. When the end of the cost code fragment is reached,
279: control is returned to the matcher and the rule becomes a {\sl defer}
280: mode match. Cost values are returned to the matcher by assigning to
281: the ``{\tt cost}'' variable in the cost clause. If no assignment is
282: made to the {\tt cost} variable then the returned cost will be {\tt
283: DEFAULT\_COST}.
284:
285: Action clauses are expected to return a new tree which will replace
286: the subject tree. This is done by returning using the standard C
287: ``{\tt return($new\_tree$); }'' statement
288: where {\tt $new\_tree$} is of type
289: {\tt NODEPTR}. When the end of the action clause is encountered, the
290: matcher resumes execution and the subject tree is not replaced.
291: \vfil\eject
292: \line{\bf An Example\hfil}
293:
294: The following are examples of twig rules that generate VAX code for
295: the subtract instruction:
296: \midinsert
297: \moveright 1truein \vbox{\settabs 9 \columns
298: \+prologue & $\{$\cr
299: \smallskip
300: \+NODE & gettemp();\cr
301: \smallskip
302: \+$\}$;\cr\smallskip
303: \+node&long constant sub;\cr
304: \+label&operand temp;\cr
305: \smallskip
306: \+operand:&long;&&&$/*$ rule 1 $*/$\cr
307: \+operand:&constant;&&&$/*$ rule 2 $*/$\cr
308: \+operand:&temp;&&&$/*$ rule 3 $*/$\cr
309: \smallskip
310: \+temp:&operand&&&$/*$ rule 4 $*/$\cr
311: \+&$\{$ cost = {\tt TEMP\_COST}+$\$\%1\$\to$cost;$\}$\cr
312: \+&$=\{$\cr
313: \+&&NODE t = gettemp();\cr
314: \+&& emit(``mov'', $\$\$$, t, 0);\cr
315: \+&&return(t);\cr
316: \+&$\}$;\cr
317: \smallskip
318: \+operand:&sub(operand,operand)&&&$/*$ rule 5 $*/$\cr
319: \+&$\{$cost = $\$\%1\$\to$cost + $\$\%2\$\to$cost+{\tt SUB\_COST};$\}$\cr
320: \+&=$\{$\cr
321: \+&&NODE t = gettemp();\cr
322: \+&&emit(``sub'', $\$1\$$, $\$2\$$, t, 0);\cr
323: \+&&return(t);\cr
324: \+&$\}$;\cr
325: \smallskip
326: \+temp:&sub(temp,constant)&&&$/*$ rule 6 $*/$\cr
327: \+&$\{$\cr
328: \+&&if(value($\$2\$$)==1)\cr
329: \+&&&cost = $\$\%1\$\to$cost+{\tt DEC\_COST};\cr
330: \+&&else ABORT;\cr
331: \+&$\}$=$\{$\cr
332: \+&&emit(``dec'', $\$1\$$, 0);\cr
333: \+&&return($\$1\$$);\cr
334: \+&$\}$;\cr
335: }
336: \endinsert
337: {\parindent=0pt
338: $\bullet$ Rules 3 and 4 form a loop.
339: The potential loop: temp$\to$operand$\to$temp$\to$operand$...$ is
340: broken
341: by the matcher recognizing that the cost of the second match of temp
342: does not cost less than the first match of temp.
343:
344: $\bullet$ Rule 4 localizes the testing of whether an operand is a
345: temporary. It is not necessary but makes the coding of other
346: cost clauses less tedious.
347:
348: $\bullet$ In the cost clause of rule 5, the cost is the sum of the
349: leaves plus the cost of the subtract instruction.
350: The action clause emits code to add the two operands
351: and leave the result in a temporary location. The temporary is
352: returned as a substitution for the subject tree.
353:
354: $\bullet$ Rule 6 handles a special case where the left operand is
355: already in a temporary and the constant is one. In this case, the
356: temporary is directly decremented and returned as the new tree.
357: }\vfil\eject
358: \end
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.