Saturday, November 7, 2009

Programming in Scala: Chapter 21 - Implicit Conversions and Parameters

Some notes from chapter-21, Programming in Scala.

Implicits are a way of "adding new methods" to a class. With implicits, you can make one object behave like other.

They are defined like regular methods except that they start with a keyword "implicit".

On finding something like x op y, compiler checks to see if op is defined on x or if there is an implicit converter available such that object returned from convert(x) has op and it replaces x with convert(x).

Rules - Here are 4 rules that govern implicit conversions.

1.Marking Rule: Only definitions marked implicit are available.
Scope Rule: An inserted implicit conversion must be in scope as a single identifier, or be associated with the source or target type of the conversion.

"Single Identifier" means compiler will not try to use someVariable.convert, it has to be available as a single identifier. One usual practice is to define all the implicits in an object Preamble and client code can simply do "import Preamble._" to make all of them available.
However there is one exception to this rule, the compiler will also look for implicit definitions in the companion object of source or target type.For example if you pass a Dollar to a method that expects Euro, compiler will look inside companion objects of Dollar and Euro to see if there is any implicit available to convert Dollar to Euro.

2.Non-Ambiguity rule:
If there are two or more implicits available to do same conversion, compiler will raise an error.

3.One-at-a-time Rule: The compiler will never try to rewrite x + y into convert2(convert1(x))

4.Explicit-First rule: x + y will never be re-written if + is already defined for x.

Note: Usually name of the implicit does not matter.


Where are implicits tried?

They are tried in three places.

1.conversion to an expected type: For example you have a String and you might want to pass it to a function that expects RandomAccessSeq[Char].

2.conversion of the receiver of a selection: If a method is called on an object that doesn't have it for example x + y, if x of a type that doesn't define + then implicits will be tried. One very interesting example of this is in supporting the syntax like.. Map(1 -> "one", 2 -> "two", 3 -> "three"), -> is a method in a class named ArrowAssoc and scala.Predef contains an implicit to do the conversion. Its defined as follow...
package scala
object Predef {
class ArrowAssoc[A](x: A) {
def -> [B](y: B): Tuple2[A, B] = Tuple2(x, y)
}
implicit def any2ArrowAssoc[A](x: A): ArrowAssoc[A] =
new ArrowAssoc(x)
...
}

This kind of "rich wrappers" pattern is pretty common in libraries that provide syntax-like extensions to the language.

3.implicit parameters:
You can define method like
def meth(a: A)(implicit b:B, c:C)

You can call meth like a regular method by providing all the parameter list, or you can optionally leave out the whole implicit parameter list as following.
meth(x)

In this case, compiler will look for implicit vals defined of type B,C to insert automatically. So one should make them available like..

implicit val bVal = new B..
implicit val cVal = new C..


As a style rule, it is best to use a custom named type in the types of implicit parameters. For example it is not advised to have following..
def meth(a: A)(implicit b: String)
because String is a very common type and there might be implicit values available of type String that you don't know about so you're better off wrapping the String in a custom type.

View bounds:
Look at the following method...
def maxListImpParm[T](elements: List[T])
(implicit orderer: T => Ordered[T]): T =
elements match {
case List() =>
throw new IllegalArgumentException("empty list!")
case List(x) => x
case x :: rest =>
val maxRest = maxListImpParm(rest)(orderer)
if (orderer(x) > maxRest) x
else maxRest
}

Since orderer is implicit, it can be left out in the method body at both the places and following code means the same..
def maxListImpParm[T](elements: List[T])
(implicit orderer: T => Ordered[T]): T =
elements match {
case List() =>
throw new IllegalArgumentException("empty list!")
case List(x) => x
case x :: rest =>
val maxRest = maxListImpParm(rest) //(orderer) is implicit
if (x > maxRest) x //orderer(x) is implicit
else maxRest
}


Notice, in the second definition, there is no mention of orderer and hence the name does not matter. Since this kind of pattern is very common in scala, scala lets you leave out the name of this parameter and shorten the method header by using a view bound.. above method with new signature will be written as..

def maxListImpParm[T <% Ordered[T]](elements: List[T])

Here [T <% Ordered[T]], means "Any T can be used as long as there is an implicit available to convert it to Ordered[T]". By default an identity implicit converter is always available that would convert Ordered[T] to Ordered[T].


Debugging the Implicits:
Sometimes you might wonder why the compiler did not find an implicit conversion that you think should apply. In that case it helps to write the conversion out explicitly. If that also gives an error message, you then know why the compiler could not apply your implicit.

If above works, then you know one of the other rules(such as scope rule) is preventing the use of converter by the compiler.

When you are debugging a program, it can sometimes help to see what implicit conversions the compiler is inserting. The Xprint: typer option to the compiler/interpreter is useful for this. If you run scalac with this option, then the compiler will show you what your code looks like after all implicit conversions have been added by the type checker.


Caution:
As a word of warning, implicits can make code confusing if they are used too frequently. Thus, before adding a new implicit conversion, first ask whether you can achieve a similar effect through other means, such as inheritance, mixin composition, or method overloading. If all of these fail, however, and you feel like a lot of your code is still tedious and redundant, then implicits might just be able to help you out.

Thursday, November 5, 2009

Programming in Scala: Chapter 20 - Abstract Members

Some notes from chapter-20 of the book "Programming in Scala".

There can be 4 kind of abstract members in a class/trait:
vals (defined using val)
vars (defined using var)
methods (defined using def)
types (defined using type)

Classes can be abstract and traits by definition are abstract, but neither of these are abstract types in scala. An abstract type in scala is always a member of some class/trait.

A parameterless abstract method can be overriden by a val with same name but not viceversa, Why?
"val x" means, once its defined in a concreteObject, then client should get same value whenever concreteObject.x is called, if a parameterless method could override "val x" then that implementation may be such that concreteObject.x is not always the same.

An abstract var:
When you declare a var, you implicitly declare two defs, setter and getter. Notice that following two are same...
trait A {
var x: Int
}


and

trait A {
def x: Int
def x_=: Unit
}


Hence an abstract var can be overriden by a var or two defs.

Initializing abstract vals:

trait A {
val x: Int
val y = { require(x > 0); 1/x }
}


we can create an instance of the anonymous class that mixes above trait by following expression

new A { val x = expr }

Here expr will be evaluated only *after* the class is initialized, during initialization x will have its default value which is zero. So, following fails..

scala> val a = 20
a: Int = 20

scala> new A { val x = 2 * a }
java.lang.IllegalArgumentException: requirement failed
at scala.Predef$.require(Predef.scala:107)
at A$class.$init$(:7)
at $anon$1.(:8)
at .(:8)
at .()
at RequestResult$.(:3)
at RequestResult$.()
at RequestResult$result()
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Meth...


To overcome this, we have two ways

Pre-Initialized fields:
It lets you initialize a field of a subclass before the superclass is called. To do this simply place the field definition in braces before the superclass constructor. So this succeeds...

scala> new { val x = 2 * a } with A
res8: java.lang.Object with A = $anon$1@14d6015


pre-initialized fields are not restricted to anonymous classes, they can be used with objects and named classes also as in following example..

scala> object B extends { val x = 2 * a} with A
defined module B

scala> B.x
res9: Int = 40


Note: Because pre-initialized fields are initialized before the superclass constructor is called, their initializers can not refer to the object that is being constructed.

Lazy vals:
If you prefix a val definition with lazy modifier, the initializing expression on the right hand side is evaluated the first time the val is used. So we can redefine trait A as following..
trait A {
val x: Int
lazy val y = { require(x > 0); println("init x"); 1/x }
}


this works now...

scala> new A { val x = 2 * a }
res12: java.lang.Object with A = $anon$1@1b8737f


Caution: if the expression on the right hand side of lazy val produces a side effect, it will happen only once. As soon as the expression is evaluated once, its value will be memoized.

You can neither create an instance of an abstract type nor have an abstract type as a sypertype of another class. A work around is to have an abstract factory method along with the type, whose concrete implementation can create the instances of the concrete type. And, its usually a good idea to have factory methods in separate objects.

You can have a class member and a val member with same identifier in a class. For example, following compiles without any issue.
class A {
class B
val B = 5
}


BTW, if you wanted to refer to class B, you would write A#B and not A.B

Programming in Scala: Chapter 19 - Type Parameterization

Some notes from the chapter-19 from the book "Programming in Scala".

Type parameterization allows you to write generic classes and traits in scala.

Whether a type parameter is covariant, contravatiant or nonvariant, its called parameter's variance.

The + or - symbols, you can place, before the type parameters(to make it covariant,contravariant respectively) are called variance annotations.


In general, If a classes type parameter is also one of the argument's parameter of a method, its not possible to have that parameter covariant. It is not allowed because of being unsafe. See the book for plenty of example describing why.

Methods can also declare type parameters. So we can't have unsafe thing like..
class Queue[+T] {
...
def append(x: T)
}


but, can have
class Queue[T] {
...
def append[U <: T](x: U)
}


This sort of design is called type-driven design, where the type of class/trait "guides" its details and implementation.

Liskov Substitution Principle: In type driven design: it is safe to assume that a type T is subtype of type U if you can substitute a value of type T wherever a value of U is required. The principle holds if T supports all operations that of U and require less but more than the corresponding operation in U.

Note: Queue is not a type but type constructor; Queue[String], Queue[Int] etc are types.

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








Wednesday, September 30, 2009

Discrete Maths, Lecture-15 : Generating Functions

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

This lecture covers Generating Functions(a way to represent sequences), their usage in solving some counting problems and recurrance equations.

Here are my notes...





Tuesday, September 29, 2009

Discrete Maths, Lecture-14 - Discrete Probability

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

This lecture introduces basic discrete probability, mainly the two things..

1. P(A) = #of favorable cases where A happen / total # of cases

2. Probability of A, given B has happened

P(A|B) = P(A /\ B) / P(B)

Here are my notes...



Saturday, September 26, 2009

Discrete Maths, ProblemSet#5

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

Doing this problem set makes me realize that One needs to continually practice solving counting problems to learn permutation-combination properly by heart, it really becomes confusing pretty quickly for not-so-trivial cases.

Anyway, Here are my solutions...











anonymous class in scala

Scala also supports java style syntax of defining anonymous classes. Take a look at this code snippet from Actor companion object definition in Actor.scala from scala actors library.
  /* Notice the argument of actor method, its a
* no-arg(not empty arg list)
* function that returns Unit */
def actor(body: => Unit): Actor = {
/* Here java style syntax of anonymous classes is being used.
* we're creating an instance not of Actor class but a anonymous
* subclass that is implementing a method act() which is declared
* in trait Reactor(also its evident that its not mandatory to use
* keyword override when implementing something from the trait)
* and overriding scheduler. */
val a = new Actor {
def act() = body
override final val scheduler: IScheduler = parentScheduler
}
/* also see that actor is started right here. */
a.start()
a
}

type param in method name in scala

Type parameters can be specified with methods also like in the example below...
scala> def A[a](b:a){ println(b) }
A: [a](a)Unit

scala> A[String]("hi")
hi
scala> A[String](2)
:6: error: type mismatch;
found : Int(2)
required: String
A[String](2)
^

They're being used in receive method in Actor class, lets take a look at the signature of receive
def receive[R](f: PartialFunction[Any, R]):R
The advantage is that we automatically get the type checking done to be sure that return type of receive is gonna be same as the second type parameter of the PartialFunction.

Tuesday, September 22, 2009

Discrete Maths, Lecture-13 : Counting-III

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

This lecture covers following topics..
1. Inclusion-Exclusion principle (a generalization of sum rule using same theorem from set theory)
2. Pigeonhole Principle
3. Derrangement Problem

Here are my notes...


Friday, September 18, 2009

Discrete Maths, Lecture-12 : Counting-II

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

This lecture covers generalized permutation and combinations (that basically means repetition is allowed). Though there are "formulae" presented for each case but more emphasis is(and should be) given to how we can think and solve the problems of generalized permutation and combinations using the already covered 5 principles and simple permutation/combination. The intention of this lecture is not to give you the formula but to teach you how you reach to them.

Here are my notes...




Thursday, September 17, 2009

combination formula and recursion

Today, while solving some problems in counting I tried to relate the combination formula and recursion.
The idea is, can we derive combination formula using recursion?

Let us start with a particular case.

How many ways can we make groups of 2 out of n people?

Let T(n) be the answer for n people.
Let us think wishfully and see if we can get to solution for n when solution for n-1 is known.











[n][# of pairs][pairs]
2 - A,B1(A,B)
3 - A,B,C3(A,B);(B,C);(C,A)
4 - A,B,C,D6(A,B);(B,C);(C,D);(D,A);(A,C);(B,D)

From above table, it is easy to observe that
T(n) = T(n-1) + (n-1)
We can solve this recurrence using substitution and see that
T(n) = n(n-1)/2
which is indeed (n combination 2).

How many ways can we make group of k ppl out of n ppl?

Let it be denoted by T(n,k).
Clearly, T(k,k) = 1
We can apply the process as in above case by solving for T(n,3), T(n,4) etc and easily see that
T(n,k) = T(n-1, k) + T(n-1, k-1)

Wednesday, September 16, 2009

Discrete Maths, Lecture-11 : Counting-I

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

In Summary, this lecture covers following things...
  • 5 important principles of counting(2 official and 3 unofficial ones) namely Multiplication principle, Addition principle, Counting the Opposite, Counting double and Just another principle.
  • Permutation and Combination(and its relation to Binomial coefficients)
  • Interesting observations of Pascal's triangle
  • Ways to prove theorems using counting arguments.
A general thing that always helped is that when you're solving some general case n, observe the behaviour for small values of n such as 1,2,3 etc .. this gives good insight/understanding into the problem.

Here are my notes....
Note: Unless specified otherwise, in these notes n objects implicitly mean n distinct objects.