Allow lower bounds on type parameters of functions

[eernstg]

This issue is a proposal for adding lower bounds on type parameters of functions and methods. They are supported in, for instance, Scala, and they are a well-established device that enables some constructs involving variance to be statically sound.

A lower bound on a type parameter of a method is a covariant position, so if we add sound variance it would be allowed to use covariant and invariant type variables in that position. Currently all class type variables are covariant, so they can all safely be used there. The syntax of type parameters would be extended to allow X super T (allowing both an upper and lower bound on the same type variable is not supported).

For example, consider this program where we are using a standard Dart approach (similar to List) where the type parameter E occurs in some contravariant positions:

abstract class Node<E> {
  ListNode<E> prepend(E element) => // Unsafe parameter type!
      ListNode(element, this);
}

class ListNode<E> extends Node<E> {
  final E head;
  final Node<E> tail;
  ListNode(this.head, this.tail);
}

class Nil<E> extends Node<E> {}

void main() {
  Node<num> node = ListNode<int>(1, Nil<int>());
  node = node.prepend(3.4); // Throws.
}

One might assume that an immutable list would be immune to the dynamic type errors associated with dynamically checked covariance (usually, those errors arise when we mutate a list), but a method like prepend shows that it can occur even with immutable classes.

However, prepend creates a new list, so we can make the choice to give it a new type argument:

abstract class Node<E> {
  ListNode<U> prepend<U>(U element) =>
      ListNode(element, this as Node<U>);
}

class ListNode<E> extends Node<E> {
  final E head;
  final Node<E> tail;
  ListNode(this.head, this.tail);
}

class Nil<E> extends Node<E> {}

void main() {
  Node<num> node = ListNode<int>(1, Nil<int>());
  node = node.prepend(3.4);
  print(node.runtimeType); // `ListNode<num>`.
}

In this case we are creating a new ListNode<num>, and it is statically safe to put 3.4 into it (there is no unsafe covariance here, because E only occurs covariantly).

Of course, we have two casts this as Node<U>, and they will fail unless E <: U. However, the statically known value Es of E satisfies E <: Es (because the classes are covariant in E), so if we ensure that Es <: U then it is also guaranteed that E <: U.

So we can ensure this with a lower bound on U:

abstract class Node<E> {
  ListNode<U> prepend<U super E>(U element) =>
      ListNode(element, this);
}

class ListNode<E> extends Node<E> {
  final E head;
  final Node<E> tail;
  ListNode(this.head, this.tail);
}

class Nil<E> extends Node<E> {}

void main() {
  Node<num> node = ListNode<int>(1, Nil<int>());
  node = node.prepend(3.4);
  print(node.runtimeType); // `ListNode<num>`.
}

This version of the code is statically safe: there are no occurrences of E in a contravariant position, so there are no dynamic type checks.

We could also consider a static approach:

abstract class Node<E> {
  static Node<U> buildNode<U>(U element, Node<U> node) =>
      ListNode<U>(element, node);
}

class ListNode<E> extends Node<E> {
  final E head;
  final Node<E> tail;
  ListNode(this.head, this.tail);
}

class Nil<E> extends Node<E> {}

void main() {
  Node<num> node = ListNode<int>(1, Nil<int>());
  node = Node.buildNode(3.4, node);
  print(node.runtimeType); // `ListNode<num>`.
}

This approach seems to be equally powerful as the approach based on a lower bound, but this is not quite true:

abstract class Node<E> {
  ListNode<U> prepend<U super E>(U element) {
    if (element is E) return ListNode<E>(element, this);
    return ListNode(element, this);
  }
}

class ListNode<E> extends Node<E> {
  final E head;
  final Node<E> tail;
  ListNode(this.head, this.tail);
}

class Nil<E> extends Node<E> {}

void main() {
  Node<num> node = ListNode<int>(1, Nil<int>());
  node = node.prepend(5);
  print(node.runtimeType); // `ListNode<int>`.
  node = node.prepend(2.4);
  print(node.runtimeType); // `ListNode<num>`.
}

This illustrates that we are able to combine the static type safety and the dynamic preservation of the more specific type argument.

[lrhn]

Another example where a lower bound would help are:

class Iterable<E> ... {
 R firstWhere<R super E>(bool Function(E) test, {R Function()? orElse});
}

where null safety migration has hit a lot of cases of listOfNonNullable.firstWhere(..., () => null); which no longer works.

[leafpetersen]

Tagging this with variance as it seems like something we might want to consider for combination with that feature.

[eernstg]

Here's another related issue: dart-lang/sdk#51248, where this comment mentions that a lower bound would be useful for Future.catchError.

[eernstg]

Here is yet another example where lower bounds on type parameters of functions would allow us to change a dynamic function call to a statically checked function call: #3007 (comment).

[cranst0n]

I believe I have another use case for this. I'm attempting to port some Scala code from fs2 to Dart and have hit a snag.

Scala:

sealed abstract class Pull[+F[_], +O, +R] {
    ...
    ...
    def flatMap[F2[x] >: F[x], O2 >: O, R2](f: R => Pull[F2, O2, R2]): Pull[F2, O2, R2] = ???

source

And what I've been able to come up on the Dart side:

sealed class Pull<O, R> {
    ...
    Pull<O2, R2> flatMap<O2, R2>(covariant Function1<R, Pull<O2, R2>> f) => ???

source

The constraints on the relationship between O and O2 can't be represented in Dart unfortunately and I think I'm stuck. Not sure if this feature alone would solve my issue or if I would also need control over the variance of the Pull type parameters as well.

[eernstg]

I think it's fair to mention that F[_] declares F as a variable type constructor (a higher-kinded type, rather nicely described in https://stackoverflow.com/questions/6246719/what-is-a-higher-kinded-type-in-scala). Dart does not support higher-kinded types at all, and I don't think it's likely that it will.

I don't think there's a reasonable way to emulate higher-kinded types in a language where they aren't supported natively. So if you're primarily interested in playing around with this kind of fancy types then Dart isn't your language.

However, if you just need a specific run-time behavior, and that behavior could have been managed using such types, I think it would make sense to consider a dynamically typed approach: Use the type dynamic and/or types where dynamic is a subterm in you software, at the smallest possible set of locations, and then restore static type safety by dynamic type checks whenever possible.

The following is a silly example, but I think it illustrates the idea:

// We'd like to have a recursive type `typedef TreeOfInt = int | List<TreeOfInt>;`
// But we can't express that in Dart.
// So we use `List<dynamic>` containing `List<dynamic>` or `int`,
// and maintain the discipline manually.

var /*TreeOfInt*/ tree = <dynamic>[1, 2, 3, <dynamic>[4, 5]];

void printTreeOfInt(/*TreeOfInt*/ dynamic tree) {
  if (tree is int) {
    print(tree);
  } else if (tree is List<dynamic>) {
    print('[');
    for (dynamic node in tree) printTreeOfInt('$node, ');
    print(']');
  } else throw "Malformed `TreeOfInt` encountered!";
}

[rubenferreira97]

@cranst0n Even if it is difficult to implement higher-kinded types in Dart we can always upvote #1655

[cranst0n]

@eernstg thanks for your feedback. What you're saying makes sense. I've taken a similar approach like in this case so I guess I'll just have to do the same here. It would be nice though to have the compiler do the heavy lifting instead of my mental model 😄

I'm not really concerned with higher kinded types in this particular instance, as I've fixed the F[_] type parameter to a concrete type (the IO I referenced above), but I certainly wouldn't complain if dart ever changed course and decided to support them.