Re: [boost] [mpl] multiset

Subject: Re: [boost] [mpl] multiset
From: Eric Niebler (eniebler_at_[hidden])
Date: 2015-03-08 15:56:13

On 3/7/2015 6:41 AM, Louis Dionne wrote:
> Strictly speaking, the definition of `lift` in the MPL11 is as above
> to workaround a GCC bug. Otherwise, it is exactly the same as in Meta:
> 
>         template <template <typename ...> class f>
>         struct lift {
>             using type = lift;
> 
>     #if defined(BOOST_MPL11_GCC_PACK_EXPANSION_BUG)
>             template <typename ...x>
>             struct apply : f<x...> { };
>     #else
>             template <typename ...x>
>             using apply = f<x...>;
>     #endif
>         };

FWIW, this implementation will quickly run afoul of core issue 1430[*],
which I know you're aware of because you commented on a gcc bug about
it. :-) You should have a look at how I avoided the problem in Meta.
meta::quote is somewhat subtle.

[*] http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1430

> That being said, it is true that MPL11 uses "thunks", i.e.
> nullary metafunctions. The reason for that is exactly what I
> have been advocating during the whole construction of the MPL11;
> it is easier to build up more complex metafunctions when they are
> lazy, because you don't risk instantiating metafunctions that would
> fail whenever you branch.

I don't disagree about the importance of laziness. The question is how
to deal with it, and whether casual users need to be aware of it.

>> In contrast, here is (in essence) how Meta defines quote:
>>
>> template <template <typename ...> class f>
>> struct quote
>> {
>>     template <typename ...xs>
>>     using apply = f<xs...>;
>> };
>>
>> In Meta, the template aliases are used extensively, and types evaluate
>> directly to their results. Things are done eagerly. There are no "thunks".
> 
> Here's my understanding of how Meta works:
> 
> Meta still uses the classical concept of a metafunction with a nested type,
> but it is hidden behind `meta::eval`. 

No. Metafunctions in Meta are incidental, not fundamental. If it were
possible to specialize template aliases, there would be no nested ::type
anywhere in Meta -- it's used as an implementation detail only for some
of the algorithms. I use some tricks to *implement* Meta that I don't
use when I'm *using* Meta. When using Meta, laziness is best (IMO)
achieved with defer, lambda, and let (although nothing is stopping
someone from creating metafunctions and using the meta::lazy namespace
in a more "traditional" way).

> Basically, the main interface of the
> library is the `*_t` version of the actual metafunctions. Then, Meta uses
> `defer` to systematically provide a lazy version of each eager metafunction
> in the `lazy` namespace, because lazy metafunctions are often useful as you
> rightfully noted.

Defer isn't used with metafunctions. There would be no point. Defer is
used with aliases (which are not metafunctions, but some are implemented
that was under the covers, see above). Defer turns eager computations
into lazy ones. How the eager computations are implemented is beside the
point.

> In contrast, MPL11 just uses lazy metafunctions all the time, and you only
> need to use `eval` (or actually `typename ::type`) at the very end of a
> computation. It would thus be equivalent to provide `*_t` aliases for all
> MPL11 metafunctions.

In meta, a lazy computation is evaluated by wrapping it in let<>.
Without local variables, a let<> is nothing more than a nullary lambda
invocation.

>> Of course, when writing a lambda or a let expression, evaluation needs
>> to be deferred until the substitutions are made. I use a template called
>> "defer" for that. It's only intended for use by let and lambda. Although
>> it does give things a nested "::type", it doesn't strictly need to;
>> indeed when I first added it, it didn't.
>>
>> Anyway, that may seem like a subtle difference, but it feels like sea
>> change to me. I find it much nicer working this way.
> 
> I don't find that defaulting to eager metafunctions is nicer working. 
> It has been, at least for me, the source of a lot of pain because
> I was required to write helper metafunctions to branch lazily.

I never need to use helper metafunctions. Meta's expression evaluator
handles laziness.

> Plus, when you use lazy metafunctions all the time, you almost 
> never have to type `typename f<x>::type` (instead you just use 
> `f<x>`), and so the syntax looks pretty much the same as when 
> you use template aliases.

<snip discussion of Foldable>
> If you go down that road, just add `*_t` aliases
> to the MPL11 and you're done. Otherwise, keep it as simple as
> possible and just manipulate dumb type lists, which is what 
> 90% of the people need anyway. That's my .02.

This, IMO. And I suspect 90% is a low estimate.

I feel like Meta's approach to laziness hasn't been understood. Here,
for instance, is a SFINAE-friendly implementation of std::common_type;
it has a ::type when a common type exists, but otherwise it doesn't.
When it was implemented with metafunctions it was a huge mess. With
meta::defer and meta::let, it's simple and straightforward.

(NOTE: No metafunctions, no eval except to define common_type_t.)

namespace m = ranges::meta;
namespace ml = ranges::meta::lazy;

template<typename T, typename U>
using builtin_common_t =
    decltype(true? std::declval<T>() : std::declval<U>());
template<typename T, typename U>
using lazy_builtin_common_t =
    m::defer<builtin_common_t, T, U>;

template<typename...Ts>
struct common_type
{};

template<typename ...Ts>
using common_type_t = m::eval<common_type<Ts...>>;

template<typename T>
struct common_type<T>
  : std::decay<T>
{};

template<typename T, typename U>
struct common_type<T, U>
  : m::if_c<
        ( std::is_same<decay_t<T>, T>::value &&
          std::is_same<decay_t<U>, U>::value ),
        ml::let<lazy_builtin_common_t<T, U>>,
        common_type<decay_t<T>, decay_t<U>>>
{};

template<typename T, typename U, typename... Vs>
struct common_type<T, U, Vs...>
  : ml::let<ml::fold<m::list<U, Vs...>, T, m::quote<common_type_t>>>
{};

// TESTS
static_assert(std::is_same<common_type_t<char, short, char, short>,
int>::value, "");
static_assert(std::is_same<common_type_t<char, short, float, short>,
float>::value, "");

// HAS NO COMMON TYPE:
static_assert(!m::has_type<common_type<int, int, int*>>::value, "");

What's interesting here is that you get a SFINAE-friendly common_type
for free. Since Meta's expression evaluator is handling laziness, it can
be SFINAE-friendly itself. Nowhere do you need to test whether a
computation has succeeded or failed. If any substitution failure occurs
in an immediate context, the whole computation is aborted. It just falls
out of the lambda/defer interaction.

(You can get backtraces by moving computations into non-immediate contexts.)

I would be curious to see this implemented in Hana and in Turbo.

As for lazy branches, that can also be handled simply by let/defer:

// Test that the unselected branch does not get evaluated:
template<typename T>
using test_lazy_if_ =
   let<lazy::if_<std::is_void<T>, T, defer<std::pair, T> > >;
static_assert(std::is_same<test_lazy_if_<void>, void>::value, "");

Obviously, std::pair can't be instantiated with only one argument. It is
never tried since the condition is true and the branch is never taken.
The code compiles. (Short-circuiting in lambdas is a recent addition.)

FWIW, I find the MPL's lambda evaluator *extremely* confusing and
frustrating. That business of "after substitutions, test to see if
::type exists; if so that's the result ... but only if parameter
substitutions were made!" is just awful.

-- 
Eric Niebler
Boost.org
http://www.boost.org