Playing with type level programming

prolog.scala

  // We want to use the Scala type system as a logic programming language by resolving at compile
  // the simple "ancestor" Prolog exercise.

  import shapeless._
  import syntax.singleton._

  // Prolog version

//  parent(stacy, bob).
//  parent(bob, bill).
//  parent(bob, ben).
//
//  ancestor(X, Y) :- parent(X, Y).
//  ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

  // Facts

  case class Parent[A, B](parent: A, child: B)

  val bob = 'bob.narrow
  val bill = 'bill.narrow
  val stacy = 'stacy.narrow
  val ben = 'ben.narrow
  val buffy = 'buffy.narrow
  val sarah = 'sarah.narrow
  val philip = 'philip.narrow

  implicit val fact1 = Parent(stacy, bob)
  implicit val fact2 = Parent(philip, bob)

  implicit val fact3 = Parent(bob, bill)
  implicit val fact4 = Parent(bill, buffy)

//  implicit val fact5 = Parent(bob, ben)
//  implicit val fact6 = Parent(ben, sarah)

  // Rules

  trait Ancestor[A, B]

  implicit def directAncestor[A, B]
  (implicit parent: Parent[A, B]): Ancestor[A, B] = new Ancestor[A, B] {}

  implicit def ancestor[A, B, Z]
  (implicit parent: Parent[A, Z], ancestor: Ancestor[Z, B]): Ancestor[A, B] = new Ancestor[A, B] {}

  // Test

  // The ancestor relationship between p1 and p2 is checked at compile time !
  def doSthWithP1AncestorOfP2[A, B](p1: A, p2: B)(implicit related: Ancestor[A, B]) = {
    println(s"$p1 is an ancestor of $p2")
  }

  doSthWithP1AncestorOfP2(bob, bill) // compile
  doSthWithP1AncestorOfP2(stacy, bill) // compile
  doSthWithP1AncestorOfP2(stacy, buffy) // compile
//  doSthWithP1AncestorOfP2(ben, bill) // does not compile

Issue: apparently, there is no backtracking when implicit resolution has taken the wrong path during the DFS... Or maybe the error is something else?

implicit val fact5 = Parent(bob, ben)
implicit val fact6 = Parent(ben, sarah)
doSthWithP1AncestorOfP2(stacy, buffy) // does not compile, but it should

Did you have a look it this: https://skillsmatter.com/skillscasts/4905-theres-a-prolog-in-your-scala
The author summarizes well the issues of this approach compared to the real Prolog.

@julienrf: Yes you're right: "Scala does not perform the DFS." https://speakerdeck.com/folone/theres-a-prolog-in-your-scala