C/C++ Preprocessor Metaprogramming

Background

To start off, I want to give credit where credit is due. I want to thank Paul Fultz and his description of C Preprocessor tricks, tips, and idioms (which I recommend reading!). This is pretty much based off that and I used that as a tutorial to do it myself.

Next, there is also Pauls Cloak library and a Boost Library to do many of these features and I encourage you to check them out.

There's also other macro languages that are probably more powerful. One of my friends has been recommending m4 and so I would recommend looking into it as its pretty cool!.

I have also created a similar library with a couple of extra features. The goal of this post is not to advertise the library however it is to explain how they work, how they are created and how they can be used.

Motivation

The preprocessor is tool to achieve meta-programming in C/C++. A lot of times I've heard how preprocessor is generally a bad thing especially if you're using macros. I wanted to show how we can use the preprocessor to help write less repetitive code, potentially faster code and potentially cleaner code. I'm not going to lie, the preprocessor macros we're going to define are pretty horrible to look at however I'm going to try explaining it as best as I can. However, once we have these macros defined they can be used to create nicer code.

Preprocessor as a programming language

The preprocessor is has a surprising number of features it can provide us. The problem is we need to implement most of these functions. The best way to describe the preprocessor is that it is a pattern matching language that doesn't have stack. As a result, there’s no concept of local (only parameters to macros), recursion (only tail recursion is allowed), addition/subtraction, loops etc.

However pattern matching can let us implement a bunch of stuff such as conditionals/recursion/arithematic/list comprehension/etc. The first set of tutorials are meant to explain how to generate these functions and the latter part is applications of these features. Since there’s a lot to discuss, I have split it into multiple posts:

Basics

Advanced Concepts

Applications

C/C++ Preprocessor Metaprogramming - Applications: Variable Dumping

Another small thing I found this useful for was outputting multiple variables for debugging purposes. I wanted to output variables and their respective values in one call. We can use FOR_EACH to help us achieve this.

#define STRINGIFY(x) #x
#define DUMP_VAR(x) std::cout << STRINGIFY(x) << ": " << x << std::endl;
#define DUMP_VARS(...) \
  std::cout << __FILE__ << " (Line #" __LINE__ << ")" << std::endl; \
  FOR_EACH(DUMP_VAR, __VA_ARGS__)

int main()
{
  int a = 10;
  string b ("Foo");
  float c = 1.4f;

  DUMP_VARS(a, b, c);
  /*
    Foo.cpp (Line #11)
    a: 10;
    b: Foo;
    c: 1.4f;
  */
}

C/C++ Preprocessor Metaprogramming - Lists and FOR_EACH

One of the most powerful things we can have in the preprocessor is the power of FOR_EACH (or MAP in functional terms). With this functionality, we can do stuff like loop unrolling, generating enum tables, generate typedefs, dynamic template parameters (these examples in a later post).

FOR_EACH allows us to evaluate a macro function to each of the arguments we pass our FOR_EACH. Lets look at we want to implement.

FOR_EACH(f, a, b, c, d) -&amp;amp;gt; returns f(a) f(b) f(c) f(d)
FOR_EACH(f, (a, b), (x, y)) -&amp;amp;gt; returns f(a, b) f(x, y)

Lists

First we need to define what we mean by list and a couple of macros for lists.

/*
 A simple list can be represented by a, b, c
 A tuple is represented as (a, b, c, d)

 We will need three functions for list:
 1) Head: Gets first value of a list
    -&amp;amp;gt; HEAD(a, b, c) = a
 2) Tail: Returns everything after the first element
    -&amp;amp;gt; TAIL(a, b, c) = b, c
 We can make use of the fact that if list are not enclosed,
 they act as parameters to a macro
 Therefore HEAD is simply the first parameter
 TAIL simply returns the remaining parameters
*/
#define HEAD(x, ...) x
#define TAIL(x, ...) __VA_ARGS__

HEAD(a, b, c) // Expands to a
TAIL(a, b, c) // Expands to b, c
HEAD((a, b), (x, y)) // Expands to (a, b)
TAIL((a, b), (x, y)) // Expands to (x, y)

/*
 3) Test if a list is empty or not.
 A list maybe a list of values or a list of tuples.
 We need to account for both cases
   -&amp;amp;gt; IS_LIST_EMPTY()       = 1
   -&amp;amp;gt; IS_LIST_EMPTY(a, b)   = 0
   -&amp;amp;gt; IS_LIST_EMPTY((a, b)) = 0
   -&amp;amp;gt; IS_LIST_EMPTY(,,)     = 0
 We will achieve this through pattern matching.
 For our list we'll add a value LAST but without a comma operator
 As a result, our lists will now look like
   -&amp;amp;gt; a, b           = a, b LAST
   -&amp;amp;gt; (a, b), (c, d) = (a, b), (c, d) LAST
   -&amp;amp;gt; &amp;amp;lt;nothing&amp;amp;gt;      = LAST
  We will simply take the first value of the new list and MATCH for LAST
*/
#define TEST_LAST EXISTS(1)
#define IS_LIST_EMPTY(...) \
  TRY_EXTRACT_EXISTS( \
    DEFER(HEAD) (__VA_ARGS__ EXISTS(1))\
  , 0)
#define IS_LIST_NOT_EMPTY(...) NOT(IS_LIST_EMPTY(__VA_ARGS__))

IS_LIST_EMPTY()       // 1
IS_LIST_EMPTY(a, b)   // 0
IS_LIST_EMPTY((a, b)) // 0
IS_LIST_EMPTY(,,)     // 0

Tuples are essentially enclosed lists, lets look at some functions we need for tuples

/*
 We also want a function to convert tuples into lists (remove brackets)
 As for why, recall our example:
 FOR_EACH(f, (a, b), (x, y)) -&amp;amp;gt; returns f(a, b) f(x, y)
 We need to remove the the brackets from (a, b) so we can
 pass it into f as two parameters.
 Now this just uses our pattern matching stuff before
 1) First test and see if it is enclosed (discussed in previous section)
 2) If it is enclosed remove enclosure otherwise return as normal
*/
#define ENCLOSE(...) ( __VA_ARGS__ )
#define REM_ENCLOSE_(...) __VA_ARGS__
#define REM_ENCLOSE(...) REM_ENCLOSE_ __VA_ARGS__

#define IF_ENCLOSED_1(true, ...) true
#define IF_ENCLOSED_0(true, ...) __VA_ARGS__
#define IF_ENCLOSED(...) CAT(IF_ENCLOSED_, IS_ENCLOSED(__VA_ARGS__))
// This function will optionally remove brackets around its arguments
// if there are any. Otherwise it will return normally
#define OPT_REM_ENCLOSE(...) \
  IF_ENCLOSED (__VA_ARGS__) ( REM_ENCLOSE(__VA_ARGS__), __VA_ARGS__ )

ENCLOSE(a, b) // (a, b)
REM_ENCLOSE((a, b)) // a, b
f ( OPT_REM_ENCLOSE((a, b)) ) // Expands to f(a, b)
f ( OPT_REM_ENCLOSE(a, b) )   // Expands to f(a, b)

FOR_EACH

So with the boiler plate done, lets look at how FOR_EACH works. FOR_EACH works by going through the last passed and evaluating a function for each one. To do this, we need to go through the list recursively. We can make use of the HEAD and TAIL functions. First lets look at how we would implement in in function pseudo form

FOR_EACH(fVisitor, list)
{
  if ( !is_empty( list ) )
  {
    fVisitor( tuple_to_list_opt(head(list)));
    FOR_EACH(fVisitor, tail(list));
  }
}

Converting this to using our MACROs:

// Remember list is simply varargs to our macro
// As a result list = ...
#define FOR_EACH(fVisitor, ...) \
  IF ( IS_LIST_NOT_EMPTY( list )  ) \
  ( \
    fVisitor( OPT_REMOVE_ENCLOSE(HEAD(__VA_ARGS__)) ) \
    FOR_EACH(fVisitor, TAIL(__VA_ARGS__)) \
  )

Then, lets apply indirection to get rid of the direct recursion and get our final macro

#define FOR_EACH_INDIRECT() FOR_EACH_NO_EVAL
#define FOR_EACH_NO_EVAL(fVisitor, ...) \
  IF ( IS_LIST_NOT_EMPTY( __VA_ARGS__ )  ) \
  ( \
    fVisitor( OPT_REM_ENCLOSE(HEAD(__VA_ARGS__)) ) \
    DEFER2 ( FOR_EACH_INDIRECT ) () (fVisitor, TAIL(__VA_ARGS__)) \
  )
#define FOR_EACH(fVisitor, ...) \
  EVAL(FOR_EACH_NO_EVAL(fVisitor, __VA_ARGS__))

FOR_EACH(f, a, b, c, d)     // Expands to f(a) f(b) f(c) f(d)
FOR_EACH(f, (a, b), (x, y)) // Expands to f(a, b) f(x, y)

And there have it, we've implemented FOR_EACH! FOR_EACH doesnt have to be limited to 1 dimension.

Extending FOR_EACH to higher dimensions

Lets consider a 2D version of FOR_EACH. We want it to take two lists and apply a function to all permutations of the function. Lets look at an example

FOR_EACH_2D(f, (a, b), (x, y)) -&amp;amp;gt; returns f(a, x) f(a, y) f(b, x) f(b, y)

Ideally we'd use the FOR_EACH function however using our current macros, its not possible (we would need to implement bind which we will discuss later). For now we'll do it iteratively like we did for FOR_EACH. Lets look at the functional form:

FOR_EACH_2D(fVisitor, listA, origListA, listB, origListB):
{
  // Check to see if we've iterated thourgh all our values in listB
  // If we havent then we can iterate
  if ( !empty(listB) )
  {
    // Call visitor in the first elements of each
    fVisitor ( head(listA), head(listB) );
    // Then move onto the next list
    FOR_EACH_2D(fVisitor, listA, origListA, tail(listB), origListB)
  }
  // If we've processed all the values in listB with our current A value
  // Then move onto the next value of A if we havent run out yet
  else if ( !empty(tail(listA)) )
  {
    FOR_EACH_2D(fVisitor, tail(listA), origListA, origListB, origListB)
  }
}
FOR_EACH_2D(fVisitor, listA, listB):
  FOR_EACH_2D(fVisitor, listA, listA, listB, listB)

Using our macros we get this form:

#define FOR_EACH_2D_(fVisitor, listA, origListA, listB, origListB) \
  /* Note we dont use brackets because listB is already bracketed */ \
  IF ( IS_LIST_NOT_EMPTY listB )\
  ( \
    fVisitor ( HEAD listA, HEAD listB  ) \
    FOR_EACH_2D_(fVisitor, listA, origListA, (TAIL listB), origListB) \
  , /* else */ \
    IF (IS_LIST_NOT_EMPTY ( TAIL listA ) ) \
    ( \
     FOR_EACH_2D_(fVisitor, TAIL(listA), origListA, origListB, origListB) \
    ) \
  )
#define FOR_EACH_2D(fVisitor, listA, listB) \
  FOR_EACH_2D_ ( fVisitor, listA, listA, listB, listB )

And finally applying indirection, we get the final form

#define FOR_EACH_2D_INDIRECT() FOR_EACH_2D_
#define FOR_EACH_2D_( visitorExp, listA, origListA, listB, origListB )\
  IF ( IS_LIST_NOT_EMPTY listB )\
  (\
    visitorExp( HEAD listA, HEAD listB )\
    DEFER2(FOR_EACH_2D_INDIRECT) () ( visitorExp, listA, listA, (TAIL listB), origListB )\
    ,\
    IF ( IS_LIST_NOT_EMPTY( TAIL listA ) )\
    ( \
      DEFER3(FOR_EACH_2D_INDIRECT) () ( visitorExp, (TAIL origListA), (TAIL origListA), origListB, origListB )\
    )\
  )
#define FOR_EACH_2D_NO_EVAL(visitorExp, listA, listB) \
  FOR_EACH_2D_(visitorExp, listA, listA, listB, listB)
#define FOR_EACH_2D(visitorExp, listA, listB) \
  EVAL(FOR_EACH_2D_NO_EVAL(visitorExp, listA, listB))

FOR_EACH_2D(f, (a, b), (x, y))
// Expands to f( a, x ) f( a, y ) f( b, x ) f( b, y )

We can extend this a dimension further too. Im not going to go into the derivation but its the same as the second but doing another loop. Heres what FOR_EACH_3D looks like

#define FOR_EACH_3D_INDIRECT() FOR_EACH_3D_
#define FOR_EACH_3D_( visitorExp, listA, origListA, listB, origListB, listC, origListC )\
  IF ( IS_LIST_NOT_EMPTY listC )\
  (\
    visitorExp( HEAD listA, HEAD listB, HEAD listC )\
    DEFER2(FOR_EACH_3D_INDIRECT) () ( visitorExp, listA, listA, listB, listB, (TAIL listC), origListC )\
    ,\
    IF ( IS_LIST_NOT_EMPTY( TAIL listB ) )\
    ( \
      DEFER3(FOR_EACH_3D_INDIRECT) () ( visitorExp, origListA, origListA, (TAIL origListB), (TAIL origListB), origListC, origListC )\
      IF ( IS_LIST_NOT_EMPTY( TAIL listA ) )\
      ( \
        DEFER4(FOR_EACH_3D_INDIRECT) () ( visitorExp, (TAIL origListA), (TAIL origListA), origListB, origListB, origListC, origListC )\
      )\
    )\
  )
#define FOR_EACH_3D_NO_EVAL(visitorExp, listA, listB, listC) \
  FOR_EACH_3D_(visitorExp, listA, listA, listB, listB, listC, listC)
#define FOR_EACH_3D(visitorExp, listA, listB, listC) \
  EVAL(FOR_EACH_3D_NO_EVAL(visitorExp, listA, listB, listC))

FOR_EACH_3D(f, (a, b), (x, y), (1, 2) )
/*  Expands to
    f( a, x, 1 ) f( a, x, 2 )
    f( a, y, 1 ) f( a, y, 2 )
    f( b, x, 1 ) f( b, x, 2 )
    f( b, y, 1 ) f( b, y, 2 )
*/