Re: [boost] [mpl] multiset

Subject: Re: [boost] [mpl] multiset
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-03-10 09:46:29

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).

 
> >> 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).

Ok, I understand. It's mostly a philosophical difference, but one
that's worth noting.

> >> 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.

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 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.)
> 
> [...]
> 
> 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.
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 {}; });

    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
    , "");

Of course, you can enable/disable SFINAE-friendliness just by using
a non-monadic fold and removing usages of `sfinae`:

    auto builtin_common_t = [](auto t, auto u) -> decltype(type<
        std::decay_t<decltype(true ? traits::declval(t) : traits::declval(u))>
    >) { return {}; };

    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(foldl(tuple_t<Tn...>,
                         type<std::decay_t<T1>>,
                         metafunction<common_type>))
    { };

I'll try to prepare another challenge soon, but time is missing today.

Regards,
Louis