One simple but non obivious (at least to me) trick when implementing tagged unions: put the union discriminator/tag at the end, not the beginning - that way a pointer to a union is also a pointer to the value, no need to increment the pointer to point past the tag after discriminating.
It's a perf issue for the stuff I write, it's just faster to deserialize without having to go back in the file. This comes up with tagged types like variant/expected/...
It's a bit like putting the length of an array at the end rather than the beginning though - you need to know its size first to know the offset.
The value of a tagged union may be like a flexible array member - in that the size of the value depends on the tag. We shouldn't need to allocate the maximum possible variant's space when most of the instances may be the smallest. Unlike a C `union`, which are a fixed size, a tagged union has no such requirement - it can be dynamically sized depending on tag.
Usually when dealing with something like 'Union(BigThing, SmallThing)' you have to allocate sizeof(BigThing + tag) in most places anyway because you need to statically know the size so that it can be a struct/array member, live on the stack etc.
The only time you can get away with only allocating the 'real' size is if you're sticking it in its own separte memory allocation and using a pointer to refer to it in the aforementioned contexts. Which, to be fair, is a sensible thing to do if BigThing is very big, as opposed to just 'on the bigger end of sane struct sizes'.
To clarify I'm talking about what you'd do in a language implementation where the actual memory layout is opaque to userspace and bit twiddling optimizations aren't making things harder to understand for everything, not what you'd do when writing handwritten C code or an api where you expect people to access the memory directly. This isn't unheard of - e.g. from my research Swift does it, some C++ stdlib implementations do it.
A frequent implementation method for unions does not need to change the pointer, because the tag is accessed with a negative offset and the pointer always points to the value.
In some languages (eg, on dotnet), tagged unions are implemented through an OOP hierarchy, where you have, for example, something like:
public sealed abstract class Option<T> {
private Option() { }
public sealed class Some<T> : Option<T> {
private readonly T value;
public Some(T value) {
this.value = value;
}
}
public sealed class None<T> : Option<T> {
public None() { }
}
public static Option<T> Some(T value) { return new Some(T); }
static readonly Option<T> _None = new None();
public static Option<T> None() { return _None; }
}
Where you can use `Option.Some` or `Option.None`, and the return type is inferred from the parameter.
The sizeof(None) is not the same as sizeof(Some<T>) - the Some class has an additional field not present in the None class - and the size of Some depends on the type parameter T.
If the objects have RTTI, we don't even need a tag field, as their is an implicit tag in the form of type information in the object - the pattern matching facility can test `opt is Some<T>` or `opt is None`
What is the best source for cross-language description of language features? Eg: “optional types”: which langs have them and how do they work? Same with “union types” etc.
There's no single oracle for these things, unfortunately. One common citation is "Types and Programming Languages" by Benjamin Pierce (2002), but otherwise people generally just use the nomenclature of a specific language and hope cross-linguistic adventurers will figure it out. I think there's somewhat less variance with more modern languages, though, so in some ways it's less of an issue than it once was.
It seems bizarre to me that Copper includes Union types and then, for implementation reasons, does not include so many of its basic features, and even its basic properties.
Like, what do you mean you can’t have three union members? And that the order of the union matters? These are some of the most useful properties of union types, and the arguments for what Copper did are weak sauce.
Agreed. They don't seem to understand the difference between sum types and union types. If you're worried about tags you shouldn't be considering union types in the first place, for example.
It looks like you can have three union members, just not nesting (weak) or compatibility between T1|T2 and T1|T2|T3 (probably fine). I'm not convinced about ordering being a problem.
Ordering is a problem because there's no good way to handle duplicate members. If you have a generic function `f(T) -> T|A` what is the compiler supposed to do when T = A|B? Return A|B|A breaking the main rule of unions or give up and throw a compile error?
And set unions are supposed to be unordered anyway. You're going against what everyone expects from other languages and basic math.
> The option type, despite being simpler than union type introduces many new concepts and requires additional knowledge that make the language more complex.
That's why I do such things in my language in a different way. Optional and union types are just library container classes. More methods may be added if necessary, internal layout may be changed, etc. without changing the language core itself. But in such an approach the language itself should provide necessary means allowing creation of such library abstractions.
28 comments
[ 2.9 ms ] story [ 29.0 ms ] threadhttps://www.youtube.com/shorts/XK_D7Z-cKZ4
Unless, you do de-serialization and serialization in tight-loop I guess is it acceptable.
NOTE: A bigger problem is when you need to decide at runtime which one of the kind you have been handled.
It's a bit like putting the length of an array at the end rather than the beginning though - you need to know its size first to know the offset.
The value of a tagged union may be like a flexible array member - in that the size of the value depends on the tag. We shouldn't need to allocate the maximum possible variant's space when most of the instances may be the smallest. Unlike a C `union`, which are a fixed size, a tagged union has no such requirement - it can be dynamically sized depending on tag.
The only time you can get away with only allocating the 'real' size is if you're sticking it in its own separte memory allocation and using a pointer to refer to it in the aforementioned contexts. Which, to be fair, is a sensible thing to do if BigThing is very big, as opposed to just 'on the bigger end of sane struct sizes'.
To clarify I'm talking about what you'd do in a language implementation where the actual memory layout is opaque to userspace and bit twiddling optimizations aren't making things harder to understand for everything, not what you'd do when writing handwritten C code or an api where you expect people to access the memory directly. This isn't unheard of - e.g. from my research Swift does it, some C++ stdlib implementations do it.
The sizeof(None) is not the same as sizeof(Some<T>) - the Some class has an additional field not present in the None class - and the size of Some depends on the type parameter T.
If the objects have RTTI, we don't even need a tag field, as their is an implicit tag in the form of type information in the object - the pattern matching facility can test `opt is Some<T>` or `opt is None`
Like, what do you mean you can’t have three union members? And that the order of the union matters? These are some of the most useful properties of union types, and the arguments for what Copper did are weak sauce.
And set unions are supposed to be unordered anyway. You're going against what everyone expects from other languages and basic math.
That's why I do such things in my language in a different way. Optional and union types are just library container classes. More methods may be added if necessary, internal layout may be changed, etc. without changing the language core itself. But in such an approach the language itself should provide necessary means allowing creation of such library abstractions.