BOOST_PREPROCESSOR_WHILE(C,F,X) (was Re: [boost] PREPROCESSOR library review)

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-03 06:35:13

From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
> From: "Vesa Karvonen" <vesa.karvonen_at_[hidden]>
> > Hi,
> >
> > A few hours ago, I invented a technique for implementing ADD(X,Y) and
> SUB(X,Y)
> > using linear amount of tokens.
> [snip]
> > It is highly likely that other interesting and useful operations could be
> > implemented in the future.
>
> I have now implemented also MUL(X,Y), MAX(X,Y) and MIN(X,Y).
>
> A pint of beer is promised to the first person to implement DIV(X,Y) and
> MOD(X,Y) using at most a linear amount of tokens (and the result must, of
> course, be a single token).

I implemented DIV and MOD about two hours ago (local time is currently 13:50),
so it seems like that I get the beer...

I'll probably post more details later, but I'll first present the primary
technique. Basically, it seems to be possible to simulate the WHILE statement
using the preprocessor:

  // C = Condition
  // F = Body / Function
  // X = State (tuple)
  #define WHILE(C,F,X) IF(C X,IF(C X,WHILE0,DUMMY)(C,F,F X),X)
  #define WHILE0(C,F,X) IF(C X,IF(C X,WHILE1,DUMMY)(C,F,F X),X)
  #define WHILE1(C,F,X) IF(C X,IF(C X,WHILE2,DUMMY)(C,F,F X),X)
  #define WHILE3(C,F,X) IF(C X,IF(C X,WHILE3,DUMMY)(C,F,F X),X)
  #define WHILE4(C,F,X) IF(C X,IF(C X,WHILE4,DUMMY)(C,F,F X),X)
  // ...

If you look closely, you'll notice the funny looking "C X" and "F X"
expressions. They are tuple function calls. The state X, is a tuple. For
example, a 4-tuple could look like this:

  (1, 2, 3, 4)

To make a function for manipulating a tuple, say increment the first and
decrement the second element of a 2-tuple, you could write it like this:

  #define ADD_F(X,Y)\
   ( INC(X)\
   , DEC(Y)\
   )

Another function on a 2-tuple could simply return the second element:

  #define TUPLE2_E1(E0,E1) E1

With these you can implement ADD:

  #define ADD(X,Y) WHILE(TUPLE2_E1, ADD_F, (X,Y))

Well, not quite, you need to extract the first element from the resulting
tuple. It can be done with these helper primitives:

  #define TUPLE2_E0(E0,E1) E0
  #define ID(X) X

Integrating these to ADD we get:

  #define ADD(X,Y) ID( TUPLE2_E0 WHILE(TUPLE2_E1, ADD_F, (X,Y)) )

(I wrote the above code snippets directly into this e-mail so they may contain
typos.)

This technique can be extended so that it is possible to call other functions,
which may use WHILE, without having to know about it. Basically, you just need
to pass the current recursion depth to the functions that you call and then
catenate that number with WHILE in each function that uses WHILE.