How to Introduce a Parametric Top Type?

[odersky]

We'd like to introduce a parametric top type (call it Top for now) with the following properties:

• Top is a supertype of Any.
• Any is the only class directly inheriting from Top.
• The only member of Top is asInstanceOf
• To check a scrutinee X against a pattern P, both X and P must be instances of Any.

The question is where Top would replace Any in the rest of the language. There are several choices.

Minimal Solution

Top is just another type. We have to opt in when using it. For instance, we could write

opaque type IArray[+T] <: Top = Array[T]

This would close the hole described in #7314.

This solution is maximally backwards compatible with current Scala. But it has the downside that abstract or opaque types with Top as upper bound are not very useful. They cannot be passed to any regular unbounded type parameter, since such parameters would have upper bound Any.

Intermediate Solution

Opaque types have Top as default upper bound. Type parameters and abstract types stay as they are. This would still be backwards compatible with Scala-2, since opaque types are a new construct. But the problems of usability of opaque types remain.

Maximal Solution

Unbounded abstract types, opaque types, and type parameters have Top as upper bound, instead of Any.
This means

1. we cannot pattern match on such types anymore
2. we cannot use the ==, equals, hashCode, or toString defined in Any on such types. On the other hand, we could re-introduce these methods as extension methods for these types, which was not possible before.

This is ultimately the most clear and useful solution, but it poses a lot of problems for migration and interoperability.

• Migration: Lots of code will break. Think of HashMaps, for instance. We could alleviate some of the breakage by adding an implicit conversion from Top to Any which would warn each time it is inserted. Not sure how much this would help.

• Interoperability: How should we interpret a Java or Scala-2 unbounded type parameter? If we assume bounds Nothing..Any this would again hamper the usefulness of Scala 3 parametric types. I.e. we could not even do xs.map(f) if xs is of type List[T] and T is unbounded. This looks unacceptable. If we assume bounds Nothing..Top, this means that we accept that the abstraction might be broken in Scala-2 or Java code. This is bad, but better than the alternative. One additional problem is that when reading Scala-2 code we not not even know whether a type parameter is bounded or whether it has explicitly given Nothing..Any bounds. The two are indistinguishable in the pickle format. So we'd have to widen these bounds unconditionally to Nothing..Top.

Questions

• Is it at all feasible to introduce Top?
• What is the best solution (or maybe we need a sequence of steps)?
• What is the migration story?
• What timeline is realistic for this?

[sjrd]

Just to be clear: you're not aiming to do any of this for 3.0.0, are you?

[odersky]

I don't think 3.0.0 is feasible. The maximal thing we could do before 3.0 is released is something under a -Y flag, analogous to -Yexplicit-nulls. Even that is a loong stretch.

[djspiewak]

This is amazing and I love where it's going. I also don't want it in 3.0.0. 😃

Obviously my interests are aligned with the maximally useful case, but clearly there are some significant barriers to work out to make that possible. An alternative type variable syntax might be one way to improve this, though I'm not sure if that's better than explicit bounds. The real problem is the network effect. Everything that can bound with Top would need to, otherwise it would be very difficult to use in downstream signatures. That alone implies that the only meaningfully useful incarnation of this is the maximal one, and the compatibility story would need to be carefully sorted out.

[IndiscriminateCoding]

Given that Maximal Solution is breaking lots of things anyway - doesn't it makes sense to also rename Any -> Object and Top -> Any?

[LPTK]

I think the truly maximal approach would be to also make traits and classes by default extend Top instead of AnyRef. Most traits are not meant to be matched anyway, and it would be nice to opt out of having equals and co. defined by default on every class. Case classes, sealed traits and enums would obviously still extend AnyRef by default.

It seems completely acceptable to me that Scala 2 signatures be interpreted as bounding types between Nothing..Top instead of Nothing..Any. It's a small unsoundness to pay for providing a reasonable migration story towards a great improvement of the language.

[nafg]

As @IndiscriminateCoding alluded, there are really two questions here. One is the added "expressivity" to the type hierarchy and what the defaults are (which things by default have things like equals and type testing). The other is whether the expressivity is achieved by adding a new type above Any, or by moving some of Any's current power down into an immediate subtype.

One difference is if I take e.g. a parameter with the explicit type Any, am I affected?

It seems that it would be easier for learning at least, if the names convey as much as possible. According to that argument, Any should include everything, and there could be a new subtype. Perhaps Scrutable or something in that direction?

[odersky]

@nafg I tend to agree. It seems the only practicable solution is the maximal one. Every other scheme incurs too much friction between mismatching bounds. But then it's better to leave the extreme types as Any and Nothing. So Any is the new Top. Most Any methods would go to a new trait or abstract class, Scrutable (or Inspectable or Classable/Classed/Classified?`).

So we'd have:

abstract class Any:
  def asInstanceOf

abstract class Classable extends Any:
  def isInstanceOf
  def getClass
  def ==
  def !=
  def ##
  def equals
  def hashCode
  def toString

class AnyVal extends Classable

class Object extends Classable

For migration there would be an implicit conversion from Any to Classable that issues a warning. Another useful addition would be an extension method toString on Any. toString is pervasively used and relatively harmless. If it's not wanted for some code the extension method could be unimported,

[sjrd]

How should we interpret a Java or Scala-2 unbounded type parameter?

Since this is not going in 3.0.0, and it will break TASTy compatibility, it won't be included before 3.T. At that point, binary compat with Scala 2 will be dropped, and therefore the question of how to interpret Scala 2 code is moot: we won't interpret Scala 2 code.

For the same reason, the Intermediate Solution is pointless. It's equivalent to the Minimal Solution.

Java compatibility is a different problem. It's not only about type parameters coming from Java, but also values of type Object. Realistically, we'll have to map them to Any (was Top) I think.

toString() will probably have to be allowed in some way or another. Or are we also going to prevent using Anys in string interpolation? That would also mean no way to print the contents of collections, and in general significantly reduce the ability to do print-based debugging.

[odersky]

How would it break TASTy compatibility?

[LPTK]

@odersky How should I understand the name Classable? Something that can be "classed"? It sounds a bit weird.

Collections are probably one of the biggest roadblock. They shouldn't require Classable type arguments, otherwise they will become unusable (can't make a list of values of unbounded generic type, for instance).

Operations like distinct should probably be made to require a type class for equals and hashCode (which could have a default implementation for all Classable types), and collection types like Set and Map likewise. This may be a good thing as it will allow not using multiversal equality, which could improve performance.

These collection changes would obviously break TASTy compatibility.

[odersky]

@odersky How should I understand the name Classable? Something that can be "classed"? It sounds a bit weird.

Yes, something that has a getClass. Not sure about what's the best name myself.

These collection changes would obviously break TASTy compatibility.

Sure. But before that we can also leave collections as they are in 2.13. They would be unsafe in the new model, but that's OK for a while.

[odersky]

How about Classy?

[julienrf]

• The only member of Top is asInstanceOf

May I ask why we even need it? Is the goal to have a parametric top type?

• Interoperability: How should we interpret a Java or Scala-2 unbounded type parameter?

Maybe Sébastien already suggested something similar, I’m not sure, but could we explicitly store in TASTy the type bounds Nothing..Top of unbounded type parameters compiled with Scala 3? When reading Scala 2 classfiles, we would use the bounds Nothing..Any.

• Migration: Lots of code will break. Think of HashMaps, for instance.

toString() will probably have to be allowed in some way or another. Or are we also going to prevent using Anys in string interpolation? That would also mean no way to print the contents of collections, and in general significantly reduce the ability to do print-based debugging.

I think it would be worth experimenting with a really empty top type (with no members). Personally, I’m not sure toString does more good than harm. Of course, this would mean redesigning the collections to take an implicit Show[A] to print the collection elements, and to take an implicit CanEqual[K] (or Hash[K]) to compare Map keys. But this could be an interesting experiment.

[odersky]

Some lessons learned from experimenting with it in #10670

1. Adding a class Scrutable and putting isInstanceOf like behavior in it is quite feasible. In Add Matchable trait #10670, there are three operations that are now only possible on Scrutable instances: getClass, isInstanceOf, and deconstruction with constructor patterns or typed patterns. An implicit conversion maps from Any instances to Scrutable instances. The conversion can be tuned to be on only for certain language versions or under certain flags.

2. It would be much harder to migrate equality, hashCode, and toString. The problem is that these operations are recursive, so they cannot really be expressed as a member of a universal trait. This affects all case classes. For instance, :: and with it List cannot have a sound equality since the element type of lists is not bounded by Scrutable. Nor can they have hashCodes and toStrings if these operations are moved to Scrutable. So moving these operations to Scrutable would affect fundamentally what code we guarantee in case classes and how we construct libraries. I do not see a way to do this without causing huge migration pain.

But the biggest win in terms of parametricity is achieved anyway by doing (1). (1) prevents us from full featured access including mutations after downcasting. An example of code that would be prevented is in #7314:

  val imm = IArray(1,2,3) // supposedly immutable
  imm match
    case a: Array[Int] => a(0) = 0

By comparison, (2) just prevents certain oracles. I.e. say we have

def f[A](x: A, y: A): A

With (1), we know that f will return either x or y (always assuming no casts or unchecked matches). With full-featured parametricity we'd know in addition that f will either always return x or always return y. But that guarantee holds only in a pure functional language, where no external inputs are allowed. If f had access to the current time, or a simple random generator, or could read a mutable variable, that second guarantee would be destroyed anyway. So it seems to me that for getting useful theorems for free (1) is much more important than (2).

This means there's a realistic possibility to get better parametricity by just implementing (1). If we want to do that, then we might want to put everything in now, and just turn on the warning for later. #10670 has shown that this can be done with a very high degree of backwards compatibility. The advantage is that people using opaque types (or abstract types or type parameters, really) can do so with a better degree of safety by opting for stricter checking.

How should we deal with the awkward squad in (2) then? For equality and hashCode the ultimate solution would be to make it typeclass-based. We might leave equals and hashCode as they are in Java (we don't really have a choice there), but could work to re-interpret == and ##. Or invent other equality and hashcode operators (===, ### anyone?), but I would really prefer if we could avoid that. For toString, I believe it is useful as an inspection tool for debugging, so I'd leave it where it is, and invest in a separate typeclass-based show instead.

[odersky]

One problem is the name Scrutable which is somewhat cute for experts, but unfriendly for beginners. Since this will be in every diagram of top-level classes it's important to have a friendly name. So, maybe Classy is not so bad? Or are there other candidates?