[Hana] Informal review request
Dear Boost, As some may be aware of, I am currently working on a metaprogramming library called Hana, with the intention of proposing it for inclusion in Boost. The purpose of that library is to act as a toolbox for expressing computations on both types (like the MPL) and heterogeneous values (like Fusion). The library is built around C++14 idioms and implementation techniques to maximize expressiveness and performance. I am now requesting feedback from the community, with the intention of asking for a formal review in the next months. A similar review was asked for in last August. The library has undergone several modifications since then, both to address issues raised during the review and for general improvement. Here are some issues that were raised during the review and addressed: - Usage of names and terms unknown to C++ programmers: Efforts were made to make this better, and several functions were renamed (`fmap` is now `transform`). When possible, the documentation also uses terms more familiar to C++ programmers, like concept instead of "type class". - The order of the arguments to some algorithms was unfortunate for C++. It was consistent with Haskell, but it turned out to be cumbersome in C++. This is changed in most places. - Inability to easily implement individual algorithms: This is fixed, and algorithms are now standalone structures using tag-dispatching, almost exactly as in Fusion. - Lack of a good introductory tutorial: A lot of work has gone into improving both the tutorial and the reference documentation. - Lack of support for mainstream compilers: The library is now almost fully functional with Clang 3.5. A GCC 4.9 port with reduced functionality is also underway on the `redux` branch. The library is available at [1] and the documentation at [2]. Comments should be directed to this mailing list, while bugs and other similar problems should be directed to the GitHub issue tracker. Please participate, especially if you have interest and/or experience in metaprogramming; after all, you represent the target audience for Hana. Thank you, Louis Dionne [1]: https://github.com/ldionne/hana [2]: http://ldionne.github.io/hana/
Dear Boost,
As some may be aware of, I am currently working on a metaprogramming
On 03/05/2015 02:41 PM, Louis Dionne wrote: library
called Hana, with the intention of proposing it for inclusion in Boost. The purpose of that library is to act as a toolbox for expressing computations on both types (like the MPL) and heterogeneous values (like Fusion). The library is built around C++14 idioms and implementation techniques to maximize expressiveness and performance.
I am now requesting feedback from the community, with the intention of asking for a formal review in the next months. A similar review was asked for in last August. The library has undergone several modifications since then, both to address issues raised during the review and for general improvement. Here are some issues that were raised during the review and addressed:
I'm a FP novice and thoroughly enjoyed reading through the top level documentation. It seemed very approachable and well written. I was able to at least glimpse at what the intention was, even not being able to fully comprehend it in a first reading. I'm anxious to see where this goes and to get more familiar with the paradigm as a result. Thanks for sharing your work and contributions.
Brian Schrom <brian.schrom <at> pnnl.gov> writes:
[...]
I'm a FP novice and thoroughly enjoyed reading through the top level documentation. It seemed very approachable and well written. I was able to at least glimpse at what the intention was, even not being able to fully comprehend it in a first reading. I'm anxious to see where this goes and to get more familiar with the paradigm as a result. Thanks for sharing your work and contributions.
Thank you for your feedback. If you ever find something to be unclear, badly explained or just hard to understand in the documentation, please create a GitHub issue and I will try to make the situation better. Being understandable by non-FP people is important for Hana because of the C++ audience it is aimed at. Louis
AMDG I've just glanced over the main page of the documentation and I had a few comments: - _tuple<Person, Car, City> Historically names beginning with _ are used for placeholders. i.e. in Boost.Bind/Lambda/Phoenix/Parameter. Is there a good reason not to call it tuple? - // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? I think you should probably avoid using these constructs in the user documentation of other parts of the library. It's just a distraction, so it's better to rely on standard components, which users probably already understand. - Is there a reason for using length instead of size, which would be more idiomatic in C++? - Amphibian algorithms!!!??? Okay, I guess the name is kind of clever. I can't say that I really like it, though. - foldl/foldr. I really hate these names. I'd prefer fold/reverse_fold, but even fold_left/fold_right would be better. - count is the equivalent of std::count_if, not std::count. - find/lookup should be find_if/find - In general I would expect any algorithm that takes a single element for comparison to have both f and f_if forms. - sort(predicate): shouldn't this be sort(sequence)? In Christ, Steven Watanabe
Steven Watanabe <watanabesj <at> gmail.com> writes:
AMDG
I've just glanced over the main page of the documentation and I had a few comments:
- _tuple<Person, Car, City> Historically names beginning with _ are used for placeholders. i.e. in Boost.Bind/Lambda/Phoenix/Parameter. Is there a good reason not to call it tuple?
It is because of other constructs in Hana like `tuple_t<Types...>` which are variable templates and whose type is not specified. I have not found a good naming convention for variable templates and types yet. I'll sketch out the current state of affairs, and perhaps someone can suggest a convention that would work well. Hana currently proposes the following: _tuple<T...> : The type of a tuple containing objects of type T... make_tuple(x...): Create a tuple of type _tuple<decay_t<decltype(x)>...> tuple(x...): Currently equivalent to make_tuple(x...), but deprecated because I'd like to use it in place of _tuple. Tuple: The generalized data type of tuples. tuple_t<T...>: A variable template returning a tuple containing types. This object has an _unspecified type_, but its data type is Tuple. In other words, this behaves as a tuple, but it does not have the same representation. It's for optimization purposes. Where it becomes really tricky is that the type of this object is dependent, so it can't be used for pattern matching. However, it is currently specified as inheriting the _tuple_t<T...> type, which allows one to pattern match in overloaded functions. tuple_c<T, v...>: A variable template returning a tuple containing integral constants. This returns an object of type _tuple_c<T, v...>, which is not the same as _tuple<something...>. It behaves like a tuple, but has a different representation. For optimization purposes too. Other components follow similar conventions. For example, _range<T, from, to>: The type of a range containing IntegralConstants of data type T spanning the given interval. Range: The generalized data type of _range<...>. make_range(from, to): Create a _range<common data type(from,to), from, to>. range(from, to): Equivalent to make_range(from, to), but deprecated because I'd like it to replace `_range`. range_c<T, from, to>: Shortcut to create a range of IntegralConstants. This is similar to vector_c in the MPL. And so it goes. Writing this, perhaps it would make sense to simply replace `_range` by `range`, `_tuple` by `tuple` and etc.
- // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? I think you should probably avoid using these constructs in the user documentation of other parts of the library. It's just a distraction, so it's better to rely on standard components, which users probably already understand.
The problem is that `assert` is not define when NDEBUG is defined, but I want my tests to fire up all the time. Since these examples are Doxygen'd out of actual source files, the macros end up in the documentation. Basically, If I could redefine `assert` to be `BOOST_HANA_RUNTIME_CHECK` in those test files, I'd be really happy. Would it be against good software craftsmanship to write ... include all you need ... #ifndef assert # define assert(...) BOOST_HANA_RUNTIME_CHECK(__VA_ARGS__) #endif
- Is there a reason for using length instead of size, which would be more idiomatic in C++?
Oversight caused by personal preference. I guess I should change that.
- Amphibian algorithms!!!??? Okay, I guess the name is kind of clever. I can't say that I really like it, though.
If you have anything better to propose, I'm all ears.
- foldl/foldr. I really hate these names. I'd prefer fold/reverse_fold, but even fold_left/fold_right would be better.
I personnally hate reverse_fold, since I don't see how it is a "reverse" fold. It's just a fold with different _associativity_ properties. As for fold_right and fold_left, I guess it comes down to personal preference. I opened a "poll" on GitHub to settle this. See [1].
- count is the equivalent of std::count_if, not std::count. - find/lookup should be find_if/find
You're right. It's sometimes hard to set aside personal preferences for the greater good, but I'll do it :-).
- In general I would expect any algorithm that takes a single element for comparison to have both f and f_if forms.
It is possible that a structure can do lookup by equality but not by any predicate, so it wouldn't be able to provide both. But do you have an example in mind of a place where there's an *_if variant missing in Hana? It would almost surely be an oversight.
- sort(predicate): shouldn't this be sort(sequence)?
Typo; thanks for reporting. Louis [1]: https://github.com/ldionne/hana/issues/18
Louis Dionne <ldionne.2 <at> gmail.com> writes:
Steven Watanabe <watanabesj <at> gmail.com> writes:
[...] - Is there a reason for using length instead of size, which would be more idiomatic in C++?
Oversight caused by personal preference. I guess I should change that.
Hmm, on second thought, length applies to any Foldable, not only to sequences. There might be a case where length is meaningful but not size (or vice-versa)? What if I provided both methods, one as an alias to the other? Louis
AMDG On 03/05/2015 12:02 PM, Louis Dionne wrote:
Steven Watanabe <watanabesj <at> gmail.com> writes:
I've just glanced over the main page of the documentation and I had a few comments:
- _tuple<Person, Car, City> Historically names beginning with _ are used for placeholders. i.e. in Boost.Bind/Lambda/Phoenix/Parameter. Is there a good reason not to call it tuple?
It is because of other constructs in Hana like `tuple_t<Types...>` which are variable templates and whose type is not specified. I have not found a good naming convention for variable templates and types yet. I'll sketch out the current state of affairs, and perhaps someone can suggest a convention that would work well.
I see. You have too many similar names. I'm not fond of it, but I can't think of anything better off the top of my head.
- // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? <snip>
The problem is that `assert` is not define when NDEBUG is defined, but I want my tests to fire up all the time. Since these examples are Doxygen'd out of actual source files, the macros end up in the documentation. Basically, If I could redefine `assert` to be `BOOST_HANA_RUNTIME_CHECK` in those test files, I'd be really happy. Would it be against good software craftsmanship to write
... include all you need ...
#ifndef assert # define assert(...) BOOST_HANA_RUNTIME_CHECK(__VA_ARGS__) #endif
It won't work. assert is still defined with NDEBUG. It's just defined to do nothing. Personally, I'd just use assert and make sure that NDEBUG is not defined. It isn't really important though, and I don't think it's a good idea to put ugly workarounds in examples, since the whole point of examples is to be relatively easy to understand.
- foldl/foldr. I really hate these names. I'd prefer fold/reverse_fold, but even fold_left/fold_right would be better.
I personally hate reverse_fold, since I don't see how it is a "reverse" fold. It's just a fold with different _associativity_ properties. As for fold_right and fold_left, I guess it comes down to personal preference. I opened a "poll" on GitHub to settle this. See [1].
I see. I think of the algorithm as starting with the state and merging in successive elements. foldl starts at the beginning of the sequence and works it way to the end, while foldr starts at the end and works its way to the beginning. It sounds like the difference is that you're thinking of fold as a single mathematical operation, instead.
- count is the equivalent of std::count_if, not std::count. - find/lookup should be find_if/find
You're right. It's sometimes hard to set aside personal preferences for the greater good, but I'll do it :-).
I wouldn't really object if you only provided predicate forms. The problem is that some algorithms have only a predicate form, while others have both predicate and value forms. If you do provide both, than you need a consistent naming convention, and while f/f_if aren't the greatest names ever, they will be familar to most C++ programmers.
- In general I would expect any algorithm that takes a single element for comparison to have both f and f_if forms.
It is possible that a structure can do lookup by equality but not by any predicate, so it wouldn't be able to provide both.
That seems like a serious limitation. Logically find(s, x) should be equivalent to find(s, [](auto y) { return x == y } ) Also, your Searchable seems to be based on predicates, so I'm not sure how such a structure would work with your library.
But do you have an example in mind of a place where there's an *_if variant missing in Hana? It would almost surely be an oversight.
replace only seems to have a predicate form. In Christ, Steven Watanabe
Steven Watanabe <watanabesj <at> gmail.com> writes:
AMDG
On 03/05/2015 12:02 PM, Louis Dionne wrote:
Steven Watanabe <watanabesj <at> gmail.com> writes:
I've just glanced over the main page of the documentation and I had a few comments:
- _tuple<Person, Car, City> Historically names beginning with _ are used for placeholders. i.e. in Boost.Bind/Lambda/Phoenix/Parameter. Is there a good reason not to call it tuple?
It is because of other constructs in Hana like `tuple_t<Types...>` which are variable templates and whose type is not specified. I have not found a good naming convention for variable templates and types yet. I'll sketch out the current state of affairs, and perhaps someone can suggest a convention that would work well.
I see. You have too many similar names. I'm not fond of it, but I can't think of anything better off the top of my head.
- // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? <snip>
The problem is that `assert` is not define when NDEBUG is defined, but I want my tests to fire up all the time. Since these examples are Doxygen'd out of actual source files, the macros end up in the documentation. Basically, If I could redefine `assert` to be `BOOST_HANA_RUNTIME_CHECK` in those test files, I'd be really happy. Would it be against good software craftsmanship to write
... include all you need ...
#ifndef assert # define assert(...) BOOST_HANA_RUNTIME_CHECK(__VA_ARGS__) #endif
It won't work. assert is still defined with NDEBUG. It's just defined to do nothing.
Yes, of course, I know that. I don't know why I proposed that. Well, I could undefine assert and redefine it to my own macro, but that's probably a bad idea so I won't do it.
Personally, I'd just use assert and make sure that NDEBUG is not defined. It isn't really important though, and I don't think it's a good idea to put ugly workarounds in examples, since the whole point of examples is to be relatively easy to understand.
I just thought about another role of BOOST_HANA_RUNTIME_CHECK. It also gives me the guarantee that the expression that's being asserted upon is not an IntegralConstant. It can become very hard to track the IntegralConstantness of things because of their implicit conversion to their underlying value, so the assert macros also make sure I'm expecting the right thing. The type of assertion I use in the documentation is actually a great source of clarity as to what can be expected from the library. For example: (untested) // can only be known at runtime std::vector<int> vs{1,2,3}; BOOST_HANA_RUNTIME_CHECK(!vs.empty()); // can be known at compile-time with an IntegralConstant auto i = int_<1>; // auto j = int_<3>; // notice no constexpr BOOST_HANA_CONSTANT_CHECK(i != j); // can be known at compile-time, but not with an IntegralConstant. // it requires the arguments to be constexpr. constexpr int i = 1; constexpr int j = 3; static_assert(i != j, ""); // Would be equivalent to static_assert if constexpr lambdas were // supported. In other words, it's not constexpr but that's just // an implementation defect, not an intrinsic limitation. constexpr auto xs = tuple_c<int, 3,2,1>; BOOST_HANA_CONSTEXPR_ASSERT(sort(xs) == tuple_c<int, 1, 2, 3>); That being said, I agree 100% with you that the documentation should be devoid of unneeded tricks. I'm unsure whether I should just use assert or explain the different kinds of assertions. One problem with explaining them is that it requires a good understanding of foundational concepts that are covered at the end of the tutorial. I can't put these foundational concepts at the beginning of the tutorial, because people would run away screaming. Now you know my dilemma.
- count is the equivalent of std::count_if, not std::count. - find/lookup should be find_if/find
You're right. It's sometimes hard to set aside personal preferences for the greater good, but I'll do it .
I wouldn't really object if you only provided predicate forms. The problem is that some algorithms have only a predicate form, while others have both predicate and value forms. If you do provide both, than you need a consistent naming convention, and while f/f_if aren't the greatest names ever, they will be familar to most C++ programmers.
I understand. I have to provide both predicated and value-based forms because the value-based forms allow some rather heavy optimizations.
- In general I would expect any algorithm that takes a single element for comparison to have both f and f_if forms.
It is possible that a structure can do lookup by equality but not by any predicate, so it wouldn't be able to provide both.
That seems like a serious limitation. Logically find(s, x) should be equivalent to find(s, [](auto y) { return x == y } ) Also, your Searchable seems to be based on predicates, so I'm not sure how such a structure would work with your library.
I did not mean that Hana had this limitation, and it doesn't unless I'm forgetting something. I was speaking about a theoretical possibility, but I guess I was getting carried away.
But do you have an example in mind of a place where there's an *_if variant missing in Hana? It would almost surely be an oversight.
replace only seems to have a predicate form.
Noting that. There's some cleanup to be done in Functor if I adopt the systematic approach of algorithm -> searches with value algorithm_if -> searches with predicate Thanks, Louis
On 5 Mar 2015 at 19:02, Louis Dionne wrote:
- // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? I think you should probably avoid using these constructs in the user documentation of other parts of the library. It's just a distraction, so it's better to rely on standard components, which users probably already understand.
The problem is that `assert` is not define when NDEBUG is defined, but I want my tests to fire up all the time. Since these examples are Doxygen'd out of actual source files, the macros end up in the documentation. Basically, If I could redefine `assert` to be `BOOST_HANA_RUNTIME_CHECK` in those test files, I'd be really happy. Would it be against good software craftsmanship to write
... include all you need ...
#ifndef assert # define assert(...) BOOST_HANA_RUNTIME_CHECK(__VA_ARGS__) #endif
I'd suggest an alternative course: these are "current state is impossible" assertions right? In which case fatal application exit is the only valid outcome, plus you want them always there even in optimised builds, and ideally you want some sort of useful error message. You may find my BOOST_AFIO_THROW_FATAL(x) macro of use here https://github.com/BoostGSoC13/boost.afio/blob/master/include/boost/af io/detail/Utility.hpp#L135. It tries to throw an exception in a noexcept function first, and if that succeeds (e.g. MSVC) then it calls std::terminate. The print_fatal_exception_to_stderr() function dumps a stack trace to stderr on supported platforms, just to be very, very sure you get something debuggable. Most of AFIO's testing happens on a Jenkins CI to catch the really rare non-repeatable bugs, the ones not findable on your dev workstation, so having useful telemetry as to what went wrong is invaluable. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Niall Douglas <s_sourceforge <at> nedprod.com> writes:
On 5 Mar 2015 at 19:02, Louis Dionne wrote:
- // BOOST_HANA_RUNTIME_CHECK is equivalent to assert In that case, what is the point of using it instead of assert? I think you should probably avoid using these constructs in the user documentation of other parts of the library. It's just a distraction, so it's better to rely on standard components, which users probably already understand.
The problem is that `assert` is not define when NDEBUG is defined, but I want my tests to fire up all the time. Since these examples are Doxygen'd out of actual source files, the macros end up in the documentation. Basically, If I could redefine `assert` to be `BOOST_HANA_RUNTIME_CHECK` in those test files, I'd be really happy. Would it be against good software craftsmanship to write
... include all you need ...
#ifndef assert # define assert(...) BOOST_HANA_RUNTIME_CHECK(__VA_ARGS__) #endif
I'd suggest an alternative course: these are "current state is impossible" assertions right? In which case fatal application exit is the only valid outcome, plus you want them always there even in optimised builds, and ideally you want some sort of useful error message.
The *_CHECK macros in Hana are just meant to be used for unit testing. They should be enabled in all build configurations so I can test both the Debug and Release modes. Currently, BOOST_HANA_RUNTIME_CHECK(expr) is defined (roughly) as if (!expr) { std::cerr << "some useful error message"; std::abort(); } Of course it is less naive PP-wise, but that's the gist of it.
You may find my BOOST_AFIO_THROW_FATAL(x) macro of use here https://github.com/BoostGSoC13/boost.afio/blob/master/include/boost/af io/detail/Utility.hpp#L135. It tries to throw an exception in a noexcept function first, and if that succeeds (e.g. MSVC) then it calls std::terminate.
The print_fatal_exception_to_stderr() function dumps a stack trace to stderr on supported platforms, just to be very, very sure you get something debuggable. Most of AFIO's testing happens on a Jenkins CI to catch the really rare non-repeatable bugs, the ones not findable on your dev workstation, so having useful telemetry as to what went wrong is invaluable.
Thanks, I was wishing for a stack trace just earlier today. I'll take a look. Louis
On 6 Mar 2015 at 1:11, Louis Dionne wrote:
I'd suggest an alternative course: these are "current state is impossible" assertions right? In which case fatal application exit is the only valid outcome, plus you want them always there even in optimised builds, and ideally you want some sort of useful error message.
The *_CHECK macros in Hana are just meant to be used for unit testing. They should be enabled in all build configurations so I can test both the Debug and Release modes. Currently, BOOST_HANA_RUNTIME_CHECK(expr) is defined (roughly) as
if (!expr) { std::cerr << "some useful error message"; std::abort(); }
Of course it is less naive PP-wise, but that's the gist of it.
Ah, then I'd urge you to use BOOST_CHECK/BOOST_REQUIRE which will spit out the results of all your tests into an XML file that Jenkins CI can display on a pretty graph. Then you can get Hana being nightly soak tested for compilation time/memory consumption regressions etc. You don't need Boost.Test necessarily for this, yet to be renamed BindLib has a threadsafe CATCH fork wrapped into Boost Test emulation macros. CATCH is totally header only, my threadsafe fork you can fetch as one giant single standalone include file at: https://github.com/ned14/Catch-ThreadSafe/blob/develop/single_include/ catch.hpp Just drop that into your git repo. No dependencies needed. If you want a preformed set of Boost test macros which thunk into threadsafe CATCH, that can be found at: https://github.com/ned14/Boost.BindLib/blob/master/include/boost/test/ unit_test.hpp Which is also header only, I even use some undefined behaviour to avoid you having to bother with with defining your own main(). Oh, and CATCH prints your unit testing results in pretty colours to the console. Plus you can run unit test filters, useful when you want to narrow into a very small part of the test suite. Much nicer than std:cerr :) Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
On Thu, Mar 5, 2015 at 6:41 AM, Louis Dionne <ldionne.2@gmail.com> wrote:
The library is available at [1] and the documentation at [2]. Comments should be directed to this mailing list, while bugs and other similar problems should be directed to the GitHub issue tracker. Please participate, especially if you have interest and/or experience in metaprogramming; after all, you represent the target audience for Hana.
Thank you, Louis Dionne
[1]: https://github.com/ldionne/hana [2]: http://ldionne.github.io/hana/
Looking great. I do have one (imo, very big) issue though, but one that can be resolved. I notice you are still doing things like: static_assert(pointers == tuple_t<Car*, City*, void*>, ""); I think I brought up the subtle problem with this a CppNow last year. Because == is used, which is an unqualified function call, it means that ADL takes place. Because ADL takes place, it means that all associated namespaces need to be considered. Because tuple_t<...> yields an instance of _tuple<...>, if I understand correctly from your current description, included in those associated namespaces are things like all of the base classes of template arguments of the types involved (in this case, any base classes of Car and City). What this implies is that simply by writing pointer == tuple_t<Car*,...>, the effect is that the type "Car" is implicitly instantiated at this point (if it were template instantiation), because the compiler needs to see if there are base classes in order to properly form the set of associated namespaces! In this particular example it might not be too apparent why this is so bad, but in the general case, instantiating such types that are involved can cause a number of serious issues: 1) Perhaps the most obvious is that instantiation can potentially fail (and therefore cause a compile error even though it doesn't look like the type would be used). 2) They can cause considerable compile-time overhead for a template definition's instantiation that otherwise might not be used. 3) Worst case, but probably the least likely. It can compile but produce strange results in the program in a very subtle way, not even necessarily directly at this point in code, due to the type being instantiated "prematurely" with respect to what the user may have expected. This can can cause problems, for instance, if certain types are still incomplete at this point in the translation unit, or if important functions/overloads have not yet been declared, etc. Because of memoization, at the point that the user thinks they are first instantiating the template, they will get an instantiation that they likely did not expect. As great as it is to be able to use operators, I don't think it should be recommended (or probably supported, unless these issues can be fixed). As I see it right now, ADL here should *always* be avoided, whether it's an operator or not, for similar reasons. Instead, it probably makes sense to have all "functions" be global function objects and/or variable templates so that people can't accidentally use ADL. Similarly, that point needs to be stressed for users who wish to create their own metafunctions. This is an unfortunate subtlety that would be very much important for metaprogrammers to understand so that they too wouldn't accidentally fall victim to them. An alternative to this kind of fix that might allow operators to still be used is to make the tuple type not (directly) be a template instantiation with template arguments by instead (as an example) making the tuple type a non-template local type that is declared inside of a function template. You'd return an instance of this type from the function, and use a c++14 auto-deduced return type. The operator would be defined in that function template's namespace or in another associated namespace of that local type. The downside of this approach is that (I believe) it removes any ability to have something like a namespace-scope _tuple<T, U> type/alias be used in a function parameter list in the case that T and U are to be deduced, unless there is some other trick that can be thought of. I'm sure these problems can be resolved, but I definitely think it is important to fully address them before formal review. The subtlety of the problems and the ease of misuse makes things really scary to me and I would be worried if a lot of library code ended up getting written on top of this without solutions in place. If any of this is already solved by way of tricks that I'm not aware of (I haven't looked through the source yet), then just make sure people know that they, too, must utilitze such tricks when making their own hana-style metafunctions. -- -Matt Calabrese
AMDG On 03/05/2015 01:15 PM, Matt Calabrese wrote:
<snip>What this implies is that simply by writing pointer == tuple_t<Car*,...>, the effect is that the type "Car" is implicitly instantiated at this point (if it were template instantiation), because the compiler needs to see if there are base classes in order to properly form the set of associated namespaces!
In this particular example it might not be too apparent why this is so bad, but in the general case, instantiating such types that are involved can cause a number of serious issues: 1) Perhaps the most obvious is that instantiation can potentially fail (and therefore cause a compile error even though it doesn't look like the type would be used).
I'm glad you brought this up. This problem is not academic. I've seen real bugs reported against at least one Boost library because of something like this.
2) They can cause considerable compile-time overhead for a template definition's instantiation that otherwise might not be used. 3) Worst case, but probably the least likely. It can compile but produce strange results in the program in a very subtle way, not even necessarily directly at this point in code, due to the type being instantiated "prematurely" with respect to what the user may have expected. This can can cause problems, for instance, if certain types are still incomplete at this point in the translation unit, or if important functions/overloads have not yet been declared, etc. Because of memoization, at the point that the user thinks they are first instantiating the template, they will get an instantiation that they likely did not expect.
In Christ, Steven Watanabe
Matt Calabrese <rivorus <at> gmail.com> writes:
On Thu, Mar 5, 2015 at 6:41 AM, Louis Dionne <ldionne.2 <at> gmail.com> wrote:
[...]
I'm sure these problems can be resolved, but I definitely think it is important to fully address them before formal review. The subtlety of the problems and the ease of misuse makes things really scary to me and I would be worried if a lot of library code ended up getting written on top of this without solutions in place.
If any of this is already solved by way of tricks that I'm not aware of (I haven't looked through the source yet), then just make sure people know that they, too, must utilitze such tricks when making their own hana-style metafunctions.
Yes, this is already taken care of and no unfortunate instantiations will take place. The downside is that `decltype(tuple_t<T...>)` is an unspecified dependent type that only _inherits_ `_tuple<T...>`. It is still possible to use pattern matching in overloads as follows: template <typename ...T> void f(hana::_tuple_t<T...>) { // ... } You can see how this is implemented here: http://goo.gl/iISNpb And the unit test here: http://goo.gl/sBqMZo I'm playing with fire, I know :-). I read the process of ADL very carefully when I thought about this, but it is also possible that I'm exploiting a Clang bug. What do you think? Louis P.S.: Thanks for letting me know of this issue at C++Now.
On Thu, Mar 5, 2015 at 12:56 PM, Louis Dionne <ldionne.2@gmail.com> wrote:
Yes, this is already taken care of and no unfortunate instantiations will take place.
Awesome!!!
The downside is that `decltype(tuple_t<T...>)` is an unspecified dependent type that only _inherits_ `_tuple<T...>`.
I'm playing with fire, I know :-). I read the process of ADL very carefully when I thought about this, but it is also possible that I'm exploiting a Clang bug. What do you think?
Hmm, I think that really might be relying on a clang bug, but I don't have the standard in front of me right now. From my understanding, if you inherit from _tuple<T...>, then "T..." again needs to be considered for the list of associated namespaces. -- -Matt Calabrese
Matt Calabrese <rivorus <at> gmail.com> writes:
On Thu, Mar 5, 2015 at 12:56 PM, Louis Dionne <ldionne.2 <at> gmail.com> wrote:
Yes, this is already taken care of and no unfortunate instantiations will take place.
Awesome!!!
The downside is that `decltype(tuple_t<T...>)` is an unspecified dependent type that only _inherits_ `_tuple<T...>`.
I'm playing with fire, I know . I read the process of ADL very carefully when I thought about this, but it is also possible that I'm exploiting a Clang bug. What do you think?
Hmm, I think that really might be relying on a clang bug, but I don't have the standard in front of me right now. From my understanding, if you inherit from _tuple<T...>, then "T..." again needs to be considered for the list of associated namespaces.
I just checked on GCC and MSVC (online compilers) and it works too. If you want to check for yourself, I wrote a gist at [1] that is a self-contained test. Actually, I would appreciate if someone with access to more exotic compilers (Intel for example) could try compiling it just to make sure. I also double-checked the standard (ok, cppreference.org [2] to be fair). For what follows, let's denote by Hidden the type `_tuple_t<T...>::_` as can be seen in the gist. Here's my reading of it (the standardese is indented):
[...] For every argument in a function call expression and for every template template argument of a template function, its type is examined to determine the associated set of namespaces and classes that it will add to the lookup
1) For arguments of fundamental type, the associated set of namespaces and classes is empty
We don't care, Hidden is not a fundamental type.
2) For arguments of class type (including union), the set consists of a) The class itself b) All of its direct and indirect base classes c) If the class is a member of another class, the class of which it is a member d) The innermost enclosing namespaces in the classes added to the set
a) We're ok; Hidden can be instantiated safely. b) We're ok, `_tuple_t<T...>` can be instantiated safely. c) We're ok; Hidden is a member of `_tuple_t<T...>`, but this can be instantiated safely. d) Don't care.
3) For arguments whose type is a class template specialization, in addition to the class rules, the following types are examined and their associated classes and namespaces are added to the set a) [...] b) [...] c) [...]
We don't care about any of this, because Hidden is not a specialization.
[bunch of other clauses that clearly do not apply to us]
So from my reading, it looks like we're good. Louis [1]: https://gist.github.com/ldionne/b022f25ee87ebc2ff839 [2]: http://en.cppreference.com/w/cpp/language/adl
On Thu, Mar 5, 2015 at 1:28 PM, Louis Dionne <ldionne.2@gmail.com> wrote:
I also double-checked the standard (ok, cppreference.org [2] to be fair). For what follows, let's denote by Hidden the type `_tuple_t<T...>::_` as can be seen in the gist. Here's my reading of it (the standardese is indented):
Cool, I just looked it up in the standard as well, and I think you're right. I thought the associated namespaces of the bases were considered, but it's only the namespaces of the associated base classes that are considered. -- -Matt Calabrese
On Mar 5, 2015, at 4:28 PM, Louis Dionne <ldionne.2@gmail.com> wrote:
The downside is that `decltype(tuple_t<T...>)` is an unspecified dependent type that only _inherits_ `_tuple<T...>`.
I'm playing with fire, I know . I read the process of ADL very carefully when I thought about this, but it is also possible that I'm exploiting a Clang bug. What do you think?
Hmm, I think that really might be relying on a clang bug, but I don't have the standard in front of me right now. From my understanding, if you inherit from _tuple<T...>, then "T..." again needs to be considered for the list of associated namespaces.
I just checked on GCC and MSVC (online compilers) and it works too. If you want to check for yourself, I wrote a gist at [1] that is a self-contained test. Actually, I would appreciate if someone with access to more exotic compilers (Intel for example) could try compiling it just to make sure.
I can verify that the linked gist compiles and runs successfully on the latest Intel C++ compiler. [jasonr@dirac:~/Downloads]$ icpc --version icpc (ICC) 15.0.1 20141022 Copyright (C) 1985-2014 Intel Corporation. All rights reserved. Jason
Jason Roehm <jasonr <at> 3db-labs.com> writes:
[...]
I can verify that the linked gist compiles and runs successfully on the latest Intel C++ compiler.
[jasonr <at> dirac:~/Downloads]$ icpc --version icpc (ICC) 15.0.1 20141022 Copyright (C) 1985-2014 Intel Corporation. All rights reserved.
Awesome! Thank you very much! Louis
On 3/5/2015 9:41 AM, Louis Dionne wrote:
Dear Boost,
As some may be aware of, I am currently working on a metaprogramming library called Hana, with the intention of proposing it for inclusion in Boost. The purpose of that library is to act as a toolbox for expressing computations on both types (like the MPL) and heterogeneous values (like Fusion). The library is built around C++14 idioms and implementation techniques to maximize expressiveness and performance.
I am now requesting feedback from the community, with the intention of asking for a formal review in the next months. A similar review was asked for in last August. The library has undergone several modifications since then, both to address issues raised during the review and for general improvement. Here are some issues that were raised during the review and addressed:
- Usage of names and terms unknown to C++ programmers: Efforts were made to make this better, and several functions were renamed (`fmap` is now `transform`). When possible, the documentation also uses terms more familiar to C++ programmers, like concept instead of "type class".
- The order of the arguments to some algorithms was unfortunate for C++. It was consistent with Haskell, but it turned out to be cumbersome in C++. This is changed in most places.
- Inability to easily implement individual algorithms: This is fixed, and algorithms are now standalone structures using tag-dispatching, almost exactly as in Fusion.
- Lack of a good introductory tutorial: A lot of work has gone into improving both the tutorial and the reference documentation.
- Lack of support for mainstream compilers: The library is now almost fully functional with Clang 3.5. A GCC 4.9 port with reduced functionality is also underway on the `redux` branch.
The library is available at [1] and the documentation at [2]. Comments should be directed to this mailing list, while bugs and other similar problems should be directed to the GitHub issue tracker. Please participate, especially if you have interest and/or experience in metaprogramming; after all, you represent the target audience for Hana.
Thank you, Louis Dionne
[1]: https://github.com/ldionne/hana [2]: http://ldionne.github.io/hana/
In the Quick Start:
auto stuff = make_tuple(Person{"Louis"}, Car{"Toyota"}, City{"Quebec"}); Notice how the auto keyword is used when defining xs;...
It should be:
Notice how the auto keyword is used when defining 'stuff';...
Edward Diener <eldiener <at> tropicsoft.com> writes:
[...]
In the Quick Start:
auto stuff = make_tuple(Person{"Louis"}, Car{"Toyota"}, City{"Quebec"}); Notice how the auto keyword is used when defining xs;...
It should be:
Notice how the auto keyword is used when defining 'stuff';...
Thank you, fixed! Louis
Le 05/03/15 15:41, Louis Dionne a écrit :
Dear Boost,
As some may be aware of, I am currently working on a metaprogramming library called Hana, with the intention of proposing it for inclusion in Boost. The purpose of that library is to act as a toolbox for expressing computations on both types (like the MPL) and heterogeneous values (like Fusion). The library is built around C++14 idioms and implementation techniques to maximize expressiveness and performance. Hi and thanks in advance for your work. I am now requesting feedback from the community, with the intention of asking for a formal review in the next months. A similar review was asked for in last August. The library has undergone several modifications since then, both to address issues raised during the review and for general improvement. Here are some issues that were raised during the review and addressed:
- Usage of names and terms unknown to C++ programmers: Efforts were made to make this better, and several functions were renamed (`fmap` is now `transform`). When possible, the documentation also uses terms more familiar to C++ programmers, like concept instead of "type class". I'm not sure the use of the term "concept" instead of "type class" is appropriated (given that the C++ standard is defining concepts in a different way). Hana "type class" is based, as Concept C++0x, on signatures. An instance "type" of a "type class" needs a mapping of the signature. I can live with the term TypeClass. Nevertheless if you don't want to use it I will suggest you the terms "MappedConcept" or "SignaturedConcept" instead of "Concept".
- The order of the arguments to some algorithms was unfortunate for C++. It was consistent with Haskell, but it turned out to be cumbersome in C++. Just for curiosity, could you give some examples of these changes and why it was cumbersome? This is changed in most places.
- Inability to easily implement individual algorithms: This is fixed, and algorithms are now standalone structures using tag-dispatching, almost exactly as in Fusion. Just for curiosity, could you give some examples of these changes and why it was difficult before the changes?
- Lack of a good introductory tutorial: A lot of work has gone into improving both the tutorial and the reference documentation.
I appreciate what has been done already to improve the tutorial. Next follows some comments about the design. DataTypes and TypeClasses ---------------------- I appreciate what has been done already. I have some trouble with the "datatype" use. If I understand it correctly, the type you map to a "type class" is not the type itself but its datatype (which can be the same). In Haskell, type classes can be universally quantified or not. E.g. the "type class" Eq is not universally quantified class Eq a `(==) :: a -> a -> Bool (/=) :: a -> a -> Bool while the "type class" Functor it is universally quantified class Functor f where fmap :: (a -> b) -> f a -> f b That means that the instance mapping for Eq is from types (*) and the instance mapping for Functor is for type constructors having one parameter (* ->*). Let me show the instance mapping for Either in Haskell (Eq a, Eq b) => Eq (Either a b) Functor (Either a) Note the difference. In the first case the instance is Either a b. In the second it is Either a. I don't see this nuance in your library. The datatype of left<A>/right<B> is Either, and the instance of Comparable and Functor is always Either. BTW, I'm missing a type either<A,B> see below I'm wondering if the library shouldn't make this difference and make either<A,B> be an instance of Comparable and either<A,_> be an instance of Functor, where either<A,_> stands for the universal type constructor having a parameter. Compile-time error reporting -------------------- I would expect that the library provide some king of "TypeClass" check use (As Eric's Range library does with Concepts) so that the compile time errors are more explicit. Unnamed data types ----------------- I'm missing, between other, the concrete types _either<A,B> and _maybe<T>, as we have _pair<A,B>. How the user can declare a structure having data members with these data types? About a pure type meta programming sub-library Hana/Meta ---------------------------------------------------- While I agree that it is good to be able to define the algorithms only once for types and values, I find the syntax cumbersome when the user wants only to work at the meta-programming level. I wonder if the library shouldn't contain a sublibrary Hana/Meta that defines in a meta namespace all the algorithms/types that work directly on types and integral constants. Instead of defining a hana::tuple_t, I suggest to define it in meta::tuple that works only with types and a meta::transform that works only on types. This will allow to write ([1]) static_assert( meta::transform<meta:: tuple<int, char const, void>, std::add_pointer>{} == meta::tuple<int*, char const*, void*>{} , ""); instead of static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::metafunction<std::add_pointer>) == hana::tuple_t<int*, char const*, void*> , ""); The definition of meta::transform will just do the steps 2 and 3 of the process you describe: 1. Wrap the types with |type<...>| so they become values 2. Apply whatever type transformation |F| by using |metafunction<F>| 3. Unwrap the result with |decltype(...)::type| namespace meta { template <class Tuple, class F> using transform = |decltype(|hana::transform(Tuple{}, ||hana::metafunction<F>))::type } An additional advantage of having this Meta library is that it can be defined using just a C++11 compiler, as it is done in Eric's Meta library. Best, Vicente [1] the name could be also meta::list.
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
[...]
I appreciate what has been done already to improve the tutorial. Next follows some comments about the design.
DataTypes and TypeClasses ---------------------- I appreciate what has been done already. I have some trouble with the "datatype" use. If I understand it correctly, the type you map to a "type class" is not the type itself but its datatype (which can be the same).
That is correct. Hana also calls them generalized types, because they are like types, but ones that don't care about the actual representation (memory layout) of the objects. In a sense, a data type is like a C++ concept, but one that would only be modeled by a couple of types that would be exactly the same up to representation differences.
In Haskell, type classes can be universally quantified or not. E.g. the "type class" Eq is not universally quantified
[...]
That means that the instance mapping for Eq is from types (*) and the instance mapping for Functor is for type constructors having one parameter (* ->*).
[...]
I don't see this nuance in your library. [...]
This is because this nuance is _voluntarily_ left aside. More generally, the design choice I made was to leave parametric data types to the documentation level only, as is documented in the section about generalized data types[1]. As I already said on this list during the last informal review, what I make is a tradeoff between mathematical correctness and usability of the library. While Hana provides structures that satisfy the laws rigorously, I want users to be able to use those structures in a quick and dirty way as a mean of being more productive when needed. For example, I would not object to someone writing [pseudocode]: auto to_string = [](auto x) { /* convert x to a std::string */ }; auto xs = hana::make_tuple(1, 2.2, "abc"); auto ys = hana::transform(xs, to_string); Since `1`, `2.2` and `"abc"` do not share a common data type and the signature of `transform` is (for a Functor F) transform : F(T) x (T -> U) -> F(U) , the above should normally be ill-formed. However, the library makes such usage possible because I kept in mind that we're working in a "dirty" heterogeneously-typed context. Bottom line: Concepts in Hana are rigorously specified and coherent internally. You are free to bypass them when you need to, because, while it would always be possible to do it, it would be painful to always justify how operations are mathematically correct [2].
Compile-time error reporting --------------------
I would expect that the library provide some king of "TypeClass" check use (As Eric's Range library does with Concepts) so that the compile time errors are more explicit.
Doing this for all parameters of all functions is intractable due to the heterogeneous context, but basic support could be added easily. I'm promoting this on my todo list.
Unnamed data types ----------------- I'm missing, between other, the concrete types _either<A,B> and _maybe<T>, as we have _pair<A,B>. How the user can declare a structure having data members with these data types?
You can't if you don't know beforehand whether it's going to be a `just` or a `nothing`. Hence, it is useless to create such a data member _explicitly_. The reason is that whether a Maybe is a `just` or a `nothing` is encoded in its type, so you have to know it if you want to _explicitly_ declare such a data member. That's the downside. The upside is that it allows you to interact with heterogeneous objects, which was the initial goal. There's an example of how this can be used to encode SFINAE-failures at [3].
About a pure type meta programming sub-library Hana/Meta ----------------------------------------------------
While I agree that it is good to be able to define the algorithms only once for types and values, I find the syntax cumbersome when the user wants only to work at the meta-programming level.
I think you overestimate how often you actually need to do computations on types. We were just accustomed by the MPL to write everything with raw types, but this is not the only way to do it. The only times we actually need to manipulate types is when we use <type_traits>, which does not represent the largest part of metaprogramming in my experience.
I wonder if the library shouldn't contain a sublibrary Hana/Meta that defines in a meta namespace all the algorithms/types that work directly on types and integral constants.
Instead of defining a hana::tuple_t, I suggest to define it in meta::tuple that works only with types and a meta::transform that works only on types.
This will allow to write ([1])
static_assert( meta::transform<meta:: tuple<int, char const, void>, std::add_pointer>{} == meta::tuple<int*, char const*, void*>{} , "");
instead of
static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::metafunction<std::add_pointer>) == hana::tuple_t<int*, char const*, void*> , "");
The definition of meta::transform will just do the steps 2 and 3 of the process you describe:
1. Wrap the types with |type<...>| so they become values 2. Apply whatever type transformation |F| by using |metafunction<F>| 3. Unwrap the result with |decltype(...)::type|
[...]
First of all, the first alternative will almost surely need to look more like: static_assert( meta::transform<meta::tuple<int, char const, void>, meta::quote<std::add_pointer>>{} == meta::tuple<int*, char const*, void*>{} , ""); Notice meta::quote. Now, if you compare with static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::metafunction<std::add_pointer>) == hana::tuple_t<int*, char const*, void*> , ""); , I think you have to admit the difference is tiny. Hana also provides integration with <type_traits>, which means that you can actually write: static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::traits::add_pointer) == hana::tuple_t<int*, char const*, void*> , ""); The difference is that with Hana, you would then need to use `decltype(...)::type` to get back the actual type. Again, my answer is that this is only required at some thin boundaries where you actually need the types. HOWEVER, there seem to be some demand for this from the community. I'll be very honest and direct with you and everyone else on this list: if this addition can make people feel more at home because it resembles the MPL, and if in turn that eases the process of making Hana part of Boost, then I could do it. However, on my part, I would find that it encourages people to leverage only the _tiny_ part of Hana that deals with type-level metaprogramming, and hence reduce what can be done with it to a small portion of its full power. Also, if I could be shown examples in which the 3-step process described above is really painful, and if those examples turned out not to simply be non-idiomatic Hana, I would add those facilities by the end of the day. On a more serious note, and because this issue has to be closed once and for all, I created a poll at [4] to resolve whether such facilities should be added. It is not a guarantee that I'll do it if people want it, but I'd like to have an idea of how badly people want it.
An additional advantage of having this Meta library is that it can be defined using just a C++11 compiler, as it is done in Eric's Meta library.
I understand they _could_ be implemented in C++11 only, but concretely they would use Hana as a backend and so they would need C++14. I would not reimplement those operations from scratch. Thanks for your comments and questions that never fail to challenge me, Vicente. Regards, Louis [1]: http://ldionne.github.io/hana/#tutorial-hetero [2]: For the example I gave, it would be possible, for example, to say that we're creating a Tuple of things that can be converted to a `std::string`. Let's call this data type `Stringizable`. Then, the data type of the tuple would be `Tuple(Stringizable)`, and the signature of transform that we would be using is transform : F(Stringizable) x (Stringizable -> std::string) -> F(std::string) Until I have a deeper formal understanding of the way this process of "intersecting the concepts of the objects in a sequence" works, which I'm working on as my bachelor's thesis, I'd rather keep Hana's concepts free of higher-order data types. Even if/when I'll have a deeper formal understanding, I would likely need language support to make this applicable. [3]: http://goo.gl/MgUIpl [4]: https://github.com/ldionne/hana/issues/19
Le 07/03/15 17:38, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes: I would appreciate a comment about the TypeClass to Concept renaming
[...]
I appreciate what has been done already to improve the tutorial. Next follows some comments about the design.
DataTypes and TypeClasses ---------------------- I appreciate what has been done already. I have some trouble with the "datatype" use. If I understand it correctly, the type you map to a "type class" is not the type itself but its datatype (which can be the same). That is correct. Hana also calls them generalized types, because they are like types, but ones that don't care about the actual representation (memory layout) of the objects. In a sense, a data type is like a C++ concept, but one that would only be modeled by a couple of types that would be exactly the same up to representation differences.
I see much more you datatype as a tag. Do you have an equivalence in Haskell to your datatype/generalized type?
In Haskell, type classes can be universally quantified or not. E.g. the "type class" Eq is not universally quantified
[...]
That means that the instance mapping for Eq is from types (*) and the instance mapping for Functor is for type constructors having one parameter (* ->*).
[...]
I don't see this nuance in your library. [...] This is because this nuance is _voluntarily_ left aside. More generally, the design choice I made was to leave parametric data types to the documentation level only, as is documented in the section about generalized data types[1].
I can understand that you want to let the constraint as comments or documentation as the Standard library does. However I expect that implementations do a check at compile time when possible.
As I already said on this list during the last informal review, what I make is a tradeoff between mathematical correctness and usability of the library. While Hana provides structures that satisfy the laws rigorously, I want users to be able to use those structures in a quick and dirty way as a mean of being more productive when needed. For example, I would not object to someone writing [pseudocode]:
auto to_string = [](auto x) { /* convert x to a std::string */ }; auto xs = hana::make_tuple(1, 2.2, "abc"); auto ys = hana::transform(xs, to_string);
Since `1`, `2.2` and `"abc"` do not share a common data type and the signature of `transform` is (for a Functor F)
transform : F(T) x (T -> U) -> F(U)
, the above should normally be ill-formed. However, the library makes such usage possible because I kept in mind that we're working in a "dirty" heterogeneously-typed context. Bottom line: I don't think heterogeneous types are dirty. We need just a different type of function (Overloaded) to transform them.
if you have an heterogeneous type as pair for example, the mathematical transform function should transform : pair(T,U) x (T -> R) x (U -> S) -> pair(R, S) As C++ has overloaded functions we don't need to pass two functions, but just an overloaded function.
Concepts in Hana are rigorously specified and coherent internally. You are free to bypass them when you need to, because, while it would always be possible to do it, it would be painful to always justify how operations are mathematically correct [2].
Compile-time error reporting --------------------
I would expect that the library provide some king of "TypeClass" check use (As Eric's Range library does with Concepts) so that the compile time errors are more explicit. Doing this for all parameters of all functions is intractable due to the heterogeneous context, but basic support could be added easily. I'm promoting this on my todo list.
Unnamed data types ----------------- I'm missing, between other, the concrete types _either<A,B> and _maybe<T>, as we have _pair<A,B>. How the user can declare a structure having data members with these data types? You can't if you don't know beforehand whether it's going to be a `just` or a `nothing`. Hence, it is useless to create such a data member _explicitly_. The reason is that whether a Maybe is a `just` or a `nothing` is encoded in its type, so you have to know it if you want to _explicitly_ declare such a data member. That's the downside. The upside is that it allows you to interact with heterogeneous objects, which was the initial goal. There's an example of how this can be used to encode SFINAE-failures at [3]. How the fact to have either<A,B> and maybe<A> makes it more dificult to interact with heterogeneous objects?
About a pure type meta programming sub-library Hana/Meta ----------------------------------------------------
While I agree that it is good to be able to define the algorithms only once for types and values, I find the syntax cumbersome when the user wants only to work at the meta-programming level. I think you overestimate how often you actually need to do computations on types. We were just accustomed by the MPL to write everything with raw types, but this is not the only way to do it. The only times we actually need to manipulate types is when we use <type_traits>, which does not represent the largest part of metaprogramming in my experience. I have done a lot of meta-programming. Having the simpler syntax would be much appreciated.
I wonder if the library shouldn't contain a sublibrary Hana/Meta that defines in a meta namespace all the algorithms/types that work directly on types and integral constants.
Instead of defining a hana::tuple_t, I suggest to define it in meta::tuple that works only with types and a meta::transform that works only on types.
This will allow to write ([1])
static_assert( meta::transform<meta:: tuple<int, char const, void>, std::add_pointer>{} == meta::tuple<int*, char const*, void*>{} , "");
instead of
static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::metafunction<std::add_pointer>) == hana::tuple_t<int*, char const*, void*> , "");
The definition of meta::transform will just do the steps 2 and 3 of the process you describe:
1. Wrap the types with |type<...>| so they become values 2. Apply whatever type transformation |F| by using |metafunction<F>| 3. Unwrap the result with |decltype(...)::type|
[...] First of all, the first alternative will almost surely need to look more like:
static_assert( meta::transform<meta::tuple<int, char const, void>, meta::quote<std::add_pointer>>{} == meta::tuple<int*, char const*, void*>{} , "");
Notice meta::quote. I wonder if the meta::transform couldn't take care of quote.
Now, if you compare with
static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::metafunction<std::add_pointer>) == hana::tuple_t<int*, char const*, void*> , "");
, I think you have to admit the difference is tiny. Hana also provides integration with <type_traits>, which means that you can actually write:
static_assert( hana::transform(hana::tuple_t<int, char const, void>, hana::traits::add_pointer) == hana::tuple_t<int*, char const*, void*> , "");
The difference is that with Hana, you would then need to use `decltype(...)::type` to get back the actual type. Again, my answer is that this is only required at some thin boundaries where you actually need the types.
HOWEVER, there seem to be some demand for this from the community. I'll be very honest and direct with you and everyone else on this list: if this addition can make people feel more at home because it resembles the MPL, and if in turn that eases the process of making Hana part of Boost, then I could do it. However, on my part, I would find that it encourages people to leverage only the _tiny_ part of Hana that deals with type-level metaprogramming, and hence reduce what can be done with it to a small portion of its full power.
Also, if I could be shown examples in which the 3-step process described above is really painful, and if those examples turned out not to simply be non-idiomatic Hana, I would add those facilities by the end of the day.
An additional advantage of having this Meta library is that it can be defined using just a C++11 compiler, as it is done in Eric's Meta library. I understand they _could_ be implemented in C++11 only, but concretely they would use Hana as a backend and so
On a more serious note, and because this issue has to be closed once and for all, I created a poll at [4] to resolve whether such facilities should be added. It is not a guarantee that I'll do it if people want it, but I'd like to have an idea of how badly people want it. Good idea. they would need C++14. I would not reimplement those operations from scratch.
Thanks for your comments and questions that never fail to challenge me, Vicente. You are welcome. Regards, Louis
[1]: http://ldionne.github.io/hana/#tutorial-hetero
[2]: For the example I gave, it would be possible, for example, to say that we're creating a Tuple of things that can be converted to a `std::string`. Let's call this data type `Stringizable`. Then, the data type of the tuple would be `Tuple(Stringizable)`, and the signature of transform that we would be using is
transform : F(Stringizable) x (Stringizable -> std::string) -> F(std::string)
Until I have a deeper formal understanding of the way this process of "intersecting the concepts of the objects in a sequence" works, which I'm working on as my bachelor's thesis, I'd rather keep Hana's concepts free of higher-order data types. Even if/when I'll have a deeper formal understanding, I would likely need language support to make this applicable. My point was more on how the library is checking the fist argument of Transform is a Functor and that the second argument is a "function" from
Agree, quoted traits are good syntactic sugar the Functor's underlying type T to another type U. transform : Functor<T> x (T -> U) -> Functor(U) If the implementation declares transform as auto transform = [] (auto F, auto Fun) Couldn't the the library check that the arguments passed in F and Fun respect the requirements? Vicente
[3]: http://goo.gl/MgUIpl [4]: https://github.com/ldionne/hana/issues/19
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 07/03/15 17:38, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
[...]
I see much more you datatype as a tag.
That's exactly what they are. However, Fusion and MPL did not see tags for what they are actually: a powerful way of lifting the type system one level higher up to make representation differences unimportant. Fusion and MPL only saw tags as part of their dispatching system. I think it's mostly a philosophical difference at this point.
Do you have an equivalence in Haskell to your datatype/generalized type?
No, but shooting from the hip you could approximate them with type classes. For example, the Tuple data type could be implemented as -- The different actual representations for tuples data Tuple0 = Tuple0 data Tuple1 a = Tuple1 a data Tuple2 a b = Tuple2 a b data Tuple3 a b c = Tuple3 a b c -- etc... -- The Tuple generalized type representing all those guys class Tuple t where len :: t -> Int instance Tuple Tuple0 where len _ = 0 instance Tuple (Tuple1 a) where len _ = 1 instance Tuple (Tuple2 a b) where len _ = 2 instance Tuple (Tuple3 a b c) where len _ = 3 -- etc... Admittedly, the above is missing something fundamental if we want to implement other functions like `head`, but that reaches the limit of my Haskell-fu. I think looking at Haskell's type families [1] might provide more insight.
[...]
This is because this nuance is _voluntarily_ left aside. More generally, the design choice I made was to leave parametric data types to the documentation level only, as is documented in the section about generalized data types[1].
I can understand that you want to let the constraint as comments or documentation as the Standard library does. However I expect that implementations do a check at compile time when possible.
Strictly speaking, a "check" is done at compile-time, in that you'll get a nasty compiler error if the types don't match. Nothing is "erased" and left to deal with by some runtime, if that's what you meant. Of course, in practice, Hana will static_assert in some places to make these errors more explicit.
As I already said on this list during the last informal review, what I make is a tradeoff between mathematical correctness and usability of the library. While Hana provides structures that satisfy the laws rigorously, I want users to be able to use those structures in a quick and dirty way as a mean of being more productive when needed. For example, I would not object to someone writing [pseudocode]:
auto to_string = [](auto x) { /* convert x to a std::string */ }; auto xs = hana::make_tuple(1, 2.2, "abc"); auto ys = hana::transform(xs, to_string);
Since `1`, `2.2` and `"abc"` do not share a common data type and the signature of `transform` is (for a Functor F)
transform : F(T) x (T -> U) -> F(U)
, the above should normally be ill-formed. However, the library makes such usage possible because I kept in mind that we're working in a "dirty" heterogeneously-typed context. Bottom line:
I don't think heterogeneous types are dirty. We need just a different type of function (Overloaded) to transform them.
if you have an heterogeneous type as pair for example, the mathematical transform function should
transform : pair(T,U) x (T -> R) x (U -> S) -> pair(R, S)
As C++ has overloaded functions we don't need to pass two functions, but just an overloaded function.
That's an interesting point of view. However, with this approach, you can't say that Pair is a Functor. It instead becomes a BiFunctor [2]. Furthermore, let's say you have a pair(T, T). transform is then transform : pair(T, T) x (T -> R) x (T -> S) -> pair(R, S) transform should hence still receive two functions, regardless of the fact that we could provide a single overloaded function. Let me now use a tuple instead of a pair as an example because it sticks more closely to what happens in Hana (Pair is not a Functor in Hana). transform then becomes: transform : Tuple(T1, ..., Tn) x (T1 -> R1) x ... x (Tn -> Rn) -> Tuple(R1, ..., Rn) First, if you use this approach, you can't say that Tuple is a Functor. It has to be a N-Functor, which is the N-argument equivalent to the BiFunctor. Furthermore, you have to provide N different functions to be able to transform it. So for example, when transforming a tuple(int, int, int), you would have to say transform(tuple(1, 2, 3), [](int i) { return i + 1; }, [](int i) { return i + 1; }, [](int i) { return i + 1; } ) That's not "heterogeneous" programming; it's just an equivalent way of writing r1 = f1(t1) r2 = f2(t2) ... rn = fn(tn) where `tk` are the elements of a tuple, and `fk` are the functions mapped on it by the N-Functor's `transform`. What we actually want is r1 = f(t1) r2 = f(t2) ... rn = f(tn) where `f` is defined as f : (intersection of the data types of the tuple's elements) -> (some other type) In other words, `f` is a function whose domain is "the set of all objects with which I can do X". If there are objects in the tuple that don't support "X", then the program is ill-formed. Concepts will put us much closer to this. The principle behind Hana's generalized types is really that we "lift" the types of the objects and then consider objects up-to-different-representations. I also think it can be seen as a quotient of the set of all types by the equivalence relation T ~ U if and only if T and U model exactly the same concepts in exactly the same way Concretely, the mathematical universe we're working with is not only a set; it's actually the C++ category where objects are Types and morphisms are functions. Hence, that "quotient" would have to also take morphisms into account. But I'm reaching the end of my math-fu now.
[...]
How the fact to have either<A,B> and maybe<A> makes it more dificult to interact with heterogeneous objects?
Let's try to implement a type _maybe<A>: template <typename A> struct _maybe { struct empty { }; union { A a; empty e; } val; bool is_nothing; constexpr _maybe() : val{empty{}}, is_nothing{true} { } constexpr _maybe(A a) : val{a}, is_nothing{false} { } }; Now, let's try to implement, for example, the `maybe` function, which has signature maybe :: B x (A -> B) x _maybe<A> -> B. Remember that those A's and B's are actually generalized types, not usual C++ types (we're working with heterogeneous stuff): template <typename Default, typename F, typename M> constexpr auto maybe(Default def, F f, M m) { return m.is_nothing ? def : f(m.val.a); } Seems legit? This works: maybe(1, [](int i) { return i + 1; }, _maybe<int>{1}); But this does not, even though std::tuple<> and std::tuple<int> have the same generalized type: maybe( std::tuple<>{}, [](int i) { return std::make_tuple(i); }, _maybe<int>{1} ); It fails with error: incompatible operand types ('tuple<(no argument)>' and 'tuple<int>') return m.is_nothing ? def : f(m.val.a); ^ ~~~ ~~~~~~~~~~ m.is_nothing is not a constant expression inside the function. If it was, we could use `bool_<m.is_nothing>` to use overloading to pick which branch we're executing instead of doing it at runtime, like we do right now. This is explained in the section on the limitations of constexpr [3].
[...]
Notice meta::quote.
I wonder if the meta::transform couldn't take care of quote.
If it takes care of quote, then we need to always pass templates to higher order algorithms. Basically, that would be like accepting metafunctions instead of metafunction classes in the MPL interface. There are good reasons not to do that.
[...]
My point was more on how the library is checking the fist argument of Transform is a Functor and that the second argument is a "function" from the Functor's underlying type T to another type U.
transform : Functor<T> x (T -> U) -> Functor(U)
If the implementation declares transform as
auto transform = [] (auto F, auto Fun)
Couldn't the the library check that the arguments passed in F and Fun respect the requirements?
Yes, but that would require `Fun` stating that it is a function from data type T to data type U, which is impractical. In particular it means that this: transform(make_tuple(1, 2, 3), [](int i) { return i + 1; }); would not work. Instead one would need to write transform(make_tuple(1, 2, 3), hana::function<int(int)>([](int i) { return i + 1; })); Then, say you have transform(make_tuple(1, std::string{"abc"}, my_class{}), hana::function<???(???)>([](auto x) { ... })); The way I see it, it's just not convenient. Doing it would definitely force us to be mathematically correct though. Instead, I aim to catch most programming errors by checking that F is a Functor (which is easy). If you send in a random function, then the compiler will tell you where you're wrong, but Hana won't. Regards, Louis [1]: http://goo.gl/fY8pcw [2]: http://goo.gl/Iy4FKu [3]: http://ldionne.github.io/hana/#tutorial-constexpr
Le 07/03/15 21:00, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 07/03/15 17:38, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes: [...]
Do you have an equivalence in Haskell to your datatype/generalized type? No, but shooting from the hip you could approximate them with type classes. A type class that is instantiated with another type class? For example, the Tuple data type could be implemented as
-- The different actual representations for tuples data Tuple0 = Tuple0 data Tuple1 a = Tuple1 a -- etc...
-- The Tuple generalized type representing all those guys class Tuple t where len :: t -> Int
instance Tuple Tuple0 where len _ = 0
As I already said on this list during the last informal review, what I make is a tradeoff between mathematical correctness and usability of the library. While Hana provides structures that satisfy the laws rigorously, I want users to be able to use those structures in a quick and dirty way as a mean of being more productive when needed. For example, I would not object to someone writing [pseudocode]:
auto to_string = [](auto x) { /* convert x to a std::string */ }; auto xs = hana::make_tuple(1, 2.2, "abc"); auto ys = hana::transform(xs, to_string);
Since `1`, `2.2` and `"abc"` do not share a common data type and the signature of `transform` is (for a Functor F)
transform : F(T) x (T -> U) -> F(U)
, the above should normally be ill-formed. However, the library makes such usage possible because I kept in mind that we're working in a "dirty" heterogeneously-typed context. Bottom line: I don't think heterogeneous types are dirty. We need just a different type of function (Overloaded) to transform them.
if you have an heterogeneous type as pair for example, the mathematical transform function should
transform : pair(T,U) x (T -> R) x (U -> S) -> pair(R, S)
As C++ has overloaded functions we don't need to pass two functions, but just an overloaded function. That's an interesting point of view. However, with this approach, you can't say that Pair is a Functor. It instead becomes a BiFunctor [2]. Right. A Functor has only one type parameter. In Haskell you can not overload functions so that the functions must be named differently. But in C++ we can use the same name, so we could have a transform : BiFunctor x BiCallable -> BiFunctor. Furthermore, let's say you have a pair(T, T).
Admittedly, the above is missing something fundamental if we want to implement other functions like `head`, but that reaches the limit of my Haskell-fu. I think looking at Haskell's type families [1] might provide more insight. Does it means that you are associating a "principal" type class (obtained by the function datatype) to a data type, that is used to instantiate the other type classes? transform is then
transform : pair(T, T) x (T -> R) x (T -> S) -> pair(R, S)
transform should hence still receive two functions, regardless of the fact that we could provide a single overloaded function.
pair(T, T) can be seen as an instance of Functor as list(T) does. We need an alias template <class T> using pairT = pair<T,T>;
Let me now use a tuple instead of a pair as an example because it sticks more closely to what happens in Hana (Pair is not a Functor in Hana).
tuple<T ...> shouldn't be a Functor neither.
transform then becomes:
transform : Tuple(T1, ..., Tn) x (T1 -> R1) x ... x (Tn -> Rn) -> Tuple(R1, ..., Rn)
First, if you use this approach, you can't say that Tuple is a Functor. It has to be a N-Functor, which is the N-argument equivalent to the BiFunctor. Furthermore, you have to provide N different functions to be able to transform it. So for example, when transforming a tuple(int, int, int), you would have to say
transform(tuple(1, 2, 3), [](int i) { return i + 1; }, [](int i) { return i + 1; }, [](int i) { return i + 1; } )
As pair<T,T>, and list<T> tuple<T,T,T> can be seen as an instance of a Functor. But not its heterogeneous variants.
That's not "heterogeneous" programming; it's just an equivalent way of writing
r1 = f1(t1) r2 = f2(t2) ... rn = fn(tn)
where `tk` are the elements of a tuple, and `fk` are the functions mapped on it by the N-Functor's `transform`. What we actually want is
r1 = f(t1) r2 = f(t2) ... rn = f(tn)
where `f` is defined as
f : (intersection of the data types of the tuple's elements) -> (some other type) I'm sure doing such kind of transformations is useful. However the semantic doesn't match to the transform(fmap) function associated to the Functor I know.
In other words, `f` is a function whose domain is "the set of all objects with which I can do X". If there are objects in the tuple that don't support "X", then the program is ill-formed. Concepts will put us much closer to this.
Do you mean C++17/20 Concepts? Couldn't "type classes" help here?
The principle behind Hana's generalized types is really that we "lift" the types of the objects and then consider objects up-to-different-representations. I also think it can be seen as a quotient of the set of all types by the equivalence relation
T ~ U if and only if T and U model exactly the same concepts in exactly the same way
Concretely, the mathematical universe we're working with is not only a set; it's actually the C++ category where objects are Types and morphisms are functions. Hence, that "quotient" would have to also take morphisms into account. But I'm reaching the end of my math-fu now.
Thanks for the clarification. I believe I start to understand your generalized type design/concept. I was looking for another design/concept closer to a "type constructor".
[...]
How the fact to have either<A,B> and maybe<A> makes it more dificult to interact with heterogeneous objects? Let's try to implement a type _maybe<A>:
template <typename A> struct _maybe { struct empty { };
union { A a; empty e; } val; bool is_nothing;
constexpr _maybe() : val{empty{}}, is_nothing{true} { } constexpr _maybe(A a) : val{a}, is_nothing{false} { } };
Now, let's try to implement, for example, the `maybe` function, which has signature maybe :: B x (A -> B) x _maybe<A> -> B. Remember that those A's and B's are actually generalized types, not usual C++ types (we're working with heterogeneous stuff):
template <typename Default, typename F, typename M> constexpr auto maybe(Default def, F f, M m) { return m.is_nothing ? def : f(m.val.a); }
Seems legit? This works:
maybe(1, [](int i) { return i + 1; }, _maybe<int>{1});
But this does not, even though std::tuple<> and std::tuple<int> have the same generalized type:
maybe( std::tuple<>{}, [](int i) { return std::make_tuple(i); }, _maybe<int>{1} );
It fails with
error: incompatible operand types ('tuple<(no argument)>' and 'tuple<int>') return m.is_nothing ? def : f(m.val.a); ^ ~~~ ~~~~~~~~~~
This seems normal to me. Does it mean that classes as experimental::optional<T> couldn't be seen as an instance of Hana Functor type class?
m.is_nothing is not a constant expression inside the function. If it was, we could use `bool_<m.is_nothing>` to use overloading to pick which branch we're executing instead of doing it at runtime, like we do right now. This is explained in the section on the limitations of constexpr [3].
Does it means that your data types Maybe and Either are usable only as meta-programming tools? I don't see where could I use them at run-time.
[...]
Notice meta::quote. I wonder if the meta::transform couldn't take care of quote. If it takes care of quote, then we need to always pass templates to higher order algorithms. Basically, that would be like accepting metafunctions instead of metafunction classes in the MPL interface. There are good reasons not to do that. I see.
[...]
My point was more on how the library is checking the fist argument of Transform is a Functor and that the second argument is a "function" from the Functor's underlying type T to another type U.
transform : Functor<T> x (T -> U) -> Functor(U)
If the implementation declares transform as
auto transform = [] (auto F, auto Fun)
Couldn't the the library check that the arguments passed in F and Fun respect the requirements? Yes, but that would require `Fun` stating that it is a function from data type T to data type U, which is impractical. In particular it means that this:
transform(make_tuple(1, 2, 3), [](int i) { return i + 1; });
would not work. Instead one would need to write
transform(make_tuple(1, 2, 3), hana::function<int(int)>([](int i) { return i + 1; }));
Then, say you have
transform(make_tuple(1, std::string{"abc"}, my_class{}), hana::function<???(???)>([](auto x) { ... }));
The way I see it, it's just not convenient. Doing it would definitely force us to be mathematically correct though. Instead, I aim to catch most programming errors by checking that F is a Functor (which is easy). If you send in a random function, then the compiler will tell you where you're wrong, but Hana won't.
Maybe it could be a different "transform" function that applies to ProductTypes instead of to Functors. The requirement on Fun could be that Fun is callable with any of the types on the ProductType and that each one of these overloads should have the same result U. I think that I need to understand better the scope of the library, is Hana a pure functional programming library or another way to do pure meta-programming or both at the same time, but restricted to the limitations of the intersection? Best, Vicente
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 07/03/15 21:00, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 07/03/15 17:38, Louis Dionne a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes: [...]
Do you have an equivalence in Haskell to your datatype/generalized type? No, but shooting from the hip you could approximate them with type classes.
A type class that is instantiated with another type class?
Like I said, I don't know Haskell well enough to tell whether there's a direct mapping between data types in Hana and something else in Haskell. Is there an equivalent to Fusion/MPL tags in Haskell?
[...]
Does it means that you are associating a "principal" type class (obtained by the function datatype) to a data type, that is used to instantiate the other type classes?
I was just using the Tuple type class as a hack to "group" the different TupleN representations under the same umbrella. Again, I'm not a Haskell wizard and there might be a clean way to do it.
[...] if you have an heterogeneous type as pair for example, the mathematical transform function should
transform : pair(T,U) x (T -> R) x (U -> S) -> pair(R, S)
As C++ has overloaded functions we don't need to pass two functions, but just an overloaded function. That's an interesting point of view. However, with this approach, you can't say that Pair is a Functor. It instead becomes a BiFunctor [2].
Right. A Functor has only one type parameter. In Haskell you can not overload functions so that the functions must be named differently. But in C++ we can use the same name, so we could have a transform : BiFunctor x BiCallable -> BiFunctor.
IIUC, BiCallable basically represents two functions with different domains stitched into a single function via C++ overloading, right? Then, I say we don't want that because it still represents two different functions with two different domains, instead of a single function with the proper domain.
Furthermore, let's say you have a pair(T, T). transform is then
transform : pair(T, T) x (T -> R) x (T -> S) -> pair(R, S)
transform should hence still receive two functions, regardless of the fact that we could provide a single overloaded function.
pair(T, T) can be seen as an instance of Functor as list(T) does.
We need an alias
template <class T> using pairT = pair<T,T>;
See below.
Let me now use a tuple instead of a pair as an example because it sticks more closely to what happens in Hana (Pair is not a Functor in Hana). tuple<T ...> shouldn't be a Functor neither. transform then becomes:
transform : Tuple(T1, ..., Tn) x (T1 -> R1) x ... x (Tn -> Rn) -> Tuple(R1, ..., Rn)
First, if you use this approach, you can't say that Tuple is a Functor. It has to be a N-Functor, which is the N-argument equivalent to the BiFunctor. Furthermore, you have to provide N different functions to be able to transform it. So for example, when transforming a tuple(int, int, int), you would have to say
transform(tuple(1, 2, 3), [](int i) { return i + 1; }, [](int i) { return i + 1; }, [](int i) { return i + 1; } )
As pair<T,T>, and list<T> tuple<T,T,T> can be seen as an instance of a Functor. But not its heterogeneous variants.
Fine, but what about tuple<T, U, T>? Clearly, transform should receive three different functions: transform : tuple<T, U, T> x (T -> A) x (U -> B) x (T -> C) -> tuple<A, B, C> And hence we still have a 3-Functor (for w/e that means). I think I'm starting to understand where our views diverge: You keep on trying to see heterogeneous data structures like tuples as product types, which they are at the most basic level. I lift the type-system one level higher up and see tuples as a fixed-length arrays of objects with the same "type" (generalized type). This approach has some advantages, like being able to look at objects of the Type data type as objects of the same "type". Those objects all have a common interface, which corresponds to the <type_traits>.
That's not "heterogeneous" programming; it's just an equivalent way of writing
r1 = f1(t1) r2 = f2(t2) ... rn = fn(tn)
where `tk` are the elements of a tuple, and `fk` are the functions mapped on it by the N-Functor's `transform`. What we actually want is
r1 = f(t1) r2 = f(t2) ... rn = f(tn)
where `f` is defined as
f : (intersection of the data types of the tuple's elements) -> (some other type) I'm sure doing such kind of transformations is useful. However the semantic doesn't match to the transform(fmap) function associated to the Functor I know.
It's because Hana does not use the Functor _you_ know. It's pretty much a work in progress, but you might be interested in taking a look at my thesis [1]. I show how we can categorify Hana, and I'm about to explain how Functors materialize themselves. It is in essence exactly the same thing as what happens with the Hask category, except that you replace "type" by "generalized type".
In other words, `f` is a function whose domain is "the set of all objects with which I can do X". If there are objects in the tuple that don't support "X", then the program is ill-formed. Concepts will put us much closer to this.
Do you mean C++17/20 Concepts? Couldn't "type classes" help here?
Yes, C++ Concepts. I just meant that C++ Concepts would help us put constraints on families of types, without having to fix their representation.
[...]
How the fact to have either<A,B> and maybe<A> makes it more dificult to interact with heterogeneous objects? Let's try to implement a type _maybe<A>:
template <typename A> struct _maybe { struct empty { };
union { A a; empty e; } val; bool is_nothing;
constexpr _maybe() : val{empty{}}, is_nothing{true} { } constexpr _maybe(A a) : val{a}, is_nothing{false} { } };
Now, let's try to implement, for example, the `maybe` function, which has signature maybe :: B x (A -> B) x _maybe<A> -> B. Remember that those A's and B's are actually generalized types, not usual C++ types (we're working with heterogeneous stuff):
template <typename Default, typename F, typename M> constexpr auto maybe(Default def, F f, M m) { return m.is_nothing ? def : f(m.val.a); }
Seems legit? This works:
maybe(1, [](int i) { return i + 1; }, _maybe<int>{1});
But this does not, even though std::tuple<> and std::tuple<int> have the same generalized type:
maybe( std::tuple<>{}, [](int i) { return std::make_tuple(i); }, _maybe<int>{1} );
It fails with
error: incompatible operand types ('tuple<(no argument)>' and 'tuple<int>') return m.is_nothing ? def : f(m.val.a); ^ ~~~ ~~~~~~~~~~
This seems normal to me.
It _is_ normal, but it's not useful in a context of dealing with heterogeneous values, because you can't return objects of different types from that function. What we need is to store the information required to make that branch in the Maybe's type, and then we can return objects of different types from that function, because the conditional is actually implemented as an overload.
Does it mean that classes as experimental::optional<T> couldn't be seen as an instance of Hana Functor type class?
Yes, it can be a Functor. Just like std::vector is a Hana Functor (I added this recently). However, some types that are fundamentally useful at runtime can't model some concepts in Hana. For example, the current library requires the is_empty method (from Iterable) to return an IntegralConsant. For this reason, std::vector can't be made Iterable.
m.is_nothing is not a constant expression inside the function. If it was, we could use `bool_<m.is_nothing>` to use overloading to pick which branch we're executing instead of doing it at runtime, like we do right now. This is explained in the section on the limitations of constexpr [3].
Does it means that your data types Maybe and Either are usable only as meta-programming tools? I don't see where could I use them at run-time.
You're right, they are mostly useless at runtime, just like boost::optional and boost::variant are completely useless at compile-time. That's exactly the point; Hana is a _metaprogramming_ library. Quoting from Maybe's documentation [2]: [...] However, there is an important distinction to make between Maybe and std::optional: just(x) and nothing do not share the same type. Hence, whether a just or a nothing will be returned from a function has to be known at compile-time for the return type to be computable at compile-time. This makes Maybe well suited for static metaprogramming tasks but very poor for anything dynamic.
[...]
My point was more on how the library is checking the fist argument of Transform is a Functor and that the second argument is a "function" from the Functor's underlying type T to another type U.
transform : Functor<T> x (T -> U) -> Functor(U)
If the implementation declares transform as
auto transform = [] (auto F, auto Fun)
Couldn't the the library check that the arguments passed in F and Fun respect the requirements? Yes, but that would require `Fun` stating that it is a function from data type T to data type U, which is impractical. In particular it means that this:
transform(make_tuple(1, 2, 3), [](int i) { return i + 1; });
would not work. Instead one would need to write
transform(make_tuple(1, 2, 3), hana::function<int(int)>([](int i) { return i + 1; }));
Then, say you have
transform(make_tuple(1, std::string{"abc"}, my_class{}), hana::function<???(???)>([](auto x) { ... }));
The way I see it, it's just not convenient. Doing it would definitely force us to be mathematically correct though. Instead, I aim to catch most programming errors by checking that F is a Functor (which is easy). If you send in a random function, then the compiler will tell you where you're wrong, but Hana won't.
Maybe it could be a different "transform" function that applies to ProductTypes instead of to Functors. The requirement on Fun could be that Fun is callable with any of the types on the ProductType and that each one of these overloads should have the same result U.
We're basically saying the same thing here. IIUC, your ProductTypes are basically what I call Functors, and saying that Fun is callable with any of the types in the ProductType is just saying they share a set of common concepts, which I try to embody in the concept of data type. There's a small generalization missing from my understanding to bridge the gap between concepts and data types, which I think are the same in the end. See the remark at the end of the section on generalized data types [3].
I think that I need to understand better the scope of the library, is Hana a pure functional programming library or another way to do pure meta-programming or both at the same time, but restricted to the limitations of the intersection?
Like Fusion, Hana is a library that bridges between runtime and compile-time. Basically, you can manipulate sequences with heterogeneous objects in them, but their length has to be known at compile-time. I know there's a way to generalize this so that it works with homogeneous sequences whose size is known at runtime too, but I'm not tackling this right now. Then, type-level computations come for free when you have heterogeneous sequences, but we had just never saw it as clearly as we do now. Hana is not just a "pure functional" library that works at runtime. It's a generalized Boost.Fusion which happens to use concepts from the functional paradigm because it's convenient. Regards, Louis [1]: https://github.com/ldionne/hana-thesis [2]: http://ldionne.github.io/hana/structboost_1_1hana_1_1_maybe.html [3]: http://ldionne.github.io/hana/index.html#tutorial-hetero
Louis Dionne <ldionne.2 <at> gmail.com> writes:
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
[...]
Compile-time error reporting --------------------
I would expect that the library provide some king of "TypeClass" check use (As Eric's Range library does with Concepts) so that the compile time errors are more explicit.
Doing this for all parameters of all functions is intractable due to the heterogeneous context, but basic support could be added easily. I'm promoting this on my todo list.
Before I go an change the code, I'd like to make sure I understand your comment properly. Currently, if you use a method with a parameter that does not model the required concept, you'll get an assertion. For example, hana::head(1); Produces [...] error: static_assert failed "no definition of boost::hana::head for the given data types" static_assert(wrong<head_impl<It>, Xs>{}, ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~ [...] note: in instantiation of function template specialization 'boost::hana::head_impl<int, boost::hana::when<true> >::apply<int>' requested here return head_impl<typename datatype<Xs>::type>::apply( ^ [...] note: in instantiation of function template specialization 'boost::hana::_head::operator()<int>' requested here hana::head(1); The check is currently being done in the base case of the tag-dispatched method, `head_impl`. It could also be done higher up, in the "interface method", i.e. `head` itself. For example, here's what I experimented with locally: hana::head(1); Produces [...] error: static_assert failed "hana::head(xs) requires xs to be an Iterable" static_assert(models<Iterable(typename datatype<Xs>::type)>{}, ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ [...] note: in instantiation of function template specialization 'boost::hana::_head::operator()<int>' requested here hana::head(1); Is this the kind of improvement you were talking about, or was it something else entirely? Regardless, I like this better than my current system and I'll probably do it, but I'd like to make sure I understand your point. Louis
Le 07/03/15 19:09, Louis Dionne a écrit :
Louis Dionne <ldionne.2 <at> gmail.com> writes:
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
[...]
Compile-time error reporting --------------------
I would expect that the library provide some king of "TypeClass" check use (As Eric's Range library does with Concepts) so that the compile time errors are more explicit. Doing this for all parameters of all functions is intractable due to the heterogeneous context, but basic support could be added easily. I'm promoting this on my todo list. Before I go an change the code, I'd like to make sure I understand your comment properly. Currently, if you use a method with a parameter that does not model the required concept, you'll get an assertion. For example,
hana::head(1);
Produces
[...] error: static_assert failed "no definition of boost::hana::head for the given data types" static_assert(wrong<head_impl<It>, Xs>{}, ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~ [...] note: in instantiation of function template specialization 'boost::hana::head_impl<int, boost::hana::when<true> >::apply<int>' requested here return head_impl<typename datatype<Xs>::type>::apply( ^ [...] note: in instantiation of function template specialization 'boost::hana::_head::operator()<int>' requested here hana::head(1);
The check is currently being done in the base case of the tag-dispatched method, `head_impl`. It could also be done higher up, in the "interface method", i.e. `head` itself. For example, here's what I experimented with locally:
hana::head(1);
Produces
[...] error: static_assert failed "hana::head(xs) requires xs to be an Iterable" static_assert(models<Iterable(typename datatype<Xs>::type)>{}, ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ [...] note: in instantiation of function template specialization 'boost::hana::_head::operator()<int>' requested here hana::head(1);
Is this the kind of improvement you were talking about, or was it something else entirely? Regardless, I like this better than my current system and I'll probably do it, but I'd like to make sure I understand your point.
Yes, this is exactly what I would expect. Report errors at the interface level, not the implementation. Vicente
On 05/03/2015 15:41, Louis Dionne wrote:
- Lack of support for mainstream compilers: The library is now almost fully functional with Clang 3.5. A GCC 4.9 port with reduced functionality is also underway on the `redux` branch.
This might sound discouraging, but I consider any library that doesn't work fully with GCC 4.9, Clang 3.5 and MSVC14, which are already bleeding-edge compilers, to not be suitable for real use, and thus not suitable for inclusion into Boost either. The risk is that this library might never be more than a mere curiosity.
Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:
On 05/03/2015 15:41, Louis Dionne wrote:
- Lack of support for mainstream compilers: The library is now almost fully functional with Clang 3.5. A GCC 4.9 port with reduced functionality is also underway on the `redux` branch.
This might sound discouraging, but I consider any library that doesn't work fully with GCC 4.9, Clang 3.5 and MSVC14, which are already bleeding-edge compilers, to not be suitable for real use, and thus not suitable for inclusion into Boost either.
The risk is that this library might never be more than a mere curiosity.
First, Clang 3.5 is now fully supported. Second, you imply that any library which uses variable templates, extended constexpr or other C++14 features that are not well supported yet is not suited for real use. I humbly disagree. On the contrary, I think it is a good occasion to push compiler implementers a bit by making more cutting-edge libraries available to the large public. Then, there will be a bigger incentive to support C++14 properly, but most importantly there will be more bug reports comming in, which triggers improvement. I hope the rest of this community is not feeling the same towards cutting edge libraries. I would suspect that some of the most groundbreaking libraries that are now well accepted and supported by compilers were in Hana's position when they started. Regards, Louis
AMDG On 03/08/2015 11:20 AM, Louis Dionne wrote:
Mathias Gaunard <mathias.gaunard <at> ens-lyon.org> writes:
On 05/03/2015 15:41, Louis Dionne wrote:
- Lack of support for mainstream compilers: The library is now almost fully functional with Clang 3.5. A GCC 4.9 port with reduced functionality is also underway on the `redux` branch.
This might sound discouraging, but I consider any library that doesn't work fully with GCC 4.9, Clang 3.5 and MSVC14, which are already bleeding-edge compilers, to not be suitable for real use, and thus not suitable for inclusion into Boost either.
The risk is that this library might never be more than a mere curiosity.
First, Clang 3.5 is now fully supported. Second, you imply that any library which uses variable templates, extended constexpr or other C++14 features that are not well supported yet is not suited for real use. I humbly disagree.
On the contrary, I think it is a good occasion to push compiler implementers a bit by making more cutting-edge libraries available to the large public. Then, there will be a bigger incentive to support C++14 properly, but most importantly there will be more bug reports comming in, which triggers improvement.
I hope the rest of this community is not feeling the same towards cutting edge libraries. I would suspect that some of the most groundbreaking libraries that are now well accepted and supported by compilers were in Hana's position when they started.
Back in the day, most libraries bent over backwards to support VC6. Anyway, I'm with Louis on this. As long as you conform to the current standard, I don't have a problem if your library only works on one compiler right now. The caveat is that you'll need to be much more careful about standard compliance if you can't check against multiple implementations. Of course, I also expect you to make make a commitment to getting your code to work with more compilers as they catch up with the standard. In Christ, Steven Watanabe
This might sound discouraging, but I consider any library that doesn't work fully with GCC 4.9, Clang 3.5 and MSVC14, which are already bleeding-edge compilers, to not be suitable for real use
Its important to support more than one compiler, but, I think, it is perfectly acceptable if it doesn't support bug-ridden compilers such as MSVC. Boost is about pushing innovation in C++, and we can't let a compiler that is over half a decade behind the rest of the industry hold back that innovation. Paul -- View this message in context: http://boost.2283326.n4.nabble.com/Hana-Informal-review-request-tp4672703p46... Sent from the Boost - Dev mailing list archive at Nabble.com.
On 3/8/2015 12:56 PM, pfultz2 wrote:
This might sound discouraging, but I consider any library that doesn't work fully with GCC 4.9, Clang 3.5 and MSVC14, which are already bleeding-edge compilers, to not be suitable for real use
Its important to support more than one compiler, but, I think, it is perfectly acceptable if it doesn't support bug-ridden compilers such as MSVC. Boost is about pushing innovation in C++, and we can't let a compiler that is over half a decade behind the rest of the industry hold back that innovation.
This. MSVC is hopelessly behind, and we shouldn't let them pull the C++ community down any longer. Moving on. Boost has always had a tradition of pushing the compiler vendors toward compliance. Any library that compiles on two compilers has been acceptable in the past. I think that's a good benchmark. -- Eric Niebler Boost.org http://www.boost.org
Dear Boost, Here is a non-exhaustive list of some issues that were raised during the informal review of Hana last week, along with an explanation of what I did or am doing to resolve them. 1. It was suggested that size be renamed to length. The resolution is that an alias to `length` named `size` was added. `length` was kept because it applies to any Foldable, which includes things like Maybe. I found that writing `size(just('x'))` or `size(nothing)` made less sense than writing `length(just('x'))` or `length(nothing)`. Also, I find it prettier. This resolution should satisfy those seeking consistency with the standard library, while causing a minimal amount of changes to Hana. 2. It was suggested that `assert` be used in the documentation instead of other Hana specific macros in order to simplify things. The resolution is that I use `assert` and `static_assert` at the very beginning of the tutorial, and I then briefly explain what are those other macros. I then use those Hana-specific macros in the documentation because they provide more information to the reader than `assert`/`static_assert`. 3. It was suggested that the `algorithm`/`algorithm_if` convention be used for algorithms accepting an optional predicate. The resolution is that this convention is now used whenever it makes sense. In particular, the following algorithms were added/renamed: - count(seq, pred) -> count_if(seq, pred) + count(seq, val) - adjust(seq, pred, f) -> adjust_if(seq, pred, f) + adjust(seq, val, f) - replace(seq, pred, val) -> replace_if(seq, pred, newval) + replace(seq, oldval, newval) - find(seq, pred) -> find_if(seq, pred) - lookup(seq, val) -> find(seq, val) 4. It was suggested that `foldl` and `foldr` be renamed to something else. I started a poll at [1] to ask for the people's opinion, and the results so far clearly show that people want `fold/reverse_fold`. There is currently no resolution because I realized afterwards that `reverse_fold` in Fusion and `foldr` in Hana do not have exactly the same semantics. First, the order of the arguments is flipped, i.e. reverse_fold(seq, state, f) == foldr(seq, state, flip(f)) This is a benign difference. However, there is a more serious incompatibility stemming from how `reverse_fold` is usually specified and understood: as starting from the end. This causes a problem for infinite data structures, which obviously have no reachable end. Instead, `foldr` is usually specified recursively in a way that makes it possible to right-fold infinite data structures (and it is indeed possible to do so in Haskell and with MPL11). There is no real support for infinite data structures in Hana right now, but simple Concept generalizations which I have been thinking about might make this possible. In summary, I want to make sure I'm not blocking myself if I make the `foldl/foldr` change, but rest assured that I understood very well the people's desire. 5. It was suggested that some errors should be caught at the interface level, like when one uses a function with arguments that do not model the proper concepts. The resolution is that almost all the algorithms now static_assert that their arguments are models of the proper concepts (when possible). These checks can be enabled or disabled with the BOOST_HANA_CONFIG_DISABLE_DATA_TYPE_CHECKS macro, which is documented at [2]. 6. In a different thread [3], it was suggested that a MPL-like interface for type-only computations be provided. I implemented part of the MPL in a somewhat-backward-compatible manner, as can be seen at [4]. I am pondering whether to include it as part of Hana's public interface or to leave it as a proof of concept in the example/ directory. So far, I have not witnessed any use case in which type-only computations expressed in a classic MPL style provide a substantial gain over type-level computations expressed in idiomatic Hana, and actually I found it to often be the contrary. I'm waiting for a good reason of pushing that idea forward before I do it. There's also a poll at [5] if you want to express yourself. 7. In a different thread [6], it was suggested that the Logical concept should interact well with Lazy computations. I have begun to investigate possible ways of nicely tying both together, as can be seen at [7], and will try to have something definitive before a formal review. 8. In the same thread [6], it was also suggested that Hana provides a way to write inline metafunctions, pretty much like MPL's lambda expressions. I think this is an interesting idea that could make simple type-level computations super easy to write and I will try to explore it in time for the formal review. If you think I am missing something above, and that an issue was raised but not acknowledged or addressed, please reply to this message and I will make it right. Also, if you have more comments, please keep them coming. In the interest of full disclosure, the plan is to ask for a formal review during the month of April and then present the results of the review at C++Now in May. To put all the chances on my side, I would like to rule out as many objections as possible before we even start the review, so please raise your objections as soon as possible so I can address them. Regards, Louis [1]: https://github.com/ldionne/hana/issues/18 [2]: http://ldionne.github.io/hana/group__group-config.html [3]: http://article.gmane.org/gmane.comp.lib.boost.devel/257894 [4]: http://goo.gl/59xTvj [5]: https://github.com/ldionne/hana/issues/19 [6]: http://article.gmane.org/gmane.comp.lib.boost.devel/258248 [7]: http://ldionne.github.io/2015/03/16/laziness-as-a-comonad/
On 3/16/2015 4:43 PM, Louis Dionne wrote: <snip>
However, there is a more serious incompatibility stemming from how `reverse_fold` is usually specified and understood: as starting from the end. This causes a problem for infinite data structures, which obviously have no reachable end. Instead, `foldr` is usually specified recursively in a way that makes it possible to right-fold infinite data structures (and it is indeed possible to do so in Haskell and with MPL11). There is no real support for infinite data structures in Hana right now, but simple Concept generalizations which I have been thinking about might make this possible. In summary, I want to make sure I'm not blocking myself if I make the `foldl/foldr` change, but rest assured that I understood very well the people's desire.
I personally don't see a problem with keeping foldr's semantics but changing the name to reverse_fold, if that's what people want.
7. In a different thread [6], it was suggested that the Logical concept should interact well with Lazy computations. I have begun to investigate possible ways of nicely tying both together, as can be seen at [7], and will try to have something definitive before a formal review.
[7] http://ldionne.github.io/2015/03/16/laziness-as-a-comonad
Awesome. I'm really looking forward to reading this.
8. In the same thread [6], it was also suggested that Hana provides a way to write inline metafunctions, pretty much like MPL's lambda expressions. I think this is an interesting idea that could make simple type-level computations super easy to write and I will try to explore it in time for the formal review.
I'll be interested to see if/how you avoid Boost.MPL's lambda evaluation semantics quagmire. I find the business of tracking whether/where substitutions were done, conditionally probing for ::type, then conditionally selecting the substitution, to be pretty unsatisfactory. Too much magic, too difficult to grok, and could even cause errors by causing inadvertent instantiations of things not meant to be instantiated -- which means things need to be protect'ed, etc, etc. I would prefer a simpler, more predictable algorithm, even at the expense less pithy lambdas.
In the interest of full disclosure, the plan is to ask for a formal review during the month of April and then present the results of the review at C++Now in May. To put all the chances on my side, I would like to rule out as many objections as possible before we even start the review, so please raise your objections as soon as possible so I can address them.
Thanks for all your work, Louis. -- Eric Niebler Boost.org http://www.boost.org
Eric Niebler <eniebler <at> boost.org> writes:
On 3/16/2015 4:43 PM, Louis Dionne wrote: <snip>
However, there is a more serious incompatibility stemming from how `reverse_fold` is usually specified and understood: as starting from the end. This causes a problem for infinite data structures, which obviously have no reachable end. Instead, `foldr` is usually specified recursively in a way that makes it possible to right-fold infinite data structures (and it is indeed possible to do so in Haskell and with MPL11). There is no real support for infinite data structures in Hana right now, but simple Concept generalizations which I have been thinking about might make this possible. In summary, I want to make sure I'm not blocking myself if I make the `foldl/foldr` change, but rest assured that I understood very well the people's desire.
I personally don't see a problem with keeping foldr's semantics but changing the name to reverse_fold, if that's what people want.
The problem is that in the infinite case, it's not a "reverse" fold anymore, and hence the name becomes very misleading. For those that might be reading this and wondering what I mean by non-strict folds, here's how `foldr` can be defined recursively: template <typename Sequence, typename State, typename F> auto foldr(Sequence xs, State s, F f) { if (is_empty(xs)) return s; else return f(head(xs), foldr(tail(xs), s, f)); } In a strict evaluation context, when the else branch is taken, the foldr(tail(xs), s, f) is always evaluated. However, in a non-strict context, a "thunk" (a deferred computation) is built instead and the else branch looks more like return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); where thunk[expr] is just an `expr` that will be evaluated if its value is required inside of f. So, for example, if `f` is (pseudo) defined as auto f(auto x, auto ignored) { return x; } since `f` never uses the value of its second argument, this argument is never evaluated. So the "else" branch inside the `foldr` becomes: return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); --> return head(xs); and the recursive call to `foldr` is never evaluated. This allows processing infinite lists lazily and writing short-circuiting algorithms such as template <typename Sequence, typename Predicate> bool any_of(Sequence xs, Predicate pred) { return foldr(xs, false, [](auto x, auto y) { return pred(x) || pred(y); }); } implicitly. In the above example, if `pred(x)` returns true for some `x`, then the corresponding `pred(y)` is never evaluated because `||` short-circuits. Because we're in a hypothetical non-strict evaluation world, this causes `y` not to be evaluated at all. However, if you go back to the definition of `foldr` above, the `y` was an expression of the form foldr(tail(xs), s, f) where f is our lambda in the `any_of` algorithm. So basically, we're saying that the recursive call to `foldr` is not evaluated, and hence our `any_of` algorithm short-circuits automatically. So anyway, my point is that seeing right-folds as f(x1, f(x2, f(x3, ...f(xN, state))) is slightly more general than seeing them as starting from the end, because it allows for the case where there's no end. That being said, I'm aware that we're _not_ in Haskell and so it does not really apply to Hana. I'd just like to make sure that I (or someone else) won't find a nice application for infinite data structures in Hana that would make me regret that choice. But writing this, I have the germ of an idea that these lazy folds might be nothing more than a monadic fold with the Lazy Monad, which would resolve the issue. I have to look into this further before I can say anything.
7. In a different thread [6], it was suggested that the Logical concept should interact well with Lazy computations. I have begun to investigate possible ways of nicely tying both together, as can be seen at [7], and will try to have something definitive before a formal review.
[7] http://ldionne.github.io/2015/03/16/laziness-as-a-comonad
Awesome. I'm really looking forward to reading this.
As it stands, I find the post to be a bit boring because there's no interesting use case at the end. I'm thinking about expanding on how we can compose lazy computations (as Applicatives and Monads), which is really the fun part and also the part that gives us pretty semantics for composing arbitrary lazy computations. Locally, I have prototyped a new `if_` with both lazy and non-lazy semantics which I think will be going into Hana. Anyway, will do if time permits!
8. In the same thread [6], it was also suggested that Hana provides a way to write inline metafunctions, pretty much like MPL's lambda expressions. I think this is an interesting idea that could make simple type-level computations super easy to write and I will try to explore it in time for the formal review.
I'll be interested to see if/how you avoid Boost.MPL's lambda evaluation semantics quagmire. I find the business of tracking whether/where substitutions were done, conditionally probing for ::type, then conditionally selecting the substitution, to be pretty unsatisfactory. Too much magic, too difficult to grok, and could even cause errors by causing inadvertent instantiations of things not meant to be instantiated -- which means things need to be protect'ed, etc, etc. I would prefer a simpler, more predictable algorithm, even at the expense less pithy lambdas.
I too agree that MPL's lambda expressions are no fun, especially to implement. For Hana, I would aim for something much simpler because it would just be a way to quickly compose type-level computations in order to save a couple of lines. For more complex computations, my opinion is still that one should use plain functions. Regards, Louis
AMDG On 03/17/2015 11:39 AM, Louis Dionne wrote:
<snip>
template <typename Sequence, typename State, typename F> auto foldr(Sequence xs, State s, F f) { if (is_empty(xs)) return s; else return f(head(xs), foldr(tail(xs), s, f)); }
<snip> since `f` never uses the value of its second argument, this argument is never evaluated. So the "else" branch inside the `foldr` becomes:
return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); --> return head(xs);
and the recursive call to `foldr` is never evaluated. This allows processing infinite lists lazily and writing short-circuiting algorithms such as
template <typename Sequence, typename Predicate> bool any_of(Sequence xs, Predicate pred) { return foldr(xs, false, [](auto x, auto y) { return pred(x) || pred(y); }); }
I know this looks cool, but it's actually a perfect example of why foldr on an infinite sequence isn't a good idea. On an infinite sequence, this any_of will either return true or will go into infinite recursion. I can't see any practical use for such behavior. If I ever needed to use any_of on an infinite sequence, I doubt that having the false case fail would be acceptable. An any_of that actually handles the false case for infinite sequences can't be implemented generically. IMHO, foldr makes it much too easy to write algorithms like this that almost work. In Christ, Steven Watanabe
Steven Watanabe <watanabesj <at> gmail.com> writes:
AMDG
On 03/17/2015 11:39 AM, Louis Dionne wrote:
<snip>
template <typename Sequence, typename State, typename F> auto foldr(Sequence xs, State s, F f) { if (is_empty(xs)) return s; else return f(head(xs), foldr(tail(xs), s, f)); }
<snip> since `f` never uses the value of its second argument, this argument is never evaluated. So the "else" branch inside the `foldr` becomes:
return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); --> return head(xs);
and the recursive call to `foldr` is never evaluated. This allows processing infinite lists lazily and writing short-circuiting algorithms such as
template <typename Sequence, typename Predicate> bool any_of(Sequence xs, Predicate pred) { return foldr(xs, false, [](auto x, auto y) { return pred(x) || pred(y); }); }
I know this looks cool, but it's actually a perfect example of why foldr on an infinite sequence isn't a good idea. On an infinite sequence, this any_of will either return true or will go into infinite recursion. I can't see any practical use for such behavior. If I ever needed to use any_of on an infinite sequence, I doubt that having the false case fail would be acceptable. An any_of that actually handles the false case for infinite sequences can't be implemented generically. IMHO, foldr makes it much too easy to write algorithms like this that almost work.
Sorry for the late reply. Well, any_of might not have been the best example, but lazy right folds still make sense in a number of contexts. Being lazy when right-folding also allows interesting optimizations to take place (for example, see [1]), but that's a different story and we're far from there in Hana. On another note, I dismantled my germ of thought that lazy folding is just monadic folding with the Lazy monad; it's not that simple. I think achieving lazy right folds generically would require adding a generic expression evaluator that would be used everywhere to evaluate expressions, and then by overriding it one could pick between lazy and strict algorithms. I'm not sure though; I'm still trying to understand F-Algebras as presented by Bartosz in [2]. Anyway, so the conclusion is that lazy right folds won't be supported in Hana, at least not for a while. So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr, because renaming them all at once would require more work, especially with the new naming scheme with no-state overloads that was discussed in the poll at [3]. I hope this sounds reasonable. Regards, Louis [1]: http://goo.gl/hHzkuJ [2]: https://www.fpcomplete.com/user/bartosz/understanding-algebras [3]: https://github.com/ldionne/hana/issues/18
On 3/21/2015 10:20 AM, Louis Dionne wrote:
Steven Watanabe <watanabesj <at> gmail.com> writes:
AMDG
On 03/17/2015 11:39 AM, Louis Dionne wrote:
<snip>
template <typename Sequence, typename State, typename F> auto foldr(Sequence xs, State s, F f) { if (is_empty(xs)) return s; else return f(head(xs), foldr(tail(xs), s, f)); }
<snip> since `f` never uses the value of its second argument, this argument is never evaluated. So the "else" branch inside the `foldr` becomes:
return f(thunk[head(xs)], thunk[foldr(tail(xs), s, f)]); --> return head(xs);
and the recursive call to `foldr` is never evaluated. This allows processing infinite lists lazily and writing short-circuiting algorithms such as
template <typename Sequence, typename Predicate> bool any_of(Sequence xs, Predicate pred) { return foldr(xs, false, [](auto x, auto y) { return pred(x) || pred(y); }); }
I know this looks cool, but it's actually a perfect example of why foldr on an infinite sequence isn't a good idea. On an infinite sequence, this any_of will either return true or will go into infinite recursion. I can't see any practical use for such behavior. If I ever needed to use any_of on an infinite sequence, I doubt that having the false case fail would be acceptable. An any_of that actually handles the false case for infinite sequences can't be implemented generically. IMHO, foldr makes it much too easy to write algorithms like this that almost work.
Sorry for the late reply. Well, any_of might not have been the best example, but lazy right folds still make sense in a number of contexts. Being lazy when right-folding also allows interesting optimizations to take place (for example, see [1]), but that's a different story and we're far from there in Hana.
On another note, I dismantled my germ of thought that lazy folding is just monadic folding with the Lazy monad; it's not that simple. I think achieving lazy right folds generically would require adding a generic expression evaluator that would be used everywhere to evaluate expressions, and then by overriding it one could pick between lazy and strict algorithms. I'm not sure though; I'm still trying to understand F-Algebras as presented by Bartosz in [2].
Anyway, so the conclusion is that lazy right folds won't be supported in Hana, at least not for a while. So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr, because renaming them all at once would require more work, especially with the new naming scheme with no-state overloads that was discussed in the poll at [3]. I hope this sounds reasonable.
I would like to urge you to use easily understandable names in your library rather than shortened and more cryptic names. Any extra typing a user of your library may have to do is easily offset by the fact that more easily understandable names make your library much more understandable to use.
Edward Diener <eldiener <at> tropicsoft.com> writes:
On 3/21/2015 10:20 AM, Louis Dionne wrote:
[...]
Anyway, so the conclusion is that lazy right folds won't be supported in Hana, at least not for a while. So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr, because renaming them all at once would require more work, especially with the new naming scheme with no-state overloads that was discussed in the poll at [3]. I hope this sounds reasonable.
I would like to urge you to use easily understandable names in your library rather than shortened and more cryptic names. Any extra typing a user of your library may have to do is easily offset by the fact that more easily understandable names make your library much more understandable to use.
Of course, my goal was never to use more cryptic names for the sole purpose of reducing the number of letters. When it makes sense to do so, I use the names that are used in C++. When there are good reasons not to, I use the names used everywhere else in functional programming. If you have specific examples of places where I use names that seem cryptic, please point them out. I will be happy to discuss the reasons behind those names and to change them if those reasons are deemed insufficient after consideration. Thank you, Louis Dionne
On 3/21/2015 12:11 PM, Louis Dionne wrote:
Edward Diener <eldiener <at> tropicsoft.com> writes:
On 3/21/2015 10:20 AM, Louis Dionne wrote:
[...]
Anyway, so the conclusion is that lazy right folds won't be supported in Hana, at least not for a while. So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr, because renaming them all at once would require more work, especially with the new naming scheme with no-state overloads that was discussed in the poll at [3]. I hope this sounds reasonable.
I would like to urge you to use easily understandable names in your library rather than shortened and more cryptic names. Any extra typing a user of your library may have to do is easily offset by the fact that more easily understandable names make your library much more understandable to use.
Of course, my goal was never to use more cryptic names for the sole purpose of reducing the number of letters. When it makes sense to do so, I use the names that are used in C++. When there are good reasons not to, I use the names used everywhere else in functional programming.
If you have specific examples of places where I use names that seem cryptic, please point them out. I will be happy to discuss the reasons behind those names and to change them if those reasons are deemed insufficient after consideration.
A name like 'foldl' and 'foldr' is what I mean.
Edward Diener <eldiener <at> tropicsoft.com> writes:
On 3/21/2015 12:11 PM, Louis Dionne wrote:
[...] > If you have specific examples of places where I use names that seem cryptic, please point them out. I will be happy to discuss the reasons behind those names and to change them if those reasons are deemed insufficient after consideration.
A name like 'foldl' and 'foldr' is what I mean.
Quoting from my original reply to Steven: [...] So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr [...] It might not have been clear because I said "opens the door for [...]" and "probably start by [...]", but I actually meant that `fold` and `reverse_fold` __will__ be provided by Hana. The decision is already taken. I take it that the point of your intervention was to make sure this was the case. If you come across other functions that seem to be misnamed, please fill a GitHub issue so we can discuss the problem and resolve it. Regards, Louis
On 3/21/2015 9:06 PM, Louis Dionne wrote:
Edward Diener <eldiener <at> tropicsoft.com> writes:
On 3/21/2015 12:11 PM, Louis Dionne wrote:
[...]
If you have specific examples of places where I use names that seem cryptic, please point them out. I will be happy to discuss the reasons behind those names and to change them if those reasons are deemed insufficient after consideration.
A name like 'foldl' and 'foldr' is what I mean.
Quoting from my original reply to Steven:
[...] So this opens the door for renaming foldl/foldr to fold/reverse_fold. I'll probably start by adding aliases and then consider removing foldl/foldr [...]
It might not have been clear because I said "opens the door for [...]" and "probably start by [...]", but I actually meant that `fold` and `reverse_fold` __will__ be provided by Hana. The decision is already taken. I take it that the point of your intervention was to make sure this was the case.
If you come across other functions that seem to be misnamed, please fill a GitHub issue so we can discuss the problem and resolve it.
The point of my comment was to encourage not to you names like 'foldl/foldr' at all in your programming endeavors. Shorthand names rather than descriptive names always seems to me a bad way to program. No doubt I am sometimes guilty of it myself but the use of short but cryptic mnemonics always seems to me to be bad. Ages ago when memory was scarce and disk space was scarce the micro-computer world may have had a use for these short mnemonics, as in Unix/Linux etc., but nowadays I see no use for it. C++ very smartly has not pursued the cryptic mnemonics of C as a rule and I see little reason why good C++ programmers should ever follow the cryptic menemonics path anymore. It only makes functionality harder to understand and remember.
Edward Diener <eldiener <at> tropicsoft.com> writes:
[...]
The point of my comment was to encourage not to you names like 'foldl/foldr' at all in your programming endeavors. Shorthand names rather than descriptive names always seems to me a bad way to program. No doubt I am sometimes guilty of it myself but the use of short but cryptic mnemonics always seems to me to be bad. Ages ago when memory was scarce and disk space was scarce the micro-computer world may have had a use for these short mnemonics, as in Unix/Linux etc., but nowadays I see no use for it. C++ very smartly has not pursued the cryptic mnemonics of C as a rule and I see little reason why good C++ programmers should ever follow the cryptic menemonics path anymore. It only makes functionality harder to understand and remember.
I understand your point, and I mostly agree with it. Even though I do not consider foldl/foldr to be cryptic, some other names following the same pattern give me nightmares (strto{k,d,f,l,ld,ll,ul,ull}, seriously?). So I think I understand how you can feel about fold{l,r}. However, for the case of `foldl` and `foldr` precisely, those functions are very well known in the functional programming community (see [1] for example). I think this constitutes a good motivation for using those names. This does not change the fact that fold/reverse_fold aliases will be provided for those that want it. I'll try to add them tomorrow. Regards, Louis [1]: http://goo.gl/ropQkM
Bjorn Reese <breese <at> mail1.stofanet.dk> writes:
On 03/22/2015 07:23 AM, Louis Dionne wrote:
I understand your point, and I mostly agree with it. Even though I do not consider foldl/foldr to be cryptic, some other names following the same
How about fold_outwards/fold_inwards (or fold/fold_inwards)
I don't understand which one should be which. I personally don't see how fold left is inwards (or outwards), and ditto for fold right. While aliases for people used to Fusion are provided, it is planned to have fold_right and fold_left, which everyone in the FP community can understand out of the box. See [1] for the resolution regarding foldl/foldr. Regards, Louis [1]: http://github.com/ldionne/hana/issues/18
-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Edward Diener Sent: 21 March 2015 14:41 To: boost@lists.boost.org Subject: Re: [boost] [Hana] Informal review request
On 3/21/2015 10:20 AM, Louis Dionne wrote:
I would like to urge you to use easily understandable names in your library rather than shortened and more cryptic names. Any extra typing a user of your library may have to do is easily offset by the fact that more easily understandable names make your library much more understandable to use.
+1 - definitely. Boost prefers clarity to curtness. So always fold_left rather than foldl. Paul --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830
Louis Dionne <ldionne.2 <at> gmail.com> writes:
Dear Boost,
Here is a non-exhaustive list of some issues that were raised during the informal review of Hana last week, along with an explanation of what I did or am doing to resolve them.
[...]
4. It was suggested that `foldl` and `foldr` be renamed to something else. [...]
fold/reverse_fold aliases are now provided (see [1] for commit). Those aliases follow the behavior of Fusion/MPL closely, with the extension that it's possible to provide no initial state. Specifically, fold(sequence, state, f) == foldl(sequence, state, f) fold(sequence, f) == foldl1(sequence, f) reverse_fold(sequence, state, f) == foldr(sequence, state, flip(f)) reverse_fold(sequence, f) == foldr1(sequence, flip(f))
7. In a different thread [6], it was suggested that the Logical concept should interact well with Lazy computations. [...]
Arbitrary Lazy values and computations can now be used as branches to `eval_if` (see [2] for commit). More generally, anything that can be `eval`uated can be used as branches to `eval_if`, which means nullary lambdas: eval_if(condition, []{ return something; }, other_branch ) unary lambdas (useful for delaying instantiations, explained in the docs): eval_if(condition, [](auto delay) { return delay(f)(something); }, other_branch ) Lazy computations/values: eval_if(condition, lazy(f)(x, y, z), other_branch ) More syntactic sugar will probably be added so that `eval_if` looks prettier. Something along the lines of eval_if(condition)([]{ branch1 }).else_([]{ branch2 }) would be nice. I got this functionality (and more) locally, but I want to study all the possibilities before I check something in. Regards, Louis Dionne [1]: http://goo.gl/6hIWrA [2]: http://goo.gl/6yEhAz
participants (13)
-
Bjorn Reese -
Brian Schrom -
Edward Diener -
Eric Niebler -
Jason Roehm -
Louis Dionne -
Mathias Gaunard -
Matt Calabrese -
Niall Douglas -
Paul A. Bristow -
pfultz2 -
Steven Watanabe -
Vicente J. Botet Escriba