CSC/ECE 517 Fall 2013/ch1 1w25 avam

Hi, Coming soon!

<mainpage-leftcolumn-start />

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.

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.

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.

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.

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.

Following aspects of block structure are viewed in OOP languages:-

• Locality:- The major advantage of block structure is locality. This makes it possible to restrict the existence of an object and its description to the environment where it has meaning.
• Scope Rule :- These are following aspects of scope rules for names declared within an object:
  • They only exist when the object exist. This is a consequence of locality.
  • Access to global names and re-declaration of names.
  • Access to names within a block from “outside” the block may be restricted. Like in Simula language.

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.