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

11 comments:

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.

Muad`Dib said...

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...

@Muad'Dib: very interesting question.
I've tried to use "internal DSL" and always between quotes because I'm sure the term is not well defined (maybe embedded is a better name).
But if I can express the intention directly in the domain language, does it matters if I'm writing a new parser or reusing an existing one?

Gabriel C. said...

Here's what I mean when I say "internal DSL":
Building Domain-Specific Embedded Languages (1996) - Paul Hudak

Fibonacci Numbers said...

I am here to discuss a simple definition of Boolean logic as-Boolean logic is a system of symbolic logic which is used in computers.Study of mathematical operations performed on binary variables that can have only two values: true or false. It provides a set of rules called Boolean logic that are indispensable in digital computer-circuit and switching-circuit design.