6/2/09

Boolean Algebra Internal DSL in Scala (aka fun with Unicode names )

In Scala, operator names can be characters from the unicode set of mathematical symbols (Sm) or other symbols (So). That can lead to interesting possibilities:


val Π = Math.Pi
def √(x:Double)=Math.sqrt(x)
val x= √(9*Π)


Here, "Π" is just another constant and "√" is a function like "q".
(To use unicode in eclipse, you have to go to Preferences->General->Workspace, and change the text encoding to UTF-16)

Another example: with the ∑ and ∏ you can have define summation and the product of a sequence as follows:


def ∑(r:Range)(f:Int =>Int)=r.reduceLeft(_+ f(_))
def ∏(r:Range)(f:Int =>Int)=r.reduceLeft(_* f(_))


And now we can write:


val s= ∑(1 to 100)(x=>x^2)
val p= ∑(1 to 100 by 2)(x=>x^2)
val y= ∏(1 to 30 by 3)(_)


Of course, I'm not advocating using Scala as a substitute of a specific mathematical tool, besides, there's already a "language with symbols" (btw, I wonder if one can make a Scala "skin" that looks like APL). I'm not sure how other languages can do this (except APL maybe?), but this goes to show the power of Scala for "internal DSL".

For a slightly more complex example, let's define an internal DSL for boolean logic, with the appropriate symbols: ¬,V,Λ,and →.


class LogicBoolean(val value:Boolean) {
import LogicBoolean.¬
override def toString=value.toString

def V(b:LogicBoolean)=new LogicBoolean(this.value || b.value)
def Λ(b:LogicBoolean)=new LogicBoolean(this.value && b.value)
def →(b:LogicBoolean)=(¬(this)) V (this Λ b)
}

object LogicBoolean {
def ¬(a:LogicBoolean)=new LogicBoolean(!a.value)
implicit def boolToLogicBool(x:Boolean)=new LogicBoolean(x)
}


The only prefix operators that can be defined in Scala are ‘+’, ‘’, ‘!’ or ‘~’, so no luck for ¬. But we if we define it as a function, we can import it and use it (almost) like a prefix op. As we want an implicit conversion from boolean to our LogicBoolean class, a companion object is the ideal place to put both. By importing all the methods in the companion, we bring the ¬ operator and the implicit conversion into scope:


import LogicBoolean._

val A=true
val B=false

println("¬A :"+ ¬(A))
println("¬B :"+ ¬(B))
println("A Λ B :"+ (A Λ B))
println("A V B :"+ (A V B))
println("A → B :" + (A → B))
println("B → A :" + (B → A))


With everything in place, with a for comprehension is very easy to print the truth tables of any complex formula (just be careful with the precedence, use parenthesis):


import LogicBoolean._

val r=List(true,false)


def expr(a:Boolean,b:Boolean,c:Boolean,d:Boolean)=
( (a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b) )

//let's print the truth table
println ("\na\tb\tc\td\t(a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b)")
for (
a <- r; b <- r; c <- r; d <- r ) println (a+"\t"+b+"\t"+c+"\t"+d+"\t"+expr(a,b,c,d))

If you run the examples you get:


¬A :false
¬B :true
A Λ B :false
A V B :true
A → B :false
B → A :true

a b c d (a Λ b) V ¬(a Λ c) ) Λ ((c V d) Λ ¬(b)
true true true true false
true true true false false
true true false true false
true true false false false
true false true true false
true false true false false
true false false true true
true false false false false
false true true true false
false true true false false
false true false true false
false true false false false
false false true true true
false false true false true
false false false true true
false false false false false

The ability to easily adapt the language to looks like the domain is one of the main selling features of languages like Lisp. Though Scala is no way like Lisp, it can go very far in the "internal DSL" direction and provides many features to make that easy.

EDIT: Something very similar in Ruby