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

14 comments:

Dean Wampler said...

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

Unknown 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

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

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

Unknown 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?

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

tutor said...

心理學】控制命運的自證預言心理學
JasChan, 2 months ago 1 min read 128
世界真的有「想成為什麼就變成什麼」的概念嗎?社會心理學(sociopsychology)多年的論證告訴你:這種看似離地的現象確實存在,而且不需要花費你一分錢,這種現象我們稱為—自證預言(self-fulfilling prophecy)。但究竟要如何做到呢?是不是要擁有強大的心理學知識或專業的心理學家才能自主的控制命運?Tutor Circle尋補接下來為大家講解一下自證預言這個心理學概念。


1. 什麼是自證預言?
圖片來源:尋補Blogger Jas Chan

自證預言其實是一個循環
自證預言其實是一個循環
首先,相信大家或去也有以下類此的經驗:小時候被一位老師稱讚過自己的中文文筆很好,這句話一路印在腦海裡,你深深相信自己的中文能力比起其他科目也要好,結果在往後的考試和人生中,你對自己的中文能力也充滿把握;又或者,你曾經被朋友當眾取笑過你的英文口音,自此你就不斷質疑自己的英文說話能力,縱使在未來遇上很好的練習機會,你也因為自己搖擺不定的信念而放棄嘗試。這正正是著名心理學家Robert K. Merton 於1948年所提出的自證預言現象。人們會對自己有一系列期望或預測,基於人們都是先入為主的動物,我們會潛移默化地作出相應的行動,去盡可能實現或加強這些期望或預測。簡單來說這心理學的理論就是我們的信念(正面或負面)會影響我們的行動。


2. 自證預言的驗證—畢馬龍效應
圖片來源


心理學家Robert Rosenthal的畢馬龍效應對驗證自證預言起了很大作用。
此外,美國心理學家Robert Rosenthal的畢馬龍效應(Pygmalion effect)成功驗證了自證預言。畢馬龍效應指出高期望會引申出較佳的表現,相反,低的期望會導致較差的表現。在一個心理實驗中,一群被隨機選出的學生被老師告知他們是高智商和聰明的,縱使他們的才智水平根本與其他沒有被選出的學生一樣。這實驗的結果非常驚人,被隨機選出的學生在實驗完結後,成績的確比沒被選出的學生高,而這群學生的學習能力也在不知不覺間提大大升了。



【延伸閱讀】心理學出路 – 讀心理學就一定識讀心?唔通要做讀心神探?

【延伸閱讀】香港臨床心理學家揭秘 – 關於臨床心理學家的4個問題

【延伸閱讀】外籍老師教英文 – 睇下你小朋友適唔適合!


3. 畢馬龍效應驚人的實驗結果
圖片來源

別人對自己的讚賞或批評影響我們如何自控命運,包括老師。
別人對自己的讚賞或批評影響我們如何自控命運,包括老師。
另外,對於這個實驗結果,不同的心理學家也提出了不同見解,普遍的結論也認為學生成績突飛猛進是受老師的言語影響,那些由老師說出的稱讚說話,默默在學生的腦袋中轉化為一種期望和信念:「我是一個聰明的學生,所以我必定要取得好成績!」。在自證預言的影響下,學生會因應這個信念而作出正面行為(例如努力溫習、主動向老師請教等)、避免一些與自己信念矛盾的行為(例如不專心上課、考試前一天才溫習等),一旦成績合乎期望,學生會持續加強正面行為,確保自己不與期望偏離。
flowclass補習社
補習免中介
搵補習
補習平台
補習老師

補習免中介
搵補習

Techsaga Corporations said...

A Software development company in Noida has to perform in accord with the client's engineering team for ideal results. Techsaga addresses this facet of the software development process most aggressively with our streamlined and well-planned resources.

Muskan said...

Great exploration of using Unicode symbols in Scala for mathematical expressions!
Also Read: CodeCraft Full Stack Development Strategies for Modern Applications