Re: [boost] [Hana] Formal review for Hana

Subject: Re: [boost] [Hana] Formal review for Hana
From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2015-06-16 11:24:29

On Tue, Jun 16, 2015 at 9:35 AM, Louis Dionne <ldionne.2_at_[hidden]> wrote:

> Zach Laine <whatwasthataddress <at> gmail.com> writes:
>
> >
> > On Tue, Jun 16, 2015 at 8:04 AM, Louis Dionne <ldionne.2 <at> gmail.com>
> wrote:
> >
> > > [...]
> > >
> > > That is the incorrect workaround. The proper, Hana-idiomatic way to
> write
> > > what you need is:
> > >
> > >     namespace detail {
> > >         auto make_matrix_type = [](auto rows) {
> > >             auto nrows = hana::size(rows);
> > >             static_assert(nrows >= 1u,
> > >             "matrix_t<> requires at least one row");
> > >
> > >             auto ncolumns = hana::size(rows[hana::size_t<0>]);
> > >             auto uniform = hana::all_of(rows, [=](auto row) {
> > >                 return hana::size(row) == ncolumns;
> > >             });
> > >             static_assert(uniform,
> > >             "matrix_t<> requires tuples of uniform length");
> > >
> > >             using tuple_type = decltype(hana::flatten(rows));
> > >
> > >             return hana::type<matrix_t<tuple_type, nrows, ncolumns>>;
> > >         };
> > >     }
> > >
> > >     template <typename ...Rows>
> > >     using matrix = typename decltype(
> > >
>  detail::make_matrix_type(hana::make_tuple(std::declval<Rows>()...))
> > >     )::type;
> > >
> >
> > While that definitely works, it also definitely leaves me scratching my
> > head.  Why doesn't
> >
> > static const std::size_t columns = hana::size(HeadRow{});
> >
> > Work in the code above, especially since
> >
> > auto ncolumns = hana::size(rows[hana::size_t<0>]);
> >
> > does?  That seems at least a little obscure as an interface.
>
> Notice that
>
>     static const std::size_t columns = hana::size(HeadRow{});
>
> requires the `hana::size(HeadRow{})` expression to be a constant
> expression.
> This requires HeadRow to be both default-constructible and a literal type.
> On the other hand,

Right. I do understand that; I noted this in the original comment in my
review.

    auto ncolumns = hana::size(rows[hana::size_t<0>]);
>
> just defines a (non-constexpr) variable inside a lambda. It also does not
> require anything about the constructibility of `HeadRow`. note that I could
> have written the above Hana-metafunction as follows:
>
>     auto make_matrix_type = [](auto head_row, auto ...tail_rows) {
>         auto nrows = hana::size_t<sizeof...(tail_rows) + 1>;
>         static_assert(nrows >= 1u,
>         "matrix_t<> requires at least one row");
>
>         auto ncolumns = hana::size(head_row);
>
>         auto rows = hana::make_tuple(head_row, tail_rows...);
>         auto uniform = hana::all_of(rows, [=](auto row) {
>             return hana::size(row) == ncolumns;
>         });
>         static_assert(uniform,
>         "matrix_t<> requires tuples of uniform length");
>
>         using tuple_type = decltype(hana::flatten(rows));
>
>         return hana::type<matrix_t<tuple_type, nrows, ncolumns>>;
>     };
>
> which is closer to your initial implementation. Now, it is obvious that
>
>     auto ncolumns = hana::size(head_row);
>
> should work, right?

I also understand why this works.

I do *not* understand why this did not work for me, since it seems to be
exactly what the code in your PR does:

static const std::size_t columns = hana::size(std::declval<HeadRow>());

> > I also could not get hana::size(hana::type<HeadRow>); to work, btw.
>
> `hana::size` is a function from the Foldable concept. `hana::type<...>`
> represents a C++ type. Since a C++ type is not Foldable (that wouldn't
> make any sense), you can't call `hana::size` on a `hana::type<...>`.
>
> To understand why what you're asking for can't be done without breaking the
> conceptual integrity of Hana, consider what would happen if I defined
> `std::vector<>` as a Foldable. Obviously, the following can't be made
> to work:
>
>     hana::size(hana::type<std::vector<int>>)
>
> Hana works with objects, and the `hana::type<>` wrapper is there to allow
> us
> to represent __actual C++ types__ as objects, for the purpose of calling
> type traits on them, essentially. The idiomatic Hana-way to do what you're
> trying to achieve is to consider your matrix rows as objects, which they
> are,
> instead of types.
>

Right.  I should have been more clear.  The use of type<...> was a
suggestion for a workaround interface for non-literal types that I was
suggesting.  I shouldn't have conflated the two threads of discussion.  I
made that suggestion because I tried both of these:

// Does not work; not a literal type
static const std::size_t columns = hana::size(HeadRow{});

// Does not work for as-yet-mysterious-to-me reasons
static const std::size_t columns = hana::size(std::declval<HeadRow>());

... and was looking for a way to get a "fake" object of type HeadRow to
pass to hana::size().

> [...]
> >
> > > > That being said, I really, really, want to do this:
> > > >
> > > > tuple_1 foo;
> > > > tuple_2 bar;
> > > >
> > > > boost::hana::copy_if(foo, bar, [](auto && x) { return
> my_predicate(x);
> > > });
> > > >
> > > > Currently, I cannot.  IIUC, I must do:
> > > >
> > > > tuple_1 foo;
> > > > auto bar = boost::hana::take_if(foo, [](auto && x) { return
> > > > my_predicate(x); });
> > > >
> > > > Which does O(N^2) copies, where N = boost::hana::size(bar), as it is
> > > > pure-functional.  Unless the optimizer is brilliant (and it
> typically is
> > > > not), I cannot use code like this in a hot section of code.  Also,
> IIUC
> > > > take_if() cannot accommodate the case that decltype(foo) !=
> decltype(bar)
> > >
> > > I don't understand; take_if() is not an algorithm provided by Hana.
> > >
> >
> > Right!  I meant filter().  Sorry.
>
> No problem. Now I understand better. So basically you want to write
>
>     tuple_1 foo;
>     auto bar = boost::hana::filter(foo, my_predicate);
>
> I don't understand why that's O(N^2) copies. That should really be N
> copies,
> where `N = hana::size(bar)`. As a bonus, if you don't need `foo` around
> anymore, you can just write
>
>     tuple_1 foo;
>     auto bar = boost::hana::filter(std::move(foo), my_predicate);
>
> and now you get N moves, not even N copies.
>

That's good to know.  I was concerned that the pure functional
implementation would internally produce intermediate values of size 1, 2,
3, ... N.  This is often the case in pure functional implementations.  Even
so, it returns a temporary that must then be copied/moved again into bar.
That means I'm doing 2*N copies/moves instead of N.  That implies that I
still cannot use filter() in hot code.  (I know that above bar is
initialized with the result of filter(), but in many cases, the result will
be assigned to an existing value, and the final copy is not guaranteed to
be elided.  In much of my code, I need that guarantee, or a way to fall
back to direct assignment where the elision does not occur.)

> > [...]
> >
> > > Since Hana expects
> > > functions to be pure in general and assignment is a side effect, this
> > > cannot
> > > be achieved with a normal algorithm. However, Hana provides some
> algorithms
> > > that alow side-effects. One of them is for_each, and the other is
> `.times`
> > > (from IntegralConstant). I suggest you could write the following:
> > >
> > >     hana::size(foo).times.with_index([&](auto i) {
> > >         using T = std::remove_reference_t<decltype(bar[i])>;
> > >         bar[i] = static_cast<T>(foo[i]);
> > >     });
> > >
> >
> > Ok.  You also had this in the PR you made for Units-BLAS:
> >
> > hana::size(xs).times.with_index([&](auto i) {
> >     xs[i] = ys[i];
> > });
> >
> > ... which is even simpler.  However, either is a pretty awkward way to
> > express an operation that I think will be quite often desired.  copy(),
> > copy_if(), move(), and move_if() should be first-order operations.  I
> also
> > want the functional algorithms, but sometimes I simply cannot use
> them....
>
> First, assignment to tuples will be fixed and I consider it a bug right
> now.
> However,
>
> copy:
>     auto tuple1 = hana::make_tuple(...);
>     auto tuple2 = tuple1;
>
> copy_if:
>     auto tuple1 = hana::make_tuple(...);
>     auto tuple2 = hana::filter(tuple1, predicate);
>
> move:
>     auto tuple1 = hana::make_tuple(...);
>     auto tuple2 = std::move(tuple1);
>
> move_if:
>     auto tuple1 = hana::make_tuple(...);
>     auto tuple2 = hana::filter(std::move(tuple1), predicate);
>
> Does that solve your problem, or am I misunderstanding it?

That all works fine, but I actually need assignment across tuple types that
are different, but have compatible elements:

hana::_tuple<A, B> x = ...;
hana::_tuple<C, D> y = ...;

// some stuff happens ...

// This should compile iff std::is_same<A, C>::value && std::is_same<B,
D>::value
x = y;

// But this should work as long as a C is assignable to an A and a D is
assignable to a B:
hana::copy(x, y);

> > Now where's my pony?
>
> Here :-) http://goo.gl/JNq0Ve

That's a pretty pony.

Zach