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

Subject: Re: [boost] [Hana] Formal review for Hana
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2015-06-16 09:04:39

Zach Laine <whatwasthataddress <at> gmail.com> writes:

> [...]
>
> There are some things that I consider worth changing, however:
>
> - The use of '.' in names instead of '_' (Louis has already said that he
>   will change this).

Yes, I'm currently changing this. You can refer to [1].

> - The inclusion of multiple functions that do the same thing.  Synonyms such
>   as size()/length() and fold()/fold.left() sow confusion.  As a maintainer
>   of code that uses Hana, it means I have to intermittently stop and refer
>   back to the docs.  Hana is already quite large, and there's a lot there
>   to try to understand!

The synonyms were added as a balm in the few cases where there was a rather
strong disagreement on what I wanted and what other people wanted. Perhaps
I should have held my position harder, or I should have done the contrary.
If the aliases seem to annoy a significant number of persons, I'll consider
removing them (and keeping IDK which one yet).

> [...]
>
> - I'd like to see first() / last() / after_first() / before_last() instead
>  of head() / last() / tail() / init() (this was suggested by Louis offline),
>   as it reinforces the relationships in the names.

Actually, I thought we had agreed on front/back drop_front/drop_back :-).
Anyway, this is tracked by this issue [2]. It's not a 100% trivial change
because that will mean that `drop` is replaced by `drop_front`, which can
also take an optional number of elements to drop. Same goes for `drop_back`,
which will accept an optional number of elements to drop from the end of the
sequence.

> - I find boost::hana::make<boost::hana::Tuple>(...) to be clunkier than
>   boost::hana::_tuple<>, in many places.

You can use boost::hana::make_tuple(...).

>   Since I want to write this in some cases, it would be nice if it was
>   called boost::hana::tuple<> instead, so it doesn't look like I'm using
>   some implementation-detail type.

Right; since `_tuple<...>` is a well specified type, I guess it could have
a proper name without a leading underscore. More generally, I have to clean
up some names I use. For example, you can create a Range with

    - boost::hana::make_range(...)
    - boost::hana::make<boost::hana::Range>(...)
    - boost::hana::range(...)
    - boost::hana::range_c<...>

And the type of any of these objects is called _range<...>, although it is
implementation-defined. I opened this issue [3] to track this cleanup process.

>   * Implementation
>
> Very good; mind-bending in some of the implementation details.  However,
> there are some choices that Louis made that I think should be changed:
>
> - The inclusion of standard headers was forgone in an effort to optimize
>   compile times further (Hana builds quickly, but including e.g.
>   <type_traits> increases the include time of hana.hpp by factors).
>   This is probably not significant in most users' use of Hana; most users
>   will include Hana once and then instantiate, instantiate, instantiate.
>   The header-inclusion time is just noise in most cases, and is quite fast
>   enough in others.  However, rolling one's own std::foo, where std::foo is
>   likely to evolve over time, is asking for subtle differences to creep in,
>   in what users expect std::foo to do vs. what hana::detail::std::foo does.
>   What happens if I use std::foo in some Hana-using code that uses
>   hana::detail::std::foo internally? Probably, subtle problems.  Moreover,
>   this practice introduces an unnecessary maintenance burden on Hana to
>   follow these (albeit slowly) moving targets.

The current develop branch now uses `<type_traits>` and other standard
headers. I am glad I have finally made the move, since this was also
preventing me from properly interoperating with `std::integral_constant`
and other quirks. All for the better!

> - I ran in to a significant problem in one case that suggests a general
>   problem.
>
>   In the linear algebra library I partially reimplemented, one declares
>   matrices like this (here, I use the post-conversion Hana tuples):
>
>   matrix<
>       hana::tuple<a, b>,
>       hana::tuple<c, d>
>   > m;
>
>   Each row is a tuple.  But the storage needs to be a single tuple, so
>   matrix<> is actually a template alias for:
>
>   template <typename Tuple, std::size_t Rows, std::size_t Columns>
>   matrix_t { /* ... */ };
>
>   There's a metafunction that maps from the declaration syntax to the
>   correct representational type:
>
>   template <typename HeadRow, typename ...TailRows>
>   struct matrix_type
>   {
>       static const std::size_t rows = sizeof...(TailRows) + 1;
>       static const std::size_t columns = hana::size(HeadRow{});
>
>       /* ... */
>
>       using tuple = decltype(hana::flatten(
>           hana::make<hana::Tuple>(
>               HeadRow{},
>               TailRows{}...
>           )
>       ));
>
>       using type = matrix_t<tuple, rows, columns>;
>   };
>
>   The problem with the code above, is that it works with a HeadRow tuple
>   type that is a literal type (e.g. a tuple<float, double>).  It does not
>   work with a tuple containing non-literal types (e.g. a
>   tuple<boost::units::quantity<boost::units::si::time>, /* ... */>).
>
>   This is a problem for me.  Why should the literalness of the types
>   contained in the tuple determine whether I can know its size at compile
>   time?  I'd like to be able to write this as a workaround:
>
>   static const std::size_t columns = hana::size(hana::type<HeadRow>);

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;

By the way, see my pull request at [4]. I'm now passing all the tests, and
with a compilation time speedup!

>   I'd also like Hana to know that when it sees a type<> object, that is
>   should handle it specially and do the right thing.  There may be other
>   compile-time-value-returning algorithms that would benefit from a similar
>   treatment.  I was unable to sketch in a solution to this, because
>   hana::_type is implemented in such a way as to prevent deduction on its
>   nested type (the nested type is actually hana::_type::_::type, not
>   hana::_type::type -- surely to prevent problems elsewhere in the
>   implementation).

This is done to prevent ADL to cause the instantiation of `T` in `_type<T>`.
For this, `decltype(type<T>)` has to be a dependent type in which `T` does
not appear.

>   As an aside, note that I was forced to name this nested '_' type
>   elsewhere in a predicate.  This is not something I want my junior
>   coworkers to have to read:
>
>   template <typename T>
>   constexpr bool some_predicate (hana::_type<T> x)
>   { return hana::_type<T>::_::type::size == some_constant;}

You made your life harder than it needed to be. First, you should have
written

    `decltype(hana::type<T>)::type::size`

instead of

    `hana::_type<T>::_::type`

This `_` nested type is an implementation detail. But then, you realize that
this is actually equivalent to `T::size`. Indeed, `decltype(type<T>)::type`
is just `T`. So basically, what you wanted is

    template <typename T>
    constexpr bool some_predicate (hana::_type<T> x)
    { return T::size == some_constant;}

which looks digestible junior coworkers :-).

>   Anyway, after trying several different ways to overcome this, I punted on
>   using hana::size() at all, and resorted to:
>
>   static const std::size_t columns = HeadRow::size;
>
>   ... which precludes the use of std::tuple or my_arbitrary_tuple_type with
>   my matrix type in future.

I think my workaround should make this OK.

> - I got this error:
>
>   error: object of type 'boost::hana::_tuple<float, float, float, float>'
>   cannot be assigned because its copy assignment operator is implicitly
>   deleted

This is a known problem, tracked by this issue [5].

>   This seems to result from the definitions of hana::_tuple and
>   hana::detail::closure.  Specifically, the use of the defaulted special
>   member functions did not work, given that closure's ctor is declared like
>   this:
>
>   constexpr closure_impl(Ys&& ...y)
>       : Xs{static_cast<Ys&&>(y)}...
>   { }
>
>   The implication is that if I construct a tuple from rvalues, I get a
>   tuple<T&&, U&&, ...>.  The fact that the special members are defaulted is
>   not helpful, since they are still implicitly deleted if they cannot be
>   generated (e.g. the copy ctor, when the members are rvalue refs).  I
>   locally removed all the defaulted members from _tuple and closure, added
>   to closure a defined default ctor, and changed its existing ctor to this:
>
>   constexpr closure_impl(Ys&& ...y)
>       : Xs{::std::forward<Ys>(y)}...
>   { }
>
>   ... and I stopped having problems.  My change might not have been entirely
>   necessary (I think that the static_cast<> might be ok to leave in there),

Actually, `std::forward<Y>(y)` is equivalent to `static_cast<Y&&>(y)`. I'm
using the latter because I measured a compile-time speedup of about 13.9%
when removing it. This is because Hana uses perfect forwarding quite a bit,
and that was the cost of instantiating `std::forward` (lol).

So the only thing you changed really is to remove all the defaulted members.

>   but something needs to change, and I think tests need to be added to cover
>   copies, assignment, moves, etc., of tuples with different types of values
>   and r/lvalues.

That is true. Added this issue [6].

>   * Documentation
>
> Again, this is overall very good.  Some suggestions:
>
> - Make a cheatsheet for the data types, just like the ones for the
>   algorithms.

Great idea. See this issue [7].

> - Do the same thing for the functions that are currently left out (Is this
>   because they are not algorithms per se?).  E.g. I used
>   hana::repeat<hana::Tuple>(), but it took some finding.

I only put the __most__ useful algorithms in the cheatsheet, to avoid
crowding it too much. I can add some more.

>   * Tests
>
> - The tests seem quite extensive.
>
>   * Usefulness
>
> Extremely useful.  I find Hana to be a faster, *much* easier-to-use MPL, and
> an easier-to-use Fusion, if only because it shares the same interface as the
> MPL-equivalent part.  There are other things in there I haven't used quite
> yet that are promising as well.  A lot of the stuff in Hana feels like a
> solution in search of a problem -- but that may just be my ignorance of
> Haskell-style programming.  I look forward to one day understanding what
> I'd use hana::duplicate() for, and using it for that. :)

Lol. The Comonad concept (where duplicate() comes from) is more like an
experimental to formalize Laziness. See my blog post about this [8].

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

> What I ended up doing was this:
>
> hana::for_each(
>     hana::range_c<std::size_t, 0, hana::size(foo)>,
>     [&](auto i) {
>         hana::at(bar, i) =
>             static_cast<std::remove_reference_t<decltype(hana::at(bar,
> i))>>(
>                 hana::at(foo, i)
>             );
>     }
> );
>
> ... which is a little unsatisfying.
>
> I also want move_if().  And a pony.

Oh, so you're trying to do an element-wise assignment? 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]);
    });

> - Did you attempt to use the library? If so:
>   * Which compiler(s)
>
> Clang 3.6.1, on both Mac and Linux.  My code did actually compile (though
> did not link due to the already-known bug) on GCC 5.1.

Cool!

>   * What was the experience? Any problems?
>
> I had to add "-lc++abi" to the CMake build to fix the link on Linux, but
> otherwise no problems.

That is curious, because the Travis build is on linux and does not need that.
Did you set the path to your libc++ installation on Linux? The README states
that you should use

    -DLIBCXX_ROOT=/path/to/libc++

when generating the CMake build system. If it does not work as expected,
I'll open up an issue because I really want to track down these problems,
which make the library more painful to tryout.

Thanks for the review, Zach. I also appreciate all the comments you provided
privately; they were super useful. And you were right about the dots in the
names; I should have changed them before the review. :-)

Regards,
Louis

[1]: https://github.com/ldionne/hana/issues/114
[2]: https://github.com/ldionne/hana/issues/66
[3]: https://github.com/ldionne/hana/issues/122
[4]: https://github.com/tzlaine/Units-BLAS/pull/1
[5]: https://github.com/ldionne/hana/issues/93
[6]: https://github.com/ldionne/hana/issues/123
[7]: https://github.com/ldionne/hana/issues/124
[8]: http://ldionne.com/2015/03/16/laziness-as-a-comonad/