This library is built on top of Boost.MPL, thus the reader is expected to be familiar with that library and its concepts. This tutorial introduces the different components of Metamonad using examples. The tutorial refers to things coming from Boost.MPL as mpl::...
and omits the boost::
namespace.
Template metafunctions are one of the basic concepts template metaprograms are built around. To define one, the developer has to write a class or a template class, for example:
template <class A, class B>
struct add : mpl::plus<A, B> {};
The above metafunction adds two values by calling mpl::plus
. When someone reads the code, how can he tell, that add
is a metafunction, not just a simple template class? The fact that add
inherits from mpl::plus
suggests that it is a template metafunction, but it may not be that obvious. At the end of the day, add
is a template class and is represented as such in the program code. Metamonad provides the MPLLIBS_METAFUNCTION
macro that helps readability here:
MPLLIBS_METAFUNCTION(add, (A)(B)) ((mpl::plus<A, B>));
This macro takes the name of the metafunction as its first argument and the list of arguments in brackets as the second argument. This argument list is a sequence data structure coming from Boost.Preprocessor. The macro call has to be followed by the body of the macro in double parentheses.
The use of this macro makes it explicit, that add
is a template metafunction, not just some random template class.
It is useful to be able to look at the result of calling a metafunction. It helps development and is invaluable during debugging. Tools like Metashell and Templight can help doing this. They are based on Clang, thus the compiler evaluating the metaprograms is Clang. Other compilers may evaluate the metaprograms in a different way and produce other results. In this case these tools are less useful.
Metamonad offers the fail_with_type
template function. It can be used to check the result of the above add
function:
int main()
{
fail_with_type< add<mpl::int_<11>, mpl::int_<2>>::type >();
}
Compiling this code generates an error message which contains the result of calling add<mpl::int_<11>, mpl::int_<2>>
.
What happens when someone tries calling a metafunction with less arguments than what it expects? For example:
add<mpl::int_<1>>::type
add
expects two arguments: the two values to add, but the above expression called it with only one argument. Metafunctions implemented using MPLLIBS_METAFUNCTION
support currying, which is a form of partial evaluation. When the number of arguments provided is less than what the metafunction needs, it returns a metafunction class expecting the remaining arguments. The body of the metafunction is evaluated only when all arguments are provided.
Thus the above expression returns a metafunction class expecting one argument and then it adds 1
to that argument. It can be used to increment all items of an mpl::vector
by one:
mpl::transform_view<
mpl::vector_c<int, 10, 12>,
add<mpl::int_<1>>
>
This example passes the partially evaluated add<mpl::int_<1>>
to mpl::transform_view
. When mpl::transform_view
calls this partially evaluated metafunction with the elements of the vector, it adds 1
to them.
Providing no arguments to add
turns it into a metafunction class taking two arguments, for example:
mpl::apply<add<>, mpl::int_<10>, mpl::int_<3>>::type
The above example calls the metafunction class add<>
with two arguments, mpl::int_<10>
and mpl::int_<3>
. The result of this call is mpl::int_<13>
.
add<>
can be used to summarise the elements of a vector:
mpl::fold<
mpl::vector_c<int, 1, 1, 2, 3, 6>,
mpl::int_<0>,
add<>
>
This example folds over the elements of the vector [1, 1, 2, 3, 6]
. The initial state is 0
and the forward operation adds the current element to the state. The result of the above expression is mpl::int_<13>
.
Currying makes it easy to build template metafunction classes from template metafunctions in many cases and can reduce the amount syntactic noise this way.
A call to a metafunction, such as mpl::plus
looks like the following:
mpl::plus<mpl::int_<1>, mpl::int_<2>>
The difference between this syntax and the syntax of function calls in C++ is that this uses angle-brackets. The above expression is an instance of a template class, but for a template metaprogrammer, this is a template metaprogramming expression. These expressions are called angle-bracket expressions. Angle-bracket expressions play a key role in providing the tools Metamonad provides, thus it is important to be able to build and evaluate such expressions. They may not be as simple as the above example, since metafunction calls can be combined in one expression:
mpl::plus<
mpl::minus<mpl::int_<2>, mpl::int_<1>>,
mpl::plus<mpl::int_<1>, mpl::int_<1>>
>
If mpl::plus
and mpl::minus
were normal C++ functions, the above expression would look like the following:
mpl::plus(mpl::minus(2, 1), mpl::plus(1, 1))
The evaluation of such expressions happens the following way: mpl::minus(2, 1)
and mpl::plus(1, 1)
are evaluated in some order and their results are passed to mpl::plus
as arguments.
The evaluation of an angle-bracket expression in template metaprogramming happens in a different way. An angle-bracket expression can be evaluated by accessing its ::type
. For example:
mpl::plus<
mpl::minus<mpl::int_<2>, mpl::int_<1>>,
mpl::plus<mpl::int_<1>, mpl::int_<1>>
>::type
This evaluates the outermost mpl::plus
and passes the sub-expressions
mpl::minus<mpl::int_<2>, mpl::int_<1>>
mpl::plus<mpl::int_<1>, mpl::int_<1>>
to mpl::plus
as arguments. While in C++ it is guaranteed, that all of the arguments of a function are evaluated before the function is called, it is not true for angle-bracket expressions. The template metaprogrammer can enforce the evaluation of a sub-expression by accessing its ::type
, otherwise the sub-expression is passed to the function as it is. To evaluate all the arguments of mpl::plus
before it is called the above example needs to be changed:
mpl::plus<
mpl::minus<mpl::int_<2>, mpl::int_<1>>::type,
mpl::plus<mpl::int_<1>, mpl::int_<1>>::type
>::type
In this case mpl::minus<mpl::int_<2>, mpl::int_<1>>::type
is a typedef
of mpl::int_<1>
and mpl::plus<mpl::int_<1>, mpl::int_<1>>::type
is a typedef
of mpl::int_<2>
. Thus, the outermost mpl::plus
is called with mpl::int_<1>
and mpl::int_<2>
as its arguments. But using ::type
inside an angle-bracket expression changes its meaning. When ::type
is used for a sub-expression, the sub-expression itself is not part of the angle-bracket expression any more - it is replaced by the result of the evaluation.
To be able to pass the sub-expressions to mpl::plus
without accessing their ::type
, mpl::plus
has to accept angle-bracket expressions as arguments.
When a class has a nested type called type
, one can look at it as a metafunction taking no arguments. Such classes are called nullary metafunctions. Template metaprogrammers come across nullary metafunctions more often than they may expect it. For example angle-bracket expressions built of metafunction calls are nullary metafunctions, since they have a nested ::type
type.
Let's start with a simple expression:
mpl::plus<
mpl::int_<11>,
mpl::int_<2>
>::type
This doesn' seem to be a difficult one, it returns mpl::int_<13>
. Now let's make it a bit more complicated:
mpl::plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>::type
The only difference is that instead of using mpl::int_<2>
as the second argument of mpl::plus
, this code uses mpl::if_
with a constant true value as the condition to choose from mpl::int_<2>
and mpl::int_<3>
. Of course mpl::if_
chooses mpl::int_<3>
.
This seems to be fine, even though it isn't. Evaluating this example breaks the compilation. mpl::plus
complains that mpl::if_<mpl::true_, mpl::int_<2>, mpl::int_<3>>
is not a number. This might seem strange, since evaluating it gives mpl::int_<2>
. The key thing here is evaluating it gives mpl::int_<2>
- it is not evaluated yet, it is a nullary metafunction waiting to be evaluated.
If mpl::plus
and mpl::if_
were normal C++ functions and not metafunctions, the expression would look like this:
plus(11, if_(true, 2, 3))
Of course, integer and boolean literals are used instead of the wrapped ones. During the evaluation of such an expression the arguments are evaluated before they are passed to a function, thus if_(true, 2, 3)
is evaluated before it is passed to mpl::plus
. This makes this thing work. However, in template metaprogramming it happens in a different way: the arguments passed to a template metafunction are not evaluated. They are treated as angle-bracket expressions and passed to metafunctions like mpl::plus
as they are. It is the responsibility of mpl::plus
to evaluate them if needed.
mpl::plus
does not evaluate its arguments, it assumes, that they are already evaluated. Template metafunctions evaluating their arguments are called lazy template metafunctions, while metafunctions assuming that their arguments are already evaluated are called strict template metafunctions. When a metafunction is strict - like mpl::plus
- it is the caller's responsibility to evaluate the arguments before passing them to the metafunction. It can be done by passing the ::type
of the argument instead of the argument itself to the metafunction:
mpl::plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>::type
>::type
This code evaluates the second argument of mpl::plus
before the metafunction call happens by passing mpl:if_<...>::type
to mpl::plus
.
How can one ensure, that the metafunction he writes is lazy? For example when someone writes the following metafunction:
MPLLIBS_METAFUNCTION(add2, (N)) ((add<mpl::int_<2>, N>));
Is add2
lazy? Well, it depends on add
. Since add2
passes its argument further to add
, it does not have evaluate it to be lazy. If add
is lazy, it makes add2
lazy, but if add
is strict, add2
will be strict.
The metafunctions Boost.MPL provides are strict. For example, mpl::plus
expects that its arguments are evaluated. However, one can easily write a lazy wrapper for it:
MPLLIBS_METAFUNCTION(lazy_plus, (A)(B))
((mpl::plus<typename A::type, typename B::type>));
This wrapper handles only the case when exactly two arguments are provided, but it is enough to demonstrate how to build a lazy wrapper for a strict metafunction. lazy_plus
is a lazy metafunction, it evaluates its arguments and passes them to the strict metafunction mpl::plus
that does the addition.
When writing such a wrapper, one has to evaluate all of the arguments. Metamonad provides a macro for these cases, it is MPLLIBS_LAZY_METAFUNCTION
. It is similar to MPLLIBS_METAFUNCTION
, however, it evaluates its arguments. It can be used to implement the above example:
MPLLIBS_LAZY_METAFUNCTION(lazy_plus, (A)(B)) ((mpl::plus<A, B>));
A
and B
refer to typename A::type
and typename B::type
in the body of the metafunction, thus it makes it easier to write these lazy wrappers.
Using the arithmetic operations of Boost.MPL through the lazy wrappers, one can evaluate the complex expression
lazy_plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
This code still passes an angle-bracket expression as argument to lazy_plus
, but it evaluates its argument before it does the addition, thus the above code works.
Wrapping all strict metafunctions with lazy wrappers is possible, but it is still a lot of work and produces a large amount of code that needs to be maintained in the future. Metamonad provides a tool, using which there is no need for these lazy wrappers. It is the lazy
template. It wraps an angle-bracket expression and changes the way arguments are passed to the metafunctions. It evaluates the arguments of the metafunctions before calling them. The above example can be implemented using it:
lazy<
mpl::plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>
The original metafunctions coming from Boost.MPL can be used as they were lazy metafunctions because lazy
makes sure that their arguments are evaluated before they are passed to them. lazy
evaluates the above expression the following way:
mpl::plus<
mpl::int_<11>::type,
mpl::if_<
mpl::true_::type,
mpl::int_<2>::type,
mpl::int_<3>::type
>::type
>::type
As mpl::if_<mpl::true_, mpl::int_<2>, mpl::int_<3>>::type
is mpl::int_<2>
, this wrapped number is passed to mpl::plus
.
mpl::if_
chooses either its second or third argument based on the value of the condition. Putting an expression that should not be evaluated, such as divides<mpl::int_<1>, mpl::int_<0>>
should not be a problem, since this expression trying to divide 1
with 0
should not be selected by mpl::if_
:
mpl::plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>
>
However, putting the entire expression into lazy
changes things. It makes sure that all arguments of a metafunction are evaluated before the metafunction is called and since mpl::if_
is a metafunction, it evaluates all of its arguments as well - which includes both cases, not just the selected one. Thus, lazy
evaluates the expression trying to divide 1
by 0
before mpl::if_
would get the chance to choose the other one.
To solve these issues, Metamonad provides the already_lazy
template which can be used inside lazy
to protect some sub-expressions from the enforced argument evaluation.
lazy<
mpl::plus<
mpl::int_<11>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
already_lazy<mpl::divides<mpl::int_<1>, mpl::int_<0>>>
>
>
>::type
lazy
leaves things wrapped with already_lazy
alone. Thus, the above expression evaluates the following:
mpl::plus<
mpl::int_<11>::type,
mpl::if_<
mpl::true_::type,
mpl::int_<2>::type,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>::type
>::type
The arguments that were not wrapped with already_lazy
are evaluated before they are passed to mpl::if
, however, the expression that tries to divide by 0
was wrapped with already_lazy
and is passed unchanged to mpl::if_
.
Let's create a metafunction from the above example and replace mpl::int_<11>
with a metafunction argument:
MPLLIBS_METAFUNCTION(add2, (N))
((
lazy<
mpl::plus<
N,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>
));
This code adds mpl::int_<2>
to its argument. To keep it simple mpl::int_<3>
is used instead of the expression trying to divide by 0
.
Calling this metafunction with mpl::int_<11>
gives the expected result, add2<mpl::int_<11>>::type
is mpl::int_<13>
. However calling it with a complex expression can break the compilation:
add2<
mpl::if_<
mpl::true_,
mpl::int_<11>,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>
>::type
When a call like this is done, the body of add2
is evaluated:
lazy<
mpl::plus<
mpl::if_<
mpl::true_,
mpl::int_<11>,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>::type
Since arguments are not evaluated when they are passed to a metafunction, the angle-bracket expression mpl::if_<...>
is used inside the body of add2
. But it is used inside lazy
and therefore it is evaluated as it was originally written inside lazy
. This is probably not what the caller of add2
expects. In the above example it evaluates the division by zero for example.
To avoid these bad surprises, when using lazy
in the body of a metafunction, the arguments have to be protected. Let's protect the argument with already_lazy
:
MPLLIBS_METAFUNCTION(add2, (N))
((
lazy<
mpl::plus<
already_lazy<N>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>
));
This code protects the argument N
inside the lazy
block with already_lazy
, thus it is left untouched by lazy
. Calling add2
with the same argument as before evaluates the body the following way:
lazy<
mpl::plus<
already_lazy<
mpl::if_<
mpl::true_,
mpl::int_<11>,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>
>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>::type
Because of using lazy
, it evaluates the following expression:
mpl::plus<
mpl::if_<
mpl::true_,
mpl::int_<11>,
mpl::divides<mpl::int_<1>, mpl::int_<0>>
>,
mpl::if_<
mpl::true_::type,
mpl::int_<2>::type,
mpl::int_<3>::type
>::type
>::type
As the argument value was protected with already_lazy
, it is left untouched while the rest of the expression is evaluated at all levels. The two arguments passed to mpl::plus
are two angle-bracket expression, however the first one - which was the argument - is not evaluated while the second one is evaluated. Not evaluating the argument is what we used already_lazy
for, but in this case this angle-bracket expression is given to mpl::plus
which can not deal with it. Using already_lazy
made add2
a strict metafunction.
To make add2
lazy, the argument has to be evaluated before it is passed to mpl::plus
, but it should be evaluated by getting its ::type
and without evaluating any sub-expression of it. Using already_lazy
does not evaluate the argument, but not using it evaluates it by evaluating all the sub-expressions as well. Another tool is needed here, which is lazy_protect_args
. When it is used inside lazy
, the expression wrapped by it is evaluated but without evaluating any of its sub-expressions.
MPLLIBS_METAFUNCTION(add2, (N))
((
lazy<
mpl::plus<
lazy_protect_args<N>,
mpl::if_<
mpl::true_,
mpl::int_<2>,
mpl::int_<3>
>
>
>
));
This version of add2
is lazy, because by using lazy_protect_args
it evaluates the argument N
but without changing the way it would be normally evaluated, thus it won't surprise the caller of add2
.
The lazy
template makes it possible to use strict metafunctions in larger expression, however, as the examples demonstrate, it adds syntactic overhead to the code, thus using (and building) lazy metafunctions keeps the code readable and makes it possible to build complex expressions.
In Boost.MPL compile-time values have a member type called tag
that is used to determine whether that value is a wrapped integral, a list, a vector, etc. There may be more than one implementations of a compile-time data-type, such as wrapped integrals. As long as they provide the same interface and have the same tag
, all metafunctions operating on the wrapped integrals can deal with them. The tag
is used to identify that they are wrapped integrals.
This tag
works like the type information of compile-time data-structures. Polymorphic metafunctions in Boost.MPL get the tag
information of the arguments, instantiate a helper metafunction class with the tags as template parameters and pass the original arguments to that metafunction class. Different specializations of the metafunction class can be created for different tags and tag combinations. Each specialization implements one overload of the metafunction. Since a new specialization can be implemented without changing existing code, new overloads for newly created classes can be implemented later.
Metamonad treats tags as first class citizens of template metaprograms, thus they are expected to be passed around as data in metaprograms. But in that case tags need to have a tag as well. Metamonad provides the tag tag_tag
for that.
Metamonad provides the tmp_tag
to help defining tags:
struct my_tag : tmp_tag<my_tag> {};
The above usage makes use of the Curiously recurring template pattern and provides a ::type
referencing my_tag
and a ::tag
referencing tag_tag
. my_tag::type
is my_tag
and my_tag::tag
is tag_tag
. ::type
is needed to avoid lazy metafunctions crashing when one passes a tag to them.
Let's add two numbers together using lazy_plus
:
lazy_plus<mpl::int_<1>, mpl::int_<1>>
Assuming lazy_plus
is a lazy wrapper around mpl::plus
, the first thing it does is evaluating its arguments, thus taking mpl::int_<1>::type
. But mpl::int_<1>
represents a number, it is not a nullary metafunction. In order to make it work in situations like this one, it has to be a nullary metafunction evaluating to itself. Such classes are called template metaprogramming values.
Metamonad assumes, that every class that is used as a value in template metaprogramming is a nullary metafunction evaluating to itself. Metamonad also assumes, that every metafunction returns a metaprogramming value, thus taking ::type
twice yields the same result as taking it only once. For example mpl::plus<mpl::int_<1>, mpl::int_<1>>::type::type
means the same as mpl::plus<mpl::int_<1>, mpl::int_<1>>::type
.
Metamonad provides the tmp_value
template for supporting the creation of metaprogramming values. This template is expected to be used the following way:
struct some_class : tmp_value<some_class> {};
The above usage makes use of the Curiously recurring template pattern and provides a ::type
referencing some_class
. Now some_class::type
is some_class
.
tmp_value
supports specifying the tag of a class as well. It accepts an optional second argument, which is when provided defines ::tag
referencing that second argument. For example:
struct some_tag : tmp_tag<some_tag> {};
struct some_class : tmp_value<some_class, some_tag> {};
Using the above, some_class::type
is some_class
, some_class::tag
is some_tag
.
One of the basic programming constructs is if
, which chooses from two cases based on a condition. A version of such a construct, that fulfils Metamonad's assumptions about metafunctions is needed. Such an if
should always return a template metaprogramming value.
Boost.MPL provides two if
constructs:
mpl::if_<C, T, F>
returns either T
or F
based on the value of C
. When T
or F
is a nullary metafunction, the nullary metafunction is returned, which may not be a metaprogramming value.mpl::eval_if<C, T, F>
chooses one from T
and F
based on the condition, evaluates it and returns the result. Even when the arguments are nullary metafunctions, mpl::eval_if
returns their result - which must be a metaprogramming value based on Metamonad's assumption.Even though mpl::eval_if
fulfils Metamonad's assumptions - as later sections present it - Metamonad gives a different meaning to the eval_
prefix than what Boost.MPL uses it for. With Metamonad's terminology, the selection function should be called if_
.
Metamonad provides the if_
metafunction that accepts nullary metafunctions as the condition and evaluates the selected argument.
The assumption, that everything template metaprograms operate on is a template metaprogramming value makes building template metaprograms easier, but it also means that common types, such as int
, double
, etc can not be used in template metaprograms. Wrapping things that are available at compile-time but can not be used directly in template metaprograms works well for constant integral values, why wouldn't it work for classes as well? Metamonad provides a wrapper class, box
, that wraps any type and turns it into a metaprogramming value. Boxed types can be safely passed around and unboxed using unbox
at the end.
Angle-bracket expressions can be treated as template metaprogramming code blocks. If they can be passed around in template metaprograms, complex control structures can be implemented. But angle-bracket expressions are not template metaprogramming values - when someone tries accessing their ::type
they get evaluated. They could be boxed as any other type, but the only thing that can be done with a boxed type is unboxing it, while there are more operations for angle-bracket expressions.
Metamonad provides syntax
, a custom wrapper for angle-bracket expressions. An angle-bracket expression wrapped with this template is called a syntax. For example the following syntax can be passed around as a value in template metaprograms:
syntax<
mpl::plus<mpl::int_<9>, mpl::int_<4>>
>
When a lazy metafunction evaluates it, it does not evaluate the wrapped angle-bracket expression:
syntax<
mpl::plus<mpl::int_<9>, mpl::int_<4>>
>::type
returns
syntax<
mpl::plus<mpl::int_<9>, mpl::int_<4>>
>
Such syntaxes make sense only when the wrapped expression can be evaluated when the time has come. Metamonad provides the eval_syntax
metafunction for that.
eval_syntax<
syntax<
mpl::plus<mpl::int_<9>, mpl::int_<4>>
>
>::type
The above expression evaluates to mpl::int_<13>
.
An expression may contain variables. When it does, expressions like
syntax<
mpl::plus<a, b>
>
can be constructed, where a
and b
represent the open variables of the expression. The value of such variables can then be specified later. Metamonad assumes, that instances of the var
template are variables. The var
template class has a template argument, which identifies the variable. Any class that has been declared can be used as an identifier. For example a variable called state
can be created the following way:
struct state;
var<state>
Another option to name variables is to use template metaprogramming strings as the identifier. The BOOST_METAPARSE_STRING
macro of Boost.Metaparse helps creating them. For example:
var<BOOST_METAPARSE_STRING("state")>
Metamonad provides pre-defined variables that can be used without declaring anything. These names are in the mpllibs::metamonad::name
namespace, thus writing
using namespace mpllibs::metamonad::name;
brings only these pre-defined variables in. These variables are called a
, b
, ..., z
. They are easy to use in expressions, for example:
using namespace mpllibs::metamonad::name;
syntax<
mpl::plus<a, b>
>
a
, b
, ... are typedefs
of things wrapped with var
, thus they can be used without having to write var
in the code.
A syntax with variables is not something that could be evaluated.
syntax<
mpl::plus<a, b>
>
Trying to evaluate the above syntax using eval_syntax
would lead to a compilation error, since mpl::plus
would complain, that an integer can not be added to a variable. To make the above expression evaluable, the variables have to be replaced with values. Metamonad provides let
for this substitution. It takes three arguments:
For example
let<
a, syntax<mpl::int_<9>>,
syntax<
mpl::plus<a, b>
>
>::type
Replaces a
with mpl::int_<9>
. It returns the following syntax:
syntax<
mpl::plus<mpl::int_<9>, b>
>
It is still not something that can be evaluated, b
needs to be replaced with a value as well:
let<
b, syntax<mpl::int_<4>>,
syntax<
let<
a, syntax<mpl::int_<9>>,
syntax<
mpl::plus<a, b>
>
>
>
>::type
The outer let
replaces b
with mpl::int_<4>
. But things wrapped with syntax
are treated as values, thus when a syntax contains another thing wrapped with syntax
, let
does not change it. Since the expression mpl::plus<a, b>
is wrapped with syntax
, the outer let
does not change it.
Metamonad provides another version of let
, let_c
to resolve this issue. This is similar to let
, but instead of taking syntaxes, it takes angle-bracket expressions as arguments and wraps them with syntax
internally.
let_c<
b, mpl::int_<4>,
let_c<
a, mpl::int_<9>,
mpl::plus<a, b>
>
>::type
The above code uses let_c
instead of let
. The outer let_c
does the substitution and wraps its result with syntax
, thus it returns
syntax<
let_c<
a, mpl::int_<9>,
mpl::plus<a, mpl::int_<4>>
>
>
To get the fully substituted expression, this syntax needs to be evaluated:
eval_syntax<
syntax<
let_c<
a, mpl::int_<9>,
mpl::plus<a, mpl::int_<4>>
>
>
>
Evaluating the syntax evaluates the inner let_c
of the original expression, which substitutes a
with mpl::int_<9>
and returns
syntax<
mpl::plus<mpl::int_<9>, mpl::int_<4>>
>
Which is the original syntax with both substitutions done. Thus, the working version of this example is the following:
eval_syntax<
let_c<
b, mpl::int_<4>,
let_c<
a, mpl::int_<9>,
mpl::plus<a, b>
>
>
>::type
The outer let_c
substitutes b
and returns a syntax containing the inner let_c
. This syntax is evaluated by eval_syntax
, which evaluates the inner let_c
that does the other substitution and gives the fully substituted version of syntax<mpl::plus<a, b>>
.
let_c
used inside eval_syntax
is so common, that Metamonad provides eval_let_c
that does this:
eval_let_c<
b, mpl::int_<4>,
let_c<
a, mpl::int_<9>,
mpl::plus<a, b>
>
>::type
This example uses eval_let_c
instead of using let_c
inside eval_syntax
to make the code more compact. The inner let_c
remains let_c
, thus it returns the fully substituted syntax. If this needs to be evaluated as well, eval_let_c
can be used there as well. To see the difference:
When the inner let_c
remains let_c
, the result of the above expression is syntax<mpl::plus<mpl::int_<9>, mpl::int_<4>>>
.
When eval_let_c
is used instead of let_c
, the result is mpl::int_<13>
.
The main difference between let_c
and eval_let_c
is that while one of them transforms a syntax, the other one transforms a syntax and evaluates the result. In that sense, eval_let_c
is more like the let expressions other languages provide.
As presented in the previous chapter, substituting multiple variables inside one expression may be difficult and one has to be careful to avoid a number of pitfalls. Metamonad provides a special version of let
for substituting multiple variables at a time, this is multi_let
. It can be used the following way:
multi_let<
mpl::map<
mpl::pair<b, syntax<mpl::int_<4>>>,
mpl::pair<a, syntax<mpl::int_<9>>>
>,
syntax<mpl::plus<a, b>>
>::type
multi_let
takes an mpl::map
as its first argument describing all the variable bindings and the syntax to do the substitution in as the second argument. It substitutes all variables specified by the mpl::map
in the syntax.
The classic implementation of a list in functional programming languages is that a list is either an empty list or the combination of a head element and the remaining list. This can be represented in template metaprogramming as well using a class and a template class.
The empty list can be represented using a type:
struct empty : tmp_value<empty> {};
It is a type that is also a template metaprogramming value. A list with a head element and a remaining list can be represented using a template class:
template <class Head, class Tail>
struct cons : tmp_value<con<Head, Tail>> {};
Head
represents the first element of the list and Tail
is a list - either empty
or an instance of cons
.
Any list can be represented using these two elements. For example the empty list is empty
. The [1, 2, 3, 4]
list is
cons<
mpl::int_<1>,
cons<
mpl::int_<2>,
cons<
mpl::int_<3>,
cons<
mpl::int_<4>,
empty
>
>
>
>
This approach uses cons
recursively to build longer and longer lists. The empty
class stops this recursion.
The empty
class and the instances of cons
are template metaprogramming values, thus empty
and cons
are used for constructing values. They are called constructors. They represent a list together, thus the two constructors together form a type. These types are called algebraic data-types. Such types have a name and a number of constructors.
Metamonad provides the MPLLIBS_DATA
macro for defining algebraic data-types. The list type can be created the following way:
MPLLIBS_DATA(list, 0, ((empty, 0))((cons, 1)));
The name of the type is list
. The second macro argument, 0
specifies that the type itself has no arguments - more on that later. The third argument of the macro is a preprocessor sequence of two element tuples. Each tuple defines a constructor. The first element of the tuple is the name of the constructor, the second element is the arity.
The tag of the values built using the constructor is algebraic_data_type_tag
, thus the polymorphic metafunctions of Boost.MPL can be overloaded for algebraic data-types.
The macro defines the class list_tag
. If the second argument of MPLLIBS_DATA
is greater than 0
, this class becomes a template class taking classes as template arguments. This list_tag
class describes the type of the values. When it is a template class, the type has type arguments, for example defining list
the following way
MPLLIBS_DATA(list, 1, ((empty, 0))((cons, 1)));
defines list_tag
to be a template class taking one argument. This argument can be used to describe the type of the list elements.
The values built using the constructors don't carry this type information with them. Metamonad constructs and metafunctions assume that when it is needed, the calling code provides this type information as an extra argument to the metafunctions.
Constructors of algebraic data-types serve as metafunctions for constructing algebraic data-type values. They are lazy metafunctions, for example the expression
cons<
mpl::plus<mpl::int_<9>, mpl::int_<4>>,
empty
>::type
builds the value
cons<
mpl::int_<13>,
empty
>
This value is then a metaprogramming value, thus
cons<
mpl::int_<13>,
empty
>::type
gives
cons<
mpl::int_<13>,
empty
>
When a constructor of an algebraic data-type is evaluated, it evaluates its arguments and instantiates itself again with the evaluated arguments. When the arguments are nullary metafunctions, this serves as a metafunction call. When the arguments are already metaprogramming values, it turns the constructor into a metaprogramming value as it instantiates itself again with the same arguments.
The division function provided by Boost.MPL breaks the compilation when one tries dividing by zero. One could build a version that returns some error value in such a situation - but what should be that error value?
An algebraic data-type can be introduced to represent results that may be failures. The most simple such type is maybe
. It has two constructors:
just<...>
which represents the result of a successful computation
nothing
which represents the failure
Using maybe
it is easy to implement the safe division function:
MPLLIBS_LAZY_METAFUNCTION(safe_divides, (A)(B))
((
mpl::eval_if<
mpl::equal_to<mpl::int_<0>, B>,
nothing,
just<mpl::divides<A, B>>
>
));
This function checks if B
is null and when it is, it returns nothing
indicating that the division is not valid. Otherwise it returns the result of the division wrapped by just
.
maybe
is a good tool for error reporting, however, it can only tell that there was a failure. It can not provide further details about the problem which makes debugging much more difficult. Another algebraic data-type, either
can be used in such situations where further details about the problem can be useful. It has two constructors:
right<...>
for representing results of a successful computation
left<...>
for representing failures
The argument of left
can provide further details about the problem. For example, a special class, division_by_zero
can be used to indicate what happened:
struct division_by_zero : tmp_value<division_by_zero> {};
MPLLIBS_LAZY_METAFUNCTION(safe_divides, (A)(B))
((
mpl::eval_if<
mpl::equal_to<mpl::int_<0>, B>,
left<division_by_zero>,
right<mpl::divides<A, B>>
>
));
This implementation of safe_divides
returns an either
value. When the division is valid, it returns the result of it wrapped by right
, otherwise it returns division_by_zero
wrapped by left
.
Let's write a metafunction for getting the first element of a non-empty list. The metafunction will be called head
. For example when it is called with cons<mpl::int_<13>, empty>
, it should return mpl::int_<13>
. In order to implement such a function, a tool is needed for getting the first argument of the cons
constructor. Using a syntax it is easy to specify which part of the constructor is needed:
syntax<cons<h, _>>
The above syntax uses the h
name to point out the interesting argument of the constructor and _
to express that the second argument can be anything, it is not important.
Metamonad provides the match
metafunction for doing the matching:
MPLLIBS_METAFUNCTION(head, (L))
((
eval_syntax<
mpl::at<
typename match<syntax<cons<h, _>>, L>::type,
h
>
>
))
match
matches the list L
against the pattern cons<h, _>
. When it matches, it returns an mpl::map
binding variables to syntaxes. When it doesn't match, it returns an exception
, which in this case breaks the compilation, as mpl::at
can not deal with it. More on that later. Let's assume, that it matches. In that case, mpl::at
gets the syntax h
referred to in the pattern and the enclosing eval_syntax
unpacks and evaluates it.
For example calling head<cons<mpl::int_<13>, empty>>::type
evaluates the following expression:
eval_syntax<
mpl::at<
typename match<syntax<cons<h, _>>, cons<mpl::int_<13>, empty>>::type,
h
>
>
It evaluates match<syntax<cons<h, _>>, cons<mpl::int_<13>, empty>>::type
, which tries matching the value cons<mpl::int_<13>, empty>
against the pattern cons<h, _>
. It matches and binds the value mpl::int_<13>
to h
, thus match
returns the following mpl::map
:
mpl::map<
mpl::pair<h, syntax<mpl::int_<13>>>
>
This mpl::map
describes that the value mpl::int_<13>
is bound to y
.
match
has a match_c
pair, which takes the pattern as an angle-bracket expression instead of a syntax.
What happens when a variable appears twice in a pattern? For example
mpl::pair<x, x>
is a pattern describing that it expects an mpl::pair
. x
should be bound to the first element and x
should be bound to the second element as well. Only those mpl::pair
values match, where the two elements of the mpl::pair
are the same. For example:
match_c<
mpl::pair<x, x>,
mpl::pair<mpl::int_<11>, mpl::int_<13>>
>::type
This example returns an exception
, since the two elements of mpl::pair<mpl::int_<11>, mpl::int_<13>>
differ, thus it can not be matched against the pattern, which expects the same value at both positions. At the same time
match_c<
mpl::pair<x, x>,
mpl::pair<mpl::int_<13>, mpl::int_<13>>
>::type
works fine, since in this case both elements of the mpl::pair
are mpl::int_<13>
, thus it can be matched against the pattern. It returns the following mpl::map
:
mpl::map<
mpl::pair<x, syntax<mpl::int_<13>>>
>
This mpl::map
binds mpl::int_<13>
to x
. Even though x
appeared twice in the pattern, it is bound only once.
Of course, the special element in the patterns, _
can be used multiple times without extra restrictions. Every occurrence of it means here can be anything.
match_c<
mpl::pair<_, _>,
mpl::pair<mpl::int_<11>, mpl::int_<13>>
>::type
In the above example mpl::int_<11>
is matched against the pattern _
and later mpl::int_<13>
is matched against the pattern _
. Both of them matches and none of them is in the resulting mpl::map
, thus, the above expression returns
mpl::map<>
It returns an empty mpl::map
, since there were no variables in the pattern.
An earlier example used multi_let
to substitute multiple variables at the same time in one expression:
multi_let<
mpl::map<
mpl::pair<b, syntax<mpl::int_<4>>>,
mpl::pair<a, syntax<mpl::int_<9>>>
>,
syntax<mpl::plus<a, b>>>
>::type
multi_let
takes an mpl::map
describing the variable bindings and the expression to do the substitution in. The mpl::map
describing the bindings has the same format as the output of match_c
, thus this map can be built using pattern matching as well:
multi_let<
match_c<mpl::pair<a, b>, mpl::pair<mpl::int_<9>, mpl::int_<4>>>,
syntax<mpl::plus<a, b>>
>::type
This example builds a pair from the values mpl::int_<9>
and mpl::int_<4>
and uses pattern matching to bind a
to mpl::int_<9>
and b
to mpl::int_<4>
. match_c
returns
mpl::map<
mpl::pair<b, syntax<mpl::int_<4>>>,
mpl::pair<a, syntax<mpl::int_<9>>>
>
which is the map describing the variable bindings for multi_let
. Metamonad provides match_let
, which combines match
and multi_let
this way and lets the developer write the above example in a more compact way:
match_let<
syntax<mpl::pair<a, b>>, mpl::pair<mpl::int_<9>, mpl::int_<4>>,
syntax<mpl::plus<a, b>>
>::type
It takes the pattern as the first argument, the expression to match against the pattern as the second one and the expression to do the binding in as the third one. It does the matching and does all the variable replacements.
The common extensions, such as match_let_c
, eval_match_let
or eval_match_let_c
are also available.
Assume, that a safe_divides
function is available for doing an integral division. When the second argument is zero, it returns nothing
, otherwise it returns the result wrapped by just
. Using this function, let's write another one which takes two numbers and tries dividing them. When this is possible, it returns the result of the division, otherwise it returns 1
. Since this function can not fail, there is no point in wrapping the result by just
or something similar.
The problem here is that the result of safe_divides
needs to be checked if it is nothing
or just
, and when it is just
, the value needs to be unwrapped. Metamonad provides case_
to support such situations. It can be used the following way:
MPLLIBS_METAFUNCTION(f, (A)(B))
((
eval_syntax<
case_< safe_divides<A, B>,
matches<syntax<just<x>>, syntax<x>>,
matches<syntax<nothing>, syntax<mpl::int_<1>>>
>
>
));
The above code defines the function described earlier. It takes two arguments, A
and B
and tries dividing them with safe_divides
. The result of it is given to case_
which has two cases, each of which is described by a matches
block. A matches
block takes a pattern and a syntax. When the value returned by the original expression matches the pattern of a matches
block, that block is selected and the body of it, which is the second template argument of matches
is returned. The open variables of the pattern can be used in the corresponding body. The patterns are tried in order and the first one that matches is selected. When none of them matches, case_
returns an exception
.
As case_
returns a syntax, it needs to be evaluated, that is why the whole expression is wrapped by eval_syntax
. To reduce the syntactic noise of codes using case_
, Metamonad provides eval_case
which is the combination of eval_syntax
and case_
.
Metamonad provides matches_c
as well, which is a version of matches
that takes the pattern and the body as angle-bracket expressions and wraps them with syntax
internally.
Using all the above, the f
example can be simplified a bit:
MPLLIBS_METAFUNCTION(f, (A)(B))
((
eval_case< safe_divides<A, B>,
matches_c<just<x>, x>,
matches_c<nothing, mpl::int_<1>>
>
));
This code uses matches_c
to avoid writing syntax
several times and eval_case
immediately evaluate the body of the matches_c
that was selected.
Metafunction classes are callable objects in template metaprogramming. They are values, thus they can be passed around in template metaprograms, but they are functions at the same time, thus they can be called. Metamonad provides tools to construct such objects.
A metafunction class is a function and as every other function, it has function arguments and a function body. Metamonad provides lambda
to construct a metafunction class:
typedef lambda<a, b, syntax<mpl::plus<a, b>>> add;
The above example builds a metafunction class for adding two values. The arguments of the function are represented by variables, the body is represented by a syntax.
The tools provided by Boost.MPL can be used to call this metafunction class. For example:
mpl::apply_wrap2<add, mpl::int_<11>, mpl::int_<2>>::type
The above expression calls the metafunction class add
with two arguments: mpl::int_<11>
and mpl::int_<2>
. add
evaluates mpl::plus<mpl::int_<11>, mpl::int_<2>>
and returns its result, mpl::int_<13>
.
lambda
takes its body as a syntax, but Metamonad provides lambda_c
as well, which takes its body as an angle-bracket expression.
What makes metafunction classes useful is that they can be passed around as data in metaprograms. They can be arguments of or be returned by a metafunction. Such metafunctions that operate on functions are called higher order metafunctions. For example:
MPLLIBS_METAFUNCTION(addn, (N)) ((lambda_c<x, mpl::plus<N, x>>));
This example defines a metafunction, addn
taking a number, N
as argument and building a metafunction class taking a number and increasing it with N
. It can be used as a complicated way of adding two values:
mpl::apply_wrap1<
addn<mpl::int_<11>>::type,
mpl::int_<2>
>::type
This example uses addn
to add the value mpl::int_<2>
to mpl::int_<11>
. The expression addn<mpl::int_<11>>
builds a metafunction class expecting one argument and adding it to mpl::int_<11>
. mpl::apply_wrap1
is used to call this metafunction class with mpl::int_<2>
.
The above example demonstrated how functions can return metafunction classes. Let's build another example showing how a function can take a metafunction class as argument. The classic example for such functions is twice
, a function taking a metafunction class and an argument, calling the metafunction class with the argument and calling it again with the result coming from the first call. For example twice<addn<mpl::int_<1>>, mpl::int_<11>>
would evaluate the following:
mpl::apply_wrap1<
addn<mpl::int_<1>>::type,
mpl::apply_wrap1<
addn<mpl::int_<1>>::type,
mpl::int_<11>
>::type
>::type
This calls addn<mpl::int_<1>>
with mpl::int_<11>
first and then with apply_wrap1<addn<mpl::int_<1>>::type, mpl::int_<11>>
again. twice
can be implemented the following way:
MPLLIBS_METAFUNCTION(twice, (F)(A))
((
mpl::apply_wrap1<
typename F::type,
typename mpl::apply_wrap1<
typename F::type,
A
>::type
>
));
It is lazy for its F
argument (and leaves laziness for A
on F
). It calls F
with A
and calls F
with the result of this. Thus, for example twice<addn<mpl::int_<1>>, mpl::int_<11>>::type
returns mpl::int_<13>
, since it adds 1
to 11
twice.
As template metafunctions built with MPLLIBS_METAFUNCTION
, template metafunction classes built with lambda
support currying. For example:
mpl::apply_wrap2<add, mpl::int_<1>>::type
add
expects two arguments: the two values to add, but the above expression called it with only one argument. It returns another metafunction class expecting the remaining arguments. The body of the lambda
is evaluated only when all arguments are provided.
Thus the above expression returns another metafunction class expecting one argument and then it adds 1
to that argument. Thus, by using currying, there is no need for the addn
metafunction. For example:
twice<mpl::apply_wrap1<add, mpl::int_<1>>, mpl::int_<11>>::type
This example calls twice
with a metafunction class adding 1
to its argument, but this time this metafunction class was not constructed using addn
, but by using currying by calling add
with only one argument.
Currying makes it possible to think of add
as the metafunction class version of addn
:
addn
is a metafunction taking one argument and returning a metafunction class taking another argument and adding the two arguments together.
add
is a metafunction class taking one argument and returning a metafunction class taking another argument and adding the two arguments together.
This commonality makes the development of complex metafunction classes easier.
lambda
can be used to construct functions inside an expression and let
can be used to replace all occurrences of a variable with some expression. Let's look at how the two could be used together to define a function for a sub-expression using let
and lambda
:
let_c<
f, lambda_c<a, b, mpl::plus<a, b>>,
mpl::apply_wrap2<f, mpl::int_<11>, mpl::int_<2>>
>::type
The above expression binds the metafunction class lambda_c<a, b, mpl::plus<a, b>>
to the variable f
in the expression mpl::apply_wrap<f, mpl::int_<11>, mpl::int_<2>>
, thus it uses let
to define an addition function for that expression.
So far, so good, let's do something more complicated. What about defining a recursive function using let
and lambda
? Let's write a factorial this way:
let_c<
f,
lambda_c<n,
if_<
mpl::equal_to<mpl::int_<0>, n>,
mpl::int_<1>,
lazy_times<n, mpl::apply_wrap1<f, lazy_minus<n, mpl::int_<1>>>>
>
>,
mpl::apply_wrap1<f, mpl::int_<3>>
>::type
lazy_minus
and lazy_times
are lazy wrappers around the arithmetic functions coming from Boost.MPL. The above let_c
expression binds a metafunction class to the f
variable in an expression calling this metafunction class with the argument mpl::int_<3>
. This may seem to be fine for the first time, but there is a problem here. The let_c
expression binds the metafunction class to the f
variable in the expression mpl::apply_wrap1<f, mpl::int_<3>>
only, while f
is used inside lambda_c
as well, since the factorial function is defined as a recursive function.
Since let_c
does not bind f
inside lambda_c
, f
is a free variable of the lambda_c
expression. When the above expression is evaluated and the evaluation reaches the first recursive call, mpl::apply_wrap1
complains, that f
is not a function, but a variable. This complain may be a bit difficult to read, since it is coming from the compiler not knowing that it is a template metaprogramming error.
Metamonad provides the letrec
construct for recursive let
bindings. The difference between let
and letrec
is that letrec
does the binding in the expression bound to the variable itself as well. Using letrec_c
in the above example binds the metafunction class to f
inside the metafunction class as well:
letrec_c<
f,
lambda_c<n,
if_<
mpl::equal_to<mpl::int_<0>, n>,
mpl::int_<1>,
times<n, mpl::apply_wrap1<f, minus<n, mpl::int_<1>>>>
>
>,
mpl::apply_wrap1<f, mpl::int_<3>>
>::type
This example works, since due to the recursive binding provided by letrec_c
the metafunction class can call itself recursively to calculate the factorial value.
Boost.MPL supports polymorphic metafunctions. For example the addition operation makes sense for a number of different types. Integers, longs, etc can be added. An add
metafunction the way Boost.MPL supports it can be implemented the following way:
template <class TagA, class TagB>
struct add_impl;
MPLLIBS_LAZY_METAFUNCTION(add, (A)(B))
((mpl::apply_wrap2<add_impl<typename A::tag, typename B::tag>, A, B>));
It assumes, that each metaprogramming value has a tag associated with it and declares a template class, add_impl
taking two arguments: the tags of the values to be added. The instances of this template are assumed to be metafunction classes taking two arguments: the values to be added. A new overload can be added by specialising add_impl
for some tag. For example to specialise it for integers:
typedef mpl::int_<0>::tag int_tag;
template <>
struct add_impl<int_tag, int_tag> : tmp_value<add_impl<int_tag, int_tag>>
{
MPLLIBS_METAFUNCTION(apply, (A)(B))
((mpl::int_<A::type::value + B::type::value>));
};
This code specialises add_impl
for the case when both arguments are mpl::int_
values and does the addition by unwrapping the arguments, evaluating the addition and wrapping the arguments again.
To prepare add
for adding mpl::long_
values, add_impl
needs to be specialised again:
typedef mpl::long_<0>::tag long_tag;
template <>
struct add_impl<long_tag, long_tag> : tmp_value<add_impl<long_tag, long_tag>>
{
MPLLIBS_METAFUNCTION(apply, (A)(B))
((mpl::long_<A::type::value + B::type::value>));
};
This specialisation works the same way as the previous one, but it wraps the results as mpl::long_
values.
How can a subtraction operation be implemented? By writing another overloadable metafunction for it:
template <class TagA, class TagB>
struct sub_impl;
MPLLIBS_LAZY_METAFUNCTION(sub, (A)(B))
((mpl::apply_wrap2<sub_impl<typename A::tag, typename B::tag>, A, B>));
This code declares the sub_impl
template class, that can be specialised later and it defines the sub
metafunction instantiating and calling sub_impl
with the tags of the arguments. Multiplication and division can be implemented in a similar way.
Let's introduce the concept of a number and assume, that numbers can be added, subtracted, multiplied and divided. Thus, when something is a number, then all of these metafunctions are overloaded to handle it. How is the connection between these metafunctions implemented? It lives in the documentation, describing what being a number means. What happens when someone introduces a new type, for example float_<...>
and forgets to overload add
for float_
? When someone uses float_
values assuming that they are numbers and tries calling add
for float_
values, he gets an error message saying that add
is not overloaded for float_
values (he actually gets an error message complaining about the missing definition of add_impl<float_tag, float_tag>
, but it is easy to learn what it means). What is missing there, is: the code assumed that float_
is a number, but it isn't.
There is a way of adding this information to the error message by using traits. The operations of the number concept can be collected into a trait:
template <class Tag>
struct number;
This template class, when instantiated with a tag defines all operations required by the number concept. Declaring this template means: there is a concept called number
. Unfortunately the way it can specify the list of required operations is listing them in the documentation or a comment:
template <class Tag>
struct number;
The above code defines the number
concept and lists the required operations. To say that mpl::int_
values are numbers, this template class needs to be specialised:
template <>
struct number<int_tag> : tmp_value<number<int_tag>>
{
struct add : tmp_value<add>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B)) ((int_<A::value + B::value>));
};
struct sub : tmp_value<sub>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B)) ((int_<A::value + B::value>));
};
struct mul : tmp_value<mul>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B)) ((int_<A::value * B::value>));
};
struct div : tmp_value<div>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B)) ((int_<A::value / B::value>));
};
};
This code implements the four operations for mpl::int_
values. To add mpl::int_<2>
to mpl::int_<11>
using this solution, one has to write
mpl::apply_wrap2<number<int_tag>::add, int_<11>, int_<2>>::type
This code calls the add
operation of the number
concept for the two values to add. As this approach is inspired by typeclasses in Haskell, concepts like number
are called typeclasses. Following the Haskell terminology, when the number
template class is specialised for mpl::int_
values, mpl::int_
values are instances of the number
typeclass. To avoid having to use mpl::apply_wrap
all the time, these operations can be wrapped by helper metafunctions:
MPLLIBS_LAZY_METAFUNCTION(add, (Tag)(A)(B))
((mpl::apply_wrap2<typename number<Tag>::add, A, B>));
This add
function makes calling the add
operation of the number
typeclass easier, since it can be used the following way:
add<int_tag, int_<11>, int_<2>>::type
This solution passes the tag to use and the arguments of the add
operation to the add
wrapper metafunction. Instead of expecting it as an extra argument, the add
wrapper metafunction could use the ::tag
of one of its arguments as well:
MPLLIBS_LAZY_METAFUNCTION(add_, (A)(B))
((mpl::apply_wrap2<typename number<typename A::tag>::add, A, B>));
This version of the add
wrapper metafunction takes only two arguments: the values to add and uses the ::tag
of the first argument to choose the right instance of the number
typeclass.
While not having to pass the tag as an extra argument to add_
is more convenient, the ability to be able to explicitly specify it adds extra flexibility to this solution which typeclasses provided by Metamonad (monad
, monoid
) can take advantage of.
Let's implement an ord
typeclass for values that can be compared:
template <class Tag>
struct ord;
This typeclass expects one operation - more can be added later. Let's make mpl::int_
values an instance of this typeclass:
template <>
struct ord<int_tag>
{
struct less : tmp_value<less>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B))
((mpl::bool_<(A::value < B::value)>));
};
};
The above code specialises ord
for int_tag
and implements the comparison operation by unwrapping the values, comparing them and wrapping the result again. Since the result of a comparison is a logical value, the result is wrapped with mpl::bool_
.
Now let's make mpl::long_
values an instance of ord
as well:
template <>
struct ord<long_tag>
{
struct less : tmp_value<less>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B))
((mpl::bool_<(A::value < B::value)>));
};
};
The implementation of the less
operation for mpl::long_
values is the same as it was for mpl::int_
values. And for a number of other types it is the same as well. Not for all of them, for example for mpl::string
values it would be different. But the above implementation would be a reasonable default implementation, that could be overridden for instances that can not use it.
The default implementation can be provided by another template class, ord_defaults
:
template <class Tag>
struct ord_defaults
{
struct less : tmp_value<less>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B))
((mpl::bool_<(A::value < B::value)>));
};
};
This template class defines the default less
operation. It takes the tag as a template argument in case the default implementation of an operation would rely on another operation provided by the ord
typeclass - this is not the case in this example.
Implementations of ord
can make use of the defaults:
template <>
struct ord<int_tag> : ord_defaults<int_tag> {};
template <>
struct ord<long_tag> : ord_defaults<long_tag> {};
Both instances of ord
inherit form ord_defaults
and inherit the default implementation of the operations. The above code may suggest that having the following implementation may be a good idea:
template <class Tag>
struct ord : ord_defaults<Tag> {};
This code inherits from ord_defaults
for all Tag
and the specialisations for int_tag
and long_tag
are not needed, since they are already handled by this code. What happens, when someone tries comparing two mpl::vector_c
values using ord
?
mpl::apply_wrap2<
ord<vector_tag>::less,
vector_c<int, 1, 2>,
vector_c<int, 3>
>::type
As mpl::vector_c
values are not instances of the ord
typeclass, they can not be compared, thus it emits an error message. Will the error message say: vectors can not be compared? No, it won't. It will complain about that an mpl::vector_c
has no ::value
. However, by defining ord
the original way makes the error message better:
template <class Tag>
struct ord;
template <>
struct ord<int_tag> : ord_defaults<int_tag> {};
template <>
struct ord<long_tag> : ord_defaults<long_tag> {};
Trying to compare vectors with ord
would generate an error message complaining about that ord<vector_tag>
has no definition, which means that vector values are not instances of ord
, thus they can not be compared. As the metaprogramming libraries have no control over the error messages the compiler displays, the connection between the error message and its meaning needs to be learned, but fortunately it always means the same.
To keep the code maintainable typeclasses are always expected to have a _defaults
implementation even when it is empty and specialisations of the trait of the typeclass are always expected to inherit from it.
A benefit of using typeclasses is that generic code can be written using them. For example, let's define a typeclass for values that can be added (no further arithmetic operations are required this time):
template <class Tag>
struct addable;
template <class Tag>
struct addable_defaults {};
It expects one operation, add
which implements adding two values. It has no default implementation, thus the class addable_defaults
is empty. A helper metafunction for calling add
is useful:
MPLLIBS_LAZY_METAFUNCTION(add, (Tag)(A)(B))
((mpl::apply_wrap2<typename addable<Tag>::add, A, B>))
This is the convenience wrapper for calling the add
operation. The mpl::int_
values can be made instances of this typeclass:
template <>
struct addable<int_tag> : addable_defaults<int_tag>
{
struct add : tmp_value<add>
{
MPLLIBS_LAZY_METAFUNCTION(apply, (A)(B)) ((mpl::int_<A::value + B::value>));
};
};
This is similar to the add
operation of the earlier number
typeclass. Since only addition is required, lists can be made an instance of this typeclass in a reasonable way:
typedef mpl::list<>::tag list_tag;
template <>
struct addable<list_tag> : addable_defaults<list_tag>
{
typedef
lambda_c<a, b,
lazy<
mpl::insert_range<
lazy_protect_args<a>,
mpl::end<lazy_protect_args<a>>,
lazy_protect_args<b>
>
>
>
add;
};
This implementation appends the two lists together using mpl::insert_range
. Thus, evaluating:
add<list_tag, mpl::list_c<int, 1, 2>, mpl::list_c<int, 3, 4>>::type
gives mpl::list_c<int, 1, 2, 3, 4>
as its result.
When the values of a type can be added, they can be multiplied by non-negative integer values as well. For any x
value, 3 * x
can be implemented as x
x x
. A metafunction can be written that accepts any addable
value and a non-negative multiplier and does the multiplication:
MPLLIBS_LAZY_METAFUNCTION(mult, (T)(N))
((
if_<
mpl::equal_to<mpl::int_<1>, N>,
T,
add<typename T::tag, mult<T, mpl::minus<N, int_<1>>>, T>
>
));
This metafunction takes T
, the value to be multiplied and N
, the multiplier. It uses a recursive implementation to call add
N
times. And as it uses the addable
typeclass, it works for mpl::int_
and mpl::list_c
values:
mult<mpl::int_<3>, mpl::int_<4>>::type
evaluates to mpl::int_<12>
mult<mpl::vector_c<int, 1>, mpl::int_<4>>::type
evaluates to mpl::vector_c<int, 1, 1, 1, 1>
.What happens when someone tries multiplying mpl::void_
values, that can not be added? When mult
tries calling the add
operation of addable
, the compiler emits an error about that mpl::void_
values are not addable.
Monoids come from abstract algebra, they are a combination of a set of values and a binary operation on them. To be a monoid, the binary operation has to be associative and there has to be an identity value.
For example the mpl::int_<...>
values and the mpl::plus<..., ...>
operation form a monoid. Addition - implemented by mpl::plus
- is associative and the identity value is mpl::int_<0>
, since mpl::plus<x, mpl::int_<0>>
and mpl::plus<mpl::int_<0>, x>
both return x
for any x
number.
Another example is mpl::int_<...>
values and the mpl::times<..., ...>
operation, they also form a monoid. Multiplication - implemented by mpl::times
- is associative and the identity value is mpl::int_<1>
.
The above examples show that the same set of values with different operations can form different monoids - the identity value depends on the operation.
Not only numbers can form monoids. Lists together with list concatenation form a monoid as well. The identity value in this case is the empty list.
Metamonad provides the monoid
typeclass for representing monoids. Unfortunately, the set of values can only be specified informally by the documentation. However, this makes the definition of these sets more flexible than it is in Haskell, since it is not limited by the type system. The binary operation of the monoid is an operation expected by the typeclass. It is called mappend
. The typeclass also expects a nullary metafunction, mempty
returning the identity value.
In Haskell a type can be an instance of a typeclass only once, but as the examples at the beginning of this chapter show the same set of values can be part of multiple typeclasses when they are combined with different operations. Since the typeclass implementation of Metamonad is based on tags instead of types and this is not deduced from the values but provided as a template argument when using the operations of the typeclass, in Metamonad a type may be part of different monoids depending on which tags are used.
Monads play a central role in the Haskell language. Based on the commonalities of Haskell and template metaprogramming, Metamonad brings monads into template metaprogramming. A monad is a structure for abstracting computations. It consists of the following:
tag
, identifying the monad itselfreturn_<...>
taking some value and returning an element of the setbind<..., ...>
taking an element of the set and a function, taking some value and returning an element of the set. bind
returns an element of the set.bind_
taking two monadic values and returning a new one. It has a default implementation that calls bind
with the first value and a metafunction class that always returns the second argument of bind_
.fail
taking a value and returning a monadic value that breaks the execution of the monad. It has a default implementation that throws a compile-time exception. More on them later.In Haskell the set of values is identified by the type system, in template metaprogramming it is identified by an informal description in the documentation.
Similarly to Haskell, Metamonad provides the monad
typeclass for implementing monads. It requires return_
and bind
to be implemented as metafunction classes.
Metamonad uses tags
to identify monads themselves, but not to identify the set of values. tags
are used as a replacement of Haskell's value constructors and pattern matching. For example Haskell's Maybe
is implemented the following way to support metafunction overloading:
struct nothing_tag;
struct just_tag;
struct nothing { typedef nothing_tag tag; };
template <class T>
struct just { typedef just_tag tag; };
The Maybe
monad consists of the nothing
and just
values, which have different tags
. Because of this, tags
cannot be used to identify the set of values belonging to a monad.
Metamonad provides metafunctions for the operations implemented by the typeclass to hide the typeclass itself behind monads. These functions take the tag
of the monad as their first argument and call the same operation of the typeclass:
template <class MonadTag, class SomeValue>
struct return_;
template <
class MonadTag,
class SomeValue,
class FunctionReturningElementOfSet
>
struct bind;
Haskell has semantic expectations for monads that are documented but can not be verified by the compiler. The C++ template metaprogramming equivalent of these expectations are the following.
monad<Tag>::bind<monad<Tag>::return_<X>, F>
is equivalent to mpl::apply<F, X>
.monad<Tag>::bind<M, monad<Tag>::return_>
is equivalent to M
.monad<Tag>::bind<M, lambda<x, monad<Tag>::bind<mpl::apply<F, x>, G>>>
is equivalent to monad<Tag>::bind<monad<Tag>::bind<M, F>, G>
. lambda
is Metamonad's lambda expression implementation.Similarly to Haskell, Metamonad cannot verify these expectations. It is the responsibility of the monad's author to satisfy these expectations.
Haskell provides syntactic sugar for monads, called do notation. In Haskell, a do block is associated with a monad and contains a number of monadic function calls and value bindings. Here is an example do block:
do
r <- may_fail1 13
may_fail2 r
This evaluates may_fail1 13
, binds r
to its result and evaluates may_fail2 r
. Metamonad implements a similar notation for writing monadic template metaprograms. A do block using Metamonad looks like the following:
do_<monad_tag,
step1,
step2,
// ...
stepn
>
monad_tag
is the tag
identifying the monad. This has to be passed to the return_
and bind
functions. do_<monad_tag>
is a metafunction class, taking the steps of the do block as arguments. The steps have to be syntaxes and of course do_c
is also provided. A step is either a nullary metafunction returning a monadic value or a binding of an expression to a name. A binding is expressed by the following structure:
set<name, step>
where set
is a template class. step
is a nullary metafunction returning a monadic value. name
is the name of a class, the binding binds the result of step
to this name. The bound name can be used in the steps of the do block following the binding.
Using return_
in do blocks directly is not convenient since the tag
of the monad has to be passed to the return_
metafunction explicitly, thus every time return_
is used, the tag
of the monad needs to be repeated. For example:
do_c<monad_tag,
step1,
step2,
set<some_name, return_<monad_tag, some_value>>,
// ...
stepn
>
To make using return_
in do blocks simpler, Metamonad provides a template class, do_return
, that can be used in do blocks:
do_c<monad_tag,
step1,
step2,
set<some_name, do_return<some_value>>,
// ...
stepn
>
A do_return<X>
instance of this template class gets automatically translated to return_<Tag, X>
inside a do block with Tag
as tag;
A number of tools have been presented for error handling in template metaprograms. The easiest way is to emit a compilation error and break the compilation process. When this happens, no wrapper code prepared for handling error situations can recover from this.
One can use maybe
to be able to report that there was a failure. In this case returning nothing
indicates that there was an error and returning the result wrapped by just
indicates success. The problem with this approach is that no further details can be provided - the only information the caller gets is that something went wrong and it is his task to guess what.
To overcome the limitation of maybe
, either
can report error details as well. A function may return the result of the computation wrapped by right
when things went fine and some template metaprogramming value wrapped by left
when something went wrong. The caller can interpret the value wrapped by left
to get further information about the problem. This works, but it still changes the interface of the function. Something as simple as safe_divides<mpl::int_<26>, mpl::int_<2>>
returns right<mpl::int_<13>>
and the caller has to unwrap it later.
Metamonad provides another approach for error reporting. When the computation is successful, the result can be returned as it is without further wrappers like just
or right
. However, when something goes wrong, the function can return some metaprogramming value wrapped by exception
. The value itself can provide further details about the problem that happened.
Using exception
, the safe_divides
function can be implemented the following way:
struct division_by_zero : tmp_value<division_by_zero> {};
MPLLIBS_LAZY_METAFUNCTION(safe_divides, (A)(B))
((
if_<
mpl::equal_to<mpl::int_<0>, B>,
exception<division_by_zero>,
mpl::divides<A, B>
>
));
This code defines the template metaprogramming value division_by_zero
to describe the problem of dividing by zero. safe_divides
checks if B
is zero. When it is, it returns division_by_zero
wrapped by exception
, otherwise it returns the result of the division.
A function taking two numbers, dividing them when possible and returning 1
when they can not be divided can be implemented the following way:
MPLLIBS_METAFUNCTION(f, (A)(B))
((
eval_case< safe_divides<A, B>,
matches_c<exception<_>, mpl::int_<1>>,
matches_c<r, r>
>
));
This code calls safe_divides
and does pattern matching on its result. When it matches the pattern exception<_>
, it returns mpl::int_<1>
, otherwise it returns the result of safe_divides
, since everything matches the pattern r
.
This can be done, because template metaprogramming is loosely typed and no type-checker complains about the type of the return value of safe_divides
.
case_
and eval_case
can be used to detect and handle exceptions, however, they are generic tools. Metamonad provides further tools for catching exceptions. The above example can be implemented using catch_all
as well:
MPLLIBS_METAFUNCTION(f, (A)(B))
((catch_all<safe_divides<A, B>, lambda_c<_, mpl::int_<1>>>));
This code evaluates safe_divides
and if it returned an exception
, the lambda expression is called and the value wrapped by exception
is passed to it as argument. Otherwise the result is returned. This can be used to catch all exceptions that may be returned by an expression.
When only a subset of the exceptions should be caught, catch_just
can be used. It takes a predicate that decides if the exception should be handled or it should be returned unchanged.
MPLLIBS_METAFUNCTION(f, (A)(B))
((
catch_just<
safe_divides<A, B>,
lambda_c<e, boost::is_same<division_by_zero, e>>,
lambda_c<_, mpl::int_<1>>
>
));
This code catches only division_by_zero
exceptions. For the rest of the exceptions the predicate, which is the second argument of catch_just
, returns false and in those cases the handler, the third argument of catch_just
is not called.
Let's assume, that two metafunctions, may_throw1
and may_throw2
are given. Both of them takes a number as argument and either returns a number or an exception. Let's try to evaluate the following expression:
mpl::plus<
may_throw1<mpl::int_<11>>::type,
may_throw2<mpl::int_<13>>::type
>
The above expression adds the result of may_throw1
and may_throw2
together and works fine as long as they don't return an exception. But when any of them returns an exception, mpl::plus
breaks the compilation, since exceptions can not be added. Ideally, mpl::plus
should forward the exception to its caller by returning it. However, mpl::plus
among a large number of metafunctions is not prepared for forwarding exceptions. Thus, the user of mpl::plus
has to make sure, that exceptions coming from sub-expressions are handled properly. The above example can be rewritten to prepare for every possible exception:
eval_case< may_throw1<mpl::int_<11>>,
matches_c<exception<e>, exception<e>>,
matches_c<a,
eval_case< may_throw2<mpl::int_<13>>,
matches_c<exception<e>, exception<e>>,
matches_c<b, mpl::plus<a, b>>
>
>
>
It evaluates may_throw1<mpl::int_<11>>
first, checks if it has returned an exception. If so, the exception is propagated, otherwise may_throw3<mpl::int_<13>>
is evaluated and if it has returned an error, it is propagated. When none of them has returned an error, mpl::plus
is called.
To propagate exceptions properly, every function call that may return an exception has to be individually verified - and when one looks at the expression that is prepared for exception propagation, it takes time to figure out what the code is really doing, exception propagation adds too much syntactic noise.
Metamonad defines the exception monad for handling this situation. The monadic values are errors wrapped by exception
and values not wrapped by exception
, thus, basically every template metaprogramming value is a monadic value. The bind
operation checks if its first argument is an exception. If yes, it returns that exception otherwise it evaluates the action, the second argument of bind
. return
is the identity function.
Using the exception monad and the the do notation, the above expression can be simplified:
do_c<exception_tag,
set<a, may_throw1<mpl::int_<11>>>,
set<b, may_throw2<mpl::int_<13>>>,
mpl::plus<a, b>
>
It makes use of the do notation to simplify error propagation. The arguments of mpl::plus
are stored in temporary variables, a
and b
and mpl::plus
is called at the last step only. Due to the way do blocks are evaluated, when any of the arguments evaluates to an exception
, the execution of the do block gets stopped and the exception is returned.
This way of writing such expressions is easier and has less syntactic noise, however, it is still not as readable as the original form. Metamonad provides another tool, make_monadic
for transforming the original expression into this form.
make_monadic<
exception_tag,
mpl::plus<
may_throw1<mpl::int_<11>>::type,
may_throw2<mpl::int_<13>>::type
>
>
The above code automatically transforms the original expression, which is the second argument of make_monadic
into the form using the do block, thus it adds exception propagation to it. Since the monad to use is an argument of this function, it is not limited to the exception monad only.
Let's add exception handling to the above example. When evaluating the expression returns an exception, some special value should be returned - based on the type of the error. It can be done using the tools presented so far:
catch_all<
catch_just<
make_monadic<
exception_tag,
mpl::plus<
may_throw1<mpl::int_<11>>::type,
may_throw2<mpl::int_<13>>::type
>
>,
lambda_c<e, boost::is_same<e, division_by_zero>>,
lambda_c<_, mpl::int_<1>>
>,
lambda_c<_, mpl::int_<0>>
>
The above expression may look overly complicated for the first time, even though it does simple things only. It turns the original expression into a monadic one by using make_monadic
and checks if it has returned a division_by_zero
exception
by using catch_just
. In that case, it returns mpl::int_<1>
, otherwise it checks if the expression has returned any other exception by using catch_all
. If there was another exception, it returns mpl::int_<0>
, otherwise it returns the result of the original expression.
To reduce the amount of syntactic noise and make the above code more compact, Metamonad provides try_
blocks:
try_<
syntax<
mpl::plus<
may_throw1<mpl::int_<11>>::type,
may_throw2<mpl::int_<13>>::type
>
>,
catch_<e, syntax<boost::is_same<e, division_by_zero>>, syntax<mpl::int_<1>>>,
catch_<e, syntax<mpl::true_>, syntax<mpl::int_<0>>>
>
try_
takes a syntax as its first argument and adds exception propagation to it using make_monadic
. When no further arguments are provided, try_
returns the result of evaluating this, thus it can be used as a short form of make_monadic<exception_tag, ...>
. However, catch_
arguments can be provided, that can handle any exception returned by the expression. The first argument of such a catch_
is a variable, which will reference the exception in the rest of the catch_
block. The second argument is a syntax that should evaluate to a boolean value. It is used to decide if this catch_
block should handle the exception. When it evaluates to true, the third argument of catch_
, which is also a syntax is evaluated and its result is returned by try_
.
The catch_
blocks are checked in order and the first one that handles the exception is used - the remaining blocks are not checked. Even, when the handler returns an exception, it is not handled by any of the remaining catch_
blocks.
The _c
versions of try_
and catch_
are also provided and using them helps making the code more compact:
try_c<
mpl::plus<
may_throw1<mpl::int_<11>>::type,
may_throw2<mpl::int_<13>>::type
>,
catch_c<e, boost::is_same<e, division_by_zero>, mpl::int_<1>>,
catch_c<e, mpl::true_, mpl::int_<0>>
>
This code does the same as the previous one, however by using try_c
and catch_c
the syntax
templates could be removed.
Copyright Abel Sinkovics (abel at elte dot hu) 2011. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt