A box for typeclasses

Design
1

My team has been trying to develop a subset of Scala that only uses typeclasses and no inheritance. Along the way, we have identified some relatively small changes to Scala (like wildcard context bounds) that e.g. Rust has and make life a lot better.

One thing that we have been struggling with is how to make a function that returns an object that implements a typeclass, but without a static guarantee of what that object will be. In Rust, one can return a Box<dyn Typeclass> and it is possible to call any method defined on Typeclass on the resulting pointer. I had hoped this would be possible with export in Scala 3, but that doesn’t quite work as hoped. I found something that gets pretty close to a nice interface that I wanted to share, both to let folks know that it’s possible, but also to ask if there’s anything even better I’m missing.

class BoxImpl[Self, Typeclass[_]](val self: Self)(using inst: Typeclass[Self]) {  
  inline def apply[U](f: Typeclass[Self] => Self => U): U = f(inst)(self)
  inline def apply[U, Arg](f: Typeclass[Self] => Self => Arg => U)(arg:Arg): U = f(inst)(self)(arg)
  inline def apply[U, Arg1, Arg2](f: Typeclass[Self] => Self => (Arg1, Arg2) => U)(arg1:Arg1, arg2: Arg2): U = f(inst)(self)(arg1, arg2)
  // ... for other arities as well
}

type Box[Typeclass[_]] = BoxImpl[_, Typeclass]
object Box {
  def apply[Self, Typeclass[_]](self: Self)(using Typeclass[Self]): Box[Typeclass] = BoxImpl(self)
  def unapply[Typeclass[_]](box: Box[Typeclass]): Some[Any] = Some(box.self)
}

with the above, it’s possible to write a method like

def branch(b: Boolean): Box[MyTypeclass] = {
  if (b) Box("4") else Box(3) // assuming given instances MyTypeclass for String and Int
}

and then do

val boxed = branch(true)
boxed(_.nullaryMethod)   // assuming extension (self: Self) def nullaryMethod: String on MyTypeclass
boxed(_. unaryMethod)(1) // assuming extension (self: Self) def unaryMethod(x: Int): String on MyTypeclass

You can also unbox using

boxed match {
  case Box("5") => ...
}

It’d be nice to have the compiler enforce that there exists an implementation of MyTypeclass for String in the pattern, but that’s not possible without some changes to type inference in patterns.

It’s nice, but it’d be even better if one could do boxed.nullaryMethod and boxed.nameOf(1). I am aware that one could manually write out extension methods using extension (Box[MyTypeclass]), but that was something I was specifically trying to avoid doing.

2

It’s a shame that this much simpler version of BoxImpl is not sufficient.

class BoxImpl[Self, Typeclass[_]](val self: Self)(using inst: Typeclass[Self]) {  
  inline def apply[U](f: Typeclass[Self] ?=> Self => U): U = f(self)
}
3

Right. I had tried that here and was very excited to see a context functions in action, but unfortunately extension methods are static dispatch.

4

I think I may have a found an encoding that works with context functions.

trait Box[Typeclass[_]]:
  type Self
  protected def self: Self
  protected def inst: Typeclass[Self]
  inline def apply[U](f: Typeclass[Self] ?=> Self => U): U = f(using inst)(self)


class BoxImpl[Self0, Typeclass[_]](val self: Self0)(using val inst: Typeclass[Self0]) extends Box[Typeclass]:
  type Self = Self0


object Box:
  def apply[Self, Typeclass[_]](self: Self)(using Typeclass[Self]): Box[Typeclass] = BoxImpl(self)
  def unapply[Typeclass[_]](box: Box[Typeclass]): Some[Any] = Some(box.self)

And then:

trait Foo[A]:
  extension (a: A) def foo(i: Int): Int

given Foo[Int] with
  extension (a: Int) def foo(i: Int): Int = a * i

given Foo[String] with
  extension (a: String) def foo(i: Int): Int = a.length * i

def branch(switch: Boolean): Box[Foo] =
  if switch then Box(4) else Box("foo")

val box: Box[Foo] = branch(true)

box(_.foo(5)) // 20
2 Likes
5

Huh, your solution is great, but branch(true)(_.foo(5)) fails with

Found:    Playground.Foo[Box_this.Self]
Required: Playground.Foo[?1.Self]

but it goes away if apply is not inline. Is that a bug?

1 Like
6

http://mark.hammons.fr/blog/containers-redux-2022-08-26.gmi

I think this may be relevant to your needs.

I have also developed a sister type called ContextProof that can bundle up proof of the existence of type classes for a type (useful for opaque types and such)

1 Like
7

It could be a bug. Probably some limitation or oversight in the inlining scheme.

1 Like
8

Why would one do that?

There is already Flix:

https://flix.dev/

This seems quite fishy.

Type-classes give you static dispatch.

If you can’t dispatch statically (because the static type of an object isn’t known) type-classes are just the wrong tool.

It has reasons why Rust added dynamic dispatch. You sometimes need it. Not everything can be done nicely with static dispatch. When you have the one but not the other your language is crippled.

Scala has already perfectly fine dynamic dispatch! It’s even the default. (Classes with inheritance, like C++)

The only thing is: Dynamic dispatch is clearly overrated. Languages have build-in support for it because it was once, as it was new, a big hype topic. But the truth is, you only need it seldom. Rust did quite good for a long time without having that feature build-in. (Because of course you can do it manually anytime, and build your v-tables by hand; so language support isn’t even strictly necessary; but convenient).

The problem is Scala copied “all the wrong defaults” (quoting here Brian Goetz)¹ from Java.

Dynamic features were fashionable back than so Java is actual a dynamic language—with some static types added on top (which leads to awful usability as everyone knows, because you have to constantly cast your way around the abysmal bad and mostly useless Java type system).

The C++ people at least recognize their wrong by now: Classes with inheritance are something that should be mostly avoided in “modern C++”. Java OTOH will never be able to correct this historic mistake because they went all in on dynamic dispatch.

But Scala could correct this. All what’s needed is better language level—and runtime!—support for static dispatch. As it’s in the real world the much more useful, and especially efficient variant when implemented correctly; only that the last point still needs to be fixed in Scala. (Proper static dispatch could give Scala Native performance in the Rust / C++ ballpark; something that’s otherwise impossible without runtime JIT).

But back on topic: Rust’s Box is equivalent to Java’s Object. Rust’s dyn will give you v-table mechanics. Both are features already prominently present on the JVM. Use the platform!

Trying to implement Box and dyn (which are both native JVM features!) on top of Scala’s type-classes, that are already implemented on top of the dynamic dispatch features of the JVM, is an addition of multiple layers of strictly unnecessary indirection. Not only that this makes everything overly complicated (please lean back and look once more closely on the code presented here), the result would be even extremely inefficient on the JVM. That just makes not sense.

My 2ct. Thanks for reading. :slight_smile:

¹ Hear it out of the horse’s mouth: https://youtu.be/ZyTH8uCziI4?t=2274
He stated the point about Java’s all wrong defaults also multiple times in interviews.

1 Like