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.

• "Our language does integer additon, and it does integer addition well" first one says.
• He continues "There's a pull request of someone sending in ** operator. We are concerned that this will destablize the code base."
• The second language designer adds "That's not all. There's another pull request of someone adding UInt! How will it support addition with Int?"

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

• "Hi, my name is Philip Wadler, and you must implement these features as library, without recompiling existing code, and without using casting. This is the expression problem."

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:

• Scala overloads unboxed primitive == comparisons, and it outsources the implementation to Java, which by Java Language Specification widens comparisons between different unboxed types such as 1L == 1 or 1F == 1.
• To maintaintain the transparent boxing from unboxed Int to boxed java.lang.Integer, Scala emulates the widening semantics for == operator and ##, which uses Int hashCode for Float, Double etc.

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.

• We should make 1 == 1L an error under strictEquality
• We should allow custom types to participate in constant expression conversion using FromDigits