Thread: Introduction to C++ Metaprogramming: Basics

Results 1 to 1 of 1
  1. #1 Introduction to C++ Metaprogramming: Basics 
    Registered Member
    Anthony`'s Avatar
    Join Date
    Sep 2008
    Age
    29
    Posts
    763
    Thanks given
    75
    Thanks received
    164
    Rep Power
    204
    This article will discuss metaprogramming in C++11 using templates, otherwise known as template metaprogramming. These examples were compiled using the latest clang C++ compiler.

    What is metaprogramming?

    Metaprogramming isn't specific to C++ only, as a matter of fact, C++'s metaprogramming facilities came as a result of a mistake due to templates being Turing-complete. Putting it simply: a language is Turing-complete if any algorithm that can be expressed as a computer program can be written in that language; C++'s templates are such a language.

    A metaprogram is a program that operates on other programs, including itself. In the context of C++, template metaprograms generally operate on types and compile-time expressions. Template metaprograms share some important features of purely functional programming:
    • Call-by-need, otherwise known as lazy evaluation. Templates are instantiated when they need to be by the compiler.
    • No side-effects. Applying functions don't produce side-effects.
    • Variable bindings are immutable.

    Let's write a metaprogram.

    Computing factorials

    A major advantage of template metaprogramming is the fact that your metaprograms will be executed during compile-time as opposed to run-time. Essentially, your compiler is executing the metaprogram and embedding its values in the source code then compiling the rest of the program. An immediate advantage is that less code execution is taking place at run-time, but as a cost of such a feature this means it takes longer for the compiler to compile the program as a whole.

    A pretty common implementation for a program that computes a factorial looks like:
    Code:
    #include <iostream>
    
    unsigned int factorial(unsigned int n) {
      return n == 0 ? 1 : n * factorial(n - 1);
    }
    
    int main() {
      std::cout << factorial(5) << std::endl;
      return 0;
    }
    As you might expect, running the program outputs 120.

    Notice that I implemented the factorial function as a recursive one, other than being easier to write, it is also how we are going to write our factorial metafunction, since it's also easier to write ion this way.

    A template metafunction is a class template that returns a type or compile-time expression. This isn't a strict definition, but I find Boost's implementations of metafunctions to be quite well-defined and concise. A template metafunction is called as such: `metafunction<args...>::type`. For now, we will be defining a numeric metafunction that doesn't exactly conform to this convention.
    Code:
    template <unsigned int n>
    struct factorial {
      static constexpr unsigned int value = n * factorial<n - 1>::value;
    };
    First, it's worth noting that this is a regular class-template except I'm using a struct here. You could just as easily use a class but recall that in C++ structs only differ from classes in visibility; by default its struct members are public, so we can avoid an extra line by using structs as our template-classes.

    Since metafunctions are executed at compile-time, the compiler needs to know that the `value` member is a compile-time expression. C++11 introduced the `constexpr` type-qualifier, but `const` could also be used (see here for differences). Also, we use the `static` qualifier so the compiler can store its value in the data segment of the program (this means we don't need to instantiate a class in order to get access to its value -- a run-time operation).

    However, there is one more thing we need to deal with: the base case. The base case for our recursive factorial metafunction is the same for its non-metafunction: when N = 1, the function should return 1. Using template specialization, this is simple:
    Code:
    template <>
    struct factorial<0> {
      static constexpr unsigned int value = 1;
    };
    Thus, our complete factorial metaprogram looks like:
    Code:
    #include <iostream>
    
    template <unsigned int n>
    struct factorial {
      static constexpr unsigned int value = n * factorial<n - 1>::value;
    };
    
    template <>
    struct factorial<0> {
      static constexpr unsigned int value = 1;
    };
    
    int main() {
      std::cout << factorial<5>::value << std::endl; // 120
      return 0;
    }
    Integral constant wrappers

    Since our metafunction will be returning a type in our next example, we need some way of encapsulating the properties of a compile-time expression such as: type, value, next/previous values, and itself. It turns out this isn't very difficult to do using `typedef`s or C++11's new `using` keyword:
    Code:
    template <int N>
    struct _int {
      using type = _int<N>;
      using value_type = int;
      static constexpr int value = N;
      using next = _int<N + 1>;
      using prev = _int<N - 1>;
    };
    If you look closely you will notice `_int<N>` in the code, which means it must instantiate itself... right? Right!? Actually, no. This is one of the features of template metaprogramming; `_int<5>` isn't instantiated until we need it, so the compiler doesn't instantiate it at all! Recall this is known as call-by-need or lazy evaluation.

    You can also spend some time implementing basic mathematical operations on integral constants like so:
    Code:
    template <typename T, typename N>
    struct plus : _int<T::value + N::value> {};
    
    template <typename T, typename N>
    struct minus : _int<T::value - N::value> {};
    Use as:
    Code:
    plus<_int<1>, _int<1>>::value // 2
    We didn't need to re-implement all of `_int`'s fields since we are forwarding them via instantiation. Another way to look at it is as if we are inheriting `_int`'s properties into its child classes (`plus` and `minus`). This technique is known as template metafunction forwarding.

    Computing binary to decimal

    This example will look at computing a metafunction that converts a binary string to its base-10 value. In this example, we will also follow Boost's convention of a metafunction.

    Following the previous section on integral constant wrappers and taking advantage of metafunction forwarding, our metaprogram looks like:
    Code:
    #include <iostream>
    
    template <unsigned int N>
    struct _uint {
      using type = _uint<N>;
      using value_type = unsigned int;
      static constexpr unsigned int value = N;
      using next = _uint<N + 1>;
      using prev = _uint<N - 1>;
    };
    
    template <>
    struct _uint<0> {
      using type = _uint<0>;
      using value_type = unsigned int;
      static constexpr unsigned int value = 0;
      using next = _uint<1>;
      using prev = _uint<0>;
    };
    
    template <unsigned int N>
    struct binary : _uint<binary<N / 10>::type::value * 2 + (N % 10)> {};
    
    template <>
    struct binary<0> : _uint<0> {};
    
    int main() {
      std::cout << binary<101>::type::value << std::endl; // 5
      return 0;
    }
    Reply With Quote  
     

  2. Thankful user:



Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. An Introduction to JAVA: The Basics.
    By `Dell in forum Application Development
    Replies: 18
    Last Post: 01-12-2011, 03:21 AM
  2. best way to learn visual basic?
    By Unity in forum Chat
    Replies: 0
    Last Post: 07-15-2009, 07:04 AM
  3. My Introduction to You!
    By Sånçtitÿ ™ in forum The Red Carpet
    Replies: 8
    Last Post: 02-07-2009, 09:54 PM
  4. [TUT]VB.NET - How to make a basic calculator[TUT]
    By Visual in forum Application Development
    Replies: 0
    Last Post: 01-28-2009, 01:29 AM
  5. How to fix some basic errors
    By Zachyboo in forum Tutorials
    Replies: 9
    Last Post: 12-17-2007, 10:35 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •