LDM Notes for January 13th, 2025

[333fred]

https://github.com/dotnet/csharplang/blob/main/meetings/2025/LDM-2025-01-13.md

Agenda

• Discriminated Unions

[orthoxerox]

I am really happy that you have decided to go ahead with class unions before finalizing the whole design.

Speaking of struct union challenges, how does F# work around the problem of large structs? As far as I know, it performs no optimizations to reduce the size of the union.

There are ways of compacting the representation, e.g. by overlapping fields, but the more you do, the more time is spent packing and unpacking values. This starts to offset the benefits of avoiding allocation.

If compaction uses unsafe techniques, the runtime might get confused and turn off its own optimizations. Runtime work to address this directly would likely be costly.

I thought the bigger problem was that generic types couldn't have explicit locations. Runtime doesn't get confused, it flat out refuses to load a struct union where you try to pack all kinds into [FieldOffset(1)] if any of them is generic.

[AndersKehlet]

New to F# 9 is that the compiler will reuse fields for cases with the same type (and optional label).

The following union will compile to a single "item" field in addition to the "_tag" field.

[<Struct>]
type Fruits =
    | Apple of int
    | Orange of int
    | Pear of int
    | Kiwi of int

[orthoxerox]

That's interesting, I was playing with sharplab.io earlier this morning and it wouldn't merge any fields, probably because they had different labels.

[AndersKehlet]

Yeah, previously cases with the same type required unique labels, so they've enabled this new behavior without changing the compilation of existing code.

[huoyaoyuan]

I've seen a real desire of struct union with overlapped fields. The code is implementing a "manual" heap to reduce GC. By overlapping fields, it would be able to use an aligned union struct with object fields in it, and allowed to have references to GC heap. The size saving is important in this case because there are more than 10 cases on the "heap".

[stepanbenes]

An alternative is to not erase, and instead have implementation types such as ValueUnion<T1, T2> etc. However, this has semantic consequences: Now (string or bool) will not be the same type as (bool or string)! We've investigated runtime approaches to dealing with this, but they are imperfect and very expensive!

The types can by sorted by some type id when constructing ValueUnion type. Or am I missing something?

[Richiban]

That doesn't work with generics, where the actual types might not be known at compile time. E.g.

(T1 or T2) Either<T1, T2>(bool b, T1 left, T2 right) => b ? left : right;

var x = Either<string, int>(someBool, "1", 1);
var y = Either<int, string>(someOtherBool, 1, "1");

x = y; // This would require some runtime tricks in order to work

[DavidArno]

We will proceed with in-depth design work on class unions.

This is almost too amazing for words. Unions finally looking like they are coming to the C# language. Bloody brilliant. 🥳 🍾 🎉

[Richiban]

How much overlap is there between discriminated unions and type unions? In these discussions on GitHub we often talk about them together but as far as I see it they're completely separate features. Would C# get them both? Are unions preferred over DUs (imagined as closed hierarchies with some declaration sugar)?

Completely separate point: how will type unions work with casts, especially regarding generics? Assuming that this is not legal:

var x = (Cat or Dog)y;

where does the error occur in this?:

T Cast<T>(object val) => (T)val;

var x = Cast<Cat or Dog>(y);

[Richiban]

That section in the proposal didn't really answer my query; perhaps I'm wrong but I thought it would lead to an ambiguity in the case of explicit cast operators but, now that I think about it, those won't run in these kind of cases.

[333fred]

How much overlap is there between discriminated unions and type unions?

The latter is an implementation of the former, as mentioned in the summary of the proposal we discussed in LDM 😉.

As to anonymous unions, there are significant issues with implementation, and we will be proceeding with class-based unions for now.

[Richiban]

Thanks @333fred; I need to give the latest LDM notes a good read because I'm using the term type unions to refer to what you're calling anonymous unions. I should update my nomenclature for these discussions.

[333fred]

If there's one consistent theme in these discussions, it's that words do not mean the same thing to different people.

[Richiban]

Back to the casting issue (I know it's about anonymous unions, but still, I'm interested), what happens here?

var c = new C();

var b = (A or B)c;

class C
{
}

class A
{
	public static implicit operator A(C c) => new A();
}

class B
{
	public static implicit operator B(C c) => new B();
}

[HaloFour]

By "class union" I presume this means something akin to F# discriminated union, which is a closed hierarchy of nested types declared kind of like an enum of records, right?

type Shape =
    | Rectangle of width : float * length : float
    | Circle of radius : float
    | Prism of width : float * float * height : float

🍝

public union Shape {
    record Rectangle(float width, float length);
    record Circle(float radius);
    record Prism((float, float) width, float height);
}

While I'm sure it's the easiest form to solve for I am also curious as to the use cases. It's a departure from how domain types are defined today, and presumably could not be adapted to existing models. I also don't believe that it would serve the Option<T>/Result<T, TError> cases either due to overhead.

[HaloFour]

Right, I feel like the nesting in those cases is an artifact of lacking support for sealing the hierarchy without resorting to a private constructor. Other languages don't require this nesting so it's not a problem:

// Java 17 ADTs

sealed interface Packet
    // this clause is not required if the cases are declared in the same compilation unit
    permits SomeThing, SomeOtherThing, SomeDataThing { }

class SomeThing implements Packet { }
record SomeOtherThing(String SomeString) implements Packet { }
record SomeDataThing(byte[] Data) implements Packet { }

// Scala 2.x

sealed abstract class Option[A+] { ... }
final case class Some[+A](value: A) extends Option[A] { ... }
case object None extends Option[Nothing] { ... }

[Richiban]

@HaloFour Apart from much preferring the syntax of nested cases (personally it feels like the cases somehow belong to the union type) there's a problem with the non-nested version when you consider that C# doesn't have a bottom type.

In your second example you've used the generic union Option but, if we try to write this in pseudo-new C# without nesting we can't:

public abstract closed class Option<T> {}
public sealed class Some<T>(T value): Option<T> { }
public sealed class None: Option<???> {} // What do we write here?

Assuming C# doesn't get a bottom type like Scala's Nothing our only options with generic unions (at least those where not all cases use all the type parameters of the union) is either to:

1. nest the cases in the parent type, so that the cases can access the type parameters of the parent, or
2. have all cases take in all type parameters, which might suck pretty hard in some cases.

@jnm2 's recent proposal for omitting type names on static member access makes option (1) above by far the more attractive of the two.

[HaloFour]

@Richiban

I think the lack of a bottom type will be problematic either way, as Option<Foo>.None won't be assignable to Option<Bar>.None. With Scala's JVM trickery None is a singleton instance that can be assigned to both.

Although, honestly, I would argue that Option<T> wouldn't be good to map as a type hierarchy anyway, and that None should be a tag matched through some other means, like it is in F# with struct unions.

Either way, my comments about the type nesting come more from a place that DUs implemented as type hierarchies are as old as C# itself, and they're rarely modeled in this fashion.

[orthoxerox]

@Richiban implicit conversions get you most of the sugar you might need without a bottom type (although I would love to have a bottom type).

[Richiban]

@HaloFour You've reminded me now that I talked years ago on this repo about the fact that DUs were going to be somewhat hobbled by the lack of covariance support outside of interfaces.

When covariance was first introduced into C# (over 20 years ago) apparently they never put it into classes because "It would mean the class would have to be essentially immutable, and who would do that!?"; I'd love to see it get added now (or the version after class-based DUs). I maintain that people are going to start complaining when they find out that Cons<string> is not assignable to Cons<object>.