Re: [boost] [mpl] multiset

Subject: Re: [boost] [mpl] multiset
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-03-07 09:41:02

Eric Niebler <eniebler <at> boost.org> writes:

>
> On 3/5/2015 4:52 AM, Louis Dionne wrote:
> > Eric Niebler <eniebler <at> boost.org> writes:
> >
> >>
> >> [...]
> >>
> >> [*] My GSoC idea: my Meta library is built around variadic parameter
> >> packs, aka lists, and I think I'm happy with that. But it has been
> >> suggested that it could be built instead around the Foldable concept.
> >> The project would be to redesign Meta around Foldable types, and add
> >> other "containers" to Meta besides lists, like sets, and have the
> >> algorithms work with anything that is Foldable.
> >
> > Thanks for the feedback, Eric. However, there's something that has been
> > tickling me for a while with Meta. I am seeing some kind of convergence
> > in Meta towards the MPL11, especially with the addition of the lazy
> > operations. If you go down the Foldable road, then you would end up
> > with something incredibly similar. The MPL11 does exactly that work
> > of splitting sequences into Foldable, Iterable and other similar concepts.
> > Frankly, my impression is that Meta is reinventing MPL11's wheel, and I
> > would like to know whether (1) I am wrong (2) this is done unconsciously
> > (3) this is done consciously because you think the MPL11 doesn't cut it.
> >
> > Of course, it is the possibility of (3) that has been tickling me .
>
> I found MPL11 and read some of its docs. Although there are many
> similarities (naturally, we're both influenced by the MPL), I think
> there is a fundamental difference. Meta isn't built around metafunctions
> as folks here know them. The Meta library is built around template
> aliases. The difference is illustrated in the way the quote feature is
> implemented in the two libraries.
>
> In MPL11, it's called "lift" and it looks like:
>
> template <template <typename ...> class f>
> struct lift {
>     template <typename ...xs>
>     struct apply
>         : f<xs...>
>     { };
> };
>
> Here, the assumption seems to be that "f" is a what you're calling a
> thunk or a boxed value; aka a metafunction. Something with a nested ::type.

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
        };

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.

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

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.

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

Regarding the usage of other concepts like Foldable, you say it 
was suggested that everything could be implemented around folds.
This is false in general, because stuff like `transform` require
a different structure than what is needed to be Foldable. However,
something can be said about the link between Foldable and an 
hypothetical Iterable concept (which would allow iteration over
a data structure one element at a time): In an eager context, both
do not coincide and you will need to introduce other concepts like 
Hana does (e.g. Iterable, Searchable) to be able to express most
operations on type lists. In a non-strict context, e.g. where you
can right-fold infinite data structures without crashing the 
compiler, I think both coincide but frankly one step is missing 
from my proof. Bottom line: while Foldable is a nice abstraction,
it does not encompass everything (far from that) and you would
need to introduce a bunch of other concepts to "conceptualize" 
everything. 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.

Louis