]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <html> |
2 | <head> | |
3 | <title>reentrancy.html</title> | |
4 | <link rel="stylesheet" type="text/css" href="../styles.css"> | |
5 | </head> | |
6 | <body> | |
7 | <h4> | |
8 | Reentrancy | |
9 | </h4> | |
10 | <div> | |
11 | Macro expansion in the preprocessor is entirely functional. Therefore, | |
12 | there is no iteration. Unfortunately, the preprocessor also disallows | |
13 | recursion. This means that the library must fake iteration or recursion | |
14 | by defining sets of macros that are implemented similarly. | |
15 | </div> | |
16 | <div> | |
17 | To illustrate, here is a simple concatenation macro: | |
18 | </div> | |
19 | <div class="code"> | |
20 | <pre> | |
21 | #define CONCAT(a, b) CONCAT_D(a, b) | |
22 | #define CONCAT_D(a, b) a ## b | |
23 | ||
24 | CONCAT(a, CONCAT(b, c)) // abc | |
25 | </pre> | |
26 | </div> | |
27 | <div> | |
28 | This is fine for a simple case like the above, but what happens in a scenario | |
29 | like the following: | |
30 | </div> | |
31 | <div class="code"> | |
32 | <pre> | |
33 | #define AB(x, y) CONCAT(x, y) | |
34 | ||
35 | CONCAT(A, B(p, q)) // CONCAT(p, q) | |
36 | </pre> | |
37 | </div> | |
38 | <div> | |
39 | Because there is no recursion, the example above expands to <code>CONCAT(p, q)</code> | |
40 | rather than <code>pq</code>. | |
41 | </div> | |
42 | <div> | |
43 | There are only two ways to "fix" the above. First, it can be documented | |
44 | that <code>AB</code> uses <code>CONCAT</code> and disallow usage similar to the | |
45 | above. Second, multiple concatenation macros can be provided.... | |
46 | </div> | |
47 | <div class="code"> | |
48 | <pre> | |
49 | #define CONCAT_1(a, b) CONCAT_1_D(a, b) | |
50 | #define CONCAT_1_D(a, b) a ## b | |
51 | ||
52 | #define CONCAT_2(a, b) CONCAT_2_D(a, b) | |
53 | #define CONCAT_2_D(a, b) a ## b | |
54 | ||
55 | #define AB(x, y) CONCAT_2(x, y) | |
56 | ||
57 | CONCAT_1(A, B(p, q)) // pq | |
58 | </pre> | |
59 | </div> | |
60 | <div> | |
61 | This solves the problem. However, it is now necessary to know that <code>AB</code> | |
62 | uses, not only <i>a</i> concatenation macro, but <code>CONCAT_2</code> specifically. | |
63 | </div> | |
64 | <div> | |
65 | A better solution is to abstract <i>which</i> concatenation macro is used.... | |
66 | </div> | |
67 | <div class="code"> | |
68 | <pre> | |
69 | #define AB(c, x, y) CONCAT_ ## c(x, y) | |
70 | ||
71 | CONCAT_1(A, B(2, p, q)) // pq | |
72 | </pre> | |
73 | </div> | |
74 | <div> | |
75 | This is an example of <i>generic reentrance</i>, in this case, into a fictional | |
76 | set of concatenation macros. The <code>c</code> parameter represents the | |
77 | "state" of the concatenation construct, and as long as the user keeps track of | |
78 | this state, <code>AB</code> can be used inside of a concatenation macro. | |
79 | </div> | |
80 | <div> | |
81 | The library has the same choices. It either has to disallow a construct | |
82 | being inside itself or provide multiple, equivalent definitions of a construct | |
83 | and provide a uniform way to <i>reenter</i> that construct. There are | |
84 | several contructs that <i>require</i> recursion (such as <b>BOOST_PP_WHILE</b>). | |
85 | Consequently, the library chooses to provide several sets of macros with | |
86 | mechanisms to reenter the set at a macro that has not already been used. | |
87 | </div> | |
88 | <div> | |
89 | In particular, the library must provide reentrance for <b>BOOST_PP_FOR</b>, <b>BOOST_PP_REPEAT</b>, | |
90 | and <b>BOOST_PP_WHILE</b>. There are two mechanisms that are used to | |
91 | accomplish this: state parameters (like the above concatenation example) | |
92 | and <i>automatic recursion</i>. | |
93 | </div> | |
94 | <h4> | |
95 | State Parameters | |
96 | </h4> | |
97 | <div> | |
98 | Each of the above constructs (<b>BOOST_PP_FOR</b>, <b>BOOST_PP_REPEAT</b>, and <b>BOOST_PP_WHILE</b>) | |
99 | has an associated state. This state provides the means to reenter the | |
100 | respective construct. | |
101 | </div> | |
102 | <div> | |
103 | Several user-defined macros are passed to each of these constructs (for use as | |
104 | predicates, operations, etc.). Every time a user-defined macro is | |
105 | invoked, it is passed the current state of the construct that invoked it so | |
106 | that the macro can reenter the respective set if necessary. | |
107 | </div> | |
108 | <div> | |
109 | These states are used in one of two ways--either by concatenating to or passing | |
110 | to another macro. | |
111 | </div> | |
112 | <div> | |
113 | There are three types of macros that use these state parameters. First, | |
114 | the set itself which is reentered through concatenation. Second, | |
115 | corresponding sets that act like they are a part of the the primary set. | |
116 | These are also reentered through concatenation. And third, macros that | |
117 | internally use the first or second type of macro. These macros take the | |
118 | state as an additional argument. | |
119 | </div> | |
120 | <div> | |
121 | The state of <b>BOOST_PP_WHILE</b> is symbolized by the letter <i>D</i>. | |
122 | Two user-defined macros are passed to <b>BOOST_PP_WHILE</b>--a predicate and an | |
123 | operation. When <b>BOOST_PP_WHILE</b> expands these macros, it passes | |
124 | along its state so that these macros can reenter the <b>BOOST_PP_WHILE</b> set. | |
125 | </div> | |
126 | <div> | |
127 | Consider the following multiplication implementation that illustrates this | |
128 | technique: | |
129 | </div> | |
130 | <div class="code"> | |
131 | <pre> | |
132 | // The addition interface macro. | |
133 | // The _D signifies that it reenters | |
134 | // BOOST_PP_WHILE with concatenation. | |
135 | ||
136 | #define ADD_D(d, x, y) \ | |
137 | BOOST_PP_TUPLE_ELEM( \ | |
138 | 2, 0, \ | |
139 | BOOST_PP_WHILE_ ## d(ADD_P, ADD_O, (x, y)) \ | |
140 | ) \ | |
141 | /**/ | |
142 | ||
143 | // The predicate that is passed to BOOST_PP_WHILE. | |
144 | // It returns "true" until "y" becomes zero. | |
145 | ||
146 | #define ADD_P(d, xy) BOOST_PP_TUPLE_ELEM(2, 1, xy) | |
147 | ||
148 | // The operation that is passed to BOOST_PP_WHILE. | |
149 | // It increments "x" and decrements "y" which will | |
150 | // eventually cause "y" to equal zero and therefore | |
151 | // cause the predicate to return "false." | |
152 | ||
153 | #define ADD_O(d, xy) \ | |
154 | ( \ | |
155 | BOOST_PP_INC( \ | |
156 | BOOST_PP_TUPLE_ELEM(2, 0, xy) \ | |
157 | ), \ | |
158 | BOOST_PP_DEC( \ | |
159 | BOOST_PP_TUPLE_ELEM(2, 1, xy) \ | |
160 | ) \ | |
161 | ) \ | |
162 | /**/ | |
163 | ||
164 | // The multiplication interface macro. | |
165 | ||
166 | #define MUL(x, y) \ | |
167 | BOOST_PP_TUPLE_ELEM( \ | |
168 | 3, 0, \ | |
169 | BOOST_PP_WHILE(MUL_P, MUL_O, (0, x, y)) \ | |
170 | ) \ | |
171 | /**/ | |
172 | ||
173 | // The predicate that is passed to BOOST_PP_WHILE. | |
174 | // It returns "true" until "y" becomes zero. | |
175 | ||
176 | #define MUL_P(d, rxy) BOOST_PP_TUPLE_ELEM(3, 2, rxy) | |
177 | ||
178 | // The operation that is passed to BOOST_PP_WHILE. | |
179 | // It adds "x" to "r" and decrements "y" which will | |
180 | // eventually cause "y" to equal zero and therefore | |
181 | // cause the predicate to return "false." | |
182 | ||
183 | #define MUL_O(d, rxy) \ | |
184 | ( \ | |
185 | ADD_D( \ | |
186 | d, /* pass the state on to ADD_D */ \ | |
187 | BOOST_PP_TUPLE_ELEM(3, 0, rxy), \ | |
188 | BOOST_PP_TUPLE_ELEM(3, 1, rxy) \ | |
189 | ), \ | |
190 | BOOST_PP_TUPLE_ELEM(3, 1, rxy), \ | |
191 | BOOST_PP_DEC( \ | |
192 | BOOST_PP_TUPLE_ELEM(3, 2, rxy) \ | |
193 | ) \ | |
194 | ) \ | |
195 | /**/ | |
196 | ||
197 | MUL(3, 2) // expands to 6 | |
198 | </pre> | |
199 | </div> | |
200 | <div> | |
201 | There are a couple things to note in the above implementation. First, | |
202 | note how <code>ADD_D</code> reenters <b>BOOST_PP_WHILE</b> using the <i>d</i> state | |
203 | parameter. Second, note how <code>MUL</code>'s operation, which is | |
204 | expanded by <b>BOOST_PP_WHILE</b>, passes the state on to <code>ADD_D</code>. | |
205 | This illustrates state reentrance by both argument and concatenation. | |
206 | </div> | |
207 | <div> | |
208 | For every macro in the library that uses <b>BOOST_PP_WHILE</b>, there is a | |
209 | state reentrant variant. If that variant uses an argument rather than | |
210 | concatenation, it is suffixed by <code>_D</code> to symbolize its method of | |
211 | reentrance. Examples or this include the library's own <b>BOOST_PP_ADD_D</b> | |
212 | and <b>BOOST_PP_MUL_D</b>. If the variant uses concatenation, it is | |
213 | suffixed by an underscore. It is completed by concatenation of the | |
214 | state. This includes <b>BOOST_PP_WHILE</b> itself with <b>BOOST_PP_WHILE_</b> | |
215 | ## <i>d</i> and, for example, <b>BOOST_PP_LIST_FOLD_LEFT</b> with <b>BOOST_PP_LIST_FOLD_LEFT_</b> | |
216 | ## <i>d</i>. | |
217 | </div> | |
218 | <div> | |
219 | The same set of conventions are used for <b>BOOST_PP_FOR</b> and <b>BOOST_PP_REPEAT</b>, | |
220 | but with the letters <i>R</i> and <i>Z</i>, respectively, to symbolize their | |
221 | states. | |
222 | </div> | |
223 | <div> | |
224 | Also note that the above <code>MUL</code> implementation, though not | |
225 | immediately obvious, is using <i>all three</i> types of reentrance. Not | |
226 | only is it using both types of <i>state</i> reentrance, it is also using <i>automatic | |
227 | recursion</i>.... | |
228 | </div> | |
229 | <h4> | |
230 | Automatic Recursion | |
231 | </h4> | |
232 | <div> | |
233 | Automatic recursion is a technique that vastly simplifies the use of reentrant | |
234 | constructs. It is used by simply <i>not</i> using any state parameters at | |
235 | all. | |
236 | </div> | |
237 | <div> | |
238 | The <code>MUL</code> example above uses automatic recursion when it uses <b>BOOST_PP_WHILE</b> | |
239 | by itself. In other words, <code>MUL</code> can <i>still</i> be used | |
240 | inside <b>BOOST_PP_WHILE</b> even though it doesn't reenter <b>BOOST_PP_WHILE</b> | |
241 | by concatenating the state to <b>BOOST_PP_WHILE_</b>. | |
242 | </div> | |
243 | <div> | |
244 | To accomplish this, the library uses a "trick." Despite what it looks | |
245 | like, the macro <b>BOOST_PP_WHILE</b> does not take three arguments. In | |
246 | fact, it takes no arguments at all. Instead, the <b>BOOST_PP_WHILE</b> macro | |
247 | expands <i>to</i> a macro that takes three arguments. It simply detects | |
248 | what the next available <b>BOOST_PP_WHILE_</b> ## <i>d</i> macro is and returns | |
249 | it. This detection process is somewhat involved, so I won't go into <i>how</i> | |
250 | it works here, but suffice to say it <i>does</i> work. | |
251 | </div> | |
252 | <div> | |
253 | Using automatic recursion to reenter various sets of macros is obviously much | |
254 | simpler. It completely hides the underlying implementation details. | |
255 | So, if it is so much easier to use, why do the state parameters still | |
256 | exist? The reason is simple as well. When state parameters are | |
257 | used, the state is <i>known</i> at all times. This is not the case when | |
258 | automatic recursion is used. The automatic recursion mechanism has to <i>deduce</i> | |
259 | the state at each point that it is used. This implies a cost in macro | |
260 | complexity that in some situations--notably at deep macro depths--will slow | |
261 | some preprocessors to a crawl. | |
262 | </div> | |
263 | <h4> | |
264 | Conclusion | |
265 | </h4> | |
266 | <div> | |
267 | It is really a tradeoff whether to use state parameters or automatic recursion | |
268 | for reentrancy. The strengths of automatic recursion are ease of use and | |
269 | implementation encapsulation. These come at a performance cost on some | |
270 | preprocessors in some situations. The primary strength of state | |
271 | parameters, on the other hand, is efficiency. Use of the state parameters | |
272 | is the only way to achieve <i>maximum</i> efficiency. This efficiency | |
273 | comes at the cost of both code complexity and exposition of implementation. | |
274 | </div> | |
275 | <h4> | |
276 | See Also | |
277 | </h4> | |
278 | <ul> | |
279 | <li><a href="../ref/for.html">BOOST_PP_FOR</a></li> | |
280 | <li><a href="../ref/repeat.html">BOOST_PP_REPEAT</a></li> | |
281 | <li><a href="../ref/while.html">BOOST_PP_WHILE</a></li> | |
282 | </ul> | |
283 | <div class="sig"> | |
284 | - Paul Mensonides | |
285 | </div> | |
286 | <hr size="1"> | |
287 | <div style="margin-left: 0px;"> | |
288 |