使用“Prolog in Scala”查找可用的类型类实例

Question

考虑到https://speakerdeck.com/folone/theres-a-prolog-in-your-scala，我想要“滥用”Scala类型系统，以找到所有符合给定条件的CanBuildFrom实例。按照Prolog风格，我会评估以下伪代码：

can_build_from(Src, int, list[int])
Src = somecollectiontype1[int]
Src = somecollectiontype2[int]
... etc

即运行时将查找所有满足语句can_build_from(Src, int, list[int])的Src的值。
现在，我知道Scala隐式查找系统是一个原始的约束/逻辑编程环境，并不适合用于这种技巧，并且不能“返回”Src的多个找到的值。所以我的问题是：是否有一种“魔法技巧”可以使它工作，以便我能够获得CanBuildFrom[X, Int, List[Int]]中X的所有可能值？
附加示例：

trait CanFoo[T, U]

implicit val canFooIntString  = new CanFoo[Int,     String] {}
implicit val canFooDblString  = new CanFoo[Double,  String] {}
implicit val canFooBoolString = new CanFoo[Boolean, String] {}
implicit val canFooIntSym     = new CanFoo[Int,     Symbol] {}
implicit val canFooDblSym     = new CanFoo[Double,  Symbol] {}
implicit val canFooBoolSym    = new CanFoo[Boolean, Symbol] {}

现在我想查询CanFoo[X，String]并返回X ∈ [Int，Double，Boolean]，或者CanFoo[Int，X]并返回X ∈ [String，Symbol]。

另外，CanFoo[X，String]将返回List(canFooIntString，canFooDblString，canFooBoolString)，即所有匹配的CanFoo实例。

- Erik Kaplun

---

在这种情况下，集合是无限的：X 可以是所有 T 的 List[T]... 我猜那不是你想要的。 - Miles Sabin

@MilesSabin：即使输出集合是List[Int]，也可以吗？也许我不理解CanBuildFrom，但这个想法通常可以实现吗？ - Erik Kaplun

好的，现在假设您有一个低优先级的 def canFooDefaultUnit[T] = new CanFoo[T, Unit] {} ... 您会期望第一个类型参数的集合是什么？ - Miles Sabin

如果查询是 CanFoo[X, Unit]，你的意思是什么？我想我明白了你的观点，但这是否意味着它是不可能的，或者至少通常是不可能的？ - Erik Kaplun

@EECOLOR：实际上，我正在尝试查找哪些实例可用于“CanBuildFrom”类型类。 - Erik Kaplun

Answer 1

在某些情况下，可以通过编译器内部的方法来实现这一点。

import scala.language.experimental.macros
import scala.reflect.internal.util
import scala.reflect.macros.{blackbox, contexts}

object Macros {

  def allImplicits[A]: List[String] = macro impl[A]

  def impl[A: c.WeakTypeTag](c: blackbox.Context): c.Tree = {
    import c.universe._

    val context = c.asInstanceOf[contexts.Context]
    val global: context.universe.type = context.universe
    val analyzer: global.analyzer.type = global.analyzer
    val callsiteContext = context.callsiteTyper.context

    val tpA = weakTypeOf[A]

    val search = new analyzer.ImplicitSearch(
      tree = EmptyTree.asInstanceOf[global.Tree],
      pt = tpA.asInstanceOf[global.Type],
      isView = false,
      context0 = callsiteContext.makeImplicit(reportAmbiguousErrors = false),
      pos0 = c.enclosingPosition.asInstanceOf[util.Position]
    )

    q"${search.allImplicits.map(_.tree.symbol.toString).distinct}"
  }
}

allImplicits[CanFoo[_, String]]
// List(value canFooBoolString, value canFooDblString, value canFooIntString)

在2.13.0中进行了测试。

---

在2.13.10仍然有效。

Scala 3的实现方式类似。

import dotty.tools.dotc.typer.{Implicits => dottyImplicits}
import scala.quoted.{Expr, Quotes, Type, quotes}

inline def allImplicits[A]: List[String] = ${impl[A]}

def impl[A: Type](using Quotes): Expr[List[String]] = {
  import quotes.reflect.*
  given c: dotty.tools.dotc.core.Contexts.Context =
    quotes.asInstanceOf[scala.quoted.runtime.impl.QuotesImpl].ctx

  val typer = c.typer

  val search = new typer.ImplicitSearch(
    TypeRepr.of[A].asInstanceOf[dotty.tools.dotc.core.Types.Type],
    dotty.tools.dotc.ast.tpd.EmptyTree,
    Position.ofMacroExpansion.asInstanceOf[dotty.tools.dotc.util.SourcePosition].span
  )

  def eligible(contextual: Boolean): List[dottyImplicits.Candidate] =
    if contextual then
      if c.gadt.isNarrowing then
        dotty.tools.dotc.core.Contexts.withoutMode(dotty.tools.dotc.core.Mode.ImplicitsEnabled) {
          c.implicits.uncachedEligible(search.wildProto)
        }
      else c.implicits.eligible(search.wildProto)
    else search.implicitScope(search.wildProto).eligible


  def implicits(contextual: Boolean): List[dottyImplicits.SearchResult] =
    eligible(contextual).map(search.tryImplicit(_, contextual))

  val contextualImplicits = implicits(true)
  val nonContextualImplicits = implicits(false)
  val contextualSymbols = contextualImplicits.map(_.tree.symbol)
  val filteredNonContextual = nonContextualImplicits.filterNot(sr => contextualSymbols.contains(sr.tree.symbol))

  val implicitStrs = (contextualImplicits ++ filteredNonContextual).collect {
    case success: dottyImplicits.SearchSuccess => success.tree.asInstanceOf[ImplicitSearchSuccess].tree.show
  }

  Expr(implicitStrs)
}

trait CanFoo[T, U]

object CanFoo {
  given canFooIntString: CanFoo[Int, String] with {}
  given canFooDblString: CanFoo[Double, String] with {}
  given canFooBoolString: CanFoo[Boolean, String] with {}
  given canFooIntSym: CanFoo[Int, Symbol] with {}
  given canFooDblSym: CanFoo[Double, Symbol] with {}
  given canFooBoolSym: CanFoo[Boolean, Symbol] with {}
}

allImplicits[CanFoo[_, String]] 
//"CanFoo.canFooIntString", "CanFoo.canFooBoolString", "CanFoo.canFooDblString"

Scala 3.2.0。

- Dmytro Mitin