CSC/ECE 517 Fall 2010/ch1 1e az

Programming Paradigms

Every computer program needs a style of writing which specifies how to solve a software engineering problem. This style is represented by the paradigm. Each computer program follows one or more paradigm which differs in representing the elements of a program(such as variables and objects) and the steps needed to compute a task.

Diferent paradigms are:

1. Procedural/imperative paradigms: Assembly, C, C++, Java, C#

2. Object Oriented paradigm : C++, Java, Python, Ruby, Scala, C#

3. Functional Paradigm : Lisp, Haskell, Clojure, Scala, OCaml, Ruby

4. Logic Paradigm: Prolog

Multi-Paradigm Programming

Multiparadigm refers to use of a combination of programming paradigms for solving a computer problem. Some languages subscribe strictly to a single paradigm like Assembly and C. Others like Java, C++, Scala and C# employ more than one paradigm. Every paradigm comes with its own strength and weakness and this quite motivates us to take advantage of each paradigm and use it in a manner that best fits the problem at hand.

Overview of Functional Programming

Functional programming is derived from lambda calculus which models computations as the evaluation of functions and recursions. More emphasis is laid on application of functions rather than changing the state of variables in a program. Functional programming relies heavily on recursions and it is the only way to iterate instead of loops.

How it differs from imperative programming

Imperative programming follows the Von-Neumann architecture and mainly consists of loops and usage of globa states to perform a computation. For example consider the task of computing the sum of numbers from 1 to n.

In imperative style,

       sum := 0         // global state
       for i <- 1 to n do
           sum := sum + i
           

In Functional style,

        func sum(n)        // note that sum is a function and is recursive
          if  n = 1 then
              return 1
          else
              return n + sum(n-1)

Pure and impure functional programming

Purely functional programming exhibit referential transparency [1] which does not involve any global state or I/O changes. If the same functional expression results in the same output value for the same argument x at different stages of execution , then the function is said to be pure which is devoid of any global state change. For example Haskell [2] is purely functional.

Overview of object oriented programming

Typially programs were written with a procedural view where the program's logic was given utmost importance and it follows a sequential structure. But object oriented techniques really cares about the data or objects we want to mainpulate with rather than the logic of a program. Every object contains its own state(in the form of variables) and and a number of methods to manipulate the variables.For example consider the class Add:

          class Add{
          /* Object variables */
                 private int sum = 0;
         /* Object Methods */
                 public void calculate_sum(int n){
                     int i=0;
                     while(i <= n){
                         sum = sum + i;
                         i++;
                     }
                 }
           }
      
           Add instance1 = new Add();     // instance1 is an object of type Add
           instance1.calculate_sum(100);
          

Principles of object oriented design

1. Encapsulation: Encapsulation refers to hiding the internal representation of the object from the outside view. For example algorithm to compute the calculate_sum() method may be hidden, but it will present the user with the expected results.

2. Polymorphism: Polymorphism means ability to take multiple forms. For example an operation may exhibit different behaviour at different instances. Consider the operator '+', for numbers it will generate the sum, but for strings it will produce a third string which concatenates the input strings.

3. Inheritance: Inheritance involves base and derived classes with derived class inheriting all the methods and states frm the base class. Inheritance basically forms a hirerachy. For example if shape is an object, then objects square, rectangle, circle all derive the same characteristic as shape does.

Functional + OOP code

Functions as Objects

One of the cornerstone of functional and object oriented code is treating functions as objects.It means that we can pass functions as arguments, store it and return them from other functions. This is highly useful in an user interface code where it can be used as call back functions which get called when an event occurs( in event driven programming)

An example in Scala [3]:

 Object Timer{
   def  action(callback() : () => unit){              // callback() is the function passed as an argument
        while( some condition)                                                            
        { 
           callback();
           Thread.sleep(3000)
        }
    }
    def event(){                                      //  event is the method which tells what to do 
        /* process the event here
        
        */      
    }
       
 }

Another example of functional concept in object oriented design is the concept of blocks especially in Ruby. Blocks are basically nameless functions which can be passed to a function and then that function can invoke the passed in nameless function. This is a common style called higher order function style among languages that handle functions as first class objects. Basically blocks can be designed for loop abstraction and lets the user to design their own way of iterating the values, thereby hiding the implementation details. For example if we want to iterate backwards from the end to the beginning without revealing its internal implementations, we could implement the loop logic inside the block and pass it to a method or function.

Here is a Ruby implementation of block

def printlist(array,&reverse)
   array.each do |element|
      puts "array element: #{element}"
   end
   reverse.call(array)   /* Here it prints the reverse implementation of list*/
   end
 
printlist([1,2,3,4,5,6]) { |array| 
  array.reverse.each do |element| 
    puts "array element: #{element}" 
  end 
}

Next we will take a look at some of the features of Scala which supports a blend of functional and object oriented concepts in a concise manner.

Scala

Scala is a modern multi-paradigm programming language designed to express common programming patterns in a concise, elegant, and type-safe way. It smoothly integrates features of object-oriented and functional languages

Scala can be considered a very good blend of the best of functional and object oriented world. It was conceived(in 2001) and implemented by Martin Odersky who was also the author of Sun javac compiler and played a major role in the design and retrofitting of generics into Java. The latest version of Scala is 2.8 and includes a number of performance improvements over previous versions. We shall see more about the features of Scala in the following pages, but for fun, some facts!

Features

Statically Typed

Scala belongs to the family of languages which do not allow the type of variables once they have been defined. In other words, the type information of each and every variable is encoded in the generated code and the compiler makes sure, you are not doing something funny. For example, lets consider the following example,

In Ruby,

  irb(main):001:0> str="Hello World"
   => "Hello World"
   irb(main):002:0> puts str.class
   String
   irb(main):003:0> str=123
   => 123
   irb(main):004:0> puts str.class
   Fixnum

In the above example, first we define 'str' variable to be of type String and then as a number. So basically, no type information is associated with the variable at any point in the program. Hence we can easily reassociate that variable with an object/instance of a different type. This is a feature of all dynamically typed languages(like Ruby, Python, Clojure). However most of the statically typed languages such as Scala, Java, C/C++ do not allow you do so. In Scala,

 scala> var str="Hello World"
 str: java.lang.String = Hello World
 scala> str=123
 <console>:6: error: type mismatch;
  found   : Int(123)
  required: java.lang.String
        str=123

Mixed paradigm

Scala is a strange specimen. It is a complete blend of object oriented and functional programming. How can this happen? Functional world advocates immutability but object oriented world is all about state and how do you mutate it to fit your needs. Scala allows you create both mutable and immutable objects. Consider the following example,

val str: String = "Hello World"

In the first line, I am creating a immutable variable(a misnomer indeed). Roughly translating the above line to Java is below:

final String str = "Hello World"; //note the extra semi-colon

Consider the next example below,

val list: List[String] = List("Scala", "is", "the coolest", "language", "in the world!")

The same code can be written in Java as below

 List<String> mutableList = new ArrayList<String>();
 list.add("Scala");
 list.add("is");
 list.add("the coolest");
 list.add("language");
 list.add("in the world!");
 List<String> immutableList = Collections.immutableList(mutableList);

Compared to Java, Scala reduces the total number of lines you need to type and at the same time looks so much simpler and less verbose. Even though the above example shows immutable collection example, scala also provides mutable collection and object types under the package scala.collection.mutable.*

As it can be observed, even though scala advocates immutability, it does not restrict you from creating mutable objects. So its the best of both worlds. Another part of functional world is the concept of functions as 'first class members' of the language. Some of the common languages like Ruby, Python and JavaScript all incorporate this feature. In the sense you can pass around functions to methods as a parameter. Enough talking;

Let us have a class say 'Person' which has properties, name and another variable age. In Java:

class Person{
   private String name;
   private int age;
   public String getName(){
       return name;
   }
   public void setName(String s){
       this.name = s;
   }
   public int getAge(){
       return age;
   }
   public void setAge(int age){
       this.age = age;
   }
}

In Scala:

case class Person(name: String, age: Int)

This single line is equivalent to the above java code! So much cooler.. I would not be doing justice if I don't mention the fact that getters for name and age are generated. Also equals() and hashCode() method are automatically generated for you by the compiler. Isn't this an awesome feature? No wonder Scala is considered a beautiful and high level language. Now assume we have a list of persons and we want to filter out all the persons who are of age 23. How would you do that in Java?

 List<Person> persons; //has a bunch of person objects in it.
 List<Person> twentyThree = new ArrayList<Person>();
 for(Person p: persons){
     if(p.getAge() == 23){
         twentyThree.add(p);
     }
 }

In Scala:

val twentyThree: List[Person] = persons.filter( _.age == 23)

That's it! In case you are wondering whats going on, filter is a method present on scala.List class and the code block _.age == 23 is a function created on the fly and passed onto the filter method. More precisely its called a closure - a functional concept which can be emulated in java only using anonymous inner classes. In case you are wondering how scala does this, scala's compiler transforms our one line function into some anonymous inner classes when generating java byte code but allows developer to define functions in a simple manner.

Infact every function is an object in scala. Scala's standard library has a number of functions which are object themselves.

Sophisticated Syntax/Features

When we say sophisticated, its really an awesome feature which is present in other functional languages like Haskell, (O)Caml and Erlang. Consider the following example,

  val name = "Jackie Chan"
  println(name.getClass) //prints out String.

Previously we saw that scala is a statically typed language and yet in the above example we don't specify what type is the variable name. In Java, you would type in the following:

String name = "Jackie Chan"

So basically in Java you specify what type the name variable is. Scala compiler is very smart in the manner that it can automatically detect the type of the variable even if you don't specify it. Consider the following example,

case class Person(name: String, age: Int)
val persons = List(
                       Person("Jackie Chan", 51), Person("Jet Li", 41),
                       Person("RajniKanth", 51), Person("Kamal Hasan", 44),
                       Person("Martin Odersky", 18), Person("Steve Yegge", 23))
//notice that you don't have to use 'new' keyword to create new instances. This is taken care of by the companion objects.

The above lines of code create a list with 6 different persons(An immutable list)

Now, as in ruby scala supports the concepts of closure. Let's see what it is.

val twentyThree: List[Person] = persons.filter( { p: Person => p.age == 3})

In the above set of lines, the code within the '{ }' brackets is a function's body. Basically what the compiler did was to create a function which takes a single argument and returns either true or false. Now that's called a high level language. Ready for more?

A Scalable Language

In almost all programming languages, there is a necessity to profile the running time of the procedures and tune its performance. The old way of doing things in Java would be:

public class Main{
public static int factorial(int x){
  if(x == 0 || x == 1) return 1
  else return x * factorial(x-1)
 }
 public static void main(String [] args){
   long beforeTime = System.currentTimeMillis();
   int result = factorial(5);
   System.out.println("Total time taken to execute factorial(5) is " + (System.currentTimeMillis() - result)+"ms");
   System.out.println("factorial(5) = " + result);
 }
}

However, if you want to find out the execution time of some other method, you would have to type in all the above lines again. So much for code re-use! Lets see how its done in Scala. Hold on to your seats...

object Main{
 def main(args: Array[String]){
   def factorial(x: Int):Int = x match{
     case 0 | 1 => 1
     case _ => x * factorial(x-1)
 }
 import System.currentTimeMillis
 def timeIt(msg: String = "Time to execute is: ")(func: => Unit){
   val before = currentTimeMillis
   func
   println(msg + (currentTimeMillis - before) + "ms")
 }
 timeIt("Total time taken to execute factorial(5) is "){
     val result = factorial(5)
     println("factorial(5) = " + result)
 }
}
//would print: factorial(5) = 120
// Total time taken to execute factorial(5) is 1ms

That's not right! The function timeIt looks like a feature inbuilt into the language. Turn your disbelief into amazement;save the above code into a separate file and run it. Infact using this feature, it is possible to build powerful DSL languages which can run at full speed on JVM.

Ruby allows you to add new methods to objects. This feature is often called as Monkey Patching because you are splitting open the class and adding/overriding methods (in)|(to) the class. Often this leads to unexpected behavior at runtime because, other libraries including into build path may depend on some methods which you changed. Scala provides yet another feature called implicits.

In Java, String class is final so there is no way you can add new methods to it. But with implicits you can do more! Suppose you have some text in memory and you know it represents a number. But in Java the usual way to convert string to int is to do a Integer.parseInt(string) which seems so unnecessary. Let us make our lives easier...

 implicit def strToInt(str: String) = new {
   def asInt = Integer.parseInt(str)
 }
 val str = "1234"
 println(str.asInt * 3) //prints out 3702

The above code gives us an impression as if String class has gained new 'asInt' method. Can static object oriented languages do this? No! Infact scala cheats by calling our implicits to convert it into a different object as and when needed.

The above functionalities are purely object oriented, yet they are safe. They don't pollute the global namespace unlike Ruby or Python

Broad Classification of Functions

Predicate

It is a function which receives an object as argument and either returns true or false. They are useful in a number of situations. Suppose you had a list of integers and you wanted to filter out all odd numbers you could apply the predicate on every element in the list and

• If the predicate returned true, add it to the new list
• else ignore the current entry and try next.

scala> val numbers = 0 to 20
numbers: scala.collection.immutable.Range.Inclusive with  scala.collection.immutable.Range.ByOne = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
scala> val evenNumbers = numbers.filter( _ % 2 == 0)
evenNumbers: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

Closure

A function which does some operation on an object but does not return any result. In otherwords, the return type of closure is void. Say we have a list of strings and we need to print them all to the console; we can do it the following way:

scala> val strs = List("print", "all", "to", "console")
strs: List[java.lang.String] = List(print, all, to, console)
scala> strs.foreach(println) //println == System.out.println
print
all
to
console

• foreach is a method which is executed for every element present in the list.
• str.foreach(println) - Now, this is getting little confusing. Whats println doing without any arguments? Scala's compiler is intelligent enough to determine that println takes in a single argument and so allows us to skip specifying it.

Transformer

A function which recieves an entity/object and returns an another object(possibly of different type). Infact both predicate and a closure are transformers. To understand more what a transformer is, let us change the case of all the strings in a list.

In Scala:

  val list = List("Scala", "is", "the coolest", "language", "in the world!")
scala> list.map(_.toUpperCase)
res5: List[java.lang.String] = List(SCALA, IS, THE COOLEST, LANGUAGE, IN THE WORLD!)

Here

• map is scala.List's method which takes in a function as a parameter and for every element in the list invokes the function. The result returned by the function is added to a new list.
• _.toUpperCase is the transformer function upcasing all the strings.

Currying

Excellent tutorial here: [4] Named after its inventor 'Haskell Curry', it is a way of converting a function which takes multiple arguments, into a function with lesser number of arguments. Theory is always boring or we feel so. Let's jump right in and work out an example. Consider a simple function which adds two numbers.

def add(x:Int)(y:Int) = x + y

Now assume you want to create a function which will add '5' to all its input and return the sum. Can you re-use the code above? Currying works great in these scenarios..

val add5ToInput = add(5) _  // the '_' is to tell the compiler to create a curried version of the above function.
println(add5ToInput(10))  //surprise surprise - prints 15!

So basically what happens is that compiler creates an intermediate function which always has 5 as the first parameter. So when we say add5ToInput(10) in reality, it inturn calls add(5)(10). So currying basically helps us reduce the total number of parameters which needs to passed to functions and in turn helps re-use code in a functional way!

Pattern Matching

also see [5] Yet another unique feature of functional programming languages is the concept of pattern matching. Let us see what pattern matching is all about. Continuing our previous example of Person objects, let us write some code to guess the profession of a person based on his name.(I know it sounds lame..)

def guessProfession(p: Person) = p.name match {
       case "Jackie Chan" | "Jet Li" => "Martial Artist and Actor"
       case "RajniKanth" | "Kamal Hasan" => "South Indian Actor"
       case "Martin Odersky" | "Steve Yegge" => "Famous Programmer"
       case _ => "I don't know %s".format(p.name)
   }

val p = Person("Kovalan Venkatesan", 24)
val p1 = Person("Martin Odersky", 31)
println(guessProfession(p)) //prints I don't know Kovalan Venkatesan.
println(guessProfession(p1)) //prints "Famous Programmer"

As you may have noticed, the above example is very similar to switch statements in imperative languages such as C, Java. However, it is more powerful and extensible. Why?

1. In both C and Java only numeric types can be used in switch statements.(including enums which are simply names mapped onto integers). In Scala you can use almost use anything you want. Infact scala supports custom extractor patterns, whose scope is beyond this text. Please consider visiting scala resources to learn more.
2. The cases do not allow fall through. In Java and C, you have to manually type 'break' after the end of every case. Scala does not have any 'break' nor 'continue' keywords(shocking?)

A purely object oriented person may argue that we could use Visitor Pattern to do the same. That is true, but how many lines of code would you have to write to accomplish the same functionality? Wanna guess?[6]

More explanation of case statements:

• 'match' is equivalent to switch keyword in C, C++ and Java.
• 'case' keyword signifies the beginning of the particular case.
• The '_'(underscore) signifies many things in scala. When we say "case _ => ", it is equivalent to the 'default' keyword in C/Java.

Handling exceptions - Scala way!

In Java, exception matching is considered verbose and ugly. To open and write a file,

try {
   File file = new File("/tmp/sample.txt");
   PrintStream printStream = new PrintStream(file);
   printStream.write("something".getBytes());
} catch (FileNotFoundException e) {
   System.out.println("Unable to find the file /tmp/sample.txt");
   e.printStackTrace();
} catch (IOException e) {
  System.out.println("Unknown IO error");
   e.printStackTrace();
}

In Scala:

 try{
   val file = new File("/tmp/sample.txt")
   val ps = new PrintStream(file)
   ps.write("something".getBytes())
 }catch{
   case e: FileNotFoundException => println("Unable to find file /tmp/sample.txt")
   case IOException => println("Unknown IO error")
 }

We have just scratched the surface of Scala, but it has innumerable features which show a beautiful blend of functional and object oriented features. Scala proves we can use them both together.

Conclusion

Functional programming integrated with object oriented style leads to:

1. better understanding of program behavior as a result of immutability features 2. use of efficient recursive techniques such as tail call optimization 3. Reduction in number of lines of code

By using these techniques we utilize the best of both functional and object oriented techniques.

External Links

• [1]: http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
• [2]: http://www.haskell.org
• [3]: http://www.scala-lang.org
• [4]: http://bit.ly/16Qs6l
• [5]: http://bit.ly/3o5JA1
• [6]: http://www.artima.com/weblogs/viewpost.jsp?thread=166742