Mimir:Draft5 Chapter3

From Openitware
Jump to: navigation, search

Back to Main Textbook Index


Contents

Chapter 3: Imperative Programming

"Perl programming is an *empirical* science!" - Larry Wall

In this chapter you will learn:

  1. Imperative Paradigm
  2. Introduction to Python
  3. Introduction to Perl
  4. Basic Programming Concepts in Python
  5. Basic Programming Concepts in Perl
Imperative Programming.png

History and Introduction to Imperative Paradigm

In computer science, Imperative programming is a paradigm that uses statements which changes the program state. Imperative programming is most widely used and well-developed programming paradigm. It is a paradigm that evolved alongside the first computers and computer programs in 1940. The earliest imperative languages were the machine languages of the computer. In these languages, instructions were simple which made execution easier, however hindered the creation of complex programs. FORTRAN was the first major imperative programming language developed at IBM which removed the obstacles presented by machine language in the creation of complex programs.

Imperative programming follows the model of computation described in the Turing Machine, hence they maintain the state of the machine. In Turing Machine, state of program is given by configuration of memory tape, and the pointer in table of rules. In case of imperative programming, it’s program counter that defines the next set of instructions. Imperative program issues machines orders that defines the next action to be taken. Instructions are combined to make up commands. There are mainly three categories of commands: assignments, branches and sequences. Some of the most popular programming languages that follows imperative paradigm are: • C • C++ • Java • Swift • Perl • PHP and few more.

Example of Imperative Paradigm

The example below focusses on evaluating expression and storing the result in a variable. We can call this expressions as instructions, and imperative program is nothing but a set/sequence of instructions. The execution of each operation can alter the memory state.

a=5
b=10
c=a+b

Advantages of Imperative programming

  • Efficient
  • Close to the machine
  • Popular
  • Familiar
  • Scalable

Concepts of Imperative programming with examples

Variables and assignments

Variables in most of the imperative languages follow the standard nomenclature of an alphanumeric name beginning in a letter or underscore. Variables in any imperative languages are case sensitive. This means that myname and myName are different variables, stored at different locations in memory. In some programming languages variables needs to be declared with their data types, however in very few like Python it considers data type automatically based on the data allocated to a variable. This means that if you assign a string to a variable, Python automatically knows it is a string and if you assign the number '2' to a variable, again Python automatically knows it is an integer. However, in case of Java, variable needs to be declared with its data type before you can initialize it with some value.

Most imperative languages supports the following data types:

boolean 
integer 
long 
float 
string 

Below is an example of how you declare a variable in Python and C. Note again that you are not declaring a specific type in Python. All you need to do in Python is assign a variable a name and then assign whatever value you want afterwards, Python will take care of the rest for you. Whereas, you will find that this is not the case in C.

Python variable declaration example:

My_variable = 10
my_int = 7
my_float = 1.23

C variable declaration example:

int my_int = 7;
char str[15] = "Hello World";
float my_float = 1.23;


Here we will be changing the value of a variable. Reassigning remains the same in either C or Python with same data type, though there is a slight change in C if the data type of the previous assignment and new assignment are not similar.

my_int = 7
my_int = 3

Now if you were to print my_int the value of it will be 3 instead of 7, since you reassigned the variable.


Operators

Operators available are addition, subtraction, multiplication, division and modulus arithmetic. The symbols used are similar in between many programming languages.

Operation 	      Symbol
Addition	        +
Subtraction	        -
Multiplication	        *
Division	        /
Modulus                 %

An example of some simple math you can do in any programming language. Note that, you should initialize the variables names with either integer or float data type in some programming languages before performing the operations given below.

addition = 1 + 23
subtraction = 10 – 2
multiplication = 0.5 * 0.5
division = 15 / 3
modulus = 5 % 4

Flow Control
Boolean Comparators

Boolean operations in imperative languages also come with the typical six boolean comparison operators.

Equal to (==)
Not equal to (!=)
Less than (<)
Less than or equal to (<=)
Greater than (>)
Greater than or equal to (>=)

Programming languages uses boolean variables to evaluate conditions. The boolean values True and False are returned when an expression is compared or evaluated.

Example:

x = 3
print (x == 3) # prints out True
print (x != 5) # prints out True
print (x < 5) # prints out True
print (x > 10) # print out False

Note that (==) compares whether two things are equal, and (=) assigns a value to a variable.


Conditional Statements

In order to write useful programs, we almost always need the ability to check conditions and change the behavior of the program accordingly. Conditional statements give us this ability to do this in any programming language. They operate the same way in any programming languages, just the way they might differ is syntactically.

If Statement

An 'if' statement is a conditional statement that executes some specified code after checking if its expression is True. The general form of the 'if' statement is:

if BOOLEAN EXPRESSION
   STATEMENTS

Here is an example:

if (8 < 9):
    print ("Eight is less than nine!")

In this example, 8 < 9 is the checked expression and print "Eight is less than nine!" is the specified code.

Else Statement

The else statement complements the if statement. An if/else pair says: "If this expression is true, run this indented code block; otherwise, run this code after the else statement." The else statement doesn't require an expression, it only runs if the previous expression in the if statement evaluated to False.

The syntax for an if else statement looks like this:

if BOOLEAN EXPRESSION
   STATEMENTS_1        # executed if condition evaluates to True
else
   STATEMENTS_2        # executed if condition evaluates to False

The statement inside the 'if' block of an if else statement is executed, if the Boolean expression evaluates to True. But the entire block of statements is skipped if the Boolean expression evaluates to False, and instead all the statements within 'else' will be executed.

For Example:

if (8 > 9):
   print "8 is greater than 9"
else:
   print "8 is less than 9"

The code above will skip the 'if' block and will execute the 'else statement block because the condition in the 'if' statement is evaluated to False.

Else if Statement

This statement is used if you want to check multiple conditions. If x is 1, if x is 2, if x is 3, etc. In Python programming language the syntactical difference is it uses 'elif' whereas in Java and C its 'else if'

For Example:

if (8 >= 9):
    print "False!"
elif (8 < 9):
    print "8 is less than 9!"
else:
    print "False"

In the example above, the 'elif' statement is only checked if the original 'if' statement is False.


Loops

All loops function in the same manner, They all loop over the same code block until some condition is deemed to be true. Python's loops are not much different compared to other languages.

while

The while loop is similar to an if statement. It executes the code inside of it if some condition is true. The difference is that the while loop will continue to execute as long as the condition is true. It will keep running for an unknown amount of times until the condition is met. In other words, instead of executing if something is true, it executes while that thing is true.

The general syntax for the while statement looks like this:

while BOOLEAN_EXPRESSION:
    STATEMENTS

For Example:

count = 0
if count < 5:
    print ("Hello, I am an if statement and count is", count)
while count < 5:
    print ("Hello, I am a while and count is", count)
    count += 1

The while statement decides when the loop will be executed. As long as count is less than 5, the loop will continue to execute, and increases count by 1. This happens over and over until count equals 5. When count is no longer less than 5, the loop will be exited.

The output for the code above will be

Hello, I am an if statement and count is 0
Hello, I am a while and count is 0
Hello, I am a while and count is 1
Hello, I am a while and count is 2
Hello, I am a while and count is 3
Hello, I am a while and count is 4

for

Another way to loop is the for loop. The syntax is as shown;

for LOOP_VARIABLE in SEQUENCE:
    STATEMENTS

The following example means "for each number i in the range 0 - 4, print i".

print "Counting..."
for i in range(5):
    print i

Output for the code above is:

Counting...
0
1
2
3

continue Skips the rest of the body of the loop for the current iteration and continue execution at the beginning of the next iteration.

break Ends the execution of the while loop.

Example:

for j in range(0,10):
    while (k < j):
        print "j = " + str(j) + " k = " + str(k)
        if (j == 1): 
            break
        k=k+1
        print "j equals k or j equals 1"

for-each

for x in array: statements

Loops over the array given by array. On each iteration, the value of the current element is assigned to x and the internal array pointer is advanced by one.

Example:

a = ["abc","def","ghi"]
for x in a:
  print x

Program Structure
Pointers

A pointer is a variable which contains the address in memory of another variable. We can have a pointer to any variable type. The unary or monadic operator & gives the ``address of a variable.

The indirection or dereference operator * gives the ``contents of an object pointed to by a pointer.

To declare a pointer to a variable do:

  int *pointer;
  int main()
 {
   int x = 10;
   int *ptr;
   ptr = &x;

   return 0;
  }

To declare a pointer variable we use the * (Asterisk) before the variable.

To access address of the variable to a pointer, we use the unary operator &(ampersand) that returns the address of that variable.

  int main()
 {
   int x;
   // Prints address of x
   printf("%p", &x);
   return 0;
  }

How to uses pointers

There are a few important operations, which we will do with the help of pointers very frequently. (a) We define a pointer variable (b) assign the address of a variable to a pointer and (c) finally access the value at the address available in the pointer.

This is done by using unary operator * that returns the value of the variable located at the address specified by its operand.

Operations performed on the Pointers

A limited set of arithmetic operations can be performed on pointers. A pointer may be:

  • incremented ( ++ )
  • decremented ( — )
  • an integer may be added to a pointer ( + or += )
  • an integer may be subtracted from a pointer ( – or -= )

Pointer arithmetic is meaningless unless performed on an array.

An array name acts like a pointer constant. The value of this pointer constant is the address of the first element. For example, if we have an array named val then val and &val[0] can be used interchangeably.

 void extras()
 {
   // Declare an array
   int val[3] = { 5, 10, 20 };
   // pointer variable
   int *ptr;
   // Assign address of val[0] to ptr.
   // We can use ptr=&val[0];(both are same)
   ptr = val ;
   cout << "Elements of the array are: ";
   cout << ptr[0] << " " << ptr[1] << " " << ptr[2];
   return;
 }

 // Test Driver program
 int main()
 {
   extras();
   return 0;
 }

NULL pointers

It is always a good practice to assign a NULL value to a pointer variable in case you do not have an exact address to be assigned. This is done at the time of variable declaration. A pointer that is assigned NULL is called a null pointer.

The NULL pointer is a constant with a value of zero defined in several standard libraries. Consider the following program −

 #include <stdio.h>
 int main () 
 {
  int  *pointer = NULL;
  printf("The value of pointer is : %x\n", pointer  );
  return 0;
 }

output: The value of the Pointer is 0

Pointers in detail

1.Pointer Arithmetic There are four arithmetic operators that can be used in pointers: ++, --, +, -

2. Array of Pointers You can define the arrays to hold a number of pointers

3. Pointers to pointers C allows you to have pointer on a pointer and so on.

4. Passing pointers to function Passing an argument by reference or by address enable the passed argument to be changed in the calling function by the called function.

5. Return pointer from function in C C allows a function to return a pointer to the local variable, static variable, and dynamically allocated memory as well.

Arrays

The most common Imperative language consists of statements such as-

a = 10;
b = 5;
c = a + b;

The above example focus on evaluating expressions and storing results in a variable.

Imperative programming is closer to the machine representation, as it introduces memory state which the execution of the program’s actions will modify. We call these actions of programs instructions, and an imperative program is a list, or sequence, of instructions. The execution of each operation can alter the memory state4.

Let’s take an example of Imperative program in Python.

Greatest common divisor:

def gcd (x, y):
   r = 0
   while y > 0
      r = x % y
      x = y
      y = r
   return x
x y r
9702 945 0
945 252 252
252 189 189
189 63 63
63 0 0

The following table shows the change of states during each iteration of the while loop. We are diving x with y and storing the divisor in r (remember r initially was 0). Every time the execution take place the value stored in variable x, y, r change. After the execution is completed the value of x returned is 63.

Any Imperative Programming (IP) Languages can contain the following Characteristics:

  • Sequence of Statements.
  • Order of execution of Statements is very important.
  • They contain state.
  • They use both Immutable and Mutable Data.
  • They can change state.
  • They may have Side-effects.
  • Stateful Programming Model.
  • They directly change the state of Program.
  • They represent state with Data Fields.

At the heart of this paradigm – The main idea is of assignment (changing the value of a memory location and destroying its previous value).

             sum = sum + num;
Functions
Functions in Python are defined with the following syntax
def funct(arg_1, arg_2, ..., arg_n):
   print "This is a function."
   return value

Any Python code, including other function and class definitions, may appear inside a function. Functions may also be defined within a conditional, but in that case the function's definition must be processed prior to its being called. Python does not support function overloading but does support variable number of arguments, default arguments, and keyword arguments. Return types are not specified by functions.

Example of a Double function:

function double(n):
   n = n*2
   return n
x = double(x)
File I/O (Input/Output)

Python also has the ability to open, read and write files on your computer. You only need to have a Python script running the same directory as your file, or as otherwise specified.

For example:

file = open(“testfile.txt”,”w”) 
file.write(“Hello World”) 
file.close() 

This example would open a file, looking for the name testfile.txt, with the "w" parameter, which stand for write. You could then write that string "Hello World", or any variable, array, etc to that file. You then close the file.

If you wanted to read from a file.

For example:

file = open(“testfile.text”, “r”) 
print (file.read())
file.close()

Notice how the structure is similar. We open the same file, but this time instead of "w" for write, we use "r" for read. Then we print out our "Hello World" line and then close the file.

This is just a simple example. You could do more with this, like writing a log to a text file, and then reading through that log and displaying it to the user. Keep files of old logs. Write variable values to a text log at certain points in the code. We just want to cover the basics here.


Understanding Memory Allocations in Imperative programming

Imperative programming languages have developed over time. Every time the when a new language is introduced in the market it comes with some improvement in memory management for storing the information of the program. In this part of the chapter, we will discuss memory management in C language which is one of the very old but still used languages.

Static Allocation

This involves storing the local and global variables which are fixed during compilation and remains constant during the run-time program. The size is fixed when the program is created. It applies to global variables, file scope variables, and variables which are statically defined inside functions. Even the variables of structures and arrays are stored in the memory during the compilation.

Stack-based Allocation

Stacks are data structures where data is added and removed last-in-first-out (LIFO) manner. Each thread has a reserved memory as its stack. When a thread executes a function, the function is responsible for both adding and removing the added data from the stack. The location of a function call is stored in the thread's memory so that the return statements can return to the correct function. This kind of memory allocation is called stack-based allocation. This is typically faster than than heap-based memory allocation/dynamic memory allocation because of the simple LIFO based data manipulation. This sort of memory allocation is automatically done during runtime.

Heap-based Allocation (Dynamic Memory Allocation)

Heap is a large pool of memory which is used to satisfy memory requests during the execution of a function. This is done by allocating portions of this memory for each request. This memory can also be deallocated the memory when not required. Recent programming languages do this automatically.

For example, there are different functions available in C to perform this dynamic allocation of memory. These functions are listed and explained in detail below.

Malloc A memory block is allocated with a function called malloc(). The function reserves the memory in bytes of the desired size and returns the base address to a pointer variable. The prototype is declared in the alloc.h and stdlib.h. The syntax for the function is explained below.

Example:

Write a C program to find the sum of n elements entered by the user. Use malloc function for dynamic memory allocation.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num, i, *pointer, sum = 0;
    printf("Enter number of elements: ");
    scanf("%d", &num);
    pointer = (int*) malloc(num * sizeof(int));  //memory allocated using malloc
    if(pointer == NULL)
    {
        printf("Error! memory not allocated.");
        exit(0);
    }
    for(i = 0; i < num; ++i)
    {
        printf("Enter %dth element of array: ", i+1);
        scanf("%d", pointer + i);
        sum += *(pointer + i);
    }
    printf("Sum = %d\n", sum);
    return 0;
}

Calloc This function is used to assign multiple blocks of memory. It is declared with two arguments. Similar to malloc function the prototype are declared in alloc.h and stdlib.h. The syntax for writing calloc function.

pointer = (datatype *) calloc(block, size)

Example

Write a C program to find the sum of n elements entered by the user. Use calloc function for dynamic memory allocation.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num, i, *pointer, sum = 0;
    printf("Enter number of elements: ");
    scanf("%d", &num);
    pointer = (int*) calloc(num, sizeof(int));
    if(pointer == NULL)
    {
        printf("Error! memory not allocated.");
        exit(0);
    }
    for(i = 0; i < num; ++i)
    {
        printf("Enter %dth element of array: ", i+1);
        scanf("%d", pointer + i);
        sum += *(pointer + i);
    }
    printf("Sum = %d\n", sum);
    return 0;
}
Hybrid Allocation

The hybrid allocation of memory involves the combination of multiple methods including Static Allocation, Stack-based Allocation, and Heap-based Allocation. This mainly deals with the allocation of memory in multiple different ways that aren't covered specifically by any one of these categories. For an example, a program may use static allocation of memory for one part of the program, and stack-based allocation for another part of the program. This could be a program with local and global variables, that also maintains a stack call using the Last-In-First-Out (LIFO) method.

Summary

Imperative programming is a programming paradigm that describes computation in terms of statements that change a program state. This is in opposition to declarative programming, which expresses what the program should accomplish without prescribing how to do it in terms of sequences of actions to be taken7. An Imperative language is formed around a structure of code where you describe a series of statements for the computer to execute. These statements are giving directions to the computer in order for it to take specific actions following a certain order in the form of code blocks. The block of code is a part of code that is more of a sequence of statements that contain/form/code and is one of the innovations that came along with imperative languages. A paradigm can better be described as a pattern or an archetype and while all computer languages are unique, all share a common paradigm. "Perl" (created by Larry Wall in 1987) and "Python" (created by Guido van Rossum between 1985 and 1990) are two most widely known imperative programming languages. Developed to be used as a general Unix scripting language, Perl stands for Practical Extraction and Report Language. Perl includes: scalars (variables), arrays, hashes, subroutines, loops, conditionals, regular expressions, objects, file I/O, and many more features.

Key Terms

  • Calloc: This function is used to assign multiple blocks of memory.
  • Conditionals: Conditionals are statements used to evaluate conditions on bases of true or false in order to perform different computations.
  • Heap-Based Memory Allocation: Heap is a large pool of memory which is used to satisfy memory requests during the execution of a function.
  • Hybrid Memory Allocation: The hybrid allocation of memory involves the combination of multiple methods including Static Allocation, Stack-based Allocation, and Heap-based Allocation.
  • Imperative Paradigm: In computer science terminologies, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state.
  • Malloc: The function reserves the memory in bytes of the desired size and returns the base address to a pointer variable.
  • Pointer: A pointer is a variable which contains the address in memory of another variable.
  • Stack-Based Allocation: Stacks are data structures where data is added and removed last-in-first-out (LIFO) manner.
  • Static Memory Allocation: This involves storing the local and global variables which are fixed during compilation and remains constant during the run-time program.
  • Subroutine: Subroutines are blocks of code that performs a specific task. Once created they can be called multiple times within the program or implemented into other programs with ease. Subroutines eliminate code duplication, makes code cleaner, and easier to maintain.

Problem Sets

Theoretical Questions

1. List the advantages of imperative programming.

2. What is a pointer?

3. What is imperative programming?

4. What are conditionals?

5. Define subroutine.

A list of practice problems to do in Perl and in Python:

1) Write a program that determines whether a number inputted by the user is even or odd.

2) Write a guessing game. Create a random number and then ask for user input. If the guess is below, print to the user the guess was below. Do the same for if it is too high.

3) Write a Fibonacci sequence.

4) Write a program that prints out a string input backwards.

References

  1. Adrian Kashivskyy. Imperative vs. Declarative Programming - Pros and Cons - Netguru, Netguru, Mar 2, 2015, www.netguru.co/blog/imperative-vs-declarative
  2. en.wikipedia.org/wiki/Imperative_programming
  3. citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.59.9378&rep=rep1&type=pdf
  4. caml.inria.fr/pub/docs/oreilly-book/html/book-ora024.html
  5. www.tutorialspoint.com/python/
  6. www.tutorialspoint.com/python/python_overview.htm
  7. www.csaldenham.co.uk/wp-content/uploads/2014/08/Programming-Languages.pdf

Top of Page - Prev Chapter - Next Chapter