CSC/ECE 517 Fall 2013/ch1 1w25 avam

From Expertiza_Wiki
Revision as of 15:26, 14 September 2013 by Avrohama (talk | contribs)
Jump to navigation Jump to search

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 OOP?

OOP 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. Objective-C, Smalltalk, Java and C# are well-known examples of object-oriented programming languages.

1. State-based vs. Stateless: OOP 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.

2. Data and behavior aspects: In OO 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).

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

3. Thread safety: OO 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.

4. Exception Handling in OOP:

OOP allows programmers to have the facility of error handling, which traditional functional programming doesn’t. OOP 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. OOP also provides the freedom to group error types to create similar hierarchical structures for easier exception handling. However, a common problem in OOP 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.

Exception Handling in Functional Programming: Handling exceptions in functional languages has received less attention mainly due to the inherent conflict between the control flow oriented approach of exception handlers and the functional style of evaluation. One advantage of functional programming is that all functional signatures are checked statically and only then invoked. As a result, there are no object instances of code which leaves no chance of a code instance of not existing. This prevents the occurrence of any Null Pointer Exceptions.


5. References to variables (data) OOP supports both pass by reference and pass by value. You can pass a value to another function by reference i.e. the calling function still maintains the reference to the data that is passed and any modification to same data in the called function are automatically reflected in the calling function’s reference variable as well.

Since the functional programming languages, do not maintain any state, there is no possibility of stale references. Functions operate on input data and the data is passed to any function by values and never references. Once some function calls another function, it cannot keep a reference to the same data.


Important links:

http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2012/ch1b_1w56_ms

http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2011/ch1_1e_aa

http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2011/ch1_1e_an

http://wiki.expertiza.ncsu.edu/index.php/CSC/ECE_517_Fall_2012/ch1_1w8_aa (Best link)


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 functions: 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 are Miranda, Clean and Haskell. Functional programming in non-functional languages There are known techniques of using a functional style in non-functional languages. Examples are languages like D and Fortran which are traditionally not functional languages but still support pure functions. Also, anonymous classes in Java can be used to simulate the functionality of closures. Many object oriented patterns are expressible in functional programming terms. In a similar way, the concept of an immutable data object prevalent in functional programming can be included in imperative programming languages like Python.

Features of OOP

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 code in 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.