Re: [boost] "Simple C++11 metaprogramming"

Subject: Re: [boost] "Simple C++11 metaprogramming"
From: Bruno Dutra (brunocodutra_at_[hidden])
Date: 2015-08-20 19:50:52

2015-08-19 20:31 GMT-03:00 Eric Niebler <eniebler_at_[hidden]>:

> <snip>
>
> > I concur with Eric that functional composition is a killer feature and
> > I strongly believe it should constitute the very core of any
> > metaprogramming library. I just go a step further and greatly simplify
> > things by getting rid of "metafunction classes" altogether. I've
> > managed to transfer the entire burden of abstraction to an analogous
> > of MPL's apply, which expects a "lambda expression" and a set of
> > arguments and, through a handful of partial specializations, directly
> > evaluates it. Atop apply<>, bind<> becomes a one-liner, as do
> > everything else just as gracefully. Oh and this way one also avoids
> > dealing with core issue #1430, since MPL's quote<> is no more.
>
> Although interesting from a design perspective, I suspect that if you
> benchmark you'll find this approach is too heavy. Compile-time lambdas
> are expensive. Turning *every* metafunction evaluation into a lambda
> evaluation is going to kill compile-times.
>
> Apologies if I've misunderstood.
>

Not every metafunction evaluation is made into a lambda evaluation, just
those that require higher order composability, such as fold, transform,
count_if, etc. In any case I'd like to discuss some numbers regarding the
following three *naive* implementations of transform<>, where extract<> is
an alias to "typename ::type", eval<> [1] is a SFINAE friendly metafunction
evaluator and apply<> behaves like its homonym from MPL, but uses eval<> as
its SFINAE backend.

template<

    template<typename...> class expr,

    template<typename...> class list,

    typename... args

>

struct transform<expr, list<args...>>

{

//    using type = list<extract<expr<args>>...>             A

//    using type = list<extract<eval<expr, args>>...>       B

//    using type = list<extract<apply<expr<_1>, args>>...>  C

};

And the numbers for GCC 5.2.0 are:

    1000    3000    5000

A   0.64    1.65    2.62

B   0.86    2.31    3.73

C   2.01    5.51    9.36

Clearly you are right, lambdas are expensive, but interestingly eval<> is
not that much. Congratulations, you have just convinced me to provide a
further specialization for apply<>:

template<

    template<template<typename...> class> class lbd,

    template<typename...> class expr,

    typename... args

>

struct apply<lbd<expr>, args...> :

        eval<expr, args...>

{};

Which allows the user to not depend on lambdas if she doesn't need to.

template<template<typename...> class> struct lbd;

template<

    template<typename...> class expr,

    template<typename...> class list,

    typename... args

>

struct transform<expr, list<args...>>

{

    using type = list<extract<apply<lbd<expr>, args>>...>;

};

And the numbers are

    1000    3000    5000

D   0.84    2.33    3.75

i.e. essentially the same as B.

> If one looks closer, by doing the actual recursive metafunction
> > evaluation in a SFINAE context behind the scenes, apply<> becomes a
> > monadic bind of metafunctions, which, from this perspective, are
> > themselves nothing more than optionals. Such concepts bring great
> > expressiveness to a functional world.
>
> You refer to your eval template that returns just<Ret> or nothing? It's
> interesting, but essentially the same as turning evaluation failures
> into a SFINAE-able condition. It has the same pros and cons, too. If you
> get back a "nothing" from a complicated computation, you're left
> wondering why. I don't have a good solution to that yet.

What I mean is that by carefully using SFINAE to avoid internal errors one
can guarantee that instantiating any metafunction part of the library is
"safe", provided of course the user provides SFINAE friendly arguments. Now
allow me  to elaborate on what I mean by "safe".

First let's consider the case where user provided arguments are SFINAE
friendly, i.e. user provided lambda, for instance, does not inherit from
some undefined/final/fundamental type or anything of the sort, then
instantiating any metafunction<args...> part of the library is guaranteed
to be strictly equivalent to either of the following:

1. opt {};
2. opt {using type = ret;};

Since, by definition, a lazy metafunction is only evaluated when its nested
::type is named, then any metafunction is inherently a model of optional,
that is, it either has a nested type (just something) or not (nothing).
Such a guarantee allows one to provide traits such as is_just and
is_nothing that can be used to safely test whether any metafunction call
has succeeded, this way, has_key, for example, may be reduced to the
following:

template<typename seq, typename key>

struct has_key :

        is_just<at_key<seq, key>>

{};

and is guaranteed to safely inherit from either std::true_type or
std::false_type for whatever arguments the user provides.

Now lets imagine the user nonetheless tries to evaluate a metafunction that
instantiates to "nothing". The only error the compiler will raise will look
similar to the following:

error: no type named 'type' in 'struct metafunction<args...>'

That's it, no scary internals exposed.

Now lets assume the user provides arguments that are not SFINAE friendly
that do induce some irrecoverable error. In this case the compiler will
complain about an error in the user code, which is even less scary than
some internal error inside a library. I don't think there is any better
approach regarding user friendliness apart from static_assert'ing
everything, which, on the other hand, has the down side of making it
impossible to implement useful traits such as is_just and is_nothing.

Thank you for such an insightful discussion,
Bruno

[1] https://brunocodutra.github.io/metal/structmetal_1_1eval.html