A short introduction to CPP meta programming techniques

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-05-19 16:27:36

A short introduction to CPP meta programming techniques
=======================================================

CPP meta programming is subject to heated discussions. Part of this is
caused by bad experiences with dangerous techniques, such as defining inline
functions using macros. As a rule of thumb, if you can find a clean and
manageable way to do something without using the CPP, then you should do it
that way. However, CPP actually enables something that no other C++ language
constructs enable: CPP can manipulate and "generate" tokens.

CPP considered harmfull
=======================

Lets first survey some of the widely known problems with using CPP in a
problem/solution format.

:::

PROBLEM: CPP does not respect scope, therefore macros can accidentally and
sometimes silently replace code.

SOLUTION A: Use all caps identifiers for macros and only macros. This
practically eliminates the possibility that a macro might replace other kind
of code accidentally.

SOLUTION B: Use the Local Macro idiom:

 #define MACRO ...
 // Use MACRO
 #undef MACRO

This makes sure that a macro can not accidentally replace code outside of
the scope of the local macro.

A problem with this solution that the #undef can not be automated and may be
forgotten. Experienced programmers generally write the #undef either before
(in time) or immediately after writing the macro definition.

SOLUTION C: Use the Unique Macro Prefix idiom:

 #define UMP_MACRO
 // Use UMP_MACRO

This makes accidental substitution and collisions highly unlikely.

Problems with this solution:
- There can still be naming collisions inside a large project.
- Macros still pollute the global namespace.

By combining all solutions, whenever possible, the scope problem can be
largely avoided.

:::

PROBLEM: CPP code is difficult to read. It requires understanding the basic
process of how the CPP recursively expands macros and finding the macro
definition and mentally substituting the parameters of the macro.

SOLUTION: Any parameterization technique, including simple functions and
templates requires finding the definition and mentally substituting
parameters. This is fundamental to parameterization and can not be avoided.
However, it is good to know a few techniques:
- By using as much Local Macros as reasonable, the bulk of the searching
process can be eliminated.
- Code browsers and text search tools make it easier to find the
definitions.
- The compiler can be used for generating the preprocessed source code in
order to look for expansion bugs.
- Before turning something into a CPP meta program, first implement a small
scale version of it without CPP. Then work bottom->up to replacing hand
written constructs by using CPP. This way you can test the code
incrementally. Experienced programmers often skip many stages, but if
something proves too complex to write directly, it is always possible to
fall back to incremental methods.

An especially important thing to remember is to limit the use of CPP to the
structured, well understood and safe methods. Structure helps to understand
complex systems (there is a reference to a number of studies on this in Code
Complete by Steve McConnell).

:::

PROBLEM: "CPP should be abolished"

SOLUTION: CPP will be here for a long time.

:::

In practice, CPP meta programming is far simpler and more portable than
template meta programming.

:::

CPP Meta Programming Techniques
===============================

The CPP meta programming techniques are presented in example format.

NOTE: I've omitted the unique prefixes from the macros in the code snippets
to make them as short and readable as possible. Don't do that in production
code!

I'm sure I've left out one or more important examples, and I'm sure that
others will find new techniques in the future.

:::

EXAMPLE: Use a Local Macro to avoid small scale repetition on site

 #define DEF(op)             \
   template<class T, int n>  \
   Vec<T,n>&                 \
     operator op##=(         \
       Vec<T,n>& lhs,        \
       const Vec<T,n>& rhs)  \
   {                         \
     for (int i=0; i<n; ++i) \
       lhs(i) op##= rhs(i);  \
     return lhs;             \
   }

 DEF(+)
 DEF(-)
 DEF(*)
 DEF(/)
 #undef DEF

TIP: It is usually okay to use a standard macro name like DEF for this kind
of code, because the macro is in the immediate site of its use.
TIP: It is easier to verify proper use of the line continuation operator
when they are aligned.

NOTES: You can extend this example by defining more and different kind of
operators. Before doing so, consider using the Algebraic Categories
technique introduced in Scientific and Engineering C++ or a layered
architecture (see for instance Generative Programming). However, at some
point you must type the operator tokens *,/,+,-,..., because it is
impossible to generate them using template meta programming. The resulting
Categorical Repetition of tokens can be eliminated using CPP meta
programming.

:::

EXAMPLE: Use EMPTY as an "unused argument"

 #define DEF(cv)        \
   template<class Base> \
   cv typename Implement_Subscript_Using_Begin_Subscript<Base>::Val_Type \
     Implement_Subscript_Using_Begin_Subscript<Base>::operator[](        \
       Idx_Type         \
         i) cv          \
   {                    \
     return Begin()[i]; \
   }

 DEF(EMPTY)
 DEF(const)
 #undef DEF

The EMPTY macro expands (eventually) to nothing and can be used as an
"unused argument".

CAVEAT: You can not safely use concatenation while using the EMPTY macro.

TIP: Occasionally one or two lines are considerably longer than the rest. It
can often save some work to not align all of the line continuation operators
without making the code too unreadable.
TIP: Use syntax highlighting on CPP meta programming macro and parameter
identifiers such as DEF, EMPTY, CAT, RPT, LST0, LST1, cv, ...

:::

EXAMPLE: Use delayed CAT instead of ## when necessary

 #define STATIC_ASSERT(expr)\
   typedef char CAT(meta_assertion_,__LINE__)[(expr) ? 1 : -1]

WHY: Macro expansion proceeds recursively in "layers". Token pasting happens
immediately and this may prevent the CPP from fully performing macro
expansion, therefore it is often necessary to delay the token concatenation.

:::

EXAMPLE: Use LIST to avoid O(n) code repetion on argument lists

 NS( namespace Private { )
   struct Make_List_End;
 NS( } )

 template
 <
 #define ARG(i) class T##i = NS(Private::)Make_List_End
   LIST(MAKE_LIST_MAX_LENGTH, COMMA_FUN, ARG)
 #undef ARG
 >
 struct Make_List
 {
 private:
   enum
   {
     end = Is_Same<T0,NS(Private::)Make_List_End>::ret
   };

   typedef typename
     IF<end,
       IDENTITY<End>,
       Make_List<
 #define ARG(i) T##i,
         LIST(MAKE_LIST_MAX_LENGTH, ARG, EMPTY_FUN)
 #undef ARG
       NS(Private::)Make_List_End
       >
     >::RET Tail_Fun;
 public:
   typedef typename
     IF<end,
       End,
       Cons<T0,typename Tail_Fun::RET>
     >::RET RET;
 };

HOW: LIST uses simulated recursion:

 // S = SEPARATOR (1,2,...), E = ELEMENT (0,1,...)
 #define LIST(n, S, E) CAT(LIST_,n)(S, E)
 #define LIST_0(S, E)
 #define LIST_1(S, E) E(0)
 #define LIST_2(S, E) LIST_1(S, E) S(1) E(1)
 #define LIST_3(S, E) LIST_2(S, E) S(2) E(2)
 // ...

COMMA_FUN(i) expands to a comma:

 #define COMMA_FUN(i) ,

EMPTY_FUN(i) expands to nothing:

 #define EMPTY_FUN(i)

:::

EXAMPLE: Use a Conditional Define to enable user configuration of code
repetition based on need rather than some "reasonable" upper limit

 #ifndef MAKE_LIST_MAX_LENGTH
 #define MAKE_LIST_MAX_LENGTH 8
 #endif

:::

EXAMPLE: Use REPT/LIST and a Token Look-Up Function to eliminate categorical
repetition

 // CAVEAT: My compiler is not standard on fundamental types.
 #define FUNDAMENTAL_NON_VOID_TYPE(i)  CAT(FUNDAMENTAL_NON_VOID_TYPE_,i)
 #define FUNDAMENTAL_NON_VOID_TYPE_0   bool
 #define FUNDAMENTAL_NON_VOID_TYPE_1   char
 #define FUNDAMENTAL_NON_VOID_TYPE_2   signed char
 #define FUNDAMENTAL_NON_VOID_TYPE_3   unsigned char
 #define FUNDAMENTAL_NON_VOID_TYPE_4   short
 #define FUNDAMENTAL_NON_VOID_TYPE_5   unsigned short
 #define FUNDAMENTAL_NON_VOID_TYPE_6   int
 #define FUNDAMENTAL_NON_VOID_TYPE_7   unsigned int
 #define FUNDAMENTAL_NON_VOID_TYPE_8   long
 #define FUNDAMENTAL_NON_VOID_TYPE_9   unsigned long
 #define FUNDAMENTAL_NON_VOID_TYPE_10  float
 #define FUNDAMENTAL_NON_VOID_TYPE_11  double
 #define FUNDAMENTAL_NON_VOID_TYPE_12  long double
 #define FUNDAMENTAL_NON_VOID_TYPE_CNT 13

 //  ...

 #define DEF(i)                           \
   catch (FUNDAMENTAL_NON_VOID_TYPE(i) t) \
   {                                      \
     Report_Typeid(t);                    \
     Report_Value(t);                     \
   }

 REPT(FUNDAMENTAL_NON_VOID_TYPE_CNT, DEF)
 #undef DEF

 // ...

NOTE: The repetition of the above example can be eliminated using template
meta programming as well. However categorical repetition of operator tokens
can not be completely eliminated by using template meta programming.

:::

EXAMPLE: Use RPTi/LSTi to avoid O(n*n) (or higher polynomial) repetition

 #ifndef MAX_VEC_ARG_CNT_PLUS_1
 #define MAX_VEC_ARG_CNT_PLUS_1 14
 #endif

 //  ...

 #define ARG_FUN(i) T a##i
 #define ASSIGN_FUN(i) (*this)[i] = a##i;

 #define DEF_VEC_CTOR_FUN(i)
   Vec( LST0(i, COMMA_FUN, ARG_FUN) )
   {
     RPT0(i, ASSIGN_FUN)
   }

 RPT1(MAX_VEC_ARG_CNT_PLUS_1, DEF_VEC_CTOR_FUN)

 #undef ARG_FUN
 #undef ASSIGN_FUN
 #undef DEF_VEC_CTOR_FUN

 // ...

HOW: RPTi and LSTi use distinct macros so it is possible to combine them as
long as each "layer" uses a distinct i.

THE END