Bramz' warehouse

When you learn C++, first you learn C++ without templates. Later, you learn how to use templates to write containers and algorithms for different data types, and you think you’ve seen it all. It’s only after that, you learn that the template mechanism in C++ is actually a full blown functional programming language that is executed at compile time. And then you’re in for a bit of fun. So, I’ve had my bit of fun =)

download: meta_quicksort.cpp.

In this C++ “program”, there’s lots of stuff forming the basics of writing programs in this “template metaprogramming language”: data types, operators (both on values and types), higher-order programming, list operations like append and filter, pseudorandom number generator, and of course the quicksort itself. The quicksort takes a list and a binary strict weak ordering predicate (the A is less than B kind of predicate).

The demo shows how to perform this quicksort on both values and types. As you can see, values are actually wrapped in value_type, making values also a kind of type. This helps writing the algorithms, and makes sure we can use inheritance to implement it much easier (I got this from boost::mpl). The values can be sorted using the default predicate less_fun, but for sorting types, we have to use something different. The demo uses the predicate is_base_of, so that A is considered less than B if A is a base class of B.

Why quicksort? Well, Haskell, one of the most famous functional programming languages, always uses quicksort to show off how much better it is compared to C. So, I decided it would be nice to implement the same algorithm with template metaprogramming, just to show the difference.

Here’s what it looks like in Haskell (source: HaskellWiki):

qsort []     = []
qsort (x:xs) = qsort(filter (<x) xs) ++ [x] ++ qsort(filter (>=x) xs)

How does it work? qsort takes a single-linked list as argument. In C, a single-linked list is either a NULL pointer, or a pointer to a pair of a value and a next pointer to the rest of the list. In Haskell, this translates to either an empty list [] or a pair x:xs of a value x and another single-linked list xs. If case of an empty list, the result is also an empty list. Otherwise, xs is split in two parts by complementing filters. The first keeps the elements of xs less than x, the second one keeps the elements greater than or equal to x. Both lists are recursively sorted. Finally both lists are concatenated using the ++ operator, with the single element list [x] in between.

And here’s the same algorithm in template metaprogramming style:

template <typename L, typename BinPred = less_fun> struct quick_sort;

template <typename BinPred>
struct quick_sort<null_type, BinPred>: public null_type {};

template <typename H, typename T, typename BinPred>
struct quick_sort<list_type<H, T>, BinPred>: public
    append 
    < 
        typename quick_sort
        <
            typename filter
            <
                T, 
                bind_2nd_fun<BinPred, H> 
            >::type,
            BinPred
        >::type, 
        list_type
        <
            H, 
            typename quick_sort
            <
                typename filter
                <
                    T, 
                    f_gx_fun<not_fun, bind_2nd_fun<BinPred, H> >
                >::type,
                BinPred
            >::type
        >
    > {};

Obviously, the latter has a horrible syntax. But then, what is to be expected of some construct of which it is only accidentily discovered that it is in fact a full programming language?

For more information on C++ template metaprogramming, see the Boost MPL library and the accompanying book C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond.