C++ Template Metaprogramming

Note: with C++14 & C++17 life gets much better with constexpr. Details: computing-exp-at-compile-time and constexpr2

factorial(number) = 1 * 2 * 3 * … * (n-1) * n

1
2
3
4
5
6
7
8
9
static int factorial_imperative(int value)
{
    int factorial = 1;
    for(auto idx = value; idx > 1; --idx )
    {
        factorial *= idx;
    }
    return factorial;
}

Very compact code, which is good as well as bad for it can be difficult to understand at times
Understanding when to stop, specifying termination condition correctly

So here is the recursive and immutable version for evaluating factorial:

1
2
3
4
5
6
static int factorial_recursive(int value)
{
    return
            value <= 1 ? 1 :
            (value * factorial_recursive(value-1));
}

we are not mutating any variable, even though we generate new values due to recursion but we are not mutating
well defined termination condition, at line 4: value <= 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//  in metaprogram every thing is a template-class/struct
template<int Num>
struct factorial_c
{
enum
    {
        value = Num * factorial_c<Num-1>::value
    };
};

//  terminating conditions
//
//  factorial of 1 is 1
//
template<>
struct factorial_c<1>
{
    enum
    {
        value = 1
    };
};


//  factorial of 0 is 1
//
template<>
struct factorial_c<0>
{
    enum
    {
        value = 1
    };
};


int main()
{
    auto factorial_5 = factorial_c<5>::value;
    std::cout << "factorial of 5 is "
              << factorial_5 << std::endl;
    return 0;
}

Here is how the compiler evaluates the template recusions:

1
2
3
4
5
6
7
factorial_5 = factorial_c<5>::value;
factorial_5 = 5 * factorial_c<4>::value;
factorial_5 = 5 * 4 * factorial_c<3>::value;
factorial_5 = 5 * 4 * 3 * factorial_c<2>::value;
factorial_5 = 5 * 4 * 3 * 2 * factorial_c<1>::value;
factorial_5 = 5 * 4 * 3 * 2 * 1;
factorial_5 = 120;

Recursive & Immutable runtime code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
static int gcd_recursive(int a, int b)
{
    if( a == b )
    {
        return a;
    }
    //
    auto max = a > b ? a : b;
    auto min = a < b ? a : b;
    //
    //
    if( min == 0 )
    {
        return max;
    }
    return gcd_recursive(min, max % min);
}

TMP:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//  equivalent to max function
//
template<int One, int Two>
struct  max_c
{
    enum
    {
        value = One > Two ? One : Two
    };
};
//
//
//  equivalent to min function
//
template<int One, int Two>
struct min_c
{
    enum
    {
        value = One < Two ? One : Two
    };
};
//
//
//  TMP version of gcd
//
template<int One, int Two>
struct gcd_c
{
    enum
    {
        //  equivalent to:
        //  value = gcd(min, max % min)
        //
        value = gcd_c<  min_c<One, Two>::value,
                        max_c<One, Two>::value %
                        min_c<One,Two>::value>::value
    };
};
//
//
//  template specialization for
//  Min being 0, this is our
//  termination condition for recursion
//
template<int Max>
struct gcd_c<Max, 0>
{
    enum
    {
        value = Max
    };
};

lcm (least common multiple)

Recursive & Immutable runtime code:

1
2
3
4
static int lcm_r(int one, int two)
{
    return one * two / gcd_recursive(one, two);
}

TMP:

1
2
3
4
5
6
7
8
template<int One, int Two>
struct lcm_c
{
    enum
    {
        value = One * Two / gcd_c<One, Two>::value
    };
};

Parting Thoughts

Well I don’t have summary for this post, as it is not yet finished. We have barely scratched the surface of this beast. C++ TMP has a complete language of its own, well thats what Boost.MPL library is all about. I will follow up on TMP with few more posts.

C++