Last active
December 21, 2015 04:58
-
-
Save bkyrlach/6253215 to your computer and use it in GitHub Desktop.
Some thoughts on implementing a logic DSL in Scala.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object Jealousy { | |
| import Scalog._ | |
| def main(args: Array[String]): Unit = { | |
| implicit val knowledge = | |
| Functor("loves", "vincent", "mia") :: | |
| Functor("loves", "marsellus", "mia") :: | |
| Functor("loves", "pumpkin", "honey_bunny") :: | |
| Functor("loves", "honey_bunny", "pumpkin") :: | |
| Rule(Functor("jealous", "X", "Y"), Functor("loves", "X", "Z") and Functor("loves", "Y", "Z")) :: | |
| Nil | |
| println(query(Functor("jealous", "marsellus" ,"W"))) | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.UUID | |
| abstract class LogicElement { | |
| def and(t: LogicElement): And = this match { | |
| case And(terms) => And(t :: terms) | |
| case _ => And(t :: this :: Nil) | |
| } | |
| } | |
| case class And(terms: List[LogicElement]) extends LogicElement | |
| case class Atom[A](val v: A) extends LogicElement | |
| case class Variable(val name: String) extends LogicElement | |
| case class Functor(val name: String, val terms: LogicElement*) extends LogicElement { | |
| def arity: Int = terms.size | |
| } | |
| case class Rule(impliciation: LogicElement, condition: LogicElement) extends LogicElement | |
| case class LogicList(val elems: LogicElement*) extends LogicElement | |
| case object Underscore extends LogicElement | |
| object Scalog { | |
| type Context = Map[String, LogicElement] | |
| implicit def any2atom[A](a: A): Atom[A] = Atom(a) | |
| implicit def string2element(s: String): LogicElement = if(s.head.isUpper) Variable(s) else Atom(s) | |
| def bound(v: Variable, c: Context): Boolean = c.contains(v.name) | |
| def unifyVarWithTerm(v: Variable, t: LogicElement)(implicit kb: List[LogicElement], c: Context): (Boolean, Context) = { | |
| if(bound(v, c)) { | |
| unify(c(v.name), t) | |
| } else { | |
| (true, c + (v.name -> t)) | |
| } | |
| } | |
| def unify(t1: LogicElement, t2: LogicElement)(implicit kb: List[LogicElement], c: Context): (Boolean, Context) = (t1, t2) match { | |
| case (Atom(x), Atom(y)) => (x == y, c) | |
| case (f1: Functor, f2: Functor) => { | |
| if(f1.arity == f2.arity && f1.name == f2.name) { | |
| f1.terms.zip(f2.terms).foldLeft((false, c))((acc, t) => unify(t._1, t._2)(kb, acc._2)) | |
| } else (false, c) | |
| } | |
| case (t: LogicElement, r: Rule) => { | |
| val ur = unify(t, r.impliciation) | |
| if(ur._1) query(r.condition)(kb, ur._2) else (false, c) | |
| } | |
| case (v1: Variable, v2: Variable) => { | |
| if(!(c.contains(v1.name) && c.contains(v2.name))) { | |
| val newV = new Variable(UUID.randomUUID.toString) | |
| (true, (c + (v1.name -> newV)) + (v2.name -> newV)) | |
| } else (false, c) | |
| } | |
| case (v: Variable, t: LogicElement) => unifyVarWithTerm(v, t) | |
| case (t: LogicElement, v: Variable) => unifyVarWithTerm(v, t) | |
| case (l1: LogicList, l2: LogicList) => { | |
| val ur = unify(l1.elems.head, l2.elems.head) | |
| if(ur._1) { | |
| if(l1.elems.size > 2 && l2.elems.size > 2) unify(LogicList(l1.elems.tail:_*), LogicList(l2.elems.tail:_*))(kb, ur._2) else { | |
| if(l1.elems.size == 2) { | |
| unify(l1.elems.tail.head, LogicList(l2.elems.tail:_*))(kb, ur._2) | |
| } else { | |
| unify(LogicList(l1.elems.tail:_*), l2.elems.tail.head)(kb, ur._2) | |
| } | |
| } | |
| } else ur | |
| } | |
| case (t: LogicElement, Underscore) => (true, c) | |
| case _ => (false, c) | |
| } | |
| def query(t: LogicElement)(implicit kb: List[LogicElement], c: Context = Map.empty[String, LogicElement]): (Boolean, Context) = t match { | |
| case And(terms) => { | |
| terms.foldLeft((true, c)){(acc, t) => | |
| val ur = kb.foldLeft((false, acc._2)){ (acc, k) => if(acc._1) acc else unify(t, k)(kb, acc._2) } | |
| (acc._1 && ur._1, ur._2) | |
| } | |
| } | |
| case _ => kb.foldLeft((false, c)){ (acc, k) => if(acc._1) acc else unify(t, k) } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Output for Jealousy...
(true,Map(X -> Atom(marsellus), Y -> Variable(b432a265-55ef-459c-a9b8-2c4e03e0b0f6), W -> Variable(b432a265-55ef-459c-a9b8-2c4e03e0b0f6), b432a265-55ef-459c-a9b8-2c4e03e0b0f6 -> Atom(vincent), Z -> Atom(mia)))