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.

[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

[Foxtrek64]

See #8604 for the champion