If you want to understand C++ template metaprogramming (TMP) you have to know functional programming. Seriously. I want you to think of TMP as maximally obfuscated (subset of) Haskell, and I’ll illustrate this point by point. If you don’t know Haskell, don’t worry, I’ll explain the syntax as I go.
The nice thing about single-paradigm languages like Haskell is that they have very simple syntax (think of Lisp that does everything with just a bunch of parentheses). I will start the Haskell-C++TMP mapping with basics, like functions and recursion, but I’ll try to cover a lot more, including higher-order functions, pattern matching, list comprehension (did you know it was expressible in C++?), and more.
Keep in mind that my Haskell examples are runtime functions operating on runtime data whereas their C++ TMP equivalents are compile-time templates operating mostly on types. Operation on types are essential in providing correct and efficient implementations of parametrized classes and functions.
By necessity the examples are simple, but the same mapping may be applied to much more complex templates from the C++ Standard Library and Boost. As a bonus, I’ll also explain the hot new thing, variadic templates.
Functional Approach to Functions
How do you implement useful functions if you don’t have mutable variables, if statements, or loops? To a C++ programmer that might seem like an impossible task. But that’s the reality of C++ compile-time language that forms the basis of TMP. Functional programming to the rescue!
As a warm-up, let’s see how Haskell implements a simple function, the factorial:
fact 0 = 1 fact n = n * fact (n - 1)
The first line states that the factorial of zero is one. The second line defines factorial for a non-zero argument, n (strictly speaking it only works for positive non-zero arguments). It does it using recursion: factorial of n is equal to n times the factorial of n-1. The recursion stops when n is equal to zero, in which case the first definition kicks in. Notice that the definition of the function fact is split into two sub-definitions. So when you call:
fact 4
the first definition is looked up first and, if it doesn’t match the argument (which it doesn’t), the second one comes into play. This is the simplest case of pattern matching: 4 doesn’t match the “pattern” 0, but it matches the pattern n.
Here’s almost exactly the same code expressed in C++ TMP:
template<int n> struct fact { static const int value = n * fact<n - 1>::value; }; template<> struct fact<0> { // specialization for n = 0 static const int value = 1; };
You might notice how the horrible syntax of C++ TMP obscures the simplicity and elegance of this code. But once you are equipped with the C++/Haskell decoder ring, things become a lot clearer.
Let’s analyze this code. Just like in Haskell, there are two definitions of fact, except that their order is inverted. This is because C++ requires template specialization to follow the template’s general definition (or declaration, as we’ll see later). The pattern matching of arguments in C++ does not follow the order of declarations but rather is based on “best match”. If you instantiate the template with argument zero:
cout << "Factorial of 0 = " << fact<0>::value << endl;
the second pattern, fact<0>, is a better fit. Otherwise the first one, <int n>, is used.
Notice also the weird syntax for “function call”
fact<n>::value
and for the “return statement”
static const int value = n * fact<n - 1>::value;
This all makes sense if you look at templates as definitions of parameterized types, which was their initial purpose in C++. In that interpretation, we are defining a struct called fact, parameterized by an integer n, whose sole member is a static const integer called value. Moreover, this template is specialized for the case of n equal zero.
Now I want you to forget about what I just said and put on the glasses which make the C++ code look like the corresponding Haskell code.
Here’s another example–this time of a predicate (a function returning a Boolean):
is_zero 0 = True is_zero x = False
Let’s spice it up a little for C++ and define a predicate on types rather than integers. The following compile-time function returns true only when the type T is a pointer:
template<class T> struct isPtr { static const bool value = false; }; template<class U> struct isPtr<U*> { static const bool value = true; };
This time the actual argument to isPtr is first matched to the more specialized pattern, U* and, if it fails, the general pattern is used.
We can add yet another specialization, which will pattern-match a const pointer:
template<class U> struct
isPtr<U * const> {
static const bool value = true;
};
These types of type predicates may be, for instance, used to select more flexible and efficient implementations of parameterized containers. Think of the differences between a vector of values vs. a vector of pointers.
Lists
The basic data structure in functional languages is the list. Haskell’s lists are introduced using square brackets. For instance, a list of three numbers, 1, 2, 3, looks like:
[1, 2, 3]
List processing in functional languages follows the standard pattern: a list is split into head and tail, an operation is performed on the head, and the tail is processed using recursion. The splitting is done by pattern matching: the Haskell pattern being (head:tail) (to be precise, the colon in parentheses represents the cons operation–the creation of a list by prepending an element to an existing list).
Here’s a simple function, count, that calculates the length of a list:
count [] = 0 count (head:tail) = 1 + count tail
The first pattern, [], matches an empty list; the second a non-empty one. Notice that a function call in Haskell doesn’t use parentheses around arguments, so count tail is interpreted as a call to count with the argument tail.
Before C++0x, TMP was severely crippled by the lack of a list primitive. People used separate definitions for a list of zero, one, two, etc., elements, and even used special macros to define them. This is no longer true in C++0x, thanks to variadic templates and template parameter packs. Here’s our Haskel count translated into C++ TMP:
// Just a declaration template<class... list> struct count; template<> struct count<> { static const int value = 0; }; template<class head, class... tail> struct count<head, tail...> { static const int value = 1 + count<tail...>::value; };
First we have a declaration (not a definition) of the template count that takes a variable number of type parameters (the keyword class or typename introduces a type parameter). They are packed into a template parameter pack, list.
Once this general declaration is visible, specializations may follow in any order. I arranged them to follow the Haskell example. The first one matches the empty list and returns zero. The second one uses the pattern, <head, tail…>. This pattern will match any non-empty list and split it into the head and the (possibly empty) tail.
To “call” a variadic template, you initiate it with an arbitrary number of arguments and retrieve its member, value, e.g.,
int n = count<int, char, long>::value; // returns 3
A few words about variadic templates: A variadic template introduces a template parameter pack using the notation class… pack (or int… ipack, etc…). The only thing you may do with a pack is to expand it and pass to another variadic template. The expansion is done by following the name of the pack with three dots, as in tail…. You’ll see more examples later.
Variadic templates have many applications such as type-safe printf, tuples (objects that store an arbitrary number of differently typed arguments), variants, and many more.
Higher-Order Functions and Closures
The real power of functional programming comes from treating functions as first class citizens. It means that you may pass functions to other functions and return functions from functions. Functions operating on functions are called higher-order functions. Surprisingly, it seems like compile-time C++ has better support for higher-order functions than run-time C++.
Let’s start with a Haskell example. I want to define a function that takes two predicate functions and returns another predicate function that combines the two using logical OR. Here it is in Haskell:
or_combinator f1 f2 = λ x -> (f1 x) || (f2 x)
The or_combinator returns an anonymous function (the famous “lambda”) that takes one argument, x, calls both f1 and f2 with it, and returns the logical OR of the two results. The return value of or_combinator is this freshly constructed function. I can then call this function with an arbitrary argument. For instance, here I’m checking if 2 is either zero or one (guess what, it isn’t!):
(or_combinator is_zero is_one) 2
I put the parentheses around the function and its arguments for readability, although they are not strictly necessary. 2 is the argument to the function returned by or_combinator.
The lambda that’s returned from or_combinator is actually a closure. It “captures” the two arguments, f1 and f2 passed to or_combinator. They may be used long after the call to or_combinator has returned.
It might take some getting used to it before you are comfortable with functions taking functions and returning functions, but it’s much easier to learn this stuff in Haskell than in the obfuscated C++. Indeed, here’s an almost direct translation of this example:
template<template<class> class f1, template<class> class f2> struct or_combinator { template<class T> struct lambda { static const bool value = f1<T>::value || f2<T>::value; }; };
Since in the metalanguage a function is represented by a template, the template or_combinator takes two such templates as arguments. It “calls” these templates using the standard syntax f<T>::value. Actually, the or_combinator doesn’t call these functions. Instead it defines a new template, which I call lambda, that takes the argument T and calls those functions. This template acts like a closure–it captures the two templates that are the arguments to or_combinator.
Here’s how you may use the or_combinator to combine two tests, isPtr and isConst and apply the result to the type const int:
std::cout << "or_combinator<isPtr, isConst>::lambda<const int>::value = " << or_combinator<isPtr, isConst>::lambda<const int>::value << std::endl;
Such logical combinators are essential for predicate composability.
Higher-Order Functions Operating on Lists
Once you combine higher-order functions with lists you have a powerful functional language at your disposal. Higher-order functions operating on lists look very much like algorithms. Let me show you some classic examples. Here’s the function (or algorithm), all, that returns true if and only if all elements of a list satisfy a given predicate.
all pred [] = True all pred (head:tail) = (pred head) && (all pred tail)
By now you should be familiar with all the techniques I used here, like pattern matching or list recursion.
Here’s the same code obfuscated by the C++ syntax:
template<template<class> class predicate, class... list> struct all; template<template<class> class predicate> struct all<predicate> { static const bool value = true; }; template< template<class> class predicate, class head, class... tail> struct all<predicate, head, tail...> { static const bool value = predicate<head>::value && all<predicate, tail...>::value; };
Except for the initial declaration required by C++ there is a one-to-one paradigm match between the two implementations.
Another useful algorithm, a veritable workhorse of functional programming, is “fold right” (together with it’s dual partner, “fold left”). It folds a list while accumulating the results (that’s why in runtime C++ this algorithm is called “accumulate”). Here’s the Haskell implementation:
foldr f init [] = init foldr f init (head:tail) = f head (foldr f init tail)
Function f, which is the first argument to foldr, takes two arguments, the current element of the list and the accumulated value. Its purpose is to process the element and incorporate the result in the accumulator. The new accumulated value is then returned. It is totally up to the client to decide what kind of processing to perform, how it is accumulated, and what kind of value is used. The second argument, init, is the initial value for the accumulator.
Here’s how it works: The result of foldr is generated by acting with f on the head of the list and whatever has been accumulated by processing the tail of the list. The algorithm recurses until the tail is empty, in which case it returns the initial value. At runtime this type of algorithm would make N recursive calls before starting to pop the stack and accumulate the results.
For instance, foldr may be used to sum the elements of a list (so_far is the accumulator, which is initialized to zero):
add_it elem so_far = elem + so_far sum_it lst = foldr add_it 0 lst
The accumulator function is add_it. If, instead, I wanted to calculate the product of all elements, I’d use a function mult_it and the starting value of one. You get the idea.
Here’s the same algorithm in C++ TMP:
template<template<class, int> class, int, class...> struct fold_right; template<template<class, int> class f, int init> struct fold_right<f, init> { static const int value = init; }; template<template<class, int> class f, int init, class head, class...tail> struct fold_right<f, init, head, tail...> { static const int value = f<head, fold_right<f, init, tail...>::value>::value; };
Once you understand the Haskell version, this complex code suddenly becomes transparent (if it doesn’t, try squinting 😉 ).
Lists of Numbers
Let’s now switch to integers for a moment. Haskell defines a function sum that adds all elements of a list:
sum [] = 0 sum (head:tail) = head + (sum tail)
We can do the same in C++ TMP (in five times as many lines of code):
template<int...> struct sum; template<> struct sum<> { static const int value = 0; }; template<int i, int... tail> struct sum<i, tail...> { static const int value = i + sum<tail...>::value; };
List Comprehension
Haskell has one more trick up its sleeve for operating on lists without explicit recursion. It’s called list comprehension. It’s a way of defining new lists based on existing lists. The nomenclature and notation are borrowed from Set Theory, where you often encounter definitions such as: S is a set of elements, where… Let’s look at a simple Haskell example:
[x * x | x <- [3, 4, 5]]
This is a set (list) of elements x * x, where x is from the list [3, 4, 5].
Remember our recursive definition of count? Using list comprehension it’s reduced to a one-liner:
count lst = sum [1 | x <- lst]
Here, we create a list of ones, one for each element of the list. Our result is the sum of those ones. To make this definition more amenable to translation into C++, let’s define an auxiliary function one that, for any argument x, returns 1.
one x = 1
Here’s the modified definition of count:
count lst = sum [one x | x <- lst]
Now we are ready to convert this code to C++ TMP:
template<class T> struct one { static const int value = 1; }; template<class... lst> struct count { static const int value = sum<one<lst>::value...>::value; };
Here our list is stored in a template parameter pack, lst. If we wanted to expand this pack, we’d use the notation lst…, but that’s not what’s happening here. The ellipsis appears after the pattern containing the pack:
one<lst>::value...
Compare this with the equivalent Haskell:
[one x | x <- lst]
In C++, when the ellipsis follows a pattern that contains a pack, it’s not the pack that’s expanded, but the whole pattern is repeated for each element of the pack. Here, if our list were <int, char, void*>, the pattern would be expanded to:
<one<int>::value, one<char>::value, one<void*>::value>
The subsequent call to sum would be made with those arguments.
Notice that a different positioning of the ellipsis would result in a completely different expansion. This pattern:
one<lst...>::value
would result in the call to one with the list of types, which would be an error.
Here’s another example of pattern expansion: a function that counts the number of pointers in a list of types:
template<class... lst> struct
countPtrs {
static const int value = sum<isPtr<lst>::value ...>::value;
};
In this case the pattern is:
isPtr<lst>::value ...
and it expands into a list of Booleans. (I’m taking advantage of the fact that false is zero and true is one, when converted to integers.)
You may find a more complex practical example in the Gregor, Järvi, and Powell paper (see bibliography).
Continuations
List comprehension can be used to define some very useful higher-order functions. One of such functions is map, which takes a list and applies a unary function to each element, resulting in a new list. You might be familiar with the runtime implementation of this algorithm in C++ STL under the name of transform. This is what map looks like in Haskell:
map f lst = [f x | x <- lst]
Here, f is the unary function and lst is the input list. You have to admire the terseness and elegance of this notation.
The first impulse would be to translate it into C++ TMP as:
template<template<class> class f, class... lst> struct
map {
typedef f<lst>... type;
};
This is surprisingly terse too. The problem is that it doesn’t compile. As far as I know there is no way for a template to “return” a variable list of elements. In my opinion, this is a major language design flaw, but that’s just me.
There are several workarounds, none of them too exciting. One is to define a separate entity called a typelist along the lines of:
template struct
typelist<hd, tl...> {
typedef hd head;
typedef typelist<tl...> tail;
};
(As a matter of fact I have implemented typelists and related algorithms both in C++ and D.)
Another approach is to use continuations. Template parameter packs cannot be returned, but they can be passed to variadic templates (after expansion). So how about defining an algorithm like map to take one additional function that would consume the list that is the result of mapping? Such a function is often called a continuation, since it continues the calculation where normally one would return the result. First, let’s do it in Haskell:
map_cont cont f lst = cont [f x | x <- lst]
The function map_cont is just like map except that it takes a continuation, cont, and applies it to the result of mapping. We can test it by defining yet another implementation of count:
count_cont lst = map_cont sum one lst
The continuation here is the function sum that will be applied to the list produced by acting with function one on the list lst. Since this is quite a handful, let me rewrite it in a more familiar notation of runtime C++:
int map_cont(int (*cont)(list), int (*f)(int), list lst) { list tmp; for (auto it = lst.begin(); it != lst.end(); ++it) tmp.push_front(f(*it)); return cont(tmp); }
Now for the same thing in compile-time C++:
template<template<class...> class cont,
template<class> class f,
class... lst> struct
map_cont {
static const int value =
cont<typename f<lst>::type ...>::value;
};
It’s a one-to-one mapping of Haskell code–and it has very little in common with the iterative runtime C++ implementation. Also notice how loose the typing is in the TMP version as compared with the runtime version. The continuation is declared as a variadic template taking types, function f is declared as taking a type, and the list is a variadic list of types. Nothing is said about return types, except for the constraints that f returns a type (because cont consumes a list of types) and cont returns an int. Actually, this last constraint can be relaxed if we turn integers into types–a standard trick (hack?) in TMP:
template<int n> struct
Int {
static const int value = n;
};
Loose typing–or “kinding,” as it is called for types of types–is an essential part of compile-time programming. In fact the popularity of the above trick shows that C++ kinding might be already too strong.
The D Digression
I’m grateful to Andrei Alexandrescu for reviewing this post. Since he objected to the sentence, “I’m disappointed that the D programming language followed the same path as C++ rather than lead the way,” I feel compelled to support my view with at least one example. Consider various implementations of all.
In Haskell, beside the terse and elegant version I showed before:
all pred [] = True all pred (head:tail) = (pred head) && (all pred tail)
there is also a slightly more verbose one:
all pred list = if null list then True else pred (head list) && all pred (tail list)
which translates better into D. The D version (taken from its standard library, Phobos) is not as short as Haskell’s, but follows the same functional paradigm:
template allSatisfy(alias F, T...) { static if (T.length == 1) { alias F!(T[0]) allSatisfy; } else { enum bool allSatisfy = F!(T[0]) && allSatisfy!(F, T[1 .. $]); } }
It definitely beats C++, there’s no doubt about it. There are some oddities about it though. Notice that the type tuple, T… gets the standard list treatment, but the split into the head and tail follows the array/slice notation. The head is T[0] and the tail is an array slice, T[1..$]. Instead of using value for the return value, D uses the “eponymous hack,” as I call it. The template “returns” the value using its own name. It’s a hack because it breaks down if you want to define the equivalent of “local variable” inside a template. For instance, the following code doesn’t compile:
template allSatisfy(alias F, T...) {
static if (T.length == 1)
{
alias F!(T[0]) allSatisfy;
}
else
{
private enum bool tailResult = allSatisfy!(F, T[1..$]);
enum bool allSatisfy = F!(T[0]) && tailResult;
}
}
This breaks one of the fundamental property of any language: decomposability. You want to be able to decompose your calculation into smaller chunks and then combine them together. Of course, you may still use decomposition if you don’t use the eponymous hack and just call your return value value. But that means modifying all the calling sites.
By the way, this is how decomposition works in Haskell:
all2 pred [] = True; all2 pred (head:tail) = (pred head) && tailResult where tailResult = all2 pred tail
Anyway, the important point is that there is no reason to force functional programming paradigm at compile-time. The following hypothetical syntax would be much easier for programmers who are used to imperative programming:
template allSatisfy(alias Pred, T...) { foreach(t; T) if (!Pred!(t)) return false; return true; }
In fact it’s much closer to the parameterized runtime function proposed by Andrei:
bool all(alias pred, Range)(Range r) { foreach (e; r) if (!pred(e)) return false; return true; }
This is why I’m disappointed that the D programming language followed the same path as C++ rather than lead the way.
Conclusions
I have argued that some familiarity with Haskell may be really helpful in understanding and designing templates in C++. You might ask why C++ chose such horrible syntax to do compile-time functional programming. Well, it didn’t. The ability to do compile-time calculations in C++ was discovered rather than built into the language. It was a very fruitful discovery, as the subsequent developments, especially the implementation of the Boost MPL, have shown. However, once the functional paradigm and its weird syntax took root in C++ TMP, it stayed there forever. I’m aware of only one effort to rationalize C++ TMP by Daveed Vandevoorde in Reflective Metaprogramming in C++.
I have tested all code in this blog using the Hugs interpreter for Haskell and the GNU C++ compiler v. 4.4.1 with the special switch -std=c++0x. The names I used in the blog might conflict with the standard definitions. For instance, Hugs defines its own map and foldr.
If you want to learn more about template metaprogramming, I recommend two books:
- Andrei Alexandrescu, Modern C++ Design
- David Abrahams and Aleksey Gurtvoy, C++ Template Metaprogramming
The reference I used for variadic templates was the paper by Douglas Gregor, Jaakko Järvi, and Gary Powell
October 21, 2009 at 5:12 pm
Thanks for the article — I had not previously been aware of the variadic templates in C++0x.
For a look at how to take Haskell-in-C++ to the next level, see FC++, a C++ library by Yannis Smaragdakis and his (now graduated) student Brian McNamara:
http://www.cc.gatech.edu/~yannis/fc++/
Click to access fcpp-jfp.pdf
Includes currying, lazy evaluation, and even polymorphic functions (through lots of template magic). As Yannis says, “It is the first library to fully combine higher-order and polymorphic functions, by neatly exploiting C++ type inference.” It includes implementations of the bulk of the Haskell Standard Prelude, in a Haskell-like style.
Best,
— Emery Berger (www.cs.umass.edu/~emery)
October 21, 2009 at 5:23 pm
“…some familiarity with Haskell may be really helpful in understanding and designing templates in C++”
I agree, however, a little more familiarity than that may result in the desire never to see another line of C++ again, so you have to be careful. 😉
October 21, 2009 at 6:26 pm
smitten 🙂
This is a very good and useful post.
I am unfamiliar with D syntax, so I tried to interpret based on the context.
Would have been more helpful if you could explain the use of kinds more.
And the use of these techniques for some real data. Your sum example is a good one.
So is it also possible to have type classes, and then Monads and Arrows and all those funky Haskell jargon here in C++ land too?
October 21, 2009 at 6:54 pm
Social comments and analytics for this post…
This post was mentioned on Reddit by MrN: C++ TMP indeed is obfuscated functional programming. And like Haskell, it is strict (NO side effects) and has lazy evaluation.
You can do a lot of things with it, though it is always much more effort than in a…
October 22, 2009 at 1:24 am
fuck C++ is ugly 🙂
October 22, 2009 at 3:57 am
On a very related topic, you may be interested in Metagene, a ocaml (functional) to C++ templates converter:
http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/200406-MPOOL
However, playing with this code, we quickly reached programs that requires days (!) to compile with g++ …
October 22, 2009 at 4:37 am
Function application:
(or_combinator is_zero is_one) 2
works ok without the parenthesis:
or_combinator is_zero is_one 2
because of currying.
October 22, 2009 at 9:22 am
There is also Template Haskell if you want to do transformations at compile time. Personally I find ghc compiled code to be fast enough that I don’t resort to this and instead just do things at runtime as you are.
http://www.haskell.org/haskellwiki/Template_Haskell
October 22, 2009 at 1:31 pm
Thanks for the links. What Yannis does is implement Haskell features to do calculations at runtime. My examples are all compile-time.
October 22, 2009 at 2:09 pm
To csoroz: you’re right, the parentheses are not necessary. I made the change in the post to reflect it. Thanks!
October 22, 2009 at 3:28 pm
Thanks, very nice post,
I remembered, that I have understood the template metaprogramming on C++ only after I had learned Lisp.
October 22, 2009 at 4:42 pm
@Bartosz: yes, that’s right, FC++ is at least partially a runtime story, although the type inference is dispatched at compile time.
Template metaprogramming is fun, but also sometimes very useful. I use it for static asserts all the time, and in a few select places, I use it to compute some constants to enable otherwise-impossible code optimizations. The resulting code one gets from judicious use of templates can substantially outperform even well-tuned C code.
October 23, 2009 at 1:18 am
[…] What Does Haskell Have to Do with C++? « Bartosz Milewski’s Programming Caf… a few seconds ago from Twidge […]
October 23, 2009 at 5:05 pm
[…] What Does Haskell Have to Do with C++? If you want to understand C++ template metaprogramming (TMP) you have to know functional programming. Seriously. I want […] […]
October 24, 2009 at 2:23 pm
I have been working in a pseudo haskell to c++ translator (for my thesis). The main purpose is make a framework to write active libraries.
Here are some examples of the generated code:
http://code.google.com/p/phaskell/wiki/index
This wiki is a little old, now the framework enable us to use generatrix, a generatrix is a new concept to generate code in compilation time.
Cheers
Marcelo
October 24, 2009 at 2:57 pm
Great stuff, Marcelo. Now you might want to add variadic templates and list comprehension to your arsenal.
October 26, 2009 at 1:27 pm
[…] is now available; and so are the slides. I pretty much covered the material from my last blog post, but many people (including me) find a video presentation easier to […]
October 26, 2009 at 2:25 pm
Bortosz – excellent article. I never thought I would ever read such a thing. Alignment with the ultra complex C++ template meta programming with haskell. Astonishing. When I was doing C++, the compilers just couldn’t support this style.
Anyways, fantastic article. Thanks for putting this together.
October 28, 2009 at 5:38 pm
Thanks for writing this (though to be honest, the C makes me feel a little nauseous). I’d like to add that in addition to Template Haskell, there is also compile time programming capability within Haskell available purely with in the type inferencing system as demonstrated by the paper Type Level Instant Insanity in the Monad Reader issue 8: http://www.haskell.org/sitewiki/images/d/dd/TMR-Issue8.pdf
Broke my brain when I finally got through it, it did.
April 11, 2010 at 3:59 am
Is your “fold_right” definition restricted int lists? Either way, could you provide a reference application?
You supply such for “count” and “or_combinator”; here’s one for “all” which will be true:
bool b = all<isPtr,int*,float*,bool*>::value;
(I re-formated the code using < and > for angle brackets, BM)
April 11, 2010 at 4:03 am
My angle brackets were swallowed. “all” should be followed by “isPtr,int*,float*,bool*” enclosed in angle brackets. One last try:
template struct isPtr
{ static const bool value = false; };
template struct isPtr
{ static const bool value = true; };
bool b = all::value;
[\code]
April 11, 2010 at 11:22 am
Yes, my fold_right is restricted to int lists. You could write one for longs or chars, but not much more–there are very few value types that can be used to parametrize a template.
As for an example, you could use fold_right to calculate the sum of a list, just like in Haskell. I know, it’s not very exciting.
It’s also easy to rewrite fold_right to work on lists of types, except that I can’t really find any application for it. From the top of my head, you could use it to find the most indirect type from a list of types (e.g., the one that has the most stars in its definition, like
int***
), but that’s stretching it.A good source of examples is the paper by Gregor, Jarvi and Powel I mention at the end of the post. It also describes function templates, which I ignored in my post.
April 11, 2010 at 2:12 pm
Cut and paste is obviously a challenge for me, but the only way I can get something like this:
template<int A, int B> struct Add {
static const int value = A+B;
};
…
int r = fold_right<Add, 0, 1,2,3>::value;
…to work out is if I change the variadic template parameters of fold_right to be of type int instead of class.
Great post btw.
April 11, 2010 at 2:55 pm
Yes, you’re right. For the sum example you need the following definition:
With the definition from the post, you might be able to, for instance, calculate the number of pointers in a list of types.
October 28, 2010 at 11:29 am
[…] What Does Haskell Have To Do With C++? […]
October 30, 2010 at 2:54 am
Wow, I want a static_if in C++ (assuming it doesn’t instantiate the wrong branch at all)!
November 3, 2010 at 4:48 pm
Hi Bartosz,
Nice article! There were many prior papers on parameter packs and variable length template arguments. The one finally accepted by the committee was the least amount of functionality to get the job done for things like bind, tuples, printf etc.
Still like the original templates feature added to C++03, I expect that there will be some creative uses that none of us thought about.
Oh and Doug did the lion share of the work on this.
-Gary-
November 3, 2010 at 4:55 pm
Oh here are the links to the various papers submitted to the C++ committee on Variadic templates.
Click to access n1603.pdf
Click to access n1704.pdf
Click to access n1799.pdf
Click to access n2087.pdf
If you are having trouble sleeping, I highly recommend them!
-Gary-
November 3, 2010 at 5:38 pm
Thanks Gary. I remember your talk about concepts. Despite concepts having been voted out of C++0x, I’m planning on talking about them at NWCPP in November, this time in the context of Haskell type classes.
November 25, 2010 at 6:44 pm
“The nice thing about single-paradigm languages like Haskell is that they have very simple syntax (think of Lisp that does everything with just a bunch of parentheses).”
Lisp is very, very multiparadigm. It’s at least on par with C++ in terms of multiparadigmness. It has builtin support for doing imperative, functional, and object-oriented programming. I’ve seen an implementation of fully parenthesized Prolog embedded into Lisp using the macro system.
I’d say that simplicity of syntax has no direct correlation to multiplicity of paradigm.
November 25, 2010 at 11:56 pm
Dear Bartosz Milewski,
You are too good! This is one hell of “aaha!” kind of article—by just reading the first factorial program comparison of Haskell and C++ templates, a whole new world has dawned upon me.
Thanks!
November 26, 2010 at 3:06 pm
Cory: What I meant was that Haskell (and Lisp) support the functional paradigm natively. It so happens that the functional paradigm (based on Lambda Calculus) is the most universal of all, and can be used to implement other paradigms. You wouldn’t call C an object-oriented language, although it’s possible to implement in it structs with tables of function pointers that simulate classes. And if you have a macro system built into the language, you can even imitate some of the syntax used by other paradigms.
November 26, 2010 at 6:11 pm
[…] What Does Haskell Have to Do with C++? « Bartosz Milewski’s Programming CafeJust enough to totally PWN it. Via the Code Project.Tags: haskell c++ fp templates c++0x Tags: c, c%2B%2B, c0x, childhood, del.icio.us, fp, haskell, memories, perl, photos, templates, unix, urxvt […]
November 27, 2010 at 2:52 am
Excellent, more ways to piss off my profs with functionally inspired code in my C/C++ assignments.
November 28, 2010 at 1:18 pm
[…] What Does Haskell Have to do With C++? […]
January 2, 2011 at 12:25 pm
[…] What Does Haskell Have to Do with C++? October 200935 comments and 2 Likes on WordPress.com 3 […]
January 25, 2011 at 1:46 am
Thanks for this very interesting post!
But as a matter of fact, you can write an imperative version of AllSatisfy to be executed at compile time, at least with the current version of D2.
bool AllSatisfy(alias pred, T…)(T t)
{
foreach (e; t)
if (!pred(e))
return false;
return true;
}
unittest
{
static assert(AllSatisfy!((x){ return x>0; })(1, 2.3, 4.5));
}
I believe this is pretty much different from C++ and really cool!
January 25, 2011 at 11:52 am
[…] template language used for metaprogramming in C++ is a pure functional language (see my blog post, What does Haskell have to do with C++?). If monads are so important in functional programming, they must also pop up in C++ […]
July 11, 2011 at 1:11 pm
[…] Haskell makes C++ template metaprogramming if not easy then at least approachable (see my blog, What Does Haskell Have to Do with C++?). You have to understand that compile-time C++ is a strict functional language operating (mostly) […]
July 21, 2011 at 12:48 pm
From one of your replies:
“It’s also easy to rewrite fold_right to work on lists of types, except that I can’t really find any application for it. From the top of my head, you could use it to find the most indirect type from a list of types (e.g., the one that has the most stars in its definition, like int***), but that’s stretching it.”
I want to find the right primitive type for the proper alignment given a size. ie
aligned_storage_for::type;
(which I suspect, for 20 would be an int, but for 24 might be a double – ie the largest primitive that divides evenly into the given size).
I’m thinking fold could be useful here.
July 21, 2011 at 2:45 pm
grrr. lost the angle brackets. make due with (* and *)
aligned_storage_for(*20*)::type
August 1, 2011 at 12:55 pm
[…] Haskell makes C++ template metaprogramming if not easy then at least approachable (see my blog, What Does Haskell Have to Do with C++?). You have to understand that compile-time C++ is a strict functional language operating (mostly) […]
February 7, 2012 at 11:24 pm
You said “As far as I know there is no way for a template to ‘return’ a variable list of arguments.”
Here’s how you do it:
https://github.com/dennisferron/LikeMagic/blob/master/Include/LikeMagic/Utility/FuncPtrTraits.hpp
See line 65: typedef TypePack(Args…) TPack;
Note, my TypePack is not an implementation of the TypeList hack that you covered; TypePack is an empty struct that takes a variadic number of template args – and does absolutely nothing with them. The key is that the list of types is encoded in the signature of the type itself, regardless of whether it does anything with those types they’re still part of it’s observable type. To turn the returned TypePack typedef’ed type back into a list of types, simply pass “TPack” to any template that takes TypePack(Args…), and template pattern match-up will unwrap the TypePack and reconstitute “Args…”. This allows you to return a variable list of template arguments, store it, forward it, even pass it to function templates by including an instance of a TPack() object as a function argument!
You can do similarly cool things with an IndexPack (simply a list of numbers 0..n stuffed in a template (int…) struct). Using IndexPack and TypePack together you can do cool things like index all the elements of an array of pointers-to-base while static casting them to their real types.
February 8, 2012 at 4:16 pm
@Dennis: How would you implement and use my “map” example? In particular, would you be able to call map on the result of map?; the equivalent of Haskell:
February 14, 2012 at 3:59 am
Brilliant and very instructive! I wonder when I can finally use this… until then I ‘ll just enjoy it 🙂 Thanks!
April 28, 2012 at 3:27 am
[…] had recently read an article which explained how functional programming style can be adopted by using template metaprogramming. […]
July 16, 2012 at 9:32 am
[…] examples. So we need a better way of expressing functional pattern in order to make progress. As I argued previously, knowing Haskell is a great help in designing and understanding more advanced patterns in C++. So […]
August 26, 2012 at 2:52 am
[…] What Does Haskell Have to Do with C++? 这篇 […]
October 4, 2012 at 8:49 pm
[…] path instead of learning C++ , you would learnHaskell or CommonLisp. Haskell would be perfect. (https://bartoszmilewski.com/2009/…)but i took the other one (Common Lisp).(http://letoverlambda.com/).9. Now its time to lose focus on […]
August 3, 2013 at 3:14 am
[…] c++ metaprogramming is closely related to functional programming (for more on that see for instance What Does Haskell Have to Do with C++? by Bartosz Milewski), and experience from that domain gives the right answer: use recurrence. […]
August 28, 2013 at 10:28 am
[…] examples. So we need a better way of expressing functional pattern in order to make progress. As I argued previously, knowing Haskell is a great help in designing and understanding more advanced patterns in C++. So […]
November 5, 2013 at 9:36 am
[…] a better, more complicated example using template meta-programming in C++ (discovered via cpp-next.com). My thought process is that one aspect of functional programming […]
November 17, 2014 at 4:42 pm
Effects on me:
Helped me understand how to map the functional paradigms to C++, and why some of them are not implementable in runtime C++.
Roused my interest in Haskell.
December 7, 2014 at 3:41 pm
[…] here. 6. accumulate – C++ Reference 7. Bartosz Milewski’s Programming Cafe 8. What Does Haskell Have to Do with C++? 9. To be honest, perfect forwarding was added later. 10. C++14 11. Lazy evaluation 12. Range […]
December 30, 2014 at 12:00 pm
Nice article, thank you so much.
February 14, 2019 at 7:07 am
February 14, 2019 at 9:34 am
Yes, it’s progress. Functions are now first class citizens. Now if you could only control side effects and mutation at runtime.
September 6, 2019 at 11:26 am
[…] “Category Theorist” Bartosz Milewski talks about variadic functions and the similarities to pattern matching in functional programming in one of his articles: https://bartoszmilewski.com/2009/10/21/what-does-haskell-have-to-do-with-c/ […]