Template meta-programming in C++

1. C++ templates are parameterized declarations
 - class templates (struct similar)
 template<class T>   // template parameter declaration
 class stack {
     std::vector<T> s; // parameter used as template argument
  public:
     void push(const T& t);   // template parameter usage
     T pop();
     bool is_empty() { ... }
 };

 - function templates: parameterises concrete function on argument type
 template<class T>
 T min(const T& a, const T& b){
    if(a < b) return a;
    else return b;
 }

 http://www.cplusplus.com/doc/oldtutorial/templates/

 https://msdn.microsoft.com/en-us/library/y097fkab.aspx


2. Templates and Polymorphism
 : Templates implement parametric polymorphism: (almost) no assumptions about template parameter


3. Template Parameters
 - types / classes: most common cases
  1) usually denoted by class keyword
  2) alternative syntax: typename

 - non-types: can have (integral type) value arguments but class templates only
  template<class T, int Max>

 - templates: type parameters can be class templates
  template<template <class T> class TT>

 - all parameter classes can be defaulted:
 struct nil {};
 template<class T = nil, int Max = 10>
 class tuple;
 tuple<int, float, char> a;
 tuple<std::string> b;


4. Template instantiation is syntactic macro expansion
 : instantiation of (non-default) parameters with arguments triggers expansion by compiler
 : fully expanded template is like normal type
 - function templates can be implicitly instantiated
 int smaller = ::min(1,2);
 std::string a("Cat"), b("Hat")l
 std::string first = ::min(a, b);
 - Template instantiation and Code bloat
  => Implementation usually follows instantiation model
  => for each template instance, a separate piece of code is generated, and compiled: no sharing between different template instrances

 http://www.cplusplus.com/forum/articles/14272/

 http://stackoverflow.com/questions/24333345/how-does-template-cause-the-code-bloat-in-c


5. Template Specialization
 - a program can provide specialised versions of templates
 - specialisation redefines entire templates: no "inheritance" of member functions
 - a compiler must select the most specialised instance
 ! T1 more specialised than T2 ( T1 > T2 )
  iff "every template argument list that matches T1 also matches T2, but not vice versa"
 !! T1 is maximally specialised (wrt. T)
  iff it matches T and there is no more specialised T2 matching T
 !!! compile-time error if no matching instance at all / no unique maximally specialised template for instance

 - specialisation is allowed for all template parameters
 - requires compile-time expression evaluation
 - selection of most specialised instances can encode conditionals
 http://www.cprogramming.com/tutorial/template_specialization.html


6. Template meta-functions can mix compile-time and run-time arguments
 template<int n>
 int power(int m){
     return power<n-1>(m) * m;
 }
 template<> int power<0>(int m){ return 1; }


7. Template meta-programming
 : template meta-programming is partial evaluation
 https://en.wikipedia.org/wiki/Partial_evaluation

 : no binding time analysis but staging
  => turning function arguments into template arguments


8. Concepts of the Template Meta-programming Language
 - Class templates as functions
  1) input: integers or types (realised by template parameters)
  2) output: integers or types (realised by enum or typedef called RET)

 - Integers and types as data
 - Symbolic names instead of variables
  1) constant initialization / typedef instead of assignment
  2) no update
 - Lazy evaluation: template only instantiated if struct accessed (via ::)

 https://en.wikipedia.org/wiki/Template_metaprogramming

 https://www.codeproject.com/Articles/3743/A-gentle-introduction-to-Template-Metaprogramming

Template IF<>	Template WHILE<>
IF<> as "syntactic sugar" for specialisation	WHILE<> as "syntactic sugar" for recursion
template<bool Cond, class Then, class Else>  struct IF {     typedef Then RET;  };  // only specialisation for Cond==false required  template<class Then, class Else>  struct IF<false, class Then, class Else> {     typedef Else RET;  };  // usage  IF<1==0, int, double>::RET f; // double f;  const static int g = IF<1==0, Zero, One>::RET; // g = One::RET;	template<class Stmt>  struct STOP {     typedef Stmt RET;  }  template<class Cond, class Stmt>  struct WHILE {     typedef IF<Cond::template Code<Stmt>:: RET,                WHILE<Cond, typename Stmt::Next>,                STOP<Stmt>              >::RET::RET     RET  }

 

Fibonacci via Templates

template<int n>  struct Fibonacci {      enum { RET = WHILE<FibCond<n>,                               FibStat<1, 1, 0>                       >::RET::x             };  };  template<int i_, int x_, int y>  struct FibStat {      enum { i = i_, x = x_ };      typedef FibStat<i+1, x+y, x> Next;  };  template<int n>  struct FibCond {     template<class Memory>     struct Code {         enum { RET = Memory::i < n };     };  };

 

Loop Unrolling via an (inlined) function templates

template<int n>  inline void addVect(double* c, double* a, double* b){     *c = *a + *b'     addVect<n - 1>(c + 1, a + 1, b + 1);  }  template<>  inline void addVect<0>(double* c, double* a, double* b){ }

 

Loop Unrolling via Templates

template<int n, class B>  struct FOR {      static void loop(int m){         for(int i = 0 ; i < m/n ; i++){            UNROLL<n, B>::iteration(i * n);         }         for(int i = 0 ; i < m%n ; i++){            B::body(n * m/n + i);         }      }  };  template<int n, class B>  struct UNROLL {      static void iteration(int i){         B::body(i);         UNROLL<n-1, B>::iteration(i + 1);      }  };  template<class B>  struct UNROLL<0, B> {      static void iteration(int i) { }  };  class AddVecBody {      private double *a, *b, *c;      inline void body(int i){         *(c+1) = *(a+1) + *(b+1);      }  };  // Add two 1000-element vectors in chunks of 4  FOR<4, AddVecBody>::loop(1000);

 

Encoding Abstract Data Types

1) use class templates as constructor functions  2) represent fields via   - enum (== values)   - typedef (== pointers)   - copy constructor arguments into local fields  3) use class templates to implement methods  https://en.wikipedia.org/wiki/Abstract_data_type

struct Nil {     enum { head = ERROR };     typedef Nil Tail;  };  template<int head_, class Tail_ = Nil>  struct Cons {     enum { head = head_ };     typedef Tail_ Tail;  };  // recurse over lists, stop via specialisation  template <class List>  struct Length {     enum { RET = Length<typename List::Tail>::RET + 1 };  };  template <>  struct Length<Nil> {     enum { RET = 0 };  };  template <class L1, class L2>  struct Append {     typedef Cons<L1::head,                    typename Append<typename L1::Tail, L2>::RET              > RET;  };  template <class L2>  struct Append<Nil, L2> {     typedef L2 RET;  };

 

Expression Templates

Template meta-programming can implement domain-specific languages   1) Expression template represents AST   2) class templates implement AST transformations   3) eval method links syntax (AST) to semantics (C++): inline trick allows code generation   4) function templates using overloaded operations provided syntactic sugar    https://en.wikipedia.org/wiki/Expression_templates    https://www.codeproject.com/Articles/998366/Gentle-introduction-into-expression-templates

// General expression template: scalar with eval  template <class L, class BinOp, class R>  class Expr {     L &l_; R &r_;    public:     Expr(const L &l, const R &r) : l_(l), r_(r) {};     double eval(){         return BinOp::apply(l_, r_);     }     // vector with index     double operator[](uint i){ return BinOp::apply(l_[i], r_[i]); };  };  // operator tags; similar for minus, times, ...  class plus {      inline double apply(double a, double b){ return (a+b); }  };  // additional operator; similar for minus, times, ...  template<class L, class R>  Expr<L, plus, R> operator+(const L &l, const R &r){ return Expr<L, plus, R>(l, r); };