Tuesday, 17 June 2014

Programming Paradigms

     Paradigm: In science,  a paradigm describes distinct concepts or thought patterns in some scientific discipline. In programming we can distinguish 3 main paradigms.
1. Imperative programming
2. Functional Programming
3. Logic Programming

Object Oriented Programming is orthogonal to the above 3 paradigms, in the sense it can be combined well with both imperative programming but also with functional programming or even logic programming.

Imperative Programming :

Imperative Programming is really about

a. Modifying mutable variables using assignments and those will be composed with control structures such as if-then-else, loops, break, continue, return and so on.

The most common informal way to understand imperative programs is as instruction sequences for a Von Neumann computer. Von Neumann was one of the pioneers of the computer built first computer around in 1945. Von Neumann computer essentially consists of a processor, memory and then there is bus that reads both instructions and data from memory into processor, and what's important is the width of bus is about one machine word such as 32 bit or 64 bit now a days.

This model of computer has shaped programming to a small degree. There is a very strong correspondence between memory cells of a Von Neumann computer and mutable variables in the programming language. Variable dereferences correspondent to load instructions in the computer. Variable assignments are like store instructions. Control structures all translate into a sequence of loops.

Mutable variables =  memory cells
Varaibale dereferences = load instrucions
Variable assignments = store instructions
Control structures = jumps

That's all very well up, but the problem is scaling up. We want to avoid conceptualizing programs just word by word, we want to reason in larger structures. That was the argument made by John Backus, in his Turing Award Lecture title " Can Programming be Liberated From The Von Neumann Style ? ".

John Backus was argued that in the end, pure imperative programming is limited by the "Von Neumann bottleneck " , which means that we conceptualize data structures word-by-word. If you want to scale up, we need to define high-level abstractions such as collections, polynomials, geometric shapes, strings, documents, and so on, and to be thorough, we need theories of these higher level abstractions.

What is the Theory? 

In Mathematics , A theory consists of
a. One or more data types,
b. Operations on these types,
c. Laws that describe the relationships between values and operations.

And what important is that, a theory in mathematics does not describe mutations. Mutation means change something while keeping the identity of the thing same.

Consequences for Programming: 

If we want to implement high-level concepts following their mathematical theories, there's no place for mutation.

a. The theories do not admit it. They don't have a mutation operator.
b. If you would add it, in fact mutation can destroy useful laws in the theories.

This leads to new style of programming, where we want to

a. Concentrate on defining these theories for operators expressed as functions.
b. Avoid mutations
c. Have powerful ways to abstract and compose functions.

Functional Programming :

So Functional Programming means avoid mutations, get new ways to abstract and compose functions. In fact we can look at functional programming in two ways,

1. In a restricted sense, functional programming means programming without mutable variables, assignments, loops, and other imperative control structures. So it takes lot of thing away.
2. In a wider sense, functional programming means focusing on the functions.
3. In particular, functions can be values that are produced, consumed, and composed.

All these can be done in any programming languages, but this becomes easier in functional language.
4. Functions in a functional programming language are first-class citizens, this means,
a. They can be defined any where, including inside of other functions.
b. Like any other value, they can be passed as parameters to functions and returned as results.
c. As for other values, there exists a set of operators to compose functions into richer functions.

Some functional programming languages are, Lisp, Scheme, Racket, Clojure, SML, Ocaml, F#, Haskell, Scala, Smalltalk, Ruby etc.

Some traditional imperative languages are C, C++, Java etc.

Logic Programming :

     The logic programming paradigm has its roots in automated theorem proving from which it took the notion of deduction. Logic programming is based on the syntax of first - order logic. This programming paradigm can be viewed as "Computation as deduction".

Prolog is the language that is based on Logic Programming paradigm. Prolog can be seen as a practical realization of the idea of logic programs. It started as a programming language for applications in natural language processing, but soon after it was found that it can be used as a general purpose programming lanuage, as well.

The logic programming paradigm influenced a number of developments in computer science. It led to the creation of deductive databases that extend the relational databases by providing deduction capabilities.

The logic programming paradigm substantially differs from other programming paradigms. It can be summarized by the following three features :

  1. computing takes place over the domain of all terms defined over a "universal" alphabet.
  2. values are assigned to variables by means of automatically generated substitutions, called most general unifiers. These values may contain variables, called logical variabls.
  3. the control is provided by a single mechanism: automatic backtracking


Post a Comment

Note: only a member of this blog may post a comment.