Table of Contents
Metal is a single header C++11 library designed to make you love template metaprogramming.
There is a myriad of C++ metaprogramming libraries out there so why Metal?
- Portable - compatible with the most popular compilers.
- Blazing fast - browse up to date benchmarks at metaben.ch.
- Trivial Integration - everything you need in a single self-contained header file
metal.hpp. - SFINAE-Friendly - control overload resolution and make the most out of function templates.
Overview
Definitions
Template metaprogramming may be seen as a language of its own right, it shares the usual syntax of C++ templates, but has its own unique semantics. Because constructs assume different meanings in its context it is useful to define a few key concepts.
Value
Values are the objects of metaprogramming.
Requirements
Any type is a Value.
Examples
Counterexamples
See Also
Number
A Number is a compile-time representation of a numerical value.
Requirements
num is a model of Number if and only if num is a specialization of metal::number.
metal::number<n> is guaranteed to be an alias template to std::integral_constant<metal::int_, n>. Examples
Counterexamples
See Also
metal::number, metal::is_number, metal::as_number
Expression
Expressions, also called metafunctions, are mappings over the set of Values.
Requirements
expr is a model of Expression if and only if expr is a class, union or alias template that only expects Values as arguments.
Examples
Counterexamples
Lambda
Lambdas, short for Lambda Expressions, are first-class Expressions. As Values themselves, Lambdas can serve both as argument as well as return value to other Expressions and Lambdas, thus enabling higher-order composition.
Requirements
lbd is a model of Lambda if and only if lbd is a specialization of metal::lambda.
Examples
See Also
metal::lambda, metal::is_lambda, metal::as_lambda
List
A List is a sequence of Values.
Requirements
list is a model of List if and only if list is a specialization of metal::list.
Examples
Counterexamples
See Also
metal::list, metal::is_list, metal::as_list
Pair
Requirements
A Pair is any List whose size is 2.
Examples
Counterexamples
See Also
metal::pair, metal::is_pair, metal::as_pair
Map
A Map is a collection of unique Values, each of which associated with another Value.
Requirements
A Map is a List of Pairs, whose first elements are all distinct, that is
[[k0, v0], ..., [kn, vn]]; ki != kj for all i, j in {0, n} and i != j
Examples
Counterexamples
See Also
metal::map, metal::is_map, metal::as_map
Examples
IS_SAME(X, Y) is just a terser shorthand for static_assert(std::is_same<X, Y>{}, ""). Parsing Raw Literals
If you ever considered augmenting std::tuple, so that instead of the rather clunky std::get<N>()
one could use the more expressive subscript operator [N]
you might have come up with something like this
only to realize the hard way that this is simply not valid C++.
error: non-type template argument is not a constant expression
While the keyword constexpr tells the compiler the value returned by operator [] might be a compile time constant, it imposes no such constraint on its arguments, which may as well be unknown at compile-time. It might seem we are out of luck at this point, but let us not forget that long before C++ had constexpr variables, integral constants strictly known at compile time could be expressed with the help of non-type template parameters.
So how about refactoring operator [] to take an instance of metal::number and relying on template pattern matching to extract its non-type template argument?
That looks promising, but then again metal::number<1>{} is even clunkier than std::get<1>(), we want something more expressive.
A custom literal operator that constructs Numbers out of integer literals could help reducing the verbosity
but how is operator ""_c implemented?
It might be tempting to try something like this
but let us not forget the reason why we got this far down the road to begin with, recall we can't instantiate a template using a non-constexpr variable as argument!
All is not lost however, because we can still parse raw literals, in other words, we are in for some fun!
The Raw Literal Operator Template
Raw literal operator templates in C++ are defined as a nullary constexpr function templated over char...
where cs... are mapped to the exact characters that make up the literal, including the prefixes 0x and 0b
as well as digit separators
The operator ""_c
We start by defining the literal operator _c as a function that forwards the raw literal characters as a List of Numbers to parse_number and returns a default constructed object of whatever type it evaluates to, which is guaranteed to be a Number in this case.
Resolving the Radix
In its turn parse_number strips the prefix, if any, thus resolving the radix, then forwards the remaining characters to parse_digits, which is in charge of translating the raw characters to the numerical values they represent. The radix and digits are then forwarded to assemble_number, which adds up the individual digits according to the radix.
Notice how we are able to use template pattern matching and partial template specializations to extract all relevant information from the tokens.
Parsing Digits
Before translating characters to their corresponding numerical values, we need to get rid of all digit separators that may be in the way. To do that we'll use metal::remove, which takes a List l and a Value val and returns another List that contains every element in l and in the same order, except for those that are the same as val.
The remaining characters can then be individually parsed with the help of metal::transform, which takes a Lambda lbd and a List l and returns another List that contains the Values produced by the invocation of lbd for each element in l.
[lbd(l[0]), lbd(l[1]), ..., lbd(l[n-2]), lbd(l[n-1])]
Notice how characters are translated to their actual numerical representation.
Thus we have
Assembling Numbers
We now turn to assemble_number. It takes a List of digits and adds them up according to the radix, in other words
D0*radix^(n-1) + D1*radix^(n-2) + ... + D{n-2}*radix + D{n-1}
which can also be written recursively
((...((0*radix + D0)*radix + D1)*...)*radix + D{n-2})*radix + D{n-1}
This is the equivalent of left folding a List, or, in Metal parlance, metal::accumulate, after its run-time counterpart in the standard library.
Here we introduced a new Expression expr from which we created a Lambda, but we could also have chosen to use bind expressions instead.
std::bind returns anonymous functions, and that metal::_1 and metal::_2 are the equivalents of std::placeholders. Finally
Fun With operator ""_c
It also works for very long binary literals.
And ignores digit separators too.
Church Booleans
Church Booleans refer to a mathematical framework used to express logical operation in the context of lambda notation, where they have an important theoretical significance. Of less practical importance in C++, even in the context of template metaprogramming, they will nevertheless help us acquaint with bind expressions in this toy example.
The boolean constants true_ and false_ are, by definition, Lambdas that return respectively the first and second argument with which they are invoked.
Now, using the fact that booleans are themselves Lambdas, it's not too hard to realize that invoking a boolean with arguments <false_, true_> always yields its negation.
However, to enable higher-order composition we really need not_ to be a Lambda, not an Expression. Granted one could easily define former in terms of the latter as metal::lambda<not_>, but that would defeat the whole purpose of this exercise, the idea is to use bind expressions directly.
Admittedly a little more verbose, but that saves us from introducing a new named alias template.
Using a similar technique, we can also define operators and_ and or_.
This exercise might me mind-boggling at first, but you'll get used to it soon enough.
Without further ado we present the logical operator xor.
Notice how we bind not_, which is only possible due to the fact it is a Lambda.
Automatic Test Cases Generation
Suppose you have a component you want to test, say an algorithm on sequences. Because it's a generic algorithm, it's able to work with any kind of containers and, as such, is specialized for different categories of iterators so that it always delivers optimal performance. Moreover, to provide exception safety guarantees without compromising on execution time or memory consumption, it must also specialize on noexcept properties of the elements, particularly of their move constructors. Finally, it's conceivable that such a generic algorithm could also take advantage of other properties, such as whether elements can be ordered or not.
As such a complex implementation, it ought to be thoroughly tested for all relevant combinations of iterator categories and interesting properties implemented by the contained elements. Furthermore, it's crucial that all corner cases are covered, such as empty sequences to name the most obvious, so, before we even start to get fancy with our test cases, we already have three dimensions that vary independently, namely
- Iterator category;
- Element properties;
- Size of the sequence.
How can we possibly implement this testing suite?
First of all, it's a good idea to subdivide each test case into three steps: the set-up phase constructs the particular sequence to be tested, the execution phase runs our algorithm and the tear-down phase releases the resources. This way we can leverage on RAII and reduce the boilerplate to a minimum.
That's a good start, but in order to run all test cases we still have to manually instantiate each and every combination of iterator categories, element type and sequence size. That is, if we want to test for M different categories of iterators, N sets of interesting properties that could be provided by elements and O different sizes of containers, we end up with M*N*O distinct instantiations to maintain! That's too troublesome and prone to error, there ought to be a way to generate all test cases automatically.
Fortunately Metal can do just that for us. With the help of metal::cartesian, we can generate every test case automatically, which we can then run by instantiating a single driver class. It's actually very simple.
And that was it.
To verify that we are in fact generating all possible combinations of test cases under the hood, let's inspect the return type of generate_test_cases
A Word on SFINAE-Friendliness
An Expression is said to be SFINAE-friendly when it is carefully designed so as never to prevent the SFINAE rule to be triggered. In general, such Expressions may only trigger template substitution errors at the point of declaration of a type, which includes the instantiation of alias templates, default template arguments and the signature of function templates. SFINAE-friendly Expressions are exceedingly powerful, because they may be used to drive overload resolution, think std::enable_if on steroids. For this reason, all Expressions in Metal are guaranteed to be strictly SFINAE-friendly.
Conversely, a SFINAE-unfriendly Expression produces so called hard errors, which require the compilation to halt immediately. Examples of hard errors are failed static_assert'ions or template substitution errors at the point of definition of a class or function template. SFINAE-unfriendly Expressions are very inconvenient, because they force compilation to halt when they are not selected by overload resolution, thereby hindering the usage of the entire overloaded set.
make_array
To illustrate how useful SFINAE-friendliness can be, suppose we need a factory function make_array that takes an arbitrary number of arguments and returns a std::array. Because arrays are homogeneous collections, we need the common type of all its arguments, that is, the type to which every argument can be converted to.
The base case is straightforward.
Now suppose we need an array of tuples
error: no matching function for call to 'make_array'
Even though the common tuple is really just a tuple of common types, std::common_type_t is unable to find it in general. That means we need to overload make_array and handle the array of tuples case.
make_array of tuples
The idea is to define a metafunction that computes the common tuple from a set of tuples and then use it to overload our factory function.
This sounds like a use-case for Boost.Hana, let's try it.
It works as expected for std::tuples
but we get a compilation error as soon as we try to make an array of anything that is not a Boost.Hana Sequence, even though the first overload remains available and would be a perfect match otherwise.
error: static_assert failed "hana::zip_with(f, xs, ys...) requires 'xs' and 'ys...' to be Sequences"
make_array of tuples done right
The reason why Boost.Hana can't help us overload make_array is the fact that it doesn't provide any SFINAE-friendliness guarantees, which essentially means that it cannot be used effectively to control overload resolution. Metal, on the other hand, was carefully designed to never trigger hard errors but rather substitution failures, which makes it able to select candidates from an overloaded set by means of the SFINAE rule.
Let's try the same approach using Metal.
This time it works not only for std::tuple's
but also for numerical values
Again, this only works as expected because of the strict SFINAE-friendliness guarantees provided by Metal.
Quick Start
- Download metal.hpp
# include </path/to/metal.hpp>- Love template metaprogramming
Migrating from Boost.MPL
A quick glance Metal and Boost.MPL might look very similar, but because Metal leverages modern language features that were not available at the time Boost.MPL was developed, they are in fact fundamentally distinct.
Metafunctions
The representation of metafunctions has been completely redesigned in Metal. Instead of expressing them as class templates that define a nested typename type, Metal assumes metafunctions to be templates, usually but not necessarily alias, that evaluate directly to the result type.
That is, instead of something like this
you should simply write this
Notice that traditional lazy metafunctions are still valid Expressions in Metal, but keep in mind that their nested typename type is never implicitly evaluated.
Don't worry, you can still use lazy metafunctions with Metal just fine, you just need to use the adaptor metal::lazy instead of metal::lambda.
Additionally, you can also explicitly evaluate lazy values using metal::eval.
Type Traits
Traditionally, type traits are represented as class templates that define a nested integral constant value. Metal on the other hand defines a type trait as any Expression that returns a Number, but that's not to say you can't use good old type traits with Metal just fine, on the contrary, in a similar fashion to lazy metafunctions, all you have to do is use the trait adaptor metal::trait instead of metal::lambda.
Alternatively, you can also explicitly convert traits to Numbers using metal::as_number.
Metafunction Classes
The concept of Metafunction Class became obsolete with Metal. Instead of defining first-class metafunctions like you would with Boost.MPL
you just have to wrap regular metafunctions using metal::lambda instead
It's that simple.
Frequently Asked Questions
What are some advantages of Metal with respect to Boost.MPL?
The most apparent advantage of Metal with respect to Boost.MPL is the fact Metal Lists and Maps can easily exceed the hundreds and even thousands of elements with little impact to the compiler performance, whereas Boost.MPL Sequences, such as mpl::vector and mpl::map, are hard-limited to at most a couple dozen elements and even then at much longer compilation times and higher memory consumption than Metal. Another obvious improvement in Metal is the much terser syntax made possible by alias templates, which were not available at the time Boost.MPL was developed.
Visit metaben.ch for up to date benchmarks that compare Metal against Boost.MPL and other notable metaprogramming libraries. For a brief discussion about fundamental design differences between Boost.MPL and Metal, refer to Migrating from Boost.MPL.
What are some advantages of Metal with respect to Boost.Hana?
As a tool specifically designed for type level programming, Metal is able to provide stronger guarantees and much faster compilation times than Boost.Hana when used for similar purposes. In fact, Metal guarantees SFINAE-friendliness, whereas Boost.Hana does not. Check out A Word on SFINAE-Friendliness for a real world example of the limitations of Boost.Hana with this respect.
Moreover, since Metal concepts are defined by their type signatures, it is always safe to use template pattern matching on them to partially specialize class templates or overload function templates. In contrast, the types of most Boost.Hana objects are left unspecified.
Why isn't std::integral_constant a Number in general?
Numbers are defined as a specific specialization of std::integral_constants, whose binary representation is fixed to metal::int_, an implementation-defined integral type. This design choice stems from the fact two Values compare equal if and only if they have the same type signature. As Values themselves, Numbers are also subject to this requirement, thus had Numbers been defined as a numerical value plus its binary representation, would two Numbers only compare equal if they had both the same numerical value and the same binary representation. This is unreasonable in the context of metaprogramming, where the binary representation of numerical values is entirely irrelevant.