CSC/ECE 517 Fall 2012/ch1 1w8 aa

From PG_Wiki
Jump to: navigation, search

Contents

Introduction

This wiki page explores the idea of mixing functional and object-oriented code. Mixing different programming paradigms is called multi-paradigm programming. There are four major paradigms:

In this wiki we explain how functional and object-oriented paradigms can be mixed. First, we explain what functional and object-oriented style programming is. Secondly, we will show how to apply functional techniques to object-oriented programming. Lastly, we discuss languages that support mixing functional and object-oriented code.

Functional Programming

Functional programming treats computation as the evaluation of mathematical functions. It is compute-centric rather than data-centric. Functional programming keeps no global state, does not use for or while loops, and mandates that data is immutable. Instead, everything is done using functions, usually functions that evaluate mathematical expressions. Each of these functions maintain no internal state and will always produce the same output given the same input.

Example Contrasting Imperitive and Functional Styles

Let's look at an example. Suppose we have a list of numbers and we want to multiply each number in the list by 2. The first approach is the imperitive style:

    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. The following code is written in a functional style.

     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.

Advantages of Functional Programming

Some advantages of this approach are:

Object-oriented Programming

Object-oriented programming (OOP) is a programming paradigm organized around interacting "objects"(usually instances of a class) rather than "actions" and data rather than logic. A basic principle of OOP is that a program consists of a list of subroutines which can perform individually.

An object-oriented programming language provides support for the following object-oriented concepts--object, class, interface and inheritance. To illustrate this idea clearly and vividly let's review the following example-- your limbs. The "Limbs" is a class. Your body has two objects of type "limbs", named arms and legs. Their main functions are controlled/ managed by a set of biological signals sent from central nervous system( through an interface). So the nervous system is an interface which your body uses to interact with your limbs. The "limbs" is a well architected class. The "legs" has a subclass which contains "left leg" and "Right leg". The "legs" is being re-used to create the left leg and right leg by slightly changing the properties of it. If the "legs" owns attributes like length, color of skin etc, then the subclass, which contains "left leg" and "right leg" in this case, automatically inherit these attributes( that is called inheritance).

We could code in object-oriented paradigm as:

 class Limbs  
 #define a class of limbs
   def initialize(limbs,length,colorofskin)
   @limbs=limbs
   @length=length
   @colorofskin=colorofskin
   end
 end
 limbs=Limbs.new("legs","100cm","white")  
 #create a new object in class "Limbs"
 class Legs<Limbs   
 #create a subclass "Legs",which belong to class"Limbs"
   def initialize(legs,length,colorofskin)
     super(length,colorofskin)
     @legs=legs
   end 
 end
 legs=legs.new("left leg") 
 #create a new object in class of "Legs"

Features of Object-oriented Programming

Advantages of Object-oriented Programming

Mixing Functional and Object-Oriented Programming

In object-oriented world, data and operations are grouped together into modular units called objects and we combine objects into structured networks to form a program. The results are depend on arguments and objects' state at method invocation time. While in functional world, the basic elements are variables in the mathematical sense and functions in the mathematical sense. Functional programming can reduce side-effects. If there is no side-effects, it means your can apply the function at anywhere freely. No matter how you apply this function, the same input arguments produce the same results.

Functional - Mathematical Functions Object-Oriented - Objects
Compact Modular
Easy to debug Easy to maintain

Overall, object-oriented programming requires more upfront design, but is easier to maintain long-term. Obviously if we apply functional programming techniques to object-oriented programming, everything can be done better--the code is easier to write, runs faster, and uses less memory.

Functional Techniques useful for Object-Oriented Programming

According to above-mentioned information, we can perform functional programming on an object-oriented programming language because: 1). object can have constant state 2). method can depend only on its arguments and context available at method definition time

Combining both these paradigms not only provide us a robust design structure, but also enable the programmers to develop solutions to complex problems quickly and effectively. One of the cornerstone of mixing 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).

Some of the basic features of Functional Programming which can be combined with Object Oriented paradigm are:

Let us now understand how each of the above feature of Functional language fits in the Object Oriented paradigm.

Lambda Calculus

Lambda calculus is the most critical basis of functional programming. A lambda expression is an anonymous expression that contain expressions and statements.Each expression stands for a function with one parameter.

Let consider the following function:

 def f(x)
 return x**2 
 print f(4)

We can use a lambda calculus to compute this expression without assigning it to a variable:

 (lambda x:x**x)(4)  

We can see that these two code snippets have the same results. It is more concise and flexible to define with lambda. The above is a pure functional approach. In order to make code more state-less and concise, lambdas can be embedded inside the object-oriented language. The below code in Python demonstrates the use of lambda in a closure:

 def fun(x):
   return x%3==0
   str=[2, 18, 9, 22, 17, 24, 8, 12, 27]
   filter(fun,str)

The above code works to find numbers which are divisible by 3. We can simplify the code by the use of lambda as following:

 str=[2, 18, 9, 22, 17, 24, 8, 12, 27]
 print filter(lambda x: x%3==0, str)

Currying

In the above information we have learned much about lambda calculus, which take care of one argument, now let me introduce you another concept called currying functions which takes in multiple arguments and returns a chain of functions with lesser number of arguments. It can be interpreted as the technique to decompose a function that takes n parameters into n functions and each of the n functions takes one parameter.

Currying is really an interesting concept. Let's take a sample code in JavaScript to understand it:

 //This is a function for calculating x+y. The difference between this function and general is that this is a currying function.
 function add(x, y)
 {
 if(x!=null && y!=null) return x + y;
 else if(x!=null && y==null) return function(y)
  { 
    return x + y;  //return a closure with parameter y for subsequent calculations
   }
 else if(x==null && y!=null) return function(x)
  {
    return x + y;  //return a closure with parameter x for subsequent calculations
   }
  }
 var a = add(3, 4);  //compute the value of (3+4) and return the value of 7
 var b = add(2);  //add(2) is equal to a function of (2+y)
 var c = b(10);  //pass 10 to y, and return the value of (2+10) which is 12

In the above sample, b=add(2) gives us a currying function of add(), which is function of y when x=2.

More interestingly, we can define a currying form of arbitrary functions.

 function Foo(x, y, z, w)
 {
  var args = arguments;
  if(Foo.length < args.length)
    return function()
   {
     return args.callee.apply(Array.apply([], args).concat(Array.apply([], arguments)));
   }
  else
    return x + y – z * w;
  }

Pattern Matching

What is pattern matching? I think all of you do know what it is, you just don't know you know it. The semantics are equally straightforward.Firstly, we evaluate the value expression, then we walk down the clauses. For each one, we see if the pattern matches the value. If so, we execute the body and end. Simply put, pattern matching is a technique to search string for the occurrence of any patterns or regularity.

Pattern matching allows you to do different calculations according to different identifier values. It looks the same with nests of "if...else" statements, as well as "switch" statements in C++ and C#. But here it is much stronger and more flexible.

You may find that there are two main types of usage of pattern matching:

For example, the following code snippets writes a message if a string contains the text Perl or Python:

 if line =~ /Perl|Python/
 puts "Scripting language mentioned:#{line}"  
 end

Next, let us consider the following sample in which a part of a string matched by a regular expression can be replaced with different text using one of Ruby’s substitution methods:

 line.sub(/Perl/, 'Ruby') # replace first 'Perl' with 'Ruby'
 line.gsub(/Python/, 'Ruby') # replace every 'Python' with 'Ruby'

Advantages of Pattern Matching:

Examples of Mixing

A number of programming languages support mixing of both functional and object-oriented code. Three of these (Scala, Ruby, and Conjure), are described in more detail below.

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. It supports mixing functional and object-oriented code.

Mixing Functional and Object-Oriented Code in Scala

Scala is a strange specimen. It is a complete blend of object-oriented and functional programming. How can this happen? The functional world advocates immutability, but the object-oriented world focuses on the state and how to change 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 . A rough translation into 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:

 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 much simpler and less verbose. Even though the above example shows an immutable collection, scala also provides mutable collections and object types in the package scala.collection.mutable.*

As can be observed, even though Scala advocates immutability, it does not restrict you from creating mutable objects. So it's the best of both worlds. Another part of the 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! Getters for name and age, equals(), and hashCode() method are automatically generated for you by the compiler. Isn't this an awesome feature?

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. Scala's compiler transforms our one line function into some anonymous inner classes when generating java byte code, allowing developers to define functions in a simple manner.

In fact, every function is an object in Scala. Scala's standard library has a number of functions which are objects themselves.

Implicits in Scala

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 or DRY (dont't repeat yourself)! Lets see how its done in Scala.

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 built into the language. Try saving the above code into a separate file and run it - It will still work. 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. Since you are splitting open the class and adding/overriding methods (in)|(to) the class, this feature is often called Monkey Patching. Because other libraries may depend on some methods which you changed, often this leads to unexpected behavior at runtime. However, Scala provides yet another feature called implicits which helps you do this better.

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.

Ruby

Ruby is another language that, like Scala, supports mixing functional and object-oriented code. It is a dynamically typed Object-Oriented Language which supports multiple programming paradigms, including functional, object-oriented, imperative and reflective. In Ruby, everything is an object, every bit of information and code can have its own properties and actions. However, Ruby’s blocks can be functional. A Ruby programmer can attach a closure to any method, which generates a functional block inside an object oriented code. A closure is a piece of code that can access the lexical environment of its definition 11.

Ruby Mixing Example

Consider the following code snippet in Ruby which uses Object Oriented concepts like Classes and functional programming concepts like lambda.

class Multiply
  def initialize(n)
    @block = lambda {|a| n * a}
  end
  def mul(a)
    @block.call a
  end
end
twoMultiplier = Multiply.new 2                     
puts twoMultiplier.mul(6)

Here,@block is a closure. When we call the class Multiply using twoAdder = Multiply.new 2 ,the initialize method is called by passing the parameter 2. Here n=2 binds itself to the block. So @block will be 2*a, that is,the closure remembers the parameter with which the initialize method was called even after the initialize method exits.

This value is used when the block is called in the add method. Thus,twoMultiplier.mul(6) will return 2*6 = 12

Functional Style Coding in Ruby Blocks

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.

Clojure

Clojure[31] is also a functional programming language, and it is a dialect of Lisp. It is not a pure functional language. Instead, it is a dynamically typed language. Just like Java it runs on JVM platform, but its syntax differs from Java. It is represented as :


(functions arguments...)


The function and its arguments are enclosed in paranthesis. It has features like immutable data structures, high-order functions, recursion, and easy and fast java interoperability.

In Clojure's model, value calculation is purely functional. Values never change. New values are functions of old. But, logical identity is well supported via atomic references to values. The value of a reference (state of an identity) is always observable without coordination and freely shareable between threads. When programs are constructed this way, functional value calculation is independent of identity-value association. This makes clojure easier to understand and test.

Example Using Functional Technique in Clojure

Consider the following functional programming example in Clojure-

(defn make-adder [x]
  (let [y x]
    (fn [z] (+ y z))))
(def add2 (make-adder 2))
(add2 4)

Here,defn make-adder [x] defines a function called make-adder.let [y x] gives a local name y for the value x. Since the scope of any local names is lexical, a function created in the scope of local names will close over their values.fn [z] (+ y z) does the addition of y and z. def add2 (make-adder 2) calls the function make-adder passing the parameter 2 and calls this as add2.Now, add2 has computed 2+z. When add2 4 is called it computes 2+4=6

Example Using Object-Oriented Technique in Clojure

The following program implements Run-Time Polymorphism which is an object-oriented programming concept.

(defmulti encounter (fn [x y] [(:Species x) (:Species y)]))
(defmethod encounter [:Bunny :Lion] [b l] :run-away)
(defmethod encounter [:Lion :Bunny] [l b] :eat)
(defmethod encounter [:Lion :Lion] [l1 l2] :fight)
(defmethod encounter [:Bunny :Bunny] [b1 b2] :mate)
(def b1 {:Species :Bunny :other :stuff})
(def b2 {:Species :Bunny :other :stuff})
(def l1 {:Species :Lion :other :stuff})
(def l2 {:Species :Lion :other :stuff})

(encounter b1 l1)
-> :run-away
(encounter l1 l2)
-> :fight

Here,defmulti is used to define multiple methods which have the same method name encounter.Depending on the parameters passed to the encounter method, one of the four methods is called. def defines each of the different species. When, (encounter b1 l1) is called, the first encounter method is called with the parameters Bunny and Lion. As a result, run-away is printed.

Summary of Languages Supporting Mixing

Each of the languages contains both functional and object-oriented features. The following table shows how each of the languages have both functional and object-oriented characterics. Not all characteristics of the languages are listed, but enough to demonstrate that the languages each have different ways of mixing object-oriented and functional techniques.

Functional Characteristics Object-Oriented Characteristics
Scala Immutable objects, the ability to pass functions as parameters, implicits, closures. Every value is a object, mutable objects.
Ruby Functional programming used in blocks. Everything is an object.
Clojure Immutable data structures, high-order functions, recursion. Objects, runtime polymorphism, multimethods.

Conclusion

In summary, functional and object-oriented programming can be successfully mixed in programs. Many functional techniques are useful in object-oriented programs. Functional programming integrated with object oriented style leads to:

Languages such as Scala, Ruby, and Clojure effectively support mixing these two paradigms, allowing programmers to create cleaner, less buggy object-oriented code.

References

Special thanks to writers of previous wiki pages (see last three references below).

  1. Wikipedia - Functional Programming
  2. Notes on programming Standard ML of New Jersey
  3. Introduction to Computing - Dickinson College
  4. Wikipedia - Object Oriented Programming
  5. More on Object Oriented Programming
  6. Understanding Ruby Blocks, Procs and Lambdas - Robert Sosinski
  7. Power of Functional Programming, its Features and its Future
  8. Mixing Functional and Object Oriented Approaches to Programming in C#
  9. Programming Paradigm
  10. Recursion
  11. Scala
  12. Scala Wikipedia
  13. Clojure
  14. Ruby
  15. Standard ML
  16. Haskell
  17. ML Family
  18. Java
  19. Python
  20. C++ Programming Language
  21. Visual Basic .Net
  22. Bagwell. Learning Scala. Available from http://www.scala-lang.org/node/1305 (2009); Accessed 24 April 2010.
  23. Bjarne Stroustrup. Multiple Inheritance for C++. 1999.
  24. Chris Smith. Programming F#. O'Reilly Media, Sebastopol, CA, 2009.
  25. Jean E. Sammet, David Hemmendinger. Encyclopedia of Computer Science. John Wiley and Sons Ltd., Chicester, UK, 2003.
  26. Jeremiah Willcock, Jaakko Jarvi, Doug Gregor, Bjarne Stroustrup, Andrew Lumsdaine. Lambda expressions and closures for C++. 2006.
  27. Lee Braine. An Object-Oriented Functional Approach to Information Systems Engineering, Department of Computer Science, University College London.
  28. Microsoft Corporation. Visual F#. Available from http://msdn.microsoft.com/en-us/library/dd233154.aspx (2010)
  29. Ph. Narbel. Functional Programming at Work in Object-Oriented Programming. ETH Zurich, Chair of Software Engineering, Journal of Object Technology, 2009. Vol. 8, No. 6.
  30. Shriram Krishnamurthi, Matthias Felleisen, Daniel P. Friedman. Synthesizing Object-Oriented and Functional Design to Promote Re-use. European Conference on Object-Oriented Programming, 1998.
  31. Stuart Hallway. Programming Clojure. Pragmatic Bookshelf, USA, 2009.
  32. O'Reilly (2009), "Programming Scala", O'Reilly Media Inc..
  33. Dave Thomas, Chad Fowler, Andy Hunt (2006) Programming Ruby, The Pragmatic Bookshelf.
  34. Philipp Halle, Lightweight language support for type-based, concurrent event processing, Lausanne, Switzerland, April 2010.
  35. Burak Emir, Object-Oriented Pattern Matching, EPFL, October 2007.
  36. Object-Oriented Programming,February 2007.
  37. CSC/ECE 517 Fall 2010/ch1 1e az
  38. CSC/ECE 517 Fall 2010/ch1 1e AE
  39. CSC/ECE 517 Fall 2010/ch1 1e bb
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox