Repository files navigation

Enjoy template metaprogramming

This is not an official Boost library. It might be proposed as a successorfor the current Boost.MPL in the future, but there is no guarantee. Also, Iam currently working onBoost.Hana, a library which tries tomerge MPL11 and Boost.Fusion into a single library. If that works out, itwould probably replace the MPL11.

The library is unstable at the moment; do not use for production.

This was initially supposed to be a simple C++11 reimplementation of theBoost.MPL. However, for reasons documented in therationales,the library was redesigned and the name does not fit so well anymore.

• Installation
• Introduction
• Metafunctions
  • Boxed types
  • Laziness
  • Lifted metafunctions
• Datatypes and data constructors
  • Boxed data constructors
  • Laziness in data constructors
  • Conversions
• Methods
• Typeclasses
• Rewrite rules
• Acknowledgements
• Rationales
• Todo list

The MPL11 is a header only library. To use it in your own project, just add theinclude directory to your compiler's header search path and you aredone.

The library has no dependencies - not even the standard library. However,it requires a C++14-able compiler. The test suite passes under the followingcompilers:

• clang version 3.4
• clang version 3.5.0
• GCC 4.9.0 20140302 (experimental)
• Apple LLVM version 5.1 (clang-503.0.38)

To compile the unit tests, you will also needCMake. Once you have it, youcan go to the root of the project and do:

$ mkdir build$cd build$ cmake ..$ make tests# Compiles the unit tests.

A minified version of the library is also provided. To use it, simply includetheboost/mpl11.min.hpp header, which contains the whole library. Note thatthe minified header must not be used in conjunction with other headers fromthe library.

The MPL11 is a C++11 library providing composable, high-level primitives forsolving complextemplate metaprogramming problems. The library isbuilt around a few core concepts; the aim of this tutorial is to present them,while the handful of tools provided by the library are left to thereference documentation.

This tutorial assumes a good understanding of template metaprogramming andbasic functional programming concepts. Also, a good understanding of theBoost.MPL library will be helpful. However, the MPL11 diverges from theBoost.MPL in many ways, and one should be careful not to transfer knowledgebetween both libraries without checking the documentation.

Informally, a metafunction is a template representing a compile-time functiontaking types as arguments and returning a type as a result. Readers comingfrom the MPL should be careful here, since the formal definition differsfrom that of the MPL.

Formally, letf be a C++ template with an arbitrary number of typetemplate parameters, and type template parameters only. Then,f is ametafunction if and only if there exists typesx1, ..., xn suchthatf<x1, ..., xn>::type is a valid type name. In this context,

• x1, ..., xn are thearguments off.
• Forming a specializationf<x1, ..., xn> is calledsuspendingfwithx1, ..., xn.
• A specializationf<x1, ..., xn> is called athunk or asuspension.
• The nested::type of a thunk is called theresult of the thunk. If thethunk is of the formf<x1, ..., xn>, we can also say it is theresultoff withx1, ..., xn.
• Fetching the result of a thunk is calledevaluating the thunk. If thethunk is of the formf<x1, ..., xn>, we can also sayinvokingfwithx1, ..., xn orapplyingf tox1, ..., xn.
• Thearity of a metafunction is the number of arguments it can beinvoked with. A metafunction with arityn is said to be an-arymetafunction.
• A metafunction that can be invoked with any number of arguments is saidto bevariadic. By definition, a variadic metafunction is n-ary forany non-negative integer n.

It is important to note the difference between this definition and the onegiven by the Boost.MPL. With this definition, a metafunction can never be anormal C++ type; it must always be a template. Hence, Boost.MPL nullarymetafunctions implemented as non-template classes are not considered asmetafunctions. Here are some examples:

// A unary metafunction.template<typename x>structunary {structtype; };// A binary metafunction.template<typename x,typename y>structbinary {structtype; };// A variadic metafunction.template<typename ...>structvariadic {structtype; };// A nullary metafunction. It can only be invoked with// 0 arguments, and it is therefore 0-ary (nullary).template<typename ...>structnullary;template<>structnullary<> {structtype; };// Not a metafunction with the MPL11; it is not a template!structMPL_nullary {structtype; };// Not a metafunction; it never has a result (a nested ::type)!template<typename ...>structno_result { };

Informally, a boxed type is a type that has yet to be evaluated. Hence,before knowing the actual "value" of a boxed type, one must evaluate it,a process which is called unboxing.

Formally, for an arbitrary C++ typeT, aboxedT is an arbitrary C++typeB such thatB::type isT. In this context,B is called abox(ofT) and fetching the nested::type inside ofB is calledunboxingT.

structT;structB {using type = T; };// a boxed T (equivalently, a box of T)B::type;// unboxing T

Conversely, wrapping an arbitrary typeT in a typeB such thatB::typeisT is calledboxingT (intoB or withB). It is important tonote thatB may depend onT, without which boxing would be of limitedinterest.

structT;template<typename t>structB {using type = t; };B<T>;// boxing T into B

Note that types may be boxed an arbitrary number of times. This is probablynot useful, but the definition is general enough to allow it.

B<B<T>>;// this is a "box of B<T>", aka a "box of (box of T)"

There exists a special boxed type namedundefined (sometimes calledbottom) which has the characteristic of causing a compile-time errorwhen it is unboxed, even in SFINAE-able contexts.undefined can beseen as an invalid value, or the result of a computation that failed.

Here are some examples to illustrate the previous definition:

// This template takes an arbitrary type T and boxes it.template<typename T>structbox {using type = T;};// These are not boxed.classx;structy {char foo; };char;box<char>::type;// These are boxed types.box<char>;// a boxed `char`box<box<char>>;// a boxed `box<char>`box<box<char>>::type;// a boxed `char`structx {using type =char; };// a boxed `char`structy {structtype; };// a boxed `y::type`structz {using type = z; };// self-referential? why not!

It is important to note that there are many different representations for aboxedT. This makes equivalence between boxed types a bit tricky. Considerthe following:

structT;structB1 {using type = T; };// a boxed TstructB2 {using type = T; };// a boxed T too

Certainly,B1 andB2 are equivalent w.r.t. to the type they box since theyboth box the same typeT. However,B1 andB2 arenot equivalent w.r.t.the C++ type system because they are different types. Now, this is importantbecause it tells us that we can't use pattern matching to define ametafunction taking a boxed type as an argument. Indeed, since therepresentation of a boxed type is not unique, we can't know what formwill have our argument in advance, and therefore we can't pattern match.Consider the following:

// B should be a boxed type.template<typename B>structf;// This should handle boxed chars, but we don't know// what a boxed char may look like!template<>structf<????> {// ...};

Now, we might be tempted to do the following:

// box is the template that we defined earlier. It takes an// arbitrary type and boxes it.template<>structf<box<char>> {// ...};

But then...

template<typename T>structbad {using type = T;};// works, as expectedf<box<char>>::type;// does not work, even though bad<char> is clearly a boxed charf<bad<char>>::type;

Instead, we would have to do something more convoluted like:

template<typename T>structf_impl;template<>structf_impl<char> {using type = ...;};template<typename B>structf    : f_impl<typename B::type>{ };f<box<char>>::type;// worksf<bad<char>>::type;// works too

It is interesting to note that boxed types and thunks share a lot. Infact, a thunk is nothing but a boxed type that was formed bysuspendinga metafunction. Hence, whenever a boxed type is expected, a thunk may beused instead.

This section introduces the notion of laziness in the context of templatemetaprograms and explains how it relates to the previous notions. This isby no means a rigorous treatment of the broader subject of evaluationstrategies, and knowledge of those concepts is expected.

Informally, laziness is a property of a metafunction meaning that themetafunction performs the least amount of work needed to give its result.It requires the metafunction to only evaluate the expressions that areactually needed in its body, and to evaluate them no more than once.

The second point is called memoization and it is handled behind the scenes bythe compiler. While the C++ standard does not require compilers to memoizetemplate instantiations, this is always the case in practice. Consider:

template<typename x>structf {using type = x;};f<int>::type;// instantiate f<int>f<int>::type;// f<int> is already instantiated, nothing is done.

The first point, however, must be handled manually when writing templatemetaprograms.

TODOFinish this section. Specifically, explain the following:

• What is a lazy metafunction (mf classes follow from that)
• The inverse of a lazy metafunction is a strict metafunction (broadly)
• Lazy metafunctions must take boxed types, otherwise they would alwaysevaluate their arguments whether they are needed or not. This isequivalent to call-by-name.
• Strict metafunctions can take unboxed arguments, because they alwaysevaluate their arguments anyways. However, strict metafunctions can stilltake boxed arguments and unbox them unconditionally; this is just a matterof convention.
• Metafunctions take boxed arguments by default in the MPL11.
• Metafunctions are lazy by default (i.e. whenever possible) in the MPL11.
• Strict metafunctions usually still take boxed arguments for consistency.
• Some metafunctions don't follow the convention, and in this case thisbehavior is documented.
• Metafunctions that don't follow the convention do it because it'snecessary or because it's much easier to do such or such when breakingthe convention.
• Why are lazy metafunctions useful?This could use thedrop metafunction of the old introduction.Laziness often leads to increased expressiveness; for example it becomeseasy to define new control structures and infinite data structures.
• Consider keeping the optional section on non-strictness.

At this point, it is probably helpful to clarify that returning from a lazymetafunction is no different than returning from a strict metafunction. Forexample, consider the following lazy metafunction implementing anifstatement:

template<typename Condition,typename Then,typename Else>structif_ {using Branch = std::conditional<Condition::type::value, Then, Else>::type;using type =typename Branch::type;};

Sinceif_ is lazy, its arguments are all boxed types. Here, we unboxBranch and return that instead of returningBranch itself. This way,if_<Condition, Then, Else> is a thunk and we can pass it to other lazymetafunctions as-is:

// A lazy metafunction.template<typename x>structf;using result = f<   if_<Condition, Then, Else>  >::type;

If we had definedif_ as follows

template<typename Condition,typename Then,typename Else>structif_ {using Branch = std::conditional<Condition::type::value, Then, Else>::type;using type = Branch;// Note that we don't unbox Branch here};

thenif_ would return a thunk and we would need to do the following instead:

using result = f<   if_<Condition, Then, Else>::type    >::type;                                              ^^^^^^

Informally, a lifted metafunction is a representation of a metafunction thatallows it to be manipulated as a first class citizen in template metaprograms.Formally, an arbitrary C++ typef is alifted metafunction if and onlyiff::apply is a metafunction. In general, lifted metafunctions inherit theterminology of metafunctions, and the characteristics of a lifted metafunctionfollow from that of its nestedapply metafunction. For example, the arity ofa lifted metafunctionf is that off::apply.

The definition of a lifted metafunction is almost the same as the definitionof a metafunction class in the Boost.MPL. The only difference is thedifference between metafunctions in both libraries.

Here are some examples of lifted metafunctions:

// A unary lifted metafunction.structunary {template<typename x>structapply {structtype; };};// A binary lifted metafunction.structbinary {template<typename x,typename y>structapply {structtype; };};// A variadic lifted metafunction.structvariadic {template<typename ...>structvariadic {structtype; };};// A nullary lifted metafunction.structnullary {template<typename ...>structapply;};template<>structnullary::apply<> {structtype; };// Not a lifted metafunction with the MPL11; its nested apply// is not a metafunction!structMPL_nullary {structapply {structtype; };};// Not a lifted metafunction; its nested apply never has a result!structno_result {template<typename ...>structapply { };};

Any metafunction can be lifted, and the MPL11 defines a template to dojust that.

template<template<typename ...>classf>structlift {template<typename ...xs>structapply        : f<xs...>    { };};

lift is essentially the same asquote in the Boost.MPL. The namelift was preferred because of its relation to alift in categorytheory. For completeness,lift is actually an equivalence of categoriesbetween the category where objects are C++ types and morphisms aretemplates to the category where objects are C++ types and morphismsare structs with a nestedapply template.

At compile-time, a type becomes a value. A legitimate question would then be:what is the type of that value? In the MPL11, datatypes play that role.Closely related are data constructors, which are a way of creating valuesof a given datatype. For example, let's create a simple compile-time list:

// A "tag" representing the datatype.structList;// The list constructor. It represents a value of type List that// contains the provided elements.template<typename ...Elements>structlist {using mpl_datatype = List; };// The cons constructor. It represents a value of type List// with the provided head and tail.template<typename Head,typename Tail>structcons {using mpl_datatype = List; };// The nil constructor. It represents an empty List.structnil {using mpl_datatype = List; };

Data constructors must provide a nested::mpl_datatype alias representingtheir datatype. One can then use thedatatype metafunction to retrieve it:

datatype<nil>::type;// == List

It is also possible to specializedatatype instead of providing anestedmpl_datatype alias. So this definition ofcons is equallyvalid (and the other constructors could be defined analogously):

template<typename Head,typename Tail>structcons;// no nested mpl_datatypenamespaceboost {namespacempl11 {template<typename Head,typename Tail>structdatatype<cons<Head, Tail>> {using type = List;    };}}

Being able to do this is paramount when adapting code over which we don't havethe control, but for simplicity we'll stick with the nestedmpl_datatypewhenever possible. When unspecialized,datatype<T> simply returnsT::mpl_datatype if that expression is a valid type name, andForeignotherwise. Hence,Foreign is the default datatype of everything.

Note thatdatatype is a strict metafunction and that it does not obey theconvention of taking boxed arguments. Breaking the convention is necessaryto allow user-defined specializations.

While it is not mandatory, it is often a good idea to box data constructorssince it makes them usable as-is in lazy metafunctions. Let's rewrite theprevious data constructors that way:

template<typename ...Elements>structlist_impl {using mpl_datatype = List;};template<typename Head,typename Tail>structcons_impl {using mpl_datatype = List;};structnil_impl {using mpl_datatype = List; };template<typename ...Elements>structlist {using type = list_impl<Elements...>;};template<typename Head,typename Tail>structcons {using type = cons_impl<Head, Tail>;};structnil {using type = nil_impl;};

The downside is that we end up with twice the amount of code, half of whichis complete boilerplate. Also, this approach causes twice as many templatesto be instantiated each time we unbox a data constructor, which can hurtcompile-time performance. Fortunately, we can use self-referential boxingto make this better.

template<typename ...Elements>structlist {using type = list;using mpl_datatype = List;};template<typename Head,typename Tail>structcons {using type = cons;using mpl_datatype = List;};structnil {using type = nil;using mpl_datatype = List;};

That way, only one additional line of code is required per data constructorand we only instantiate one template when we unbox it. Indeed,cons<...>::type is justcons<...>, which is already instantiated.

You might wonder why I have even bothered with the inferior solution usingcons_impl and friends in the first place, since the self-referentialsolution is so obvious. This was to highlight the fact that boxed dataconstructors do notneed to be self-referential; it is merely a convenientimplementation trick. This is a subtle difference between the MPL11 and thempllibs library collection, which I wanted to point out.

There is something rather important that we have left undefined when wecreated thelist andcons data constructors: what do their argumentslook like?

template<typename ...Elements>structlist;template<typename Head,typename Tail>structcons;

There are two possible answers here, and both are valid. In the end, this ismainly a design choice. The first option is to require the arguments to benormal (non-boxed) types. We could then use the constructors like so:

using x = list<int,char,float>;using y = cons<int, list<char,float>>;using z = cons<int, cons<char, cons<float, nil>>>;

The second option is to require boxed arguments. We could then use theconstructors like so:

using x = list<box<int>, box<char>, box<float>>;using y = cons<box<int>, list<box<char>, box<float>>>;using z = cons<box<int>, cons<box<char>, cons<box<float>, nil>>>;

Note that we do not need to box the second arguments tocons ourselves,because we have already madelist,cons andnil boxed.

This is clearly less natural than the first solution. Still, for reasonsthat will soon become clearer, the MPL11List constructors use the secondsolution, and so will we for the rest of this tutorial. To reduce thesyntactic noise, we will define aliases that will make our life easier:

template<typename ...Elements>using list_ = list<box<Elements>...>;template<typename Head,typename Tail>using cons_ = cons<box<Head>, box<Tail>>;

Note that we would not need to box the second argument ofcons_ because weexpect it to be aList, and allList constructors are already boxed. Sobox<Tail> is really redundant, but we still do it here for the sake ofclarity.

We will say that a data constructor taking unboxed arguments isstrict,and that a data constructor taking boxed arguments islazy. An interestingobservation is that some (but not all) constructors are also metafunctions.Specifically, boxed constructors taking type template parameters aremetafunctions. Therefore, strict boxed constructors correspond to strictmetafunctions, and lazy boxed constructors correspond to lazy metafunctions!

The MPL11 provides a way to convert values from one datatype to the other. Theusefulness of this is clearest when implementing numeric datatypes, but we'llstick withList because we already have it. Let's suppose we want to convertvalues from aList to anstd::tuple and vice-versa. First, we will need todefine a datatype of whichstd::tuple can be a data constructor.

structStdTuple;namespaceboost {namespacempl11 {template<typename ...T>structdatatype<std::tuple<T...>> {using type = StdTuple;    };}}

We can now considerstd::tuple as a data constructor for theStdTupledatatype. Note that unlike the arguments tolist, the arguments tostd::tuple must be unboxed; this will be important for what follows.The next step is to implement the conversion itself. This is done byspecializing thecast lifted metafunction for the involved datatypes.

namespaceboost {namespacempl11 {template<>structcast</*from*/ List,/*to*/ StdTuple> {template<typename>structapply;template<typename ...Elements>structapply<list<Elements...>> {using type = std::tuple<typename Elements::type...>;        };template<>structapply<nil> {using type = std::tuple<>;        };template<typename Head,typename Tail>structapply<cons<Head, Tail>> {using type =/* omitted for simplicity*/;        };    };template<>structcast</*from*/ StdTuple,/*to*/ List> {template<typename>structapply;template<typename ...Elements>structapply<std::tuple<Elements...>> {using type = list_<Elements...>;        };    };}}

There are a few things to note here. First, it is very important to provide aconversion for all the data constructors of a datatype. If, for instance, wehad forgotten to provideapply<nil>, we could only convert from thelistandcons constructors. Second, we had to unbox the elements of thelistwhen passing them tostd::tuple becausestd::tuple expects unboxed types.Similarly, we had to box the elements of thestd::tuple when passing them tolist. Third, thecast lifted metafunction is strict and it does not followthe convention of taking boxed arguments, which makes it possible to patternmatch data constructors. Here is how we could now convert between the twodatatypes:

using my_list = list_<int,char,float>;using my_tuple = std::tuple<int,char,float>;cast<List, StdTuple>::apply<my_list>::type;// == my_tuplecast<StdTuple, List>::apply<my_tuple>::type;// == my_list

Also note that casting from a datatypeT to itself is a noop, so you don'thave to worry about that trivial case. The library also defines a handycast_to lifted metafunction that reduces the syntactic noise ofcast:

cast_to<StdTuple>::apply<my_list>::type;// == my_tuplecast_to<List>::apply<my_tuple>::type;// == my_list

cast_to simply deduces the datatype to cast from by using that of itsargument and then forwards tocast.cast_to is strict and does nottake boxed arguments.

TODO: Give more details on theForeign datatype.

So far, we have created theList datatype and a couple of constructors tocreate "values" of that type, but we still don't have a way to manipulatethose values in a useful way. Let's define ahead metafunction that willreturn the first element of aList. We will stick to the convention oftaking boxed arguments.

template<typename List>structhead_impl;template<typename Head,typename ...Tail>structhead_impl<list<Head, Tail...>>    : Head{ };template<typename Head,typename Tail>structhead_impl<cons<Head, Tail>>    : Head{ };// head_impl<nil> is not defined since that's an error.template<typename List>structhead    : head_impl<typename List::type>{ };

First, we need to add a level of indirection (head_impl) becauseheadreceives boxed arguments and we need to pattern match the constructors.Second, note thathead is a strict metafunction because its argumentis always evaluated. Third, we inherit fromHead inhead_impl becausetheList constructors are lazy and henceHead is boxed.

It is now possible to see why it was useful to make theList constructorslazy. Consider the following situation:

using refs = list<    std::add_lvalue_reference<int>,    std::add_lvalue_reference<void>>;head<refs>::type;// == int&

Since we can't form a reference tovoid, we will trigger a compile-timeerror if we evaluate thestd::add_lvalue_reference<void> thunk. However,since we only ever use the value of the first element in the list, it wouldbe nice if we could only evaluate that element, right? Makinglist a lazyconstructor makes that possible. If, instead, we had decided to makeliststrict, we would need to write:

using refs = list<    std::add_lvalue_reference<int>::type,    std::add_lvalue_reference<void>::type>;

which does not compile. The same reasoning is valid if the contents of thelist were the results of complicated computations. By making the constructorlazy, we would only need to evaluate those computation whose result isactually used. In the end, the reasons for writing lazy data constructorsare similar to the reasons for writing lazy metafunctions.

Thehead metafunction we have so far is useful, but consider the followingdatatype and lazy boxed constructor:

structVector;template<typename ...Elements>structvector {structtype {using mpl_datatype = Vector;    };};template<typename Head,typename ...Tail>structvector<Head, Tail...> {structtype {using head = Head;using mpl_datatype = Vector;    };};

SinceVector is really some kind ofList, it is only reasonable to expectthat we can invokehead on aVector just like we do on aList. But howwould we go about implementinghead forVector? Assuming we can't modifythe implementation ofVector, the only way we have right now is to usepartial specialization ofhead_impl onVector's constructor.Unfortunately, that constructor isvector<...>::type, notvector<...>.Since we can't partially specialize on a dependent type, we're out of luck.To bypass this limitation, we will refinehead so it uses the datatype ofits argument.

template<typename Datatype>structhead_impl;template<typename List>structhead    : head_impl<typename datatype<typename List::type>::type>::templateapply<typename List::type>{ };

We now considerhead_impl as a lifted metafunction parameterized over thedatatype of its argument. Implementinghead forList andVector is nowa breeze.

template<>structhead_impl<List> {template<typename>structapply;template<typename Head,typename ...Tail>structapply<list<Head, Tail...>>        : Head    { };template<typename Head,typename Tail>structapply<cons<Head, Tail>>        : Head    { };};template<>structhead_impl<Vector> {template<typename v>structapply        : v::head    { };};

It is sometimes useful to exert a finer grained control over templatespecializations than what we currently have. A common idiom is for theprimary template to provide an additional dummy parameter which can beSFINAE'd upon in partial specializations:

template<typename T,typename Enable =void>structtrait;template<typename T>structtrait<T, std::enable_if_t<std::is_trivial<T>::value>> {// ...};

This enables the specialization to depend on an arbitrary compile-time booleanexpression (in fact on the syntactic validity of an arbitrary expression).Note that all partial specializations using the enabler must have mutuallyexclusive conditions or the specialization will be ambiguous; this can betricky at times. A variant of this trick is to use a default type oftrue_instead ofvoid for the dummy template parameter. That makes it possible toleave thestd::enable_if_t part for most use cases:

template<typename T,typename Enable = true_>structtrait;template<typename T>structtrait<T, bool_<std::is_trivial<T>::value>> {// ...};

Note that we usedbool_<...> instead ofstd::is_trivial<T>::type becausethe latter isstd::true_type, which is not necessarily the same astrue_.

Also, we don't use a straightbool for the enabler because partialspecializations cannot have dependent non-type template arguments.

Since this functionality can really be useful, it might be a good idea tosupport it in thehead_impl lifted metafunction. Fortunately, that onlyrequires changing thehead_impl forward declaration to:

template<typename Datatype,typename = true_>structhead_impl;

TODO: Provide a use case where this is useful.

In this section, we went through the process of designing a simple yetpowerful way of dispatching metafunctions. The subset of metafunctionsusing this dispatching technique are calledmethods in the MPL11.

TODO: Tackle binary operators and mixed-datatype dispatch.

Typeclasses come from the observation that some methods are naturally relatedto each other. For example, take thehead,tail andis_empty methods.When implementing any of these three methods, it is probable that the othertwo should also be implemented. Hence, it would be logical to group them insome way; that is the job of typeclasses. However, typeclasses are much morethan mere method bundles. They provide a clean way of specifying and extendingthe interface of a datatype through a process called typeclass instantiation.

Let's make a typeclass out of thehead,tail andis_empty methods.Datatypes supporting all three methods look somewhat likeLists; hencewe will call the typeclassIterable. We start by grouping the*_impllifted metafunctions of the methods together under theIterable banner.In the following code snippets, thetail andis_empty methods will beomitted when illustratinghead suffices.

structIterable {template<typename Datatype,typename = true_>structhead_impl;// ...};template<typename Iter>structhead    : Iterable::head_impl<typename datatype<typename Iter::type>::type>::templateapply<typename Iter::type>{ };// ...

To implement the methods forList, we now have to write:

template<>structIterable::head_impl<List> {template<typename the_list>structapply {// ...    };};

Soon enough, we notice that we can regroup the datatype parametrization onIterable instead of leaving it on each nested lifted metafunction.

template<typename Datatype,typename = true_>structIterable {structhead_impl;// ...};template<typename Iter>structhead    : Iterable<typename datatype<typename Iter::type>::type>::      head_impl::template apply<typename Iter::type>{ };// ...

The next logical step is to prune the superfluous indirection through the*_impl lifted metafunctions and to simply make them metafunctions.

template<typename Datatype,typename = true_>structIterable {template<typename Iter>structhead_impl;// ...};template<typename Iter>structhead    : Iterable<typename datatype<typename Iter::type>::type>::templatehead_impl<typename Iter::type>{ };// ...

Since it might be useful to query whether a datatype supports the operationsofIterable, we would like to have a boolean metafunction that does justthat. Fortunately, we can use theIterable for this task with a smallmodification.

template<typename Datatype,typename = true_>structIterable : false_ {// ...};

By default,Iterable is therefore also a boolean metafunction returningfalse, meaning that arbitrary datatypes don't implement thehead,tailandis_empty metafunctions. In its current form, theIterable template iscalled atypeclass, and metafunctions likehead following thisdispatching pattern through a typeclass are calledtypeclass methods.In order to implementhead and friends, one would now write

template<>structIterable<List> : true_ {template<typename the_list>structhead_impl {// ...    };// ...};static_assert(Iterable<List>{},"List is an Iterable!");

The three methodsIterable contains so far are very basic; for any givendatatype, it is not possible to provide a suitable default implementation.However, there are other metafunctions that can be implemented in terms ofthese three basic blocks. For example, consider thelast metafunction thatreturns the last element of anIterable. A possible implementation would be:

template<typename iter>structlast    : if_<is_empty<tail<iter>>,        head<iter>,        last<tail<iter>>    >{ };

While we could provide this metafunction as-is, some datatypes might be ableto provide a more efficient implementation. Therefore, we would like to makeit a method, but one that can be defaulted to the above.

Note that method dispatching incurs some compile-time overhead; hence thereis a tradeoff between using (typeclass) methods and regular metafunctions.The rule of thumb is that if a method is likely to never be specialized(i.e. the default implementation is almost always the best), then it shouldprobably be a regular metafunction.

It turns out that providing a default implementation can be done easily usingtypeclasses and a little convention. First, we makelast a normal typeclassmethod.

template<typename Iter>structlast    : Iterable<typename datatype<typename Iter::type>::type>::templatelast_impl<typename Iter::type>{ };

Then, we require specializations ofIterable to inherit some special typeas follows:

template<>structIterable<List> : instantiate<Iterable>::with<List> {// ...};

Here,instantiate<...>::with<...> istrue_ by default. Hence, it onlytakes care of makingIterable a true-valued boolean metafunction, which wedid by ourselves previously. However,instantiate may be specialized bytypeclass designers in such a way that the member templatewith alsocontains default methods. In our case, we would provide alast_implmetafunction corresponding to the default implementation oflast shownabove. This way, if a datatype does not implement thelast method, ourdefault implementation will be used.

namespaceboost {namespacempl11 {template<>structinstantiate<Iterable> {template<typename Datatype>structwith : true_ {template<typename Iter>structlast_impl {// default implementation            };        };    };}}

This technique provides a lot more flexibility. One notable improvement is theability to add new methods toIterable without breaking existing client code,provided the new methods have a default implementation. Hence, in the MPL11,all typeclass specializations are required to use this technique, regardlessof whether they actually need defaulted methods.

You might wonder why we useinstantiate<Typeclass>::with<Datatypes...>instead of just usinginstantiate<Typeclass>. This is because sometypeclasses need to know the datatype(s) they operate on to providemeaningful defaults. Also, we don't useinstantiate<Typeclass, Datatypes...>because that would make defaulted typeclass parameters hard to handle.

A typeclass specialization using the technique we just saw is called atypeclass instantiation. When a typeclass instantiation exists fora typeclassT and a datatypeD, we say thatD is aninstance ofT. Equivalently, we say thatDinstantiatesT, or sometimes thatDis aT. The set of definitions thatmust be provided for atypeclass to be complete is called theminimal complete definition ofthe typeclass. The minimal complete definition is typically the set of methodswithout a default implementation, but it must be documented for each typeclass.

The termtypeclass instantiation is borrowed from Haskell and should not bemistaken withtemplate instantiation even though they share similarities,especially in the MPL11.

TODO

• Tackle mixed-datatype typeclass-method dispatch

TODO

The development of this library drew inspiration from a couple of projects withdifferent levels of involvement in template metaprogramming. I would like tothank the people involved in these projects for their work, without which thislibrary wouldn't be the same. The most notable sources of inspiration andenlightenment were:

• TheHaskell programming language
• The originalBoost.MPL
• Thempllibs library

This section contains rationales for some design decisions of the library. Inits early development, the library was rewritten several times becausefundamental aspects of it needed to be changed. Hence, only the rationalespertaining to the current design are kept here. If you have a question abouta design decision that is not explained here, please contact the creator ofthe library (Louis Dionne).

The following points led to their removal:

• Lazy views were hard to implement because they required creating newiterators, which is a pain. Using a different abstraction for sequencesmade it much easier.
• Iterators being hard to implement and non-composable is a known problem,which is addressed e.g. by the Boost.Range library or in thispaper by Andrei Alexandrescu.
• There is no performance gain to be achieved by using iterators. In fact, itoften makes straightforward implementations more complicated, which can hidepossible optimizations.
• Implementing infinite ranges using iterators is hacky at best.

There are two main reasons for this. First, ifapply were a method, one wouldneed to make every lifted metafunction an instance of the typeclass definingapply. Since lifted metafunctions are very common, that would be verycumbersome. Second, makingapply a method requires using the usual methoddispatching mechanism, which adds some overhead.

In some previous design of the library, these were methods. However, allowingand_ andor_ to be non-strict required special casing these methods. SinceI could not find any use case, I decided to make them normal metafunctions.

Switching the evaluation burden from the caller to the callee makes this uselessin most cases.

It introduces a special case in the definition of metafunction that prevents usfrom usingf::apply<> to invoke a nullary lifted metafunction. We have to useapply<f>, which will then use eitherf::apply<> orf::apply. This adds atemplate instantiation and an overload resolution to each lifted metafunctioninvocation, which significantly slows down compilation. Considering nullarymetafunctions are of limited use anyway (why would you want a function withoutarguments in a purely functional setting?), this is not worth the trouble. Also,note that MPL-style nullary non-template metafunctions fit in the definition ofa boxed type, so they're not completely forgotten.

• What should we do for default typeclass methods?1. We reuse the "official" method and we rebox the arguments.cpp template <typename x, typename y> using equal_impl = not_<not_equal<box<x>, box<y>>>;

  2. We create an "official" unboxed method and we use that.  ```cpp  template <typename x, typename y>  using equal_impl = not_<not_equal_<x, y>>;  ```  where `not_equal_` is a non-boxed version of `not_equal`.3. We directly forward to the implementation of the method in the   typeclass.  ```cpp  template <typename x, typename y>  using equal_impl = not_<Comparable<Left, Right>::not_equal_impl<x, y>>;  ```

• Implement cross-type typeclasses.

• Implement associative data structures.

• Implement a small DSL to implement inline lifted metafunctions (likeBoost.MPL's lambda). Consider let expressions. Using the Boost.MPL lingo,such a DSL should:- Allow leaving placeholders as-is inside a lambda, if this is desirable.- Allow performing placeholder substitution in a lambda without actuallyevaluating the expression, if this is desirable.- Allow "variadic placeholders", i.e. placeholders expanding to severaltypes. One pitfall of this is using such a placeholder with ametafunction that is not variadic:

    ```cpp  template <typename, typename>  struct f;  using F = lambda<f<_args>>; // error here, f is not unary  using Result = F::apply<int, char>::type;  ```This fails because `f` requires 2 arguments.

• Consider allowing types to be printed somehow. The idea is to havesomething like aShow typeclass that allows types to be pretty-printedfor debugging purposes.

• Think about a convention or a system to customize some metafunction calls.Something neat would be to have a way of passing a custom predicate whencomparing sequences; that would makeequal as powerful as theequalalgorithm from the Boost.MPL. Maybe we can achieve the same effect inanother way.

• Consider having a wrapper that allows treating template specializationsas data. Something like sequence operations on template specializationsand/or tree operations.

• Consider addingwhile_ anduntil metafunctions.

• Consider ditchingForeign and making the default datatype the dataconstructor itself.

• Consider addingEither.

• Right now, we must includeboost/mpl11/core.hpp to get theinstantiate<> template in client code. Maybe typeclass headersshould take care of it. Or maybeboost/mpl11/core.hpp shouldnever have to be included by clients altogether?

• Add interoperability with the Boost.MPL, Boost.Fusion and componentsin thestd namespace.

• Useconstexpr to perform numeric computations on homogeneous sequencesof integral constants.

• Consider providing data constructors taking unboxed types for convenience.

• Consider makingint_<> a simple boxedint without a value.

• Write a rationale for why we don't have parameterized datatypes.Or is this possible/useful?

• Make bool.hpp lighter. In particular, it should probably not dependon integer.

• Design a StaticConstant concept?

• In the tutorial, when we specialize lifted metafunctions inside theboost::mpl11 namespace, we don't make them boxed. This makes sensebecause they are lifted metafunctions, not boxed lifted metafunctions.What should we do? Should we1. Make the specializations boxed2. Do not take for granted that they are boxed when we use them in thelibrary and box them redundantly, which is correct but suboptimal.3. Explicitly state that nothing may be specialized inside theboost::mpl11 namespace unless specified otherwise. Then,specify what can be specialized on a per-component basis andthen we apply (2) only to the components that might not be boxed.

• Consider having a public data constructor forForeign, which wouldsimply preserve type identity. Also; might consider changing the nameofForeign.

• Consider regrouping the typeclass instantiations of a datatype in thedatatype itself. This was done in a previous version, but it might havesome advantages.

• Consider providing automatic currying for metafunctions.

• By making some std algorithms constexpr and providing a couple ofcontainers with constexpr iterators, would we have constexpr for freealmost everywhere?

• Consider makingbool_ a lifted metafunction that behaves likeif_.

• Provide a better syntax for casting. Considercast<Datatype(expr)>.

• Seriously consider making datatypes lifted metafunctions.

• Consider prototype-based objects?