Re: [boost] [mpl] multiset

Subject: Re: [boost] [mpl] multiset
From: Eric Niebler (eniebler_at_[hidden])
Date: 2015-03-10 18:37:28

On 3/10/2015 6:46 AM, Louis Dionne wrote:
> Eric Niebler <eniebler <at> boost.org> writes:
>> On 3/7/2015 6:41 AM, Louis Dionne wrote:
>> [...]
>>
>> 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
> 
> Lol, thanks. I've no such problems now with Hana (or I'm not aware of it).

It's possible that your "metafunction" variable template somehow doesn't
hit this problem. I confess I don't really understand core's problem
with template aliases here.

<snip>
>> 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).
> 
> Ok, I understand. It's mostly a philosophical difference, but one
> that's worth noting.

Not philosophical, since it changes how the library is used idiomatically.

<snip>
> Quick question; is the expression evaluator compile-time efficient?
> In my experience, such expression evaluators end up being expensive 
> at compile-time, especially if you sprinkle all your code with it.
> Of course, this _might_ only be relevant to hardcore computations,
> and in that case Hana will be slower anyway (with current compiler 
> technology) so I'm just saying you might want to benchmark it for 
> your own curiosity.

I haven't benchmarked it. It isn't free certainly, but I would expect it
to be cheaper than an MPL lambda invocation since it doesn't need to
keep track of whether/where substitutions were made or check for nested
::type aliases. And it is a cost that is paid only where laziness is
needed. If laziness is needed in a "hardcore computation", nothing is
preventing users from using the meta::lazy namespace as if it were
boost::mpl and dealing with nested ::type aliases.

I could make the expression evaluator faster by making placeholder types
special, but I've avoided doing that for now. I like the ability to
create named placeholders in-situ:

    lambda<class XYZ, lazy::eval<std::add_pointer<XYZ>>>;

<snip>
>> 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.
> 
> It's an interesting feature, but I think even better would be to 
> give people the choice whether they want SFINAE-friendliness or not.

They have the choice. They can move can-fail computations into
non-immediate contexts. In the common_type example, that would mean
changing:

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

to something like:

template<typename T, typename U>
struct builtin_common {
  using type = decltype(true? std::declval<T>() : std::declval<U>());
};
template<typename T, typename U>
using builtin_common_t = eval<builtin_common<T, U>>;

This technique can be made into a general utility like defer that turns
SFINAEs into hard errors. Might be useful for debugging.

> Anyway, implementing common_type turned out to be quite challenging
> until I realized I could use the Maybe Monad to encode SFINAE, and 
> then common_type was just a monadic fold with the Maybe Monad. Here
> you go:
> 
>     using namespace boost::hana;
> 
>     auto builtin_common_t = sfinae([](auto t, auto u) -> decltype(type<
>         std::decay_t<decltype(true ? traits::declval(t) : traits::declval(u))>
>     >) { return {}; });

This is the price of unifying MPL and Fusion.

>     template <typename ...T>
>     struct common_type { };
> 
>     template <typename T, typename U>
>     struct common_type<T, U>
>         : std::conditional_t<std::is_same<std::decay_t<T>, T>{} &&
>                              std::is_same<std::decay_t<U>, U>{},
>             decltype(builtin_common_t(type<T>, type<U>)),
>             common_type<std::decay_t<T>, std::decay_t<U>>
>         >
>     { };
> 
>     template <typename T1, typename ...Tn>
>     struct common_type<T1, Tn...>
>         : decltype(foldlM<Maybe>(tuple_t<Tn...>,
>                                  type<std::decay_t<T1>>,
>                                  sfinae(metafunction<common_type>)))
>     { };
> 
>     template <typename ...Ts>
>     using common_type_t = typename common_type<Ts...>::type;
> 
> 
>     // tests
>     static_assert(std::is_same<
>         common_type_t<char, short, char, short>, int>{}
>     , "");
> 
>     static_assert(std::is_same<
>         common_type_t<char, double, short, char, short, double>, double>{}
>     , "");
> 
>     static_assert(std::is_same<
>         common_type_t<char, short, float, short>, float
>     >{}, "");
> 
>     static_assert(
>         sfinae(metafunction<common_type>)(type<int>, type<int>, type<int*>) 
>             == nothing
>     , "");

<snip>

More or less the same as the Meta implementation aside from the
boxing/unboxing, which is distracting when doing a pure compile-time
computation, IMO. (I've also never been clear on Monadic folds, but
that's my thing.) The trade-off is that Hana is usable at runtime and
Meta is not. Fair 'nuf.

At least for light-to-medium metaprogramming, Meta or Hana serve.

Thanks,

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