Where do normal templates end and meta templates begin?

Question

Jörg's answer to this question nicely delineates between "normal" templates (what the question refers to, perhaps erroneously, as generics) which operate on data and meta templates which operate on a program. Jörg then wisely mentions that programs are data so its really all one and the same. That said, meta-templates are still a different beast. Where do normal templates end and meta templates begin?

The best test I can come up with is if a template's arguments are exclusively class or typename the template is "normal" and meta otherwise. Is this test correct?

Cock

Then what about std::array<typename T, size_t n>? Is it normal or meta? I'd say that templates are "meta" when they are somehow used at compile-time but never instantiated. – Trask

@HenriMenke, my test would say meta as the parameters are not exclusively class or typename. What I don't know is if my test is correct or not ;) – Cock

Answer 1

Attempt to differentiate and define the terms

Let's first try to roughly define the terms. I start with a hopefully good enough definition of "programming", and then repeatedly apply the "usual" meaning of meta- to it:

programming

Programming results in a program that transforms some data.

int add(int value) { return value + 42; }

I just wrote code that will result in a program which transforms some data - an integer - to some other data.

templates (meta programming)

Meta programming results in a "program" that transforms some program into another. With C++ templates, there's no tangible "program", it's an implicit part of the compiler's doings.

template<typename T>
std::pair<T,T> two_of_them(T thing) {
  return std::make_pair(thing, thing);
}

I just wrote code to instruct the compiler to behave like a program that emits (code for) another program.

meta templates (meta meta programming?)

Writing a meta template results in a ""program"" that results in a "program" which results in a program. Thus, in C++, writing code that results in new templates. (From another answer of me:)

// map :: ([T] -> T) -> (T -> T) -> ([T] -> T)
//         "List"       "Mapping"   result "type" (also a "List")
// --------------------------------------------------------
template<template<typename...> class List,
         template<typename> class Mapping>
struct map {
  template<typename... Elements>
  using type = List<typename Mapping<Elements>::type...>;
};

That's a description of how the compiler can transform two given templates into a new template.

Possible objection

Looking at the other answers, one could argue that my example of meta programming is not "real" meta programming but rather "generic programming" because it does not implement any logic at the "meta" level. But then, can the example given for programming be considered "real" programming? It does not implement any logic either, it's a simple mapping from data to data, just as the meta programming example implements a simple mapping from code (auto p = two_of_them(42);) to code (the template "filled" with the correct type).

Thus, IMO, adding conditionals (via specialization for example) just makes a template more complex, but does not change it's nature.

Your test

Definitively no. Consider:

template<typename X>
struct foo {
  template<typename Y>
  using type = X;
};

foo is a template with a single typename parameter, but "results" in a template (named foo::type ... just for consistency) that "results" - no matter what parameter is given - to the type given to foo (and thus to the behavior, the program implemented by that type).

Gurrola

I like your explanation that "normal" templates is meta programming and "meta-templates" is meta-meta-programming. – Cock

Answer 2

The boundary: Signature with Logical Behaviour

Well, in my opinion the boundary-line is to be drawn where a template's signature stops to be a simple signature yielding runtime-code and becomes a definition of explicit or implicit logic, which will be executed/resolved at compile-time.

Some examples and explanation

Regular Templates, i.e. with only typename, class or possibly value-type template parameters, produce executable cpp code, once instantiated during compile time.

The code is (important) not executed at compile time

E.g. (very simple and most likely unrealistic example, but explains the concept):

template<typename T>
T add(const T& lhs, const T& rhs) {
    return(lhs + rhs);
}

template<>
std::string add<std::string>(
                const std::string& lhs,
                const std::string& rhs) {
     return (lhs.append(rhs));
}

int main() {
    double      result = add(1.0, 2.0); // 3.0
    std::string s      = add("This is ", " the template specialization..."); 
}

Once compiled, the root-template will be used to instantiate the above code for the type double, but will not execute it. In addition, the specialization-template will be instantiated for the text-concatenation, but also: not executed at compile time.

This example, however:

#include <iostream>
#include <string>
#include <type_traits>

class INPCWithVoice {
    void doSpeak() { ; }
};

class DefaultNPCWithVoice 
    : public INPCWithVoice {
    public:
        inline std::string doSpeak() {
            return "I'm so default, it hurts... But at least I can speak...";
        }
}; 

class SpecialSnowflake
    : public INPCWithVoice {
    public:
        inline std::string doSpeak() {
            return "WEEEEEEEEEEEH~";   
        }
};

class DefaultNPCWithoutVoice {
    public:
         inline std::string doSpeak() {
            return "[...]";
        }
};

template <typename TNPC>
static inline void speak(
    typename std::enable_if<std::is_base_of<INPCWithVoice, TNPC>::value, TNPC>::type& npc) 
{
    std::cout << npc.doSpeak() << std::endl;
};

int main()
{
    DefaultNPCWithVoice    npc0 = DefaultNPCWithVoice();
    SpecialSnowflake       npc1 = SpecialSnowflake();
    DefaultNPCWithoutVoice npc2 = DefaultNPCWithoutVoice();

    speak<DefaultNPCWithVoice>(npc0);
    speak<SpecialSnowflake>(npc1);
    // speak<DefaultNPCWithoutVoice>(npc2); // Won't compile, since DefaultNPCWithoutVoice does not derive from INPCWithVoice
}

This sample shows template meta programming (and in fact a simple sample...). What happens here, is that the 'speak'-function has a templated parameter, which is resolved at compile time and decays to TNPC, if the type passed for it is derived from INPCWithVoice.

This in turn means, if it doesn't, the template will not have a candidate for instantiation and the compilation already fails. Look up SFINAE for this technique: http://eli.thegreenplace.net/2014/sfinae-and-enable_if/

At this point there's some logic executed at compile time and the entire program, will be fully resolved once linked to the executable/library

Another very good example is: https://akrzemi1.wordpress.com/2012/03/19/meta-functions-in-c11/

Here you can see a template meta programming implementation of the factorial-function, demonstrating, that even the bytecode can be entirely equal to a fixed-value use, if the meta-template decays to a constant.

Finalizing example: Fibonacci

#include <iostream>
#include <string>
#include <type_traits>

template <intmax_t N>
static unsigned int fibonacci() {
    return fibonacci<N - 1>() + fibonacci<N - 2>();     
}

template <>
unsigned int fibonacci<1>() {
    return 1;   
}

template <>
unsigned int fibonacci<2>() {
    return fibonacci<1>();    
}

template <intmax_t MAX>
    static void Loop() {
    std::cout << "Fibonacci at " << MAX << ": " << fibonacci<MAX>() << std::endl;
    Loop<MAX - 1>();
}

template <>
void Loop<0>() {
    std::cout << "End" << std::endl;    
}

int main()
{
    Loop<10>();
}

This code implements scalar template argument only template meta programming for the fibonacci-sequence at position N. In addition, it shows a compile-time for loop counting from 10 to 0!

Finally

I hope this clarifies things a bit.

Remember though: The loop and fibonacci examples instantiate the above templates for each index!!!

Consequently, there's a horrible amount of redundancy and binary bloat!!!

I'm not the expert myself and I'm sure there's a template meta programming kung fu master on stackoverflow, who can append any necessary information missing.

Sweptback

please avoid all caps lock words. It looks like YOU ARE SCREAMING AT US!!! If you want to emphasize use bold or italic, but don't overuse that either. – Jamison

I do not understand your point. There is a lot of text and code and I feel it doesn't convey your point (at least to me). – Jamison

@Jamison Thanks for the remark, fixed it. Yes there's a lot of explanation and examples to underline the point in "Where's the boundary now"... – Sweptback

Answer 3

Let me start answering using a definition from dictionary.com

Definition

meta -

2. a prefix added to the name of a subject and designating another subject that analyzes the original one but at a more abstract, higher level: metaphilosophy; metalinguistics.

3. a prefix added to the name of something that consciously references or comments upon its own subject or features: a meta-painting of an artist painting a canvas.

Template programming is formost used as a way to express relations in the type system of C++. I would argue it is therefore fair to say that template programming inherently makes use of the type system itself.

From this angle of perspective, we can rather directly apply the definition given above. The difference between template programming and meta (template-)programming lies the treatment of template arguments and the intended result.

Template code that inspects its arguments clearly falls into the former defintion while the creation of new types from template arguments arguably falls into the later. Note that this must also be combined with the intent of your code to operate on types.

Examples

Let's take a look at some examples:

Implementation of std::aligned_storage;

template<std::size_t Len, std::size_t Align /* default alignment not implemented */>
struct aligned_storage {
    typedef struct {
        alignas(Align) unsigned char data[Len];
    } type;
};

This code fulfills the second condition, the type std::aligned_storage is used to create another type. We could make this ever clearer by creating a wrapper

template<typename T>
using storage_of = std::aligned_storage<sizeof(T), alignof(T)>::type;

Now we fulfill both of the above, we inspect the argument type T, to extract its size and aligment, then we use that information to construct a new type dependent on our argument. This clearly constitutes meta-programming.

The original std::aligned_storage is less clear but still quite pervasive. We provide a result in the form of a type, and both of the arguments are used to create a new type. The inspection arguably happens when the internal array type of type::data is create.

A counter examples for completeness of the argument:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue { /*Implementation defined implementation*/ };

Here, you might have the question:

But doesn't priority queue also do type inspection, for example to retrieve the underlying Container, or to assess the type of its iterators?

And yes it does, but the goal is different. The type std::priority_queue itself does not constitute meta template programming, since it doesn't make use of the information to operate within the type system. Meanwhile the following would be meta template programming:

template<typename C>
using PriorityQueue = std::priority_queue<C>;

The intent here is to provide a type, not the operations on the data themselves. This gets clearer when we look at the changes we can make to each code.

We can change the implementation of std::priority_queue maybe to change the permitted operations. For example to support a faster access, additional operations or compact storage of the bits inside the container. But all of that is entirely for the actual runtime-functionality and not concerned with the type system.

In contrast look at what we can do to PriotityQueue. If we were to choose a different underlying implementation, for example if we found that we like Boost.Heap better or that we link against Qt anyways and want to choose their implementation, that's a single line change. This is what meta programming for, we make choices within the type system based arguments formed by other types.

(Meta-)Template signatures

Regarding your test, as we have seen above, storage_of has exclusively typename arguments but is very clearly meta programming. If you dig deaper, you will find that the type system itself is, with templates, Turing-complete. Without even needing to explicitely state any integral variables, we could for example easily replace them by recursively stacked templates (i.e. Zermelo construction of the natural numbers)

using Z = void;
template<typename> struct Zermelo;
template<typename N> using Successor = Zermelo<N>;

A better test in my eyes would be to ask if the given implementation has runtime effects. If a template struct or alias does not contain any definition with an effect only happening at runtime, it's probably template meta programming.

Closing words

Of course normal template programming might utilize meta template programming. You can use meta template programming to determine properties of normal template arguments.

For example you might choose different output strategies (assuming some meta-programming implementation of template<class Iterator> struct is_pointer_like;

template<class It> generateSomeData(It outputIterator) {
    if constexpr(is_pointer_like<outputIterator>::value) {
        generateFastIntoBuffer(static_cast<typename It::pointer> (std::addressof(*outputIterator));
    } else {
        generateOneByOne(outputIterator);
    }
}

This constitutes template programming employing the feature implemented with meta template programming.

Raeannraeburn

Answer 4

Where do normal templates end and meta templates begin?

When the code generated by templates rely on the fundamental aspects of programming, such as branching and looping, you have crossed the line from normal templates to template meta programming.

Following the description from the article you linked:

A regular function

bool greater(int a, int b)
{
   return (a > b);
}

A regular function that works with only one type (ignoring implicit conversions for the time being).

A function template (generic programming)

template <typename T>
bool greater(T a, T b)
{
   return (a > b);
}

By using a function template, you have created generic code that can be applied to many types. However, depending on its usage, it may not be correct for null terminated C strings.

Template Metaprogramming

// Generic implementation
template <typename T>
struct greater_helper
{
   bool operator(T a, T b) const
   {
     return (a > b);
   }
};

template <typename T>
bool greater(T a, T b)
{
   return greater_helper<T>().(a > b);
}

// Specialization for char const*
template <>
struct greater_helper<char const*>
{
   bool operator(char const* a, char const* b) const
   {
     return (strcmp(a, b) > 0);
   }
};

Here, you have written code as if to say:

If T is char const*, use a special function.
For all other values of T, use the generic function.

Now you have crosses the threshold of normal templates to template metaprogramming. You have introduced the notion if-else branching using templates.

Weldonwelfare

Does this mean that one cannot tell if a template is meta by only looking at it's signature? From what you said it sounds like you'd have to look at the surrounding templates to know for sure. – Cock

@chessofnerd, if the behavior of the template is clearly documented, it might give clues on whether it a simple template or does it use template metaprogramming. Looking at its implementation and the implementations of what it relies on will definitely be more revealing. – Weldonwelfare

I like your answer's brevity and clarity; however, I'm still a smidge confused. Can you give me an explicit yes-no on if my test is correct? If no, can you modify it? – Cock

@chessofnerd, the answer is "no". – Weldonwelfare