CSC/ECE 517 Fall 2010/ch1 1e az
Programming Paradigms
Every computer program needs a style of writing which specifies how to solve a specific software engineering problem. This style is represented by the term paradigm. A computer program represented by a programming language specifies a set of variables, objects and methods to solve a computational task. This task can be modeled to a level of abstraction which makes the problem more comprehensible and easier to follow before actually implementing it in a particular language. This is what paradigm refers to and the levels of abstraction depends on the type of paradigm used.
Different paradigms and the languages supported are:
- Procedural/imperative paradigms: Assembly, C, C++, Java, C#
- Object Oriented paradigm : C++, Java, Python, Ruby, Scala, C#
- Functional Paradigm : Lisp, Haskell, Clojure, Scala, OCaml, Ruby
- Logic Paradigm: Prolog
Multi-Paradigm Programming
Multiparadigm refers to use of a combination of programming paradigms for solving a computational 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. For example while C++ follows object oriented and imperative, Scala follows functional and object oriented concepts. 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. In this chapter we will focus on functional programming mixed with object oriented concepts and analyze some example languages which implements this feature.
Overview of Functional Programming
Functional programming is derived from lambda calculus which models computations as the evaluation of functions and recursions. Functional programming tries to focus on what the problem is rather than how it can be solved. In contrast to procedural style, this style avoids the usage of global states(mutable data) and nested loops. Lets look at an example. Suppose we have a list of numbers and we want to multiply each number in the list by 2, we would code in the imperative style as:
array[] = {1,2,3,4,5}
for(i=0 ; i<array.length; i++){
array[i] = array[i] * 2;
}
In the above example, array[] is a global variable. If we fail to check the array length, then a runtime exception occurs which might result in the program being crashed.
As far as functional style, there is a function called map(func,seq)(in python language) where the function 'func' is applied to each member of seq.
numbers = [1,2,3,4,5]
/* define a method called compute on each number in the list */
def compute(var):
var = var * 2
return var
/* Now call the map function */
L = map(compute,numbers)
print L // L will print [1,4,6,8,10]
Notice that there is no global data nor any nested loops and the bound checking is handled internally within the map function. The programmer is relieved of of runtime errors and thus can debug the program easily.
Pure and Impure functional programming
Functional programming comes in two flavors, pure and impure functional programming.
- Purely functional code exhibits referential transparency which does not involve any global variables, nested loops(while,for) 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 is purely functional.
- Impure functional code does not have any restrictions on global variables and nested loops. But still it has all the features of what a functional code has. Python is an example of impure functional style.
Overview of object oriented programming
Typically programs were written with a procedural view where the program's logic was given utmost importance and it follows a sequential structure.By contrast object oriented techniques defines a collection of objects where each object has a set of attributes and methods. This can be viewed similar to that of a relational database which consists of a table and each table having some set of attributes. Every object defines a number of methods, which uses the attributes to manipulate in a way that is required by the problem. This avoids the data from being modified by unauthorized users. Let's look at an example of a bank's account object which does the following:
class Account{
/* Instance variables */
private double balance = 0;
/* Instance Methods */
public double getBalance(){
return balance;
}
public void deposit_amt(double amount){
this.balance = this.balance + amount;
}
public void withdraw_amt(double amount){
this.balance = this.balance - amount;
}
}
Account user1 = new Account(); // create an instance of Account
float user_balance = user1.getbalance(); // Initially the balance is 0.0
/* Now deposit $100 */
user1.deposit_amt(100); // user's balance is $100
user1.withdraw_amt(30); // Now user's balance is $70
In the above code we have designed the banking transaction as an account object which has a private member 'balance', visible only within the current object so that a different class cannot modify the transaction. The object has two methods both of which act on the private variable and hides the complete implementation of the logic, although it can be called from outside.
Principles of object oriented design
1. Encapsulation refers to hiding the internal representation of the object from the outside view. For example algorithm to compute the calculate_interest() method may be hidden, but it will present the user with the expected results.
2. 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 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 gets called when an event occurs(event driven programming)
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
*/
}
}
In the above Scala code, when action(event) is called, the event starts executing once in 3 seconds.
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 functions 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
}
The statements between { } is a block and it gets called by reverse.call(array)within the printlist method. 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 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, an immutable version(a misnomer indeed) of str is being created . 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
foreachis a method which is executed for every element present in the list.str.foreach(println)- Now, this is getting little confusing. Whatsprintlndoing 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
mapisscala.List'smethod 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._.toUpperCaseis the transformer function upcasing all the strings.
Currying
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
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?
- 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.
- The cases do not allow fall through. In Java and C, you have to manually type
breakafter the end of every case. Scala does not have anybreaknorcontinuekeywords(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? look here
More explanation of case statements:
matchis equivalent to switch keyword in C, C++ and Java.casekeyword signifies the beginning of the particular case.- The
_(underscore) signifies many things in Scala. When we saycase _ =>, it is equivalent to thedefaultkeyword 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 mix of functional and object oriented features. Scala proves we can use them both together.
Conclusion
Functional programming integrated with object oriented style leads to:
- Better understanding of program behavior and easier debugging as a result of immutability features
- Use of techniques such as blocks and closures to implement object oriented design and reduce repetitive code
- Lesser complexity and reduction in the number of lines of code
By using these techniques we utilize the best of both functional and object oriented techniques.
References
- O'Reilly (2009), "Programming Scala", O'Reilly Media Inc..
- Dave Thomas, Chad Fowler, Andy Hunt (2006) Programming Ruby, The Pragmatic Bookshelf.
- Philipp Halle, Lightweight language support for type-based, concurrent event processing, Lausanne, Switzerland, April 2010.
- Burak Emir, Object-Oriented Pattern Matching, EPFL, October 2007.