[Boost] [Hana] Announcing Hana's formal review next week (June 10th)

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. To dive right in to examples, please see the Quick start section of the library's documentation: http://ldionne.com/hana/index.html#tutorial-quickstart Hana makes use of C++14 language features and thus requires a C++14 conforming compiler. It is recommended you evaluate it with clang 3.5 or higher.[1] Hana's source code is available on Github: https://github.com/ldionne/hana Full documentation is also viewable on Github: http://ldionne.github.io/hana To read the documentation offline: git clone http://github.com/ldionne/hana --branch=gh-pages doc/gh-pages For a gentle introduction to Hana, please see: 1. C++Now 2015: http://ldionne.github.io/hana-cppnow-2015 (slides) 2. C++Con 2014: https://youtu.be/L2SktfaJPuU (video) http://ldionne.github.io/hana-cppcon-2014 (slides) We encourage your participation in this review. At a minimum, kindly state: - Whether you believe the library should be accepted into Boost - Your name - Your knowledge of the problem domain. You are strongly encouraged to also provide additional information: - What is your evaluation of the library's: * Design * Implementation * Documentation * Tests * Usefulness - Did you attempt to use the library? If so: * Which compiler(s)? * What was the experience? Any problems? - How much effort did you put into your evaluation of the review? [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. Some users have also reported success with using Clang 3.5 on Windows. If you would like assistance configuring the former option, feel free to reach out to us for this. Best, Glen

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

Peter Dimov <lists <at> pdimov.com> 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 1:59 PM, Peter Dimov wrote:
The current Cygwin has clang 3.5.1 and g++ 4.9.2, both of which are C++14 (enough for practical use.)
Nice. Thanks; I'll start suggesting Cygwin to Windows users also. Glen

The formal review of Louis Dionne's Hana library starts Monday, 10th June and ends on 24th June.
Do you mean Wed June 10th or Monday June 8th? -- 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.

Paul Fultz II <pfultz2 <at> yahoo.com> writes:
The formal review of Louis Dionne's Hana library starts Monday, 10th June and ends on 24th June.
Do you mean Wed June 10th or Monday June 8th?
The review was scheduled from June 10 to June 24 ([1]), so I am fairly sure Glen meant Wednesday June 10. Louis [1]: http://www.boost.org/community/review_schedule.html

On Fri, Jun 5, 2015 at 4:33 PM, Louis Dionne <ldionne.2@gmail.com> wrote:
Paul Fultz II <pfultz2 <at> yahoo.com> 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

Glen Fernandes <glen.fernandes <at> gmail.com> 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. Here is a small example that uses an mpl type map and the corresponding code I put together (likely sub-optimally) using hana: // hana.cpp #include <cassert> #include <string> #include <array> #include <boost/lexical_cast.hpp> #include <iostream> #ifdef _USE_HANA #include <boost/hana.hpp> #include <boost/hana/ext/std/type_traits.hpp> #else #include <boost/mpl/map.hpp> #include <boost/mpl/range_c.hpp> #include <boost/mpl/inserter.hpp> #include <boost/mpl/insert.hpp> #include <boost/mpl/transform.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/alias.hpp> #endif #ifndef _USE_HANA template <typename _Type, typename _Sz> struct make_arr{ typedef std::array<_Type, _Sz::value> type; }; #else namespace hana = boost::hana; using namespace boost::hana::literals; #endif void run() { static constexpr int map_size = 100; #ifdef _USE_HANA constexpr auto hana_range = hana::range(hana::int_<0>, hana::int_<map_size>); auto hana_inserter = [](auto st_, auto el_){ return hana::insert(st_, hana::make_pair(el_, hana::type<std::array<char, decltype(el_)::value>>)); }; // create a map of (int_<0>, array<char, 0>)(int_<1>, array<char, 1>), etc /*constexpr*/ auto hana_map = hana::fold.left(hana_range, hana::make_map(), hana_inserter); // Can I use make_pair() here as a metafunction instead of defining my own inserter? #else typedef mpl::range_c<int, 0, map_size> mpl_range; // create a map of (int_<0>, array<char, 0>)(int_<1>, array<char, 1>), etc typedef mpl::transform< mpl_range ,mpl::pair<mpl::_, make_arr<char, mpl::_> > ,mpl::inserter<mpl::map<>, mpl::insert<mpl::_1, mpl::_2> >
::type mpl_map; #endif
#ifdef _USE_HANA // find the element at index 69; /*constexpr*/ auto hana_el_0 = hana_map[hana::int_<69>]; // instantiate the array constexpr decltype(hana_el_0)::type arr = {0}; static_assert(sizeof(arr, 69), ""); #else typedef mpl::at<mpl_map, mpl::integral_c<int, 69>>::type mpl_el_0; constexpr mpl_el_0 arr = {0}; static_assert(sizeof(arr, 69), ""); #endif } int main(int argc_, char **argv_) { int c = boost::lexical_cast<int>(argv_[1]); for(int i = 0; i < c; ++i) run(); } 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 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. 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")); and even make_map(1,2,3); It's not at all clear to me how the results of such expressions can be used.

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

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.

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.

Pete Bartlett <pete <at> pcbartlett.com> writes:
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.
Had I known about SAP Hana, I would probably have chosen a different name. However, I was already contacted a couple of times by people that were concerned with the trademark, so I checked exactly what is being trademarked. What's trademarked is "SAP Hana", not "Hana" itself. Plus, one could argue that the library's name is "Boost.Hana" (if accepted), in which case there is little room for confusion. But IANAL either. Bottom line: SAP, if you're going to sue me, just tell me and I'll change the name. :-) But seriously, it would be painful to change the name at this point because the library is starting to be publicized and the last thing we need is a name change. Regards, Louis

On 9 June 2015 at 15:20, Louis Dionne <ldionne.2@gmail.com> 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.

William Gallafent <william <at> gallaf.net> writes:
On 9 June 2015 at 15:20, Louis Dionne <ldionne.2 <at> gmail.com> 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!
Thanks for the heads up. I'm consulting Boost's attorney and we'll see how we handle this matter.
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 :/
Thanks for your interest, still! If you ever get the chance to use the library, please do not hesitate to fill bug reports and issues for any problem you might encounter. That is a very good and easy way to contribute to the library. Regards, Louis Dionne

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

Paul A. Bristow <pbristow <at> hetp.u-net.com> writes:
[...]
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.
I'd rather have a less-descriptive but easy to remember and type short name than a more descriptive longer name. I'd have taken MPL or Fusion, but they were both already taken. Also, there is precedent for funky names in Boost: Spirit (and Qi, Karma) Phoenix Proto Wave And the rest of the world seems to be very fond of cute names that do not necessarily describe the purpose of the library; go look at libraries in Ruby, JavaScript or basically any other language. Given that I've been working on the library for more than a year, and that it's getting known as Hana on the web, in conferences and mailing lists, I think it would be harmful to change the name, and for a very small benefit. That would also bring some technical pains, like changing the repository name (thus breaking a lot of existing links), changing the namespace and the documentation, and so on. All this for what? A new name which I don't even want to change. I'm sorry, but the name won't change at this point. However, feel free to use a namespace alias in your code if you really don't like typing `hana::`. Regards, Louis

Oleg Grunin <ogrunin <at> yahoo.com> writes:
Glen Fernandes <glen.fernandes <at> gmail.com> 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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana; static constexpr int map_size = 100; void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; }); 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<char, n>`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<Constant, C>{}, ^ ~~~~~~~~~~~~~~~~~~~~~~ note: in instantiation of function template specialization 'boost::hana::value<bool>' requested here hana::if_(hana::value<decltype( ^ As you can probably guess, this failure is caused by the fact that the comparison of 1 and 1 returns a `bool`, yet Hana is expecting a `Constant`.
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<hana::Map, void>::apply<int, int, int>' requested here return make_impl<Datatype>::apply(static_cast<X&&>(x)...); ^ note: in instantiation of function template specialization 'hana::_make<hana::Map>::operator()<int, int, int>' 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

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. :-) Oleg could in principle have used X<char[N]> but would that really have changed much?

Peter Dimov <lists <at> pdimov.com> 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<char[N]> but would that really have changed much?
No, that wouldn't have changed much. Regards, Louis

[...]
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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana;
static constexpr int map_size = 100;
void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; });
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
Louis Dionne <ldionne.2 <at> gmail.com> writes: 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<int, 0, 50>, mpl::range_c<int, 51, 100> > mpl_range, which would likely not work with a tuple. Btw, I couldn't find a way to combine several ranges with hana.
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.
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.
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. Isn't (1 == anything) either a bool or a compile-time error, whereas int_<1> == anything is always a bool_<> or error? Thanks for your more than exhaustive reply.

Oleg Grunin <ogrunin <at> yahoo.com> writes:
Louis Dionne <ldionne.2 <at> gmail.com> 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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana;
static constexpr int map_size = 100;
void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; });
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<int, 0, 50>, mpl::range_c<int, 51, 100> > 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<char, decltype(n)::value>; return insert(map, make_pair(n, type<Array>)); }; auto arrays = fold.left(range(int_<0>, int_<INPUT_SIZE>), 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>, "[int, char, float]"s), make_pair(make_tuple(type<int>, int_<2>), "[int, 2]"s) ); assert((map[tuple_t<int, char, float>] == "[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

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. Regards, -- Joel de Guzman http://www.ciere.com http://boost-spirit.com http://www.cycfi.com/

Joel de Guzman <djowel <at> gmail.com> 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

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

Paul Fultz II <pfultz2 <at> yahoo.com> 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

Louis Dionne <ldionne.2 <at> gmail.com> writes:
Paul Fultz II <pfultz2 <at> yahoo.com> 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
[...]
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. Consider the following: auto xs = make_set(1, 2, 3); auto ys = make_set(1, 3, 2); assert(ys == xs); The funny thing is that this actually works. If you think of it, the code that should be generated is something like: if (xs and ys have different # of elements) return false_; // known at compile-time else return 1 is in ys && 2 is in ys && 3 is in ys; // known at runtime Anyway, since the documentation says Set and Map require compile-time Comparable keys, I'll stick to it for now. However, I might decide to allow runtime keys when I'll focus on improving the associative structures. 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.

Paul Fultz II <pfultz2 <at> yahoo.com> writes:
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.
Indeed, a naive implementation would be O(n^2). However, the interest of providing this might be if you have mixed compile-time and runtime objects in your set. Then, part of the comparisons (or maybe even all of them) could be avoided at runtime because of that compile-time information: auto xs = make_set("huge-string"s, int_<1>); auto ys = make_set("huge-string"s, int_<2>); assert(xs != ys); In theory, the above can be done at compile-time, because we could compare int_<1> with "huge-string"s and then with int_<2>, and then conclude that the sets are different at compile-time because they have the same size but we can't find int_<1> in ys. I'm not sure how clever Hana would need to be to achieve this, and I'm also not sure whether that's very useful. I'll have a look at the problem and only then I'll be able to take a good decision for the future. For now, I think the only sane decision is to support compile-time keys only. Regards, Louis

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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana;
static constexpr int map_size = 100;
void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; });
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

Larry Evans <cppljevans <at> suddenlink.net> 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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana;
static constexpr int map_size = 100;
void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; });
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. I had initially misunderstood your question and I wrote what follows. Instead of throwing it away, I'll just leave it here since it explains why Map's insert is inefficient in more detail: ------------------------------------------------------------------------------ The Map is currently implemented by using a Tuple for its internal storage. The problem is not really that the representation is inefficient, but rather that inserting in a Map is implemented like this (pseudo code): insert(map, {key, value}) { if (map contains key) return map; else { new_storage = append {key, value} to map.storage, which is a tuple return a map with this new storage; } } The most expensive part is looking whether the key is found inside the map. Indeed, `contains(map, key)` is equivalent to `contains(map.storage, key)`, which in turn is implemented as `any_of(map.storage, equal.to(key))`. This `any_of` is the culprit; it is required to short circuit, and hence it must be implemented recursively and rather inefficiently. In the general case of a Tuple, this is mandatory to provide the semantics we want. However, in the case of a Map, the storage is not guaranteed to be in any special order, so we don't have to short circuit and we can then use a more efficient approach. ------------------------------------------------------------------------------ Regards, Louis

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.

Paul Fultz II <pfultz2 <at> yahoo.com> writes:
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.
I have thought about that already, but how would you define such a hash function for _heterogeneous_ objects? I just don't know how that can be done, but it is not a bad idea. Still, I think a good compile-time performance is achievable without a hash function, by simply avoiding the short-circuiting in the `contains` function. Regards, Louis

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<int, decltype(x)::value> { 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<int, 0>()] == 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<int, 0>()] == 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.

Paul Fultz II <pfultz2 <at> yahoo.com> writes:
[...]
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<int, decltype(x)::value> { 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<int, 0>()] == 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<int, 0>()] == x);
That's an interesting idea. Like I said elsewhere, I'll be investigating associative sequences for GSoC around the end of the review. I created this issue [1] to remind me to have a second look at hash-based associative sequences when the time comes. For completeness, I had looked at this possibility [2] last summer when I first implemented Map, but I think I gave up on it because it was slightly too complicated and I had other more urgent things to do. The main determinant for using this will be compile-time performance, so I'll have to benchmark. Regards, Louis [1]: https://github.com/ldionne/hana/issues/118 [2]: https://goo.gl/30sk5N

On 06/13/2015 09:52 AM, Louis Dionne wrote:
Larry Evans <cppljevans <at> suddenlink.net> 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 <boost/hana/integral_constant.hpp> #include <boost/hana/range.hpp> #include <boost/hana/tuple.hpp> using namespace boost::hana;
static constexpr int map_size = 100;
void run() { constexpr auto hana_range = range(int_<0>, int_<map_size>); auto hana_tuple = unpack(hana_range, [](auto ...n) { return tuple_t<std::array<char, decltype(n)::value>...>; });
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]

Larry Evans <cppljevans <at> suddenlink.net> writes:
On 06/13/2015 09:52 AM, Louis Dionne wrote:
Larry Evans <cppljevans <at> suddenlink.net> 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.
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?
Yes, that is what I would recommend. There's a new, extended version of this section in the develop branch, but you'd have to read the source if you wanted to see it. See [1] if you're interested. Otherwise, the section on the master branch might be enough to get you started. Regards, Louis [1]: https://goo.gl/Kl7RDN

On 06/17/2015 07:36 AM, Louis Dionne wrote:
Larry Evans <cppljevans <at> suddenlink.net> writes:
On 06/13/2015 09:52 AM, Louis Dionne wrote:
Larry Evans <cppljevans <at> suddenlink.net> 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<key_val<Key,Val>...>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<key_found_t>(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

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. - 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.
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). * 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. * the fact that the result type of a lot of functions is not a concrete type or is not defined. * the fact that the interface is not typed, the use of auto and lambdas everywhere is less informative that a typed interface. * the Signature as an alternative way to define the interface should be documented. I would find more useful to define the signature before the description. * 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. * The functional part has disappeared as there were some overlapping with Boost.Fit (We need now Boost.Fit). * the instantiation either directly or when the type is an instance of a type class (using the second parameter). 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, but Maybe the C++ standard library should be structured in a different way. Maybe the expected modules could help here.
* 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. * What a Tag/datatype is, why do we need it, alternatives, and how all this works. * Naming and order of parameters * Why and when free functions or member functions are used. The reference documentation is a little bit confusing for some one used to the C++ standard way. * The terms Concept/Superclass/Methods, ... * The Signature as an alternative way to define the interface should be documented. I would find more useful to define the signature before the description. * 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.
* 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.
- Did you attempt to use the library? If so: No yet.
I will do it as soon as I install the good compiler version.
* 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. Vicente

Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> 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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // implementation of plus() }; template <typename C> struct zero_impl<C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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 <type_traits> 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 <type_traits>, 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 <integer_sequence> // make_index_sequence & al <integral_constant> // 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 <type_traits> 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 <type_traits>, 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 <vicente.botet <at> wanadoo.fr> writes:
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;
Le 05/06/15 21:18, Glen Fernandes a écrit : 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. Then thanks Louis to make use of this idiom on your meta-programming
Le 15/06/15 22:39, Louis Dionne a écrit : library. And of course thanks to Matt and Zach. I will take a look at the presentation (I believe that I was there :( )
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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // implementation of plus() };
template <typename C> struct zero_impl<C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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.
* 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.
Agreed that heterogeneous types add some difficulty.
* 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].
Great.
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. I see this differently. It will force the user to ask himself, what exact function he is using.
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
I find clearer when the description talks of a function I know the signature it has. possible clashes.
* 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 guess that I mean here that this has disappeared at the Concept level.
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 <type_traits> 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 <type_traits>, which is usually around 3 kLOCs. At first, when Hana was really small, I think it was justified.
Ok.
* 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).
Great.
* 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.
Great.
* Naming and order of parameters I just added a rationale for what drives my name choices and the order of parameters.
Great.
* 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?
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.
* 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 <type_traits> 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 <type_traits>, which everyone includes anyway. Great.
- 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].
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-combinat...) becomes while using Hana interface.
* 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.
Vicente

Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 15/06/15 22:39, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> 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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // implementation of plus() };
template <typename C> struct zero_impl<C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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<C, C, when< models<Constant, C>() && models<Monoid, typename C::value_type>() >> { // 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

Hi, I've implemented a (very small) core of Metaparse using Hana to try the library out. The aim was not to evaluate how such a base metaprogramming library would affect the design of Metaparse, but to have a non-trivial example to try the library out with. As I have experience with compile-time only computations, I've been focusing on that aspect of Hana. A great thing about Hana is that it provides a syntax for template metaprograms that is familiar for C++ developers without large overhead for the compilation process. It makes functions over types look like "regular" C++ functions. However, this advantage might be a disadvantage in some cases. With the Boost.MPL approach, the code evaluated at compile-time has a significantly different syntax than the code executed at runtime. It is easy to tell which is which, while with the new approach, this is not (always) that simple, which might lead to confusion in more complex code. So I have some concerns about it in larger metaprograms. The library's design is strongly influenced by Haskell, which is in my opinion a good thing given the functional nature of metaprogramming in C++. Metaparse uses types that are built with Haskell's algebraic data-types in mind. (Given a type and a number of constructors). This concept works well with the "pattern matching" partial template specialisation provides. I could represent such data-types in Hana (and the library offers a few as well, eg. Optional is the Hana representation of Haskell's Maybe). 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. 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. - 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. - in some cases (and I have seen such cases in my small experiment) you don't need lambdas. If calculating both branches of the if_ is always safe and has no large overhead, you might just "inline" the two return values. Eg. instead of if_(<condition>, []() { return 1_c; }, []() { return 2_c; }) you can have if_(<condition>, 1_c, 2_c) This makes the code simpler. (My "real" example is inside a more complex function, so I came up with this artificial example, I hope it still demonstrates the idea). Because of using if_ with lambdas (in most cases), I ended up leaving almost every block in my functions with "return", so there were "return"s all over my code. I just wanted to point this out, I have no idea how to improve this. I guess it is something similar to having "typename" everywhere in MPL-style metaprograms. :) 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. 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). 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 <class T, class = std::enable_if<is_a<Tuple, T>>> auto head(T t); template <class T, class = std::enable_if<is_a<String, T>>> 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 believe this library promotes a new and better way for building metaprograms. Here are my answers to the formal review questions: On 2015-06-05 21:18, Glen Fernandes wrote:
We encourage your participation in this review. At a minimum, kindly state: - Whether you believe the library should be accepted into Boost Yes.
- Your name Ábel Sinkovics
- Your knowledge of the problem domain. I have several years of template metaprogramming experience. I have implemented MPL extensions supporting Haskell-style functional programming (Mpllibs.Metamonad). I have no experience with heterogeneous containers.
You are strongly encouraged to also provide additional information: - What is your evaluation of the library's: * Design Clean. It makes things (eg. datatype) explicit that have been implicitly present in earlier metaprogramming libraries. Some design decisions (pointed out above) should be better documented.
* Implementation I haven't looked at the implementation of the library in detail. I was using the implementation of some parts as examples for extending the library. The code was well segmented (which definitions/specialisations implement what aspects) and easy to understand.
* Documentation I find the reference useful and the tutorial is explaning the concept of the library (and the new metaprogramming technique) well.
* Tests The library seems to be well covered with tests. I haven't looked at
However, I felt that the documentation could be extended with step-by-step tutorials on how to do common things (eg. defining your new data types, how to use things like if_, etc). 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). I really like it that for some elements (eg. Functor's transform operation) the documentation contains benchmarks. them in detail.
* Usefulness I think the library is very useful as a metaprogramming base library to build on top of. However, given its limited compiler support, libraries built on top of it will probably have to wait until compilers catch up before they can be widely adopted.
- Did you attempt to use the library? If so: Yes.
* Which compiler(s)? Clang 3.6.0
* What was the experience? Any problems? It was working, I had no problems.
- How much effort did you put into your evaluation of the review? I've read the tutorial and reimplemented the core of a template metaprogramming library using Hana and tried a few other random things out.
Regards, Ábel

Abel Sinkovics <abel <at> elte.hu> 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<char const*>("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 <class T, class = std::enable_if<is_a<Tuple, T>>> auto head(T t);
template <class T, class = std::enable_if<is_a<String, T>>> 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 <class T, class = std::enable_if<is_a<Tuple, T>>> auto head_impl(T t); template <class T, class = std::enable_if<is_a<String, T>>> 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<Iterable, T>` 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

Hi Louis, On 2015-06-20 23:19, Louis Dionne wrote:
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<char const*>("abcd"_s)`, which is a non structure-preserving conversion. 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.
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 <class T, class = std::enable_if<is_a<Tuple, T>>> auto head(T t);
template <class T, class = std::enable_if<is_a<String, T>>> 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 <class T, class = std::enable_if<is_a<Tuple, T>>> auto head_impl(T t);
template <class T, class = std::enable_if<is_a<String, T>>> 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<Iterable, T>` 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.
I understand your point. (I think it might worth an entry in the Rationales section of the doc). 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<Tuple, T>" 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). Regards, Ábel

Abel Sinkovics <abel <at> elte.hu> 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<Tuple, T>" 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
participants (12)
-
Abel Sinkovics
-
Glen Fernandes
-
Joel de Guzman
-
Larry Evans
-
Louis Dionne
-
Oleg Grunin
-
Paul A. Bristow
-
Paul Fultz II
-
Pete Bartlett
-
Peter Dimov
-
Vicente J. Botet Escriba
-
William Gallafent