Dynamic dispatch of type classes

[John Nilsson]

I've been thinking that the type class feature has a major flaw: static dispatch. Especially when combined with type inference you are entirely left to the whims of the compiler as to what actually gets executed at runtime.

Example:

  class A
  class B extends A
 
  implicit def a(a: A): String = "a"
  implicit def b(b: B): String = "b"
 
  (new B): String    //> res0: String = b
  (new B: A): String //> res1: String = a

Would it be an improvement to alter the semantics of the language so that the last line would evaluate to "b" instead?

What would it take? Would it be enough to define the rules for how the dynamic dispatch is evaluated? Would you have to provide some rules regarding how and when overriding occurs?

BR,
John

[Simon Schäfer]

What you ask doesn't make sense for me. type classes as well as
implicit conversions are inserted at compile time - the compiler
doesn't know what concrete types are there at runtime.

For example

def f(x: A): String = x

is compiled to

def f(x: A): String = a(x)

The compiler must use an implicit conversion for A and not for B even
when only Bs are passed at runtime to f. The compiler never has the
guarantee that this is the case. When you know this is the case than
use (new B): String instead of (new B: A): String.

[John Nilsson]

Yes, and my suggestion is that instead of inserting a direct dispatch to a it instead inserts a dispatch to a lookup call

def f(x: A): String = x match {
  case x: A => a(x)
  case x: B => b(x)
}

BR,
John

[Simon Schäfer]

Such a thing looks dangerous to me. For example a user finds an
implicit conversion in a library and wants to use it. The user does an
import all, but this also imports several other implicit conversions.
The user now wonders why the code does not do what he want because a
different conversion is chosen.

On the other hand it is not difficult to build such a dynamic dispatch
by your own with help of pattern matching, as you already showed in
your example.

[John Nilsson]

I would say it is no more dangerous than overridden methods in a class hiearchy. The same design consideration wrt LSP applies.

Assuming LSP is respected I would even argue that the danger you describe is exactly the problem with static dispatch. Depending on which type an object is currently viewed as you could get wildly different performance characteristics. For example say you would implement foreach as a type class.

Maybe its simple to construct your own dynamic dispatch but is this a feasible approach if you intend to benefit from the effect on the expression problem a type class design has?

Also, if it were the default for the language there could be optimizations applied thorough invokedynamic or such that would be harder to achieve otherwise.

BR,
John

[Simon Schäfer]

I came up with another point:

For me, pattern matching expresses that I wanna use a dynamic dispatch.
On the other hand, when I use type classes I want to express that a
static dispatch is used and less runtime overhead is used.

Though I agree that type classes come with some overhead in the amount
of source code one has to write, I'm not sure if I wanna have dynamic
dispatch built into a concept developed for static type systems.

[John Nilsson]

I'm thinking that invokedynamic or some other cleverness would address the issue of overhead. That coupled with the possibility to provide specialized type class instances on the dynamic type would rather create a performance benefit than a performance cost.

As for concepts developed for static type systems it is my understanding that Scala is somewhat of an experiment in how subtype polymorphisms can improve upon typically functional features. So this is in my mind a natural extension to that experiment.

It is MHO that there should be no difference in semantics based on the difference between the static and the dynamic type of objects. It's just a source of confusion.


There's another benefit from dynamic dispatch in this case too. If we see type classes as a solution to the expression problem then we should not be forced to depend on a specialized subtype to provide specialized implementations of operations it just forces unnecessary coupling.

BR,
John

[Paul Phillips]

On Sun, Nov 25, 2012 at 10:32 AM, John Nilsson <jo...@milsson.nu> wrote:

It is MHO that there should be no difference in semantics based on the difference between the static and the dynamic type of objects. It's just a source of confusion.

Yeah, that would be nice, but since evaluation strategy at least is dynamic (is that a Stream or a List you're calling map on?) and since side effects aren't going away anytime soon, we are a ways from "no difference in semantics".

scala> def f[T, CC[T] <: Traversable[T]](xs: CC[T]) = xs map { x => println(x) ; x }

warning: there were 1 feature warnings; re-run with -feature for details

f: [T, CC[T] <: Traversable[T]](xs: CC[T])Traversable[T]

scala> f(1 to 10 toList)

warning: there were 1 feature warnings; re-run with -feature for details

1

2

3

4

5

6

7

8

9

10

res0: Traversable[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> f(1 to 10 toStream)

warning: there were 1 feature warnings; re-run with -feature for details

1

res1: Traversable[Int] = Stream(1, ?)

[John Nilsson]

Ah, maybe I expressed that a bit unclear. I do think the dynamic type of an object can, and should, determine semantics (respecting LSP as appropriate)

What I meant was that the difference between the static type, and the dynamic type, should have no impact on the semantics, only on provability.

That is, given some B <: A and an o of type B
(o: B).m should behave exactly the same as (o: A).m
(assuming it compiles at all...)

BR,
John

[Erik Osheim]

On Sun, Nov 25, 2012 at 02:49:09PM +0100, John Nilsson wrote:
> class A
> class B extends A
>
> implicit def a(a: A): String = "a"
> implicit def b(b: B): String = "b"
>
> (new B): String //> res0: String = b
> (new B: A): String //> res1: String = a

Call me crazy, but I think the canonical way to do what you want is:

class A { def s = "a" }
class B extends A { override def s = "b" }
implicit def as(a: A): String = a.s
(new A): String // String = a
(new B): String // String = b
(new B:A): String // String = b

I think this kind of polymorphism is best addressed through inheritance
and overriding than via the type system itself.

-- Erik

[John Nilsson]

I'm prepared to accept that conclusion

My argument against it is that type classes are better for extensibility, given how they address the expression problem. I'm thus entertaining the thought that maybe the next evolution in OOP is to drop methods entierly as a feature.

BR,
John

[Paul Phillips]

On Sun, Nov 25, 2012 at 12:04 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:

I think this kind of polymorphism is best addressed through inheritance
and overriding than via the type system itself.

It does introduce a significant divide between the execution of extension methods and the execution of inherited ones, as I was reminded of with Function1 when I tried to move tupled and curried into extension methods and broke code which depends on overriding them, since it would no longer be called if the static type of the receiver was Function1.

Both dynamic and static method dispatch have their uses; behavior refinement via overriding (dynamic dispatch) and "being more specific" (static dispatch) both have their uses; the challenge is in the number of axes upon which these elements interact and compete with one another and with a dozen related things (implicit selection, overloading, type inference, variance and the definition of specificity, etc. etc. etc.) Even if there's no better reason for it than historical accident (not saying there isn't) type classes as realized in scala are pretty well tied to static types (as are macros, something which will loom larger in the future) and I imagine both will remain that way.

[John Nilsson]

How do you mean that static dispatch (in "being more specific") differs from dynamic dispatch?

I do suspect that legacy reasons will make this discussion moot. But since it is scala "debate" I thought it would be fun to at least investigate the possibility and consequences.

I also did think of macros as another area where static types rule. Not really on-topic for this thread. But maybe even macros could be thought of as having "dynamic" semantics in some sense. It could even be easier to realize, as there wouldn't be the issue of runtime class loading to consider.

BR,
John

[Paul Phillips]

On Sun, Nov 25, 2012 at 12:50 PM, John Nilsson <jo...@milsson.nu> wrote:

How do you mean that static dispatch (in "being more specific") differs from dynamic dispatch?

Overriding takes the overridden out of the game, except to the extent that you willingly keep them in there via super. If C <: B <: A, then the override in C will always be called if it's a C, regardless of the static type. If each of C, B, A add a more specific alternative for static dispatch, then any of them might be called. I think you know all this, so maybe I misunderstand the question. In any case here is some code to make it explicit for anyone else who may care:

class A {

  def dingus = "A"

}

class B extends A {

  override def dingus = "B"

}

trait Imp {

  implicit class I1(val x: A) {

    def bippy = ("I1", x.dingus)

  }

  implicit class I2(val x: B) {

    def bippy = ("I2", x.dingus)

  }

}

object Test extends App with Imp {

  val b = new B

  println((b: A).bippy)  // (I1,B)

  println((b: B).bippy)  // (I2,B)

}

[John Nilsson]

Maybe I just got stuck on the wording. Even in the case of overrides, the overridden method could be describe as "mote specific" in my mind.

So let me rephrase the question: When do you actually want the option to dispatch to a less specific implementation? In you example, given an instance of B why would you ever want to dispatch to I1 instead of I2?

BR,
John

[Paul Phillips]

On Sun, Nov 25, 2012 at 4:46 PM, John Nilsson <jo...@milsson.nu> wrote:

When do you actually want the option to dispatch to a less specific implementation?

The most prominent reason which comes to mind (I'm sure there will be others) is when you have a different definition of specificity than does the author of the logic for choosing the most specific.

  https://groups.google.com/d/msg/scala-language/ZE83TvSWpT4/el3-hNgzwv8J

tl;dr I consider an Ordering[SomeSuperSpecificType] to be "more specific" than an Ordering[Any] (assuming a contravariant Ordering, which we lack in large part because of the specificity rules) but implicit selection feels otherwise.

[John Nilsson]

Ah, there you go. Hadn't even considered variance issues. I'll have to see what can be done with it.

Quick thought, given dynamic dispatch I guess we would actually look for an Ordering[Left, Right] for each pair of values compared. If such a thing even makes sense...

BR,
John

[Geoff Reedy]

On Mon, Nov 26, 2012 at 02:40:38AM +0100, John Nilsson said

> Ah, there you go. Hadn't even considered variance issues. I'll have to see
> what can be done with it.

I'm late to the game, but you don't even have to get into variance, just
plain subtyping because there is not a total order for types. Consider

trait Base
trait Foo extends Base
trait Bar extends Base
class Baz extends Foo with Bar

implicit def base2string(x: Base) : String = "base"
implicit def foo2string(x: Foo) : String = "foo"
implicit def bar2string(x: Bar) : String = "bar"

val aBaz = new Baz

// prints "base", under your proposed dynamic dispatch what should it do?
println((aBaz : Base) : String)

[John Nilsson]

To keep with current semantics it should produce an ambiguity error, but at runtime. Unless Base is sealed, then you would get the error at compile time.

However I do think we can improve on that. What if we instead used the linearisation rules and treated the implicit defs like any other method override? Then it would print "bar"

[John Nilsson]

Thinking more of this issue I'm not sure I agree it is related to static vs dynamic dispatch. It seems orthogonal to me (ignoring type erasure for now).

In the discussion you linked to I think we agreed on how dispatching should work. I don't think the fundamental disagreement with Martin has to do with the definition of specificity as such, but rather about what role the type of the implicit argument plays in the algorithm.

By which I mean, if we fix implicit lookup I don't see why this won't work for the dynamic type too.

On Mon, Nov 26, 2012 at 1:59 AM, Paul Phillips <pa...@improving.org> wrote:

[John Nilsson]

Actually, is not the other way around entirely? Given the below example I think it is pretty clear that we want the implementation that can make the most assumptions about its input.

I'm more concerned with the covariant case. Should we not select the implementation that has the least constraints on what it produces?

  class Producer[+T](val s: String)
  class Consumer[-T](val s: String)
  class A
  class B extends A
 
  implicit val ca = new Consumer[A]("a")
  implicit val cb = new Consumer[B]("b")
  implicit val pa = new Producer[A]("a")
  implicit val pb = new Producer[B]("b")

  def consume[T:Consumer] = implicitly[Consumer[T]].s
  def produce[T:Producer] = implicitly[Producer[T]].s

  consume[A] //> res0: String = a
  consume[B] //> res1: String = a
 
  produce[A] //> res2: String = b
  produce[B] //> res3: String = b

[Paul Phillips]

On Wed, Dec 5, 2012 at 2:46 PM, John Nilsson <jo...@milsson.nu> wrote:

Actually, is not the other way around entirely? Given the below example I think it is pretty clear that we want the implementation that can make the most assumptions about its input.

I'm more concerned with the covariant case. Should we not select the implementation that has the least constraints on what it produces?

I think it only reinforces the hard-to-avoid conclusion that the right answer to "which is most specific?" depends on who is asking. But I am not sure why we would prefer to have the fewest constraints on what it produces; the more constraints there are (that is, the deeper the subclass) the more human logic is going into the selection.

I think extensibility is the key issue one should be addressing with specificity logic. One can construct an internally consistent idea of specificity which is not useful in practice by treating the system as one in which we control all the relationships. In real life the situation is that there are some existing classes and some existing implicits, and we would like to be able to define more classes and more implicits and see all of them integrated in some sensible way.

That is why the arrow of specificity should point at the deepest subclass, regardless of the variance. That is the only direction in which we can extend. Given M[-T] and an implicit instance of M[A], at present there is no way to create a new kind of A which will lead to a more specific M. It is as if we required you to achieve greater specificity via subclassing, and threw in the proviso that all classes are final.

scala> class Ord[-T](override val toString: String) { }

defined class Ord

// You've just made the world's most specific Ord! It's over, everyone can go home.

// This is the only Ord you will ever need.

scala> implicit val x = new Ord[Any]("Any")

x: Ord[Any] = Any

Or:

scala> object Boop {

     |   class Ord[-T](override val toString: String) { }

     |   implicit val x1 = new Ord[List[Int]]("List[Int]")

     |   implicit val x2 = new Ord[Seq[Int]]("Seq[Int]")

     |   implicit val x3 = new Ord[Traversable[Int]]("Traversable[Int]")

     |   implicit val x4 = new Ord[Traversable[Any]]("Traversable[Any]")

     | }

defined module Boop

scala> import Boop._

import Boop._

scala> implicitly[Ord[List[Int]]]

res0: Boop.Ord[List[Int]] = Traversable[Any]

scala> implicitly[Ord[Seq[Int]]]

res1: Boop.Ord[Seq[Int]] = Traversable[Any]

scala> implicitly[Ord[Traversable[Int]]]

res2: Boop.Ord[Traversable[Int]] = Traversable[Any]

[John Nilsson]

The type argument can be seen as our interface to the imported module. A contravariant argument represent what we commit to provide, the covariant what we expect in return.
So by committing as much as possible to the input and relax regarding the output we maximize the modules freedom to act while still providing what we need.
If I explicitly request a foo producer why would I want the one that can only produce bars? F.ex I might need a test case producer, in this case I want it to be free to produce all relevant cases, not only an arbitrary subset.

[Paul Phillips]

On Wed, Dec 5, 2012 at 10:36 PM, John Nilsson <jo...@milsson.nu> wrote:

If I explicitly request a foo producer why would I want the one that can only produce bars? F.ex I might need a test case producer, in this case I want it to be free to produce all relevant cases, not only an arbitrary subset.

This makes sense, and indeed mirrors the contravariant case.

In fact, it seems like we can cover all bases by reformulating prioritization, ignoring specificity for specificity's sake. Instead, start by trying for an exact match; then follow the variance arrow the minimum distance.

class A

class B extends A

class C extends B

class D extends C

class E extends D

class Con[-T](override val toString: String)

class Cov[+T](override val toString: String)

object ConTest {

  implicit val a = new Con[A]("Con[A]")

  implicit val c = new Con[C]("Con[C]")

  implicit val e = new Con[E]("Con[E]")

}

object CovTest {

  implicit val a = new Cov[A]("Cov[A]")

  implicit val c = new Cov[C]("Cov[C]")

  implicit val e = new Cov[E]("Cov[E]")

}

object Test {

  def f1() {

    import ConTest._

    println(List(

      implicitly[Con[A]],

      implicitly[Con[B]],

      implicitly[Con[C]],

      implicitly[Con[D]],

      implicitly[Con[E]]

    ) mkString " ")

  }

  def f2() {

    import CovTest._

    println(List(

      implicitly[Cov[A]],

      implicitly[Cov[B]],

      implicitly[Cov[C]],

      implicitly[Cov[D]],

      implicitly[Cov[E]]

    ) mkString " ")

  }

  def main(args: Array[String]): Unit = {

    f1()

    f2()

  }

}

/*** 

Currently:

Con[A] Con[A] Con[A] Con[A] Con[A]

Cov[E] Cov[E] Cov[E] Cov[E] Cov[E]

Hypothetically:

Con[A] Con[A] Con[C] Con[C] Con[E]

Cov[A] Cov[C] Cov[C] Cov[E] Cov[E]

***/

[Ryan Hendrickson]

Wow, I would love to see this get SIP'd. I like the direction of this much more than what I saw the last few times reforming implicit resolution with variance came up.

----------------------------------------

This message is intended exclusively for the individual(s) or entity to
which it is addressed. It may contain information that is proprietary,
privileged or confidential or otherwise legally exempt from disclosure.
If you are not the named addressee, you are not authorized to read,
print, retain, copy or disseminate this message or any part of it.
If you have received this message in error, please notify the sender
immediately by e-mail and delete all copies of the message.

[Paul Phillips]

On Thu, Dec 6, 2012 at 7:46 AM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

Wow, I would love to see this get SIP'd. I like the direction of this much more than what I saw the last few times reforming implicit resolution with variance came up.

I agree this is a big improvement. The key difference from what has been proposed before is that it treats contra- and co- variance symmetrically, removing the need to articulate "the contravariance exception." But the key similarity to what has been proposed before is that contravariance would behave in the desirable fashion.