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

Dean Wampler said...

Fortress has some interesting conventions for specifying math symbols using ASCII, then displaying them using unicode.

Gabriel C. said...

Thanks! I remember hearing about Fortress in a se-radio.net interview to Guy Steele. It makes a lot of sense, since Fortress is intended to be a scientific computing language.

Anonymous said...

You can do very similar in Tcl, but you would have to live with the different expression syntax based.

Just define some procs in the ::tcl::mathfunc would add some parts, and more is possible with liberal use of unknown.

See for example for what you could do:
http://wiki.tcl.tk/1189

Gabriel C. said...

@Anonymous: Interesting approach, but from what I could understand, the code is translating APL to Tcl, and "eval" the result.
In Scala, is just another static method call but with a funky name. Not as flexible but WAY much simpler :)

Anonymous said...

It's a pity that you don't reference blog posting where this idea obviously is stolen from (of course in octobre 2007 the idea wasn't new either).

Gabriel C. said...

@Anonymous: I never stole anything, didn't know that that post existed.
If I'm guilty of something is not doing enough research :)

mtnygard said...

What a sour bunch of grapes in these comments. I think this is pretty cool as an implementation, and as an example of a different way of thinking.

Why do you call this 'DSL'?

All it does it lets you write the same programs using unicode symbols rather than ASCII symbols.

Gabriel C. said...