A different perspective of contemporary programming

Nowadays, programming is not that hard as it was earlier. Moreover, a programmer need not have a formal background in programming, though, it often depends on the problem.  

We can classify the problems broadly as End User Applications, Systems Programs, and Infrastructural Software etc. 

High level constructs, efficient libraries, proper standardization are some of the reasons why programming in most of the cases seems simple.  Sometimes it seems to me whether we really are programming a computer or not?  We are not directly giving instructions to a computer, we are instructing the high level constructs available, with languages.  Those constructs -printf, scanf etc. to name a few - hide most or almost all of the complexity and instruct the computer (generating instructions that are in one to one correspondence with computer's instructions set). But this process is not as easy as it seems.  We have to pass through many of such constructs. For example, one construct may use another and so on. These transform our high level - often very high level - source code to computer instructions: compiler/interpreter, pre-defined libraries, standard libraries, system calls and assembler. 
As end programmers, we are enjoying the compiler technology that features us with high level constructs. If you are a Python programmer, you can use those easy to use data-types it provides with a single Python instruction.
Like
        data = list()
    data.append("hello")
    data.append(23)
We should not think these are to be understood by the computer (bare machine). These are understood by intermediate systems and they modify them such that the computer can understand. We are just programming (instructing) the constructs, intermediate systems. My intention is not that one has to go for low-level programming but as mentioned, it is a different perspective of modern programming.
If you want to enjoy knowing the difficulties in building those constructs, you can revolutionize.

To be a programming language poet

Learning a programming language is same as learning any natural language. Except programming language have negligible amount of  special words and no ambiguity. Grammar and language specification/standard are major ingredients here.

You can be a poet on the other side of the language, but to reach there I strongly believe that you have to go through them: language specification/standard and grammar. Because all your questions/doubts can be answered with them. It is a bit difficult to understand them because they are intended(mainly) for language implementors, who are assumed to have sound knowledge. But being a poet counts. :)

Heapsort program in C

Before talking about heapsort I would prefer to talk about my terrible three-day-debugging story.

I thought of implementing heapsort function as qsort of C's standard library. 

I referred CLRS book for the algorithm. As it should work with any type of data, I needed to use void pointers to implement. Unfortunately, even when I followed algorithm clearly I got bad results during testing. I cross checked it again and again for three days but found no clue what was wrong with that. I figured out that I was doing something wrong while manipulating void pointers. I focused on void pointers usage; and while doing this I got a doubt : why qsort function takes size of each object when it is sufficient to have length of array to sort?

         Actually void specifies no type. So, like int it has no size specified. Then how can we expect incrementing void pointer with 1 will make it point to next object when we don't know the type of object it points to. During the debugging I found that incrementing a void pointer will make it to point next byte but not whatever the next object you are expecting it to point. So I did try sizeof(void) and got result 1. We need to understand that incrementing a type pointer where type is other than void doesn't equal to incrementing a void pointer. Size of each object must be used to calculate the offset from base of the array pointed by void pointer.

        Coming to heapsort, it is better explained in CLRS book. I implemented it as it is. No heuristics added. It is available here. I documented the source code clearly. Be careful. Don't get stuck like me.

Significance of extern and static keywords in C

Consider a module in a C program. When I say a module ,it can be a piece of large project. Let us call it as a translation unit. Because modular programming helps the programmers working on a large project. To understand keywords static and extern , we need to understand linkage and storage classes in C. Most of the times description of the above keywords confuse. Actually there are only two types of storage classes (describes the life time of the variable) in C. Those are

1. automatic storage class
2. static storage class

A variable with automatic storage class will have its lifetime equal to the execution time of the block it is defined in.

A variable with static storage will have its lifetime equal the execution time of the program (The variable can retain its value between function calls) .

We can divide any translation unit into two parts.

1. internal to a function
2. external to all functions

You can find global definitions/declarations (not every external declaration/definition is global because of scope ) and preprocessor directives (most often) external to all function. Of course you can have preprocessor directives anywhere in the translation unit.

According to the standard all the variables defined external to all functions will have static storage class (It has nothing to do with static keyword).

If you want to define a variable internal to any function with static storage class then you need to use static keyword.

Linkage determines whether the same name in another scope refers to the same object or function. You can have two types of linkages. Those are

1. internal linkage
2. external linkage
3. no linkage

We use internal linkage only for translation unit. You may want to hide some of global variables or function definitions (global means external to all functions ) from other translation units, in that case you can specify internal linkage using static keyword. Hence, internally linked variables/functions can't be accessed from other translation units.

We generally use external linkage for communication among translation units. We can allow all translation units to use the same definition of a function/variable. Unless you use static keyword with functions/variables defined they will have external linkage hence can be called/accessed from any translation unit, provided that the translation unit knows the declarations of the functions/variables (may be using header file). What if you want to use the same definition of a variable in all translation units. We know that we can have any number of declarations of a function/variable but only one definition. How can you actually declare a variable. Functions have prototypes to declare (no definition). Here is the way (only way) of declaring a variable in C, i.e, by using extern keyword. This tells the compiler that the identifier has been defined somewhere (and resolve its location during linking) but I will access here.

A block-scope variable defined without extern will have no linkage.

If the definition of the external variable occurs in the translation unit before its use in a particular function, then there is no need for an extern declaration in the function. Because of this reason we are able to access global variables in functions.

Some keywords are used for syntactic convenience in C. That confuses a lot.

We use storage-class specifiers (some keywords) to specify the storage properties of a variable, those are auto , register , static , extern , typedef .

Don't think all these keywords will specify storage class (either automatic or static).

auto - announces variable has automatic storage-class.

register - announces variable has automatic storage-class (if possible store it in CPU registers)

static - It has two roles.

1.   To specify internally defined variable has static-storage class.
2.   To announce internal linkage for an identifier (function/variable) defined external to all functions.

extern  - It specifies that this identifier has been defined somewhere(external) hence no need to allocate memory

1. If you want to use function defined in somewhere we need to use      : extern ret-type func(type arg,...);  . But it is same as   ret-type   func(type    arg,...); . Hence it is optional to use extern with declaration of identifier for a function
2. For variable identifiers : If you want to use variables defined in someother scope (like other translation units) you need to specify: extern type var-name.

typedef - does not reserve storage and is called a storage-class specifier only for

syntactic convenience (we will talk about it later).

A Case Study

Problem :

Scientist recently found a new element X, which can have different isotopes up to an atomic value of 199.

Specialty of element X is that when two atoms fuse they produce energy multiple of their atomic value and forms an atom with atomic value of their multiple modulus 199.

For Example :

If atom1 with value 56 and atom2 with value 61 fuse.

They produce energy of 3416 KJ (56 * 61)

Resulting atom will have atomic value (56*61) mod 199 = 33

Scientists created a nuclear reactor to create energy by this method.

Every day they get several atoms of  X from supplier in a particular sequence. Since this element highly radioactive they can’t risk by changing

its sequence. So each atom can fuse only with another atom nearby.

Nevertheless scientists can choose order of fusion thereby maximizing total energy produced.

Now, for given sequence of atomic values, output maximum energy that can be produced.

For Example :

If sequence of atoms are 56,61 & 2

Then they can produce 3416KJ by fusing 56&61 which results in an atom of value 33.

Then they can fuse 33 and 2 to get energy of 66KJ. So total energy generated is 3482.

But if they cleverly choose to fuse atoms 61 & 2 first then they generate 122 KJ with a resulting atom of value 122.

Then if they fuse 122 and 56, they can generate 6832 KJ. So the total energy is 6954.

Hence Maximum energy that can be generated from this sequence is 6954.

INPUT FORMAT :

Input starts with a number specifying number of inputs(n) followed by n space separated integers

specifying atomic values of n atoms.

Line 1  N,where N is the number of atoms in the  sequence to be fused.

Line 2  a1 a2 a3 .... an . where ai -> Atomic value of i th atom. and two atoms are space delimited.

Constraints:

   0 < ai < 199

   1 < n < 1000

OUTPUT FORMAT:

In Line 1  For Valid Input,print E,where E is Integer stating maximum energy that can be produced

For Invalid Input,print INVALID INPUT .

SAMPLE INPUTS AND OUTPUTS :

Sr.no            Input                Output

1                  3

                    15 75 60           8925

2                  J                        INVALID INPUT

3                  3

                    15 0 6               INVALID INPUT

4                  3

                    5 5 199             INVALID INPUT

5                  4

                    15 75 60 45      18515

                                                   :ANALYSIS:

Here, we will be given a sequence of integers (check with constraints provided, if input doesn't satisfy the constraints , exit by prompting INVALID INPUT ) . We should not change the  sequence .

We have to find a pair of elements (adjacent elements only) which maximizes the produced atom's atomic value ((first element's atomic value* second element's atomic value )%199) from the given sequence . Fuse them ( update total energy(multiplication of atomic values of two atoms) and replace those two atoms with new atom produced from them (its atomic value will be (first element's atomic value* second element's atomic value )%199 ) . Do this until we have only one atom in the sequence (In this case we don't have another atom to fuse with and this condition violates one of the constraints provided ) .

                If you observe, our data-structure is shrinking  during execution. Hence, using linked list will be a good idea .

Here is the   PROGRAM IN C .

      Let me know if you have any different approach .

Lexical Analyzer in C

After FAILING to write a Lexical Analyzer in C by just reading the source file character by character, I decided to follow a different approach to make my task simpler:

1.Trim the lines and store the result in a temporary file.

2.Take the above temporary file as input, open another temporary file to write output, look for signs

of string/character constants and comments  as they can enclose any character sequence,

if found, store that in a global data-structure write some key in place of that in new temporary file,

else write the same to the new temporary file.

After step 2 we will have a temporary file which doesn't contain string/character constants (in their place we will have keys)

and comments.

3. Use this temporary file as input and extract pre-processor directories (store them in data-structure and replace with the key)

write o/p to another temporary file.

4. Now the file contains only identifiers/­keywords/numbers/­operators/delimeters and keys we replaced with .

(If a pre-processor statement contain any string constants they will be extracted and replaced with key .

So, while printing, you need some more lines of code to replace the key with the string-constant)

5. Now read character by character and split into tokens (if you find the key print the details in key) I followed the above steps to avoid confusion.

The program I wrote can respond with some errors.

Here is Lexical Analyzer in C 

  

This program takes file names as arguments.

If you follow those steps you can write program easily even the program is large.

Let me know if you have any other approach. 

General Purpose Merge-Sort

Here is a C program for sorting different types of data in Merge-Sort paradigm . You have to include this program in your application program to use it. And important thing is that you have to specify the type of data you are going to use( Don't worry there is an example). You can sort int,char,char*,float,double,unsigned int,unsigned long types.

Merge-Sort.c contains two useful functions ,those are MergeSort(array,startindex,endindex) and a utility function to print sorted data . Below example uses these .

Here is a C program that uses this program to sort strings ( array of character pointers)

#define type string

#include "MergeSort.c"

int main(void)

    {

    char* array[]={"C programming","Python Programming","Operating System","Unix","Programs for you","How are you"};

    MergeSort(array,0,5);// starting index to last index

    PrintArray(array,0,5);

    return 0;

    }

Here is MergeSort.c .

Let me know if you have any different methods to do this or any questions .