Peter Dimov writes:

Glen Fernandes wrote:

...

[1] A note for Windows users: As mentioned, Hana requires a C++14 conforming compiler. If you would like to try it, a VM with Linux and clang 3.5 is a fairly painless option.

The current Cygwin has clang 3.5.1 and g++ 4.9.2, both of which are C++14 (enough for practical use.)

Clang 3.5.1 should be fine. However, GCC 4.9.2 is unfortunately missing variable templates, which are an important feature used in Hana. No version of GCC currently compiles Hana, although we're almost there. A port to GCC is currently on its way, but I am waiting for the GCC team to fix a bug [1] which causes constexpr variable templates to produce link errors. If the GCC team is responsive enough, Hana should be fully functional with GCC 5.2. Louis [1]: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65719

On Fri, Jun 5, 2015 at 4:33 PM, Louis Dionne wrote:

Paul Fultz II writes:

...

Do you mean Wed June 10th or Monday June 8th?

The review was scheduled from June 10 to June 24, so I am fairly sure Glen meant Wednesday June 10.

Yes. Sent a follow up e-mail correcting "Monday" to "Wednesday". :-) Glen

...

Dear Boost community,

The formal review of Louis Dionne's Hana library starts Monday, 10th June

Is there any rationale for the choice of name? Hana is simultaneously a rare word and also (I think) a registered trademark of the technology company SAP. SAP Hana is a database so there is little scope for confusion between it and Boost.Hana amongst tech professionals but from the outside world I'm not so sure...

...

Is there any rationale for the choice of name? Hana is simultaneously a rare word and also (I think) a registered trademark of the technology company SAP.

SAP Hana is a database so there is little scope for confusion between it and Boost.Hana amongst tech professionals but from the outside world I'm not so sure...

Here:

http://ldionne.com/hana/index.html#tutorial-rationales-why_Hana

it says:

I just needed a short and good looking name that people would easily remember, and Hana came up.

Thanks for the link Larry. That reasoning reads rather awkwardly when SAP's Hana pre-dates Louis's library and is trademarked (albeit only in the context "SAP Hana"??) But IANAL, it is up to Louis to decide whether there is a real issue to address here.

On 9 June 2015 at 15:20, Louis Dionne wrote:

What's trademarked is "SAP Hana", not "Hana" itself.

Be aware that SAP is currently in the process of applying for the community trademark “Hana” (by itself) too, application number 013285382 (search by application number at https://www.tmdn.org/tmview/welcome ), including in class 9 amongst others. It feels to me as if at least contacting SAP to ask for something written down which gives you / us / Boost the right to use “Boost Hana” for this project might be a good idea … either that or changing the name at this relatively early stage rather than risking being forced to later if things went sour! I've had no chance to read beyond the first few paragraphs of the documentation yet but so far it's giving me a very warm feeling, looks like great work, well done, … I'm a user of a few libraries which use TMP in their implementation, but have never written much beyond very small toy experimental projects of my own in this area. Nevertheless I hope to have a chance to get a bit further in before end of review period but it's looking unlikely :/ -- Bill Gallafent.

-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Larry Evans Sent: 09 June 2015 10:53 To: boost@lists.boost.org Subject: Re: [boost] [Boost] [Hana] the name

On 06/09/2015 03:47 AM, Pete Bartlett wrote:

...

...

...

Dear Boost community,

The formal review of Louis Dionne's Hana library starts Monday, 10th June

Is there any rationale for the choice of name? Hana is simultaneously a rare word and also (I

think) a

registered trademark of the technology company SAP.

...

SAP Hana is a database so there is little scope for confusion between it and Boost.Hana amongst

tech professionals but from the outside world I'm not so sure...

...

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Here:

http://ldionne.com/hana/index.html#tutorial-rationales-why_Hana

it says:

I just needed a short and good looking name that people would easily remember, and Hana came up.

I understand that Louis is in love with the name of his (very nice) baby, but I think it is a very bad idea for a Boost library for the simple reason that it gives no clue whatever about what it is or does. Paul PS At the very least, would it be wise to ask SAP if they mind? --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830

Oleg Grunin writes:

Glen Fernandes writes:

...

Dear Boost community,

The formal review of Louis Dionne's Hana library starts Monday, 10th June and ends on 24th June.

After playing for a few of hours with Hana I take my hat off to Louis for the impressive feat he accomplished with the library and the excellent documentation. MPL unlocked a whole new world of C++ programming that few, at the time, suspected existed. I can only hope that Hana will do the same. But I am not yet certain of it. Maybe it is due to the heavy paradigm shift which I haven't yet made. In MPL and Fusion there was a clear distinction between the compile and run-time worlds (In the former pretty much everything, save for_each, was compile-time, and in latter all the compile time stuff lived in result_of namespace ). With Hana that line is fuzzy. I understand that Louis considers it its big achievement and it may be so but I am not yet convinced. To me type manipulations (metaprogramming) were always something that went on between the programmer and the compiler and were entirely gone from the resulting binary.

They should be entirely gone from the resulting binary, and this is the case with basically everything I've tried so far. The optimizer has all the necessary information to remove this code entirely. The example you are presenting is worthy of filing a bug against Clang, which I will do once I'm done reducing the test case. See below for details.

Here is a small example that uses an mpl type map and the corresponding code I put together (likely sub-optimally) using hana:

[...]

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers. Here's the version I would have written: #include #include #include using namespace boost::hana; static constexpr int map_size = 100; void run() { constexpr auto hana_range = range(int_<0>, int_); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t...>; }); auto Array = hana_tuple[int_<69>]; // instantiate the array constexpr decltype(Array)::type arr = {{0}}; static_assert(sizeof(arr) == 69, ""); } However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

Despite Louis's claims of a significant compile-time speed up with Hana, I get the following with clang 3.6.0:

$time clang++ -O3 -D_USE_HANA -stdlib=libc++ -std=c++14 hana.cpp -o hana real 0m55.233s user 0m54.190s sys 0m0.631s

$time clang++ -O3 -stdlib=libc++ -std=c++14 hana.cpp -o mpl real 0m2.162s user 0m1.632s sys 0m0.108s

There are several reasons for the above timings. In order of importance: 1. Map and Set (the associative containers) are naively implemented right now. Optimizing and improving those data structures is the subject of my GSoC project of this summer, which I will focus on more seriously after the review (which is time consuming). I am aware of several possible optimizations that can be applied to heterogeneous associative structures, some of which would make your use case much more efficient. As you may have noticed, I never actually show benchmarks for associative data structures in the tutorial, but only for Tuple, because I know the performance of the associative containers to be bad (but not as bad as you shown, frankly). The compile-time performance claims made in the tutorial may be a bit bold for the time being, so I added a note about the associative data structures until they are optimized. 2. I think the compiler is incorrectly losing time for generating and optimizing code that should not be in the executable at all. Like I said, I consider such bad codegen to be a compiler bug. 3. You're using the wrong data structure for the task. This should have some impact on the performance, but never as much as here. I've reimplemented your example in several different ways. You can find the full code in the Gist at [1]. Here is a chart showing the compilation time of the different solutions as a function of the number of `std::array`s in the container: http://i.imgur.com/gVDA632.png As you can see, the implementations using Map + insert are really bad, but the others are all OK. Also note how using decltype with Map + insert cuts down the compilation time, which supports point (2) above.

And at run-time: (run a loop of 10000)

$ time ./hana 100000 real 0m2.834s user 0m2.825s sys 0m0.006s

$ time ./mpl 100000 real 0m0.021s user 0m0.002s sys 0m0.001s

Which clearly shows that the stuff intended to be purely compile-time has leaked into the run-time.

There are several reasons for the above timings. In order of importance (I think): 1. Clang generates horrible code for your example. I think the fault is principally on the compiler, since it generates perfect code for up to ~20 elements, and then starts emitting complete crap. I'll follow up with the Clang team about this. 2. The fault is also partially on the library, which does not compress the storage of empty types right now. Hence, your compile-time map, which contains (int_<...>, type<...>) pairs, actually has a huge sizeof, whereas it should have sizeof(char) since all those pairs are empty. Indeed, I was able to make the runtime performance issue go away by compressing the storage of empty types in Hana pairs. I opened an issue [2] to track the progress of this feature. By the way, I consider this a high priority feature. Here is a chart showing the execution time for the examples in the Gist: http://i.imgur.com/CWUoDtB.png Here is a chart showing the executable size for the examples in the Gist: http://i.imgur.com/uCThWXb.png As you can see, only your original Map example is bad, and it starts sudenly at about 30 elements, which reinforces my thinking that it's a compiler bug or quality of implementation issue. As you can see, my version using Hana Tuple is indeed 0 overhead, just like the MPL. I am confident that compressing empty types and making the Map implementation more clever should resolve the issue you presented.

Also it appears that Hana lets the compiler swallow all kinds of code that doesn't appear to have any practical meaning:

I understand (maybe erroneously) that a hana::map can have a useful application only if its keys are compile-time constructs, and yet I was able to compile: make_map(make_pair(1, "one"), make_pair(2, "two"));

You are correct when you state that Hana Maps require the keys to be comparable at compile-time, i.e. the comparison of two keys must return an IntegralConstant. The above usage, which is generally meaningless, is impossible to catch at compile-time in general, because the type of the object returned by the comparison of 1 with something else may depend on that something else. In other words, we can only flag the above usage if there exists no 'x' (of any type) such that '1 == x' returns an IntegralConstant. However there is no way to assess that in general. However, if you tried to access an element of your map, then you would see a compile-time failure: auto map = make_map(make_pair(1, "one"), make_pair(2, "two")); std::string one = map[1]; // error: error: static_assert failed "hana::value<T>() requires T to be a Constant" static_assert(_models{}, ^ ~~~~~~~~~~~~~~~~~~~~~~ note: in instantiation of function template specialization 'boost::hana::value<bool>' requested here hana::if_(hana::value

and even make_map(1,2,3);

This one is easy to catch, because make_map requires Products as arguments. This was fixed and you should now get the following pretty compile-time error: error: static_assert failed "hana::make<Map>(pairs...) requires all the 'pairs' to be Products" static_assert(hana::all(are_pairs), ^ ~~~~~~~~~~~~~~~~~~~~ note: in instantiation of function template specialization 'hana::make_impl::apply' requested here return make_impl<Datatype>::apply(static_cast(x)...); ^ note: in instantiation of function template specialization 'hana::_makehana::Map::operator()' requested here auto map = make_map(1,2,3); ^ Thanks a lot for trying the library out and providing feedback. One thing Hana sorely needs is to see more usage so that some non-obvious problems can come out and be addressed. Regards, Louis [1]: https://goo.gl/PdjhTb [2]: https://github.com/ldionne/hana/issues/89

Peter Dimov writes:

Louis Dionne wrote:

...

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers.

When testing Map's performance, it's a bit hard to come up with a sequence of keys that are not isomorphic to integers.

Note that I also wrote: However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

Oleg could in principle have used X but would that really have changed much?

No, that wouldn't have changed much. Regards, Louis

Oleg Grunin writes:

Louis Dionne writes:

...

...

[...]

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers. Here's the version I would have written:

#include #include #include using namespace boost::hana;

static constexpr int map_size = 100;

void run() { constexpr auto hana_range = range(int_<0>, int_); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t...>; });

auto Array = hana_tuple[int_<69>];

// instantiate the array constexpr decltype(Array)::type arr = {{0}}; static_assert(sizeof(arr) == 69, ""); }

However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

Indeed, I used a range just to compress the code. It could have been: typedef mpl::joint_view, mpl::range_c > mpl_range, which would likely not work with a tuple. Btw, I couldn't find a way to combine several ranges with hana.

I understand your reason for using a Map. You can't directly concatenate Ranges with Hana, but you can concatenate them if you put them into Tuples first, and what you get is a Tuple of IntegralConstants: constexpr auto xs = concat( to<Tuple>(range(int_<-10>, int_<0>)), to<Tuple>(range(int_<0>, int_<10>)) );

...

1. Clang generates horrible code for your example. I think the fault is principally on the compiler, since it generates perfect code for up to ~20 elements, and then starts emitting complete crap. I'll follow up with the Clang team about this.

I hope they'll take it up, since it's the only compiler capable of compiling this code.

I hope so too. I have reduced the problem to what I think is an inlining problem. This might be solved by a mixture of 1. Marking functions `inline` more aggressively by Hana and ensuring they have internal linkage so that they don't have to be emitted for nothing. 2. Compressing the storage of empty objects in Hana's containers. I have implemented this locally, and I can confirm it solves the runtime performance issue completely. The assembly generated by your original code and the MPL are now 100% identical. I'll push this to Hana's develop branch soon, but the patch still needs some work. 3. Having a better optimization of empty structures in Clang. For reference, the bug report I filed is at [1].

...

2. The fault is also partially on the library, which does not compress the storage of empty types right now. Hence, your compile-time map, which contains (int_<...>, type<...>) pairs, actually has a huge sizeof, whereas it should have sizeof(char) since all those pairs are empty.

Indeed, I was able to make the runtime performance issue go away by compressing the storage of empty types in Hana pairs. I opened an issue [2] to track the progress of this feature. By the way, I consider this a high priority feature.

[...] As you can see, only your original Map example is bad, and it starts sudenly at about 30 elements, which reinforces my thinking that it's a compiler bug or quality of implementation issue. As you can see, my version using Hana Tuple is indeed 0 overhead, just like the MPL. I am confident that compressing empty types and making the Map implementation more clever should resolve the issue you presented.

I wish there was a deterministic, language enforced way, to make sure that stuff intended to be compile-time stayed as such. Relying on an optimizer isn't all that comforting in this case. Although, it maybe that the lack of constexpr lambda's makes it impossible.

If constexpr lambdas were allowed, you could simply stick constexpr in front of it and you would indeed be guaranteed that it is evaluated at compile-time. Another way to go is to enclose the whole compile-time computation into decltype, like I did in the Gist I posted [2]: static constexpr int INPUT_SIZE = ...; static constexpr int INDEX = (INPUT_SIZE * 2) / 3; void run() { auto get_array = [](auto index) { auto inserter = [](auto map, auto n) { using Array = std::array; return insert(map, make_pair(n, type<Array>)); }; auto arrays = fold.left(range(int_<0>, int_), make_map(), inserter); return arrays[index]; }; constexpr decltype(get_array(int_<INDEX>))::type array{}; // ^^^^^^^^^ whole computation inside decltype static_assert(array.size() == INDEX, ""); } This ensures that the computation is done at compile-time, and the `get_array` function is never actually used. It is only used to force the compiler to perform a compile-time computation of the lambda's return type, which is what we're interested in. I find if slightly inconvenient to write everything like that, however.

...

...

Also it appears that Hana lets the compiler swallow all kinds of code that doesn't appear to have any practical meaning:

I understand (maybe erroneously) that a hana::map can have a useful application only if its keys are compile-time constructs, and yet I was able to compile: make_map(make_pair(1, "one"), make_pair(2, "two"));

You are correct when you state that Hana Maps require the keys to be comparable at compile-time, i.e. the comparison of two keys must return an IntegralConstant.

The above usage, which is generally meaningless, is impossible to catch at compile-time in general, because the type of the object returned by the comparison of 1 with something else may depend on that something else. In other words, we can only flag the above usage if there exists no 'x' (of any type) such that '1 == x' returns an IntegralConstant. However there is no way to assess that in general.

I am probably missing something, but can't you check that the first element of every pair going into the map is a compile-time constant.

No, because not only compile-time constants can be used as the keys of a Map. For example, you can use a Type to index a Map: auto map = make_map( make_pair(int_<1>, "1"s), make_pair(type<int>, "int"s) ); assert(map[int_<1>] == "1"s); assert(map[type<int>] == "int"s); More generally, anything that can be compared at compile-time can be used as a key in a Map. Hence, the following code is perfectly valid, even though the keys are not compile-time constants (in the usual sense): auto map = make_map( make_pair(tuple_t, "[int, char, float]"s), make_pair(make_tuple(type<int>, int_<2>), "[int, 2]"s) ); assert((map[tuple_t] == "[int, char, float]"s)); assert(map[make_tuple(type<int>, int_<2>)] == "[int, 2]"s);

Isn't (1 == anything) either a bool or a compile-time error, whereas int_<1> == anything is always a bool_<> or error?

For 1 == anything, you are right. Let's instead focus on the result of Hana's `equal` function, which performs a comparison on possibly heterogeneous values. `equal(1, anything)` is either a bool or an IntegralConstant. Roughly speaking, it is - a bool equivalent to `1 == anything` when 1 and `anything` are EqualityComparable, as the standard defines it. - the IntegralConstant false_ when 1 and `anything` are completely unrelated. Roughly speaking, they are unrelated when they don't have a common type. Heterogeneity makes things slightly more complex than they are in the usual world. If we did not return false_ for comparisons of unrelated objects, the following would trigger a compilation error because of the comparison between int and std::string: auto xs = make_tuple(1, 2, 3); auto c = contains(xs, std::string{"abcdef"}); Instead, in a heterogeneous setting, you probably want it to return false_. With Fusion/MPL, this is not a problem because they use `std::is_same` to perform comparisons. However, `std::is_same` performs a very shallow comparison and only allows comparing types. Instead, Hana uses a more general system which also allows comparing values, but we have to return false_ for unrelated objects, a bit like `std::is_same` returns `std::false_type` on unrelated types.

Thanks for your more than exhaustive reply.

Thanks for your challenging questions and observations. Regards, Louis [1]: https://llvm.org/bugs/show_bug.cgi?id=23818 [2]: https://goo.gl/TpxR7v

Joel de Guzman writes:

On 6/12/15 3:39 AM, Louis Dionne wrote:

...

Instead, in a heterogeneous setting, you probably want it to return false_. With Fusion/MPL, this is not a problem because they use `std::is_same` to perform comparisons. However, `std::is_same` performs a very shallow comparison and only allows comparing types. Instead, Hana uses a more general system which also allows comparing values, but we have to return false_ for unrelated objects, a bit like `std::is_same` returns `std::false_type` on unrelated types.

I might not be understanding this correctly, but Fusion == does not use std::is_same. It does value comparison much like tuples.

Joel, Indeed, my answer was not very clear. What I meant is that Fusion uses std::is_same for the fusion::{find, filter, remove, erase_key, ...} algorithms. In addition, Fusion defines the usual comparison operators for sequences (==, !=, ...), like you correctly pointed out. Instead, Hana uses the same comparison function (`equal`) for all these operations. However, for some algorithms, the comparison operator must return an IntegralConstant. Regards, Louis

Paul Fultz II writes:

...

...

I am probably missing something, but can't you check that the first element of every pair going into the map is a compile-time constant. « []

No, because not only compile-time constants can be used as the keys of a Map.

Yes, but as a simple smoke screen, you could always check that the key compared against itself will return an `IntregralConstant`. That should always be required to be valid, and it would help catch errors earlier on.

That's an interesting idea, and I just implemented this for both Set and Map. For illustration, here's what happens when 1. creating a Map with something else than pairs: auto m = make_map(1); error: static_assert failed "hana::make<Map>(pairs...) requires all the 'pairs' to be Products" static_assert(hana::all(are_pairs), ^ ~~~~~~~~~~~~~~~~~~~~ 2. creating a Map with non-Comparable keys: struct Foo { }; auto m = make_map(make_pair(Foo{}, "one")); error: static_assert failed "hana::make<Map>(pairs...) requires all the keys to be Comparable" static_assert(hana::all(are_Comparable), ^ ~~~~~~~~~~~~~~~~~~~~~~~~~ 3. creating a Map with keys that are obviously not Comparable at compile-time auto m = make_map(make_pair(1, "one")); error: static_assert failed "hana::make<Map>(pairs...) requires all the keys to be Comparable at compile-time" static_assert(hana::all(are_compile_time_Comparable), ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Similar error messages are thrown by Set when using non-Comparable or runtime-Comparable keys. Regards, Louis

Actually, I just realized something. While it is documented that Map and Set require compile-time Comparable keys, there are some operations that make sense to perform on Sets and Maps with runtime-Comparable keys.

Would this even give good performance? It seems there would need to be sorting or some form hashing for this to reasonable for runtime. Paul -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Hana-Announcing-Hana-s-formal-revie... Sent from the Boost - Dev mailing list archive at Nabble.com.

On 06/09/2015 11:00 AM, Louis Dionne wrote: [snip]

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers. Here's the version I would have written:

#include #include #include using namespace boost::hana;

static constexpr int map_size = 100;

void run() { constexpr auto hana_range = range(int_<0>, int_); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t...>; });

auto Array = hana_tuple[int_<69>];

// instantiate the array constexpr decltype(Array)::type arr = {{0}}; static_assert(sizeof(arr) == 69, ""); }

However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

[snip] Why couldn't map be implemented as a tuple, as shown here: https://gist.github.com/cppljevans/8e545e8d83946cd74311 Wouldn't that eliminate the difference in performance between map and tuple? -regards, Larry

The problem with this approach is that equality of keys can't be more general than type identity.

Instead a special "hash"-like function could be provided that would transform the keys to a type where identity could be used. This might be faster than using linear/binary search, since the the compiler can do the lookup based on identity. Paul -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Hana-Announcing-Hana-s-formal-revie... Sent from the Boost - Dev mailing list archive at Nabble.com.

...

...

The problem with this approach is that equality of keys can't be more general than type identity.

Instead a special "hash"-like function could be provided that would transform the keys to a type where identity could be used. This might be faster

...

using linear/binary search, since the the compiler can do the lookup

than based

...

on identity. « []

I have thought about that already, but how would you define such a hash function for _heterogeneous_ objects?

Its not a real hash function. It just would return an object(ie type) where identity(ie `std::is_same`) can be used. That is it will apply the function as a transform to the key, and use the result to lookup the key using name lookup. It could default to being identity: auto m = make_hash_map( identity, make_pair(type<T>, x), make_pair(type<U>, y) ); assert(m[type<T>] == x); However, if the user wants store intregral constants, and wants it to work with any integral constant, then a custom "hash" function could be used, which would convert every integral constant of the same value to the same type: auto hash_intregral_constant = [](auto x) -> integral_constant { return {}; }; auto m = make_hash_map( hash_intregral_constant, make_pair(int_<0>, x), make_pair(int_<1>, y) ); assert(m[0_c] == x); assert(m[std::integral_constant()] == x); Of course, now the user can only use integral constants as keys. However, if the user wanted to use non integral constants and have them compare using `std::is_same` then the user could just write something like this: auto m = make_hash_map( overload_linear(hash_intregral_constant, identity), make_pair(0_c, x), make_pair(1_c, y), make_pair(type<T>, x), make_pair(type<U>, y) ); assert(m[type<T>] == x); assert(m[0_c] == x); assert(m[std::integral_constant()] == x); Paul -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Hana-Announcing-Hana-s-formal-revie... Sent from the Boost - Dev mailing list archive at Nabble.com.

On 06/13/2015 09:52 AM, Louis Dionne wrote:

Larry Evans writes:

...

On 06/09/2015 11:00 AM, Louis Dionne wrote: [snip]

...

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers. Here's the version I would have written:

#include #include #include using namespace boost::hana;

static constexpr int map_size = 100;

void run() { constexpr auto hana_range = range(int_<0>, int_); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t...>; });

auto Array = hana_tuple[int_<69>];

// instantiate the array constexpr decltype(Array)::type arr = {{0}}; static_assert(sizeof(arr) == 69, ""); }

However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

[snip] Why couldn't map be implemented as a tuple, as shown here:

https://gist.github.com/cppljevans/8e545e8d83946cd74311

Wouldn't that eliminate the difference in performance between map and tuple?

The problem with this approach is that equality of keys can't be more general than type identity. In other words, in your example, writing

get<_ulong<1>>(mud)

would fail because there is no _ulong<1> key, but only a _uint<1>, even though they compare equal. I want to determine the equality of keys with the `equal` function, which is more general. Of course, in the specific case of a Map mapping types (and only types) to values, then your approach could be used, and it is in fact exactly what I had in mind.

OK. I hadn't thought of that. OTOH, why not just patch the gist map with a method for doing the get_key using the more general `equal` function. Then you could have both the fast find with get, and the more general get_key using the `equal` function? BTW, I'm trying to do this at the moment; however, I'm having a tough time figuring out how to do it. I've looked at: https://github.com/ldionne/hana/blob/master/include/boost/hana/map.hpp#L44 and guessed that maybe I can start by using superclasses for my gist map the same as the at map.hpp#L44, and then maybe reading http://ldionne.com/hana/index.html#tutorial-extending. Is that what you'd recommend? [snip]

On 06/17/2015 07:36 AM, Louis Dionne wrote:

Larry Evans writes:

...

On 06/13/2015 09:52 AM, Louis Dionne wrote:

...

Larry Evans writes:

...

On 06/09/2015 11:00 AM, Louis Dionne wrote: [snip]

...

Indeed, you are using a Map when what you really want is a Tuple, since your keys are integers. Here's the version I would have written:

[...]

However, I can easily imagine another example where you actually need the functionality of a Map. See below for performance comments.

[snip] Why couldn't map be implemented as a tuple, as shown here:

https://gist.github.com/cppljevans/8e545e8d83946cd74311

Wouldn't that eliminate the difference in performance between map and tuple?

The problem with this approach is that equality of keys can't be more general than type identity. In other words, in your example, writing

get<_ulong<1>>(mud)

would fail because there is no _ulong<1> key, but only a _uint<1>, even though they compare equal. I want to determine the equality of keys with the `equal` function, which is more general. Of course, in the specific case of a Map mapping types (and only types) to values, then your approach could be used, and it is in fact exactly what I had in mind.

OK. I hadn't thought of that. OTOH, why not just patch the gist map with a method for doing the get_key using the more general `equal` function. Then you could have both the fast find with get, and the more general get_key using the `equal` function?

That's an idea. My initial idea was to simply detect when a map is created with all the keys being Types. In that case, lookup by == is just lookup by is_same, and you can use an optimized representation for the Map, and an optimized version of the lookup algorithm. Such a Map might be created with map_t<...> or something, I haven't figured that one out yet. It's similar to the way you can use tuple_t<...> to create a tuple optimized for types.

[snip] Adding the following function after the gets works: template < typename KeyEqual , typename... Key , typename... Val > auto get_equal_key ( _map_tuple...>const& a_map ) { constexpr auto key_found_maybe_v =find(make_set(Key{}...),KeyEqual{}); constexpr auto key_found_v =from_maybe(nothing,key_found_maybe_v); using key_found_t =typename decltype(key_found_v)::type; return get(a_map); } I assume it would suffer the same slow compile times as the current map because it uses find. If the KeyEqual is not found, then the compiler errors at the key_found_t definition with and error about nothing not having a ::type. -regards, Larry

Vicente J. Botet Escriba writes:

Le 05/06/15 21:18, Glen Fernandes a écrit :

...

Dear Boost community,

The formal review of Louis Dionne's Hana library starts Monday, 10th June and ends on 24th June.

Hana is a header-only library for C++ metaprogramming that provides facilities for computations on both types and values. It provides a superset of the functionality provided by Boost.MPL and Boost.Fusion but with more expressiveness, faster compilation times, and faster (or equal) run times. <snip> We encourage your participation in this review. At a minimum, kindly state: Here is my mini review. I have created some issues on github. My vote is not subject to the result of any of them.

Thanks for your review, Vicente. Also, thanks a lot for the issues on GitHub; these will definitely contribute to improving the quality of the library.

...

- Whether you believe the library should be accepted into Boost Yes, yes and yes. I consider Boost.Hana must be accepted into Boost. - Your name Vicente J. Botet Escriba - Your knowledge of the problem domain. A good knowledge and I have learn a lot more with the work of Louis in Hana.

You are strongly encouraged to also provide additional information: - What is your evaluation of the library's: * Design Brilliant, awesome. Seen types as values is a revolutionary design. Thanks Louis.

For full disclosure, I must admit that the idea of seeing types as values was first brought up by Matt Calabrese and Zach Laine at BoostCon 2012 [1]. I discovered the thing on my own in 2014 [2], but they definitely were there first.

I liked the way the Haskel concepts have been adapted to C++14.

In previous version of the library (I don't know when this has been changed), I liked * type classes, * the instantiation either directly or when the type is an instance of a type class (using the second parameter).

If you are referring to automatically-defined models, this is still possible. For example, the model of Monoid is automatically provided for any Constant containing something that's a Monoid too: template <typename C> struct plus_impl() && models() >> { // implementation of plus() }; template <typename C> struct zero_impl() && models() >> { // implementation of zero<> }; The difference with the previous design, IIRC, is that in order to define a model of Monoid, you used to write something like template <typename C> struct Monoid::instance() && models() >> { // implementation of plus() and zero<> }; Both are essentially equivalent, except that you can now define individual algorithms more easily.

* the minimum definition set and how to inherit from them. * The split concepts and data_types to make it more evident the distinction.

All this has now disappeared, surely as requested in this ML :(.

Things that I like less are

* the data_type (tag) concept. IMO, what is behind is a type constructor. A type constructor is a class that has a nested alias template apply to build new types. A class template can also be seen as a type constructor by lifting it.

For others reading this, see this issue [3] for the ongoing discussion about this.

* the fact that the result type of a lot of functions is not a concrete type or is not defined.

This is a real difficulty. I could provide types, but then they wouldn't be useful at all in most cases, and they would often be straight up misleading. For the reference of others reading this, please see this issue [4].

* the fact that the interface is not typed, the use of auto and lambdas everywhere is less informative that a typed interface.

That is a documentation issue, right? I could devise a convention where the concepts expected from each argument is used in the signature, something like this: auto fold_left = [](Foldable&& xs, auto&& state, auto&& function) { // ... }; But then I would still need to explain the signature in prose, i.e. the fact that the function must take a state and an element from the Foldable, and so on. Anyway, I'm open to suggestions, but heterogeneous programming definitely brings different documentation challenges from usual generic programming.

* the Signature as an alternative way to define the interface should be documented.

The usage of the signature to document the interface is now explained at the end of the tutorial, in a section explaining how to use the reference documentation. This is issue [5].

I would find more useful to define the signature before the description.

So you would prefer the description in words to come after the signature in semi-formal math language? I guess I could try that out and see how it looks like, but I am under the impression that most people would prefer it the other way around. Created issue [6] to remember to try it out.

* This is a library with a lot of Concepts. It is not easy to find the correct name for each of them and each of the functions in the C++ world when the concepts come from another language with different history. There are some names that I don't like, but I recognize that finding a coherent set of names is not easy.

* the fact that all the functions are in the same namespace. This imply that we need to find a different name for each function. Making use of namespaces for each concept add a freedom degree.

One of my fears is that this would make the library much more complicated, especially for new users. What would happen if you had to prefix each algorithm with the name of the concept that defines it? I know I would sometimes ask myself "hey, what concept defines this?", so I can only imagine the worse for other users. My preference so far has been to deal with this missing degree of liberty by selecting names that do not clash. It is sometimes a bit annoying, but I think the resulting simplicity is worth it.

* The functional part has disappeared as there were some overlapping with Boost.Fit (We need now Boost.Fit).

Technically, it's still part of Hana. It was hidden in the Details section of the documentation to give me the liberty to switch to Fit in the future, but I wouldn't consider its functionality gone for good.

* the instantiation either directly or when the type is an instance of a type class (using the second parameter).

This was also listed in the things you liked, so I guess you have a love and hate relationship with this feature :-).

I'm not yet clear about * the fact that Hana has reimplemented part of the standard to avoid dependencies and improve performances. IMHO, this is not the C++ way,

I have removed Hana's reimplementation of on the develop branch. Given the size the library has grown to (> 25 kLOCs), I don't think it was justified anymore not to use , which is usually around 3 kLOCs. At first, when Hana was really small, I think it was justified.

but Maybe the C++ standard library should be structured in a different way. Maybe the expected modules could help here.

I think part of the standard library should be structured in a different way, no doubt on this. I would be happy with slightly finer-grained headers. At the very least, it would be reasonable to ask for // make_index_sequence & al // std::true_type & al <pair> // std::pair, nothing else!

...

* Implementation I used to inspect the old version. I have less inspected the current one.

I find it quite clear and elegant even if I prefer the architecture of the old version.

...

* Documentation

Very good tutorial.

The documentation would improve a lot with a better design rationale section. * What a Concept is and how the map is done.

This will be handled by the section on "Creating new concepts" in the "Extending the library" section (which is now "Hana's core" on develop).

* What a Tag/datatype is, why do we need it, alternatives, and how all this works.

Tags are now explained in a new section about Tags on the develop branch.

* Naming and order of parameters

I just added a rationale for what drives my name choices and the order of parameters.

* Why and when free functions or member functions are used.

I'm not sure whether it is Hana's job to explain why free functions are better than member functions for generic programming. I don't know, but I feel like anyone reading Hana's tutorial would know the answer :-).

The reference documentation is a little bit confusing for some one used to the C++ standard way. * The terms Concept/Superclass/Methods, ...

Now using Concept/"Refined Concept"/Functions.

* A more formal definition of the mappings from concrete type to Concepts and the Super classes

Maybe this is enough for Boost, but I would like to see a more C++ standard like documentation.

I'm not sure I understand what you mean by a more formal definition of the mapping from concrete type to concepts. Do you mean that the requirements of a concept should be defined more formally?

...

* Tests Not inspected in depth, but it seems well covered. * Usefulness Very useful.

Even if I have not used it directly, I have taken a lot of ideas from his design. If the announced performances are there, it is clear that Boost.Hana will be used more a more by those that can use a C++14 compiler. I'll hope adding a dependency on the C++ standard library will not degrade the performance so much.

Adding a dependency on the standard library (basically the and the <utility> headers) do not seem to have a large impact on compile-times right now. Actually, it might be worse for micro-benchmarks because we're pulling slightly more stuff, but for actual code bases it's going to be better because we're reusing , which everyone includes anyway.

...

- Did you attempt to use the library? If so: No yet.

I will do it as soon as I install the good compiler version.

You can try it online at [7].

...

* Which compiler(s)? * What was the experience? Any problems? - How much effort did you put into your evaluation of the review?

Thanks again Louis for this wonderful library. I would like to see in Boost a similar functional library but this time for run-time types.

Thanks for the review. Regards, Louis Dionne [1]: https://www.youtube.com/watch?v=x7UmrRzKAXU [2]: http://ldionne.com/mpl11-cppnow-2014/ (slide 20-4) [3]: https://github.com/ldionne/hana/issues/94 [4]: https://github.com/ldionne/hana/issues/99 [5]: https://github.com/ldionne/hana/issues/94 [6]: https://github.com/ldionne/hana/issues/121 [7]: http://melpon.org/wandbox/permlink/MZqKhMF7tiaNZdJg

Vicente J. Botet Escriba writes:

Le 15/06/15 22:39, Louis Dionne a écrit :

...

Vicente J. Botet Escriba writes:

[...]

...

* the instantiation either directly or when the type is an instance of a type class (using the second parameter). If you are referring to automatically-defined models, this is still possible. For example, the model of Monoid is automatically provided for any Constant containing something that's a Monoid too:

template <typename C> struct plus_impl() && models() >> { // implementation of plus() };

template <typename C> struct zero_impl() && models() >> { // implementation of zero<> };

The difference with the previous design, IIRC, is that in order to define a model of Monoid, you used to write something like

template <typename C> struct Monoid::instance() && models() >> { // implementation of plus() and zero<> };

Both are essentially equivalent, except that you can now define individual algorithms more easily. Yes, it is still possible, but you need more. With the previous design you you could design an mcd that forward to the current design.

That is true. This was at the cost of more complexity to customize specific algorithms. This was a tradeoff, and I decided to go this way. By the way, this move was very painful and I consider this was one of the larger design choices I had to make in the library, because it involved a ton of other smaller things visible only to someone who look closely.

...

...

[...]

* This is a library with a lot of Concepts. It is not easy to find the correct name for each of them and each of the functions in the C++ world when the concepts come from another language with different history. There are some names that I don't like, but I recognize that finding a coherent set of names is not easy.

* the fact that all the functions are in the same namespace. This imply that we need to find a different name for each function. Making use of namespaces for each concept add a freedom degree. One of my fears is that this would make the library much more complicated, especially for new users. What would happen if you had to prefix each algorithm with the name of the concept that defines it? I know I would sometimes ask myself "hey, what concept defines this?", so I can only imagine the worse for other users. I see this differently. It will force the user to ask himself, what exact function he is using.

Interesting. I think most users don't want to have to do this thinking, lol. My goal is to make metaprogramming easier for average programmers. In the mid/long term, I want Hana to be usable without even knowing about the Functor/Applicative/Monad/MonadPlus concepts & al. These concepts will still be available for more hardcore developers or FP people, and they are incredibly important because they are the basis on which the library is built. However, the average Joe who just wants a damn for_each on a tuple should not be required to understand Monads or even the Foldable concept (personally, it took a good while until I was finally comfortable with folds).

...

My preference so far has been to deal with this missing degree of liberty by selecting names that do not clash. It is sometimes a bit annoying, but I think the resulting simplicity is worth it. Currently you are free to use any names in boost::hana, but how would you name them if you were writing a proposal for the C++ standard? We will have Range-V3 one day and others that make use of similar names. Associating the names to the concepts allow to get rid of all these possible clashes.

I would try to piggy-back the same names as the Range-v3 library in my proposal, so that you can use algorithms both on tuples and runtime ranges. Actually, I think that's the future. But designing for the standard and for Boost are two very different things. I'll try to get the first one right, and then see if I want to go for the second too.

...

...

[...]

* Why and when free functions or member functions are used. I'm not sure whether it is Hana's job to explain why free functions are better than member functions for generic programming. I don't know, but I feel like anyone reading Hana's tutorial would know the answer . It seems that you use free functions everywhere except when you can not. Am I wrong?

Global function objects would be more precise, but yeah I think that's it. Off the top of my head, I'd say the only member functions are - .times for IntegralConstant, because that looks nice - operator[] for Sequences, because it has to be implemented as a member

...

...

The reference documentation is a little bit confusing for some one used to the C++ standard way. * The terms Concept/Superclass/Methods, ... Now using Concept/"Refined Concept"/Functions.

Thanks.

...

...

* A more formal definition of the mappings from concrete type to Concepts and the Super classes

Maybe this is enough for Boost, but I would like to see a more C++ standard like documentation. I'm not sure I understand what you mean by a more formal definition of the mapping from concrete type to concepts. Do you mean that the requirements of a concept should be defined more formally?

I would like a description that defines what expressions are valid given some constraints on other expressions.

Ok, so syntactic requirements instead of just semantic requirements. That seems a legitimate and useful thing to document. See this issue [1].

...

...

[...] I will do it as soon as I install the good compiler version. You can try it online at [7].

I will do. I would like to see how something like the metaparse library or

(http://blog.mattbierner.com/stupid-template-tricks-pride-and-parser -combinators-part-one/) becomes while using Hana interface.

That would indeed be a very interesting experiment. However, that would take a lot of time and I can't afford to do that right now. Perhaps later after the review, when all those issues I'm accumulating are fixed :-). Regards, Louis [1]: https://github.com/ldionne/hana/issues/127

Abel Sinkovics writes:

[...]

It would be useful to add a step-by-step guide to the documentation for extending the library with custom algebraic data-types - for example a "how to build your own Optional/Either/etc" (Note: I was reading Optional's implementation as an example to build my own data types).

Once I learned how to build my own data-types, I could easily create the ones I needed and they worked intuitively (to me). So it seems to be well supported and should be better documented.

This should be part of the (still incomplete) section of the tutorial on "Extending the library". I guess using a concrete example like Optional is a good idea. Thanks for the heads up.

It is great that the library makes it possible to have static if_ and switch_ in the body of a function. I think a few things should be pointed out about them (probably in the documentation):

- when entering a branch of an if_ (or switch_) you are calling a different function which is not (always) the same as having a block inside your function body. You might (and are very likely to) be affected by how you pass arguments to this function (capture in the lambda, pass by value, pass by rvalue reference, etc). This is something to be aware of when using these constructs.

Definitely. I will add this to the documentation.

- if you use these structures (especially if you have 2 or 3 nested layers of them in the same function), the same variable might have different names on each level (eg. to make sure that a branch of the if_ gets instantiated only when it is needed and safe to do so). This can be confusing.

There's actually a different way to do it, but it is not documented in the tutorial. It is documented in the reference of `eval_if` [1]. I will try to add it to the tutorial.

[...]

Even though I haven't tried it, but based on the documentation the Lazy type seems to be an interesting way to approach lazy evaluation for metaprograms. The idea of the lazy monad seems very interesting. One thing I'd fix in Lazy's documentation: eval_if is mentioned in Lazy's doc, however there is no link to it and it was not trivial to find eval_if's doc. I'd make the places mentioning eval_if links to its description.

Taking a note to add links to eval_if. More generally, this should always be handled properly but the documentation tool, but this does not happen with Doxygen :-(.

Why is string not a model of the Constant concept? I tend to think of strings as values and since they contain characters only, they should be representable at runtime. (the question is probably how they should be represented).

String used to be a model of Constant. The problem is that the `value` function, which extracts the value from the Constant, should preserve the semantics of the original Constant. However, since String's value was (formerly) a `char const*`, that structure was not preserved. For example, it would be true that "abcd"_s < "abcde"_s while value_of("abcd"_s) < value_of("abcde"_s) would not necessarily hold, because it would compare two `char const*`. The proper workaround would be to have a compile-time string class, and the `value()` of a Hana String should be a constexpr object of that type. However, if you need a `char const*` from a Hana String, you can use `to("abcd"_s)`, which is a non structure-preserving conversion.

What is the reason behind using tag dispatching in Hana? More specifically, why is tag dispatching used instead of for example enable_if? For example:

template >> auto head(T t);

template >> auto head(T t);

...

It is not clear to me why tag dispatching is preferred over this (or a similar) approach. (eg. does tag dispatching perform better?) It might be explained in the documentation.

I wanted a two-layer dispatching system because the first layer (the functions you call) are actually function objects, which allows using them in higher-order algorithms. They can also do some compile-time sanity checks, which improves error messages. Now, we could just as well write: template >> auto head_impl(T t); template >> auto head_impl(T t); and have head() call head_impl() after doing its sanity checks. However, when checking whether a type is a model of some concept, we basically check that some key functions are implemented. For example, `models` checks whether the is_empty, head and tail functions implemented for T. AFAIK, the only way to detect this with the above approach is to basically check whether the following expressions are valid in a SFINAE-able context: head_impl(std::declval<T>()) is_empty_impl(std::declval<T>()) tail_impl(std::declval<T>()) But this requires doing the actual work. With tag dispatching, we can just ask whether head_impl<T>, is_empty_impl<T> and tail_impl<T> are defined, and nothing happens until we actually call head_impl<T>::apply(...). This is one of the reasons why I went with tag-dispatching, but frankly this is also a slightly arbitrary decision. Providing customization points is not exactly easy; there are a lot of different solutions. Also, the heterogeneous context definitely makes the task of providing customization points harder, since you can't rely on the actual type of the objects to dispatch.

[...]

Multiple types are models of the Monad concept, however, the documentation does not explain how the monadic operations are implemented for the different types (eg. what chain is doing for lists, etc). I believe it is not (always) trivial and should be explained in the documentation (I had simliar things in Metamonad and decided to add it to the documentation).

Technically, the implementation of `flatten` for Sequences is documented in the Sequence concept. From there, you could derive the implementation of `chain` and all the other functions from Monad. Of course, doing so is not easy and I will add this to the documentation.

I really like it that for some elements (eg. Functor's transform operation) the documentation contains benchmarks.

In the future, I plan to provide benchmarks for almost every algorithm. That used to be the case, but I changed the benchmarking system and didn't have the time to rewrite them all.

[...]

Thanks a lot for your review, Abel! Regards, Louis [1]: http://goo.gl/c0qgsb

Abel Sinkovics writes:

Hi Louis,

[...]

So if I get it right, a compile-time string class is missing to make it a model of Constant. I know that it can be converted into a const char*, but I think it would be good in the long run to be able to think of strings as values. (as we can do it in runtime code). I guess it can be added in a future version of Hana, when such a compile-time string class becomes available.

Exactly. If I had a compile-time std::string, that would do the trick. Something like std::string_view would be just perfect, I think.

...

[...] But this requires doing the actual work. With tag dispatching, we can just ask whether head_impl<T>, is_empty_impl<T> and tail_impl<T> are defined, and nothing happens until we actually call head_impl<T>::apply(...). This is one of the reasons why I went with tag-dispatching, but frankly this is also a slightly arbitrary decision. Providing customization points is not exactly easy; there are a lot of different solutions. Also, the heterogeneous context definitely makes the task of providing customization points harder, since you can't rely on the actual type of the objects to dispatch.

I understand your point. (I think it might worth an entry in the Rationales section of the doc).

I added a rationale for it. See this issue [1].

The reason why one might prefer enable_if-based overloading is that based on my understanding of the concepts lite proposal, using them one could create a Tuple concept (eg. TupleC<T>()) checking "is_a" and then use it for overloading like

template <TupleC T> auto head(T t);

or even:

auto head(TupleC t);

Which is a nice syntactic sugar for compile-time algorithms and could make type-function overloading more "natural" for C++ programmers. (However, the price for it is probably loosing all the benefits you have explained above).

That's a very interesting idea. However, I think Hana should stick to tag-dispatching for now. In light of C++17 concepts, it might be worth doing a Hana 2.0 anyway, in which case tag dispatching could be reconsidered. Regards, Louis [1]: https://github.com/ldionne/hana/issues/144