dart-lang / dart-lang/language

Allow lower bounds on type parameters of functions

Open
#1,674 10 comments 11 reactions 0 assignees View on GitHub
small-feature variance
Dominant language
TeX
Stars
2.9k
Forks
239
Avg merge
2d 18h
Merged PRs (30d)
14

Description

This issue is a proposal for adding lower bounds on type parameters of functions and methods. They are supported in, for instance, [Scala](https://docs.scala-lang.org/tour/lower-type-bounds.html), 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:

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

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

class Nil extends Node {}

void main() {
Node node = ListNode(1, Nil());
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:

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

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

class Nil extends Node {}

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

In this case we are creating a new `ListNode`, 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`, 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`:

```dart
abstract class Node {
ListNode prepend(U element) =>
ListNode(element, this);
}

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

class Nil extends Node {}

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

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:

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

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

class Nil extends Node {}

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

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

```dart
abstract class Node {
ListNode prepend(U element) {
if (element is E) return ListNode(element, this);
return ListNode(element, this);
}
}

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

class Nil extends Node {}

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

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

Contributor guide

Open the contributing guide

Research direction

Review the proposed `X super T` syntax and the Node/ListNode examples in the issue, including the interaction with covariance and type inference. Determine the language-specification changes and compatibility rules needed, then validate that the examples are statically safe and preserve the intended inferred types.

Written by the indexing model from the issue text.

Assessment

Tech stack
dart
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.