Scala - A pure object oriented language too

A language is purely object oriented if

• every value is an object,
• they type of every value is a class and
• all operations as method calls on objects

Scala is also a pure object oriented language. You can argue that there are exceptions like primitive types and functions which are not objects. But let's have a closer look.

Primitive types as Objects

Primitive types such as Int and Boolean are conceptually treated same as any other class in Scala. Here I will explain how Boolean can be expressed as a class rather than a primitive type.

Primitive boolean to Boolean type

Boolean can be of two types viz. true or false. Lets define a class hierarchy as follows.

Boolean is an abstract class. It has an abstract method ifThenElse as follows.

package com.techmights
abstract class Boolean {
def ifThenElse[T](i: =>T,e: =>T):T
}

The ifThenElse method takes two arguments i and e. i represents the value to be returned when the if condition is satisfied and e represents the else value i.e.

if(condition)
i
else
e

Which can be expresses here as

condition.ifThenElse(i,e)

Where condition is a subtype of Boolean. Let's define the True and False objects. Both these objects are Boolean, therefore will extend abstract class Boolean and will provide the definition of ifThenElse method as follows.

object True extends Boolean{
    def ifThenElse[T](i: =>T,e: =>T) = i
}

object False extends Boolean {
    def ifThenElse[T](i: =>T,e: =>T) = e
}

The implementations are straight forward. The True object returns the true value and False object returns the false(else) value.

There are certain operations that can be performed on Boolean values viz. AND(&&), OR(||), NOT(!), EQUAL(==), NOT_EQUAL(!=) etc. As these operations are common for True and False, hence we can add these to the abstract class Boolean.

The truth table for && is as follows.

A	B	Result
True	True	True
True	False	False
False	True	False
False	False	False

From the above table, we can create a summary table as follows.

A	B	Result
True	x	x
False	x	False

The summary table says that  

• when && method is called on a True object, then the result is the argument passed i.e. x
• when && method is called on a Flase object, then the result is False regradles of the argument passed

Based on the above explanation, we can add && method as follows.

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T  
  def && (x: =>Boolean) = ifThenElse(x,False)  
}

Similarly || for True will always be True and for False, it will be the argument passed. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
}

For negation(!), when it is called on True, it should return False and vice versa. Note that negation is a unary operation and hence no argument required. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
  def unary_! :Boolean = ifThenElse(False,True) 
}

In case of comparison(==) when True==x, then the result depends on x. But when False==x then result is True if x=False else otherwise i.e. !x. The != operation will be opposite of ==. Therefore,

abstract class Boolean {
  def ifThenElse[T](i: =>T,e: =>T):T
  
  def && (x: =>Boolean) = ifThenElse(x,False)
  def || (x: =>Boolean) = ifThenElse(True,x)  
  def unary_! :Boolean = ifThenElse(False,True)
  def ==(x: =>Boolean):Boolean= ifThenElse(x, x.unary_!)
  def !=(x: =>Boolean):Boolean= ifThenElse(x.unary_!,x)
}

This completes the Boolean class and we learnt to represent a primitive type as an object in Scala with all its operations.

Binary Search Tree in Scala

In this post we are going to make a structure which is similar to Binary Search Tree (BST).

Each node contains an integer element and two child nodes. All the nodes having value less than the current node will be on the left and all nodes having value greater will be on right. If a node doesn't have any child then it will have empty node at that place.

From the description, we can deduce that there are two types on integer nodes - Empty and Non Empty. The operations can be to add a new node or to check if a node exists in the current tree. Hence lets define an abstract class IntNode with these two abstract functions.

IntNode.scala

abstract class IntNode {
  def incl(x: Int): IntNode
  def contains(x: Int): Boolean
}

This abstract class will have its first concrete implementation as Empty node. This is empty node, hence its contains function will always return false. The incl function will take an integer value and create a non-empty node. The code is as follows.

Empty.scala

class Empty extends IntNode {
  def incl(x: Int): IntNode = new NonEmpty(x, new Empty, new Empty)
  def contains(x: Int): Boolean = false
  override def toString = " . "
}

Another concrete implementation of IntNode is NonEmpty node which is as follows.

NonEmpty.scala

class NonEmpty(elem: Int, left: IntNode, right: IntNode) extends IntNode {

  def incl(x: Int): IntNode =
    if (x < elem)
      new NonEmpty(elem, left incl x, right)
    else if (x > elem)
      new NonEmpty(elem, left, right incl x)
    else
      this

  def contains(x: Int): Boolean =
    if (x < elem)
      left contains x
    else if (x > elem)
      right contains x
    else
      true

  override def toString = " { " + left + elem + right + " } "
}

The toString function is overridden to print Empty node as dot(.) and non-empty node in the order of left, element and then right node(s).

Let's first take the contains function. It compares the element x passed to it with current node element and takes a decision based on the BST property. If an element doesn't exists in the tree then it recursively reaches the Empty node of which the contains function returns false.

The incl function also uses the property of BST to add a new node. If the element already present in the list, then it avoids duplication by returning this reference. Otherwise it accordingly reconstruct the tree.

The sample Main class and its output are as follows.

Main.scala

object Main extends App {

  val t1 = new Empty
  println("t1 = " + t1)

  val t2 = t1 incl 4
  println("t2 = " + t2)

  val t3 = t2 incl 1
  println("t3 = " + t3)

  val t4 = t3 incl 5
  println("t4 = " + t4)

  val t5 = t4 incl 2 incl 7 incl 0
  println("t5 = " + t5)

  println("t1 contains 4 = " + (t1 contains 4))
  println("t2 contains 4 = " + (t2 contains 4))
  println("t5 contains 4 = " + (t5 contains 4))
  println("t5 contains 0 = " + (t5 contains 0))
  println("t5 contains 9 = " + (t5 contains 9))

  val t6 = t5 incl 1
  println("t6 = " + t6)

}

Output

t1 =  . 
t2 =  {  . 4 .  } 
t3 =  {  {  . 1 .  } 4 .  } 
t4 =  {  {  . 1 .  } 4 {  . 5 .  }  } 
t5 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 
t1 contains 4 = false
t2 contains 4 = true
t5 contains 4 = true
t5 contains 0 = true
t5 contains 9 = false
t6 =  {  {  {  . 0 .  } 1 {  . 2 .  }  } 4 {  . 5 {  . 7 .  }  }  } 

Higher Order Functions in Functional Programming

Function programming paradigm treats functions as its first class citizens which means

• you can pass a function as an argument to another function
• you can return a function from a function and
• you can compose a function inside another function and assign it to a variable too just as we do with any other value or reference type.

This provides a flexible way to compose programs.

To build up this concept, consider a summation function which gives sum of elements in the range a to b.

This can be written recursively as follows.

def summation(a: Int, b: Int): Int = {
    if (a > b) 0
    else a + summation(a + 1, b)
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

There are 2 problems with the above piece of code.

• The parameter b doesn't change, still I have to pass it to all the recursive calls as summation requires 2 parameters.
• The summation function is not tail recursive. If the range of a and b is huge then the piece of code may result into stack overflow.

If you think, summation is internally running a loop from a to b. So the new code with tail recursivenes will look like,

  def summation(a: Int, b: Int): Int = {

    def loop(a: Int, acc: Int): Int = {

      if (a > b) acc
      else
        loop(a + 1, a + acc)

    }

    loop(a,0);
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

Note that you must always specify the return type of the recursive function, otherwise the Scala compiler will not be able to infer the type, as while doing the type inference it will end into a never ending recursive calls.

Taking this a step ahead, the requirement might be to

• find sum of squares of numbers between a and b
• find sum of cubes of numbers between a and b
• find sum of factorials of numbers between a and b

The final thing is to do sum of numbers between a and b, just the function f to be applied on the number is changing. This can be expressed mathematically as

where f can be
f(x) = x*x
f(x) = x*x*x
f(x) = factorial(x)

So the summation function will take one more argument f i.e. the function to be applied on each a before adding it to the accumulator. The function f takes an Int argument and returns an Int value. Hence the summation function can be redefined as,

  def summation(a: Int, b: Int, f: Int => Int): Int = {

    def loop(a: Int, acc: Int): Int =
      if (a > b) acc
      else
        loop(a + 1, f(a) + acc)

    loop(a, 0);
  }                                               //> summation: (a: Int, b: Int, f: Int => Int)Int

Summation of factorial of numbers between a to b - Define a function fact in tail recursive way to find factorial of a number and then pass it  to summation as an argument.

  def fact(a: Int): Int = {

    def f(a: Int, acc: Int): Int =
      if (a == 0) acc
      else f(a - 1, a * acc)

    f(a, 1)
  }                                               //> fact: (a: Int)Int

  summation(3, 5, fact)                           //> res0: Int = 150

Lambda expressions - For small functions, like square, cube of a number we can define the functions inline as lambda expressions while making summation function call.

summation(1,5,x=>x*x)                           //> res1: Int = 55
summation(1,3,x=>x*x*x)                         //> res2: Int = 36

Currying the function - In Currying, a function takes only one argument and returns a value. Let's apply some currying on summation function named as summation1.

def summation1(f:Int=>Int):((Int,Int)=>Int) = {
 def FSum(a:Int, b:Int):Int = {
  
  def loop(a:Int, acc:Int):Int = {
   if(a>b) acc
   else
    loop(a+1,f(a)+acc)
  } 
  loop(a,0)
 }  
 FSum
} 

The advantage is that we can create different flavors of summation function and then call them with proper arguments when required. The illustration is as follows.

def sqrSummation = summation1 (x=>x*x)    //> sqrSummation: => (Int, Int) => Int
sqrSummation(5,7)                         //> res1: Int = 110
  
def cubicSummation = summation1 (x=>x*x*x)//> cubicSummation: => (Int, Int) => Int
sqrSummation(1,3)                         //> res2: Int = 14
 
def factoSummation = summation1(fact)     //> factoSummation: => (Int, Int) => Int
factoSummation(3,5)                       //> res3: Int = 150

summation1(x=>x)(1,10)                    //> res4: Int = 55

Taking currying to the advanced level - Rather than having a sub function being returned by a function, we can logically aggregate the parameters into the same function by passing them in separate groups. This will help in reusing the function.

Q. Can we have a series function which will do operation x (instead of only summation) and at the same time apply a function (e.g. square, cube, factorial) on the element before adding it to the result? Most importantly can it be designed in a reusable fashion?

The answer is yes. Following is the series function where Op is a function which takes two arguments and returns an integer value. Op can be summation, product or any other operation. The acc value can be 0 for summation or 1 for product which represents the unit value with respect to the operation.

def series(Op: (Int, Int) => Int, acc: Int)(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) acc
    else series(Op, Op(f(a), acc))(f)(a + 1, b)

The function can be used to do summation of squares of numbers between 1 to 5.

series((x,y)=>x+y,0)(x=>x*x)(1,5)               //> res0: Int = 55

The function can be used to define factorial function.

def fact (n:Int):Int =
 series((x,y)=>x*y,1)(x=>x)(1,n)           //> fact: (n: Int)Int
 
fact(5)                                   //> res1: Int = 120

Scala program for Counting change for a given amount and denominations

Problem Statement

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomiation 1 and 2: 1+1+1+1, 1+1+2, 2+2.

How to think
First of all, sort the denomination set in ascending order.

Thumb Rule = Let a is the amount for which you have to find all the possible ways from a given denominations set S. Then the number of possible ways amount a can be achieved is equal to

• number of ways the amount a-S_max can be achieved using S +
• number of ways a can be achieved using S' = S - S_max i.e. removing the max element from S

Apart from the implementation of thumb rule, check that

1. if amount is negative, then we have crossed the limit and no way possible, so return 0
2. if amount is equal to 0, then the change has achieved through this branch, hence return 1
3. if max index is out of bound, then return 0

Program
Following function takes the amount and denomination's set, and returns the count of number of possible ways of getting change for the amount.

def countChange(money: Int, coins: List[Int]): Int = {

    val sortedCoins = coins.sorted

    def getCount(amount: Int, maxIndex: Int): Int = {

      if (amount < 0) 0
      else if (amount == 0) 1
      else if (maxIndex < 0) 0
      else getCount(amount - sortedCoins(maxIndex), maxIndex) + getCount(amount, maxIndex - 1)
    }

    getCount(money, coins.size - 1)
  }

Pascal's Triangle in Scala

To understand the recursive logic of Pascal's triangle, draw a sample triangle as follows.

r,c	0	1	2	3	4	5	6
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1

Now, pick a a column(c) and row(r) value. You will find that,

(c,r) = (c-1,r-1)+(c,r-1)

The program in Scala is as follows.

Program

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }

  }

  def pascal(c: Int, r: Int): Int = {
    if (c == 0 || c == r) 1
    else
      pascal(c - 1, r - 1) + pascal(c, r - 1)
  }

Output

Pascal's Triangle
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1

Starting with Scala

Scala is the new buzz word. I call it "a better Java". It is clean and rich with syntax sugars. Following is a program to manage money objects, to do operations on it and to convert from one currency to another.

Money.scala

class Money(val amount: Double = 0, val currency: String = Money.US$.currency, val valuePerUSD: Double = Money.US$.valuePerUSD) {

  def +(that: Money) = new Money((this.amount / this.valuePerUSD + that.amount / that.valuePerUSD) * this.valuePerUSD, this.currency, this.valuePerUSD)
  def -(that: Money) = new Money((this.amount / this.valuePerUSD - that.amount / that.valuePerUSD) * this.valuePerUSD, this.currency, this.valuePerUSD)
  def ->(that: Money) = new Money((this.amount / this.valuePerUSD) * (that.valuePerUSD), that.currency, that.valuePerUSD)

  override def toString = s"$currency$amount"
}
object Money {
  lazy val INR = new Money(currency = "INR", valuePerUSD = 60)
  val US$ = new Money(currency = "$", valuePerUSD = 1)
  lazy val SR = new Money(currency = "SR", valuePerUSD = 4)
}

Main.scala

object Main {
  def main(args: Array[String]) = {
    println("** Welcome to Scala Money Manager **")

    val _120INR = new Money(120, Money.INR.currency, Money.INR.valuePerUSD)
    println("My Balance = " + _120INR)
    println("My Balance in USD = " + (_120INR -> Money.US$))

    //Different ways of creating Money objects
    val _0Dollars = new Money
    val _10Dollars = new Money(10)
    val _0INR = new Money(currency = Money.INR.currency, valuePerUSD = Money.INR.valuePerUSD)

    println("Adding $10 to my balance, therefore My Balance = " + (_120INR + _10Dollars))
    println("Adding $12 and $8, converting result into INR = " + ((new Money(12) + new Money(8)) -> Money.INR))
    println("INR12 + SR10 = " + (new Money(12, Money.INR.currency, Money.INR.valuePerUSD) + new Money(10, Money.SR.currency, Money.SR.valuePerUSD)))

    val _1SaudiRiyal = new Money(1, Money.SR.currency, Money.SR.valuePerUSD)
    println("SR1 + INR120 + $2 in INR = " + (_1SaudiRiyal + _120INR + new Money(2) -> Money.INR))
  }
}

Output

** Welcome to Scala Money Manager **
My Balance = INR120.0
My Balance in USD = $2.0
Adding $10 to my balance, therefore My Balance = INR720.0
Adding $12 and $8, converting result into INR = INR1200.0
INR12 + SR10 = INR162.0
SR1 + INR120 + $2 in INR = INR255.0

Database Transactions, Lock Management and Deadlock - Part 3

Deadlock

Consider the following example.

T1	T2	Comment
S(A)		Shared lock granted.
R(A)		T1 reads values of A.
	S(A)	T2 asks for shared lock. It can be granted.
	R(A)	T2 reads values of A.
	X(A)	Cannot be granted because T1 holds a shared lock.
X(A)		Cannot be granted because T2 holds a shared lock.
DEADLOCK

Such a cycle of transactions waiting for locks to be released is called a deadlock. Clearly, these two transactions will make no further progress. Worse, they hold locks that may be required by other transactions. The DBMS must either prevent or detect (and resolve) such deadlock situations.

Deadlock Prevention

In deadlock prevention the transactions are processed in such a way that it never leads to a deadlock. Hence when deadlock prevention is used then deadlock detection mechanism is not required.

We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions. 

One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction's priority, that is, the oldest transaction has the highest priority.

If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:

·         Wait-die: If Ti has higher priority, it is allowed to wait; otherwise it is aborted.

·         Wound-wait: If Ti has higher priority, abort Tj; otherwise Ti waits.

In the wait-die scheme, lower priority transactions can never wait for higher priority transactions. In the wound-wait scheme, higher priority transactions never wait for lower priority transactions. In either case no deadlock cycle can develop.

Deadlock Detection

Deadlocks tend to be rare and typically involve very few transactions. This observation suggests that rather than taking measures to prevent deadlocks, it may be better to detect and resolve deadlocks as they arise.

In deadlock detection the transactions are allowed to happen without any prior planning and the system is periodically checked for deadlocks. If deadlock is detected then some of the transactions are aborted because "abortion of transaction(s) is must to resolve a deadlock".

The lock manager maintains a structure called a waits-for graph to detect deadlock cycles. The nodes correspond to active transactions, and there is an arc from Ti to Tj if (and only if) Ti is waiting for Tj to release a lock. The lock manager adds edges to this graph when it queues lock requests and removes edges when it grants lock requests.

T1	T2	T3	Comment
X(A)			Exclusive lock granted.
W(A)
	X(B)		Exclusive lock granted.
	W(B)
		X(C)	Exclusive lock granted.
		W(C)
X(B)			Wait. T2 holds exclusive lock on B.
	X(C)		Wait. T3 holds exclusive lock on C.
		X(A)	Wait. T1 holds exclusive lock on A.
DEADLOCK

The corresponding waits-for graph is

The waits-for graph is shows a cycle, which indicate deadlock. A deadlock is resolved by aborting a transaction that is on a cycle and releasing its locks; this action allows some of the waiting transactions to proceed.

How frequently you check the graph for deadlock depends upon activity and urgency of the transaction. If an urgent query is executing and the results are not coming then check for deadlock detection every 2 minutes.