Updated Proposal: Revisiting Implicits

Scala Improvement Process
343

Martin, again this may be an annoying digression for some people on the Revisiting Implicits thread, and anything I say about type classes is probably wrong, as I really don’t understand them. I’m still struggling. But the few times I’ve implemented one (with help of experts) it reminds me meta-programming in Lisp.

To me it seems a type class is a mechanism for specifying that a certain set of types need to behave a certain way. I.e., extend the behaviour of a set of classes. In CLOS I’d extend the behaviour of a set, X, of classes by defining a meta class, M, which implements that behaviour, and arranging that each of the classes in X designate M as its meta class.

For example, normally instance slot access is done through some sort of array look-up which is predicted at compile time. However, if I want slot-access of class C to always read/write from a persistant database, I’d implement the behaviour in a meta class it as C’s meta class. For example, I’d override the get-slot-value and set-slot-value methods in the meta class.

Another example is if don’t like the order of the default CLOS class precedence list which (unlike Scala) does not allow two parent classes to inherit from the same grand-parent classes in conflicting orders. I could implement this by providing a new meta-class where I overriding the compute-class-precedence method.

In Scala, a limitation (motivated by its Java heritage) is that I cannot add methods to classes I don’t own. So to get around this limitation, I need to implement a type class which effectively intervenes in the method dispatch procedure and trampolines the method call to some other class which I do own. In CLOS this method dispatch procedure is partially predicted at compile time, and refined at run-time. In Scala, the dispatch procedure is 100% baked in at compile time (as I understand).

344

Looks better than the 0.22 planned until now! using reads much nicer than with too

One problem that was not voiced yet is this:

given [T] with Ord[T] as Ord[List[T]]

I asked about this 2 days ago. Still wondering if

given listOrd[T] as Ord[List[T]] (using Ord[T]){ ... }

or the current => syntax would be better, but what’s in your PR looks acceptable/good enough.

On the other hand…

given [T: Ordering] as Ordering[Tree]

is still pretty unreadable/confusing to me, both to me personally and imagining having to explain it to someone. Not a fan of as for this reason.

345

As for restrictions on typeclass coherence:
Rust has recently relaxed the orphan rule. They argue that the orphan rule forces one type to be aware of another. The newtype workaround is deemed cumbersome or impossible to use.

Announcing Rust 1.41.0 | Rust Blog

In Rust 1.40.0 this impl was forbidden by the orphan rule, as both From and Vec are defined in the standard library, which is foreign to the current crate. There were ways to work around the limitation, such as the newtype pattern, but they were often cumbersome or even impossible in some cases.

2451-re-rebalancing-coherence - The Rust RFC Book

Unless we expand the orphan rules, use cases like this one will never be possible, and a crate like Diesel will never be able to be designed in a completely extensible fashion.

Probably it doesn’t make sense to invent a syntax that prohibits orphans given the inconvenience of that restriction.

1 Like
346

I wouldn’t say that keyword name is in any way definitive. Rust’s traits are in fact typeclasses from FP. Scala’s traits are pimped up OOP interfaces. Apple Swift has protocols which are a variation of typeclasses.

Haskell’s class is a type class. Those names are used interchangeably in official documentation, see: A Gentle Introduction to Haskell: Classes

1 Like
347

I see. Yes, there are some overlapping use cases. But the mechanisms to achieve them are quite different.

1 Like
348

Type classes are not just about adding behavior to third-party types; that would be the strategy pattern in its most simplistic form:

def parseJson[A](json: String, formatter: JsonFormatter[A]): A = ???
object HouseJsonFormatter extends JsonFormatter[House] { ... }
val house = parseJson("...", HouseJsonFormatter)

Type classes improve this pattern by allowing the instances of the generic strategy interface to be inferred “automatically”, by the mere action of including a reference (say, import) to the definition site of the instance.

The automatic inference is expected to take place only when the type class is required / bound. When it is not bound, for instance, in this example:

trait SemiGroup[A] {
  def (x: A)|+|(y: A): A
}

object SemiGroup {
  given additive: SemiGroup[Int] {
    def (a: Int)|+|(b: Int) = a + b 
  }
}

object Example {
  import SemiGroup.given
  def main(args: Array[String]) = println(5 |+| 2)
}

then it is not a type class, but merely an extension implementing an interface (which is not even necessary).

There are two differences between type classes and extensions, which help understand the purpose of type classes:

  1. Extensions need not implement an interface.
  2. Extensions can be used without a bound interface; all they need is to be referenced in the current scope.

Type classes are intended to express the need of a certain abstract behavior via their bound interface, while extensions are merely a syntactic sugar for global / static functions.

In fact, type classes sound a lot like policy-based design, which I’m not too familiar with, but according to the wikipedia definition – “It has been described as a compile-time variant of the strategy pattern” – they seem very similar.

349

I spent some time attempting to convert the typeclasses in my project to the extension method style you suggested and I found the cases which caused the trouble.

The issue is that typeclasses like Monoid work really well with the style you’re recommending because they only have one type, and all methods are infix.

That style doesn’t work for typeclasses which involve multiple types (like Convertible), or have a postfix method that requires a type parameter (like Monad).

Interestingly, while a simplified version of the Monad definition in the “Implementing Typeclasses” docs did compile, the call site couldn’t resolve the extension method without an ops class. As the docs only show the definition, but no example of use, my guess is this is why it slipped through whatever tests you may have to ensure the docs compile.

So yes, there is currently boilerplate, and an import tax.

I’d prefer to minimize the boilerplate where feasible, and understand that it isn’t always going to be doable.

I’m fine with the import tax on syntax, managing the instances has always been the bigger headache.

I’m decidedly less fine with being told the import tax doesn’t exist when it’s fairly easy to show that it does.

Full example follows:

trait Convertible[A,B] {
  def (a: A) cast: B
}

object Convertible {
  def apply[A,B](given C: Convertible[A,B]): Convertible[A,B] = C

  given Convertible[Int, String] {
    def (a: Int) cast: String = s"<$a>"
  }
  
  object ops {
    given ops[A]: AnyRef {
      def[B](a: A) cast (given C: Convertible[A,B]): B = C.cast(a)
    }
  }
}

trait Monad[F[_]] {
  def [A, B](x: F[A]) bind(f: A => F[B]): F[B]
  def [A, B](x: F[A]) fmap(f: A => B): F[B] = x.bind(f `andThen` pure)

  def[A](x: A) pure: F[A]
}
object Monad {
  def apply[F[_]](given M: Monad[F]): Monad[F] = M
  
  given Monad[List] {
    def [A, B](xs: List[A]) bind(f: A => List[B]): List[B] = xs.flatMap(f)
    def[A](x: A) pure: List[A] = x :: Nil
  }
  object ops {
    given lifts[A]: AnyRef {
      def[F[_]] (a: A) pure (given M: Monad[F]): F[A] = M.pure(a)
    }
    given syntax[F[_], A]: AnyRef {
      def[B](fa: F[A]) fmap (f: A => B)(given M: Monad[F]): F[B] = M.fmap[A,B](fa)(f)
      def[B](fa: F[A]) bind (f: A => F[B])(given M: Monad[F]): F[B] = M.bind[A,B](fa)(f)
    }
  }
}

object Test extends App {
  def labeled(label: String, result: Any): Unit = {
    println(s"$label: $result")
  }
  {
    println("No Imports")
    println("----------")
    
    labeled("Direct call (Convertible)", Convertible[Int,String].cast(5))
    labeled("Direct call (Monad)", Monad[List].pure(5))
    
    labeled(
      "Call with type parameter",
      "error message is 'value cast is not a member of Int - did you mean (5 : Int).+?'"
      //5.cast[String]
    )
    labeled(
      "Postfix call",
      "error message is 'value pure is not a member of Int - did you mean (5 : Int).+?'"
      //5.pure[List]
    )
    labeled(
      "Infix call",
      "error message is 'value fmap is not a member of List[Int] - did you mean List[Int].map?'"
      //List(4).fmap(_.toString).bind(x => List(x, x))
    )
  }
  
  println(". ")
  
  {
    println("Extra Imports")
    println("-------------")
    import Convertible.ops.given
    import Monad.ops.given
    
    labeled("Call with type parameter", 5.cast[String])
    labeled("Postfix call", 5.pure[List])
    labeled(
      "Infix call",
      List(4).fmap(_.toString).bind(x => List(x, x))
    )
  }
}

Live Version on Scastie

350

Thanks for the examples. It seems that this was overlooked in the current language design: when the extension method comes from an instance not defined in the companion of the type of the object on which we call the method.

As far as I understand, you could avoid defining ops methods and just do:

object Convertible {
  def apply[A,B](given C: Convertible[A,B]): Convertible[A,B] = C

  given C: Convertible[Int, String] {
    def (a: Int) cast: String = s"<$a>"
  }
  
}

...

import Convertible.given
5.cast[String]

But it does not currently work.

It’s also possibly inferior to using proper syntax imports, as the error one gets if some instances have not been imported are of the kind "not a member of T" instead of the more useful “no instance of MyClass[T] in scope”.

So maybe some simulacrum-style code gen could still be useful in addition to the existing mechanisms.

351

I think there are indeed some potential issues about when extension methods are in scope and when they aren’t. But the issue here is that there is no parameterized cast method.

The following does work (https://scastie.scala-lang.org/9Q4UB9WDT7WPJ1StfwfGoA)

import Convertible.given
val x: String = 5.cast
1 Like
352

I’m not sure what you refer to as “import tax”. Is it because you have to import ops? You could just get rid of the ops objects and place the extensions (ops, lifts, syntax) directly inside the companion objects of the type classes:

trait Convertible[A,B] {
  def (a: A) cast: B
}

object Convertible {
  def apply[A,B](given C: Convertible[A,B]): Convertible[A,B] = C

  given Convertible[Int, String] {
    def (a: Int) cast: String = s"<$a>"
  }
  
  given ops[A]: AnyRef {
    def[B](a: A) cast (given C: Convertible[A,B]): B = C.cast(a)
  }
}

object Test extends App {
  import Convertible.given
  val s1 = 1.cast[String]
  val s2: String = 2.cast
}

This is the same as @Jasper-M 's xample.

353

IMHO: It is a usual point of puzzlement in a case where such imports cannot be done globally.

It is very often when companion objects of type classes are just not available for modification.
That is why I think scala should have some sort of scope injection.

1 Like
354

You mean something like this?

object external {
  trait Convertible[A,B] {
    def (a: A) cast: B
  }

  object Convertible {
    def apply[A,B](given C: Convertible[A,B]): Convertible[A,B] = C

    given Convertible[Int, String] {
      def (a: Int) cast: String = s"<$a>"
    }
  }
}

object ConvertibleOps {
  import external.Convertible

  given ops[A]: AnyRef {
    def[B](a: A) cast (given C: Convertible[A,B]): B = C.cast(a)
  }
}

object Test extends App {
  import ConvertibleOps.given
  
  val s1 = 1.cast[String]
  val s2: String = 2.cast
}

This actually seem to work, even though I didn’t expect the type instance to be propagated from the scope of ConvertibleOps to the one of Test.

355

Nevertheless I will follow martin’s advice, and will avoid such templates if it is possible.

356

This is not the surprising part and not what’s going on here. Try this instead:

object Test extends App {
  import ConvertibleOps.given
  // error - "Not found: type Convertible"
  type X = Convertible
}

Which is not different than how implicits work nowadays:

object external {
  trait Convertible[A,B] {
    def cast(a: A): B
  }

  object Convertible {
    implicit object IntToString extends Convertible[Int, String] {
      def cast(a: Int): String = s"<$a>"
    }
  }
}

object ConvertibleOps {
  import external.Convertible

  implicit class Ops[A](a: A) {
    def cast[B]()(implicit c: Convertible[A,B]): B = c.cast(a)
  }
}

object Test extends App {
  import ConvertibleOps
  
  // compiles
  val s1 = 1.cast[String]
  val s2: String = 2.cast

  // doesn't
  type X = Convertible
  val x = IntToString
}

Which is one of the reasons why implicits are confusing. They do not only get applied in the local scope upon import – a name resolution mechanism – but are being propagated between scopes, unlike names.

357

I have compiled it in dottyVersion “0.21.0-RC1”
(Original source code just cannot be compiled it seems it is misprint )
It can be compiled with

import ConvertibleOps.given

or

import ConvertibleOps._

Actually I do not understand why implicit conversion can be imported via simple import or via given import. It seems unlogical.
It is a big surprise for me that

import ConvertibleOps._

can also be compiled.

358

I really don’t know why my code does not without an expected type, and works with one. The available implicit instances are not ambiguous AFAICT (ping @smarter).

359

That’s the current Scala 2 syntax, which (in this scenario) is equivalent to Dotty’s import COps.given.

The following actually behaves in a non-surprising way (Scala 2);

object a {
  implicit val x = 1
}

object b {
  import a._
  def foo()(implicit i: Int) = i
  def bar() = foo()
}

object c {
  b.foo() // doesn't compile
  b.bar() // compiles
}

Yet this behaves surprisingly:

object a {
  trait TypeClass[A] {
    def foo(): String
  }
  object TypeClass {
    implicit object IntTC extends TypeClass[Int] { def foo(): String = "int" }
  }
}

object b {
  import a._
  def foo[A](a: A)(implicit tc: TypeClass[A]) = tc.foo()
  def bar() = foo(1)
}

object c {
  b.foo(42) // compiles (surprising)
  b.bar() // compiles
}
360

If you believe you’ve found an issue in the implementation, please report it on github.com/lampepfl/dotty/issues, it’s impossible to keep track of these things properly in a thread like this.

3 Likes
361

What are you referring to? The “surprising” behavior discussed above is the same as with the old implicits, so I’m assuming it’s intentional.

362

I’m talking in general, I don’t have time right now to look into details at all the code samples flying around above.

2 Likes