Discriminated Unions Proposal

[YairHalberstadt]

@agocke added a proposal for discriminated Unions a few hours ago. I wanted to make a few comments, but you can't comment on a proposal so I thought I'd make this issue to discuss.

The proposal is at https://github.com/dotnet/csharplang/blob/master/proposals/discriminated-unions.md

[YairHalberstadt]

ValueType DUs

Are you considering ValueType DUs to help reduce allocations.

I think rust's design involving a union and a tag should work in c#, as it is possible to specify that fields in a struct should occupy the same location.

Top Level Members

If the enum is represented as an abstract class, should it be possible to add top level members to the enum?

I think Niko Matsakis suggestions for DU improvements in Rust which I know @agocke has seen, do a good job of explaining the benefits of allowing this. I'll try to link them soon.

[ziaulhasanhamim]

But I think struct DUs are critical for DUs like Maybe to keep overhead low.

@HaloFour I'm with that. Because at the end of the day it should be like an enum that can hold extra information about the case.

I think you are not understanding my position

@CyrusNajmabadi Yeah I'm getting your point. You are trying to say to be consistent with records. But unions make more sense to be a value type. And let's be honest with the records too when is the last time we used a large-size record? I think we don't use them often.

public readonly record struct Person(
  string FirstName,
  string LastName,
  string Surname,
  string Occupation,
  string FathersName,
  string MothersName
)

This isn't large at all because those strings are just pointers. This is true about most things you will store in a record(except primitives which are also very small in size). But I can understand the logic behind the records being reference types by default. But why would unions be a reference type just to be consistent with records? Can you give an example where you really really want to use a reference type union over a value type union?

[CyrusNajmabadi]

Can you give an example where you really really want to use a reference type union over a value type union?

I think i'd likely use a reference type union almost all the time. I think of value types as something i used when profiling reveals some sort of hot-spot that needs attention, or there will be just a hojillion of them flying around. For something like DUs i could see them commonly being used for things like long arg or return type chains. Having all those copies threading deep in/out of the system just seems superfluous.

I honestly don't get what the big deal is here. If you want to use a struct DU, i'm virtually certain we'd allow that with little muss/fuss. Like with records, it would likely be a single token addition.

Or, if it makes you feel better, we can consider making it equally verbose to declare either. e.g. enum class or enum struct.

[ziaulhasanhamim]

I think i'd likely use a reference type union almost all the time

But why? What benefits will you get?

if it makes you feel better. we can consider making it equally verbose to declare either. e.g. enum class or enum struct

What's the meaning of this? We are talking about making it easier and better to use than feeling better

[CyrusNajmabadi]

But why? What benefits will you get?

I mentioned there benefits already.

What's the meaning of this? We are talking about making it easier and better to use than feeling better

I genuinely do not understand why it would be such a big deal to have a single extra token here (if they are different). Or it will be the same number of tokens if we require both to be explicit.

That seems totally fine to me, and in line with them language up to now.

I really don't get why this is an issue. You'll write the decl once and add whichever keyword is sensible for your domain. Then your reference it wherever you want and it an works out.

We're literally talking about one potential token out of thousands of lines of the year of the code for declaring and using the DU. Why is this such a big deal?

[jnm2]

This isn't large at all because those strings are just pointers.

@ziaulhasanhamim That's six 64-bit pointers, so 48 bytes are being copied implicitly every time the struct value moves from place to place. I believe anything over 16 bytes is considered large.

[YairHalberstadt]

I linked the blog posts in an earlier comment here

[333fred]

If the enum is represented as an abstract class, should it be possible to add top level members to the enum?

Yes, we discussed this explicitly during LDM. The intent is that you can declare a regular partial part of enum Type and put anything you want in there. We also talked about ending the enum section with a semicolon (ie Java-style) and letting you put standard class stuff after that as well. We still need to design if/how base constructors would work in these scenarios, but it's very much on the table.

[Trayani]

I'm up for value-type unions and more importantly, for arbitrary type.
I mean, we can already do most of what is being proposed with interfaces and/or abstract classes.

What we cannot do is to make generic struct types for patterns like: result-or-exception, T-or-T[], possibly even Value-or-Object-with-Value.
We can tinker with [StructLayout(LayoutKind.Explicit)] , but it is limited to non-generic value types-only or classes-only. Could we get more support for this attribute?

[Richiban]

Really excited about this; Discriminated Unions are the one feature of any language that I sorely miss with C# and cannot really replicate using other means. Like your designs 👍

I'm puzzled as to why these will differ from other types though in being partial by default. Is there any reason, perhaps one that's not listed in the proposal doc, as to why it would be undesirable or onerous to require the partial keyword?

[Joe4evr]

I'm puzzled as to why these will differ from other types though in being partial by default. Is there any reason, perhaps one that's not listed in the proposal doc, as to why it would be undesirable or onerous to require the partial keyword?

The use of partial in proposals is just a thing done to keep sample code concise, though it makes a lot more sense when you're proposing to add new API to an existing type. I very much doubt it's actually required in the declaration (especially considering that partial is purely a design-time feature, there's no such thing in IL) and the grammar even lists it as 'partial'? with the question mark indicating it's an optional term.

[agocke]

Just added the notes from our discussion of this proposal on Wednesday: #2968

re: struct discriminated unions, I think we should do them and there's a natural parallel here, but it's just out of scope for me right now. I'm trying not to design too many things at the same time

[Richiban]

@agocke Any thoughts yet on generic discriminated unions?

Since C# doesn't have a bottom type (aka Nothing or Never) it's not going to be possible to have a generic DU with non-generic cases (or cases with a different arity from the base).

The easy example of this would be either Option<T> or a singly linked list.

[AartBluestoke]

Open questions on the LDM: "Is switching against an argument with an enum class static type guaranteed to be constant-time?"

I don't believe anywhere else the language spec talks about implementation constraints of O(N) vs O(log(N)). For small N, a Logn scaling implementation (or even hotpath optimisation based on frequency of occurrence from profiling) is often quicker than the overhead of guaranteeing a constant time implementation.

eg: https://github.com/dotnet/csharplang/blob/5dd11df6976beb761c68091cda13475f88ecd9a7/proposals/csharp-8.0/patterns.md
has a small section titled "some possible optimisations" as the only limitations on implementation within the runtime (other than re-ordering)

eg: how compilers implement non-enum switch statements with small (or large) numbers of branches. often "guaranteed constant time" involves some type of hash, jump and collision resolution, which would be more effort than log_2(n) nested if's.

[agocke]

@Richiban

I expect you would define Option as essentially

enum class Option<T>
{
    Some(T t),
    None
}

It's true that you don't have a single None instance for all Option types, but I don't think it's that much of a problem. The only drawback I can see is that when mapping from an Option<T> to an Option<U> you have to explicitly map between Nones, which doesn't seem that bad.

[Richiban]

@agocke I thought as much.

Will there be any special type inference support, perhaps with #2926 (Name lookup for simple name when target type known)?

Basically, what I'd really like to avoid is having to write Option<string>.None everywhere, especially if it can be target-typed.

In C# var x = None is never going to work where a target type is not available, because you need either a bottom type (as previously mentioned, a la Kotlin, Scala etc) or to allow for generic values (a la Haskell and F#) which means that the generic parameter does not need to be inferred immediately, but can be left for later.

[agocke]

Right, var x = None won't work, but Option<string> x = None should work with #2926. It's not quite as short, but in C# we have a principle that we won't infer a type you can't say, and you can't give a variable an open type (Option<> x) in C#. Slightly more verbose but not crazy. In addition, if your return type is Option<string> you could just return None directly.

[orthoxerox]

@Richiban we might get a bottom type in some later version of C#, #538 has been championed.

@agocke any chance #538 could be re-triaged to the same milestone as DUs?

[agocke]

I don't see how a bottom type would help you in this scenario, since classes are invariant.

[Richiban]

As I said before, I'm very much looking forward to getting these DUs! There's a lot of work to be done in the future to make them fully featured, however. For example, this is how you properly model an Option in Kotlin.

public sealed class Option<out T>
    
public object None : Option<Nothing>()
public data class Some<T>(val value: T) : Option<T>()

Unfortunately it makes use of quite a number of features that C# doesn't have:

1. Covariance in classes. Necessary for an Option<Banana> to be assignable to Option<Fruit> etc.
2. Free objects. See: None. An object declaration is both a type and a value, i.e. a singleton. Can participate in inheritance hierarchies, as in this case.
3. Sealed classes. Necessary for the compiler to be able to prove completeness.
4. Bottom type (Nothing). Allows the singleton None, in conjunction with (1), to be assignable to Option<T> for any T.

In addition, it uses a record (marked by the data keyword) that gives the Some class a public property, structural equality etc.

[agocke]

Covariance in classes. Necessary for an Option to be assignable to Option etc.

I don't think this is necessary for all use cases. I doubt this will be in V1 regardless, since variance is a part of the CLR type system and this would require also changing the CLR.

[gafter]

Open questions on the LDM: "Is switching against an argument with an enum class static type guaranteed to be constant-time?"

FYI, our current expectation is yes. More precisely, we expect amortized constant time performance based on runtime support that we are planning in .Net core 5. Having said that, we cannot prevent someone else from supplying a "bad" runtime implementation that violates these expectations.

[orthoxerox]

Linking to #3760 for future reference

[Richiban]

I know there might be a number of DU proposals currently open... does anyone know if any of them is championed?

[HaloFour]

There's #113, which has been open for a while but from Discord it sounds like members of the team are interested in picking this up soon.