Cats: Thinking Longterm, Dotty support means removal of all macros

[LukaJCB]

We should start discussing the best way to handle migration to Dotty.
Fortunately we don't have a lot of macros in cats, the few that I can think of are Simulacrum/Machinist and the FunctionK.lift macro. We could manually expand the former (as suggested by @smarter), but I'm not sure how to handle the latter. Maybe someone else has other good ideas :)

[smarter]

FunctionK.lift macro

Seems like this only exists to work around the lack of polymorphic function types, so if it's really a blocker that could force me to prioritize getting them in sooner :). In fact, I'd like to add polymorphic SAM auto-adaptation too, so you could just write val lifted: FunctionK[List, Option] = headOption.

More generally, I'd welcome removing all macros from cats given its central place in the Scala ecosystem. A macro-less cats could probably easily become part of the dotty community build, which would help us make sure we don't break it, and would make it much easier to experiment with new features related to typeclasses or type-level programming in general in a real codebase.

[LukaJCB]

Seems like this only exists to work around the lack of polymorphic function types, so if it's really a blocker that could force me to prioritize getting them in sooner :). In fact, I'd like to add polymorphic SAM auto-adaptation too, so you could just write val lifted: FunctionK[List, Option] = headOption.

That is precisely why it exists and I think a lot of us would love to see them being prioritized!
SAM auto-adaption sounds even better 😍

More generally, I'd welcome removing all macros from cats given its central place in the Scala ecosystem. A macro-less cats could probably easily become part of the dotty community build, which would help us make sure we don't break it, and would make it much easier to experiment with new features related to typeclasses or type-level programming in general in a real codebase.

I think we can probably do this in source compatible way even.
Regarding FunctionK.lift, we could probably go the unsafe route and just use asInstanceOf, which works in general, but allows one to do some strange things. I'm not sure if this breaks anything or is just weird, but we could probably experiment with it.

[LukaJCB]

I played around with it a bit, and the fact that you can insert a type doesn't seem to cause any breakage, all of this compiles fine:

import cats._
import cats.arrow.FunctionK

sealed trait Example[A]

def lift[F[_], G[_]]
  (f: (F[α] ⇒ G[α]) forSome { type α }): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }

def sample[A](option: Option[A]): List[A] = option.toList

val lifted1: FunctionK[Option, List] = lift(sample[Int])
val lifted2: FunctionK[Option, List] = lift(sample[Any])
val lifted3: FunctionK[Option, List] = lift(sample[Example[String]])
val lifted4: FunctionK[Option, List] = lift(sample)

def foo[F[_], A](fa: F[A])(f: F ~> List): List[A] =
  f(fa)

val res1: List[String] = foo(Option("2"))(lifted1)
val res2: List[String] = foo(Option("2"))(lifted2)
val res3: List[String] = foo(Option("2"))(lifted3)
val res4: List[String] = foo(Option("2"))(lifted4)

val res5: List[Int] = foo(Option(2))(lifted1)
val res6: List[Int] = foo(Option(2))(lifted2)
val res7: List[Int] = foo(Option(2))(lifted3)
val res8: List[Int] = foo(Option(2))(lifted4)

Scalafiddle: https://scalafiddle.io/sf/223M0ER/2

[smarter]

Note that there's no forSome in Dotty so you'd have to write def lift[F[_], G[_], A](f: F[A] => G[A])

[LukaJCB]

Ideally with polymorphic functions that'd be (depending on syntax) def lift[F[_], G[_]](f: (A -> F[A] => G[A])): FunctionK[F, G], correct? :)

[smarter]

modulo syntax yes

[larsrh]

I played around with it a bit, and the fact that you can insert a type doesn't seem to cause any breakage, all of this compiles fine:

When you want to provoke the CCE, you have to think like the CCE :stuck_out_tongue_winking_eye:

import cats._
import cats.arrow.FunctionK

def lift[F[_], G[_]]
  (f: (F[α] ⇒ G[α]) forSome { type α }): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }

def sample(option: Option[String]): List[String] = List(option.getOrElse("").length.toString)

val lifted: FunctionK[Option, List] = lift(sample)

lifted(Option(3))

https://scastie.scala-lang.org/larsrh/gV8haQYCRtWDFU6JDi8NHA

[LukaJCB]

Oh wow I didn't know it would accept a Option[String] => List[String] yeah that's pretty broken 😅

[catostrophe]

This impl is fine:

object FunctionK {
  def lift[F[_]]: LiftPartiallyApplied[F] = new LiftPartiallyApplied

  private[arrow] final class LiftPartiallyApplied[F[_]](val dummy: Boolean = true) extends AnyVal {
    type T

    def apply[G[_]](f: F[T] => G[T]): FunctionK[F, G] = new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = f(fa.asInstanceOf[F[T]]).asInstanceOf[G[A]]
    }
  }
}

Works better than the original lift, doesn't need macros, may be defined with the first type param partially applied.

def sample1(option: Option[String]): List[String] =
  List(option.getOrElse("").length.toString)
def sample2[A](option: Option[A]): List[A] = option.toList
def sample3[A]: Option[A] => List[A] = _.toList

FunctionK.lift[Option](sample1) // doesn't compile - correct
FunctionK.lift[Option](sample2) // compiles
FunctionK.lift[Option](sample2[Any]) // doesn't compile - correct
FunctionK.lift[Option](sample3) // compiles, while the original lift doesn't

Props to @alexknvl and @Odomontois for showing this trick.

[LukaJCB]

Very nice, thanks @catostrophe! Care to make a quick PR out of this? :)
Otherwise, I'll create an issue for others to take

[catostrophe]

Doing this with the partial type param application would be source incompatible. Providing both params is redundant and inconvenient.

We can make a source compatible PR to 1.6 and improve it later when we're working on 2.0. What do you think?

[LukaJCB]

That sounds good to me, thanks a lot!

[catostrophe]

The thing I didn't notice is that type inference is a bit worse with the new approach.

def sample[A](option: Option[A]): List[A] = option.toList
val f1 = FunctionK.lift(sample) // doesn't infere
val f2: Option ~> List = FunctionK.lift(sample) // compiles
val f3 = FunctionK.lift[Option, List](sample) // compiles, can be simplified to lift[Option](sample)

So, unfortunately, it cannot be a replacement for the macro generated lift in 1.x due to source incompatibility.

[alexknvl]

https://github.com/alexknvl/polymorphic/tree/master/src/test/scala

    class Foo[A]

    test("constructors") {
        val f1: ∀[Foo] = ∀(new Foo)
        val f2: ∀[Foo] = Forall(new Foo)
        val f3: ∀[Foo] = Forall.of[Foo](new Foo)
        val f4: ∀[Foo] = Forall.of[Foo].from(new Foo)
        val f5: ∀[Foo] = Forall.from(new Prototype[Foo] {
            override def apply[X]: Foo[X] = new Foo
        })
        val f7 = ∀[Foo](new Foo)
        val f8 = Forall[Foo](new Foo)
        val f9 = Forall.of[Foo](new Foo)
        val f10 = Forall.of[Foo].from(new Foo)
        val f11 = Forall.from(new Prototype[Foo] {
            override def apply[X]: Foo[X] = new Foo
        })
    }

        val f1: Option ~> List = fn(_.toList)
        val f2 = fn[Option, List](_.toList)

        val f3: Option ~> List = FunctionK(_.toList)
        val f4 = FunctionK[Option, List](_.toList)

But indeed, type-inference is sub-optimal.

I'll update it in a bit to the latest cats if anyone wants to check it out.

[neko-kai]

Why not just:

object FunctionK {
  private[FunctionK] type T

  def lift[F[_], G[_]](f: F[T] => G[T]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }
}

?
It's impossible to refer to T outside of final object FunctionK and spoil this scheme, and in my experience the type inference for this kind of private 'pseudo-type-variables' is quite good.

[djspiewak]

You wouldn't be able to do type T in that fashion: it's abstract within an object. (edit: apparently I was mistaken! also learning new things about Scala) However, you could do something like a sealed trait. More precisely:

object FunctionK {
  sealed trait τ

  def lift[F[_], G[_]](f: F[τ] => G[τ]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }

This is the Scala version of a trick that Kmett came up with (and if you're curious, tau is indeed the conventional name for the sentinel type). It type infers quite well in most cases and most definitely works, though I think a lot of people are scared off by the (erased) asInstanceOf.

What this trick is doing, more formally speaking, is exploiting Skolem equivalence. The rank-1 τ type is isomorphic to an existential type (as it has no inhabitants). We're trying to encode a rank-2 universal type within the function parameter (something like lift :: (forall a . f a -> g a) -> FunctionK f g). Skolemization informs us that every rank-N existential is equivalent to a rank-N+1 universal, and so the encoding is both sound and exceptionally instructive.

If you've ever wondered what the cryptic "this is a GADT skolem" error messages are from scalac, this is the concept they're referencing.

[smarter]

You wouldn't be able to do type T in that fashion: it's abstract within an object

You can have abstract types in objects in Scala.

[djspiewak]

You can have abstract types in objects in Scala.

You… can… what?

/me frantically opens ammonite

Holy shit.

[alexknvl]

@kaishh @djspiewak Both of your snippets are unsound. https://scalafiddle.io/sf/W0brrP1/0 That weird abstract type in an AnyVal thing there is to prevent not only referring to the type, but also being able to share the type across multiple invocations.

import cats.arrow.FunctionK
import cats.{ Id, ~> }

object FunctionK {
  private[this] sealed trait τ

  def lift[F[_], G[_]](f: F[τ] => G[τ]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }
}

def coerce[U, V](u: U): V = {
  val f = FunctionK.lift[Id, λ[x => λ[y => Unit] ~> Id]] { t =>
    FunctionK.lift[λ[y => Unit], Id](_ => t)
  }
  f(u)(())
}

println(coerce[String, Int]("abc") + 1)

EDIT: Ed's trick might work with

object FunctionK {
  private[this] sealed trait τ[F[_], G[_]]

  def lift[F[_], G[_]](f: F[τ[F, G]] => G[τ[F, G]]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }
}

But I am not 100% convinced that this is enough.

EDIT 2: But if it works, this looks dope

private[package] sealed trait τ[F[_]]

type Forall[F[_]] = F[τ[F]]

implicit class ForallOps[F[_]](val a: Forall[F]) extends AnyVal {
  def runForall[A]: F[A] = a.asInstanceOf[F[A]]
}

def forall[F[_]](f: F[τ[F]]): Forall[F] = f

val nil = forall[List](Nil)

nil.runForall[Int]

EDIT 3: But type inference might be so-so because of that extra type parameter on τ, not entirely sure.

[neko-kai]

@alexknvl

Both of your snippets are unsound.

Oh, blast it, I use that everywhere!

You can probably omit the type parameter by attaching the disambiguator as a refinement instead. This should retain the exact same inference as plain T (although, that may indicate that type parameters will also retain the same inference)

object FunctionK {
  private[FunctionK] sealed trait T
  private[FunctionK] object T {
    type Aux[F[_], G[_]] = T { type Disamb = F[G[T]] }
  }

  def lift[F[_], G[_]](f: F[T.Aux[F, G]] => G[T.Aux[F, G]]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }
}

[smarter]

I've now opened a PR for removing machinist: https://github.com/typelevel/cats/pull/2925 and another PR for removing the FunctionK macro using @alexknvl trick: https://github.com/typelevel/cats/pull/2926. For kind-projector see https://github.com/typelevel/kind-projector/issues/108#issuecomment-507041136. The last remaining piece is simulacrum, I have a branch of dotty with a prototype (dotty doesn't support macro annotations so it can't be implemented outside of the compiler), and I'll see if I can get that to production, assuming no one has a better solution (make a scalafix rewrite rule to expand the macro ?)

[mpilquist]

There's roughly 50 uses of @typeclass in Cats. My advice is to remove them manually as part of Cats 3 development. I could definitely do that faster than writing a scalafix to expand the annotation. :)

[LPTK]

By the way, @alexknvl's encoding is _also_ unsound. The trouble is that you can't just cast random things to a trait, which is not erased on the JVM.

import cats.arrow.FunctionK
import cats.{ Id, ~> }

object FunctionK {
  private[this] sealed trait τ[F[_], G[_]]

  def lift[F[_], G[_]](f: F[τ[F, G]] => G[τ[F, G]]): FunctionK[F, G] =
    new FunctionK[F, G] {
      def apply[A](fa: F[A]): G[A] = 
        f.asInstanceOf[F[A] => G[A]](fa)
    }
}

println(FunctionK.lift[Option,Option](identity)(None)) // okay

println(FunctionK.lift[Id,Id](identity)(0)) // boom!

https://scastie.scala-lang.org/vpn9pRMFQ2CpnbawXaa2RQ

But even if that worked (e.g., using an opaque type), I'm confident we could still crash it by calling lift#apply inside of lift and mixing things up between the inner and outer invocations. Something like lift[Id,Id]{ a => lift[Id,Id]{ b => a }(0) + 1; a }("oops").

[travisbrown]

I now have a branch with cats-core cross-compiling on 2.12, 2.13, and Dotty. I've opened a few PRs to fix code that's broken on Dotty in cases where the changes are at least arguably an improvement (or at worst a lateral move) on Scala 2:

• Add some parentheses: https://github.com/typelevel/cats/pull/3182
• Remove some redundant final: https://github.com/typelevel/cats/pull/3183
• Avoid eta-expansion syntax for Function0: https://github.com/typelevel/cats/pull/3185
• Replace kind-projector's *[_]: https://github.com/typelevel/cats/pull/3186
• Help out type inference: https://github.com/typelevel/cats/pull/3187
• Add some type annotations for implicit definitions: https://github.com/typelevel/cats/pull/3188
• Replace do: https://github.com/typelevel/cats/pull/3189
• Add an @unchecked: https://github.com/typelevel/cats/pull/3190
• Another annotation: https://github.com/typelevel/cats/pull/3191
• Replace kind-projector's polymorphic lambda value syntax: https://github.com/typelevel/cats/pull/3193

There are a small handful of other things that need manual attention that I haven't PR'd:

• A couple of places where it's necessary to cast to Any in AndThen and Eval.
• I split FunctionK.lift out into version-specific code and didn't provide a Dotty alternative. Note that this is the only Scala 2 / 3 version-specific code that's necessary for cats-kernel and cats-core.

The biggest change that was necessary was Simulacrum, which I rewrote as a set of Scalafix rules. I also rewrote kind-projector as a couple of Scalafix rules, not as a long-term solution, but just to unblock this experiment. I'll be publishing these rules this week, probably today or tomorrow.

The other modules still need some work. Alleycats is fine, but cats-free uses some existential types in a way that I think might require version-specific code, and I'm running into a lot of errors in the laws modules that look like they might be Dotty bugs.

[larsrh]

Full Dotty support has landed in #3636.