search term:

equal protection under Eq law

Recently I wrote liberty, equality, and boxed primitive types as a writeup of how equality works in Scala. This is a part 2 of that.

expression problem

A language designer walks into a bar. The person finds a table where two other language designers are comiserating with each other.

The bar freezes. The person who joined turns back to the camera and says:

The above is how I visualize the expression problem. Typeclass allows datatypes to acquire capabilities as an add-on, and provides a solution to the expression problem. In Scala 2.x typeclass and generic operators can be expressed as implicits. Scala 3.x splits these concepts as given instances and extension methods.

scala> trait Powerable[A]
         def pow(a: A, b: A): A
      
       given Powerable[Int]
         def pow(a: Int, b: Int): Int =
           var temp = 1
           if b >= 0 then for i <- 1 to b do temp = temp * a
           else sys.error(s"$b must be 0 or greater")
           temp
      
       def [A: Powerable](a: A) ** (b: A): A =
         summon[Powerable[A]].pow(a, b)
      
// defined trait Powerable
// defined object given_Powerable_Int
def **[A](a: A)(b: A)(implicit evidence$1: Powerable[A]): A

scala> 1 ** 0
val res0: Int = 1

scala> 2 ** 2
val res1: Int = 4

This ability to extend the language after the fact is one of the fundamental aspects to a modern statically typed language.

cooperative equality and Spire

As we saw in the last post:

Both the unboxed and boxed aspects of the cooperative equality makes a closed-word assumption where no one else can implement number types.

Spire runs into this issue. In 2014, Bill Venners reported:

I also noticed that == is overloaded in some places, leading to apparent inconsistencies, like:

scala> import spire.math._
import spire.math._

scala> val u = UInt(3)
u: spire.math.UInt = 3

scala> u == 3
res6: Boolean = true

scala> 3 == u
<console>:12: warning: comparing values of types Int and spire.math.UInt using `==' will always yield false
              3 == u
                ^
res7: Boolean = false

Erik Osheim’s reply says:

It turns out that value classes in Scala get the worst of both worlds right now. They can’t participate in the built-in “universal equality” (since they can only extend universal traits) so they don’t have any mechanism for making (1 == x) evaluate to true, even if the value class “wraps” the value 1.

multiversal equality’s limitation

Multiversal Equality in Dotty will not resolve this discrimination against custom number types either because unlike a normal typeclass Eql has no implementation:

@implicitNotFound("Values of types ${L} and ${R} cannot be compared with == or !=")
sealed trait Eql[-L, -R]

This means that Int’s == operator will still be used even if we introduce a given instance for Eql[Int, UInt].

let’s remove equality between Int and Long

Starting from Scala 3.x, the user can opt-into strictEquality where Int will no longer equal with types like String, but Long and Int will be compared because of there’s a Eql[Number, Number] instance for built-in numbers.

sbt:dotty-simple> console

scala> import scala.language.strictEquality

scala> 1 == "1"
1 |1 == "1"
  |^^^^^^^^
  |Values of types Int and String cannot be compared with == or !=

scala> val oneI = 1; val oneL = 1L; oneI == oneL
val oneI: Int = 1
val oneL: Long = 1
val res1: Boolean = true

For the sake of consistency, we should remove this given instance. Removing the Java-like comparison would also open the door for removing the need for cooperative equality in boxed primitive types in the future. In the non-cooperative world, UInt and Int could just fail to be compared:

scala> class UInt(val signed: Int) extends AnyVal
      
       object UInt
         final def apply(n: Int): UInt = new UInt(n)

// defined class UInt
// defined object UInt

scala> UInt(3) == 3
1 |UInt(3) == 3
  |^^^^^^^^^^^^
  |Values of types UInt and Int cannot be compared with == or !=

scala> 3 == UInt(3)
1 |3 == UInt(3)
  |^^^^^^^^^^^^
  |Values of types Int and UInt cannot be compared with == or !=

constant expression

Dotty dropped weak conformance and introduced constant expression feature.

Dotty drops the general notion of weak conformance, and instead keeps one rule: Int literals are adapted to other numeric types if necessary.

Int constant widening or narrowing happens in one of the tree expressions:

  • the elements of a vararg parameter, or
  • the alternatives of an if-then-else or match expression, or
  • the body and catch results of a try expression,

This seems like a somewhat ad-hoc fix for bad cases of lubbing. For example it won’t work once it’s nested into Option:

scala> List(Option(1), Option(1L))
val res2: List[Option[Int | Long]] = List(Some(1), Some(1))

Using FromDigits we can coerce Int literal into UInt, but it doesn’t seem to participate into the constant expression conversion:

scala> import scala.util.FromDigits

scala> given FromDigits[UInt]
     |   def fromDigits(digits: String): UInt = UInt(digits.toLong.toInt)
// defined object given_FromDigits_UInt

scala> (3: UInt)
val res3: UInt = 3

scala> List(3, 3: UInt)
val res4: List[AnyVal] = List(3, rs$line$3$UInt@3)

scala> List(3.0, 3)
val res5: List[Double] = List(3.0, 3.0)

It seems unfair that UInt cannot participate in the vararg conversion.

FromDigits typeclass for ==?

If constant conversion could be based on the FromDigits typeclass, I wonder if this be used for == as opposed to the cooperative equality. In other words, an expression like this would be an error:

scala> val oneI = 1; val oneL = 1L; oneI == oneL

but

scala> 1 == 1L

can be converted into

scala> (1: Long) == 1L

This could be a way of retaining 1 == 1L without creating second-class numeric types. However, this could quickly get out of hand:

scala> Option(1) == Option(1L)
1 |Option(1) == Option(1L)
  |^^^^^^^^^^^^^^^^^^^^^^^
  |Values of types Option[Int] and Option[Long] cannot be compared with == or !=

So extending constant expression conversion to == would probably be a bad idea.

summary

The relationship given to Int and Long should be exactly the same as the relationship third-party library like Spire can write UInt or Rational with the first-class numeric types.