Proposal: never/bottom type

[orthoxerox]

Previously discussed in dotnet/roslyn#1226.

A new type that has no instances and is a subtype of every other type can be introduced, called never or bottom. It will be the official return type of the throw expression and will allow transforming return, break, continue and goto into expressions (see #176). This will allow them in all expression contexts where never is combined with another type (&&, ||, ??, ?:) or discarded (expression statements). Instantiating variables/fields of type never should be impossible.

It can either be implemented as a real CLR type (well, as real as void) or as a compiler trick (never-returning methods are actually void with a NeverReturnsAttribute).

[MI3Guy]

It would be really nice to be able to use never with variance. Then we could use IReadOnlyList as any type (or just class types?). This would, of course require CLR support.

[HaloFour]

@MI3Guy

I don't understand how "never" could work in generic containers? Would IReadOnlyList<never> indicate an empty list or something?

[MI3Guy]

@HaloFour

That's the idea. It would represent an empty list. It would only be possible to use never in covariant/out positions, of course.
I tend to use it in Scala with ADTs/sum types for cases that represent errors. Perhaps not the most necessary feature as you could introduce a type parameter, but it more directly expresses intent and can avoid allocating duplicate objects as a single instance can be shared.

[HaloFour]

@MI3Guy

Java manages the same without a "never" type. That only really works in the JVM due to generic type erasure and the lack of generics over primitives. With the CLR IReadOnlyList<string> and IReadOnlyList<int> are fundamentally different and the latter is not permitted to participate in variance as a result. Between reference types they are more equivalent but I believe that's considered a JIT implementation detail and not one that can necessarily be relied upon.

[orthoxerox]

@MI3Guy could you please give an example? @gafter has mentioned variance in the original issue as well, but I find it hard to wrap my mind around the idea.

[MI3Guy]

@orthoxerox
For instance:

public interface IResult<out T> { }
public sealed class ResultValue<T> : IResult<T> {
    // ...
    public T Value { get; }
}
public sealed class ResultError : IResult<never> {
    public string ErrorMessage { get; }
}

You could also add TError and make ResultValue specify never as that type.

[HaloFour]

Well, you also have that pesky issue of classes not allowed to be variant, only delegates and interfaces.

[MI3Guy]

True. I'll make it an interface.

[DavidArno]

Is there a reason why never would be needed here, rather than just using void (and thus, potentially allowing any statement to be treated as a void-returning expression, not just throw, break etc,)?

[DavidArno]

@MI3Guy,

I'm clearly missing something over your use of never in generics as the following can be done already:

public sealed class ResultError : IResult<object>
{
    public string ErrorMessage { get; }
}

but - presumably - that isn't what you are trying to achieve in your example.

[MI3Guy]

In that case, ResultError can only ever be used as an IResult<object>. It couldn't be used as a IResult<string> (or whatever class you wanted to use). You could, of course, declare ResultError with a type parameter.

public sealed class ResultError<T> : IResult<T> { ... }

But as I stated before, the use of never states more directly that ResultError does not actually contain a T and also having to specify the type parameter may result in more instances being created.

[DavidArno]

In your example, you have made IResult<> covariant. Make it contravariant and then IResult<object> can be used in place of IResult<string>:

public interface IResult<in T> { }
public sealed class ResultValue<T> : IResult<T>
{
    // ...
    public T Value { get; }
}
public sealed class ResultError : IResult<object>
{
    public string ErrorMessage { get; }
}

_ = new List<IResult<string>> {new ResultError()};

But again, I guess I'm just missing the point.

[MI3Guy]

Switching to contravariant makes ResultValue invalid. The Value property uses T in a covariant position. The never type is essentially the opposite of the object type.

[DavidArno]

The never type is essentially the opposite of the object type.

Oh! "A new type that has no instances and is a subtype of every other type". Got there in the end. Yes, I now get how it would work with covariant types. That's really nice: I could really use that! 😀

I'm not sure that bottom is a good name therefore as that implies the lowest base type (and being a biologist first, programmer second, I will always struggle to picture roots being at the top of a tree). So never works better IMO.

[orthoxerox]

Well, bottom is its official name in type theory, but since we call futures tasks I don't mind it being called never.

[gafter]

/cc @cston

[JoergWMittag]

Since @DavidArno stumbled over this, maybe it would be a good idea to make it more explicit:

A bottom type is a type which has

• no values
• is a subtype of every other type (meaning it sits at the "bottom" of the type hierarchy, if we draw it in the usual computer science direction with the root in the sky and the leaves in the ground :-D )

The bottom type represents a computation that doesn't return, e.g. an infinite loop, an error, an exit, etc.

Contrast this with a unit type which has

• exactly one value
• no special subtyping relationship apart from the obvious (subtype of object).

The unit type represents a computation that returns nothing. (In many languages, the unit type is written simply as the 0-tuple type and the unit value is written as an empty tuple, and in fact, it is isomorphic to an empty tuple: an empty tuple conveys no useful information, and it has only one value, or, all empty tuples are the same and indistinguishable.)

	unit	bottom
returns	nothing	doesn't return at all
value	singleton	no values
represents	side-effect	non-termination / abnormal termination

Here's a question: what is the type of an empty list?

In Haskell, an empty list has the polymorphic ("generic" in C♯) type [a] (that's IEnumerable<A> in C♯). The empty list ([], pronounced "Nil") is a polymorphic value. But, in C♯, values can't be generic, only static types of references can.

So, second try: IEnumerable<object>, then? Well, at first glance it seems to make sense. But! We surely should be able to assign the empty list to a variable of type IEnumerable<string>, no? After all, an empty list is a list of (no) strings. However, IEnumerable<T> is covariant in T (as it should be, we don't want to, and in fact can't make it covariant), which means IEnumerable<object> is a supertype of IEnumerable<string>. Bummer.

If we want to be able to assign the empty list to a list of strings, we need something that is a subtype of string. If we want to be able to assign the empty list to a list of integers, we need something that is a subtype of integers. And so on … we need something that is a subtype of T for all T: and that's bottom.

In Scala, bottom is called Nothing, which captures this particular usage nicely. What is the type of the empty list, i.e. a list of nothing? Well, in Scala, it's List[Nothing].

---

ChangeLog:

Sorry, @svick, @yaakov-h, @HaloFour for the confusion, I used List more as a generic (hah!) example, I didn't specifically mean the List BCL class. I replaced it with IEnumerable<T> now, which is the real equivalent to a Haskell list anyway (being (potentially) lazy).

[lachbaer]

@JoergWMittag Nice explanation! ,Nothing in VB is null in C#. List<null> would make sense, wouldn't it? Or are there situation where the null keyword as a null/bottom type would conflict?

[svick]

@JoergWMittag System.Collections.Generic.List<T> can't be covariant (even if I ignore the fact that no class can be covariant in .Net), because it's mutable. It's not a good counterpart to Haskell's [a].

Though it could (in theory, again no class can be variant) work with FSharpList<T>, or possibly ImmutableList<T>.

[yaakov-h]

Why can't you have List<nothing> just because it's mutable? If nothing has zero values, you can never add an item to the list, so it will always be empty...

[HaloFour]

@yaakov-h

Variance in the CLR is enforced at the type level, not the method level. A List<T> supports read and write operations so it is inherently invariant. There's no facility to allow variance by forbidding specific method calls, like there is in Java or the like.

[svick]

@yaakov-h You could have List<nothing>, but you couldn't use variant conversions on it, which is what @JoergWMittag was talking about.

Consider:

List<nothing> listOfNothing = new List<nothing>();

List<MemoryStream> listOfStream = listOfNothing;
listOfStream.Add(new MemoryStream());

List<string> listOfString = listOfNothing;
Console.WriteLine(listOfString[0]);

[mattwar]

Can someone explain how having a bottom/never type would benefit the language and its users?

[orthoxerox]

@mattwar

1. It will allow to explicitly mark functions that never return. This will potentially allow CLR to reuse the frame on the call stack if someone writes (or automatically rewrites) their programs in CPS. It will also allow the compiler to find additional unreachable code.

2. It will make break, continue, throw etc expresssions' treatment by the compiler straightforward.

[mattwar]

@orthoxerox Are functions that are known not to return common enough that we'd need special language syntax to call them out? As for your #2, the compiler can model these branch expressions without the need of introducing new language keywords.

[gafter]

@mattwar There are a number of such methods in the BCL, but that is not the principal motivation for this feature. It is more motivated by generics scenarios where there is a top type (object) which is very useful with generics, thank you very much, but there is no corresponding bottom type (this proposal). Also it would be particularly useful to expand the set of expression-based constructs to include those traditionally done using statements.

[mattwar]

@gafter assume I'm a user of generics, and writing a generic method or class. How is a bottom type going to affect the code I write? Where does it show up?

[JoergWMittag]

@mattwar: Assume you write some sort of immutable container. Think IEnumerable<out T>, IReadOnlyList<out T>, or a potential future addition to the BCL of IOptional<out T>. Especially for IOptional<out T>, you want to have an empty value, usually called None. You don't want to have multiple empty values, i.e. an empty None<int>, None<string>, None<Foo>.

If you want a single value that you can assign to a reference of type IOptional<int>, IOptional<string>, IOptional<Foo>, etc. then that value must be of a type that is a subtype of IOptional<T> for all T. Currently, you cannot have such a value. (Except null, which doesn't really have a type, but if it did have a type then its type would be a subtype of all reference types.) However, if you had:

class None : IOptional<nothing> {}

where nothing is our hypothetical bottom type, then a singleton instance of None could be used as a single unique value that denotes the absence of an optional value.

Similary, if you want to have a single empty list to which you can polymorphically prepend an int or a string or a Foo to get back an IMyImmutableList<int>, IMyImmutableList<string>, or IMyImmutableList<Foo>, then you want your singleton empty list to be of type IMyImmutableList<nothing>.

Or, put it another way: null is occasionally useful, albeit badly implemented. The "type" of null is a bottom type (for reference types). So, clearly a bottom type is useful. Exposing it to the programmer means that you can write null-like abstractions.

Are functions that are known not to return common enough that we'd need special language syntax to call them out? As for your #2, the compiler can model these branch expressions without the need of introducing new language keywords. [bold emphasis mine]

Actually, the whole point of this proposal is to make it possible for library authors to implement these abstractions so that you don't have to introduce "special language syntax" or "new keywords". We just want to add one type to the BCL, and one rule to the type system.

Think about it this way: we do have "special language syntax" and a keyword because of the lack of a Unit type, namely the void keyword for methods that don't return a useful value. The lack of a proper Unit type also leads to code duplication (see Func vs. Action). We want to avoid the same mistake with a bottom type.

[HaloFour]

@juliusfriedman

#538 (comment)

[yaakov-h]

What on earth is that and how is it related to a bottom type?

[333fred]

@juliusfriedman I've marked your comments as off topic as they appear to be entirely unrelated to the never type. If you want to put more detail in your comments than just a giant code blob with no explanation, feel free. Just ping me after they've been edited and I'll unhide them.

[sylveon]

A good use for this would be the ThrowHelper pattern, where you use helper functions to throw to improve codegen size and help inlining analysis. Because it's a function, it can't be used in all places where a throw expression can (??, ternaries and switch expressions being examples)

public static never ThrowArgumentException(string name, string message)
{
    throw new ArgumentException(name, message);
}

var result = item switch
{
    "hello" => 0,
    42 => 1,
    _ => ThrowHelper.ThrowArgumentException(nameof(item), "Invalid item")
};

Without the never type (using void and [DoesNotReturn]), this code wouldn't compile, because ThrowArgumentException doesn't return a type.

There is a workaround, which is making ThrowArgumentException generic so that it can have a return type, but then it's a workaround, requires you to explicitly write down the generic type, and wouldn't work with pointer types or references.

[DoesNotReturn]
public static T ThrowArgumentException<int>(string name, string message)
{
    throw new ArgumentException(name, message);
}

var result = item switch
{
    "hello" => 0,
    42 => 1,
    _ => ThrowHelper.ThrowArgumentException<int>(nameof(item), "Invalid item")
};

[gdar91]

The Never type doesn't have to be a subtype of every other type. It should just be a type with no elements. Then there will be a generic function Absurd<T>, which will take a Never as a parameter and return any value of type T that you want. It can say that it can return anything and still be a valid value of type T in any expression. Of course, it never has to actually create and return a value of type T, since it can't be called at all (because there is no way to provide a value for the argument - Never). Then, for convenience, you can add an implicit conversion operator from Never to any type T.

[Richiban]

@gdar91 Implicit conversions are not enough. One of the main use cases for a bottom type is in generics (e.g. IEnumerable<never> is assignable to IEnumerable<string> etc) but implicit conversions are not going to help you there.

[mrange]

As we discussed lists, optionals I also want to point out that Never is also useful for Choice types.

Something like this

interface IChoice<out TLeft, out TRight> {}
record Left<T>(T Value) : IChoice<T, Never>;
record Right<T>(T Value) : IChoice<Never, T>;

IChoice<int, string> x = Left(1);
x = Right("Hello")

Without Never what should the Right type be for Left? Without Never it gets inconvenient fast.

[remiguittaut]

The very big interest of a bottom type used in conjection with covariance is a variation of the IChoice type above and can be seen in Scala, which such a type called Nothing.

If we have a type IO<out L, out R> with the same record subtypes to wrap and make side-effects pure, L always representing the failure case by convention, we can define functions which accept only infaillible arguments, because we want to encode and enforce at the type level that the client argument should not fail in any case, by having a function such as Release:

interface Either<out L, out R> {}
// record cases  of the simulated union type, Left and Right
// ...

interface IO<out L, out R> {}
// record cases  of the simulated union type, Left and Right
// ...

// Either<L, R> is a similar data structure representing either an error L or a success R
// In this case, it is the result of running the pure side effect IO and awaiting it.

public IO<L, R> Release(this IO<L, R> io, Func<Either<L, R>, IO<Never, Unit>> releaseF)

The thing is that releasing a resource is by nature a best effort thing, if we can't release it, at some point we have to give up.

Without a bottom type, we can't express the required infaillible behaviour, and we can't use the covariance to return Never instead of L in the error channel.

[remiguittaut]

The gurantee of being infaillible is the fact that the bottom type is impossible to instantiate, it is just a marker, what we call a phantom type.

[acasta-yhliu]

Yes, actually the previous void type should be unit since it actually returns, but Nothing just do not return. It should be the subtype of all other types to satisfy the type system

[LupusInferni315]

@orthoxerox Are functions that are known not to return common enough that we'd need special language syntax to call them out? As for your #2, the compiler can model these branch expressions without the need of introducing new language keywords.

I don't know about for other people, but I often defer my exception throwing to other methods (that obviously never return), usually for the sake of ensuring that all exceptions are written in a standard style eg. (this is a simplified version of it, since I don't want to dig up the original code this example is from)

private static void ThrowNullBufferException(string buffername)
{
    throw new ArgumentNullException(buffername, $"'{buffername}' cannot be null or contain less than one element");
}

// then anywhere I'm validating a buffer
public static void SomeBufferRelatedMethod(object[] buffer)
{
    if(buffer == null || buffer.Length < 1)
        ThrowNullBufferException(nameof(buffer));
}

// or in some other cases where the object might not be a buffer, but follows similar rules

public static object SomeListRelatedMethod(IList<object> list)
{
    if(list == null || list.Count < 1
        ThrowNullBufferException(nameof(list));
}

or in my current situation (why I even found this page), I have a number of methods that are guaranteed to throw (like in the previous examples) but they have additional actions that must be performed before the actual throwing can occur (logging the exceptions to a logfile). I'm not sure however that I like either 'bottom' or 'never' as the keyword, perhaps it might be clearer if the syntax was

throw MethodName(whatever paramaters)
{
    // whatever actions might need to be taken before we throw
    throw SomeException();
}

[vladd]

@LupusInferni315
I think throw is not the right keyword here, as a never-returning method may just enter an endless loop or call Environment.Exit() (or [intentionally] crash in the native code).

[mrange]

For me the big use-case for me for a Never type is not to indicate a non-returning method (although it's useful). The big use-case for me is to use to indicate empty collections or be able to implement a choice type without it getting awkward. I even think it might lead to less special cases in the compiler. For example throw new AnException() could then be an expression that results in Never and that then fits into a switch expression or ?? expression without any special handling.

But I am not a compiler programmer so I am likely wrong.

[LupusInferni315]

@LupusInferni315 I think throw is not the right keyword here, as a never-returning method may just enter an endless loop or call Environment.Exit() (or [intentionally] crash in the native code).

That's true, but in the example I gave this would specifically apply to methods that always throw, not situations that enter an endless loop (since the 'endlessness' of a loop is hard to 'determine'), however; I had not considered methods that call Environment.Exit() or that method itself

[vladd]

@LupusInferni315
It's complicated to prove the mathematically strict (it requires solving the Halting problem), but the compiler can use the already existing reachability analysis. The closing brace should just be unreachable.

[Richiban]

For me the big use-case for me for a Never type is not to indicate a non-returning method

For me (who regularly uses functional languages) the real value of a Never type is actually in generics. Nothing/Never/Bottom is a type that has no values and is therefore assignable to any other type, which means that for covariant generic types MyType<Nothing> is also assignable to any MyType<T>.

This is particularly useful for things like Option types or immutable LinkedLists where None or the empty list can be singletons. This is a potential performance improvement (you don't have to allocate every time you need an Option that is None) and also allows for reference equality when comparing.

With a proper option type, this should be possible:

var none = new Option<Nothing>();

Option<string> = none;
Option<int[]> = none;
Option<object> = none;

[vladd]

@Richiban
I doubt that it's going to work with int, as value types don't support variance.

[Richiban]

@Richiban I doubt that it's going to work with int, as value types don't support variance.

You're right, I shouldn't have used a value type in my example. I'll remove it for future reference