[boost] Boost.Preprocessor: A prototype pow(N,2) max direct iteration WHILE.

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2003-01-14 12:28:46

Hi,

The WHILE construct currently defined in the Boost.Preprocessor library 
allows direct iteration up to BOOST_PP_LIMIT_MAG iterations. The limit can 
sometimes become a problem.

A long time ago, in a private e-mail discussion with Paul, we shortly 
discussed ideas for more powerful WHILE implementations (among other 
things). A few days ago, I implemented a simple prototype of a WHILE 
implementation that allows direct iteration up to Theta(pow(N,2)) iterations 
using a WHILE implementation of Theta(N) macros.

Consider the following example:

#define DELAY(d,hi,lo) WHILE_##d(DELAY_P,DELAY_O,(hi,lo))
#define DELAY_P(d,hl) 
BOOST_PP_OR(BOOST_PP_TUPLE_ELEM(2,0,hl),BOOST_PP_TUPLE_ELEM(2,1,hl))
#define DELAY_O(d,hl)\
  ( BOOST_PP_IF(BOOST_PP_TUPLE_ELEM(2,1,hl),\
                BOOST_PP_TUPLE_ELEM(2,0,hl),\
                BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(2,0,hl)))\
  , BOOST_PP_IF(BOOST_PP_TUPLE_ELEM(2,1,hl),\
                BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(2,1,hl)),\
                BOOST_PP_LIMIT_MAG)\
  )

DELAY(0,0,0) // Stops immediately
DELAY(0,0,5) // Stops after 5 iterations
DELAY(0,5,0) // Stops after 5*BOOST_PP_LIMIT_MAG iterations

The prototype WHILE is not a panacea, however. If you use a WHILE in the 
iterated PRED or OP macros, the iteration depth will be limited. The reason 
for this is not necessarily very intuitive - I'll come back to it a bit 
later. Here is how the prototype WHILE looks:

#define WHILE_C(c,i) BOOST_PP_IF(c,WHILE_##i##B,WHILE_HALT)
#define WHILE_HALT(p,o,x) x

#define WHILE_0(p,o,x) WHILE_C(p(1,x),0)(p,o,x)
#define WHILE_1(p,o,x) WHILE_C(p(2,x),1)(p,o,x)
#define WHILE_2(p,o,x) WHILE_C(p(3,x),2)(p,o,x)
#define WHILE_3(p,o,x) WHILE_C(p(4,x),3)(p,o,x)
#define WHILE_4(p,o,x) WHILE_C(p(5,x),4)(p,o,x)
#define WHILE_5(p,o,x) WHILE_C(p(6,x),5)(p,o,x)
#define WHILE_6(p,o,x) WHILE_C(p(7,x),6)(p,o,x)
#define WHILE_7(p,o,x) WHILE_C(p(8,x),7)(p,o,x)
#define WHILE_8(p,o,x) WHILE_C(p(9,x),8)(p,o,x)
#define WHILE_9(p,o,x) WHILE_C(p(10,x),9)(p,o,x)
#define WHILE_10(p,o,x) WHILE_C(p(11,x),10)(p,o,x)
#define WHILE_11(p,o,x) WHILE_C(p(12,x),11)(p,o,x)
#define WHILE_12(p,o,x) WHILE_C(p(13,x),12)(p,o,x)
#define WHILE_13(p,o,x) x

#define WHILE_0B(p,o,x) WHILE_1(p,o,WHILE_1(p,o,o(1,x)))
#define WHILE_1B(p,o,x) WHILE_2(p,o,WHILE_2(p,o,o(2,x)))
#define WHILE_2B(p,o,x) WHILE_3(p,o,WHILE_3(p,o,o(3,x)))
#define WHILE_3B(p,o,x) WHILE_4(p,o,WHILE_4(p,o,o(4,x)))
#define WHILE_4B(p,o,x) WHILE_5(p,o,WHILE_5(p,o,o(5,x)))
#define WHILE_5B(p,o,x) WHILE_6(p,o,WHILE_6(p,o,o(6,x)))
#define WHILE_6B(p,o,x) WHILE_7(p,o,WHILE_7(p,o,o(7,x)))
#define WHILE_7B(p,o,x) WHILE_8(p,o,WHILE_8(p,o,o(8,x)))
#define WHILE_8B(p,o,x) WHILE_9(p,o,WHILE_9(p,o,o(9,x)))
#define WHILE_9B(p,o,x) WHILE_10(p,o,WHILE_10(p,o,o(10,x)))
#define WHILE_10B(p,o,x) WHILE_11(p,o,WHILE_11(p,o,o(11,x)))
#define WHILE_11B(p,o,x) WHILE_12(p,o,WHILE_12(p,o,o(12,x)))
#define WHILE_12B(p,o,x) WHILE_13(p,o,WHILE_13(p,o,o(13,x)))

As you may have noticed, the essential idea is that the WHILE construct 
nests itself. Specifically, it first tests whether the predicate (p) says 
that the iteration is done. If so, it expands to the current state (x). 
Otherwise it mutates state with the operation (o) once and then invokes the 
next available WHILE *twice*. A particular branch of WHILE may run out of 
depth. If that happens, the branch is expanded to the state without applying 
the operation (note WHILE_13), so that a WHILE higher up can continue the 
work. Because each WHILE tests the predicate first, the state does not get 
mutated too many times. However, the predicate may be called many times 
after the iteration is done.

The reason why the number of nested iterations is limited is that the 
construct goes to the maximum depth N in the first N iterations. At that 
point, if the predicate or operation tries to use WHILE, it does not have 
sufficient depth left. Consider the following innocent looking ADD and MUL 
implementations:

#define ADD(d,x,y) BOOST_PP_TUPLE_ELEM(2,0,WHILE_##d(ADD_P,ADD_O,(x,y)))
#define ADD_P(d,xy) BOOST_PP_TUPLE_ELEM(2,1,xy)
#define ADD_O(d,xy) 
(BOOST_PP_INC(BOOST_PP_TUPLE_ELEM(2,0,xy)),BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(2,1,xy)))

#define MUL(d,x,y) BOOST_PP_TUPLE_ELEM(3,0,WHILE_##d(MUL_P,MUL_O,(0,x,y)))
#define MUL_P(d,rxy) BOOST_PP_TUPLE_ELEM(3,2,rxy)
#define MUL_O(d,rxy) 
(ADD(d,BOOST_PP_TUPLE_ELEM(3,0,rxy),BOOST_PP_TUPLE_ELEM(3,1,rxy)),BOOST_PP_TUPLE_ELEM(3,1,rxy),BOOST_PP_DEC(BOOST_PP_TUPLE_ELEM(3,2,rxy)))

Now,

  ADD(0,0,100)  --> 100  [, and]
  MUL(0,50,1)   --> 50   [, but]
  MUL(0,1,50)   --> 30   [!]

which can be a nasty surprise. The last MUL fails, because the nested ADD 
does not get enough iterations from WHILE.

Note that with about 2*BOOST_PP_LIMIT_MAG macros, you would get the same 
iteration capabilities as the current BOOST_PP_WHILE, except that the 
maximum direct iteration depth would be astronomical (about 
pow(2,BOOST_PP_LIMIT_MAG)).

Anyway, I think that more powerful WHILE constructs could be a useful tool, 
but it should be safer to use. A possible solution would be to use a 
completely new WHILE (macro set) implementation for each nested invocation. 
With a WHILE implementation of Theta(H*V) macros, it would possible to nest 
H times and iterate pow(V,2) times at each nesting depth.

Unfortunately, I currently do not have enough time to research techniques 
like this further. So, this is why I'm posting the stuff here, so Paul (or 
anyone else with the time) should be able to pick it up, should they desire 
to iterate more.

- Vesa Karvonen

_________________________________________________________________
The new MSN 8: smart spam protection and 2 months FREE*  
http://join.msn.com/?page=features/junkmail