Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/preprocessor/doc/topics/reentrancy.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 11.1 KB
Line 
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.&nbsp; Therefore,
12                        there is no iteration.&nbsp; Unfortunately, the preprocessor also disallows
13                        recursion.&nbsp; This means that the library must fake iteration or recursion
14                        by defining sets of macros that are implemented similarly.&nbsp;
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.&nbsp; First, it can be documented
44                        that <code>AB</code> uses <code>CONCAT</code> and disallow usage similar to the
45                        above.&nbsp; 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.&nbsp; 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.&nbsp; 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.&nbsp; 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.&nbsp; There are
84                        several contructs that <i>require</i> recursion (such as <b>BOOST_PP_WHILE</b>).&nbsp; 
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>.&nbsp; There are two mechanisms that are used to
91                        accomplish this:&nbsp; 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.&nbsp; 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.).&nbsp; 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.&nbsp; First,
114                        the set itself which is reentered through concatenation.&nbsp; Second,
115                        corresponding sets that act like they are a part of the the primary set.&nbsp; 
116                        These are also reentered through concatenation.&nbsp; And third, macros that
117                        internally use the first or second type of macro.&nbsp; 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>.&nbsp; 
122                        Two user-defined macros are passed to <b>BOOST_PP_WHILE</b>--a predicate and an
123                        operation.&nbsp; 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.&nbsp;
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.&nbsp; First,
202                        note how <code>ADD_D</code> reenters <b>BOOST_PP_WHILE</b> using the <i>d</i> state
203                        parameter.&nbsp; 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>.&nbsp; 
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.&nbsp; If that variant uses an argument rather than
210                        concatenation, it is suffixed by <code>_D</code> to symbolize its method of
211                        reentrance.&nbsp; Examples or this include the library's own <b>BOOST_PP_ADD_D</b>
212                        and <b>BOOST_PP_MUL_D</b>.&nbsp; If the variant uses concatenation, it is
213                        suffixed by an underscore.&nbsp; It is completed by concatenation of the
214                        state.&nbsp; 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.&nbsp; 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.&nbsp; 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.&nbsp; 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."&nbsp; Despite what it looks
245                        like, the macro <b>BOOST_PP_WHILE</b> does not take three arguments.&nbsp; In
246                        fact, it takes no arguments at all.&nbsp; Instead, the <b>BOOST_PP_WHILE</b> macro
247                        expands <i>to</i> a macro that takes three arguments.&nbsp; It simply detects
248                        what the next available <b>BOOST_PP_WHILE_</b> ## <i>d</i> macro is and returns
249                        it.&nbsp; 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.&nbsp; It completely hides the underlying implementation details.&nbsp; 
255                        So, if it is so much easier to use, why do the state parameters still
256                        exist?&nbsp; The reason is simple as well.&nbsp; When state parameters are
257                        used, the state is <i>known</i> at all times.&nbsp; This is not the case when
258                        automatic recursion is used.&nbsp; The automatic recursion mechanism has to <i>deduce</i>
259                        the state at each point that it is used.&nbsp; 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.&nbsp; The strengths of automatic recursion are ease of use and
269                        implementation encapsulation.&nbsp; These come at a performance cost on some
270                        preprocessors in some situations.&nbsp; The primary strength of state
271                        parameters, on the other hand, is efficiency.&nbsp; Use of the state parameters
272                        is the only way to achieve <i>maximum</i> efficiency.&nbsp; 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>
Note: See TracBrowser for help on using the repository browser.