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 24CONCAT(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 35CONCAT(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 57CONCAT_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 71CONCAT_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 197MUL(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 <i>� Copyright <a href="http://www.housemarque.com" target="_top">Housemarque Oy</a> 2002</i> 289 </br><i>� Copyright Paul Mensonides 2002</i> 290 </div> 291 <div style="margin-left: 0px;"> 292 <p><small>Distributed under the Boost Software License, Version 1.0. (See 293 accompanying file <a href="../../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or 294 copy at <a href= 295 "http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</small></p> 296 </div> 297 </body> 298</html> 299