LDM Notes for March 27th, 2024

[333fred]

https://github.com/dotnet/csharplang/blob/main/meetings/2024/LDM-2024-03-27.md
https://github.com/dotnet/csharplang/blob/main/meetings/2024/LDM-2024-03-27-presentation.pdf

Agenda

• Discriminated Unions

[hamarb123]

Just some ideas about how we could have both interchangeability and good performance/allocations:

Re interchangability and performance,
Ideally, we could generate something like:

[StructLayout(LayoutKind.Union)]
struct Union1Impl<T1, T2, T3, T4>
{
    byte tag; //first field indicates selected option, 0 = T1, 1 = T2, etc. - byte/ushort/uint/ulong are all allowed
    T1 field1; //following fields declare the different union field types
    T2 field2;
    T3 field3;
    T4 field4;
}

where LayoutKind.Union tells the runtime that the first field (tag in above) is the tag field, and the following fields are overlapped when possible automatically at runtime (based on where managed sections are).

We could then also have a runtime-interpreted attribute InterchangeableUnionAttribute, which could be used like so:

[StructLayout(LayoutKind.Union)]
[InterchangeableUnion]
struct Union2Impl<T1, T2, T3, T4>
{
    byte tag;
    T1 field1;
    T2 field2;
    T3 field3;
    T4 field4;
    static readonly byte field1_TagValue; //runtime provided, value in tag to represent T1
    static readonly byte field2_TagValue; //runtime provided, value in tag to represent T2
    static readonly byte field3_TagValue; //runtime provided, value in tag to represent T3
    static readonly byte field4_TagValue; //runtime provided, value in tag to represent T4
}

which would tell the runtime to make UnionImpl<T1, T2, T3, T4> equivalent to UnionImpl<T2, T3, T4, T1>, etc. for all the ordering (by equivalent, I mean the runtime will pick some particular one and replace all uses with it, so that they are actually exactly the same).
This strategy should work well for structs passed by generic (since they are always specialised), but could pose a problem with reference types via generics, since the generic lookup could make the TagValue not as cheap to read (like reading static field on generic type with reference type generic type parameter today), but this is already the case for many uses of generics + references types today, and should be completely elidable in cases where the type parameters are known at inline-time. (specifically, the problem is caused by __Canon and shared generics).

For these interchangeable ones, it could also be decided that, for example, if T1 == T2 (or any other equivalence of field types), then the runtime would merge these cases; if this is done, it would essentially designate Union1Impl as a tagged union, and Union2Impl as an anonymous union.

Furthermore, since this approach would clearly require runtime support, for a tagged union like Option<T>, we could emit its generated type like so:

[StructLayout(LayoutKind.Union)]
struct OptionImpl<T>
{
    byte tag;
    void field1; //None field
    T field2; //Some field
}

where the "void field" (or some other marker type if that's not possible at all) tells the runtime that it doesn't ever need to make space for the field1 case. For cases where multiple values exist per option, we could use ValueTuple (or we could invent something else if we want slightly better packing in a handful of cases). These void/valuetuple fields would only be applicable to tagged unions, whereas the [InterchangeableUnion] would only be used to indicate anonymous unions.

C# could expose these in a nice way, like so:

enum Union1<T1, T2, T3, T4>(T1 A, T2 B, T3 C, T4 D);
interchangeable enum Union2<T1, T2, T3, T4>(T1 A, T2 B, T3 C, T4 D);

where all of the Impl types are private, compiler-generated, nested types, and nice accessors are exposed instead on the actual types.

The above is obviously quite a rough sketch of how it could work, but I believe a runtime + language supported solution would provide the best performance and the best usability.

[TahirAhmadov]

If we can ask runtime to support this, then we could just go:

[Union(20)]
struct Union1Impl<T1, T2, T3, T4>
{
    byte tag; //first field indicates selected option, 0 = T1, 1 = T2, etc. - byte/ushort/uint/ulong are all allowed
    // runtime magically allocates 20 bytes
}

20 bytes (a sample number) is the number of bytes required to represent any potential option. All the GC shenanigans are handled by special logic in the runtime which interprets "areas" of the 20-byte "array" as needed.

I'm being a little facetious, obviously this is an extremely huge ask for the runtime. My point is that, it requires very careful thought about what needs to be added to the runtime, to make sure it makes sense for the overall ecosystem, satisfies all the criteria like stability/performance/etc., and doesn't represent a single huge item which ties them up for a long period of time.

[hamarb123]

If we can ask runtime to support this, then we could just go:

[Union(20)]
struct Union1Impl<T1, T2, T3, T4>
{
    byte tag; //first field indicates selected option, 0 = T1, 1 = T2, etc. - byte/ushort/uint/ulong are all allowed
    // runtime magically allocates 20 bytes
}

20 bytes (a sample number) is the number of bytes required to represent any potential option. All the GC shenanigans are handled by special logic in the runtime which interprets "areas" of the 20-byte "array" as needed.

I know you're trying to prove a point, but this strategy wouldn't work at all for a few reasons:

1. The C# compiler has no idea how many bytes would be needed in the general case, even without generics, it only knows the size for a few specific cases (built-in fixed-sized integral & float types + enums probably), and then you have pointers, which are variable size - there are multiple reasons for this, including: ref assemblies, layout changes, pointers being 4/8 bytes depending on 32/64-bit
2. It wouldn't really be possible to have GC refs with the above, because the writes to tag & where the gc refs are will be torn, therefore it's not really possible to have bytes that are both gc/non-gc regions in any practical way currently (whereas, if you just put managed structs in the own memory, then we could just treat it as alive always, ignoring the tag field, or if the runtime thinks it could do something better in the future, then it could be designed to allow it)

My approach completely side-steps both of these issues, by allowing the runtime to do the laying-out itself.

I'm being a little facetious, obviously this is an extremely huge ask for the runtime. My point is that, it requires very careful thought about what needs to be added to the runtime, to make sure it makes sense for the overall ecosystem, satisfies all the criteria like stability/performance/etc., and doesn't represent a single huge item which ties them up for a long period of time.

My suggestion, other than the [InterchangeableUnion], and ignoring the void marker field, is really not that special. All of the things to do it theoretically exist already today, just cannot be used in a generic context, or in the C# compiler. There is nothing that stops you generating these types at runtime with the perfect layout via Reflection Emit, since you can just use explicit layout + field offsets. My suggestion is that the runtime could do it for you, since it's impossible to do generically, or in the C# compiler in 99% of cases (for same reasons mentioned in 1. earlier) - this would also allow the runtime to optimise the layout to whatever it thinks is best.

[hamarb123]

Also, we can actually already do the following btw:

[Union(20)]
struct Union1Impl<T1, T2, T3, T4>
{
    byte tag; //first field indicates selected option, 0 = T1, 1 = T2, etc. - byte/ushort/uint/ulong are all allowed
    // runtime magically allocates 20 bytes
}

->

[StructLayout(LayoutKind.Sequential, Size = 21)]
public struct S1
{
    byte tag;
    //there will be 20 bytes extra here, if you want it to be aligned, you can easily adjust the size & skip some padding
}

Just in case you weren't aware. It doesn't tell runtime about GC spots obviously, though, but I explained why this likely wouldn't work even if it could in my previous message (due to tearing).
This alone is not enough to support most sorts of useful discriminated unions.

[huoyaoyuan]

public sealed enum Planets { Earth, Jupiter, Mars, Mercury, Neptune, Pluto, Saturn, Uranus, Venus }

Pluto is classified as dwarf planet since 2006. The corresponding enum value should be obsoleted in real world.

[orthoxerox]

I think that's the joke.

[MgSam]

#justiceforpluto

[orthoxerox]

One clear result from these reads was that we need to support existing "closed" type hierarchies in some fashion, even if it's just in exhaustiveness in pattern matching.

That's a result I am glad to hear about. They are the most common form of "unions of related types" along with enums ("unions of related values"), implementing exhaustiveness checks constrains the remaining design space for DUs practically to "monadic stuff people like from FP" and "easy unions of unrelated types", both of which come with their own baggage listed in the presentation (monadic sugar and interchangeability respectively), with "performant unions of unrelated types" a distant third.

[MgSam]

As I saw you guys mentioned @gafter's enum proposals in the notes- I thought I'd point out that the patents on enums that may have impacted the design space here in C# have now expired:

https://patents.google.com/patent/US7263687B2/en
https://patents.google.com/patent/EP1400895A2/un

[HaloFour]

Those patents were pretty narrow, though, and would have only really applied to enums as singleton class instances, like they are implemented in Java. Those are interesting but pretty limited, e.g. they cannot be data carriers. I think DUs are a much more interesting space that covers those use cases and more.

[mattwar]

We had not even considered patents. As a general practice we are discouraged even looking for existing patents, let alone reading them. We leave that for the lawyers, and that is typically only if we are attempting to patent something ourselves. These proposals never got to that point.

[HaloFour]

Probably less of a defense when a (previous) C# language designer is listed as an inventor on the patent. 😁

[MgSam]

I mentioned because @gafter had previously cited these patents as an impediment to C# having feature parity with Java in enum design. Though obviously the current proposals are of a different form.

[mattwar]

Apologies for all the typos and incorrect autocorrects in the slide notes. The slides did not originally have the notes, and I scrambled to add them later.

[mattwar]

The github repro used for experimenting with different implementations is here:
https://github.com/mattwar/Dumbo

[qrli]

I don't quite understand why Performant and Expressive are incompatible.

• If ValueTuple<> is used to represent the Tag types, then I think the Anonymous can be solved.
  • For type union scenario, 1-tuple would work.
• And, the ValueTuple<> assignment rules can be reused, which solves the Tag type assignability across different DU types.
• Regarding assignment at the DU level, I think DU<A|B|C> du1 = (DU<A|C>)du2 is equivalent to if (du2 is A a) { du1 = a } else if (du2 is C c) { du1 = c }, while DU<A|B|C> du1 = a and DU<A|B|C> du1 = c should work anyway.
  • I do see the if-else here may defeat the purpose of performance. But the Expressive side gives up performance anyway.
  • Or, as long as type system can tell it is assignable from DU<A|C> to DU<A|B|C>, it is technically possible to do a simple memcpy, which may need special runtime feature.

[qrli]

That's a good point.

Then back to my original question:

• Assuming record structs are used for tags, if explicit record struct types are used, then there should be no assignment compatibility question as different types are different types. The issue then, as I understand, is only when anonymous tags to be supported.

• In the anonymous tag type scenario, I think there are a few possibilities:

  1. Same mechanism as anonymous type (e.g. a generated record struct), which has the limitation of not working across assembly boundary.
  2. ValueTuple<> as I mentioned, which has the limitation of not allowing multiple tags of the same set of variables. But I cannot think of a use case for that multiple same anonymous tags - it would need another discriminator than tag type anyway. Isn't it? And if that discriminator is needed, just write a record struct.

• In the case where a tag has a single variable, no need to wrap with record struct, right? The variable type can be used as discriminator directly, and the assignment compatibility follow normal rules. Which means variable of type union { Foo | Bar } can be assigned to union { Foo | Bar | Baz }, which should be implementable as long as Foo and Bar can be assigned to union { Foo | Bar | Baz }.

[HaloFour]

Is there really value in having anonymous unions like that, particularly anonymous tagged unions?

IMO, the union itself should be a nominal type, and all of its tags should be treated as if they are also nominal types. The fact that one union has a Some and another union has a Some doesn't mean that they are semantically interchangeable. I also don't see a lot of point in trying to "hack" discriminated unions on top of type unions. They are extremely different beasts and tagged unions don't need to inherit all of that complicated-ness from type unions.

[qrli]

I'm not sure about usefulness of anonymous union either. The slides does not expand on the "Expressive" side but just a few keywords (anonymous, assignment compatibility, etc.). No detail about when and why these features will be desirable. Personally, I'd agree that assignment compatibility is desirable, especially when the tags are single-variable.

[orthoxerox]

Is there really value in having anonymous unions like that, particularly anonymous tagged unions?

@HaloFour Anonymous tagged unions sound not very useful. Anonymous type unions aren't something that I use at all, but it seems there's a large amount of people I have never intersected with (except David) that want them.

[DavidArno]

@orthoxerox, to be honest, I do reserve the right to flip my view on this.

Having used type unions in Python, I see definite use cases for them in C#, too. A union of records would fit most of my union use cases.

But tagged unions could be useful as well and potentially could be more useful, eg no need to define those records in advance. My big concern with them is what the UX will be like when it comes to pattern matching. If I have to go through extra ceremony to pattern match tag unions, then I'll not like them.

So I'll wait and see how it all pans out 😁