Friday, October 30, 2009

stackable modification with traits

This post just summarises how stackable modification(modifications made to classes by stacking components on top of a class) is done in scala using traits. In traits, super calls resolve dynamically. Following is the example from "Programming in Scala" by Martin Odersky.
abstract class IntQueue {
def get(): Int
def put(x: Int)
}
class BasicIntQueue extends IntQueue {
import scala.collection.mutable.ArrayBuffer
private val buf = new ArrayBuffer[Int]
def get() = buf.remove(0)
def put(x: Int) { buf += x }
}

//trait Doubling extends from IntQueue, this
//means, it can only be mixed with a class
//that also descends from IntQueue
trait Doubler extends IntQueue {

//calls like this are not allowed in normal classes
//here super call will resolve dynamically to the
//trait/class that is in left to this one while mixing
//and gives a concrete implementation to put
abstract override def put(x: Int) { super.put(2 * x) }
}

trait Increment extends IntQueue {
abstract override def put(x: Int) { super.put(x+1) }
}

class MyQ extends BasicIntQueue with Doubler

scala> val q = new MyQ
q: MyQ = MyQ@15bf0c5

//put in Doubler is executed(because its the rightmost component),
//super.put resolves in it
//resolves to put in BasicIntQueue as that is the next concret
//put available to it's left.
scala> q.put(10)

scala> q.put(20)

scala> q.get()
res60: Int = 20 //10 was doubled

scala> q.get()
res61: Int = 40 //20 was doubled

Notice MyQ does nothing else but the mixing only, it has no body. For this we can use the following shorthand code.
val q = new BasicIntQueue with Doubling

Let us check out one more case..
scala> val q = new BasicIntQueue with Incrementer with Doubler
q: BasicIntQueue with Incrementer with Doubler = $anon$1@4cfc65

//rightmost put is applied, which is the put in Doubler, super.put
//in Doubler resolves to put in Incrementer and same in Incrementer
//resolves to put in BasicIntQueue
scala> q.put(10)

scala> q.put(20)

scala> q.get()
res64: Int = 21 //21 = 10*2 + 1

scala> q.get()
res65: Int = 41 //41 = 20*2 + 1

Monday, October 26, 2009

Notes on Tree

Some of the notes while I read about trees from chapter 9 - Trees in the book "Discrete Mathematics and Its applications" by Rosen ....




\






Saturday, October 24, 2009

How to learn a new language...

I just want to note down the path I'm following to learn a new language, In this case its scala.. but the path is pretty generic...

>Understand the philosophy behind the language, what is unique about it because if you don't understand the philosophy you can't really *think* in it and master its idioms. Scala lets you write programs in functional as well as oo paradigm. It helps to have been read books like SICP and CTM because they're the best books to get an understanding of various programming paradigms.

>Find the best book available for the language, read...*work through* it. Usually the books written by author of the language or certain person who has *written* a lot of code in that language are good. In this case, I find "Programming in Scala" by Martin Odersky very helpful.

>Usually languages(and their libraries) are open source, get their code.. build it. Read the code whatever you can because only if you can understand the code written by authors of the language then you're really getting it. It also helps learning idioms of the language and helps you thinking in the language.

>Help others, Subscribe to the language users sort of mailing list, follow the discussions there, contribute in terms of the answers to the questions or code if someone is looking for some way of doing something in that language and you know it.

>Pick up any small standard libraries(for example List, Hashtable etc), Implement it yourself without looking at its code from the source. Then compare your implementation with that from the source code by the authors(or masters of that language).. once you do it 3-4 times then you'll really begin to write good code in that language.

>Write code in it :). Maybe, you can try to write some programs that you've written earlier in some other language... since you'll already be familiar with the problem and its solution so you can concentrate on "how to do it in scala" part.

Thursday, October 15, 2009

Discrete Maths, ProblemSet#7

These are my solutions to 7th problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my solutions....







Monday, October 12, 2009

Graph Theory Notes

Some of the notes while I read about graphs from chapter 8 - Graphs in the book "Discrete Mathematics and Its applications" by Rosen ....















Discrete Maths, Lecture-20 : Cryptography

These are my notes from 20th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

This lecture covers the basic number theory background needed to understand RSA algorithm and shows analysis of how and why RSA encryption/decryption works.

Here are my notes...







Wednesday, October 7, 2009

scala tidbits

Some notes taken while reading scala code here and there...

***************************************************************************************

In functional way, even setters should return so that you can write code that looks like
return new Account().setBalance(100).setStatus("active")
instead of
Account acct = new Account()
acct.setBalance(100)
acct.setStatus("active")
return acct


***************************************************************************************

@tailrec annotation can be used with method definitions to hint the compiler that implementation is supposed to be tail recursion optimized

***************************************************************************************

I read this code in scala.collections.immutable.Stack class
def pushAll[B >: A](elems: Iterator[B]): Stack[B] =
((this: Stack[B]) /: elems)(_ push _)


It looked so cryptic. Let us see it in pieces

[B >: A] in the type parameter of pushAll means that B has to be a type that A extends.

((this: Stack[B]).. It's simply giving an explicit expected type to an expression (§6.13 of the spec). This is different than a typecast (run-time); if the expression does not conform to the expected type, it will not type-check (compile-time). Lets look at the following example..
scala> trait S
defined trait S

scala> trait T
defined trait T

scala> class A
defined class A

scala> val a = new A with T
a: A with T = $anon$1@fb92dc

scala> (a: S)
:9: error: type mismatch;
found : A with T
required: S
(a: S)
^
scala> a.asInstanceOf[S]
java.lang.ClassCastException: $anon$1
at .(:9)
at .()
at RequestResult$.(<console>:3)
at RequestResult$.(<console>)
at RequestResult$result()
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccesso...
scala>


((this: Stack[B]) /: elems)(_ push _)The Iterator doc says that '/:' is a method defined in this class which is same as foldLeft, since method name ends with ':' so (a /: b)(_ push _) is equal to b./:(a)(_ push _), which in turn is same as b.foldLeft(a)(_ push _).

..(_ push _) This is short form of ((x1: Stack[B], x2: B) => x1.push(x2)), I don't exactly know how it works.

***************************************************************************************

We can create classes that are essentially functions as follow..

abstract class Parser[+T] extends (Input => ParseResult[T])

Here Parser is a function, since it is a function it needs to contain the apply method as following(though in this case its automatically inherited from the "super" function)..

def apply(in: Input): ParseResult[T]

***************************************************************************************

Aliasing this
A clause such as “id =>” immediately after the opening brace of a class template defines the identifier id as an alias for this in the class. For example, in
class A { a =>
...
...}

a is equivalent to using this in the class. This helps in situations like following..
class Outer { outer => class Inner { ..we can use outer instead of java style Outer.this here... } }
Above mechanism is loosely equivalent to
val outer = this
except outer.method will not be valid, if method was a private member of Outer class, because outer is just another identifier, while in above case of aliasing that would be allowed.

***************************************************************************************

In pattern matching,a binary pattern like A op B is treated as op(A, B).
Similarly in type parameters, P[A op B] is equal to P[op[A, B]]

***************************************************************************************

There is an interesting way of repeating the string in scala. Look at the following code and see how a string of 5 "x" is composed using "*" on String object.
scala> "x" * 5
res14: String = xxxxx


This is possible in scala because "*" is not an operator(in fact scala *does not* have concept of operators) but just another method defined in RichString class that takes a Int and returns String. In this case scala's way of writing method call in a op b certainly looks pleasing. This reminds me that, in scala, I should *think* about the opportunities of using symbolic method names instead of alphabatic ones wherever operator style method calls can look more meaningful.

Found it through longString method of scala.util.parsing.input.Position .

***************************************************************************************
Extractors
They are a way of wrapping pretty much any data in a way so that pattern matching can be utilized without necessarily making the type of data a case class. This gives one representational independence. In an object, you implement unapply or unapplySeq to make it an Extractors. Many of the collection libraries like List, Array etc provide all the pattern matching functionality using Extractors.

**************************************************************************************

Naming the import:
You can write things like import Fruits.{Apple => McIntosh, Organge} to import just Apple and Orange from Fruits in addition to naming Apple to McIntosh so that we can use McIntosh instead of Apple throughout the code.

**************************************************************************************

Just one observation, scala.List implementation is written heavily in imperative style. May be, the philosophy here is that, what is meant by functional in this context is that for all practical purposes(the external interface used by clients) it is functional but it is OK to write the imperative internal implementation to make it more efficient.

*************************************************************************************

x op= y has a special meaning in scala, it translates into x = x op y provided
1. op= is not defined for x even after trying implicits
2. op is defined for x
3. op is precisely defined in scala specification, but in general it suffices to know its the string of one or more operator characters like +,-,*,++..

*************************************************************************************

Tuesday, October 6, 2009

Discrete Maths, Lecture-18 : Euclid's Algorithm

These are my notes from 18th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my notes...



Discrete Maths, ProblemSet#6

These are my solutions to 6th problem set of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.








Discrete Maths, Lecture-16 : Generating Functions - II

These are my notes from 16th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

Here are my notes...