CSC/ECE 517 Fall 2013/ch1 1w25 aras

What is Functional Programming?

Functional programming is a style of programming in which all the computations are modeled as evaluation of mathematical functions avoiding any state or mutation of data. The end result of a program depends on the input given to that function and not on the state of the program.

Examples of functional programming languages:

• Haskell
• Scala
• Erlang

The functions here are different from those that we see in imperative programming languages like C, BASIC, etc. where functions do exist but they are in the form of subroutines and not based as pure mathematical functions.

What is Object Oriented Programming?

Object Oriented Programming is a programming language model which concentrates on real world “objects” and their interactions rather than simple “actions” and on “data” rather than logic. In the OOP paradigm, objects have data fields, which are the attributes that describe the object along with some associated procedures known as functions/methods. The “objects” in OOP are primarily instances of “classes” which are defined by the programmer. These objects interact with one another through methods to eventually implement applications and computer programs. To perform Object oriented programming, one needs an object oriented programming language. Examples of well-known object-oriented programming languages:

• Objective-C
• Smalltalk
• Java
• C#

Features of Functional Programming

Pure Functions

OOP has pure functions and expressions. A function is said to be purely functional if it has no side effects with regards to memory or I/O. As a result, purely functional functions and expressions can be used for code optimization.

Following are some of the aspects of having purely functional functions:

• A pure expression can be removed without having any effect on other expressions, if the result of the pure expression is not used.
• The compiler has the freedom to reorder or combine the evaluations of expressions in a program.
• When a pure function is called with parameters that cause no side-effects, then on calling the same function with the same parameters, the same result is returned. This enables programmers to utilize caching optimizations, viz. memorization.
• The order of two pure expressions can be reversed if there is no data dependency between them. These expressions can also be performed in parallel without any interference with each other’s functioning. This property is also referred to as being thread-safe.

Most compilers for imperative languages normally detect pure functions and perform common sub-expression elimination for pure function calls. However, this is not always possible in the case of pre-compiled libraries. These libraries do not expose information, which prevents optimizations that involve those external functions.

Example:

sin(x), returning the sine of a number x
length(s), returning the size of a string s

Higher-order functions and first-class function

High-order functions are a kind of functions that take functions as input arguments and also return functions as results.

Example of higher order functions:

• Differential operator d/dx in calculus: It takes function f(x) as argument and returns a derivative of that function which is also a function.

Since higher-order functions take functions as arguments and return functions as well, they quite similar to first-class functions. Difference between first-class functions and higher order functions is that first-class functions have no restriction on their occurrence in the program. They can occur wherever entities like numeric data can occur whereas higher-order functions can operate only on other functions. Higher order functions enable a technique in which functions are applied to their arguments one by one where each application returns a new function that accepts the next argument.

For a detailed example refer : http://docs.scala-lang.org/tutorials/tour/higher-order-functions.html

Recursion

Recursion is very a popular technique employed for looping i.e. iteration. Recursion is loosely defined as the ability to state and eventually solve a problem in terms of the problem itself. Recursive methods invoke themselves until a terminating condition is reached which ends the recursion. This is the simplest yet most important step in recursion, which prevents the function from calling itself infinite number of times (infinite loop).

Recursion can be easily implemented using a stack. Tail recursion, a form of recursion where the latest function call calls a smaller version of itself, can be implemented using a stack. Recursions are simple to code, however, they use up a lot of resources and are very time consuming for huge problems. Recursion is normally avoided when the solution to a problem can be implemented in an iterative way. The reason for this is that the state space for recursion increases exponentially as the problem size increases, and a large number of method calls take place, which in turn compute the same base cases multiple number of times unnecessarily.

Almost all general purpose functional languages allow programmers to use recursion and are Turing complete, which makes the halting problem (deciding whether a given problem runs to completion or keeps running indefinitely) decidable. On the other hand, special purpose functional programming languages like Coq allow only well-founded recursion, and are non-Turing-complete.

def exp(x, n):
    """
    Computes the result of x raised to the power of n.

        >>> exp(2, 3)
        8
        >>> exp(3, 2)
        9
    """
    if n == 0:
        return 1
    else:
        return x * exp(x, n-1)

Strict and non-strict evaluation

Strict and non-strict evaluation is a concept that refers to the approach of processing function arguments when a mathematical expression is evaluated. The main difference lies in the computation of failing or divergent operations which fail when strict evaluation is used whereas are not evaluated if unnecessary when non-strict evaluation is used and the purpose of computing the function does not require the computation of the failing or divergent function.

Example:

print length ([3+8, 5/0, 6-2])

The above statement aims to find the length of the array. Under strict evaluation, this computation will not succeed because of the division by zero for the expression 5/0, whereas under non-strict evaluation, the 5/0 expression is not evaluated since the purpose of length function is orthogonal to the computation of the 5/0 computation.

Examples of languages that use non-strict evaluation:

• Miranda
• Clean
• Haskell

Features of Object Oriented Programming

Abstraction

The basic purpose of abstraction is to decompose complex systems into smaller components. It is a way in which data and programs are defined in a way that is similar to the real world entity while hiding away the implementation details. Abstraction takes into account only those details about an object that are relevant to the current scenario. It is the concept of describing an entity in simple terms and hiding the details in order to focus on what is important.

In OOP, it translates using the inheritance hierarchy, where more abstract concepts are at the top and more concrete ideas at the bottom, building upon those abstractions. At the most abstract level, there are no implementation details at all. For example, at the top we might have an interface with a single method, then the next level provides several abstract classes that may or may not fill in some of the details about the top level, but branches by adding their own abstract methods and further the hierarchy increase to provide concrete implementations for these abstractions.

Inheritance

Inheritance is the property of an object oriented language which allows code reuse. It can be defined as the process where one object (subclass) acquires the properties of another (super class). With the use of inheritance, information can be made manageable in a hierarchical order. In classical inheritance, where objects are defined by classes, classes can inherit attributes and behavior from pre-existing superclasses. In prototype-based programming, objects can be defined directly from other objects without the need of defining any superclass. This kind of inheritance is called differential inheritance. The keywords extends and implements are used to signify inheritance in most object oriented languages. The ‘extends’ keyword is used to denote an IS-A relationship.

Consider the following code snippet:

public class Animal{
}
 
public class Mammal extends Animal{
}
 
public class Reptile extends Animal{
}
 
public class Dog extends Mammal{
}

In object oriented terminology, the following hold for the above example:

• Class Animal is Super class for Class Mammal
• Class Animal is the superclass of Class Reptile.
• Class Mammal and Reptile are subclasses of Animal class.
• Class Dog is the subclass of both Mammal and Animal classes

Inheritance is used for overriding and code reuse. Overriding allows subclasses to replace the original implementation/aspect/behavior of super class in order to add additional features to the base class. Code reuse prevents code duplication and allows programmers to reuse libraries/code written by programmers beforehand instead of having to write them again every time the functionality is required.

Encapsulation

Encapsulation is basically used to hide the state or values of data objects inside a class in order to prevent unauthorized parties from directly accessing the data attributes. The access is provided though accessor methods provided by the class itself and then the other classes call these methods to retrieve and modify the values within the object.

First, it is a language mechanism for restricting access to the object’s attributes. Secondly, it’s a concept of language construct that facilitates the combinational occurrence of data and the data accessor methods that operate on that data. Example of encapsulation(JAVA):

public class Account {
        private double accountBalance = 500.00m;
 
        public double getAccountBalance() {
                return accountBalance;
        }
 
        public static void main() {
                Account myAccount = new Account();
                decimal myBalance = myAccount.getAccountBalance();
 
                /* This main method can check the balance via the public
                * "getAccountBalance" method provided by the "Account" class 
                * but it cannot manipulate the value of "accountBalance" */
        }
}

Polymorphism

The concept of polymorphism in Object oriented programming provides the ability to change the form of any object, variable or function. The purpose of polymorphism is basically message-passing, in which objects of different types agree upon a shared interface of operations for users. A simple example of objects taking up different functionalities is operator overloading (+, -, /, *) based on numerical data types.

The main use of polymorphism is the ability of objects of different classes to be able to invoke method calls having the same name, but still depict different run-time behavior depending on the type of the object. It is also used in cases where a parent class reference is used to refer to instances of sub classes. Polymorphism is only concerned with application specific implementation to an interface or a more generic base class. Any Java object that can pass more than one IS-A test is considered to be polymorphic.

Consider the following code:

public interface Vegetarian{}

public class Animal{}

public class Deer extends Animal implements Vegetarian{}
 
Deer d = new Deer();
Animal a = d;
Vegetarian v = d;
Object o = d;

• All the above declarations are legal.
• All the reference variables d, a, v and o refer to the same Deer object in the heap.

Differences between FP and OOP

State-based vs. Stateless

Object Oriented Programming can be viewed as a large machine with many states. One can perceive this machine to contain states representing objects being created and their attributes being set or manipulated by functions or interactions. These objects are passed around or referenced by code, which changes the state in which the system currently resides. The application keeps track of all the state changes and object manipulations that take place within the program. Any abnormalities or corrupt computations are reported by the system and/or programmer using the exception handling procedures made available by the object oriented language.

In Functional programming, there is no notion of states being defined, or objects being manipulated by the programmer or the program as a whole. Moreover, there is no way of maintaining states in memory. This lack of referencing does in fact lead to a considerable performance improvement in terms of memory and speed of execution of programs. This allows programmers to combine many functions into one and perform complicated computations without hindering high performance.

Data and behavior aspects

In Object Oriented programming objects have 2 main aspects: data and behavior. Objects have fields/attributes/members (the data aspect) that are either objects themselves or are simple data types like int, String, boolean, etc. Object implements a way to handle itself using the accessor methods (also called getters and setters).

In functional programming there are no objects that have both attributes and behavior. Data and code are separate aspects in a functional programming language.

Thread safety

Object Oriented languages are not thread-safe implicitly. You have to implement threading and synchronization mechanisms in order to ensure thread safety in object oriented language program. Its quite possible that two threads may try to access and modify the same data leaving the final state of the data undetermined and in order to avoid this the programmer has to explicitly synchronize the method that accesses the data.

Functional programming languages are thread-safe. The existence of two references to same data is not at all possible in functional programming language. A function cannot access the data that is accessible to another function. Since the functional programming languages, do not maintain any state, there is no possibility of stale references.

Exception Handling

Object Oriented Promgramming allows programmers to have the facility of error handling, which traditional functional programming doesn’t. Object Oriented Promgramming allows programmers to separate the actual code from error handling code. When something out of the ordinary occurs while the program is being executed, the error handling code written by programmer lets the programmer know where exactly the program failed or at which section of code caused it to fail. Object Oriented Promgramming also provides the freedom to group error types to create similar hierarchical structures for easier exception handling. However, a common problem in Object Oriented Promgramming is the occurrence of Null Pointer Exceptions (NPEs). NPEs occur when a portion of code being executed knows the definition of an object, i.e. its class, but tries to invoke a method on a non-existent instance of that class.

Advantages of Functional Programming

Composability

Functional Programming (FP) is programming with pure functions. As a result, with FP you can compose pure functions and build bigger abstractions out of smaller ones in a purely referentially transparent way.

Better Modularity

Since functions are pure in FP, you can organize your program in a better way in terms of modules. This is due to two characteristic of functional programming: higher-order functions and lazy evaluation.

Parallelism

Functional programming and referential transparency encourages language based parallelism of computation. Functional programming is transformation based programming that transforms your computation to a mathematical model that can then be parallelized into various independent sub-computations.

Optimization

Functional programs are normally faster in terms of execution speed as compared to programs written using other programming paradigms.

Concurrency

It is a lot easier to achieve concurrency with functional programming because the compiler takes care of most of the operations which normally require manual setting up state variables (like the iterator in a loop).

Support for Structured programming

Functional programming is known to provide better support for structured programming than imperative programming. Functional languages aid this by making it easy to create clean and simple abstractions.

Easier debugging

Since everything is broken down into small simple functions, the functions are often easy to debug.

Advantages of Object Oriented Programming

Simplicity

Object Oriented Programming is designed so that we can use the objects in OOP to represent the real-world objects altogether with their properties and behavior. This reduces a lot of complexity and the program structure is very clear.

Improved software-development productivity

Object-oriented programming is modular. There is separation of duties in object oriented program development. Each object forms a separate entity whose internal behavior is separated from the rest of the parts in the system.

Extensibility

We can easily add new features and respond to changing environments by adding new objects and modifying properties and duties of the existing ones.

Re-usability

Objects can also be reused across the application framework.

Faster software development

Object oriented programming languages come with rich libraries of objects and functionalities which can be re-used in future objects simplifying the development.

Lower cost of development

The reuse of objects allows lowering the development cost. Usually more efforts are put in object-oriented analysis and design that helps a lot to lower the development efforts ultimately reducing the development cost.

Higher-quality software

The low development cost and rapid development speed allows more time and resources to focus on main business features that help in increasing the quality of software.

Modifiability

In object-oriented programming, it is quite easy for programmers to make minor changes in data representation or operations. Changes done inside a class do not affect any other part of the program since the world interacts with the program through the use of public interface.

Comparison in a Nutshell

Let us compare both the programming paradigms with respect to several disctinction attributes.

Point of Comparison	Functional Languages	Object-Oriented Languages
Primary focus	Functional programming emphasizes on functions that produce results which depend only on their inputs and not on the program state - i.e. pure mathematial functions.	Focus on identifying and representing the problem in terms of an 'object' which has its own data, sub-routines and state. Different objects in the problem interact by sending messages to each other and thus result in change in its internal state. The final state and values of the objects refer to the solution. It is data-centric.
Problem Solving Approach	Primarily Top-down design	Identification and design of necessary objects. Close to being 'better models of the way the world works'.
Program Flow	Often sequential with program having single point of entry and exit.	Complex program flow. Can sometimes depend on the internal state of the objects.
Modularity	Limited modularity. Program is divided into modules or per say procedures independent of each other but are constrained due to uniqueness to that particular problem.	Extremely modular due to the presence of objects which contain their own data and sub-routines.
Data Protection/Hiding	No concept of data-hiding. Variables local to one method cannot be accessed by other method. But, Global variables can be accessed anywhere within the program.	One of the main fundamentals of O-O languages. Access specifiers like 'public', 'private' and 'protected' dictate the rules of data-hiding. Data which is private is confined to one object and cannot be directly changed by any other method except its own. This places the responsibility of managing data with the object itself This is called as ownership. Thus, data can be accessed ( read/write/modified ) only through the object's own interfaces.
Ease of Understanding	Smaller programs are easy to understand but as the program increases in size; understanding the code becomes more and more difficult.	Easy to understand due to its real world-like design and flow.
Reuse of Code	Very Limited or no code re-usability.	Highly re-usable code as the code developed can be easily modified or extended to suit a problem's need.
Support for declaring new data types/classes	Difficult due to limited in-built functionality.	Easily possible due to the concept of classes. Generic classes can be built as per the required specifications.
Efficiency	Efficient for solving small problems.	Efficient for solving large problems which have a complex structure and require complex data-types, abstraction and data-security.
Maintenance	Maintenance is easy for smaller programs but can consume a-lot of effort for larger program size as it requires the programmer to know and understand the dependencies of every module in the program. This makes it difficult to debug and test the program.	Extremely simple as O-O languages aim for high modularity. Secondly, programmer is not concerned with the details of how the data is stored and represented. Thirdly, they also tend to keep low coupling which makes it easy to debug and test different modules in the program.
Extensibility	Less Extensible as modules developed need to be re-organised and re-structured heavily in order to meet different needs.	High extensibility is one of the most important advantages of OOP. Code can be easily modified and 'plugged-in' to a different program. Methods can be exteneded due to many properties such as polymorphism, inheritance and support for multiple inheritance through interfaces.
Flexibility	Less flexible. Sometimes, certain problems do not fit into the 'top-down design' approach.	High flexibility. The modelling of problems into world-like objects makes it easy to solve any practical problem.
Examples	Haskell, Scala, Erlang	C++, Java, Ruby, Python.

Further reading

• Functional Programming - Python Practice book
  
• FP Vs. OOP notes
  
• OO Vs. Functional
  
• FP Vs. OOP - XQuery Blog
  
• Functional vs. Object-Oriented JavaScript Development
  
• FP Vs. OOP @ Stack Overflow
  

References

[1] Saylor.org: http://www.saylor.org/site/wp-content/uploads/2013/02/CS101-2.1.2-AdvantagesDisadvantagesOfOOP-FINAL.pdf

[2] Wikipedia, Functional Programming : http://en.wikipedia.org/wiki/Functional_programming

[3] Wikipedia, Object Oriented Programming  : http://en.wikipedia.org/wiki/Object-oriented_programming

[4] Haskell.org : http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue3/Functional_Programming_vs_Object_Oriented_Programming

[5] http://xquerywebappdev.wordpress.com/object-oriented-vs-functional-programming/

[6] CSC/ECE_517_Fall_2011/ch1_1e_aa

[7] http://searchsoa.techtarget.com/definition/object-oriented-programming

[8] http://c2.com/cgi/wiki?OoVsFunctional