Proposal: A bottom type for C#

[Eyas]

With the introduction of Generic covariance and contravariance in C#, it is clearer that the language would benefit from having a bottom type--a type which is a subtype of all types.

This would be similar to undefined in Haskell, Nothing in Scala, ! in Rust,

Benefits of a bottom-type

Collections, optional types, and type unions commonly use bottom types to make a language more expressive, but also reduce duplication/allocations, etc.

/// Empty IEnumerable
/// right now we use Enumerable.Empty<T>() and Array<T>.Empty, which
/// allocates an empty array for each type T. But Enumerable is covariant,
/// thus IEnuemrable<bottom-type> could be a valid "empty" enum:
public static class Enumerable {
    public static readonly IEnumerable<undefined> None = new EmptyEnumerable();

    public static IEnumerable<T> Empty<T>() { // backwards compat
        return None;
    }

    private static EmptyEnumerable : IEnumerable<undefined>, IEnumerator<undefined> {
        undefined Current => throw new NotSupportedException();
        bool MoveNext() => false;

        object IEnumerable.Current => Current

        IEnumerator<undefined> GetEnumerator() => this;
    }
}

// since C# arrays are covariant, and empty arrays are immutable, we can
// actually do this for empty arrays as well:
public static class Array {
    public static readonly undefined[] Empty = new undefined[0];
}
public class Array<T> {
    public static readonly Empty = Array.Empty;
}

interface List<out T> {
    T Head { get; }
    List<T> Tail { get; }
}

public static class List {
    private static class EmptyList : List<undefined> {
        undefined Head => throw new NotSupportedException();
        List<undefined> Tail => throw new NotSupportedException();
    }
    private static class NonEmpty<T> : List<T> {
        private readonly T _head;
        private readonly List<T> _tail;

        public T Head => _head;
        public List<T> Tail => _tail;

        public NonEmpty(T head, List<T> tail) { _head = head; _tail = tail; }
    }

    public static readonly List<undefined> None = new EmptyList();
    public static List<T> Single<T>(T item) => new NonEmpty<T>(item, None);
    public static List<T> Cons<T>(T item, List<T> rest) => new NonEmpty<T>(item, rest);
}

What a bottom-type could look like in C

Bottom types are usually ''unoccupied'' types, meaning that there is no valid value that represents the bottom types. Some languages have ''occupied'' bottom types (think undefined in JavaScript), where a value exists which satisfies the property of being a sub-type of all possible types.

If there were no value types in C#, then typeof(null) would have been a great candidate for an occupied bottom type.

We can do better. We can have a value type that is never assignable, which would make code a lot cleaner. My main proposal: the type of the expression that always throws is the bottom type.

Proposal: undefined/throwing/bottom

I propose that C#'s bottom type (whatever it is called) should be the type of the expression that always throws.

I think this extends the language cleanly and makes the most sense. Check the implementation of EmptyList above to see how it works naturally. Accessing a value in an empty array would also always throw an out-of-range exception. Attempt to access Current of an empty enumerable will always throw. etc.

This is also useful for delegates, etc.:

Func<int, string> f1 = (_) { throw new NotSupportedException(); };
Func<int, bool> f2 = (_) { throw new NotSupportedException(); };
Func<int, object> f3 = (_) { throw new NotSupportedException(); };
Func<int, Point> f4 = (_) { throw new NotSupportedException(); };

// can have:
Func<int, undefined> throwing = (_) => throw new NotSupportedException();
// now an expression => throw ...; will actually resolve to type undefined instead
// of complaining about not being able to infer the return type.
f1 = throwing;
f2 = throwing;
f3 = throwing;
f4 = throwing;

Non-Proposal: void

A strawman proposal is to use void as the bottom type. I want to call that out as a bad option. We currently do not have void declarations (compile error), and cannot use void-returning functions in expressions.

[dsaf]

Not directly related, but what do you think about bringing Java's wildcard generics into C#? As far as I understand they could reduce the need to inherit from a non-generic base class in some cases.

[HaloFour]

Interesting. Are there any CLR languages that implement such a feature that you know of? I'm curious as to how they may have implemented it.

The issue is that the nature of generics is largely controlled by the CLR, which enforces the variance of the generic type parameters. The CLR offers nothing higher than object, which still denotes some kind of value. To properly support bottom values it seems like the CLR would have to offer a type that is the parent of object but cannot be represented by a value. That might also permit the CLR to support variance on value types, which it currently doesn't allow. For example, I believe in your sample you can assign f3 to f1 due to contravariance, but you couldn't assign it to the others since they are value types. But if the CLR/JIT knew that the type was not going to be used it could potentially share the instance anyway as there would be no specialized code for that value type.

Beyond that you have the other little issues of bottom, undefined and throwing being perfectly legal identifiers today, which can be solved by making them contextual keywords (like var or dynamic).

@dsaf Java wildcard generics don't really satisfy the problem. The wildcard only represents the lower boundary, generally Object, and you aren't capable of creating an instance of a class without specifying the real generic type (short of breaking out the raw types, but that's the same as using the lower boundary type). Java's limitations regarding generics and its primitive types are even more limiting. I can see some value in type erasure in very specific circumstances in C# but I think it would be really confusing to have both.

[Eyas]

@HaloFour

Are there any CLR languages that implement such a feature that you know of?

I see that Clojure has a CLR implementation, clojure/clojure-clr. Clojure has a bottom type, Nothing. I'll have to look at the implementation.

The issue is that the nature of generics is largely controlled by the CLR, which enforces the variance of the generic type parameters.

Yeah I still don't enough background to figure out if extra work on the CLR side is needed get support for this. Outside of generic type variance, how does Roslyn right now figure out that:

int Foo() { throw new Exception(); }

is not a type error?

Beyond that you have the other little issues of bottom, undefined and throwing being perfectly legal identifiers today, which can be solved by making them contextual keywords (like var or dynamic).

Yeah, that's what I was thinking. A real problem however is what happens if someone declares a class with such a name: class undefined { } is currently legal. At that point, Foo<undefined> x; and undefined y; become ambiguous.

I'm curious what kind of keywords both make sense and can be reused.

[gafter]

Duplicate of #1226.