Scala Beauty – Fun with Logic

While playing around with Mathematica, I though about implementing a simple DSL for Boolean expressions in Scala, my use case was something like this:


    val μ = (2 :: 5 :: 8 :: Φ)

    val p1 = all of μ is even
    val p2 = all of μ is odd
    val p3 = (some of μ is even) and (some of μ is odd)
    val p4 = not ( all of μ is ( _ > 5 ) )
    val p5 = p1 implies p2
    val p6 = none of μ is 13

So, even if you don’t know Scala, you should be able the figure out what is going on here!
Several language features are presented here:

  • Case classes, for modeling Propositions and Lazy boolean expressions
  • Infix syntax
  • Partially applied functions

So here is the boolean propositions model:


trait Prop {
  def of[A](a: Traversable[A]) = Of(this, a)
}
case object AllP extends Prop
case object SomeP extends Prop
case object NoneP extends Prop
case class Of[A](val p: Prop, val a: Traversable[A]) {
  def is(f: A ⇒ Boolean): Hold = p match {
    case AllP  ⇒ Hold(() ⇒ a forall f)
    case SomeP ⇒ Hold(() ⇒ a exists f)
    case NoneP ⇒ Hold(() ⇒ !(a exists f))
  }

  def is(elem: A): Hold = is(elem == _)
}
case class Hold(val pred: () ⇒ Boolean) {
  def release = pred()
  def &&(that: Hold) = Hold( () ⇒ pred() && that.pred() )
  def and(that: Hold) = this && that
  def ||(that: Hold) = Hold( () ⇒ pred() || that.pred() )
  def or(that: Hold) = this || that
  def unary_! = Hold( () ⇒ !pred() )
  def implies(that: Hold) = Implication(this, that)
}

case class Implication(lhs: Hold, rhs: Hold) {
  def release = ! (lhs release) || (rhs release)
}

I should have modeled conjunction, disjunction and negation as case classes for a complete AST, but this is just for fun :). A helper for building expressions is pretty simple as well:


object Props {
  def all = AllP
  def some = SomeP
  def none = NoneP
  def not(h: Hold) = !h
}

I needed some sugar and honey while working with Lists, still having Mathematica loaded into my brains, so I wrote a Mathematica like map operator:


implicit def iterOps[A, R](f: A ⇒ R) = new {
      def /@(x: Traversable[A]) = x map f
    }

So you can then, for example, do:


 λy /@ (1 :: 2 :: 3 :: Φ)

to map the function λy over the list (1 :: 2 :: 3 :: Φ). Φ here is just a synonym to Nil.

Let’s test our work so far:


object ScalaBeauty {

  import Props._

  type ℤ = Int

  val λx = (x: ℤ) ⇒ x * x

  val sum = (_: ℤ) + (_: ℤ)
  val square = λx
  val addOne = sum(1, _: ℤ)
  val even = (_:ℤ) % 2 == 0
  val odd = ! even(_: ℤ)


  implicit def iterOps[A, R](f: A ⇒ R) = new {
      def /@(x: Traversable[A]) = x map f
    }


  def out[A](x: Traversable[A]) =
    println( x mkString ("[", ", ", "]") )

  def main(args: Array[String]) {


    val a = (addOne andThen square) /@ ( 1 :: 2 :: 3 :: Φ)
    out(a)
    
    val λy = square andThen addOne
    val b = λy /@ (1 :: 2 :: 3 :: Φ)
    out(b)


    val μ = (2 :: 5 :: 8 :: Φ)


    val p1 = all of μ is even
    val p2 = all of μ is odd
    val p3 = (some of μ is even) and (some of μ is odd)
    val p4 = not ( all of μ is ( _ > 5 ) )
    val p5 = p1 implies p2
    val p6 = none of μ is 13

    println(p4 release)
    println(p6 release)
  }
}

Should work as expected, give it a try…

Advertisements

6 thoughts on “Scala Beauty – Fun with Logic

  1. I’m not sure the use of non-ASCII symbols are particularly helpful when used in source code intended to teach newbies. In fact, they are more likely to confuse the hell out of them as they spend half an hour looking for the Φ key on their keyboard.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s