Writing programs that represent and manipulate other programs or themselves (ie:reflection). Metaprograms are programs about programs.

Program generators, compilers, macros are generating code Other examples: AspectJ in aspect oriented programming and C++ templates.

introspection: the ability of a program to observe its own state

intercession: the ability to modify its own state

Dynamic languages (Smalltalk, Lisp, etc.) provide high level reflection Smalltalk: classes are objects of metaobjects methods, execution stack, etc. are represented by objects

Java provides lower level reflection

C++ RTTI much lower level: (typeid)

The main C++ template technique for metaprogramming is based on partial evaluation of templates.

float volumeOfCube( float len)
{
    return power( length, 3);
}

float power( float x, int n)
{
    float r = 1;
    for ( int i = 0; i < n; ++i)
        r *= x;
    return r;
}

Partial evaluation is a good method for compilers to increase efficiency

float volumeOfCube( float len)
{
    return power3( length);
}

float power3( float x)
{
    float r = 1;
    r *= x;
    r *= x;
    r *= x;
    return r;
}

These metaprograms run before the load time of the code they manipulate. Precompilers: C/C++ precompiler. Open compilers: like writing transformations on AST (hygenic macros). Two level languages: Aspect J, C++ templates

The first metaprogram:

// Erwin Unruh, untitled program, 
// ANSI X3J16-94-0075/ISO WG21-462, 1994.

template <int i>
struct D
{
    D(void *);
    operator int();
};

template <int p, int i>
struct is_prime
{
    enum { prim = (p%i) && is_prime<(i>2?p:0), i>::prim };
};

template <int i>
struct Prime_print
{
    Prime_print<i-1>    a;
    enum { prim = is_prime<i,i-1>::prim };
    void f() { D<i> d = prim; }
};

struct is_prime<0,0> { enum { prim = 1 }; };
struct is_prime<0,1> { enum { prim = 1 }; };
struct Prime_print<2>
{
    enum { prim = 1 };
    void f() { D<2> d = prim; }
};

void foo()
{
    Prime_print<10> a;
}

// output:
// unruh.cpp 30: conversion from enum to D<2> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<3> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<5> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<7> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<11> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<13> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<17> requested in Prime_print
// unruh.cpp 30: conversion from enum to D<19> requested in Prime_print

In the theory a Turing-complete system is one which has computational power equivalent to a universal Turing machine. The concept is named in honor of Alan Turing.

In other words, the system and the universal Turing machine can emulate each other. No computers completely meet this requirement, as a Turing machine has unlimited storage capacity, impossible to emulate on a real device. With this proviso, however, all modern computers are Turing-complete, as are all general-purpose programming languages.

Turing-completeness is significant in that every plausible design for a computing device so far advanced (even quantum computers) can be emulated by a universal Turing machine. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other computer is capable of. Note, however, that this says nothing about the effort to write a program for the machine and the time it may take to do such a calculation.

The Church-Turing thesis states that every effective computation or algorithm can be carried out by a Turing machine. The thesis, which is now generally assumed to be true, is named after Alonzo Church and/or after Alan Turing.

A few example of Turing-complete systems:

Not all problems can be solved. An undecidable problem is one that cannot be solved by any algorithm

Entscheidungsproblem (decision problem): given a statement in first-order predicate calculus, decide whether it is universally valid. Church and Turing independently proved this is undecidable.

The halting problem: given a program and inputs for it, decide whether it will run forever or will eventually halt. Turing proved this is also undecidable.

Template metaprogramming can inprove efficiency:

int factorial( int n)
{
    return (n==0) ? 1 : n*factorial(n-1)l
}

int main()
{
    cout << factorial(5) << endl;
    return 0;

But we can compute the value of the factorial function in compile-time:

// factorial.cpp

#include <iostream>

template <int N>
struct Factorial
{
    enum { value = N * Factorial<N-1>::value };
};

template <>
struct Factorial<1>
{
    enum { value = 1 };
};

// example use
int main()
{
    const int fact5 = Factorial<15>::value;
    std::cout << fact5 << endl;
    return 0;
}

In 1966 Bohm and Jacopini proved, that Turing machine implementation is equivalent the exsistence of conditional and looping control structures.

// IF

template <bool condition, class Then, class Else>
struct IF
{
    typedef Then RET;
};

template <class Then, class Else>
struct IF<false, Then, Else>
{
    typedef Else RET;
};


// if sizeof(int) < sizeof(long) then use long else use int
IF< sizeof(int)<sizeof(long), long, int>::RET  i;

This is a partial template specialization, we only specialize it on condition==false, Then and Else remains parameter.

Dynamic code is imperative, object-oriented and/or procedural. Static code is functional, similar to ML or Lisp. Functional languages has no variables, assignments, iterative constructions.

Factorial<5> --> Factorial<4> --> ... -> Factorial<0>

intermediate classes are in pending state recursive template instatiation nesting depth is limited

- ISO/ANSI recommend at least 17

- everyday compilers can do much more

- sometimes (g++) nesting depth is parameter

An other example: Combination:

//              n!
// C(k,n) = ---------
//          k! (n-k)!

template <int k, int n>
struct Combinations
{
    enum { RET = Factorial<n>::RET/(Factorial<k>::RET*Factorial<n-k>::RET) };
};

cout << Combinations<2,4>::RET << endl;

// other solution:
template <int k, int n>
class Combinations
{
private:
    enum
    {
        num   = Factorial<n>::RET,
        denum = Factorial<k>::RET * Factorial<n-k>::RET
    };
public:
    enum { RET = num / denum };
};

Template parameters are restricted to be scalars, ie. floating point arguments are not allowed. But:

template <int mantissa_, int exponent_ = 0>
struct Float
{
    enum
    {
        mantissa = mantissa_;
        exponent = exponent_;
    };
    operator const float() const
    {
        return mantissa * pow(10,exponent);
    }
};

typedef Float<25,-1>    f2p5;
typedef Sqrt<f2pt>::RET result;

cout << result() << endl;

In dynamic C++ one can use pointer to function as parameter or return value

accumulate(n,f) := f(0) + f(1) + ... + f(n)

template <int n, template<int> class F>
struct Accumulate
{
    enum { RET = Accumulate<n-1,F>::RET + F<n>::RET };
};

template <template<int> class F>
struct Accumulate<0,F>
{
    enum { RET = F<0>::RET };
};

template <int n>
struct Square
{
    enum { RET = n*n };
};

cout << Accumulate<3,Square>::RET << endl;

template <int n>
struct Factorial
{
    enum { RET = (n==0) ? 1 : Factorial<n-1>::RET * n };
};

This does not work!

struct Stop
{
    enum { RET = 1 };
};

template <int n>
struct Factorial
{
    typedef IF<n==0, Stop, Factorial<n-1> >::RET  PrevFact;
    enum { RET = (n==0) ? PrevFact::RET : PrevFact::RET * n };
};