Tuesday, July 22, 2008

Project Euler with Scala

I came across this interesting post about solving some Project Euler questions using Scala. Being a fan of Project Euler myself, I though I'll outline some of the solutions that I came up using Scala. Of course, I have taken trivial examples and the objective is more to learn Scala than to have an efficient solution. So here are some examples:
Warning: Spoilers ahead.

Problem 13.
"Work out the first ten digits of the sum of the following one-hundred 50-digit numbers". And hundred 50-digit numbers are given. (Not listing the numbers here to avoid clutter).

One possible solution:

object P13 extends Application {
val s = "..." //The numbers as a string separated by space.
val numbers = for (number <- s.split(" ")) yield new BigInt(new java.math.BigInteger(number))
val zero:BigInt = 0
println ((zero /: numbers)(_+_).toString.substring(0, 10))

Hmm, pretty simple program. We define an object which extends Application, so that we don't have to write main method. Then we initialize the variable. Next line simply parses the string and creates a List of BigInts. We have a constant 'zero' which is BigInt 0. Finally we add the numbers using fold and take first 10 characters. If you don't like /:, you can also use (numbers.foldLeft(zero)(_+_).

Problem 22.

"Using names.txt, a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score."
One possible solution:

import java.io._
import scala.collection.jcl._

object P22 extends Application {
val res = new BufferedReader(new FileReader("c:\\names.txt")).readLine
val actualNames = res.split(",") map (_.filter(_.isLetter).mkString)
val sorted = new TreeSet[String]
sorted ++= actualNames
val nums = sorted map (_.foldLeft(0)(_+_-64))
var sum: BigInt = 0
var t = 0
for (j <- nums) {
t += 1
sum += (t * j)

First, we read the lines of the file (so easy with scala). Then split based on ',' and strip off the '"'. Create a sorted set (we are using the same TreeSet from Java) and add the names. Calculate the value using fold left (Since they are upcase chars, subtract 64 to get int values). Ok, now we need to multiply each number by its position. Easy thing to do in imperative fashion. So lets do a traditional for each loop and that's it.

Update: Seth Tisue pointed out that zipWithIndex can be used to do the final calculation. The problem considers index starting with 1, so we cannot directly use zipWithIndex. However zip can be used as below:

val l = nums toList
val indices = 1 to l.size toList
l.zip(indices).foldLeft(sum)((a,b) => a + b._1 * b._2)

Problem 42

import java.io._
import scala.collection.jcl._
object P42 extends Application {
val triangular = new TreeSet[Int]
for (i <- 0 until 40) triangular += i*(i+1)/2
val lines = new BufferedReader(new FileReader("c:\\words.txt")).readLine
val nums = lines.split(",") map (_.filter(_.isLetter).mkString) map (_.foldLeft(0)(_+_-64))
println((0 /: nums)( (result, num) => if (triangular contains num) result+1 else result ))

By now this should be obvious. This example is similar to the one above. First we cache first 40 triangular numbers in an Array. Then read the file. Split lines by ',', ignore special characters (by filtering) and find the required sum (using map). I've done it in one line as it appears natural. Finally, count the triangular numbers. I used a fold, but it can be done imperatively as well.

Hope you enjoyed it. Do let me know if you think there are better ways of doing this (Not in terms of performance, but in terms of elegance or functional style).

Saturday, March 29, 2008

Design Patterns in Scala

Design patterns in Scala

The GoF Design Patterns are perhaps the most popular design fads of Software ever. However some people argue that they are more or less solutions to the deficiencies of Language itself (particularly C++/Java) and if the language is powerful enough they are redundant. Consider this excellent presentation from Peter Norvig for example.
I agree that patterns translate to quite natural and concise code in some languages, but the intend of the pattern may still be important. So lets consider some of the popular patterns in Scala - a language which like Ruby/Lisp etc reduces Pattern implementation to triviality (though its not a dynamic language!).

1. Singleton
Singleton is one of the frequently (over)used patterns. In spite of being the simplest of patterns, it is surprisingly difficult to implement a 'pure' singleton in Java. The particularly famous Double-checked locking and so on. However, in Scala it is trivial. Lets say you need to create a Registry object which is singleton. You can do that in the following way:

object Registry {
def getEntry(): Entry {
//Other fields/methods
//Create and use the singleton
val entry = Registry.getEntry

Thats it! The only difference from defining a normal class is that instead of the 'class' keyword we used 'object'. If you have to map it back to java, this is equivalent of defining a class and all its fields/methods are static.

2. Strategy
Like any language where functions are first-class objects or where closures are available, Strategy pattern is obvious. For eg. consider the 'taxing' example:

trait TaxPayer
case class Employee(sal: Long) extends TaxPayer
case class NonProfitOrg(funds: BigInt) extends TaxPayer

//Consider a generic tax calculation function. (It can be in TaxPayer also).
def calculateTax[T <: TaxPayer](victim: T, taxingStrategy: (T => long)) = {

val employee = new Employee(1000)
//A strategy to calculate tax for employees
def empStrategy(e: Employee) = Math.ceil(e.sal * .3) toLong
calculateTax(employee, empStrategy)

val npo = new NonProfitOrg(100000000)
//The tax calculation strategy for npo is trivial, so we can inline it
calculateTax(nonProfit, ((t: TaxPayer) => 0)

3. Factory
Factory pattern addresses the fact that object constructors cannot return arbitrary objects. If you call constructor of object A, you always get an object A. If you need different objects based on parameter types, you typically create a Singleton Factory. In Scala also you need to do the same thing, but in a bit more elegant manner.

object Car {
def apply(String type) {
type match {
case "Race" => new RaceCar();
case "Normal" => new NormalCar();
case _ => throw new Exception;
//And you can create cars like:
val myCar = Car("Race")
//instead of more verbose
//Car myCar = CarFactory.getInstance().createCar("Ferrari");

Basically, you can exploit the fact that what apparently looks like a constructor call to a singleton object is syntactic sugar for the "apply" method.
4. Visitor
Visitor pattern is considered harmful by many people, but still it has its value at specific cases. Lets see a typical java implementation of Visitor pattern:

abstract class Expression {
public void accept(Visitor v);

class Identifier extends Expression {
class Sum extends Expression {

class Visitor {
public void visit(Identifier i) { }
public void visit(Sum s) { }

Typical java boilerplate code as you would expect. In Scala you can achieve the same result by using pattern matching:

trait Expression {

case class Identifier(value: Int) extends Expression {
case class Sum extends Expression {

object EvalVisitor {
def visit(expr: Expression): Int = expr match {
case (Identifier(v)) => v
case (Sum(e1, e2)) => visit(e1) + visit(e2)

The pattern matching code is also more flexible.
5. Decorator
Finally consider the Decorator pattern. Since Scala supports mixins and implicit conversions, Decorator is also simple and natural. Conceptually, there are two ways you can decorate an object - by adding new functionality and extending existing functionality.
To decorate a class with new functionality, you can use implicit conversions. Consider the RichInt class in scala standard library in action:

val range1to10 = 1 to 10

which in scala translates to 1.to(10). However, there is no method "to" in Int class. So how does it work? Scala has an innovative concept called Implicits for pimping your library. In essence it is Ruby's open classes but lexically scoped. Its interesting stuff and you can read about it elsewhere. For us, it suffices to say that there is an implicit conversion in Predef [implicit def intWrapper(x : Int) : RichInt] that does the trick.
Mixins are also good for decorating your classes and extend its functionality in different dimensions. For example consider the typical Reader interface:

trait Reader {
type T
def read: T

trait SynchronizedReader extends Reader {
abstract override def read: T = synchronized(super.next)

trait BufferedReader extends Reader {
abstract override def read: T = {
//buffering code

//A concrete implementation
class FileReader extends Reader {
type T = char
def read: char = ..

//Now we can mix in stuff that we need
//Create a FileReader
val f = new FileReader
//create a fileReader which is synchronized
val syncReader = new FileReader with SynchronizedReader
//create a fileReader which is synchronized and buffered
val bsReader = new FileReader with BufferedReader with SynchronizedReader

Design Patterns are good recipes for designing software. However, most of them generally solve a language issue than a design issue. If you have a good Language patterns (at least most of them) will become trivial. For example, in a structured language, the concepts of virtual methods or classes may be a 'Design Pattern'. Once you move to a powerful language, the design patterns that you deal with will also change. They will be at a higher level of abstraction. More on it later!

Monday, February 18, 2008

To Ruby or To Scala?

I have been exploring alternate languages for JVM for some time now.
Why? Certainly not because I think the Java language is dying. Though java is devolving, it has crossed the threshold of immortality - there are way too many applications written in java and java developers can be busy just by maintaining them (and also by inventing 'frameworks' to get around the deficiency of the language like DI, AOP etc). However, I have started to realize the power of languages - maybe even to the extend of believing the Sapir–Whorf hypothesis. And finally, I still believe that the JVM is one of the best deployment platforms available today and java has lots of ready to use libraries - so I don't want to miss them as well. Luckily, there are host of new languages targeted at the JVM - Jython, JRuby, Groovy, Scala, Rhino, Clojure etc.

Finally I've narrowed down to two: JRuby and Scala. I'll try to outline the positives and negatives of both.

Ruby is an extremely dynamic language. It is dynamically (and strongly) typed. In my opinion, Ruby is the best language for internal DSLs (maybe next only to Lisp). Most of the successful Ruby projects have some kind of DSLs - like Rails, Rake, Builders etc. In a way, DSLs are nothing but flexible and easy-to-use interfaces.
Scala is a statically (and strongly) typed language. However, it has a powerful type inference system to avoid the pain of providing the types. It looks suitable for large systems, where precisely defined interfaces are required.

So looks to me that these languages have their own niche in programming. If you need RAD, clean, flexible and easy-to-use interfaces and small to medium sized applications, use Ruby. For large scale applications, where type safety is more important, use Scala without the burden of statically typed language.

Lets see how these fair in the popularity factor:
1. Popularity: Ruby is already a popular language (thanks mainly to Rails), while Scala is not (yet).
2. Ease-of-learning: Scala is probably a bit easier for Java folks. But in terms of documentation Ruby clearly excels. Scala documentation is poor, though it is improving.
3. Ease-of-writing: Ruby maybe an inch ahead as it is dynamically typed.
4. Ease-of-reading: For large systems, Scala seems to be a winner (thanks to static typing).
5. Terse: Both languages support functional/OO/imperative style, and not much difference here as well.

I would also outline some cool features of these languages:
Mixins: Both of these languages support mixins (though in Scala it is in a controlled way)
Open classes: Basically you can add methods to existing classes any time you wish. Scala also supports this through implicits.
Functional programming: Both languages has true closures, you can use functions as values etc.
Again, in Ruby you have complete freedom, while in Scala it is more controlled.

Of course, as a last point, the tool support is no way near to that in Java. The IDE support (in terms of auto completion, debugging, profiling etc) is currently mediocre in these languages. Also the performance is not that great. It could only be a matter of time, though. And btw, we needed those IDEs because Java was too bad anyway :)

To conclude, there is no silver bullet in programming languages. I guess we are moving towards polyglot programming where synergy of multiple languages will greatly help in tackling complexity.

Monday, January 28, 2008

What's a Software Engineer?

Recently there has been some debates on the definition of 'Engineer' and what Software Engineers do is not strictly engineering etc. Looks like Reg Brathwaite started it and Ravi Mohan wrote an excellent follow through. Of course not all agree with this. I'll propound my definition of what we (Software Engineers) do:
Definitely our work (or atleast for the majority) does not resemble 'Engineering'. To put things into perspective here's one definition taken from Wikipedia:
"The creative application of scientific principles to design or develop structures, machines, apparatus, or manufacturing processes, or works utilizing them singly or in combination; or to construct or operate the same with full cognizance of their design; or to forecast their behavior under specific operating conditions; all as respects an intended function, economics of operation and safety to life and property."

[Well, in my opinion that just shows how difficult it is to define a term like 'Engineering'.]

Anyway, applying that to Software, one can readily reflect that 'Engineering' is a misnomer. But then what's a more appropriate term for it? Before coming up with a new term, let's see what really makes it different from other engineering disciplines:

1. It is impossible to define software.
In most of the Engineering fields, the end product is often cleanly and precisely defined. Consider the building that you are sitting. First, it has definite attributes which can be defined beforehand. Like no.of floors, total area etc.
Now consider any piece of software that you have developed. Unless it was a small piece of code1, chances are that its definition itself changed over time. Even if it didn't, you have something which you can't define completely.

2. Software is inherently complex.
This is so well known that I won't dwell into it. The take-away is that building software is generally more complex than building a building (no pun intended). I agree with Harold Abelson that Computer Science is all about managing complexity.

3. Software development need not require 'theoretical backing'
This is the key point which generates lot of heat. In fact this is the answer (or atleast one of the answers) to questions like why is Lisp/FP not popular or why is java popular. Unlike other disciplines of Engineering, software development does not require any Mathematical knowledge. And there has been a plethora of software developers who entered this field just because of this fact and have greatly contributed to the complexity of already complex software development. Needless to say, the minority of software developers who does know theory and develops software that is inexpressibly beautiful or that is indistinguishable from art also are dwarfed to the category of 'Software Engineers'.

I hope that by now it is clear that 'Engineering' is not the right term. I would say a better term would be 'Software Hacker'.
Yes that is what we do.
And we are lucky to have among us a few 'Software Artists' as well.


1: Even this may not be true. Consider the following simple function that computes sum of two integers:

int sum(int a, int b) {
return a + b;

Even the definition of this function is tricky.
This will return the sum of two numbers as long as the sum is less than Integer.MAX_INT in java. In Ruby, this will behave differently.

Monday, January 14, 2008

What make a programming language popular?

Recently there were many posts on programming languages (for eg. see excellent posts by Steve Yegge and Mike Vanier). That made me wonder what makes a programming language popular. Popularity seems to have no relation with the quality. Does a language become popular out of luck (or its name)? Or is there something else to it. The following is my take on what make a language popular:

1. Popularity
The main factor that makes something popular is popularity itself. The statement may appear circular, but like recursive functions it is valid. When you decided to learn a new language what did you do? You would've read reviews, blogs etc. The more reviews you read the better. And if you are constrained by your employer this is doubly true. I agree that nerds don't care about popularity. But nerds aren't so common.

2. Ease of Learning
The next factor is ease of learning. This is the first thing if you leave aside popularity. Btw, this may not mean the same as intuitiveness.
Let's say you have the option to learn C++ and Python. What would you choose? (Assume that you are not worried about other factors like performance etc)

3. Ease of Reading
Interestingly ease of reading and ease of learning are not the same. For example, Perl is easy to learn (at least to get started), but exceedingly difficult to read (especially large code-bases). Some languages become popular because of the learning factor but over time lose popularity because reading (and hence maintaining) code is difficult. So this is the first major factor that determines the long term popularity of a language.

4. Terse
Smaller code means easier maintenance. The ability of easily creating abstractions (using closures, macros etc) is the main factor here. But then Lisp should be more popular than java right? But remember, this is the 4th factor. And java excels in all the above factors (maybe due to the way computer science is being taught). And many people think that if it tries to add these 'advanced' features it'll become dead. It is unfortunate that the main factor that has to be considered in choosing a language - the level of abstraction it provides - is ignored. But then as Russel said: If fifty million people say a foolish thing, it's still a foolish thing.