dart-lang / dart-lang/language
Allow lower bounds on type parameters of functions
- 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
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