Pre-SIP: Parametric Top

Perhaps for Scala 2, the syntax extends Top can be used to create opaque types, analogous to extends AnyVal, but without yet truly truly introducing the full glory of Top as the true top type. The idea would be to have all the features of the opaque types proposal, but with the same syntax that Dotty would have for defining them.

There are probably some serious drawbacks with this that I am blind to.

+1 on parametric Top (at least for Dotty).

If A meant A <: Top, that pattern matching must be forbidden to ensure parametricity. A probably safe and overly conservative rule would forbid matching on scrutinees whose type mention any parametric type variable. Here a type match on Array is safe, but drawing good rules for full Scala in general seems nontrivial.

@oscar IIUC, the idea here is “value classes that truly never box” — most details are in doc linked earlier, and indeed new does not box: scala.github.com/_sips/sips/2017-09-20-opaque-types.md at f61ec0dd31c9d650dc867dcb5e74506e7c26f7be · non/scala.github.com · GitHub
@scottcarey extends Top and opaque types don’t seem to have quite the same semantics… or do they?

EDIT: more importantly, this proposal without a parametric Top would give you classes with questionable semantics — you still have all methods from Any, but they have inappropriate semantics, the ones given by the implementation, something a true parametric Top avoids. Though I suspect the earlier opaque types, and the encoding from @S11001001’s blog post, share this downside.

In all these proposals, it seems polymorphism over primitives must still box.

How does one implement asInstanceOf on primitives without at least one level of boxing?
I guess in all these proposals, if A is a type variable, a is a primitive (wrapped in a “newtype” or not) and a: A , a must have been boxed anyway, but reference types need no extra boxing. (In miniboxing A <: AnyVal is erased to long, but it seems miniboxing is not going to be merged).

The only difference (maybe) is that if you use some suitable specialization (Scala 2’s, miniboxing, Dotty-linker) and have parametric Top, the optimizer has a easier time removing boxing. Casts to AnyRef would still box, and the results of reference equality would be affected, but those results shouldn’t be guaranteed under parametric Top (not sure of the current actual guarantees).

Here’s a possible way to help migration to the new scheme:

  • [T] means [T <: Top]

  • Add a deprecated implicit conversion in Predef

     @deprecated def topToAny(x: Top): Any = x.asInstanceOf[Any]
    
  • special case pattern matching, so a scrutinee bounded by Top is converted to Any, using the same deprecated conversion.

That should cover the majority of problematic cases. There will be a few that remain, but overall it seems doable.

@blaisorblade asInstanceOf is by definition unsafe. It would simply succeed if the underlying type is compatible with the representation type. So, no boxing is needed.

So assuming then that

class Foo(x: Double) extends Top

does not box, then what is the difference between:

implicit class Foo(x: Double) extends Top
implicit class Foo2(x: Double) extends AnyVal

We now have two ways to do method enrichment? That seems like a shame. I guess you should never do that after Top. Is that right?

Secondly, I find it ugly that now we would have a class that never allocates. Previously in scala class was something that could (in principle) be an allocation. Even with extends AnyVal in a generic context we get allocation. All class declarations correspond to some kind of JVM class entity.

To me, the opaque type proposal is much cleaner here because we already have type, and it never boxes or allocates (as far as I know). With opaque we are just putting additional constraints on a type but otherwise the rules apply. Similarly, we keep the notion that a class in scala corresponds to something that can be a JVM class.

2 Likes

I should add that while substitute is sufficiently powerful, it’s not necessarily convenient.

This example from the other thread which runs as written with opaque types:

def mdl(m: Map[Double, Logarithm]): Map[Logarithm, Double] = m

Suppose alternatively a =:= is provided and GADT-style =:= is made to work in patmat, it must be written

// supposing Logarithm.repr: Double =:= Logarithm
def mdl(m: Map[Double, Logarithm]): Map[Logarithm, Double] =
  Logarithm.repr match {
    case Refl() => m
  }

Supposing a =:= is provided but GADT-style is not made to work:

def mdl(m: Map[Double, Logarithm]): Map[Logarithm, Double] = {
  type F[A] = Map[Double, A] =:= Map[A, Double]
  Logarithm.repr.substitute[F](implicitly)(m)
}

Scala users might have some difficulty coming up with the correct F for various scenarios.

If we started from scratch that would still be my preferred scheme, but it’s probably too hard to migrate to it. So in what follows I propose to leave Any as it is and introduce a new, fully parametric type Top.

I’m not so sure … I think the complications of adding a new Top type
to Scala are at least as great as changing the semantics of Any and
adding AnyObj to match Dotty.

It’d be interesting to make the change and try it with a few
representative projects and see how much breaks.

Cheers,

Miles

3 Likes

I’m probably not making myself clear — simply stated, the JVM does not allow checkcast on primitives, so they have to be boxed once. Or do I miss something? That boxing is not due to newtypes but is still relevant.

In particular, saying that “newtypes never box” is as misleading as “primitives never box”. And since really never boxing is the goal, all the newtype proposals are necessary but not sufficient without specialization.

1 Like

I view extends Top as a better version of extends AnyVal — there’s a tradeoff in expressivity, but I’d never use AnyVal. extends Top or opaque types don’t let you change equals, but if you want the features of either, you need to switch to typeclass-based equality (not multiversal equality).

Type itself doesn’t, but you still box in generic contexts unless you specialize:

type T = Int // defined type alias T
def foo[U](u: U) = u //foo: [U](u: U)U
foo[T](1) //res0: T = 1 //boxing HERE

A better discussion of what boxes when is in the README for GitHub - hobwekiva/newtypes (@jvican that might help for revisions of the SIP) — I doubt you can improve on the generated code much.

I think that might be a valid and important usability concern about the concrete syntax. Maybe this should be written type Foo(a: Int) extends Top, newtype Foo(a: Int), or yet something else. In all cases, Foo would extend Top but not Any/AnyVal/AnyRef.

As long as it’s not forgotten about, this should be discussed separately so that we get the right semantics before bikeshedding the details (Pre-SIP: Unboxed wrapper types - #52 by jvican). And I’m not implying at all concrete syntax doesn’t matter, it’s just harder to discuss.

EDIT: @jvican is the plan to sketch out this proposal before choosing? It can be fine if Martin leaves details as exercises to the reader, but we still need to see the worked out version. I understand parts of the result doesn’t look very different from your earlier document on “newtype classes” ( extends Newtype), but that’s not clear. Also, details on Top are spread in a discussion over the Dotty repo that didn’t quite reach a conclusion.

  • Parametric Top: They are different types but the backend will optimize them as the same underlying type after type erasure.
  • Opacity type: They are the same type but the typer did not know.
1 Like

I’m not so sure … I think the complications of adding a new Top type
to Scala are at least as great as changing the semantics of Any and
adding AnyObj to match Dotty.

In that case I’d much prefer to keep the original proposal and keep Any as the true top type!

It’d be interesting to make the change and try it with a few
representative projects and see how much breaks.

If you get around to do this, I’d be really interested in the results!

That’s a good way to put it.

I’m probably not making myself clear — simply stated, the JVM does not allow checkcast on primitives, so they have to be boxed once. Or do I miss something? That boxing is not due to newtypes but is still relevant.

Ah yes, of course. The question is only whether newtypes do any additional boxing.

1 Like

So, we did some brainstorming on what a conversion to parametric top would entail. The basics look easy but there’s one show-stopper, and that’s parametric classes and in particular parametric case classes - shoutout to @OlivierBlanvillain for having brought up the problem.

The basics would be

  1. drop all methods except asInstanceOf on Any,

  2. Introduce a new subclass class AnyObj which has the methods that were dropped on Any.

     Any
      |
    AnyObj
      |
    Object
    

    (The text above used Top for Any and Any for AnyObj but it does not matter much either way what names are used.

  3. Introduce a deprecated conversion from Any to AnyObj

    @deprecated Any2AnyObj(x: Any): AnyObj = x.asInstanceOf[AnyObj]
    

That’s mostly it. There are some refinements on pattern matching but nothing too important. It would mean that most code should port cleanly, at the price of deprecation messages where methods were used on Any.

However, we have a problem: How should we express a class such as Some[T]?. Should that be Some[T <: AnyObj]? That would be awkward because it would mean that we cannot return an optional result over instances of unconstrained type parameters. So the only sane alternative is to keep it as Some[T <: Any]. But then, how should be define equals and hashCode on such a class?

If we keep the original definition, it would look like this:

def equals(that: Any) = that match {
  case that: Some => Any2AnyObj(this).x.==(that.x)
  case _ => false
}

Note that it’s impossible to give a proper definition of equals without the deprecated Any2AnyObj conversion (or the cast in which it is implemented). So, we can’t define equals and hashCode for Some in a non-deprecated way!

Now, we could try to do without equals and hashCode but I am afraid this would invalidate a large part of all Scala code out there without an obvious remedy. The upheaval of going to an equality type class would be enormous; among other things it would shut the door to any meaningful interop with Java.

We could still possibly live with the situation and accept that case class equals and hashCode violate the parametricity constraint. For instance, we could accept that one can now observe whether two values x and y of an unbounded type parameter are the same by writing

Some(x) == Some(y)

Not nice, but maybe that’s the only reasonable compromise. However, it looks to me then that the idea of saying that value classes extending Top never have to box is untenable. The previous approach was “these are classes, but we never need to create instances of these classes because nobody will be able to observe the difference between a class instance and its underlying value”. Nobody means: Only code that breaks the parametricity constraint using the deprecated conversion or a cast will observe the difference. But now that means that using any case class is enough to observe the difference because every case class has to use the unparametric conversion in its implementation of equality.

I think it’s still worthwhile to explore the idea of parametric top (either as the default upper bound or as a bound that needs to be given explicitly). But for unboxed value classes I think going with the opaque type proposal is the safer bet.

7 Likes

Just my 2 cents, but I think if significant portions of the standard library would have to break parametricity because it’s not feasible to introduce (among others) Equals and Shows typeclasses then parametric Any/Top is also not worth it. Almost everything a basic program could do would break parametricity anyway.

2 Likes

This problem can be resolved if we force that a top type always equal to its underlying type. We don’t have to drop runtime abilities on java.lang.Object, like eq, getClass, equals and hashCode methods. We can simply make those methods final and always forward those methods to their underlying implementations.

case class MyValueClass(s: String) extends Top

MyValueClass("foo") == "foo" // true
MyValueClass("foo".intern()) eq "foo".intern() // true
MyValueClass("foo").getClass // java.lang.String

Very simple. Nothing breaks.

The original design of Parametric Top is problematic because lack of runtime equality ability, however the syntax of Parametric Top looks more concise than Opacity Types.

Why not keep both the equality behavior from Opacity Types and the syntax from Parametric Top altogether?

Surely a type class Option would be a good thing. AnyRef could then use null as its None instance, and avoid wrapping altogether. As i understand it currently an Option Int is double wrapped, with a type class it could be reduced to a single wrapping.

One thing I’ve often wondered about it whether you could use -2 power 31 as the None value for an Option[Int]. But maybe that would create too many problems. The name could be changed to Opt at the same time. Very commonly used names should be short.

Switching to Type classes would certainly be painful. But if we were designing Scala from scratch would anyone now seriously argue against Type classes for parametrised types taking a parameter not inheriting from AnyRef? So maybe the Type class path is in the long run inevitable and its just a question of how long we take to accept the inevitable and how long we string out the pain of denying it.

You mean this allocation-less Option???

https://gist.github.com/DavidDudson/dee0d6ac075919a57090b45a450ec70b

It works without any SIP.
Works in for comprehensions etc.
Only boxes primitives once.

Or maybe @sjrd’s scala-unbox-option: https://github.com/sjrd/scala-unboxed-option.