4 ms·

Most of my enums are sums of types that don't have any intersection. You can think e.g. of a type Token that is a sum of Identifier, Number, etc. It's annoying

Most of my enums are sums of types that don't have any intersection. You can think e.g. of a type Token that is a sum of Identifier, Number, etc. It's annoying to keep wrapping Identifier in Token, instead of just assigning. I solve that by writing generic functions that accept anything that implements the From trait, but it's still boilerplate all the same. There is no shifting of cost from compile time to runtime, or slowing down access. Just like with sum types you're writing match clauses from time to time, with union types you do the same. If you need to inspect the discriminant, then you need to inspect the discriminant.

MrJohz 3y ago
There is some runtime complexity here though. With both enums and sum types, if you want to differentiate the types at runtime, you need to include a discriminant in order to be able to do that. Enums include that discriminant explicitly (that's what the `Token::Identifier(...)`/`Token::Number(...)` part represents). The memory layout for, say, a base identifier can consist only of the necessary fields for that identifies, but when it gets wrapped it will get an extra field that identifies which variant of the en it is. With sum types you have two options: * You always include a type tag directly in the representation (so a base identifier always has an extra byte or so of information with it). This is typically used in dynamic languages where the types are known at runtime anyway. I believe it's also the case in Java and I suspect other VM-based languages are similar. * You dynamically generate the enums at compile time (so a base identifier doesn't have a tag, but if it's used in a `Identifier | Number` union, then a tag for that specific union gets added in). The problem with the first is that it adds unnecessary runtime cost, because now every instance of any type has extra information in it that probably isn't needed. The problem with the second is that the creation and unwrapping of enum values becomes implicit, and you'll probably need to juggle your discriminants around more. Say I gave a function of type Identifier | Number -> Boolean | Identifier | Number, then should the discriminants for the Identifier and Number cases stay the same? Or do we need to add extra code to munge the input discriminants into output discriminants? In the first case, this adds a lot of complexity to the compiler (and may not in the general case be possible), in the second case we have runtime performance issues. This is, I think, the point that the previous poster was getting at. If you have implicit discriminators, this will have an implicit runtime cost that may not always be easy (or possible) to avoid. That is the value of explicitly wrapping types in enums - the runtime cost can be minimised, and the developer is always aware of where that runtime cost appears.
amluto 3y ago
I’ve used C++ variants (from a couple of different libraries) a fair amount, and they are sort of union types, and I generally dislike it. The problem is that logically identifying the contents based on type is confusing and refactors poorly. Suppose I have an Identifier or a Number or a StringLiteral. To work intelligently, this needs Identifier and StringLiteral to be disjoint. This isn’t just a type theory issue —- it’s a semantic issue. What is “foo”? Is it an Identifier or a StringLiteral? What happens when I add a Filename (for including/embedding files in the future)? Logically, the fact that an Identifier is encoded by a particular type is a bit of an implementation detail, and a good type system will catch errors. It’s the fact that it’s an identifier — that is, it’s purpose — that matters for semantics and for understanding the code, and union types (and C++ variants, for the most part) are very bad at exposing this.
- yakubin 3y ago
  My issues with std::variant in C++ boil down to it being a runtime, not compile-time construct, and surprising interactions with implicit casts, especially in the case of primitive types. After that, unlike what I described about combining union types with lexically-scoped-newtypes, std::variant doesn't let you build sum types when you need them. You're stuck only with union types. > What is “foo”? Is it an Identifier or a StringLiteral? Normally, it's an identifier, since there are no quotes. If there is ambiguity about it, the lexical categories you're working with are ambiguous, which is a real issue. When designing a grammar, that should be avoided. Sadly, sometimes we're given a poor-quality grammar like in C, where some tokens can be interpreted both as headers and as string literals (but neither is a subset of the other) and can't do anything about it, but then you just need to decide which category you're going to assign to ambiguous cases (either one of two, or make a third one) and later you can disambiguate based on context. In any case, I don't consider it an issue of the tool, but an essential domain problem to be solved explicitly by the programmer.
  - amluto 3y ago
    >> What is “foo”? Is it an Identifier or a StringLiteral? > Normally, it's an identifier, since there are no quotes. Sorry, I was vague. I don't mean the sequence f o o in the input or the sequence " f o o ". I mean the string (String, str, whatever your language calls it) containing the three letters f o o, which is stored in a union type. Sure, one can lexically-scoped-newtype it if the language supports it, but at that point, unless I'm missing something, it might as well be a sum type.

MrJohz 3y ago

There is some runtime complexity here though. With both enums and sum types, if you want to differentiate the types at runtime, you need to include a discriminant in order to be able to do that. Enums include that discriminant explicitly (that's what the `Token::Identifier(...)`/`Token::Number(...)` part represents). The memory layout for, say, a base identifier can consist only of the necessary fields for that identifies, but when it gets wrapped it will get an extra field that identifies which variant of the en it is. With sum types you have two options: * You always include a type tag directly in the representation (so a base identifier always has an extra byte or so of information with it). This is typically used in dynamic languages where the types are known at runtime anyway. I believe it's also the case in Java and I suspect other VM-based languages are similar. * You dynamically generate the enums at compile time (so a base identifier doesn't have a tag, but if it's used in a `Identifier | Number` union, then a tag for that specific union gets added in). The problem with the first is that it adds unnecessary runtime cost, because now every instance of any type has extra information in it that probably isn't needed. The problem with the second is that the creation and unwrapping of enum values becomes implicit, and you'll probably need to juggle your discriminants around more. Say I gave a function of type Identifier | Number -> Boolean | Identifier | Number, then should the discriminants for the Identifier and Number cases stay the same? Or do we need to add extra code to munge the input discriminants into output discriminants? In the first case, this adds a lot of complexity to the compiler (and may not in the general case be possible), in the second case we have runtime performance issues. This is, I think, the point that the previous poster was getting at. If you have implicit discriminators, this will have an implicit runtime cost that may not always be easy (or possible) to avoid. That is the value of explicitly wrapping types in enums - the runtime cost can be minimised, and the developer is always aware of where that runtime cost appears.

amluto 3y ago

I’ve used C++ variants (from a couple of different libraries) a fair amount, and they are sort of union types, and I generally dislike it. The problem is that logically identifying the contents based on type is confusing and refactors poorly. Suppose I have an Identifier or a Number or a StringLiteral. To work intelligently, this needs Identifier and StringLiteral to be disjoint. This isn’t just a type theory issue —- it’s a semantic issue. What is “foo”? Is it an Identifier or a StringLiteral? What happens when I add a Filename (for including/embedding files in the future)? Logically, the fact that an Identifier is encoded by a particular type is a bit of an implementation detail, and a good type system will catch errors. It’s the fact that it’s an identifier — that is, it’s purpose — that matters for semantics and for understanding the code, and union types (and C++ variants, for the most part) are very bad at exposing this.

yakubin 3y ago
My issues with std::variant in C++ boil down to it being a runtime, not compile-time construct, and surprising interactions with implicit casts, especially in the case of primitive types. After that, unlike what I described about combining union types with lexically-scoped-newtypes, std::variant doesn't let you build sum types when you need them. You're stuck only with union types. > What is “foo”? Is it an Identifier or a StringLiteral? Normally, it's an identifier, since there are no quotes. If there is ambiguity about it, the lexical categories you're working with are ambiguous, which is a real issue. When designing a grammar, that should be avoided. Sadly, sometimes we're given a poor-quality grammar like in C, where some tokens can be interpreted both as headers and as string literals (but neither is a subset of the other) and can't do anything about it, but then you just need to decide which category you're going to assign to ambiguous cases (either one of two, or make a third one) and later you can disambiguate based on context. In any case, I don't consider it an issue of the tool, but an essential domain problem to be solved explicitly by the programmer.
- amluto 3y ago
  >> What is “foo”? Is it an Identifier or a StringLiteral? > Normally, it's an identifier, since there are no quotes. Sorry, I was vague. I don't mean the sequence f o o in the input or the sequence " f o o ". I mean the string (String, str, whatever your language calls it) containing the three letters f o o, which is stored in a union type. Sure, one can lexically-scoped-newtype it if the language supports it, but at that point, unless I'm missing something, it might as well be a sum type.