Skip to content

Instantly share code, notes, and snippets.

@atamborrino
Last active August 29, 2015 14:13
Show Gist options
  • Save atamborrino/daa451aea542e912c2d6 to your computer and use it in GitHub Desktop.
Save atamborrino/daa451aea542e912c2d6 to your computer and use it in GitHub Desktop.
Playing with type level programming
// 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
@atamborrino
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment