<section id="intro">
<title>Introduction</>

<para>
Metaprogramming is usually defined as the creation of programs which generate other programs. Parser generators such as YACC <citation><xref linkend="ref.Joh79"></> are examples of one kind of program-generating program. The input language to YACC is a context-free grammar in Extended Backus-Naur Form <citation><xref linkend="ref.EBNF"></>, and its output is a program which parses that grammar. Note that in this case the metaprogram (YACC) is written in a language (&C;) which does not directly support the description of generated programs. These specifications, which we'll call <emphasis>&mdat;</>, are not written in &C;, but in a <emphasis>meta-language</>. Because the the rest of the user's program typically requires a general-purpose programming system and must interact with the generated parser, the &mdat; is translated into &C;, which is then compiled and linked together with the rest of the system. The &mdat; thus undergoes two translation steps, and the user is always very conscious of the boundary between her &mdat; and the rest of her program.
</>

<!-- ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| section -->
<section id="intro.native">
<title>Native language metaprogramming</>

<para>
A more interesting form of &mping; is available in languages such as Scheme <citation><xref linkend="ref.SS75"></>, where the generated program specification is given in the same language as the metaprogram itself. The metaprogrammer defines her meta-language as a subset of the expressible forms of the underlying language, and program generation can take place in the same translation step used to process the rest of the user's program. This
allows users to switch transparently between ordinary programming, generated program specification, and &mping;, often without being aware of the transition.
</>
</section>

<!-- ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| section -->
<section id="intro.cxx">
<title>Metaprogramming in &Cxx;</>

<para>
In &Cxx;, it was discovered almost by accident <citation><xref linkend="ref.Unr"></>, <citation><xref linkend="ref.Vel95a"></> that the template mechanism provides a rich facility for computation at compile-time. In this section, we'll explore the basic mechanisms and some common idioms used for metaprogramming in &Cxx;.
</>

<!-- ||||||||||||||||||||||||||||| subsection -->
<section id="intro.cxx.numeric">
<title>Numeric computations</>

<para>
The availability of <emphasis>non-type template parameters</> makes it possible to perform integer computations at compile-time. For example, the following template computes the factorial of its argument:
</>

<programlisting>
<![CDATA[
template< unsigned n >
struct factorial
{
    static const unsigned value = n * factorial<n-1>::value;
};

template<>
struct factorial<0>
{
    static const unsigned value = 1;
};
]]>
</>

<para>
The program fragment above is called a <emphasis>&mfn;</>, and it is easy to see its relationship to a function designed to be evaluated at runtime: the <quote>&mfn; argument</> is passed as a template parameter, and its <quote>return value</> is defined as a nested static constant. Because of the hard line between the expression of compile-time and runtime computation in &Cxx;, metaprograms look different from their runtime counterparts. Thus, although as in Scheme the &Cxx; metaprogrammer writes her code in the same language as the ordinary program, only a subset
of the full &Cxx; language is available to her: those expressions which can be evaluated at compile-time. Compare the above with a straightforward runtime definition of the factorial function:
</>

<programlisting>
unsigned factorial(unsigned N)
{
    return N == 0 ? 1 : N * factorial(N - 1);
}
</>

<para>
While it is easy to see the analogy between the two recursive definitions, recursion is in general more important to &Cxx; metaprograms than it is to runtime &Cxx;. In contrast to languages such as Lisp where recursion is idiomatic, &Cxx; programmers will typically avoid recursion when possible. This is done not only for efficiency reasons, but also because of <quote>cultural momentum</>: recursive programs are simply harder (for &Cxx; programmers) to think about. Like pure Lisp, though, the &Cxx; template mechanism is a <emphasis>functional</> programming language: as such it rules out the use of data mutation required to maintain loop variables.
</>

<para>
A key difference between the runtime and compile-time factorial functions is the expression of the termination condition: our meta-factorial uses template specialization as a kind of <emphasis>pattern-matching</> mechanism to describe the behavior when <literal>N</> is zero. The syntactic analogue in the runtime world would require two separate definitions of the same function. In this case the impact of the second definition is minimal, but in large
metaprograms the cost of maintaining and understanding the terminating definitions can become significant.
</>

<para>
Note also that a &Cxx; &mfn;'s return value must be <emphasis>named</>. The name chosen here, <literal>value</>, is the same one used for all numeric returns in the &MPL;. As we'll see, establishing a consistent naming
convention for &mfn; returns is crucial to the power of the library.
</>
</section>

<!-- ||||||||||||||||||||||||||||| subsection -->
<section id="intro.cxx.type">
<title>Type computations</>

<para>
How could we apply our <literal>factorial</> &mfn;? We might, for example, produce an array type of an appropriate size to hold all permutations of instances of another type:
</>

<programlisting>
<![CDATA[
// permutation_holder<T>::type is an array type which can contain 
// all permutations of a given T.

// unspecialized template for scalars
template< typename T >
struct permutation_holder
{
    typedef T type[1][1];
};

// specialization for array types
template< typename T, unsigned N >
struct permutation_holder<T[N]>
{
    typedef T type[factorial<N>::value][N];
};
]]>
</>

<para>
Here we have introduced the notion of a <emphasis>type computation</>.  Like <literal>factorial</> above, <literal>permutation_holder</> template is a &mfn;. However, where <literal>factorial</> manipulates unsigned integer values, <literal>permutation_holder</> accepts and <quote>returns</> a type (as the nested typedef <literal>type</>). Because the &Cxx; type system provides a much richer set of expressions than anything we can use as a nontype template argument (e.g. the integers), &Cxx; metaprograms tend to be composed mostly of type computations.
</>
</section>

<!-- ||||||||||||||||||||||||||||| subsection -->
<section id="intro.cxx.seq">
<title>Type sequences</>

<para>
The ability to programmatically manipulate collections of types is a central tool of most interesting &Cxx; metaprograms. Because this capability is so well-supported by the &MPL;, we'll provide just a brief
introduction to the basics here. Later on, we'll revisit the example below to show how it can be implemented using &MPL;.
</>

<para>
First, we'd need a way to represent the collection. One idea might be to store the types in a structure:
</>

<programlisting>
<![CDATA[
struct types
{
    int t1;
    long t2;
    std::vector<double> t3;
};
]]>
</>

<para>
Unfortunately, this arrangement is not susceptible to the compile-time type introspection power that &Cxx; gives us: there's no way to find out what the names of the members are, and even if we assume that they're named according to some convention as above, there's no way to know how many members there are. The key to solving this problem is to
increase the uniformity of the representation. If we have a consistent way to get the first type of any sequence and the rest of the sequence, we can easily access all members:
</>

<programlisting>
<![CDATA[
template< typename First, typename Rest >
struct cons
{
    typedef First first;
    typedef Rest rest;
};

struct nil {};

typedef
      cons<int
    , cons<long
    , cons<std::vector<double>
    , nil
    > > > my_types;
]]>
</>

<para>
The structure described by <literal>types</> above is the compile-time analogue of a singly-linked list; it has been first introduced by Czarnecki and Eisenecker in <citation><xref linkend="ref.ce98"></>. Now that we've adjusted the structure so that the &Cxx; template machinery can <quote>peel it apart</>, let's examine a simple metafunction which does so. Suppose a user wished to find the largest of an arbitrary collection of types. We can apply the recursive &mfn; formula which should by now be familiar:
</>

<example id="example.largest">
<title>'largest' metafunction</>
<programlisting>
<![CDATA[
// choose the larger of two types
template<
      typename T1
    , typename T2
    , bool choose1 = (sizeof(T1) > sizeof(T2)) // hands off!
    >
struct choose_larger
{
    typedef T1 type;
};

// specialization for the case where sizeof(T2) >= sizeof(T1)
template< typename T1, typename T2 >
struct choose_larger< T1,T2,false >
{
    typedef T2 type;
};

// get the largest of a cons-list
template< typename T > struct largest;