Are there any good sources on how implicit resolution works, especially regarding type inference and order (if any) in which implicits are searched for all implicit parameters?
First, of course I read Scala Language Specification, so I understand (or I think) the basics, like where the compiler searches for implicits. Whenever however I try to do anything a little more advanced, like recursive implicits, I always encounter supernatural problems and working with them seems like praciticing experimental magic. Even keeping all implicits together in a companion object and thus eliminating all difficult problems with conflicts, a little change in the code, which shouldn't change the semantics according to specs, sometimes makes a difference between compiling and not compiling.
I remember a case where the compiler couldn't find an implicit for Companion, but introducing import Companion._ before the call made it compile, and object Companion had only implicit defs returning Companion instances.
I had a case where a code structured this way:
object ADT {
class Evidence;
object Evidence {
class ParticularEvidence extends Evidence
object ParticularEvidence {
implicit def ... :ParticularEvidence
}
}
...
def f(...)(implicit e:ParticularEvidence) = ...
...
f(...)
didn't compile, but moving the implicits defs (the only ones for ParticularEvidence) from ParticularEvidence to parent Evidence object made them visible.
After some trial and error I understood that the resolution logic is pretty limited and constructs of this class for example:
implicit def f[X, Y, Z](x :X)(implicit e1:Evidence1[X, Y], implicit e2:Evidence[Y, Z]) :Y
...
val x :X = ...
val z:Z = x
where evidence classes are invariant to their type parameters will rarely compile even if there's exactly one type Z for which such implicit values exist. But I have no idea why the following is a problem:
/** Stub for the purpose of this example **/
sealed abstract class ||[+A,+B]
case class LeftVariant[+A](left :A) extends ||[A, Nothing]
case class RightVariant[+B](right :B) extends ||[Nothing, B]
object SupportingEvidence {
/** C is an Atom and U==C or U is a type union explicitly containg C */
sealed class ComponentOf[C, U] protected[SupportingEvidence]() extends SupportingEvidence
final class Atom[T] protected[SupportingEvidence]() extends ComponentOf[T, T]
implicit def atom[T](implicit ev :Not[T <:< ||[_,_]]) = a.asInstanceOf[Atom[T]]
implicit def leftComponent[A, B, C](implicit ev: C ComponentOf A): C ComponentOf (A || B) =
ev.asInstanceOf[ComponentOf[C, A || B]]
implicit def rightComponent[A, B, C](implicit ev: C ComponentOf B, but: Not[C ComponentOf A]): C ComponentOf (A || B) =
ev.asInstanceOf[ComponentOf[C, A || B]]
private[this] val a = new Atom[Nothing]
type Something[X] = Not[X<:<Nothing]
/** T = U - C, calculated as follows:
* U = A || B => A - C || B - C
* U <: C => Nothing
* else => U
*/
final class Minus[U, C, T] protected[SupportingEvidence]() extends SupportingEvidence
object Minus {
implicit def nothing[U, C](implicit atom :Atom[U], conforms :U ConformsTo C) :Minus[U, C, Nothing] =
certify[U, C, Nothing]
implicit def self[U, C](implicit atom :Atom[U], diff :Not[U ConformsTo C]) :Minus[U, C, U] =
certify[U, C, U]
implicit def left[A, B, C, T](implicit left :Minus[A, C, T],
leftSomething :Not[C ConformsTo A],
rightNothing :C ConformsTo B) :Minus[A || B, C, T] =
certify[A || B, C, T]
implicit def right[A, B, C, T](implicit leftNothing :C ConformsTo A,
right :Minus[B, C, T]) :Minus[A || B, C, T] =
certify[A || B, C, T]
implicit def union[A, B, C, L, R](implicit atom :Atom[C],
leftSomething :Not[C ConformsTo A],
rightSomething :Not[C ConformsTo B],
left :Minus[A, C, L],
right :Minus[B, C, R]) :Minus[A || B, C, L || R] =
certify[A || B, C, L || R]
private[this] def certify[U, C, T] = m.asInstanceOf[Minus[U, C, T]]
}
private[this] val m = new Minus[Nothing, Nothing, Nothing]
}
final class ConformsTo[-X, +Y] protected[ADT] (protected[ADT] val cast :X=>Y) //extends Conversion[X, Y]
object ConformsTo {
import SupportingEvidence._
private def apply[X, Y](fun :X=>Y) :ConformsTo[X, Y] = new ConformsTo(fun)
implicit def directlyConformsTo[X, Y](implicit ev :X <:< Y) :ConformsTo[X, Y] =
ConformsTo(ev.apply _)
implicit def conformsToLeft[X, A, B](implicit atom :Atom[X],
conform :ConformsTo[X, A],
only :Not[ConformsTo[X, B]]) :ConformsTo[X, A || B] =
ConformsTo((x :X) => LeftVariant(conform.cast(x)))
implicit def conformsToRight[X, A, B](implicit atom :Atom[X],
conform :ConformsTo[X, B],
only :Not[ConformsTo[X, A]]) :ConformsTo[X, A || B] =
ConformsTo((x :X) => RightVariant(conform.cast(x)))
implicit def conformsToBoth[X, A, B](implicit atom :Atom[X],
left :ConformsTo[X, A],
right :ConformsTo[X, B]) :ConformsTo[X, A || B] =
ConformsTo((x :X) => LeftVariant(left.cast(x)))
implicit def alternativesConform[A, B, Y](implicit left :ConformsTo[A, Y], right :ConformsTo[B, Y],
nonDirect :Not[(A || B) <:< Y]) :ConformsTo[A || B, Y] =
ConformsTo((x :A || B) => x match {
case LeftVariant(l) => left.cast(l)
case RightVariant(r) => right.cast(r)
})
}
}
/** Implicit value for Not[T] exists <=> there's no implicit value for T in scope */
final class Not[+T](override val toString :String)
object Not {
private[this] val nice = new Not[Nothing]("default")
private[this] val mean = new Not[Nothing]("conflict")
implicit def conflict[T](implicit ev :T) :Not[T] = mean
implicit def default[T] :Not[T] = nice
}
//test Minus
class SA
class SB
implicitly[Minus[SA || SB, Nothing, SA || SB]] //unhelpful divergent expansion error
I am experimenting here with boxed type unions (||[A, B] is basically a glorified Either with transparent flattening of the structure and hidden left/right options). Minus is part of type arithmetic I want to implement: in the last line I demand that the compiler provides evidence that SA||SB - Nothing = SA||SB. More generally, I expect an implicit minus[A,B,C] to exist if and only if C is the smallest type containing all values from A and none values of B. What's more, I expect it to find sch evidence even if C is unknown, only from A,B, so I can try to implement implicit evidence allowing for automatic conversion of any type union to some normalized form. eventually, I want to find such combination of implicit methods providing Normalized values, that I will be able to write something like this:
def normalize[A,B,N](v :A || B)(implicit :Normalized[A || B, N]) :N
val a :Int || java.sql.Date || Int || String || java.lang.Date = ...
val n = normalize(a) //n is of type Int || java.lang.Date || String
So the compiler, with a help of set of rules enforced by implicit methods, should be able to simplify a union type by getting rid of parts which are dominated by other parts. For that, I must be able to i plement set subtraction on types.
I know that I'm probably far in enemy teritory with this and any compiler change might break the whole program depending on this, but I treat it primarily as a puzzle and a proof of concept. Once I get to know what's possible, I will start to think what's sensible.
So the specific question is: does anybody know what's exactly wrong with the above code and can if it can be fixed?
EDIT: I rewrote this answer to focus on Minus:
I swap the implicit ConformsTo rule in minus. In nothing and self you check U ConformsTo C. You should do the same in left and right:
final class Minus[U, C, T] extends SupportingEvidence
object Minus {
implicit def nothing[U, C](implicit atom: Atom[U], conforms: U ConformsTo C): Minus[U, C, Nothing] =
certify[U, C, Nothing]
implicit def self[U, C](implicit atom: Atom[U], diff: Not[U ConformsTo C]): Minus[U, C, U] =
certify[U, C, U]
implicit def left[A, B, C, T](implicit left: Minus[A, C, T],
leftSomething: Not[A ConformsTo C],
rightNothing: B ConformsTo C): Minus[A || B, C, T] =
certify[A || B, C, T]
implicit def right[A, B, C, T](implicit leftNothing: A ConformsTo C,
right: Minus[B, C, T]): Minus[A || B, C, T] =
certify[A || B, C, T]
implicit def union[A, B, C, L, R](implicit //atom: Atom[C],
leftSomething: Not[A ConformsTo C],
rightSomething: Not[B ConformsTo C],
left: Minus[A, C, L],
right: Minus[B, C, R]): Minus[A || B, C, L || R] =
certify[A || B, C, L || R]
def certify[U, C, T] = nothingMinusNothingIsNothing.asInstanceOf[Minus[U, C, T]]
val nothingMinusNothingIsNothing = new Minus[Nothing, Nothing, Nothing]
}
It allows you to check:
trait Animal
trait Car
trait Cow extends Animal
trait Barking
class Dog extends Animal with Barking
implicitly[Minus[Dog, Animal, Nothing]]
implicitly[Minus[Dog, Barking, Nothing]]
implicitly[Minus[Cow, Barking, Cow]]
implicitly[Minus[Cow, Animal with Barking, Cow]]
implicitly[Minus[Dog || Cow, Barking, Cow]]
implicitly[Minus[Cow || Dog, Barking, Cow]]
implicitly[Minus[Cow || Car, Barking, Cow || Car]]