Question about implicit conversion

[rjolly]

Hello all,
Following recent discussions about restricting implicit conversions, I was thinking about perhaps one of the most basic use of these regarding numeric promotion, for instance from Int to BigInt as in:

val a = BigInt(1)
val b = a + 1

This is enabled by the definition below in object BigInt, together with this spec excerpt:

  implicit def int2bigInt(i: Int): BigInt = apply(i)

If an expression e is of type T , and T does not conform to the expression’s expected type pt . In this case, an implicit v which is applicable to e and whose result type conforms to pt is searched. The search proceeds as in the case of implicit parameters, where the implicit scope is the one of T => pt . If such a view is found, the expression e is converted to v(e)

Implicit Conversions - More Details (scala-lang.org)

Here the type of the parameter to + is Int whereas its expected type is BigInt, so an implicit conversion is looked up in the implicit scope of Int => BigInt, which includes BigInt’s companion object. So far so good. Now, I am looking for where in the specification is the following allowed:

val c = 1 + a

In the above reference we have:

2. In a selection e.m with e of type T, if the selector m does not denote an accessible member of T. In this case, a view v which is applicable to e and whose result contains an accessible member named m is searched. The search proceeds as in the case of implicit parameters, where the implicit scope is the one of T. If such a view is found, the selection e.m is converted to v(e).m.
3. In an application e.m(args) with e of type T, if the selector m denotes some accessible member(s) of T, but none of these members is applicable to the arguments args. In this case, a view v which is applicable to e and whose result contains a method m which is applicable to args is searched. The search proceeds as in the case of implicit parameters, where the implicit scope is the one of T. If such a view is found, the application e.m(args) is converted to v(e).m(args)

, but I cannot quite make the link with the conversion method above in terms of implicit scope, if someone has an idea…

[soronpo]

@rjolly

, but I cannot quite make the link with the conversion method above in terms of implicit scope, if someone has an idea…

It’s not the spec. There is probably an implicit class on Int that supports + with a BigInt.

[Jasper-M]

The arguments of the method also contribute to the implicit scope, but I don’t know where that’s specified.

scala> case class MyInt(i: Int) { def +(other: MyInt) = MyInt(i + other.i) }
     | object MyInt { implicit def int2MyInt(i: Int): MyInt = MyInt(i) }
class MyInt
object MyInt

scala> 4 + MyInt(5)
val res2: MyInt = MyInt(9)

scala> 4 + MyInt(5) // print
MyInt.int2MyInt(4).+(MyInt.apply(5)) // : MyInt

[som-snytt]

It’s a typo in the section on views.

In the first case, it’s searching for a conversion S => T (using the letters from the introductory paragraph). The text says “the implicit scope is the one of T => pt”.

In the second case, for a conversion that adds a named member, it says “the implicit scope is the one of T”, since the expected type { def m: ? } doesn’t add any information.

The typo is that the third case should say “the one of T => pt” again.

The expected type is { def m(x: X): ? } and so on.

The description of “parts” in 7.2 says:

if T denotes an implicit conversion to a type with a method with argument types T1,…,Tn​ and result type U, the union of the parts of T1,…,Tn and U;

This is the case that covers.

-Vtyper is a bit unwieldy in REPL, but it shows that first it will try to convert the operand to something that Int has a + method for. Failing that, it tries to convert the receiver Int to something that has a + method that takes a BigInt, and BigInt is a part of the type that contributes to implicit scope.

scala> 42 + BigInt(27)
[search 1] start `<?>`, searching for adaptation to pt=scala.math.BigInt => Double

[search 17] start `42`, searching for adaptation to pt=Int(42) => ?{def +(x$1: ? >: scala.math.BigInt): ?}

This explanation seems reasonable, so I hope it’s correct.

[rjolly]

Thank you so much. I created a pull request to improve the documentation.

[rjolly]

It leads me to the second part of my issue. In the “proposed changes” thread above, the distinction is made between several patterns, among which is a enrichment pattern, now managed by extension methods, and a promotion (aka magnet) pattern, which will remain but restricted to a declarative basis with the into keyword. Coming back to the BigInt example, numeric promotion will have to be explicitly allowed in operator methods:

  def +(that: into BigInt): BigInt = ???

But Scala 3 implicits improvement allows us to go further. Instead of a wrapper class, we could use a Numeric typeclass instance for java.math.BigInteger so as to enrich it with arithmeric operators as suggested in this thread. This could be a change of the standard library, once it is available again for updates. But the problem is with the interaction of enrichment and promotion. As seen above, the implicit conversion from Int to BigInt is found in BigInts implicit scope. But if instead we take BigInteger with a typeclass enrichment, then there is no more implicit scope where to look for the conversion. This is a very concrete issue I am facing in my computer algebra project where I can easily have numeric promotion for operands on the right but not on the left:

val a = BigInteger("1") + 1 // works
val b = 1 + BigInteger("1") // no way

I would be very happy to find a solution to this problem.

[Sporarum]

I am not sure I understand why the following does not work for you:

extension (this: Int)
  def + (that: BigInt): BigInt

In particular, did you know the following works ?
(Very useful but surprising)

trait Showable[T]:
  extension (x: T)
    def show(): String

def foo(x: Int)(using Showable[Int]) =
  x.show() // looks for show as extension in givens

[rjolly]

Well, in the long run as more algebraic structures are introduced it becomes impractical to define what each operator is supposed to do with Int (or whatever the type you want to promote from, there can be several like polynomial coefficient and so on). It is better to define a promotion from Int to each algebraic structure and stick to the basic definition when it comes to operators:

extension (this: into BigInteger)
  def + (that: into BigInteger): BigInteger

And yes instead of implicit conversions we can use context bounds, this is how my library is currently devised with such setting as:

type Conversion[T] = [X] =>> X => T
extension [U](x: U)
  def unary_~[T](using c: U => T) = c(x)
extension[U: Conversion[T]](x: U)
  def + [V: Conversion[T]](y: V) = (~x).add(~y)

, but it has its own caveats. Notice I first thought into would be some kind of syntactic sugar for the above, but it is not. In fact into is the exact same mechanism as in old implicit conversions and has different operation than the context bound approach.

[rjolly]

In fact, numeric promotion on the left works if we explicitly import the operator:

import java.math.BigInteger
import scala.language.implicitConversions

given Conversion[Int, BigInteger] = BigInteger.valueOf(_)

trait Numeric[T]:
  extension (x: T) def + (y: T): T

given r: Numeric[BigInteger] with
  extension (x: BigInteger) def + (y: BigInteger) = x.add(y)

import r.*

1 + BigInteger("1")

Would it be hard to remove this constraint?

[soronpo]

@rjolly

Would it be hard to remove this constraint?

But you don’t “own” either Int or BigInteger.
It opens up a can of worms.

[rjolly]

Not sure what you mean. Note that extension methods in a typeclass instance are already brought automatically into scope, the issue here is only with respect to implicit conversion, and on the left specifically. On the right there is no need to import:

given Conversion[Int, BigInteger] = BigInteger.valueOf(_)

given r: Numeric[BigInteger] with
  extension (x: BigInteger) def + (y: BigInteger) = x.add(y)

BigInteger("1") + 1 // works

In addition and to solve the above problem of no more implicit scope being available in the typeclass instance setting, what we could do is also bring into scope all implicits in a given instance including implicit conversions. The code above would then read:

given r: Numeric[BigInteger] with
  given Conversion[Int, BigInteger] = BigInteger.valueOf(_)
  extension (x: BigInteger) def + (y: BigInteger) = x.add(y)

BigInteger("1") + 1
1 + BigInteger("1")

Currently we have to import as so:

import r.{given, *}

[rjolly]

Where the can of worms can occur is if several different instances are in scope concurrently:

case class MyInt1(n: Int)
case class MyInt2(n: Int)

given r: Numeric[MyInt1] with
  given Conversion[Int, MyInt1] = MyInt1(_)
  extension (x: MyInt1) def + (y: MyInt1) = MyInt1(x.n + y.n)

given s: Numeric[MyInt2] with
  given Conversion[Int, MyInt2] = MyInt2(_)
  extension (x: MyInt2) def + (y: MyInt2) = MyInt2(x.n + y.n)

import r.{given, *}
import s.{given, *}

MyInt1(1) + 1 // ok
MyInt2(1) + 1 // ok
1 + MyInt1(1) // None of the overloaded alternatives of method + in class Int with types ... match arguments (MyInt1)
1 + MyInt2(1) // None of the overloaded alternatives of method + in class Int with types ... match arguments (MyInt2)

, so I imagine this problem should be addressed as well (and prior).

[rjolly]

Whe have a hint of what is wrong if we substitute a operator that is not already part of type Int:

1 ++ MyInt1(1)
^^^^
value ++ is not a member of Int.
An extension method was tried, but could not be fully constructed:

    s.++(s.given_Conversion_Int_MyInt2.apply(1))

    failed with:

        Ambiguous extension methods:
        both s.++(s.given_Conversion_Int_MyInt2.apply(1))
        and  r.++(r.given_Conversion_Int_MyInt1.apply(1))
        are possible expansions of 1.++

The extension method resolution does not try hard enough and fails to see that one of the possible solutions is working better than the other.

[spamegg1]

@rjolly

The extension method resolution does not try hard enough and fails to see that one of the possible solutions is working better than the other.

I believe this is a deliberate design decision as a change from Scala 2 to 3. In Scala 3 they preferred to make the compiler throw an error, and require us to resolve the ambiguity.

I’ve never used Scala 2 implicits but I’ve read that when one was picked by the compiler over another, it led to some very hard-to-debug issues.

You might want to read Chapter 21.7 of “Programming in Scala 5th Edition” called “When multiple givens apply”. It says that the compiler can pick one, if one is more specific than the other. For example, if you had Numeric[MyInt1] <: Numeric[MyInt2] then the compiler would be able to pick one.

Here is an excerpt:

If one of the available givens is strictly more specific than the others, however, then the compiler will choose the more specific one. The idea is that whenever there is a reason to believe a programmer would always choose one of the givens over the others, don’t require the programmer to write it explicitly. After all, method overloading has the same relaxation.
Continuing the previous example, if one of the available foo methods takes a String while the other takes an Any, then choose the String version. It’s clearly more specific.
To be more precise, one given is more specific than another if one of the following applies:
• The type of the former is a subtype of the latter’s.
• The enclosing class of the former extends the enclosing class of the latter.
If you have two givens that could be ambiguous, but for which there is an obvious first and second choice, you can place the second choice in a “LowPriority” trait and the first choice in a subclass or sub-object of that trait. The first choice will be taken by the compiler if it is applicable, even if the lower priority choice would otherwise be ambiguous. If the higher priority given is not applicable, but the lower priority given is, the compiler will use the lower priority given.

I follow this advice and put one of the givens inside an object.

[rjolly]

Yes, currently a possible solution is to establish a hierarchy between types. Most of the time in my use case I need to promote from Int to some coefficient type C and then to Polynomial[C]. If I only import the operator of the latter then I have a working solution:

import scala.language.implicitConversions
import java.math.BigInteger

trait Numeric[T]:
  extension (x: T) def + (y: T): T

given identity[T]: Conversion[T, T] = scala.Predef.identity

given r: Numeric[BigInteger] with
  given Conversion[Int, BigInteger] = BigInteger.valueOf(_)
  extension (x: BigInteger) def + (y: BigInteger) = x.add(y)

case class Poly[C](n: C)

trait PolyRing[C](using ring: Numeric[C]) extends Numeric[Poly[C]]:
  given [D](using Conversion[D, C]): Conversion[D, Poly[C]] = x => Poly(x)
  extension (x: Poly[C]) def + (y: Poly[C]) =
    import ring.*
    Poly(x.n + y.n)

given s: PolyRing[BigInteger] with {}

import r.{given}    // do not import this operator
import s.{given, *} // import this one

// everything is lifted to the top ring

BigInteger("1") + 1
1 + BigInteger("1")
Poly(BigInteger("1")) + BigInteger("1")
BigInteger("1") + Poly(BigInteger("1"))
Poly(BigInteger("1")) + 1
1 + Poly(BigInteger("1"))

I would clearly prefer to be able to import both (or better have it done automatically) and have the compiler trying harder to find the right method.

[rjolly]

I could eventually live with importing operators, except that * is recently changed to mean wilcard import in place of _, so that I could no more import just multiply if ever wanted to.

[som-snytt]

you can

import x.`*`

That was an old issue, I assume it isn’t broken syntax.

[rjolly]

Yes, it works. Unfortunately.

[rjolly]

So, I suppose no time/energy is going to be invested in this subject since implicit conversions are going to be deprecated. However, I would like to stress that the exact same effect can be obtained without implicit conversions using the context bounds approach I mentioned earlier. Here is the previous test rewritten in the corresponding terms:

import java.math.BigInteger

type Conversion[T] = [X] =>> X => T
extension [U](x: U)
  def unary_~[T](using c: U => T) = c(x)

trait Numeric[T]:
  extension (x: T)
    def add(y: T): T
  extension[U: Conversion[T]](x: U)
    def + [V: Conversion[T]](y: V) = (~x).add(~y)

given r: Numeric[BigInteger] with
  given (Int => BigInteger) = BigInteger.valueOf(_)
  extension (x: BigInteger) def add(y: BigInteger) = x.add(y)

case class Poly[C](n: C)

trait PolyRing[C](using ring: Numeric[C]) extends Numeric[Poly[C]]:
  given [D: Conversion[C]]: (D => Poly[C]) = x => Poly(~x)
  extension (x: Poly[C]) def add(y: Poly[C]) =
    import ring.*
    Poly(x.n + y.n)

given s: PolyRing[BigInteger] with {}

import r.{given}    // How do we
import s.{given, *} // get rid of these?

BigInteger("1") + 1
1 + BigInteger("1")
Poly(BigInteger("1")) + BigInteger("1")
BigInteger("1") + Poly(BigInteger("1"))
Poly(BigInteger("1")) + 1
1 + Poly(BigInteger("1"))

Improving implicit resolution in this broader sense could only benefit the rest of the community. I am considering submitting it as a GSOC project, with such title as “implicit resolution : trying harder” or “taming the can of worms”. I would be happy to (co-)mentoring it albeit I do not have by far the compiler expertise needed (I would not even know where to look…).

[Edit] I think one of the problems might be the interaction with type inference. Hence changing implicit resolution is likely to entail a complete overhaul of the typer. But while the latter is adequately described in the literature, I do not think there is a equivalent description of implicit resolution algorithms anywhere. That might be a first step to take.

[odersky]

I think implicit conversions from Int and Long to Bigint as we have now are OK. In the future, to avoid implicit conversion on use warnings, they can be explicitly allowed with into, like this:

import language.experimental.into

class BigInt(x: Int):
  // Standard operators on Bigint. 
  // These allow conversion of their right argument
  def + (other: into BigInt): BigInt = ???
  def * (other: into BigInt): BigInt = ???

object BigInt:
  given Conversion[Int, BigInt] = BigInt(_)
  
  // Extension methods on `into BigInt`. 
  // These allow conversions of their left argument
  extension (x: into BigInt)
    def + (other: BigInt): BigInt = ???
    def * (other: BigInt): BigInt = ???

@main def Test =
  val x = BigInt(2)
  val y = 3
  val a1 = x + y // uses conversion on `y`
  val a2 = y * x // uses conversion on `y`
  val a3 = x * x
  val a4 = y + y