[ishkabible]

C++ Challenge: Template Meta Programming

Template Meta Programming (TMP) was accidentally discovered and was not an intended feature of the language. It has many applications such as generating complex code at compile time and writing compile time checks to see if a type satisfies a given condition. It is a Turing complete language in and of itself. It is purely functional as well. Like all functional languages it can manipulate lists. Lists can be represented as a type which stores 2 other types one of which can be another pair; that can continue until a terminating value is reached. Functions can be represented as template classes.

I present to you a small framework for creating template meta lists and a couple of meta functions which can be applied to lists using a left fold. Your challenge is to write a class (or meta function) that performs a left fold. 2 test cases are in used in main.

#include <iostream>

//specil type for ending lists
struct meta_null {};

//type to hold value pairs; these pairs can form lists
template<class Head, class Tail>
struct meta_pair {
	typedef Head head;
	typedef Tail tail;
};

//a simple type that holds a value
template<int x>
struct meta_int {
	static const int value = x;
};

template<class I1, class I2>
struct add {
	typedef meta_int<I1::value + I2::value> value;
};

template<class I1, class I2>
struct mul {
	typedef meta_int<I1::value * I2::value> value;
};

int main() {
	typedef meta_pair<meta_int<1>,
			meta_pair<meta_int<2>,
			meta_pair<meta_int<3>,
			meta_pair<meta_int<4>,
            meta_pair<meta_int<5>, meta_null> > > > > test_list;
	//find the sum of values in the list
    std::cout<<fold_l<add, meta_int<0>, test_list>::value::value;
    std::cout<<'\n';
	std::cout<<fold_l<mul, meta_int<1>, test_list>::value::value;
    return 0;
}

For added challenge write a...

• right fold function
  
• a map function
  
• a sum function (sums a list)
  
• a product function (product of list).
  
• something i haven't thought of

Also, if you have any other TMP goodies, It would be nice if you could posts those too


hint 1:

Spoiler

to accept an un-applied template you can use the following syntax

template<template<class, class> class f>

that is a template which accepts a template that accepts two types as arguments.

hint 2:

Spoiler

template specialization is a very useful tool

hint 3:

Spoiler

it can be useful to look at a implementation; here is one in Haskell

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

If your struggling with TMP or simply want to know more about it, i recommend reading this article which compares TMP to Haskell. The same author also has this article on TMP

This post has been edited by ishkabible: 06 December 2011 - 03:59 PM

[sepp2k]

Is there a particular reason that you chose meta_null as the identity element for summation instead of meta_int<0>? Semantically it seems very strange to me that a binary addition function would even accept the empty list as a valid operand.

Oh, and regarding the rules of the contest: Is it okay if we modify the given template to some degree in our solution? And are C++11 features allowed (specifically I'm thinking about introducing a helper-template that allows easier construction of lists using variadic templates).

This post has been edited by sepp2k: 06 December 2011 - 07:08 AM

[Karel-Lodewijk]

I was experimenting with something similar using c++11 variadic templates. It is something like the new std::tuple. Look at the main fucntion to see what it actually does.

Not actually an entry to the competition as the data is not meta_data, the types are, but interesting non the less.

Spoiler

#include <iostream>
#include <string>
#include <functional>

//this is only nescessary to satisfy gcc
template <unsigned index, typename... T>
class Type_deductor;

//this is only nescessary to satisfy gcc
template <typename... T>
class Tuple;

template <unsigned index, typename T, typename... tailT> 
struct Type_deductor<index, T, tailT...> {
   typedef typename Type_deductor<index-1, tailT...>::type type;
   
   static type& get(Tuple<T, tailT...>& tuple) {
       return Type_deductor<index-1,tailT...>::get(tuple.tail());
   }
};

template <typename T, typename... tailT> 
struct Type_deductor<0, T, tailT...> {
    typedef T type;
    
    static type& get(Tuple<T, tailT...>& tuple) {
        return tuple.head();
    }
};

template<typename T, typename... tailT> 
class Tuple<T, tailT...> : public Tuple<tailT...> {
  public:   
    Tuple() {}
    Tuple(const T& head, const tailT&... tail) : Tuple<tailT...>(tail...), _head(head) {}
    template <typename... tailT2> 
    Tuple(const T& head, const tailT2&... tail) : Tuple<tailT...>(tail...), _head(head) {}
    
    template<typename... T2>
    Tuple(const Tuple<T2...>& other) : _head(other.head()), Tuple<tailT...>(other.tail()) {} 
    Tuple(const Tuple<>& other) {} 

    template<typename... T2>
    Tuple<T, tailT...>& operator=(const Tuple<T2...>& other) {
        _head = other.head();
        this->Tuple<tailT...>::operator=(other.tail());
    }
    
    Tuple<T, tailT...>& operator=(const Tuple<>& other) { return *this; }

    T& head() {return _head;}
    const T& head() const {return _head;}
    
    Tuple<tailT...>& tail() {return *this;}
    const Tuple<tailT...>& tail() const {return *this;}

    template <unsigned int index>
    typename Type_deductor<index, T, tailT...>::type& get() {
        return Type_deductor<index, T, tailT...>::get(*this);
    }

    template <class... S>
    bool operator==(const Tuple<S...>& other) const {return false;}
    bool operator==(const Tuple<T, tailT...>& other) const {
        return (head() == other.head()) && (tail() == other.tail());
    }
    
    template <class... S>
    bool operator!=(const Tuple<S...>& other) const {return !(*this == other);}   

    //+ as in concatenation
    template<typename... T2>
    Tuple<T, tailT..., T2...> operator+(const Tuple<T2...>& other) const {
       Tuple<T, tailT..., T2...> result(*this);
       Tuple<T2...>& tail_ref = result;
       tail_ref = other;
       return result;
    }
    
    T foldl(std::function<T(T, T)> f, const T& initial_value) {
        return Tuple<tailT...>::foldl(f, f(initial_value, _head));
    }
    
    T foldr(std::function<T(T, T)> f, const T& initial_value) {
        return f(_head, Tuple<tailT...>::foldl(f, initial_value));
    }

    T sum() {
        return foldl([&](T x, T y){return x+y;}, 0);
    }

    T product() {
        return foldl([&](T x, T y){return x*y;}, 1);
    }

    Tuple<T, tailT...>& map_self(std::function<T(T)> f) {
        _head = f(_head);
        Tuple<tailT...>& tail_ref(*this);
        tail_ref.map_self(f);
        return *this;
    }

    Tuple<T, tailT...> map(std::function<T(T)> f) {
        Tuple<T, tailT...> result(*this);
        return result.map_self(f);
    }

  private:
    T _head;
};

template<> 
class Tuple<> {
  public:
    template <typename... tailT2> 
    Tuple(const tailT2&... tail) {}
  
    typedef void type;
    template <class... S>
    bool operator==(const Tuple<S...>& other) const {return false;}
    bool operator==(const Tuple<>& other) const {return true;}
    template <class... S>
    bool operator!=(const Tuple<S...>& other) const {return !(*this == other);}
    
    template<typename T2, typename... tailT2>
    Tuple<> operator=(const Tuple<T2, tailT2...>& other) {return Tuple<>();}

    template<typename... T2>
    Tuple<T2...> operator+(const Tuple<T2...>& other) {return other;}
 
    template <class T>
    T foldl(std::function<T(T, T)> f, const T& initial_value) {
        return initial_value;
    }

    template <class T>
    T foldr(std::function<T(T, T)> f, const T& initial_value) {
        return initial_value;
    }
    
    template <class T>
    Tuple<> map(std::function<T(T)> f) {
        return Tuple<>();
    }
    
    template <class T>
    Tuple<>& map_self(std::function<T(T)> f) {
        return *this;
    }

    template <class T>
    T sum() {
        return 0;
    }

    template <class T>
    T product() {
        return 1;
    }
};

//this is only nescessary to satisfy gcc
template<typename... tailT> 
std::ostream& operator<<(std::ostream& out, Tuple<>& tuple) {}

template<typename T, typename... tailT> 
std::ostream& operator<<(std::ostream& out, Tuple<T, tailT...>& tuple) {
    out << "(" << tuple.head() << ", " << tuple.tail() << ")";
}

template<> 
std::ostream& operator<<(std::ostream& out, Tuple<>& tuple) {}


int main() {
    Tuple<int, double, bool> a = {1,2.1,true}; //initializer lists work

    Tuple<int, double, std::string, Tuple<std::string, int> > b = {5, 2.1, "Hello world", {"test",2}}; //yes they can be nested
    
    Tuple<int, double, std::string> c = {2}; //under initialized list
    Tuple<int, double> d = {11, 4, 5}; //over initialized list
    
    c = d; //over initialized assignment
    d = a; //under initilized assignment
    
    Tuple<> empty_tuple;
    
    auto e = empty_tuple + b + c + d + empty_tuple; //+ is an apend operator, auto type deduction works
    
    std::cout << c << std::endl;
    std::cout << d << std::endl;
    std::cout << e << std::endl;

    std::cout << a << std::endl;
    std::cout << a.head() << std::endl; //head
    std::cout << a.tail() << std::endl; //tail

    std::cout << b.get<0>() << std::endl; //elements can be accessed
    std::cout << b.get<1>() << std::endl;
    std::cout << b.get<2>() << std::endl;
    std::cout << b.get<3>() << std::endl;
    
    std::cout << ((a == B)/> ? "True" : "False") << std::endl; //equality comparison
    std::cout << ((a == a) ? "True" : "False") << std::endl;
    std::cout << ((a != B)/> ? "True" : "False") << std::endl;
    std::cout << ((a != a) ? "True" : "False") << std::endl;

    Tuple<double, double, double, double> numbers = {1.0,2.0,3.0,4.0};  
    std::cout << numbers.foldr(std::plus<double>(), 0.) << std::endl;
    std::cout << numbers.foldr(std::multiplies<double>(), 1.) << std::endl;

    std::cout << numbers.foldl(std::plus<double>(), 0.) << std::endl;
    std::cout << numbers.foldl(std::multiplies<double>(), 1.) << std::endl;

    std::cout << numbers.sum() << std::endl;
    std::cout << numbers.product() << std::endl;
    
    auto double_numbers = numbers.map([&](double x){return x*2;});  
    std::cout << double_numbers << std::endl;
}

compiled with g++ -std=c++0x

with g++ 4.6.1

Is that enough template specialization and template recursion for your taste ?


Basically the core of the idea is this.

template<typename T, typename... tailT> 
class Tuple : public Tuple<tailT...> {
  public:
    T head
};

template<> 
class Tuple<> {}

You have a type that takes any number of template parameters and creates a list. Where it inherits from the list that has all elements but the first and keeps a head element. Now head/tail functions are obvious. Mind some things are needlessly complex as I had to work with an incomplete implementation of c++11.

Edit: Added an actual foldl/foldr/sum/product/map, easy enough.

This post has been edited by Karel-Lodewijk: 06 December 2011 - 10:28 AM

[ishkabible]

sepp2k, on 06 December 2011 - 02:04 PM, said:

Is there a particular reason that you chose meta_null as the identity element for summation instead of meta_int<0>? Semantically it seems very strange to me that a binary addition function would even accept the empty list as a valid operand.

Oh, and regarding the rules of the contest: Is it okay if we modify the given template to some degree in our solution? And are C++11 features allowed (specifically I'm thinking about introducing a helper-template that allows easier construction of lists using variadic templates).

1) i didn't really think about actually instead it would be better if i dropped the empty list as a specialization for the add meta function and made the start value of the left fold meta_int<0>. nice catch! i copied the boilerplate from the printer class and i then when i got the error saying that meta_null had no "value" member i just added the specialization to fix it.

2) absolutely. i was hoping someone would bring it up varadic templates make my list representation obsolete. feel free to use them instead.

@karel: i'll have to look at that later

This post has been edited by ishkabible: 06 December 2011 - 01:05 PM

[sepp2k]

Okay, so here's my solution. I implemented the following templates:

• meta_null and meta_pair to represent lists
  
• meta_int_list<int...> to easily create lists of ints
  
• meta_int_range<from, to> to easily create lists of ints in a given range
  
• foldl to perform a left fold on a list
  
• foldr to perform a right fold on a list
  
• map to apply a given transformation to each element of a list (uses foldr)
  
• filter to create a list containing only the elements matching a given predicate (uses foldr)
  
• reverse to reverse a list (uses foldl)
  
• sum to sum all elements of an int list
  
• product to multiply all elements of an int list
  
• meta_for_each to apply a run-time function to each element of a list
  
• print_all to print all elements of a list (uses meta_for_each)

Here's the code:

#include <iostream>

// The empty list
struct meta_null {};

// Type to hold value pairs; these pairs can form lists
template<class Head, class Tail>
struct meta_pair {
    typedef Head head;
    typedef Tail tail;
};


// Left fold

template<template<class, class> class F, class Acc, class List>
struct foldl;

template<template<class, class> class F, class Acc>
struct foldl<F, Acc, meta_null> {
    typedef Acc result;
};

template<template<class, class> class F, class Acc, class Head, class Tail>
struct foldl<F, Acc, meta_pair<Head, Tail> > {
    typedef typename foldl<F, typename F<Acc, Head>::result, Tail>::result result;
};


// Right fold

template<template<class, class> class F, class Acc, class List>
struct foldr;

template<template<class, class> class F, class Acc>
struct foldr<F, Acc, meta_null> {
    typedef Acc result;
};

template<template<class, class> class F, class Acc, class Head, class Tail>
struct foldr<F, Acc, meta_pair<Head, Tail> > {
    typedef typename F<Head, typename foldr<F, Acc, Tail>::result>::result result;
};


// Map

template<template<class> class F>
struct apply_and_cons {
    template<class X, class Acc>
    struct invoke {
        typedef meta_pair<F<X>, Acc> result;
    };
};

template<template<class> class F, class List>
struct map {
    typedef typename foldr<apply_and_cons<F>::template invoke, meta_null, List>::result result;
};


// Helper template to simulate a compile-time if-statement

template<bool cond, class then, class els>
struct meta_if;

template<class then, class els>
struct meta_if<true, then, els> {
    typedef then result;
};


template<class then, class els>
struct meta_if<false, then, els> {
    typedef els result;
};


// Filter

template<template<class> class P>
struct cons_if {
    template<class X, class Acc>
    struct invoke {
        typedef typename meta_if<P<X>::result,
                                 meta_pair<X, Acc>,
                                 Acc>::result result;
    };
};

template<template<class> class P, class List>
struct filter {
    typedef typename foldr<cons_if<P>::template invoke, meta_null, List>::result result;
};


// Template to reverse a list

template<class Acc, class X>
struct cons_reversed {
    typedef meta_pair<X, Acc> result;
};

template<class List>
struct reverse {
    typedef typename foldl<cons_reversed, meta_null, List>::result result;
};


// meta_for_each: Template to call a given function on each element of a list at run-time

template<class Func, class List>
struct meta_for_each;

template<class Func>
struct meta_for_each<Func, meta_null> {
    static void apply(Func f) {}
};

template<class Func, class Head, class Tail>
struct meta_for_each<Func, meta_pair<Head, Tail> > {
    static void apply(Func f) {
        f(Head::value);
        meta_for_each<Func, Tail>::apply(f);
    }
};


// print_all: Prints all elements of a list:
template<class T>
void print(T x) {
    std::cout << x << " ";
}

template<class List, class T>
struct print_all {
    static void apply() {
        meta_for_each<void(*)(T), List>::apply(print<T>);
        std::cout << std::endl;
    }
};

// A simple type that holds a value
template<int x>
struct meta_int {
    static const int value = x;
};


// Helper template to quickly create lists of meta_ints

template<int... xs>
struct meta_int_list;
    
template<>
struct meta_int_list<> {
    typedef meta_null result;
};

template<int h, int... t>
struct meta_int_list<h, t...> {
    typedef meta_pair<meta_int<h>, typename meta_int_list<t...>::result> result;
};


// Helper template to create a list containing a range of integers

template<int from, int to>
struct meta_int_range {
    typedef meta_pair<meta_int<from>, typename meta_int_range<from+1, to>::result> result;
};

template<int from>
struct meta_int_range<from, from> {
    typedef meta_pair<meta_int<from>, meta_null> result;
};


// Templates to add and multiply two integers

template<class X, class Y>
struct add {
    typedef meta_int< X::value + Y::value > result;
};

template<class X, class Y>
struct mult {
    typedef meta_int< X::value * Y::value > result;
};



// Templates to calculate sums and products of lists

template<class List>
struct sum {
    static const int value = foldr<add, meta_int<0>, List>::result::value;
};


template<class List>
struct product {
    static const int value = foldr<mult, meta_int<1>, List>::result::value;
};

// Templates to find whether a meta_int is even or odd
template<class I>
struct even {
    static const bool result = I::value % 2 == 0;
};

template<class I>
struct odd {
    static const bool result = !even<I>::result;
};


// Template to square a meta_int
template<class I>
struct square {
    static const int value = I::value * I::value;
};

int main() {
	typedef typename meta_int_list<1,2,3,4,5>::result test_list;

    print_all<test_list, int>::apply();

    int sum1 = foldl<add, meta_int<0>, test_list>::result::value;
    std::cout << sum1 << std::endl;

    int sum2 = foldr<add, meta_int<0>, test_list>::result::value;
    std::cout << sum2 << std::endl;

    int sum3 = sum<test_list>::value;
    std::cout << sum3 << std::endl;

    int prod = product<test_list>::value;
    std::cout << prod << std::endl;

    typedef typename meta_int_range<1,10>::result one_to_ten;
    print_all<one_to_ten, int>::apply();

    typedef typename filter<even, one_to_ten>::result even_nums;
    print_all<even_nums, int>::apply();

    typedef typename filter<odd, one_to_ten>::result odd_nums;
    print_all<odd_nums, int>::apply();

    typedef typename reverse<one_to_ten>::result ten_to_one;
    print_all<ten_to_one, int>::apply();

    typedef typename map<square, one_to_ten>::result squares;
    print_all<squares, int>::apply();

    return 0;
}

The code requires -std=c++0x because of the usage of variadic templates in meta_int_list. My apologies for the lack of readability.

[ishkabible]

wow! awesome work!! I think I'm going to build off of this when i get home if you don't mind. i want to see if i can implement all of Haskell Data.List functions now

[sepp2k]

ishkabible, on 06 December 2011 - 10:10 PM, said:

wow! awesome work!!

Thanks.

Quote

I think I'm going to build off of this when i get home if you don't mind.

I don't mind.

Quote

i want to see if i can implement all of Haskell Data.List functions now

That would be a very insane ambitious undertaking. There are quite a lot of them.

[Karel-Lodewijk]

This time I made a real implementation of a meta-int list using c++11 variadic template. I did modify the interface a little, looks much nicer.

#include <iostream>
#include <string>
#include <functional>

template <int n, int n2>
struct add {
    const static int value = n + n2;
};

template <int n, int n2>
struct mul {
    const static int value = n * n2;
};

template <int n>
struct mul2 {
    const static int value = n * 2;
};


//g++ fix
template <int... T>
class Meta_int_list;

template<int n, int... tailT> 
class Meta_int_list<n, tailT...> {
  public:
    typedef Meta_int_list<tailT...> tail_type;
    const static int value = n;

    template <template <int, int> class T, int initial_value>
    struct foldr {
        const static int value = T<n, Meta_int_list<tailT...>::template foldr<T, initial_value>::value>::value;
    };

    template <template <int, int> class T, int initial_value>
    struct foldl {
        const static int value = Meta_int_list<tailT...>::template foldl<T, T<n, initial_value>::value>::value;
    };
    
    struct sum {
        const static int value = foldr<add, 0>::value;
    };

    struct product {
        const static int value = foldr<mul, 1>::value;
    };
    
    static std::ostream& print(std::ostream& out) {
        out << "( " << value, ", ";
        tail_type::print(out);
        return out << ")";
    }
    
    template <template <int> class T>
    struct map {
        typedef Meta_int_list<T<n>::value, T<tailT>::value...> type;
    };
    
};

template<> 
class Meta_int_list<> {
  public:
    typedef void tail_type;
  
    template <template <int, int> class T, int initial_value>
    struct foldr {
        static const int value = initial_value;
    };

    template <template <int, int> class T, int initial_value>
    struct foldl {
        static const int value = initial_value;
    };

    struct sum {
        const static int value = 0;
    };

    struct product {
        const static int value = 1;
    };
    
    template <template <int> class T>
    struct map {
        typedef Meta_int_list<> type;
    };
    
    static std::ostream& print(std::ostream& out) {return out;}
};

int main() {
    std::cout << "2+3 = " << add<2,3>::value << std::endl;
    std::cout << "2*3 = " <<mul<2,3>::value << std::endl;
    std::cout << "2*5 = " << mul2<5>::value << std::endl;
    
    typedef Meta_int_list<1,2,3,4> my_list;
    
    my_list::print(std::cout);
    std::cout << std::endl;
    std::cout << "sum: " << my_list::sum::value << std::endl;
    std::cout << "product: " << my_list::product::value << std::endl;
    
    std::cout << "foldr (sum): " << my_list::foldr<add, 0>::value << std::endl;
    std::cout << "foldl (product): " << my_list::foldl<mul, 1>::value << std::endl;
    
    typedef my_list::map<mul2>::type double_list;
    std::cout << "map (double): ";
    double_list::print(std::cout);
    std::cout << std::endl;    
}

compiled with

g++ -std=c++0x

with g++ 4.6.1


It implements foldl/foldr/sum/product/map

This post has been edited by Karel-Lodewijk: 06 December 2011 - 02:43 PM

[ishkabible]

@Karel-Lodewijk: nice, you added an OO twist to it; i like that very clean

@sepp2k: after looking at your implementation of foldl, i decided mine was wrong. sure mine functioned and all but it had some really weird quirks that i just attributed to the nature of TMP. i updated my example code to fit the correct solution