scala - Scala 中的发散隐式扩展，涉及链式隐式

Question

(注意:此问题从 Scala 2.13 开始已修复，请参见此处:https://github.com/scala/scala/pull/6050)

我正在开发一个涉及链式隐式的 Scala 类型系统。这个系统在许多情况下的表现都符合我的预期，但在其他情况下却因不同的扩展而失败。到目前为止我还没有对这种差异给出一个很好的解释，希望社区能够为我解释一下!

这是一个重现问题的简化类型系统:

object repro {
  import scala.reflect.runtime.universe._

  trait +[L, R]

  case class Atomic[V](val name: String)
  object Atomic {
    def apply[V](implicit vtt: TypeTag[V]): Atomic[V] = Atomic[V](vtt.tpe.typeSymbol.name.toString)
  }

  case class Assign[V, X](val name: String)
  object Assign {
    def apply[V, X](implicit vtt: TypeTag[V]): Assign[V, X] = Assign[V, X](vtt.tpe.typeSymbol.name.toString)
  }

  trait AsString[X] {
    def str: String
  }
  object AsString {
    implicit def atomic[V](implicit a: Atomic[V]): AsString[V] =
      new AsString[V] { val str = a.name }
    implicit def assign[V, X](implicit a: Assign[V, X], asx: AsString[X]): AsString[V] =
      new AsString[V] { val str = asx.str }
    implicit def plus[L, R](implicit asl: AsString[L], asr: AsString[R]): AsString[+[L, R]] =
      new AsString[+[L, R]] { val str = s"(${asl.str}) + (${asr.str})" }
  }

  trait X
  implicit val declareX = Atomic[X]
  trait Y
  implicit val declareY = Atomic[Y]
  trait Z
  implicit val declareZ = Atomic[Z]

  trait Q
  implicit val declareQ = Assign[Q, (X + Y) + Z]
  trait R
  implicit val declareR = Assign[R, Q + Z]
}

以下是该行为的演示，其中包含一些工作案例以及不同的失败:

scala> :load /home/eje/divergence-repro.scala
Loading /home/eje/divergence-repro.scala...
defined module repro

scala> import repro._
import repro._

scala> implicitly[AsString[X]].str
res0: String = X

scala> implicitly[AsString[X + Y]].str
res1: String = (X) + (Y)

scala> implicitly[AsString[Q]].str
res2: String = ((X) + (Y)) + (Z)

scala> implicitly[AsString[R]].str
<console>:12: error: diverging implicit expansion for type repro.AsString[repro.R]
starting with method assign in object AsString
              implicitly[AsString[R]].str

Answer 1

你会惊讶地发现自己没有做错任何事!至少在逻辑层面上是这样。您在这里遇到的错误是 Scala 编译器在解析递归数据结构的隐式时的已知行为。 The Type Astronaut's Guide to Shapeless 书中对此行为给出了很好的解释。 :

Implicit resolution is a search process. The compiler uses heuristics to determine whether it is “converging” on a solution. If the heuristics don’t yield favorable results for a particular branch of search, the compiler assumes the branch is not converging and moves onto another.

One heuristic is specifically designed to avoid infinite loops. If the compiler sees the same target type twice in a particular branch of search, it gives up and moves on. We can see this happening if we look at the expansion for CsvEncoder[Tree[Int]] The implicit resolution process goes through the following types:

CsvEncoder[Tree[Int]] // 1
CsvEncoder[Branch[Int] :+: Leaf[Int] :+: CNil] // 2
CsvEncoder[Branch[Int]] // 3
CsvEncoder[Tree[Int] :: Tree[Int] :: HNil] // 4
CsvEncoder[Tree[Int]] // 5 uh oh

We see Tree[A] twice in lines 1 and 5, so the compiler moves onto another branch of search. The eventual consequence is that it fails to find a suitable implicit.

在你的情况下，如果编译器继续前进并且没有这么早放弃，它最终会找到解决方案!但请记住，并非每个不同的隐式错误都是错误的编译器警报。有些实际上正在发散/无限扩展。

我知道这个问题有两种解决方案:

1. 基于宏的递归类型惰性求值:

shapeless 库有一个 Lazy 类型，它的 Hlist 头的评估与运行时不同，因此可以防止这种发散的隐式错误。我发现解释或提供它的例子超出了OP主题。但你应该检查一下。

创建隐式检查点，以便编译器事先可以使用递归类型的隐式检查点:

implicitly[AsString[X]].str

implicitly[AsString[X + Y]].str

val asQ = implicitly[AsString[Q]]

asQ.str

{
  implicit val asQImplicitCheckpoint: AsString[Q] = asQ

  implicitly[AsString[R]].str
}

如果您不喜欢这两种解决方案，那也没什么丢人的。 shapeless 的 Lazy 解决方案虽然经过尝试且确实有效，但仍然是第三方库依赖项，而且随着 scala 3.0 中宏的删除，我不确定会变成什么所有这些基于宏的技术。