# Presentation: 001020

## C++ Meta<Programming>Concepts and Results

- Walter E. Brown
***WB@fnal.gov***
**f****  Fermi National Accelerator Laboratory**

## What is Metaprogramming?

- “The art of programming programsthat read, transform, or write other programs.”
- 				- François-René Rideau

- Let’s dream for a moment:
- Suppose we could program programsthat can “transform” _themselves_ ....

*It’s not a dream:*
*Via templates, we can do exactly that**in modern C++*!

- C++ Meta<Programming>

## Overview

- Concepts:
- Generalized parameterization via C++ templates
- Kinds of templates; kinds of template parameters
- Selected results:
- Meta-algorithms & generic programming
- Templates as general computation engines:
- Compile-time computation
- Type computations
- Compile-time control structures for selection & looping
- Meta-coding and -debugging methodologies
- Performance

- C++ Meta<Programming>

## Review of Classical Parameterization

- Function behavior is traditionally expressed in terms of placeholder objects, *parameters*:
- double  square( double x )  {  return  x * x;  }
- Specific values (*arguments*) are supplied (*passed*) when the function is *invoked*:
- ...  square( -3.14 )  ...
- Such *parameter passage*:
- Happens at run-time
- Uses *copy semantics *to initialize parameters

- C++ Meta<Programming>

## Generalized Parameterization

- Modern C++ also provides compile-time placeholders, *e.g.*, *type parameters*:
- template< typename T >
- inline  T  square( T x )  {  return  x * x;  }
- Compiler processes such a *function** **template*:
- Semantics akin to text substitution:  *instantiation*
- Yields a *specialization* (argument-specific version)
- Specialization compiled & used as a function
- No further use of template

- C++ Meta<Programming>

## Specialization Details

- A specialization is instantiated iff needed:
*... **square<double>( -3.14 ) ...*
*Template arguments* may be *deduced *from the function arguments:
- square( -3.14 );    *// implies  *square<double>(...)
- MyType  m  =  ... ;
- square( m );    *// implies  *square<MyType>(...)
- We can define our own specializations:
- template<>*    // alternate algorithm for MyType*
- double  square<MyType>( MyType x )  { ... }

- C++ Meta<Programming>

## Example:  swap<>( ) from <algorithm>

- Usual algorithm, but couched *generically* (*i.e.*, a *meta-algorithm*, applicable to many types):
- template< typename T >
- inline  void  swap( T & x, T & y )  {
-     T const  tmp( x );    x  =  y;    y  =  tmp;
- }
- Note reliance on T’s *concepts* (properties):
- In above,  T must be *copyable* and *assignable*
- Compile-time enforcement (*concept-checking*) techniques available

- C++ Meta<Programming>

## Generic Programming Pitfalls

- Extra thought is necessary when designing generic components:
- template< typename X, typename Y >  *// No!*
- void  swap( X & x, Y & y )  {
-     X const  tmp( x );    x  =  y;    y  =  tmp;
- }
- Relies on  **X ** **Y**  conversion concepts:
- Post-swap() values need not match original values
- Hence, swap() twice can’t always restore originals
- Such counter-intuitive behavior ought be avoided

- C++ Meta<Programming>

## Class Templates

- Example from <complex>:
- template< class T >  class complex  {
- public:
-     complex( T r, T i )  :  realpart(r), imagpart(i)  { }
-     T  real() const  {  return realpart;  }
*    **// ... more member functions ...*
- private:
-     T  realpart, imagpart;
- };
- Usage:
- 		complex< double >  c;

- C++ Meta<Programming>

## Class Template Details

- Each function member is a function template:
- Each is independently instantiated, iff needed
- Its template parameters match those of the class
- May have its own (additional) template parameters
- Common practice is to *publish* each class template’s arguments:
- template< class T >  class Container  {
- public:
-     typedef   T   value_type;
-     *// ...*
- };

- C++ Meta<Programming>

## Unlike Function Templates ...

- Class template arguments can’t be deduced in the same way, so usually written explicitly:
- 		complex <double>  c;
- Class template parameters may have *default values*:
- template< class T, class U = int >
- class  MyCls  {  ...  };
- Class templates may be *partially specialized*:
- template< class U >
- class  MyCls< bool, U >  {  ...  };

- C++ Meta<Programming>

## Using Specializations

- First declare (and/or define) the general case:
- template< class T >
- class  C  {  */* handle most types this way */   *};
- Then provide either or both kinds of special cases as desired:
- template< class T >
- class  C< T * >  {  */* handle pointers specially */   *};
- template<>  *// note: fully specialized*
- class  C< int * >  {  */* treat int pointers thusly */  * };
- Compiler will select the most specialized applicable class template

- C++ Meta<Programming>

## Shims

- Useful for certain kinds of boilerplate code, *e.g., *a polymorphic clone( ) function:
- class Mine  :  public Parent  {
-     virtual Mine *  clone( ) const  {
-         return new Mine(*this);    }
- };
- Awkward to maintain in a hierarchy:
- Are all clone( ) functions equivalent to begin with?
- Now change all return types to BaseCls *, or use std::auto_ptr<>, or add non-const versions, or ...
- Will need to find and update each occurrence
- Did we get them all?  Are they really consistent?

- C++ Meta<Programming>

## Shims (cont’d)

- Introduce clone shims into the hierarchy:
- class Mine    :  public CloneShim< Mine  , Parent >  { ... };
- class Yours  :  public CloneShim< Yours, Mine     >  { ... };
- All clone shims arise from one class template:
- template< class D, class B > struct CloneShim : public B  {
*    **// ... constructors ...*
-     virtual  D *  clone( ) const  {  return new D( * (D*)this );  }
- };
- Result:  a single point of code maintenance!

- C++ Meta<Programming>

## Generic Algorithms with User Plug-ins

- Functor:  a class with an operator( ) member
- Functors and functions are compatible:
- void   fn( float x )  { ... }
- struct Ftor  {  void  operator( ) ( float x )  { ... }  };
- A generic algorithm can call either kind:
- template< typename Func >
- void  algo( Func f, float q )  {  f(q);  }

*// Sample invocations of generic algorithm:*
- algo( fn, -3.14 );
- algo( Ftor( ), -3.14 );    OR    Ftor  f;  algo( f, -3.14 );

- C++ Meta<Programming>

## Non-type Template Parameters

- Non-type parameters include:
- Integral, enum. types:  int,  long,  bool,  enum,  ...
- Pointer types:	int *,  std::string *,  void (*)( int ),  ...
- Example:
- template< unsigned N >
- inline  double  pow( double x )  {
-     double  ans( 1.0 );
-     for ( unsigned k = 0;  k < N;  ++k )
-         ans  *=  x;
-     return ans;
- }

- C++ Meta<Programming>

## An Improved Algorithm

- Based on mathematical identity  xN = (x2)(N/2)
- Time complexity O(log2 N) vs. prior O(N):
- template< unsigned N >
- inline  double  pow( double x )  {
-     return  pow<N % 2>( x )  *  pow<N / 2>( x * x );
- }

- template<>
- inline  double  pow<1u>( double x )  {  return x;  }

- template<>
- inline  double  pow<0u>( double x )  {  return 1.;  }

- C++ Meta<Programming>

## Representative Timings

|  | std::pow() | pow<>() v1 | pow<>() v2 |
| --- | --- | --- | --- |
| real
user
sys | 11.858 s
11.837 s
  0.020 s | 8.081 s
8.081 s
0.020 s | 3.035 s
3.024 s
0.030 s |

-  Based on  x50  repeated 10,000,000 times
-  Using gcc 2.95.2 on 700 MHz PIII, Win2K

- C++ Meta<Programming>

## Timings with Optimization

|  | std::pow() | pow<>() v1 | pow<>() v2 |
| --- | --- | --- | --- |
| real
user
sys | 11.857 s
11.847 s
  0.020 s | 4.286 s
4.236 s
0.010 s | 0.300 s
0.190 s
0.010 s |

-  Using *g++ -O2*  to compile; otherwise same
-  Improvements:  ~47% for v1; ~90% for v2!

- C++ Meta<Programming>

## Why?

- “Most of the win ... comes from the additional optimization possibilities that are opened up.”
- 				- James Kanze

- “[Use of ] templates will often result in code that is orders of magnitude faster (because costs are pushed to compile time).”
- 				- Francis Glassborow

- C++ Meta<Programming>

## Performance for Increasing Powers

- C++ Meta<Programming>

## Template Template Parameters

- A class template can be a template argument
- Example:
- template< template<class> class Bag >
- class C  {  *// ...*
-     Bag< float >  b;
- };
- Or even:
- template< class E, template<class> class Bag >
- class C  { * // ...*
-     Bag< E >  b;
- };

- C++ Meta<Programming>

## Traits/Policies/Strategy/Behavior

- Common to generic programming:
- Instantiation G<U> needs some service, guidance, or information from U
- But G doesn’t know how to ask this of arbitrary U
- Use *non-intrusive, indirect adaptor *Tr<>:
- Typedef t or static member s of Tr<> provides an interface to the needed functionality or property
- User will specialize Tr<U> for U‘s of interest
- Instantiation G<U> uses Tr<U>::s instead of U::?

- C++ Meta<Programming>

## Using Traits/Policies

- template< class >  struct Ctraits;  {    *// default traits*

- template< class U,  template<class> class Tr = Ctraits >
- class G  {    *// generic algorithm*
-     typedef  Tr<U>::return_type  type;
-     inline  type  operator( ) ( )  {  return Tr<U>::s( ); }
- };

- template<>  struct Ctraits<int>  {    *// specialized traits*
-     typedef  double  return_type;
-     static  inline double  s( )  { return 3.14; }
- };

- ... G<int>( ) ...   * // user application code*

- C++ Meta<Programming>

## Templates in Brief

- Summary so far:
- Function templates and class templates
- Type, non-type, template template parameters
- Traits, shims, functors, generic programming
- Significant inherent computational power:
- Realized only long after templates’ initial design:
- Explains unfamiliar, somewhat awkward syntax
- Is surprisingly powerful:  Turing-completeness claimed
- Exploited via *meta-programming*, advanced compile-time computation

- C++ Meta<Programming>

## Compile-time Computation

- Compile-time absolute value:
- template< int N >
- struct Abs  {
*    **// publish computed value:*
-     static  int const  ans  =  (N < 0)  ?  - N  :  N;
- };
- Usage:
- int const  myNum  =  ...;
- Abs<myNum>::ans  *// now a compile-time const*
- We’ve barely begun the fun ...

- C++ Meta<Programming>

## Example:  General Compile-time Decisions

- Consider a *type computation*:
- template< bool, class, class >
- struct  IF  {
-     typedef  ...  type;  *// publish resulting type*
- };
- This leads to *self-configuring code*:
- int const  q  =  ... ; * // user’s configuration parameter*
*// Now compiler makes decisions based on q’s value:*
- 	IF< (q<0), int, unsigned >::type  k;   *// pick 1 of 2 types*
- 	IF< (q<0), F, G >::type( )( ... )   *// call 1 of 2 functors*
*	*class D  :    *// inherit from 1 of 2 base classes*
-     public IF< (q<0), B1, B2 >::type  { ... };

- C++ Meta<Programming>

## IF<>  Behind the Scenes

- Simplest to rely on *partial specialization*:
- template< bool c, class T, class F >
- struct IF  {    *// general case; assumes condition c is true*
-     typedef   T   type;
- };
- template< class T, class F >
- struct IF< false, T, F >  {   *// special case for false condition*
-     typedef  F  type;
- };
- Alternate (long-winded) implementations are available for broken compilers

- C++ Meta<Programming>

## Combining Some Ideas

- Compile-time greatest common divisor:
- template< int M, int N >  class Gcd  {  *// via Euclid’s method*
- private:
- 	static  int const	m  =  Abs<M>::ans,
- 				n   =  Abs<N>::ans;
-     typedef   typename IF< ( n == 0 )
- 			                        ,  GcdLast<m,n>   *// final step*
- 			                        ,  GcdNext<m,n>   *// next step*
- 			                        >::type
-           	 Step;
- public:
-     static  int const  ans  =  Step::ans;
- };

- C++ Meta<Programming>

## Gcd<>’s Helpers

- Take the next step of Euclid’s algorithm:
- template< int M, int N >  struct GcdNext  {
-     static  int const  ans  =  Gcd< N, M % N >::ans;
- };
- Interpret the result when done:
- template< int M, int >  struct GcdLast  {  // Gcd<M,0>
-     static  int const  ans  =  (M == 0)  ?  1  :  M;
- };

- C++ Meta<Programming>

## Gcd<> v2:  One Fewer Helper

- Absorb GcdNext<> into main template:
- template< int M, int N >  class Gcd  {  *// via Euclid’s method*
- private:
- 	static  int const	m  =  Abs<M>::ans,
- 				n   =  Abs<N>::ans;
-     typedef   typename IF< ( n == 0 )
- 			                        ,  GcdLast<m,n>    *// final step*
- 			                        ,  Gcd<n, m % n >  *// next step*
- 			                        >::type
- 			Step;
- public:
-     static  int const  ans  =  Step::ans;
- };

- C++ Meta<Programming>

## Gcd<> v3:  Partial Spec. as 2nd Helper

- template< int M, int N >  class Gcd  {  *// via Euclid’s method*
- private:
-     static  int const  m  =  Abs<M>::ans,
-                                     n   =  Abs<N>::ans;
- public:
-     static  int const  ans  =  Gcd< n, m%n >::ans;
- };

- template< int M >
- class Gcd<M,0>  {  *// final step; subsumes GcdLast<>, IF<>*
- public:
-     static  int const  ans  =  (M == 0)  ?  1  :  Abs<M>::ans;
- };

- C++ Meta<Programming>

## Metaprogramming Issues

- Most of us have little experience with this style of programming:
- Concepts are unfamiliar
- Utility is unfamiliar
- Thought processes are unfamiliar
- Can the process be simplified, perhaps even become formulaic?
- Yes!
- Apply elementary theory of computation

- C++ Meta<Programming>

## What is a Computation?  (Simplified)

- Computer memory defines *state*:
*S*ystematically read and concatenate all bits, then interpret as a (large!) binary number
- Start-up gives an initial state
- Now any change in memory yields a new state
- A *computation* transforms stateInit  stateFinal:
- Typically composed of a sequence of *steps*, each itself a (sub-)computation
- Commonly realized (of course!) via hardware
- Each step (*instruction*) triggers a *side effect* (memory write) when carried out (*executed*)

- C++ Meta<Programming>

## Class State

- A class’ *state* has traditionally been equated with its data members’ values:
- This is *run-time state*, for execution may change it
- If no data members, the class is deemed *stateless*
- A class’ *compile-time state* is given by:
- Internal type names (typedefs or nested classes)
- Internally initialized data members (static integral or enum. consts)

- C++ Meta<Programming>

## Example of Class State

- template< class T = double >  class Multiplier  {
- public:
-     *// compile-time state:*
-     typedef   T   value_type;
-     static  int const  t_size  =  sizeof( T );
-     Multiplier( T const & factor )  :  m(factor)  { }
-     T  operator( ) ( T const & x )  {  return  m * x;  }
- private:
-     *// run-time state:*
-     T  m;
- };

- C++ Meta<Programming>

## Compile-Time Iteration

- Design based on the C++ run-time for statement as a general looping model
- Semantics based on 4 user-supplied parts:
- Initialization: a distinguished start state
- Condition: a statebool mapping
- Body: a statestate mapping
- Reinitialization: another statestate mapping
- So a for-loop maps a 4-tuple to a (final) state

- C++ Meta<Programming>

## Mantra for Compile-Time Loop State

- Use a class template with one parameter in place of each desired variable
- Publish all the parameters
- Example:
- template< int const N, long Prod=1, int K=N >
- struct State  {
-      static int	const  n	=  N;
-      static long	const  prod	=  Prod;
-      static int	const  k	=  K;
- };

- C++ Meta<Programming>

## Mantra for Compile-Time Loop Condition

- Use a class template whole sole parameter (say, S) is a state
- Publish ans, a boolean result calculated from S’s published values
- Example:
- template< class S >  struct Cond  {
-     static  bool const  ans  =  ( S::k > 0 );
- };

- C++ Meta<Programming>

## Mantra for Compile-Time StateState Map

- Use a class template whole sole parameter (say, S) is the initial state
- Publish NextState::type, the successor state, computing its template arguments from S’s published values
- Trivial (but useful!) example:
- template< class S >
- struct DoNothing  {
-     struct NextState  {  typedef  S  type;  };
- };

- C++ Meta<Programming>

## More StateState Map Examples

*// for reference:  State< int const N, long Prod, int k >*
- template< class S >  struct Body  {
-     struct NextState  {
-         typedef  State< S::n , S::prod * S::k , S::k  > type;
-     };
- };
- template< class S >  struct Reinit  {
-     struct NextState  {
-         typedef  State< S::n , S::prod , S::k - 1 > type;
-     };
- };

- C++ Meta<Programming>

## A Convenient Wrapper using For<>

- template< int N >  struct Factorial  {
- private:
-     typedef  typename  For< State<N> , Pred , Reinit
-                                                  ,  Body
-                                                  >::type
-                      FinalState;
- public:
-     static  long const  ans  =  FinalState::prod;
- };
*// usage:*
- Factorial<10>::ans   *// now a compile-time constant!*

- C++ Meta<Programming>

## How to Test?

- First thought:
- std::cout << "0! = " << Factorial< 0 >::ans << ‘\n’;
- std::cout << “1! = " << Factorial< 1 >::ans << ‘\n’;
- std::cout << “2! = " << Factorial< 2 >::ans << ‘\n’;
- std::cout << “3! = " << Factorial< 3 >::ans << ‘\n’;
- std::cout << “4! = " << Factorial< 4 >::ans << ‘\n’;
- std::cout << “5! = " << Factorial< 5 >::ans << ‘\n’;
- Observation:  this is repetitive!
- Would prefer to let the compiler generate it:
- TestFactorial<5>( );  // this works!

- C++ Meta<Programming>

## Using For<> to Generate Code

- Initial state:
- Initialize const target  n  per argument
- Initialize counter  k = 0
- Provide constructor body with code prototype
- Predicate:  k <= n
- Reinitialization:  increment  k
- Body:  nothing to do, so just use DoNothing<>!
- Wrapper:  instantiate the loop in the constructor

- C++ Meta<Programming>

## Code Generation Loop Parts

- template< int const N, int K=0 >  struct FactTestState  {
-     static  int const  n = N;    static  int const  k = K;
-     TestFactState( )  {  *// constructor*
-         std::cout << K << "! = " << Factorial<K>::ans << '\n';
-     }
- };

- template< class S >  struct FactTestPred  {
-     static  bool const  ans  =  ( S::k <= S::n );
- };

- template< class S >  struct FactTestReinit  {
-     struct NextState  {
-         typedef  TestFactState< S::n , 1 + S::k >  type;
-     };
- };

- C++ Meta<Programming>

## Code Generation Wrapper

- template< int N >  struct FactorialTest  {
-     typedef  typename   For<  FactTestState<N>
- 					    ,   FactTestPred
- 					    ,   FactTestReinit
- 					    ,   DoNothing
- 					    >
- 			 Loop;
-     TestFact( )   {  Loop( );  }  *// constructor*
- };

- C++ Meta<Programming>

## Metaprogramming’s Memory Usage

- Code space:
- Function templates are only instantiated if called
- Use of IF<> can reduce necessary instantiations
- Code optimization opportunities are plentiful
- Data space:
- It’s like coding 1 + 2:  the object code has only a 3
- Class templates, even if instantiated, seldom leave any memory footprint for data
- “Bloat” is very often an artifact of inexperience

- C++ Meta<Programming>

## Metaprogramming’s Use of CPU Time

- Build time may increase somewhat:
- Compiler is doing (considerably) more work
- Compile time often supplants execution time
- Build time may decrease somewhat:
- Unused code is not compiled
- Better inlining decreases link time

- C++ Meta<Programming>

## Overall Metaprogramming Efficiency

- Many programmers confuse *efficiency* with *performance*:
- A program giving the wrong answer at the speed of light is fast, but certainly not efficient!
- Efficiency is correctly measured as a weighted sum of all relevant costs
- Yes, metaprogramming can certainly be an important source of improved performance
- Unfamiliar, so has a longish learning curve for now
- Rapidly becoming increasingly important in modern programming

- C++ Meta<Programming>

## For More Information

- C++ language:
- Koenig & Moo:  *Accelerated C++*, 2000
- Stroustrup:  *The C++ Programming Language*,* *Special Edition, 2000
- C++ programming technique:
- www.boost.org:  “*Generic Programming Techniques*,” 2001
- Alexandrescu:  *Modern C++ Design*, 2001
- Czarnecki & Eisenecker:  *Generative Programming*, 2000

- C++ Meta<Programming>

## Commercial #1

- Brown:  *Meta*
- Support library (headers) to facilitate C++ metaprogramming
- Experimental version now available for CVS checkout via Zoom project
- No documentation yet, but lots of test programs
- Works with:
- KAI 4.0d under Irix
- gcc 2.95.3 + STLport 4.1b5 library under Cygwin/Win2K

- C++ Meta<Programming>

## Commercial #2

- Brown:  *SIunits:  the Library of Unit-Based Computation*
- Extensive application of C++ metaprogramming
- New release in preparation
- Being adopted by JPL
- Seeking summer student to help with final details of new release, *e.g.* input, testing, documentation

- C++ Meta<Programming>

## C++ Meta<Programming>Concepts and Results

- Walter E. Brown
***WB@fnal.gov***
**f****  Fermi National Accelerator Laboratory**