5 ms·

Tagged unions, or ‘variants’, in C

30 points by Procedural 9y ago

k__ 9y ago
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.
- tome 9y ago
  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).
  - k__ 9y ago
    I see. I thought that type classes are sum types also.
    - tome 9y ago
      You can sort of consider them as open sum types which third parties can add additional summands to but that's probably not a very helpful way of thinking about them.
- greydius 9y ago
  Type classes are a completely different concept. Tagged unions are sum types.
  - deleted 9y ago
    [deleted]
  - k__ 9y ago
    I see. Care to explain what type classes are then? :)
    - tome 9y ago
      A "type class" specifies an interface and you can make types into "instances" of a "type class" by saying how it implements that interface.
    - comex 9y ago
      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.)
      - k__ 9y ago
        So they're a bit like open classes in Ruby or implicit conversions in Scala?
        lmm 9y ago
        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.
        jnbiche 9y ago
        If you're familiar with Scala, then type classes in Haskell are pretty close to traits in Scala (but not implicit conversions, which can make use of traits, but are an orthogonal language feature). They're also close to Rust's traits, it you're familiar with Rust.
        9y ago
- yorwba 9y ago
  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.
  - k__ 9y ago
    Ah okay. I thought they were the Haskell equivalent. I also don't know what vtables are, haha.
    - klodolph 9y ago
      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.
      - deleted 9y ago
        [deleted]
      - ozzmotik 9y ago
        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!
- coot_ 9y ago
  Variants, sum types and type classes are all different notions. In PureScript variants (https://github.com/natefaubion/purescript-variant 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.
klodolph 9y ago
No, no, no! This is terrible! 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.
- comex 9y ago
  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).
  - klodolph 9y ago
    "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.
valbaca 9y ago
Any drawbacks of using these #defines? It looks awesome #define var __auto_type #define let __auto_type const

30 points by Procedural 9y ago

k__ 9y ago

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.

tome 9y ago
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).
- k__ 9y ago
  I see. I thought that type classes are sum types also.
  - tome 9y ago
    You can sort of consider them as open sum types which third parties can add additional summands to but that's probably not a very helpful way of thinking about them.
greydius 9y ago
Type classes are a completely different concept. Tagged unions are sum types.
- deleted 9y ago
  [deleted]
- k__ 9y ago
  I see. Care to explain what type classes are then? :)
  - tome 9y ago
    A "type class" specifies an interface and you can make types into "instances" of a "type class" by saying how it implements that interface.
  - comex 9y ago
    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.)
    - k__ 9y ago
      So they're a bit like open classes in Ruby or implicit conversions in Scala?
      - lmm 9y ago
        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.
      - jnbiche 9y ago
        If you're familiar with Scala, then type classes in Haskell are pretty close to traits in Scala (but not implicit conversions, which can make use of traits, but are an orthogonal language feature). They're also close to Rust's traits, it you're familiar with Rust.
        9y ago
yorwba 9y ago
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.
- k__ 9y ago
  Ah okay. I thought they were the Haskell equivalent. I also don't know what vtables are, haha.
  - klodolph 9y ago
    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.
    - deleted 9y ago
      [deleted]
    - ozzmotik 9y ago
      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!
coot_ 9y ago
Variants, sum types and type classes are all different notions. In PureScript variants (https://github.com/natefaubion/purescript-variant 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.

klodolph 9y ago

No, no, no! This is terrible! 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.

comex 9y ago
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).
- klodolph 9y ago
  "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.

valbaca 9y ago

Any drawbacks of using these #defines? It looks awesome #define var __auto_type #define let __auto_type const