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.

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

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

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

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 中删除了宏，我不确定所有这些基于宏的技术会变成什么样子.

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

A diverging implicit expansion in Scala, involving chained implicits

scala

implicit