[hana]Either generalization & missing variant

older
[metaparse] Review period starts...

Larry Evans

8 Jun 2015 8 Jun '15

3:12 p.m.

The page: http://ldionne.com/hana/structboost_1_1hana_1_1Either.html contains: An Either contains either a left value or a right value, both of which may have different data types. An Either containing a left value a is represented as left(a), and an Either containing a right value b is represented as right(b). which makes anyone familiar with boost::variant to think that hana's Either is simply a binary boost::variant, and left(a) ~=~ variant(a) right(b) ~=~ variant(b) where ~=~ means some sort of similarity. However, since the left and right functions only have 1 argument and no template arguments, they can't produce something like variant where the left and right types are known. IOW, it seems that left and right are just wrapper's around the types. Looking at the code, the wrappers, _left and _right are defined here: https://github.com/ldionne/hana/blob/master/include/boost/hana/either.hpp#L3... https://github.com/ldionne/hana/blob/master/include/boost/hana/either.hpp#L7... But why should Either be limited just to _left and _right wrappers. Why not provide wrapper's tagged by some enumerable? For example, something like this: template < typename X , typename Enumerable=unsigned , Enumerable tag=Tag() > struct _tagged //instead of _left and _right : operators::adl { X value; . . . template constexpr decltype(auto) go(F...&& f) const& { return (hana::arg(f...))(value); } . . . }; This would be more general than the binary Either. In addition, _tagged could be used elsewhere. For example, it could be used in a multiple inheritance implementation of tuple. _tagged is already present in a more general form, in fusion: http://www.boost.org/doc/libs/1_39_0/libs/fusion/doc/html/fusion/support/pai... where: _tagged ~=~ fusion::pair,X> The obvious advantage of Either is that it doesn't require memory use equal to the max of the components when the component with the minimum size is used. IOW, left(a) only requires sizeof(A) and right(b) only requires sizeof(B). OTOH, Either, or the generalization described above, can't be used where a true variant is needed, for example, in spirit's attributes for the alternative parser. And this brings up another question. Although hana has a tuple, it doesn't have a variant. Is there any reason for excluding variant from hana? -regards, Larry

Show replies by date

Larry Evans

8 Jun 8 Jun

4:53 p.m.

On 06/08/2015 10:12 AM, Larry Evans wrote: [snip]

...

wrappers. Why not provide wrapper's tagged by some enumerable? For example, something like this:

template < typename X , typename Enumerable=unsigned , Enumerable tag=Tag() > struct _tagged //instead of _left and _right : operators::adl { X value; . . . template constexpr decltype(auto) go(F...&& f) const& { return (hana::arg(f...))(value); } . . . };

This would be more general than the binary Either. In addition, _tagged could be used elsewhere. For example, it could be used in a multiple inheritance implementation of tuple.

Which I see hana actually does here: https://github.com/ldionne/hana/blob/master/include/boost/hana/detail/closur... but instead of _tagged, element is used where element is at: https://github.com/ldionne/hana/blob/master/include/boost/hana/detail/closur... [snip]

Louis Dionne

6:07 p.m.

Larry Evans writes:

...

The page:

http://ldionne.com/hana/structboost_1_1hana_1_1Either.html

contains:

[...]

which makes anyone familiar with boost::variant to think that hana's Either is simply a binary boost::variant, and

left(a) ~=~ variant(a) right(b) ~=~ variant(b)

where ~=~ means some sort of similarity.

[...]

But why should Either be limited just to _left and _right wrappers. Why not provide wrapper's tagged by some enumerable? For example, something like this:

[...]

Funny you brought this up; I just decided this morning to remove Either from the official documentation to give me some more time to think about it, and then I read your email. Either is effectively a binary variant, which could be generalized. However, since it is meant to be a static variant, i.e. one whose internal type is known at compile-time, it is in some sense equivalent to just an object of that type. It is also implemented precisely as such. There is a different mathematical way to view Hana's Either which makes it an actual variant over something, and this is the reason I initially added Either; mainly for completeness and for trying to validate the correctness of this mathematical viewpoint. However, I have frankly not found any actual use case for Either, so I ignored it for a while and now I decided to set it aside until I have a better idea of how/if it can be useful.

...

[...]

OTOH, Either, or the generalization described above, can't be used where a true variant is needed, for example, in spirit's attributes for the alternative parser. And this brings up another question. Although hana has a tuple, it doesn't have a variant. Is there any reason for excluding variant from hana?

I will assume you mean an actual runtime variant (like `boost::variant`). I'd say there are two reasons for this omission. 1. In the mathematical construction upon which Hana stands, sum types are exactly Either as currently implemented. An actual runtime variant can't be implemented (while staying in that mathematical universe). However, runtime variants might be a very useful addition to Hana, allowing one to have a compile-time computation depending on a runtime value to return a runtime variant instead of failing because the result can't be determined at compile-time, like it currently does. This brings us to the second point. 2. I have focused strictly on implementing "compile-time" data structures for now, since that was a sufficiently large task. So I have not taken the time to think deeply about including runtime data structures like a rutime variant, and the effect that would have on the library. I think it is an interesting path to explore. However, I think it might be better to rely on an existing variant implementation and provide adapters for it rather than try to reinvent the wheel (plus I've heard implementing variant cleverly was rather challenging). So the bottom line is: Hana does not officially provide a sum type (variant/Either) for now, and it is not useful as far as my experience shows. However, I will take some more time to think about it and come up with a good reason to exclude it or a better/generalized interface for it, but after the review. See it as a potential feature of a future version of the library. Regards, Louis

Larry Evans

7 p.m.

On 06/08/2015 01:07 PM, Louis Dionne wrote:

...

Larry Evans writes:

...
The page:

http://ldionne.com/hana/structboost_1_1hana_1_1Either.html

contains:

[...]

which makes anyone familiar with boost::variant to think that hana's Either is simply a binary boost::variant, and

left(a) ~=~ variant(a) right(b) ~=~ variant(b)

where ~=~ means some sort of similarity.

[...]

But why should Either be limited just to _left and _right wrappers. Why not provide wrapper's tagged by some enumerable? For example, something like this:

[...]

Funny you brought this up; I just decided this morning to remove Either from the official documentation to give me some more time to think about it, and then I read your email.

Either is effectively a binary variant, which could be generalized. However, since it is meant to be a static variant, i.e. one whose internal type is known at compile-time, it is in some sense equivalent to just an object of that type. It is also implemented precisely as such.

There is a different mathematical way to view Hana's Either which makes it an actual variant over something, and this is the reason I initially added Either; mainly for completeness and for trying to validate the correctness of this mathematical viewpoint.

What puzzled me was initially, was that left(a) and right(b) produced _left<A> and _right<B> and there was no indication that the result was of type either_t, where either_t is a variant like in boost::variant. Hence, I don't think the way hana implements Either, it can truly be a discriminated union because _left<A> has no information about what the other possible alternative values are in either_t.

...

However, I have frankly not found any actual use case for Either, so I ignored it for a while and now I decided to set it aside until I have a better idea of how/if it can be useful.

...
[...]

OTOH, Either, or the generalization described above, can't be used where a true variant is needed, for example, in spirit's attributes for the alternative parser. And this brings up another question. Although hana has a tuple, it doesn't have a variant. Is there any reason for excluding variant from hana?

I will assume you mean an actual runtime variant (like `boost::variant`).

Yes.

...

I'd say there are two reasons for this omission.

1. In the mathematical construction upon which Hana stands, sum types are exactly Either as currently implemented. An actual runtime variant can't be implemented (while staying in that mathematical universe). However, runtime variants might be a very useful addition to Hana, allowing one to have a compile-time computation depending on a runtime value to return a runtime variant instead of failing because the result can't be determined at compile-time, like it currently does. This brings us to the second point.

That's what I would have thought. IOW, the type returned by get depends on the *runtime* value of the discriminant (the value returned by variant::which(). However, I think there have been some constexpr get's for variant structures, at least as for as I can tell from reading: https://github.com/eggs-cpp/variant/blob/master/include/eggs/variant/detail/... and: http://article.gmane.org/gmane.comp.lib.boost.devel/259044 which says:

...

yet. The egg code mentioned by gonzalobg88 <at> gmail.com:

https://github.com/eggs-cpp/variant/blob/master/include/eggs/variant/detail/...

...

had several constexpr( or at least EGGS_CXX11_CONSTEXPR) functions. Are one of those requiring a recursive union for implementation?

Yes, pretty much all of them require a recursive union for constexpr support. The details can be found here http://talesofcpp.fusionfenix.com/post-20/eggs.variant---part-ii-the-constex... and here https://akrzemi1.wordpress.com/2012/12/13/constexpr-unions/ [snip]

...

So the bottom line is: Hana does not officially provide a sum type (variant/Either) for now, and it is not useful as far as my experience shows.

spirit uses variants as the attributes of alternative parsers: https://github.com/djowel/spirit_x3/blob/master/example/x3/calc5.cpp#L43 Is there something spirit could be using instead?

...

However, I will take some more time to think about it and come up with a good reason to exclude it or a better/generalized interface for it, but after the review. See it as a potential feature of a future version of the library.

Thanks Louis. -regards, Larry

Louis Dionne

9:33 p.m.

Larry Evans writes:

...

[...]

What puzzled me was initially, was that left(a) and right(b) produced _left<A> and _right<B> and there was no indication that the result was of type either_t, where either_t is a variant like in boost::variant. Hence, I don't think the way hana implements Either, it can truly be a discriminated union because _left<A> has no information about what the other possible alternative values are in either_t.

That is true; in its current form, no actual type checking was done to ensure that only things of type A or B were put in the Either. That is also in line with the decision not to provide parameterized data types. You can find a discussion related to your question at [1]. If you're still puzzled after reading it, please let me know and I will clarify.

...

[...]

...
I'd say there are two reasons for this omission.

1. In the mathematical construction upon which Hana stands, sum types are exactly Either as currently implemented. An actual runtime variant can't be implemented (while staying in that mathematical universe). However, runtime variants might be a very useful addition to Hana, allowing one to have a compile-time computation depending on a runtime value to return a runtime variant instead of failing because the result can't be determined at compile-time, like it currently does. This brings us to the second point.

That's what I would have thought. IOW, the type returned by get depends on the *runtime* value of the discriminant (the value returned by variant::which(). However, I think there have been some constexpr get's for variant structures, at least as for as I can tell from reading:

The difference is quite subtle, and it has to do with the problem of constexpr stripping explained at [2]. Basically, Hana's Either was supposed to be able to provide a `which()` returning a compile-time value, even if the Either itself was only known at runtime. The only way to achieve this is to encode the discriminant into the type of the Either object. In contrast, Egg's variant can only guarantee that the discriminant will be known at compile-time if everything in the variant is also known at compile-time. That can be achieved by making the which() function constexpr and making sure that the constexpr-ness of the contents of the variant is preserved by the variant. However, initializing the variant with a non-constexpr value will make it impossible to retrieve the discriminant at compile-time. The benefit of Hana's approach was that you could know the content of your variant at compile-time, whatever those contents where, which makes it useful for __static heterogeneous__ programming. The benefit of runtime variants is that they project several types T1, ..., Tn into a single type variant, which can then be used to do __dynamic heterogeneous__ programming. The goals are different.

...

[...]

...
So the bottom line is: Hana does not officially provide a sum type (variant/Either) for now, and it is not useful as far as my experience shows.

spirit uses variants as the attributes of alternative parsers:

https://github.com/djowel/spirit_x3/blob/master/example/x3/calc5.cpp#L43

Is there something spirit could be using instead?

IIUC, Spirit really needs __runtime__ variants, because they are used to store the result of parsing a string, which is done at runtime. In other words, you need the __actual__ type of the object held in the variant to be determinable at runtime, because that information is only available at runtime. You couldn't use Hana's Either, because the actual C++ type of your Either will change depending on the type of the object held in it. Regards, Louis [1]: https://groups.google.com/forum/#!topic/boost-devel-archive/H4_X1y0n7mU [2]: http://ldionne.com/hana/#tutorial-appendix-constexpr-stripping

Gonzalo BG

9 Jun 9 Jun

7:57 a.m.

While a constexpr variant is a very useful utility its scope for meta-programming is limited. IIRC a constexpr variant can only hold types that are trivially_destructible (a recursive union with an user-defined destructor is not constexpr). To allow mutation the types it holds must be trivially_constructible, and trivially_copy_constructible/assignable. These requirements are pretty strict. Given such a variant type, variant should work tho. I don't know how useful this is but maybe this is what Larry Evans had in mind. Anyhow, implementing a variant seems completely out-of-scope for Hana. Bests, Gonzalo

Michael Caisse

8 Jun 8 Jun

7:19 p.m.

On 06/08/2015 11:07 AM, Louis Dionne wrote:

...

2. I have focused strictly on implementing "compile-time" data structures for now, since that was a sufficiently large task. So I have not taken the time to think deeply about including runtime data structures like a rutime variant, and the effect that would have on the library. I think it is an interesting path to explore. However, I think it might be better to rely on an existing variant implementation and provide adapters for it rather than try to reinvent the wheel (plus I've heard implementing variant cleverly was rather challenging).

So the bottom line is: Hana does not officially provide a sum type (variant/Either) for now, and it is not useful as far as my experience shows. However, I will take some more time to think about it and come up with a good reason to exclude it or a better/generalized interface for it, but after the review. See it as a potential feature of a future version of the library.

Adapters to existing variants makes sense to me. It is the approach already used: http://www.boost.org/doc/libs/1_58_0/doc/html/boost/make_variant_over.html Converting a type list to a variant is a common thing I need to do. Creating yet-one-more-variant type is probably not in Hana's best interest. Variant is a priority for C++17 and there are already a variety of other implementations. If you provide an adapter for boost::variant (possibly as a util so it isn't a dependency of the core library) then that may satisfy the concerns. Optionally, getting an MPL style typelist from Hana would also solve these types of interfacing issues. michael -- Michael Caisse ciere consulting ciere.com

Louis Dionne

8:55 p.m.

Michael Caisse writes:

...

[...]

Converting a type list to a variant is a common thing I need to do. Creating yet-one-more-variant type is probably not in Hana's best interest. Variant is a priority for C++17 and there are already a variety of other implementations.

If you provide an adapter for boost::variant (possibly as a util so it isn't a dependency of the core library) then that may satisfy the concerns. Optionally, getting an MPL style typelist from Hana would also solve these types of interfacing issues.

If all you need is to make a variant type (boost::variant<...>) from a sequence of types (make_tuple(type<T>...) in Hana), the following will do: auto types = make_tuple(...); // a tuple of Type objects in Hana using Variant = decltype(unpack(types, template_boost::variant))::type; // Variant is now your boost::variant<...> Basically, we're considering boost::variant as a function on types (via template_), and then we're applying that function to the contents of the tuple (via unpack). Finally, we take everything back to the type level by using decltype(...)::type. Regards, Louis

Michael Caisse

8:57 p.m.

On 06/08/2015 01:55 PM, Louis Dionne wrote:

...

Michael Caisse writes:

...
[...]

Converting a type list to a variant is a common thing I need to do. Creating yet-one-more-variant type is probably not in Hana's best interest. Variant is a priority for C++17 and there are already a variety of other implementations.

If you provide an adapter for boost::variant (possibly as a util so it isn't a dependency of the core library) then that may satisfy the concerns. Optionally, getting an MPL style typelist from Hana would also solve these types of interfacing issues.

If all you need is to make a variant type (boost::variant<...>) from a sequence of types (make_tuple(type<T>...) in Hana), the following will do:

auto types = make_tuple(...); // a tuple of Type objects in Hana using Variant = decltype(unpack(types, template_boost::variant))::type; // Variant is now your boost::variant<...>

Basically, we're considering boost::variant as a function on types (via template_), and then we're applying that function to the contents of the tuple (via unpack). Finally, we take everything back to the type level by using decltype(...)::type.

Regards, Louis

Thank you for the example Louis. -- Michael Caisse ciere consulting ciere.com

3461

Age (days ago)

3462

Last active (days ago)

List overview

Download

8 comments

4 participants

participants (4)

Gonzalo BG
Larry Evans
Louis Dionne
Michael Caisse