The C++ preprocessor – recursion

I’ve been looking at how the C++ preprocessor handles recursive macros. Consider the following behavior, which is the same on MSVC++ 9.0 (Visual Studio 2008) and GNU C++ (MinGW Eclipse).

# define XX XX
# if defined( XX ) && (XX == 0)
#   // This happens
# endif

# define AA AB
# define AB AA
# if defined( AA ) && defined( AB ) && (AA == 0) && (AB == 0)
#   // This happens
# endif

This makes sense if you know the rules. They are:

  1. Be lazy. #define evaluates as little as possible. It defines the symbol as a string of tokens to be evaluated later.
  2. Evaluate when necessary. #if forces its expression to be evaluated. Except that symbols in defined(..) are not evaluated.
  3. No recursion. When a symbol is evaluated, it generates a string of tokens which are scanned again. But the original symbol is temporarily undefined while the generated symbols are scanned.
  4. Undefined evaluates to 0 (zero). An undefined symbol is 0 when #if forces evaluation.

Here’s another set of examples.

# define ITSELF ITSELF
# if defined( ITSELF ) && (ITSELF == 0)
#   // This happens
# endif

# define ITSELF2 ITSELF2 ITSELF2
// The following does not compile. "Missing right parenthesis"
/*
# if defined( ITSELF2 ) && (ITSELF2 == ITSELF2)
#   error xxkx
# endif
*/

# define ITSELF3 (ITSELF3 + ITSELF3 + ITSELF3)
# if defined( ITSELF3 ) && (ITSELF3 == 0)
#   // This happens
# endif

The last #if expands something like this.

  1. # if defined( ITSELF3 ) && (ITSELF3 == 0)
  2. # if defined( ITSELF3 ) && ((ITSELF3 + ITSELF3 + ITSELF3) == 0)
  3. # if defined( ITSELF3 ) && ((0 + 0 + 0) == 0)

Now consider this recursive definition of factorial.

# define FACTORIAL( N ) \
        (((N) == 0) ? 1 : ((N) * FACTORIAL( N - 1 )))
// The following will not compile.
/*
# if (FACTORIAL( 3 ) == 6)
# endif
*/

You can see why it doesn’t work if you expand FACTORIAL(..). (The ?: operator works fine in macros by the way.)

  1. FACTORIAL( 3 )
  2. (((3) == 0) ? 1 : ((3) * FACTORIAL( 3 – 1 )))
  3. (0 ? 1 : ((3) * FACTORIAL( 2 )))
  4. ((3) * FACTORIAL( 2 ))
  5. ((3) * 0( 2 ))

In the last step, the temporarily undefined symbol FACTORIAL becomes 0 (zero). The error message is “unmatched parenthesis: missing ‘)’”.

You see. It makes perfect sense. :)

August 14, 2008 | Filed Under C/C++, Code, Preprocessor, Programming

3 Comments 

Comments

3 Responses to “The C++ preprocessor – recursion”

  1. Mykhailo on October 25th, 2008 2:41 am

    Thanks for the very good elucidation on the topic, but if I DO want to use recursion in my macros, are there any chances for me to find a workaround?

  2. Neal on October 28th, 2008 2:52 pm

    The first thing I’d do is try to use templates instead of macros.
    You can do some amazing things with templates, and recursion is not a problem. I’ve written about templates a couple times here, and the Boost libraries have a lot of complicated examples. Look at the type_traits, MPL, and Fusion libraries.

    If templates won’t solve your problem and you need the preprocessor to get down to the tokens, take a look at the Boost Preprocessor library. It let’s you simulate recursion pretty well. I’ve written about it here.

    Or as a last resort you could write your own preprocessor. It’s not as hard as it sounds because you just have to modify an open-source (embeddable) preprocessor/tokenizer. Sounds easy, eh ;-). See Wave, which is based on Spirit.

    Let me know if any of this works out, of if you find something else interesting.

  3. Mykhailo on October 28th, 2008 6:36 pm

    Neal,

    Gosh! adapting the C++ preprocessor is too big a gun for such a small sparrow :-). I just wanted to make my header files report themselves to some kind of static metainformation manager. But still thank you for pointing out this alternative!

    Yes, I’ve resorted to template specialization and killed two birds with one stone, namely implemented both a meaningful global static assertion mechanism (by using the ‘sizeof’ operator on an undefined specialized template class) AND my beloved recursion to solve the above-mentioned challenge. With a little bit of boilerplate code pasted into each header, I’ve achieved reasonably good results.

    I knew of the Boost library before but haven’t managed to find a proper library that would do what I needed.

    Thanks for your brilliant and compendious answer and cheers!
    Mykhailo

Leave a Reply