Re: [boost] [GSoC] [Boost.Hana] Formal review request

Subject: Re: [boost] [GSoC] [Boost.Hana] Formal review request
From: Louis Dionne (ldionne.2_at_[hidden])
Date: 2014-07-30 17:39:02

pfultz2 <pfultz2 <at> yahoo.com> writes:

> 
> > That is slightly inacurate. I don't use iterators because other
> abstractions
> > provide much more expressiveness and are much more general than iterators.
> > Since performance is not an argument in favor of iterators in our case (as
> > you rightly observe), they are not used. The #1 reason is expressiveness.
> 
> I understand how it is simpler to define sequences using `head`/`tail`, but
> how is it more expressive?

Of course it's not more expressive in a formal way because you can achieve
the same things with both. I was speaking about the generality of Hana
type classes, e.g. instead of having iterator categories I have Functor, 
Foldable, Iterable and Traversable. These are more general concepts and
they can be used more widely than iterators. For example, Maybe is like a
compile-time std::optional. It is easy to make it a Functor, but it would
seem wrong to try and define an iterator over a Maybe. Not that it can't 
be done, just that it feels wrong.

> > Hana is fundamentally functional, it uses rather abstract concepts and
> > that's
> > what makes it so powerful. Truth is, "Sequence" and "Container" concepts
> > are
> > easy to understand but they only get you so far; they are not general
> > enough
> > to be used as building blocks. 
> 
> I believe Alex Stepanov would like to have a word with you ;)

I was speaking in the context of metaprogramming. Whether iterators are 
suited for this or that in another context is a different debate I'm 
neither qualified nor willing to have.

> > I did try using both.
> 
> What limitiation did you run into seperating "Sequences" and "Algorithms"?

I said Sequences and Containers, not Sequences and Algorithms. Splitting
sequences and algorithms is fine, and that's what's done in Hana. Related
algorithms are bundled into type classes and sequences (or more generally
data types) must define a fixed set of primitives to be usable with those
algorithms.

When I first started working on the MPL11, I took all the concepts from
the MPL and tried to split it so it would work without iterators. That's
when I ran into problems. I don't remember the specifics because that was
a while ago, but I could look into my old notes if you really want details.

> [...]
> 
> Yet it uses a lot of foreign functional concepts. Despite what google says,
> boost libraries are built around mostly C++-like 'interfaces'. I don't think
> its bad to introduce some functional-interfaces, but I know in the past
> libraies that libraries that were very functional were rejected from boost,
> because many people didn't grasp the purpose of them. So introducing a lot
> of functional interfaces on the surface of a library can hinder its adoption.

That is sad, because the functional concepts are exactly what makes Hana so 
powerful. Some problems are well suited for functional programming, and some
are not. Metaprogramming is __inherently__ functional, and it's about time
people embrace it.

> Also, the uses concepts that have a default methods are not very common. In
> general, a C++ concept defines a core set of functionality that can be used
> to extend a library.
> 
> > > Ideally, it would be nice to start with simple concepts, such as
> > iteration,
> > > and then have algorithms built on top of that.
> > 
> > I'm not sure what you mean by that. Do you mean change the structure of
> > type classes, or how they are introduced?
> 
> Yes, change the structure of the typeclasses. For example, `Iterable` has
> `for_each` included(which is defaulted). However, you could seperate
> `for_each` out as an algorithm that requires an `Iterable`. Then have a
> seperate mechanism to override the algorithms, such as for varidiac
> templates:
> 
>     template<template<class...> class Sequence, class... Ts>
>     struct algorithm<for_each, Sequence<Ts...>>
>     {
>         template<class F>
>         static void call(Sequence<Ts...> & s, F f)
>         {
>             ...
>         }
>     };
> 
> The same can be done for the accessors as well in the `Iterable` typeclass.

I could rip out all methods except their minimal complete definition from 
every type class, and have those other methods be "algorithms that require 
instances of the type class". However, you can now only have a single minimal 
complete definition for each type class, which is less flexible. Let's pretend 
that you can somehow have multiple MCDs. Now, the default definition of the 
algorithms that were ripped out can't depend on that MCD, because they are out 
of the type class. That's another loss of flexibility. All in all, I see no 
gains and only losses in ripping out methods from the type classes. 

You seem to be asking for flexibility. I designed every single bit of the type
class dispatching system so 
  1. Every single algorithm can be overriden provided you instantiate the 
     type class.
  2. You always get the maximum number of algorithms for as few definitions 
     as possible.
  3. You do not _ever_ have to duplicate the definition of an algorithm.
  4. Depending on the basis operations you provide when instantiating a
     type class, it is possible that the defaults will be more or less
     performant.

If you can explain to me what your proposal allows that can't be done 
right now, I'm open for discussion. That being said, and based on your
specific example for variadic templates, I think you're wondering why
there are no efficient operations for variadic sequences. It's because
I haven't had the time to add it, but here's what's planned:

    // Minimal complete definition: unpack
    struct Foldable::unpack_mcd {
        // Now, I can implement foldr, foldl, sum and whatnot _super_ 
        // efficiently, and any sequence-like thing that can unpack its 
        // content into a variadic function is qualified to get it.
    };

> > There are two things here. First, the decision not to split the library
> > into
> > a thousand headers was considered a feature, because it meant that you did
> > not need to include countless headers to get some functionality. Since the
> > library is very lightweight, it does not cause a compile-time performance
> > problem to include the whole list.hpp header.
> 
> Even so, in your implementation of list.hpp, it may not be performance hit
> to include it together, but perhaps as a user, I could be adapting a type 
> where each of those methods are heavyweight, so I would want to seperate 
> them out into seperate headers.

Ahhh, now I understand what you mean. I think that's possible and I'll 
reply when I'm fixed. Basically, I'll try to split the adaptor for Fusion
into separate header and see if it works.

> > Second, I agree that the List type class is heavy, but that's because it's
> > more like a data type really. The only reason I made it a type class is
> > because I wanted to give `fusion::vector`, `std::tuple` and friends the
> > same
> > methods as `hana::list`, for free. The laws of List force every instance
> > to
> > be isomorphic to `hana::list`, so there is no reason why you would want to
> > instantiate it.
> 
> Just as non-member functions are preferred when they only access public
> members, I believe this same advice can be applied here. Each method that
> has a default implementation could be made as a seperate function(which 
> could be designed to be overloaded as well).

I really don't think the same advice can be applied here, and I don't see
why it should. Type classes and regular structs are conceptually very
different entities, even if they are implemented in the same way.

Louis