Tagged unions, or ‘variants’, in C(gist.github.com)
gist.github.com
Tagged unions, or ‘variants’, in C
https://gist.github.com/procedural/2e3c212af4f61dde313af1123ddfbbc9
39 comments
I think it's an elegant piece of garbage actually.
All your nitpicks are fairly easy to address.
tag() just needs to take 'a' as another parameter and do a static_assert.
> It relies on struct layout
As in "ptrdiff_t needs to be the first member in a struct"? Oh, the horror. It's C, a language that generally expects you to know what you are doing.
> all the explicit casting means that this has basically no type safety at all
Duh. See above :)
Generally speaking, you are missing a point here. This sort of contraption comes handy when the code needs to add a _bit_ more of invariant checking, but without going over the top. In comparison with a plain union this will help catching the misuse. Granted, it needs to be used correctly itself.
All your nitpicks are fairly easy to address.
+ union zee_tag {
+ ptrdiff_t tag;
+ max_align_t foo;
+ };
+
struct Some {
- ptrdiff_t tag;
+ zee_tag tag;
tag() just needs to take 'a' as another parameter and do a static_assert.
> It relies on struct layout
As in "ptrdiff_t needs to be the first member in a struct"? Oh, the horror. It's C, a language that generally expects you to know what you are doing.
> all the explicit casting means that this has basically no type safety at all
Duh. See above :)
Generally speaking, you are missing a point here. This sort of contraption comes handy when the code needs to add a _bit_ more of invariant checking, but without going over the top. In comparison with a plain union this will help catching the misuse. Granted, it needs to be used correctly itself.
> As in "ptrdiff_t needs to be the first member in a struct"? Oh, the horror. It's C, a language that generally expects you to know what you are doing.
Speaking of garbage, that's some really needless posturing. The comment was about the position of the second element in the structure, I suppose that this wasn't spelled out in the comment but everyone here knows that the first member of a struct is at the beginning.
God forbid you would store __mm128i here, although generally that's an awful idea, it's not unreasonable to want to force 16-byte alignment or the like.
> tag() just needs to take 'a' as another parameter and do a static_assert.
Show me. I'm honestly curious what it would look like.
> Generally speaking, you are missing a point here. This sort of contraption comes handy when the code needs to add a _bit_ more of invariant checking, but without going over the top. In comparison with a plain union this will help catching the misuse. Granted, it needs to be used correctly itself.
Show me a version that adds invariant checking.
Speaking of garbage, that's some really needless posturing. The comment was about the position of the second element in the structure, I suppose that this wasn't spelled out in the comment but everyone here knows that the first member of a struct is at the beginning.
God forbid you would store __mm128i here, although generally that's an awful idea, it's not unreasonable to want to force 16-byte alignment or the like.
> tag() just needs to take 'a' as another parameter and do a static_assert.
Show me. I'm honestly curious what it would look like.
> Generally speaking, you are missing a point here. This sort of contraption comes handy when the code needs to add a _bit_ more of invariant checking, but without going over the top. In comparison with a plain union this will help catching the misuse. Granted, it needs to be used correctly itself.
Show me a version that adds invariant checking.
> The comment was about the position of the second element in the structure, I suppose that this wasn't spelled out in the comment but everyone here knows that the first member of a struct is at the beginning.
Wit beyond measure, fascinating.
> Show me.
An exercise left to the reader.
Wit beyond measure, fascinating.
union zee_tag {
ptrdiff_t tag;
max_align_t foo;
};
static inline void * variant_cast(void * variant_ptr, ptrdiff_t desired_tag) {
ptrdiff_t * variant_tag = (ptrdiff_t *)variant_ptr;
assert(*variant_tag == desired_tag);
- return (void *)((char *)variant_ptr + sizeof(ptrdiff_t));
+ return (void *)((char *)variant_ptr + sizeof(union zee_tag));
}
> Show me.
@@ -15,6 +15,9 @@
#define is(x, T) ((x)->tag == tag(T))
#define as(x, T) ((struct T *)variant_cast((void *)(x), tag(T)))
+#define union_field(T) struct T _##T
+#define tag_union(x, T) (x)->tag = ((x)->_##T, (ptrdiff_t)&Tag##T)
+
struct SomeOne {
int x;
int y;
@@ -25,17 +28,24 @@
float w;
} TagSomeTwo;
+struct SomeThree {
+ float zz;
+ float ww;
+} TagSomeThree;
+
struct Some {
ptrdiff_t tag;
union {
- struct SomeOne _;
- struct SomeTwo __;
+ union_field( SomeOne );
+ union_field( SomeTwo );
};
};
int main() {
struct Some a = {};
- a.tag = tag(SomeTwo);
+
+ tag_union(&a, SomeTwo);
+ tag_union(&a, SomeThree);
printf("Is `a` tagged as SomeTwo: %d\n", is(&a, SomeTwo));
An exercise left to the reader.
> Wit beyond measure, fascinating.
I'm flattered that you want to talk about me, but I'd rather talk about the code.
> An exercise left to the reader.
That's really the only interesting part, isn't it? All the other stuff is just minor bugfixes / bikeshedding. I said "show me" the version of tag() that does the static_assert, and "show me" a version that adds invariant checking (that the cast is possible). Neither of these things have been shown. I'm not claiming it's impossible, just that subjectively, this version is worse than doing things the boring way.
I'm flattered that you want to talk about me, but I'd rather talk about the code.
> An exercise left to the reader.
That's really the only interesting part, isn't it? All the other stuff is just minor bugfixes / bikeshedding. I said "show me" the version of tag() that does the static_assert, and "show me" a version that adds invariant checking (that the cast is possible). Neither of these things have been shown. I'm not claiming it's impossible, just that subjectively, this version is worse than doing things the boring way.
If you don't understand that tag_union(&a, SomeThree) throwing a compile time error is functionally equivalent to static_assert(), then I see no point in continuing this exchange. Ditto for the invariant checking - OP's original code already covered that with its assert(). In fact, that assert() is what this whole thing is about.
All points in your opening "garbage" comment were trivial nitpicks, which would've been fine if you didn't decide to express them by trashing other person's code in an overly confident manner. I don't appreciate that, just as I don't appreciate you trying to wiggle out from this exchange on technicalities.
All points in your opening "garbage" comment were trivial nitpicks, which would've been fine if you didn't decide to express them by trashing other person's code in an overly confident manner. I don't appreciate that, just as I don't appreciate you trying to wiggle out from this exchange on technicalities.
Yes, you're right, tag_union does throw a compile time error, I didn't read that correctly. By your earlier comment I was primed for a `_Static_assert` and when I didn't see that. I thought it had been left out entirely rather than reimplemented in a different manner.
On the subject of tone--I honestly believe that the original code has severe subjective design flaws and objective implementation errors, and since the post was gathering upvotes but no critique I was worried that people believed that the code was correct. There are still some nitpicks about your new version, but these are fairly minor in my view (the use of reserved identifiers is pretty tedious and easily avoided). The remaining non-nitpick, what I consider to be a show-stopper, is that you can't switch on the tag. 90% of the time when I'm using a tagged union, I'm doing switch (evt->type). While we can substitute a chain of if/else, I'm not fond of the ergonomics and I would prefer a traditional enum. This is a subjective trade-off, however.
Your responses would have been fine if they were criticisms of my argument or of the tone I took. Perhaps I crossed the line, and you called me on it? But these comments are unacceptable ad hominems:
> Oh, the horror. It's C, a language that generally expects you to know what you are doing.
> Wit beyond measure, fascinating.
On the subject of tone--I honestly believe that the original code has severe subjective design flaws and objective implementation errors, and since the post was gathering upvotes but no critique I was worried that people believed that the code was correct. There are still some nitpicks about your new version, but these are fairly minor in my view (the use of reserved identifiers is pretty tedious and easily avoided). The remaining non-nitpick, what I consider to be a show-stopper, is that you can't switch on the tag. 90% of the time when I'm using a tagged union, I'm doing switch (evt->type). While we can substitute a chain of if/else, I'm not fond of the ergonomics and I would prefer a traditional enum. This is a subjective trade-off, however.
Your responses would have been fine if they were criticisms of my argument or of the tone I took. Perhaps I crossed the line, and you called me on it? But these comments are unacceptable ad hominems:
> Oh, the horror. It's C, a language that generally expects you to know what you are doing.
> Wit beyond measure, fascinating.
> Let's not try to implement new language features on top of C with macros.
Thank you for that. This happens though, in fact I've done it because the CEO of a company I worked for did not want to use anything but C and the project had a bunch of requirements that were very hard to meet with C. It's surprising how far you can get with that approach but in the end it is simply the wrong way to approach the problem. The right tool for the job is the best way to start any job.
Thank you for that. This happens though, in fact I've done it because the CEO of a company I worked for did not want to use anything but C and the project had a bunch of requirements that were very hard to meet with C. It's surprising how far you can get with that approach but in the end it is simply the wrong way to approach the problem. The right tool for the job is the best way to start any job.
It's true that this implementation is wrong, but I disagree that it's a bad idea. Certainly it's possible to do correctly in various ways, e.g. by having the macro pass offsetof(Some, the_union) (but the existing code doesn't name the union and there would have to be consideration for multiple variant types).
"Certainly it's possible to do correctly in various ways"
Not very convincing. At the very least, you'd need to pass in the type name as a macro parameter, use non-portable GCC extensions, or define some additional boilerplate for each union type. We can't just say "offsetof" and handwave the actual macro definition here.
The traditional solution, to define an enum type, works reasonably. You can certainly get silent type errors from typos but perhaps we can tolerate the risk. It's not worse than, say, qsort in terms of type safety.
The options I alluded to above are due to the fact that in order to allow the compiler to type-check for us, we need to keep the type of "x" passed in to "as()". You need to check the tag and either abort or return the correct union member. So "x" appears twice, but that's a bad idea for a macro. So you either use the GCC extension which allows statements as expressions, or you dispatch to a boilerplate function for each union type. I can't think of a different way to do things.
Not very convincing. At the very least, you'd need to pass in the type name as a macro parameter, use non-portable GCC extensions, or define some additional boilerplate for each union type. We can't just say "offsetof" and handwave the actual macro definition here.
The traditional solution, to define an enum type, works reasonably. You can certainly get silent type errors from typos but perhaps we can tolerate the risk. It's not worse than, say, qsort in terms of type safety.
The options I alluded to above are due to the fact that in order to allow the compiler to type-check for us, we need to keep the type of "x" passed in to "as()". You need to check the tag and either abort or return the correct union member. So "x" appears twice, but that's a bad idea for a macro. So you either use the GCC extension which allows statements as expressions, or you dispatch to a boilerplate function for each union type. I can't think of a different way to do things.
> Not very convincing.
Sorry, I was in a hurry when I wrote that comment :)
The easiest way is to take advantage of the fact that a pointer to a union can be casted to a pointer to one of its members (C11 6.7.2.1.16), or in other words that all the possible variants are at the same offset. So we can do:
An alternative would be one of the options you mentioned, a boilerplate function. But it doesn't have to be 'real' boilerplate: it's possible to use macros to automate the definition of such functions. Given suitable macros, you can write something like:
Sorry, I was in a hurry when I wrote that comment :)
The easiest way is to take advantage of the fact that a pointer to a union can be casted to a pointer to one of its members (C11 6.7.2.1.16), or in other words that all the possible variants are at the same offset. So we can do:
typedef struct Some variantof_SomeOne;
#define as(x, T) ((struct T *)variant_cast(x, tag(T), \
offsetof(variantof_##T, u)))
An alternative would be one of the options you mentioned, a boilerplate function. But it doesn't have to be 'real' boilerplate: it's possible to use macros to automate the definition of such functions. Given suitable macros, you can write something like:
#define FOO_FIELDS(f) \
f(one, struct bar) \
f(two, float) \
f(three, int)
DEFINE_VARIANT(foo, FOO_FIELDS)
enum foo_tag { foo_tag_one, foo_tag_two, foo_tag_three };
struct foo {
enum foo_tag tag;
union {
struct bar one;
float two;
int three;
};
};
static inline bool
foo_is_one(struct foo *fo) {
return foo->tag == foo_tag_one;
}
static inline struct bar *
foo_get_one(struct foo *foo) {
assert(foo->tag == foo_tag_one);
return &foo->one;
}
[etc. for other variants]> It relies on struct layout, and if anything has wider alignment than ptrdiff_t, it's broken.
I think you're wrong about this. I'm pretty certain a pointer to a struct is always equivilent to a pointer to the first member, except for the type. I went and looked it up in C11 (6.7.2.1 point 15):
> A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.
Edit: A duh, the + sizeof(ptrdiff_t) is the part that's wrong. Yeah, agreed.
I think you're wrong about this. I'm pretty certain a pointer to a struct is always equivilent to a pointer to the first member, except for the type. I went and looked it up in C11 (6.7.2.1 point 15):
> A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.
Edit: A duh, the + sizeof(ptrdiff_t) is the part that's wrong. Yeah, agreed.
Yes - this is what allows you to some semblance of struct inheritance. You can embed a structure as the first member in the 'derived' structure and then up and down cast as appropriate.
I'm not a C programmer, but isn't there some directive you can add to a union to tightly pack it, or specify member memory locations or something? So that then you could guarantee that for the Some struct, `ptrdiff_t tag;` starts at offset 0 and the union starts at offset `sizeof(ptrdiff_t)`?
That doesn't help if your architecture doesn't support unaligned access.
The compiler is allowed to insert padding for a good reason, and packing is rarely the right solution for anything.
The compiler is allowed to insert padding for a good reason, and packing is rarely the right solution for anything.
Is there a reason, other than jargon, why this concept is called different names in different languages?
Do variants work different than tagged unions or type classes?
Some people told me that Haskell is superior in FP because of its type classes. Later I read TypeScript has tagged unions, which looked like type classes to me.
Then I looked into Reason and they wrote about variants and I also was reminded of type classes.
Do variants work different than tagged unions or type classes?
Some people told me that Haskell is superior in FP because of its type classes. Later I read TypeScript has tagged unions, which looked like type classes to me.
Then I looked into Reason and they wrote about variants and I also was reminded of type classes.
Tagged unions are an implementation of variants using a discriminating tag and a union type.
Variants are sometimes called sum types to emphasize the duality with product types (tuples).
Type classes are a completely unrelated concept, as others have already commented. They are more like vtables in C++: providing functions to operate on an otherwise opaque object.
Variants are sometimes called sum types to emphasize the duality with product types (tuples).
Type classes are a completely unrelated concept, as others have already commented. They are more like vtables in C++: providing functions to operate on an otherwise opaque object.
Ah okay.
I thought they were the Haskell equivalent.
I also don't know what vtables are, haha.
I thought they were the Haskell equivalent.
I also don't know what vtables are, haha.
I don't want to be that guy but there is pretty solid explanation of vtables if you do a web search.
Some of the language also derives from either more traditional set theory (union, disjoint union, discriminated union) or from category theory (sum, coproduct) even though all of these things might mean the same concept in this particular case. Category theory is comparatively "new" (barely 70 years old) and so older works and languages tend not to use it.
Some of the language also derives from either more traditional set theory (union, disjoint union, discriminated union) or from category theory (sum, coproduct) even though all of these things might mean the same concept in this particular case. Category theory is comparatively "new" (barely 70 years old) and so older works and languages tend not to use it.
nothing wrong with being that guy but at the same time there's also nothing wrong with admitting you don't know what something is before you go and look it up. i don't want to be that guy but the poster you responded to didn't ask what they were, only stated that they don't know what they are. im sure if they were curious enough and thought it relevant enough to their knowledge base they would go look it up of their own accord.
also, another point I'd really like to bring up is, while in general im comfortable with doing research and learning something from resources on the web, some people are less confident in their abilities to understand something and would prefer to ask another human being to explain it so they can open up the possibility of discussion if they don't particularly understand the verbiage or concepts contained within the answer; it's much easier to ask a person a question than to ask an article or a tutorial one when said resource may not even be actively maintained or monitored anymore and social interaction may have potentially died down on it.
im not trying to really complain as I do believe everyone should really take the time to do their own research and come to their own conclusions, but having someone they can ask is useful in and of itself in the same way having a professor in college you can ask to clarify is being useful. if you don't have another individual that is knowledgeable about the concepts you're unsure about your perception of to potentially confirm or deny your conclusions, then you're basically operating on unknown unknowns, and as far as I understand, in intellectual practice, it is the desire of the practitioner to eliminate any possible unknown unknowns through whatever means necessary and account for all possibilities and deviations.
but yeah, Google first then ask questions!
also, another point I'd really like to bring up is, while in general im comfortable with doing research and learning something from resources on the web, some people are less confident in their abilities to understand something and would prefer to ask another human being to explain it so they can open up the possibility of discussion if they don't particularly understand the verbiage or concepts contained within the answer; it's much easier to ask a person a question than to ask an article or a tutorial one when said resource may not even be actively maintained or monitored anymore and social interaction may have potentially died down on it.
im not trying to really complain as I do believe everyone should really take the time to do their own research and come to their own conclusions, but having someone they can ask is useful in and of itself in the same way having a professor in college you can ask to clarify is being useful. if you don't have another individual that is knowledgeable about the concepts you're unsure about your perception of to potentially confirm or deny your conclusions, then you're basically operating on unknown unknowns, and as far as I understand, in intellectual practice, it is the desire of the practitioner to eliminate any possible unknown unknowns through whatever means necessary and account for all possibilities and deviations.
but yeah, Google first then ask questions!
Sure, problem is when you 'think' you know something, but you don't, as I thought type classes are equivalent to variants :D
I don't think the word "sum" for disjoint union comes from category theory. It must be older than that.
[deleted]
Variants, sum types and type classes are all different notions. In PureScript variants (https://github.com/natefaubion/purescript-variant) are used to have a homogeneous sum type that mixes different types, sum types is a single type with multiple constructors. Type classes others already explained.
The tagged union/variant idea does not correspond to a Haskell type class. In fact it doesn't really even have a name in Haskell it's just the "sum type" aspect of a "algebraic data types" (which constitutes sums, products and functions, basically).
Type classes are a completely different concept. Tagged unions are sum types.
[deleted]
I see.
Care to explain what type classes are then? :)
Care to explain what type classes are then? :)
They’re known in other languages as interfaces, traits, or protocols: just a set of methods which can be implemented for different types.
Importantly, it’s possible to implement type classes for existing types in a separate declaration, as opposed to traditional OO languages where a list of implemented interfaces has to be declared upfront as part of the class declaration. Thus, for instance, a client of a library can declare its own type class and implement it for the library’s types. (Many languages other than Haskell support this too, though.)
Importantly, it’s possible to implement type classes for existing types in a separate declaration, as opposed to traditional OO languages where a list of implemented interfaces has to be declared upfront as part of the class declaration. Thus, for instance, a client of a library can declare its own type class and implement it for the library’s types. (Many languages other than Haskell support this too, though.)
So they're a bit like open classes in Ruby or implicit conversions in Scala?
They achieve the same result, but in a quite different way. I see them as decoupling the "implements X" piece of a traditional OO class in a language that has interfaces from the class itself.
A "type class" specifies an interface and you can make types into "instances" of a "type class" by saying how it implements that interface.
Any drawbacks of using these #defines? It looks awesome
#define var __auto_type
#define let __auto_type const
variant_cast is just garbage. It relies on struct layout, and if anything has wider alignment than ptrdiff_t, it's broken. For example, a double in 32-bit PowerPC has 64-bit alignment but ptrdiff_t is 32 bits, so the pointer is wrong. Maybe x64 you get away with it for most types (not all!), but can you raise your right hand and solemnly swear that you'll never ever want to port to a non-x64 system?
Additionally, all the explicit casting means that this has basically no type safety at all. I can a.tag = tag(SomeThree) even though SomeThree is not a member of a's type, and then I will be able to successfully let b = as(&a, SomeThree) and boom! I've just scribbled over memory without so much as a peep from the compiler. What is the of having tagged unions (a TYPE SAFETY FEATURE) if your tagged union implementation is LESS type safe than untagged unions?
This last point is actually a bit subtle… accessing the wrong member of a union is probably not what you want to do most of the time, but the language in the C standard is quite clear (see DR #257, language was clarified in C99 but present in earlier versions) and accessing the wrong union member just gives you whatever you stored in a union reinterpreted as whatever you read out of it. But this tagged union implementation lets you access a union member which doesn't even exist.
Let's not try to implement new language features on top of C with macros. It never ends well. Either figure out a way to live with a little boilerplate or use a different language, those are the only sane options.