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) -> returns f(a) f(b) f(c) f(d)
FOR_EACH(f, (a, b), (x, y)) -> returns f(a, b) f(x, y)


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
    -> HEAD(a, b, c) = a
 2) Tail: Returns everything after the first element
    -> 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
   -> IS_LIST_EMPTY()       = 1
   -> IS_LIST_EMPTY(a, b)   = 0
   -> IS_LIST_EMPTY((a, b)) = 0
   -> 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
   -> a, b           = a, b LAST
   -> (a, b), (c, d) = (a, b), (c, d) LAST
   -> <nothing>      = LAST
  We will simply take the first value of the new list and MATCH for LAST
#define IS_LIST_EMPTY(...) \
  , 0)

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)) -> 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 IF_ENCLOSED_1(true, ...) true
#define IF_ENCLOSED_0(true, ...) __VA_ARGS__
// This function will optionally remove brackets around its arguments
// if there are any. Otherwise it will return normally
#define OPT_REM_ENCLOSE(...) \

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)


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_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, ...) \

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)) -> 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 */ \
  ( \
    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_( visitorExp, listA, origListA, listB, origListB )\
    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_( visitorExp, listA, origListA, listB, origListB, listC, origListC )\
    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 )

Leave a Reply

Your email address will not be published. Required fields are marked *