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

Pattern matching can be a very powerful tool when it comes to preprocessor metaprogramming. It lets us do anything from boolean logic to addition/subtractions. These macros can be combined to help write macro loops which can help unroll loops!

Pattern Matching using CAT and Macro names

Pattern matching on the preprocessor arises from using token concatenation. The general form of this is we have our macro call concatenated version of our macro were our parameters are the values we want to match. So to begin, lets look implementing AND via truth table

#define CAT(x, y) x ## y
#define PRIMITIVE_CAT(x, y) CAT(x, y)
/*
We will basically pattern match the truth table
AND(0, 0) = 0 -> AND_00 = 0
AND(0, 1) = 0 -> AND_01 = 0
AND(1, 0) = 0 -> AND_10 = 0
AND(1, 1) = 1 -> AND_11 = 1

In general macro format this would be
#define AND_xy [value of and(x, y)]
*/
#define AND_00 0
#define AND_10 0
#define AND_01 0
#define AND_11 1
#define AND(x, y) CAT(CAT(AND_, x), y)
// The resulting calls expand to correct values
AND(0, 0) // 0
AND(0, 1) // 0
AND(1, 0) // 0
AND(1, 1) // 1

We're not limited to returns values only. We can also have it return functions. Lets see how we can use this to implement if statements.

If Conditions

If statements are an example of how to use pattern matching to return functions. Let 1 and 0 represent true and false. Our IF macro will then simply return the appropriate IF function.

/*
 Lets also look at the general if form.
 IF(condition) IF_CONDITION return IF_TRUE else return IF_FALSE
 Lets say we represent 1 and true and 0 as false
 IF(condition) IF_CONDITION return IF_1 else return IF_0

 We want our IF macro to basically return the appropriately
 matched IF_ macro.
*/
// Note we used variadic parameters for false so that its optional
#define IF_1(true, ...) true
#define IF_0(true, ...) __VA_ARGS__
#define IF(value) CAT(IF_, value)

IF(1) ( a, b ) // Expands to IF_1(a, b) -> a
IF(0) ( a, b ) // Expands to 1F_0(a, b) -> b

IF(1) ( a ) // Expands to a
IF(0) ( a ) // Expands to nothing

Macro Lookup - Implementing the else case in Pattern Matching

Theres 2 problems with the current pattern matching scheme right now. The first what happens when we don't have a valid pattern match? Because we're concatenating the parameters and calling the appropriate macro we will simply have an unresolved macro.

AND (1, 2) // Expands AND_12

The second problem, is really visible in the AND implementation. We need to represent all possible outcomes to be pattern matched. We know AND(x, y) is only 1 if x and y = 1 and so the other 3 pattern matches are redundant and useless.

In order to solve these problem, we need to find a way to check if a pattern match exists. If we have a pattern match, we can return its value and if it doesn't then we return some default value. (Note, an alternative approach to following section is the probe/check idiom that Paul talks about).

To achieve this, first we need our pattern matches to return their values enclosed in some name that we can pattern match. For this purpose, lets simply pack all of our return values in an EXISTS container. A simple code example should clarify things [Note, this is to show how exists should be used]

#define AND_00 EXISTS(0)
#define AND_10 EXISTS(0)
#define AND_01 EXISTS(0)
#define AND_11 EXISTS(1)
#define AND(x, y) CAT(CAT(AND_, x), y)

AND(1, 0) // Expands to EXISTS(0)
AND(1, 2) // Expands to AND_12

Now lets solve the first problem. We know that if we have a pattern match then we return an EXISTS object. The problem is if we don't have a match, it returns an unevaluated value.

As a result, we need to make a macro that tests if it was passed an EXISTS object. If it was, then it returns the EXIST value. If it isn't passed one, then return DOESNT_EXIST. Since we can only match the EXISTS object, by default we return DOESNT_EXIST. If we do get passed an EXISTS, we update our result and return the EXISTS value.

To achieve this lets have some fun with macros (Okay, this is most probably abuse but who doesnt like to hack stuff around! :)). The trick to updating parameters is that we need to splice out the old parameters and add in new parameters BEFORE the macro call is evaluated. Lets look at how we can do this:

// To splice out old parameters we need an EAT macro
// This macro simply "eats" all of its parameters
#define EAT(...) 

/*
 The next is we need some sort of update rule
 The general form of this is:
    NEW_PARAMS ) EAT (
*/
#define REPLACE_B NEW_B) EAT (
(a, REPLACE_B, OLD_B) // This expands to (a, NEW_B)
/*
 The expansion chain goes as follows
 (a, REPLACE_B, OLD_B)
 -> (a, REPLACE_B, OLD_B)
 -> (a, NEW_B) EAT (OLD_B)
 -> (a, NEW_B)
*/

The one thing to remember is that these expansions need to happen BEFORE they are used as parameters in a macro. Lets see how this applies

#define FOO(x, y) x + y

// This is an error because we didnt update
// the parameters before calling FOO
FOO(A, REPLACE_B, OLD_B)

// If we use the DEFER/EVAL idiom, we can evaluate it properly
EVAL(DEFER(FOO) (A, REPLACE_B, OLD_B)) // Becomes A + NEW_B

Now using this idiom, we can implement our EXIST testing macro

/*
 We want a LOOKUP_PATTERN(x) to return
 EXISTS(returnValues) if x returns an EXISTS
 DOESNT_EXIST if it doesnt

 We will store our result in the form
 (Value to Test, EXIST result)

 By default, this will be
 (Value to Test, DOESNT_EXIST)

 If we encounter an EXISTS, we want to update parameters to
 (EXPANDED, EXIST Value Tested)
*/

#define EAT(...)
#define EXPAND_TEST_EXISTS(...) EXPANDED, EXISTS(__VA_ARGS__) ) EAT (
#define GET_TEST_EXISTS_RESULT(x) ( CAT(EXPAND_TEST_, x),  DOESNT_EXIST )

GET_TEST_EXISTS_RESULT( EXISTS(FOO) ) // ( EXPANDED, EXISTS(foo) )
GET_TEST_EXISTS_RESULT( FOO )         // ( TEST_foo, DOESNT_EXIST )

/*
 Once we have our test macros, the next step is to extract the values out.
 Remember though, we need to make sure the evaluation of
 GET_TEST_EXISTS_RESULT to happen before we extract the value.

 In the following code, GET_TEST_EXIST_VALUE calls
 GET_TEST_EXIST_VALUE_ which allows for one deferal and proper execution
*/
#define GET_TEST_EXIST_VALUE_(expansion, existValue) existValue
#define GET_TEST_EXIST_VALUE(x) GET_TEST_EXIST_VALUE_  x 

#define TEST_EXISTS(x) GET_TEST_EXIST_VALUE (  GET_TEST_EXISTS_RESULT(x) )
// An alternative way to write #define TEST_EXISTS(x) is as
// EVAL(DEFER(GET_TEST_EXIST_VALUE_) (  GET_TEST_EXISTS_RESULT(x) ))

TEST_EXISTS( EXISTS(FOO) ) // Expands to EXISTS(FOO)
TEST_EXISTS( FOO )         // Expands to DOESNT_EXIST

We can now implement an an else case by testing if we get an EXISTS value. If we don’t we can return a default value.

/*
  We can use TEST_EXISTS to get an appropriate EXISTS or
  DOESNT_EXIST value. By pattern matching we can return the EXISTS value
  if it exists and if not we can return some default value
*/
#define DOES_VALUE_EXIST_EXISTS(...) 1
#define DOES_VALUE_EXIST_DOESNT_EXIST 0
#define DOES_VALUE_EXIST(x) CAT(DOES_VALUE_EXIST_, x)

DOES_VALUE_EXIST(EXISTS()) // 1
DOES_VALUE_EXIST(DOESNT_EXIST) // 0

#define EXTRACT_VALUE_EXISTS(...) __VA_ARGS__
#define EXTRACT_VALUE(value) CAT(EXTRACT_VALUE_, value)

#define TRY_EXTRACT_EXISTS(value, ...) \
  IF ( DOES_VALUE_EXIST(TEST_EXISTS(value)) )\
  ( EXTRACT_VALUE(value), __VA_ARGS__ )

TRY_EXTRACT_EXISTS( EXISTS(FOO), DEFAULT ) // FOO
TRY_EXTRACT_EXISTS( FOO, DEFAULT )         // DEFAULT

Using the Pattern Matching else

So after all of that work, lets look at how it actually helps us make our AND cleaner.

// We only need to match one case now
// We can have all cases return 0!
#define AND_11 EXISTS(1)
#define AND(x, y) TRY_EXTRACT_EXISTS ( CAT(CAT(AND_, x), y), 0 )

AND(0, 1) // 0
AND(1, 1) // 1
AND(-1, 1) // Invalid

Note how we no longer need to specify the values anymore. We can extend this to add more features. Why we want to do these will become apparent in the next sections.

#define AND_11 EXISTS(1)
#define AND(x, y) TRY_EXTRACT_EXISTS ( CAT(CAT(AND_, x), y), 0 )

AND(0, 0) // 0
AND(0, 1) // 0
AND(1, 0) // 0
AND(1, 1) // 1

#define OR_00 EXISTS(0)
#define OR(x, y) TRY_EXTRACT_EXISTS ( CAT(CAT(OR_, x), y), 1 )

OR(0, 0) // 0
OR(0, 1) // 1
OR(1, 0) // 1
OR(1, 1) // 1

#define XOR_01 EXISTS(1)
#define XOR_10 EXISTS(1)
#define XOR(x, y) TRY_EXTRACT_EXISTS ( CAT(CAT(XOR_, x), y), 0 )

XOR(0, 0) // 0
XOR(0, 1) // 1
XOR(1, 0) // 1
XOR(1, 1) // 0

#define NOT_0 EXISTS(1)
#define NOT(x) TRY_EXTRACT_EXISTS ( CAT(NOT_, x), 0 )

NOT(0) // 1
NOT(1) // 0

#define IS_ZERO_0 EXISTS(1)
#define IS_ZERO(x) TRY_EXTRACT_EXISTS ( CAT(IS_ZERO_, x), 0 )

IS_ZERO(0)   // 1
IS_ZERO(1)   // 0
IS_ZERO(10)  // 0
IS_ZERO(010) // 0

// We can even chain logic now too!
#define IS_NOT_ZERO(x) NOT ( IS_ZERO(x) )

IS_NOT_ZERO(0)   // 1
IS_NOT_ZERO(1)   // 0
IS_NOT_ZERO(10)  // 0
IS_NOT_ZERO(010) // 0

/*
 This is useful for when we use tuples
 Our goal we have (FOO, Bar) vs FOO, Bar

 The way this works is simple, IS_ENCLOSED_TEST x
 If x is enclosed, we call IS_ENCLOSED_TEST(...)
 If it isnt, the macro remains unevaluated and we default to 0
*/
#define IS_ENCLOSED_TEST(...) EXISTS(1)
#define IS_ENCLOSED(x, ...) TRY_EXTRACT_EXISTS ( IS_ENCLOSED_TEST x, 0 )

IS_ENCLOSED(Foo, Bar)   // 0
IS_ENCLOSED((Foo, Bar)) // 1

A Little more Complex CAT statement

One issue with TRY_EXTRACT_EXISTS is that if we get passed a value such as (x, y), CAT will fail since CAT(pattern, (x, y)) does not produce a valid token pasting. We can get around this by doing the same update parameters hack we used before.

// Find the result of testing whether a macros is enclosed or not
#define ENCLOSE_EXPAND(...) EXPANDED, ENCLOSED, (__VA_ARGS__) ) EAT (
#define GET_CAT_EXP(a, b) (a, ENCLOSE_EXPAND b, DEFAULT, b )

// Pattern match the result of testing if it is enclose or not
#define CAT_WITH_ENCLOSED(a, b) a b
#define CAT_WITH_DEFAULT(a, b) a ## b
#define CAT_WITH(a, _, f, b) CAT_WITH_ ## f (a, b)

// Defer the call to the CAT so that we get the updated parameters first
#define EVAL_CAT_WITH(...) CAT_WITH __VA_ARGS__
#define CAT(a, b) EVAL_CAT_WITH ( GET_CAT_EXP(a, b) )

CAT(a, (x, y)) // Expands to a(x, y)

Before this, I would recommend reading the Macro Basics Tutorial.  In the article we discussed rule 4 that disallowed recursion explicitly. However, this doesn't mean we cant do recursion. The rule states that if we come across the current macros name it is flagged as a macro that cannot be evaluated. The trick here is that we need an indirect macro that refers to macro we want to recurse. If the indirect macro doesn't evaluate during the macros expansion, we can then evaluate it to recurse. This is hard to follow so lets start start building it up with example. The correct code is at the end (so feel free to skip the derivation) but I want to show where everything comes from.

So first step, lets create an indirection to the recursion macro and see what happens:

#define RECURSE(x) x RECURSE_INDIRECT EMPTY () () (x)
// This the same as #define RECURSE(x) x DEFER(RECURSE_INDIRECT) () (x)
// I just kept the EMPTY() in to make it a bit more explicit

#define RECURSE_INDIRECT() RECURSE
RECURSE(x) // This evaluates to x RECURSE(x)
/*
  This example is similar to the mutual recursion example
  When the RECURSE macro is expanded, RECURSE_INDIRECT () is also
  This causes RECURSE to be added as a result of the initial RECURSE
  and as a result we disallow it from expanding more
*/

So the problem is we need to delay the evaluation of the indirection macro so that it is expanded only AFTER the initial macro. How do we do this? We make use of the delay macro discussed before. By adding an EMPTY() we can delay the execution by one step. Lets look at the updated macro

#define EXPR(...) __VA_ARGS__
#define RECURSE(x) x RECURSE_INDIRECT EMPTY () () (x)
#define RECURSE_INDIRECT() RECURSE

RECURSE(x) // This expands to x RECURSE_INDIRECT () (x)!
/*
  When we call RECURSE(x) after parameter replacement
  [x RECURSE_INDIRECT EMPTY () (x)] is evaluated to
  [x RECURSE_INDIRECT(x)]. By adding the EMPTY() we were able to
  defer the execution of RECURSION_INDIRECT.
*/

EXPR(RECURSE(x)) // This expands to x x RECURSE_INDIRECT () (x)
/*
  We did it!
  This is the same as expanding EXPR(x RECURSE_INDIRECT () (x))
  Since we expand RECURSION_INDIRECT macro (because it is a paramter to
  the EXPR macro), the RECURSE that is added as a result of the expansion
  can actually be expanded. This is because RECURSE was a result of
  the RECURSION_INDIRECT not the RECURSE macro!

  As a result when we evaluate the result of the
  expansion RECURSE is evaluated and we have no recursed!.
*/

EXPR(EXPR(RECURSE(x))) // This expands to x x x RECURSE_INDIRECT () (x)

Note, we must make sure the indirection macro doesn't actually call the macro its indirecting explicitly. At which point the indirection would be added as a result of the expansion of the indirection!

#define RECURSE(x) x RECURSE_INDIRECT EMPTY () (x)
#define RECURSE_INDIRECT(x) RECURSE(x)

RECURSE(x) // x RECURSE_INDIRECT (x)

EXPR(RECURSE(x)) // x x RECURSE_INDIRECT (x)
/* Rewrite it as EXPR(x RECURSE_INDIRECT (x)) and we can see we
   RECURSE_INDIRECT as a result of expanding RECURSE_INDIRECT
*/

EXPR(EXPR(RECURSE(x))) // As expected we get x x RECURSE_INDIRECT (x)