Next up, we're going to want to implement basic arithmetic such addition, subtraction etc. Now the problem is the preprocessed doesn’t actually do any calculations in that regard. 1 + 2 stays expanded as 1 + 2 (since we're just generating code). So how do we get around this?

We can make use of patttern matching and recursion, we can use them to do basic arithmetic. We need to however, think recursively. Remember how you learned to count and add with your hands when you were young? This is the exact same way we're going to implement addition. Lets say we want to do 2 + 3. We know that 2 + 3 = 2 + 1 + 1 + 1 = 5. We just increment our number that many times. We have two parts we need to implement. The first is incrementing/decrementing numbers, and the second is doing it recursively so that we can add/subtract.

Counting

Now there’s 2 approaches to doing this. Some people have actually implemented a full ripple carry adder. For this purpose lets simplify and use pattern matching. We will store what the incremented/decremented value for each number is going to be and pattern match that to increment/decrement. While this does limit our range, it decreases complexity (Note, the Full Adder can be extends to however many bits you want). Lets say we only care about numbers between -2[N2] and 2 (we're going to use N instead of - to represent number as the preprocessor doesn’t like - as a token). Unfortunately, we need to brute force all pattern matches (This part can be auto-generated at least! What? Why not even more meta :)! )

/*
 This is pretty much as in pattern matching.
 For all values, use pattern match to get what
 their incremented/decremented values are
*/
#define INC_N2 N1
#define INC_N1 0
#define INC_0  1
#define INC_1  2
#define INC_2  N2 // Have it overflow!

#define INC(n) CAT(INC_, n)

#define DEC_N2 2  // Have it overflow!
#define DEC_N1 N2
#define DEC_0  N1
#define DEC_1  0
#define DEC_2  1

#define DEC(n) CAT(DEC_, n)

Now the fun part. We're going to implement addition with recursion (subtraction is the same process). Lets first define our ADD function recursively.

ADD(a, b):
if ( b ! 0 ) return 1 + ADD(a, b - 1);
else return 0;

The problem with this is recursion must be done without any call stack. As a result we must convert everything into tail recursive

ADD(a, b):
if ( b != 0 ) return ADD (a + 1, b - 1);
else return a;

Now lets convert closer to our macro form.

#define ADD(a, b) \
  IF (IS_NOT_ZERO(b)) ( \
    ADD ( INC(a), DEC(b) )\
    , \
    a \
  )

However, remember we must do our recursion indirectly and evaluate the correct number of steps (as discussed in the recursion tutorial). Converting the code into the correct form, we get the following

/*
 First things first, we need to add an indirection to ADD.
 This allows us to convert ADD to a recursive macro.
 The next step was to DEFER the ADD_INDIRECT evaluation 2 depths deep.
 This is because the IF is going to cause an evaluation of its parameters
 and expansion of the ADD_NO_EVAL is also going to cause an evaluation.
 By deferring 2 steps, we can avoid the expansion until the correct time
*/
#define ADD_INDIRECT() ADD_NO_EVAL
#define ADD_NO_EVAL(a, b) \
  IF ( IS_NOT_ZERO(b) ) ( \
    DEFER2 (ADD_INDIRECT) () (INC(a), DEC(b))\
    ,\
    a \
  )
#define ADD(a, b) EVAL(ADD_NO_EVAL(a, b))

ADD(1, 1)  // 2
ADD(1, 2)  // N2
ADD(N2, 2) // 0
ADD(N2, 0) // N2

/*
  SUBTRACTION is the same as addition,
  except replace INC(a) with DEC(a)
*/
#define SUBTRACT_INDIRECT() SUBTRACT_NO_EVAL
#define SUBTRACT_NO_EVAL(a, b) \
  IF ( IS_NOT_ZERO(b) ) ( \
    DEFER2 (SUBTRACT_INDIRECT) () (DEC(a), DEC(b))\
    ,\
    a \
  )
#define SUBTRACT(a, b) EVAL(SUBTRACT_NO_EVAL(a, b))

SUBTRACT(1, 1)  // 2
SUBTRACT(1, 2)  // N1
SUBTRACT(N2, 2) // 1
SUBTRACT(N2, 0) // N2

Generating Ranges

Now that we understand arithmetic and loops, we can use this to generate ranges. The idea behind this is that we can use ranges with FOR_EACH to simulate for loops if we need. An example of what we want can be seen in the following example

// RANGE(start, end, step)
RANGE(1, 5, 2) // 1, 3, 5

To do this, we can make use of our add and subtract macros we implemented. We will loop from start to end incrementing by step and output all numbers we encounter. We need to output the last number as a special case so that we don’t add a comma after. In function form, we have

RANGE_(start, end, step):
  if ( end - start != 0 )
  {
    OUTPUT(start, );
    RANGE_(start + step, end, step);
  }
// We want to output the end of the range last
// So we have the correct bracketing
RANGE(start, end, step):
{
  RANGE_ ( start, end, step);
  OUTPUT (end);
}

Converting this to our macro form

#define OUTPUT_RANGE_VALUE(x) x,
#define RANGE_(start, end, step)\
  IF( IS_NOT_ZERO(SUBTRACT(end, start)) )                   \
  (                                                         \
    OUTPUT_RANGE_VALUE(start)                               \
    RANGE_ (ADD(start, step), end, step)                    \
  )

#define RANGE(start, end, step) RANGE_(start, end, step ) end

And finally converting to final form with indirections

#define OUTPUT_RANGE_VALUE(x) x,
#define RANGE_INDIRECT() RANGE_
#define RANGE_(start, end, step)\
  IF( IS_NOT_ZERO(SUBTRACT(end, start)) )                   \
  (                                                         \
    OUTPUT_RANGE_VALUE(start)                               \
    DEFER2(RANGE_INDIRECT) () (ADD(start, step), end, step) \
  )

#define RANGE_NO_EVAL(start, end, step) RANGE_(start, end, step ) end
// Note EVAL2 is used. This is needed because later we will have for loops
// evaluated with EVAL. As a result we need to use another EVAL stack
#define RANGE(start, end, step) EVAL2(RANGE_NO_EVAL(start, end, stop))

RANGE(1, 5, 2) // Expands to 1, 3, 5

Saad Ahmad

Random Projects and Findings

C/C++ Preprocessor Metaprogramming - Arithematic and Basic Loops

Counting

Generating Ranges