2CS24 - TOPICS IN INFORMATION PROCESSING

QUESTION: "What is a computer program?"

ANSWER: "It is an executable representation of some algorithm designed to solve some real world problem."

There are thus two elements to a computer program:

1. Logic - what we what the program to achieve.
2. Control - how we are going to achieve the end goal.

Consider the following definition (logic) for factorial n:

if n = 0 then n! = 1
if n > then n! = 1x2x3 ... xn

Imperative (Ada) implementation

with CS_IO ; use CS_IO ;

procedure FACTORIAL is
   N: integer;
   T: integer:= 1;
begin
   put("Input ");get(N);
   for K in 2..N loop
      T:= T*K;
   end loop;
   put("Factorial ");put(N);
   put("is ");put(T);newline;
end FACTORIAL;

The above comprises a series of steps which, if executed, will calculate the factorial of a given number. When writing in an imperative language the programmer needs to concentrate on both the logic (what) and the control (how). The principal idea behind declarative languages is to separate out these two elements so that the programmer is free to concentrate on the logic of a problem without being distracted by control considerations.

Declarative (PROLOG) implementation

factorial(0,1):-
        !.

factorial(N1,T2):-
        N2 is N1-1,
        factorial(N2,T1),
        T2 is N1*T1.

Here we define the logic (the desired goal or result) and not the control (how we achieve the desired goal). We say that declarative languages are goal directed or goal driven. Note the closeness of the code to the initial definition, both specify what is to be achieved (i.e. the logic).

To study computer programming languages it is convenient to devide such languages into categories according to some classification. Many classifications have been suggested. The most popular are listed below:

Classification according to levels of abstraction:

1. Machine code
2. Low level languages, e.g. assemler.
3. High level languages, e.g. Ada, C, PROLOG.

Classification according to generations of programming languages:

1. 1st Generation languages (circa 1950): Low level languages e.g. assembler.
2. 2nd Generation languages (late 1950's to early 1960's): Foundation languages, e.g. ALGOL-60, Cobol, Fortran.
3. 3rd Generation languages (late 1960's onwards): Structured languages, e,g. Ada, C, Prolog.
4. 4th Generation languages (circa 1980 onwards): 4GLs, e.g. SQL.

Classification according to application area. Most current programming languages are categorised as 3rd generation. This category is therefore sometimes divided into two sub categories:

1. General purpose high order languages, e.g. ALGOL, Pascal, Ada and C.
2. Specialised languages designed to exploit alternative paradigms, e.g. Smalltalk, declarative languages.

Declarative languages are considered to be specialised in that they were initially intended for use in Artificial Intelligence (AI) and expert systems programming. Example decalarative languages include: PROLOG, LISP, Miranda, Haskell and SML.

From the above we have established that the principal distinction between declarative languages and imperative languages is that declartaive languages allow the programmer to concentrate on the logic of an algorithm (declarative languages are goal driven, control is not the concern of the programmer), while imperative languages require the programmer to focus on both the logic and control of an algorithm. To distinguish more succinctly between declarative and imperative programming languages we will consider the models of computation on which they are based in terms of the following features:

1. Definition of relationships
2. Assignment
3. Data structures
4. Order of execution
5. Expressions and definitions as values
6. Control

1) Definition of Relationships

IMPERATIVE LANGUAGES: Imperative languages describe computable relationships in terms of sequences of operations, e.g. Ada factorial program.

DECLARATIVE LANGUAGES: Declarative programs, in turn, are made up of sets of definitions or equations describing relations which specify what is to be computed (not how it is to be computed), e.g. Prolog factorial program.

2) Assignment

IMPERATIVE LANGUAGES: Imperative languages are based on the concept of variables names which can be associated with changeable values through expressions. Typically each expression will consist of an assignment which will in some way change a value associated with a variable name. The process whereby different values are continually associated with a particular variable name is referred to as destructive assignment - each fresh assignment obliterates the existing value.

DECLARATIVE LANGUAGES: In declarative programs variables can only ever have one value "assigned" to them and this value can not be altered during a program's execution. We refer to this as non-destructive assignment. In declarative languages to achieve results such as that illustrated by the factorial Ada program, because the same name cannot be reused with different values, we must either:

• Nest relationships, or
• Use recursive techniques

3) Data Structures

IMPERATIVE LANGUAGES: Imperative language make use of data structures such as arrays, records etc. Array elements and record fields are changed by successive destructive assignments.

DECLARATIVE LANGUAGES In declarative languages, where there is no destructive assignment, explicit representations for data structures must be used. The most fundamental data structure used by declarative programming languages is the list.

4) Order of Execution

IMPERATIVE LANGUAGES Because relationships in imperative programs languages are expressed using sequences of expressions the order of execution is crucial. Values are passed from one expression to another by reference to common variables. Further one expression may change a variable's value before that variable is used in the next expression, i.e. imperative expressions have side effects. Thus if the order in which expressions are executed is changed then the behaviour of the entire program will be affected. In imperative programs, we say that commands can only be understood in the context of the previous computation.

DECLARATIVE LANGUAGES In declarative programs the values associated with variable names cannot be changed. Thus the order in which definitions or equations are called does not matter, i.e. they are order independent. Further, declarative definitions do not permit side effects, i.e. the computation of one value will not effect some other value. Of course declarative programs must be executed in some order, but the order should not affect the final result. Thus we can say that, in declarative programs, program statements are true independent of the computational context.

5) Expressions and Definitions as Values

IMPERATIVE LANGUAGES In most imperative languages sub-programs cannot be passed as actual parameters to other sub-programs, or be passed back as results (there are exceptions).

DECLARATIVE LANGUAGES In declarative languages, relationships may construct new relationships and pass then on to other relationships as arguments. Thus declarative languages allow definitions or expressions to be treated in the same manner as more standard parameter data items.

6) Control

IMPERATIVE LANGUAGES The control of programs in imperative languages is the responsibility of the programmer, i.e. the programmer is concerned with assignments and the order of assignments.

DECLARATIVE LANGUAGES In declarative languages control is transferred to the language and hence is no longer the programmers responsibility.

Summary

Characteristics of imperative languages:

1. Model of computation based on a step by step sequences of commands.
2. Program states exactly how the result is to be obtained.
3. Destructive assignment of variables.
4. Data structures changed by successive destructive assignments.
5. Order of execution is crucial, commands can only be understood in context of previous computation due to side effects.
6. Expressions/definitions cannot be used as values.
7. Control is the responsibility of the programmer.

Characteristics of declarative languages:

1. Model of computation based on a system where relationships are specified directly in terms of the constituents of the input data.
2. Made up of sets of definitions or equations describing relations which specify what is to be computed, not how it is to be computed.
3. Non-destructive assignment of variables.
4. Explicit representations for data structures used.
5. Order of execution does not matter (no side effects).
6. Expressions/definitions can be used as values.
7. Programmer no longer responsible for control.

Declarative languages make extensive use of relationships. There are two principal styles of defining relationships available to such languages:

1. Functional
2. Logic

These form the two sub-branches of the declarative family of programming languages.

Functional Definition

Functional declarative languages tend to be inspired by the Lambda Calculus ( Calculus), a computational model proposed by Alonzo Church in the 1930's. As the name suggests, using the functional style, relationships are expressed using functions. Example:

(square (n)
        (* n n))

This is a function, square, that express the relationship between the input n and the output value n*n.

Logic Definition

Logic declarative languages, in turn, tend to be inspired by Predicate Calculus and, more particularly, the Horn Clause subset of Predicate calculus. In this style of declarative programming relationships are declared using expressions known as clauses. Thus:

square(N, M):-
        M is N*N.

Clauses can be used to express both facts and rules. A logic programme can therefore be treated as a relational database to which we can pose queries of various forms.