cplusplus.co.il

Metalists for fun and profit

Posted on: 07/02/2010

My name is Nadav Rotem and I am a guest blogger on this blog. I am here to write about metalists. Not metalists like Metallica or Iron Maiden, but meta-lists. Lists which are “template maiden”.

The First thing I am going to show you is how to create a data structure which is similar to a linked list. Next we are going to define the Push, Pop and Concat operations. After we have those, we will implement the Walsh transform (similar to FFT on integers) on our list. After that, we will use template templates to define generators to create lists. Finally we are going to implement the Map and Reduce operations on our lists. Let’s start.

… .. .

… .. .

First and foremost, let us define the most basic element class imaginable.

template <int val>
struct Int {
 enum {value = val};
};

Now we are going to create the list. Much like linked list, each element in our list will hold the rest of the list or Null. Unlike linked list, our data structure will not hold a pointer to the rest of the list, but the rest of the list itself.

// A struct of two elements. The element that we want to hold, and the rest of the list (tail).
template <typename E, typename T=Nil>
struct Element {
 typedef E element;
 typedef T tail;
};

// Nil much like NULL indicates the end of a list
struct Nil{
 typedef Nil tail;
};

Singly-linked-list.svg

A simple linked list holding ‘3,2,1’ will look like this:

Element<Int<3>, Element<Int<2>, Element<Int<1>, Nil> > >

Each element holds an integer wrapped in the Int class and the rest of the list, which is also of type element.

To ease the creation of lists we can define the Push and Pop operations.
Push is easy to understand. It defines a new typename called ‘element’ which holds a new Element struct with the integer n and the tail of the list.
The second parameter, the Pop is more interesting. A simple Pop would simply return the ‘tail’ part of the element. Easy! However, we would like to implement a pop operation which would pop the first ‘k’ elements, where k is an integer. In here we use partial template specialization. The pop operation is defined with an integer which holds a counter and is defined recursively. It keeps returning the tail of the list until the counter reaches zero. When the counter reaches zero the partial specialization template is recognized and the recursion stops.

// Add a new integer to the list
template <typename E, int n>
struct Push {
 typedef Element<Int<n>, E> element;
};

// Pop the first item, continue to pop 'count-1' more elements
template <typename E, int count=1>
struct Pop {
 typedef typename Pop<typename E::tail, count-1>::element element;
};

// Stop the recursion, perform the last pop.
template <typename E>
struct Pop<E, 0> {
 typedef typename E::tail element;
};

We can use our Push and Pop operations this way:

// Create an empty list
typedef Nil empty;

// Adding numbers to the list
typedef Push<empty, 3>::element list0;
typedef Push<list0, 9>::element list1;
typedef Push<list1, 2>::element list2;

// Pop one element from the list
typedef Pop<list2>::element shorter;

// Pop two elements from the list
typedef Pop<list2, 2>::element shortest;

Next we will create a way to access our list in random access. We will implement the Nth operation. Much like the recursive pop operation, the Nth struct accesses itself in a recursive manner. Notice that in here we define an enum named value, and not a typename named element.

// Fetch the Nth element in the list
template <typename E, int n>
struct Nth {
 enum {next = Nth<typename E::tail, n-1>::value};

 enum {value = next};

};

// Stop the recursion
template <typename E>
struct Nth<E, 0> {

 enum {value = E::element::value};

};

// Once we have the Nth operation defined we can use it as following:
// Accessing the list
std::cout<<"1st:"<<Nth<list2, 0>::value<<std::endl;
std::cout<<"2nd:"<<Nth<list2, 1>::value<<std::endl;

In the exact same way we can also define the Length operation to test the length of the list. The Find operation or any scanning of the list is almost identical. Later on we will see how we can make this operation more general using template templates.

template <typename E>
struct Length {

 enum {next = Length<typename E::tail>::value};

 enum {value = 1 + next};

};

template <>
struct Length<Nil> {

 enum {value = 0};

};

The next operation we are going to implement is the concatenation of two lists. Here, we create a new list and insert each of the elements of the first list in a recursive manner, until we hit the Nil element. The Nil element is specialized and instead of inserting a Nil, to terminate the new list, we insert a copy of the second list.

template <typename E, typename V>
struct Concat {

 typedef Element<typename E::element ,typename Concat< typename E::tail,V>::element> element;

};

template <typename V>
struct Concat<Nil, V> {

 typedef V element;

};

We can implement an almost identical operation to fetch the first ‘k’ elements of a list. We will call this operation TopElement.

// Take the first 'length' elements
template <typename E, int length>
struct TopElement {

 typedef Element<typename E::element , typename TopElement<typename E::tail,length-1>::element> element;

};

// Stop when length is zero
template <typename E>
struct TopElement<E, 0> {

 typedef Nil element;

};

Adding two vectors, where the first element of A is added to the first element of B and stored in the first element of the new list, etc. is easy to implement and is also almost identical to the previous operations. To generalize this operation we define a sign parameter which we multiply with the second list. If we set this parameter to negative one, then we get the effect of subtracting two lists. Note that when the lists are not the same length then we get compile error because the list is only terminated by the partially specialized <Nil,Nil> operations.

template <typename X, typename Y, int sign=1>
struct AddVectors {
 // Addition of the rest of the list
 typedef typename AddVectors<typename X::tail, typename Y::tail>::element tail;
 // Current element in the list
 enum {current = X::element::value + sign * Y::element::value};
 // The entire list (current + tail)
 typedef Element< Int<current>, tail > element;
};

// When reaching the end of the lists, stop.
template <>
struct AddVectors<Nil, Nil> {
 typedef Nil element;
};

The Walsh–Hadamard transform is a generalized class of Fourier transforms. We are going to implement the Fast Walsh-Hadamard transform on our list using the operations which we defined so far. First we are going to split our list/vector into two halves. We name them up and down (see figure). We recursively operate the transform on each of the halves. Next we need to add/subtract the two pieces as shown in the figure. Finally we concat the two lists to create our result. TA-DA! We’ve implemented FFT in compile time over a list of elements.

template <typename E, int depth = Length<E>::value >
struct Walsh {
 // Split the vector into two halves (up, down)
 typedef typename TopElement<E, Length<E>::value/2 >::element up;
 typedef typename Pop<E, Length<E>::value/2 -1 >::element down;

 // Walsh each of the two halves
 typedef typename Walsh<up, depth/2>::element wup;
 typedef typename Walsh<down, depth/2>::element wdown;

 // Create the two chunks of this level by adding the lower levels
 typedef typename AddVectors<wup, wdown>::element fup;
 typedef typename AddVectors<wdown, wup, -1>::element fdown;

 // Join the two pieces
 typedef typename Concat<fup, fdown>::element element;
};

// On the lower level, no need to do anything
template <typename E>
struct Walsh<E, 1> {
 typedef E element;
};

Next, we are going to define generators. Those who know Python are familiar with the ‘xrange’ function which generates an iterator which generates a sequence of integers. Here we are going to implement a simple generator to create a list. This generator is pretty simple and works much like the rest of the operations that we have seen so far.

// Create a sequence recursively
template <int length>
struct XRange {
 typedef typename XRange<length-1>::element tail;
 typedef Element<Int<length>, tail > element;
};

// End the sequence after generating the number zero.
template <>
struct XRange<-1> {
 typedef Nil element;
};

This generator is simple and not very general. What if we wanted to generate numbers which are going down to zero, or a list of numbers which is constant. Would we want to copy and paste this generator and change the second line in it ? Nope. In the spirit of c++ and template programming I am going to make this more interesting by introducing the Generator struct and the Policies it uses. A Generator is an operation which creates a list of numbers. Unlike the XRange generator the Policy it uses to generate the numbers is given as a parameter. The Policy parameter is a template itself. It is a template of two integers. The ‘n’ parameter indicates our index in the list, and the ‘data’ parameter is a helper parameter which the user can use to implement the policy.

template <int length, template <int n, int data> class Policy, int data=0>
struct Generator {
 typedef typename Generator<length-1, Policy, data>::element tail;
 typedef Element< typename Policy<length, data>::element, tail > element;
};
template <template <int n, int data> class Policy, int data>
struct Generator<-1, Policy, data> {
 typedef Nil element;
};

Our XRange operation can easily be implemented as the following RangePolicy. A list of constants can be creates using the ConstPolicy. We can also create strange strange generators like the RangeModuloPolicy which generates a list of ‘n’ numbers each modulo by the ‘data’ parameter. On a side note, we can also implement a StopPolicy to indicate how long we want the generated sequence to be.

template <int n, int data>
struct RangePolicy {
 typedef Int<n> element;
};

template <int n, int data>
struct ConstPolicy {
 typedef Int<data> element;
};

template <int n, int data>
struct RangeModuloPolicy {
 typedef Int<n % data> element;
};

Finally we are going to implement the Map and Reduce operations, both use template templates to generalize them. Map is implemented using Map Policies. Much like generators the policy as access to ‘n’ which is the index and a user defined ‘data’ parameter.

template <typename E, template <int A, int n, int data> class Policy, int data = 0>
struct Map {
 typedef typename Map<typename E::tail, Policy>::element mytail;
 enum {length = Length<E>::value };
 enum {current = Policy<E::element::value, length, data>::value};
 typedef typename Push< mytail, current >::element element;
};

template <template <int A, int n, int data> class Policy, int data>
struct Map<Nil, Policy, data> {
 typedef Nil mytail;
 typedef Nil element;
};

// Set all of the values in the array to 'data'
template <int A, int n, int data>
struct MemSetPolicy {
enum {value = (data)};
};

// Increment each element by one
template <int A, int n, int data>
struct Inc1Policy {
 enum {value = (A+1)};
};

// This increases each element in the range by 1
typedef Map<range, Inc1Policy>::element range_1;

Reduce is defined similarly, Policies operate on two values and return one, thus reducing the number of elements in the set. Using Reduce we can calculate the length of a list, much like before just with fewer lines of code. We can also implement the Sum operation and Min and Max. Reduce Policies define the identity value if we want to preserve the value of the other element. For example, zero is the identity value for Sum.

template <typename E, template <int A, int B> class Policy>
struct Reduce {
 enum {next = Reduce<typename E::tail, Policy>::value};
 enum {local = E::element::value};
 enum {value = Policy<next, local>::value};
};

template <template <int A, int B> class Policy>
struct Reduce<Nil, Policy> {
 enum {value = Policy<0,0>::identity};
};

template <int A, int B>
struct SumPolicy {
 enum {value = A+B};
 enum {identity = 0};
};

template <int A, int B>
struct MaxPolicy {
 enum {value = (A>B) ? A : B};
 enum {identity = -999};
};

template <int A, int B>
struct LengthPolicy {
 enum {value = 1 + A};
 enum {identity = 0};
};

Finally, let’s put it all together.

// Create a range of numbers [0..n]
typedef XRange<10>::element range;

// This increases each element in the range by 1
typedef Map<range, Inc1Policy>::element range_1;

// This increases each element in the range by 77
typedef Map<range, IncDataPolicy, 77>::element range_77;

// Sum the numbers between [0..3).
int v0 = Reduce< XRange<3>::element, SumPolicy>::value;

// The length of the sequence .
int v1 = Reduce< XRange<3>::element, LengthPolicy>::value;

// Create a list of length 10, all elements are 2
Generator<10, ConstPolicy, 2>::element c;

// Create a list of length 15, all elements are [n % 7]
Generator<15, RangeModuloPolicy, 7>::element e;

// Calculating a dot product of two vectors.
Walsh<range0>::element d;

That’s all folks. I hope you liked this use of meta programming. Comment below if you can find other cool uses or tricks with meta-lists. Now go and make Ozzy Osbourne, a true metalist, proud.

Cheers,
Nadav Rotem

Advertisements

9 Responses to "Metalists for fun and profit"

Great post Nadav! This is very similar to Alexandrescu’s Type Lists.

I wonder if anybody could come up with an even crazier use-case for this technique, perhaps something seen in a production code.

Thanks 🙂 Next week we can do the one on PI and SIN.

I think you just proved Greenspun’s tenth rule again http://en.wikipedia.org/wiki/Greenspun%27s_Tenth_Rule
🙂

You could have also called your functions cons, car and cdr…

cept no one really uses lisp in real projects

Very well.
You have proved again that templates are Turing complete.

Anyway some useful idea.
It is better to follow Boost.MPL naming convention
( http://www.boost.org/doc/libs/1_42_0/libs/mpl/doc/index.html )
and to use the written classes instead of writing your own 🙂

E.g. there is boost::mpl::map too
http://www.boost.org/doc/libs/1_42_0/libs/mpl/doc/refmanual/map.html

nadavrot: Greate article, but maybe you could add a mention to [Boost Fusion lists](http://www.boost.org/doc/libs/1_41_0/libs/fusion/doc/html/fusion/container/list.html)? Seems pretty related to whay you present here…

Can you work with Reduce that outputs types other than int? Than you could implement Map using it.

It is perfectly possible to have Reduce result in a type instead of an int (or any other specific type). – This is left as an exercise 🙂

Indeed, if Reduce would result in a type then we could implement Map as a Reduce which executes a metafunction on every member and inserts its ‘output’ into the list which is its result. Very nice point!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: