Getting started with PHP and apache

Someone who gives it a thought of using PHP , apache and stuff for the first time will be faced up with a few number of fixed problems . Configuring your apache server , establishing a connection between PHP and apache , stuffs like that . Here is a basic introduction to start using these things and kick off as a web programmer .

Obviously you need to have PHP and apache installed on your system .

$ : sudo apt-get install apache2

$ : sudo apt-get install php5-cli

$: sudo apt-get install libapache2-mod-php5

 

would get you apache and PHP installed on your system  .

Using the appropriate versions is left upto individuals .

Just have a peep into some of the files like :

/etc/php5/apache2/php.ini -----> You would see a lot of variables set to 'ON'  and 'OFF' . You may well have to toggle those values as and when necessary .

 

Try starting , stopping and restarting your apache web server .

$ :sudo  /etc/init.d/apache2 start

$: sudo /etc/init.d/apache2 stop

$: sudo /etc/init.d/apache2  restart

 

Once everything is fine and and perfect  , try out your first PHP script . Script it , save it in a file with a '.php' extension and put your file in the directory '/var/www '. Now you could access this script from your browser

localhost/'scriptname'

and you see the result right there in front of you . Thats just how you enter the world of web programming .

GreaseMonkey : Customizing your webpages

There would have been times when you would have felt if the web page in front of you behaved a bit more according to your like . This might specially happen if the page consists of forms that you fill with data directed to live servers .  In such cases you wouldn't mind customizing the page to suit your needs so that you don't do some nonsense that would result in chaos .

Firefox , i see many using it as their default browser , offers a plugin called 'Grease monkey'  that allows you to do just that . All you need to is to install the plugin , write your own javascripts , install them ( thats pretty easy to do ) and start using them  .

Write your javascripts to customize your webpage . What you need to do in addition is to add some metadata providing extra information to greasemonkey .

The meta data might look as follows :



 

 

 

 

 

 

The first and the last lines are necessary to indicate to the greasemonkey that the script it to be processed by it .

The name and the description are optional . It might prove helpful to you if you have scripted and installed a number of greasemonkey scripts .

The 4th an the 5th line of the metadata are extremely important and needs to be well understood . These lines tell the greasemonkey the URLs on which the script is to be applied and not to be applied .

@include -> specifies the URLs on which the script is to be installed . Here '*' is specified which is just a wildcard and indicates that the script is to applied on all the sites  .

@exclude -> specifies the URLs that are to be left out . It is to be noted that @exclude is processed before @include .

This gives you an idea of the metadata part of the script . Now you may write your own javascript , add your metadata at the beginning and save the file with the extension ' .user.js '  .

To install the script , open the file in firefox and you would see an option 'install' . Just give a click and you are ready to use your greasemonkey script .You could manage your script , disable it , uninstall it as well . Just click

Tools ----> Greasemonkey ----> Manage user scripts ....

Having another plugin 'firebug' may help you in the process of writing the script . This allows you to view the html code of the webpage that is infront of you . Infact the plugin is almost a necessity to help you write efficient code with greasemonkey .

Now you may start writing your own greasemonkey scripts and customize any of the webpages as and according to your like . It's also to be understood that greasemonkey is a plugin of firefox . If you use Google chrome as your browser , you wouldn't need to install any plugin . The facility to customize the webpage is provided by default . You may use the same code that you have written to work with greasemonkey . The metadata and the process of installing is the same and obviously the results are the same as well .

Using Screens

You might have often had the experience where you would have had to open quite a few terminals on your screen simultaneously . This might often be the case when you are doing stuffs like data processing on particular files and you intend not to sit idle during that particular time . What you do is to keep unnecessary number of terminals open on your screen .

You could get rid of this by using the 'screens' option in Linux . This allows you to enter a new screen where you could perform time consuming processes like a data processing operation using the  'awk'  command . Start the process in the screen , exit the screen and now do your own stuff in the main console , go back to your screen after a while and view the results of  whatever operations you had performed . You could do all this stuff without the necessity of opening terminals again and again .

Create a new Screen :

$ : screen -S 'Screen name'

To detach from the current screen :

Use CTRL + a + d

To terminate a screen :

Use CTRL + d

To attach an already created screen :

$ : screen -x 'screen name'

You could keep on creating screens within screens and keep going on as and when needed  .

Semaphores and Synchronization Patterns

Semaphores as we know is a mechanism that is used to solve the issue of synchronization . The concept and use of semaphores is a bit more than what you normally call ' tricky ' .Here we try and analyze a basic synchronization pattern and solve the issue with semaphores .

Have a look into the pattern given below .

statements in THREAD A

strcpy(a , "Hello ");   -  A1
printf("%s\n" ,b);      -    B2

statements in THREAD B

strcpy(b , "World")  - B1
printf("%s\n" ,a);    -  A2

Here we have two threads which consists of two statements each .
Constraint :
What we need to ensure is that the statements suffixed A1 & B1 are executed before the statements suffixed A2 & B2  execute. Here the two threads 'rendezvous ' at a point of execution and is not allowed to proceed until both have arrived .

Without using a mechanism like semaphore , no way is it possible to ensure such a constraint due to the scheduling mechanism that cannot be predicted . Hence we use semaphores to solve this issue .

To ensure that it works according to wish  , we do this :

THREAD A

strcpy(a , "Hello ");  - A1
up(sem1);
down(sem2);
printf("%s\n" ,b);   - B2

THREAD B

strcpy(b , "World");  - B1
up(sem2);
down(sem1);
printf("%s\n" ,a);   - A1

Now we need to give a thought on how this works .
Here we have two semaphores ,sem1 and sem2 as we have two critical sections

Now , how is the synchronization issue solved .?
The 'down ' operation just before the two statements suffixed '2' ensures that the two statements are not executed until the 'up' operation on the corresponding semaphore is not invoked . Hence whichever be the order of scheduling , both the threads rendezvous at a point and will not proceed ( as a result of the 'down' operation )until the next thread arrives (and the corresponding 'up' operation is performed ).

This synchronization pattern as been solved using semaphores .

You could find the solution to these and more such patterns from here .

Memcheck : A Memory Error Detection Tool

Linux distros provide a  tool suite called 'Valgrind' that consists of a number of tools that help you make your programs faster and more correct . The most popular tool out of this is called is memcheck that is used to detect memory related errors in C and C++ programs that can lead to serious issues like  segfaults and even more grevious issues like unpredictable behaviours .

Lets take a look into how we use the tool 'memcheck' so that we detect , try and avoid the memory related issues in our program.

First of all we need to create a memory leak so that we have something to detect .

We write a program that consists of a memory leak . Here is one such in a file ' pgm.c'

1 #include <stdlib.h>
2 #include <string.h>
3 void f(char *s)
4 {
5 char *x = malloc(strlen(s));
6 x[7] = 0;
7 }

8 int  main()
9 {
10 char *s="Hello";
11 f(s);
12 }

As you could see , there are two major memory related bugs in this code:

1) Trying to write in the location x[7] which is out of the allocated memory space .This will lead to what is called a 'heap block overrun' .

2) The memory that is allocated to x remains unused . This memory becomes garbage on returning from the function . In short , you have seen a 'memory leak '.

Now lets try and detect the two problems using memcheck :

You need to have valgrind installed in your system .
$ : apt-get install valgrind
if you don't have it already .

Do

$: cc -g pgm.c

We  compile the program using the -g option so that the line number informations are displayed when using memcheck .

Do

$: valgrind  --leak-check = yes a.out

the option  ' --leak-check ' being set equal to yes displays the informations on memory leak issues .

Now lets look out what are the informations that are being displayed when the memcheck tool is used .

First lets have a look into the 'heap block overrun' problem :

==3350== Invalid write of size 1
==3350==    at 0x80483F6: f (pgm.c:6)
==3350==    by 0x804841D: main (pgm.c:11)
==3350==  Address 0x419102f is 2 bytes after a block of size 5 alloc'd
==3350==    at 0x4023D6E: malloc (vg_replace_malloc.c:207)
==3350==    by 0x80483EC: f (pgm.c:5)
==3350==    by 0x804841D: main (pgm.c:11)

The above few lines is the code that was generated by memcheck  .

'3350' is the process id .

The actual error is seen right at the first line .

'Invalid write  of size 1' .

You get a stack trace right after this line , that

the invalid write has occured at the 6th line as a result of the 12th line . You could see what line numbers '6' and '11' do by having a look into our code , its the point of occurence of the error and the function call respectively.

A line showing the the fact that the location you are trying to access ( x[7] ) is 2 bytes after the allocated area can also be seen added with lines that contain information about the main and the function .These lines provide great help to the programmer especially when the case becomes a lot more complicated .

Now the informations that are displayed about the 'memory leak problem' can also be looked into .

==3350== LEAK SUMMARY:
==3350== definitely lost: 5 bytes in 1 blocks.
==3350== possibly lost: 0 bytes in 0 blocks.
==3350== still reachable: 0 bytes in 0 blocks.
==3350== suppressed: 0 bytes in 0 blocks.

You could view the lines that provide information about the memory leak problem .
The first line of the 'LEAK SUMMARY ' is the most significant to us . It shows the amount of memory definitely lost ( 5 Bytes ). Changes need to be made in the program so that the memory leak is prevented .

Memcheck produces these result which helps the programmer so as to view and correct the memory related issues rather convincingly . It needs to be noted that Memcheck is a 'dynamic instrumentation tool ' and not a static tool like 'lint ' . Hence to detect the memory leaks in a program , the control actually needs to get transferred to that segment of the program where the issues occur . In short you need to invoke the function 'f' from your 'main' so that Memcheck could detect those memory related issues that exists within the function 'f' .

Common Subexpression elimination ( CSE) by the GCC Compiler

Common subexpression elimination (CSE) is a compiler optimization technique of finding redundant expression evaluations, and replacing them with a single computation . This saves the time overhead resulted by evaluating the expression for more than once . We will have a look into this phenomenon by considering a simple code and again taking a walk through its assembly code .

Consider the code that we have written and saved in file ' pgm.c '

main(){
int i, j, k, r;
scanf("%d%d", &i, &j);
k = i + j + 10;
r = i + j + 30;
printf("%d %d\n", k, r);
}

Do :

$ : cc -S pgm.c

$ : less pgm.s

Read the assembly code ' pgm.s '

Scan the assembly code and find out the call to the function 'scanf()' . This is where our area of interest begins . This is because its after calling 'scanf ' that we load the value of the input variables into the registers .

Right after the call to 'scanf ' , i have this in my assembly code ,

movl    -16(%ebp), %edx
movl    -20(%ebp), %eax .

Here we move the values of the two variables 'i ' and 'j ' into registers 'edx ' and 'eax ' .

Now just have a look into our C code and you will see the two expressions as follows :

k = i + j + 10;
r = i + j + 30;

Looking at the two expressions , you would find out the redundant part in the two expressions .

Its that 'i+j' is calculated twice .

Now lets find out what happens in the assembly code :

I had these statements in your assembly code :

movl    -16(%ebp), %edx

movl    -20(%ebp), %eax ----------> We had mentioned these two statements  above .

leal   (%edx,%eax), %eax -------->  values in edx and eax are added and loaded into eax

addl    $10, %eax -------------------->  the constant 10 is added with the value in eax

leal   (%edx,%eax), %eax --------->   values in edx and eax are added and loaded into eax

addl    $30, %eax -------------------->  the constant 30 is added with the value in eax

You could see that there is redundancy in the assembly code .

The statement ' leal(%edx,%eax), %eax ' performs the evaluation of the subexpression ( ' i + j ' ) which is done twice thereby throwing in redundancy and hence creating unnecessary overheads .

Obviously our compiler when asked to perform optimization would avoid this redundancy .This is what is termed as Common Subexpression Elimination ,i.e , the subexpression that is common( ' i + j ' ) in the two expressions is evaluated only once , in essence the second evaluation is eliminated .  Lets have a look into CSE by again peeping into our assembly code  .

Do

$ : cc - S - O3 pgm .c

$ : less pgm.s

Take a look into your assembly code  .

As mentioned above , our area of interest starts from the call to 'scanf ()' .

Instead of those 6 statements that were used to evaluate those two expressions ,

i + j + 10 & i + j + 30 ,

you would find this ,

movl    -12(%ebp), %eax ---------------->  move the value of the variable 'i' into eax

addl    -8(%ebp), %eax -------------------> add the value of the variable 'j' with 'i' stored in eax .

leal    30(%eax), %edx -------------------> adds 30 with eax ( contains the sum of i & j ) and stores in edx

addl    $10, %eax ---------------------------> adds 10 with eax ( contains the sum of i & j ) and stores in eax .

Here the second statement performs the evaluation of the subexpression , ' i + j ' . You could get it quite clearly from the code segment that the redundancy that was found in the unoptimized assembly code has been eliminated by the compiler .

The later 2 statements perform the evaluation of the expressions

( i + j + 30 )   and    ( i + j + 10 ) respectively .

We have just used a very simple case of CSE , but this optimization technique could be used in even more useful cases . Consider :

k = f() + g() + 30

r = f() + g() + 10

where f() and g() are functions . In an unoptimized code , the technique of CSE wouldn't be used and hence there would be overhead due to the redundancy added with the more serious problem of having to call each function twice . The technique of Common Subexpression Elimination avoids this very redundancy  .

Function inlining

Function inlining is performed when a request has been made to the compiler to perform optimization on the code . The compiler will try (its important to remember that ,it is a request made to the compiler, not an order) and insert the complete body of the function in every place in the code where that function is used so as to eliminate the time overhead when the function is called . We could get an idea of function inlining by peeping into the assembly code generated by the compiler .

We do this with the help of a small program :

int sqr(int x)
{
return x*x;
}

main()
{
printf("%d\n", sqr(10));
}

We have the program written in a file  'pgm.c'

Do :

$: cc -S pgm.c

We could now view the assembly code generated by the compiler

Do:

$: less pgm.s

I found out the following lines in the 'main' function of ' pgm.s '

movl    $10, (%esp)
call    sqr

You would have the idea cleared up

The constant '10 '  is stored in the stack , and the call to the function 'sqr ' is made . The result of squaring up 10 is performed in the function 'sqr' . This obviously would create overheads for invoking the function .

Now consider the case where you have requested the compiler to perform all optimizations on your code .

$ :cc -S -O3 pgm.c

Now have a look into your assembly code .

$ :less pgm.s


Now just have a look into the your 'main' function and find out what you see where you had seen the previous two lines that i did mention above .

You would just find a singe line corresponding to those two lines which you had found in your assembly code that was not optimized .

This is what i found ,

movl    $100, 4(%esp)


The final value that you obtain after finding the square of 10 ( i.e 100 ) is has been moved into the stack , but where is the call to the function 'sqr' ?

You have just seen ' function inlining '. The function body had been inserted at the point where the function was used and the value '100 ' calculated at compile time instead of performing the calculation at run time .This saves a lot of time that would have been required to calculate the value of '100' by making a call to the function at run time .Performing function inlining avoids this .

Python DB-API

Python is one of the more popular Open Source programming languages, owing largely to its own native expressiveness as well as to the variety of support modules that are available to extend its capabilities. One of these modules is DB-API, which, as the name implies, provides a database application programming interface. We will have a discussion about how to connect and use a General purpose database system like Mysql with Python. The DB API provides a minimal standard for working with databases, using Python structures and syntax wherever possible .

4 Steps of the Python DB-API includes the following:

1) Importing the API module. 

2) Acquiring a connection with the database.

3) Issuing SQL statements and stored procedures.

4) Closing the connection

There are lots of database systems that are available .Here we use Mysql as our database system .You could also use database systems like PostgreSQL, SQL Server etc. Python's DB-API uses a two-level architecture in which the top level provides an abstract interface that is similar for all supported database engines, and a lower level consisting of drivers for specific engines that handle engine-dependent details. This means, of course, that to use DB-API for writing Python scripts, you must have a driver for your particular database system. Since we have fixed our database system as MySQL, DB-API provides database access by means of the MySQLdb driver . Therefore we need a module MySQLdb in Python '' .

At first , we need to get Mysql installed in our system.

$: apt-get install mysql-server-5.0

Just try and enter into the interactive prompt of mysql .

$: mysql -u 'user' -p

You will get your mysql interactive prompt where you could just brush up your sql knowledge.

Step 1) Importing the API module.

You need to make sure that you that have MySQLdb installed on your machine.

Do this:

$: python

>>>import MySQLdb

Obviously if you dont have it installed , you would be getting this :

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ImportError: No module named MySQLdb

To install MySQLdb module, download it from MySQLdb Download page and proceed as follows:

$ gunzip MySQL-python-1.2.2.tar.gz
$ tar -xvf MySQL-python-1.2.2.tar
$ cd MySQL-python-1.2.2
$ python setup.py build
$ python setup.py install

Now do

$ : python

>>>import MySQLdb

>>>

We have done with Step 1) out of the 4 steps of the Python DB-API .

Now we move into step 2). The prerequisite for performing step 2) of the DB-API is that you need to create a database ( 'Persons' in our examples to follow ) in mysql .

You could do this by :

$: mysql -u 'user' -p

Enter mysql .

Do :

mysql>CREATE DATABASE Persons;

mysql>Query OK, 1 row affected (0.03 sec)

Once you have done with this

Step 2 ) Acquiring a connection with the database.

 

conn = MySQLdb.connect (host = "localhost",

user = "user",

passwd = "asdfgh",

db = "Persons")

Here we open a database connection using the 'connect' function of the MySQLdb module.

The four parameters that are passed to the function 'connect' are :

host --      the system in which the database is created

user --      the user who is trying to acquire a connection with the database ( the user must be authenticated with mysql if the attempt to create a connection needs to be successful.

passwd --      the password of the mysql database system .

db --      the name of the database created using mysql .

If the 'connect()' call succeeds, it returns a connection object that serves as the basis for further interaction with MySQL( here 'conn'). If the call fails, it raises an exception .Therefore you better perform exception handling so that you get to know more about the root cause of the error.

try:

conn = MySQLdb.connect (host = "localhost",

user = "root",

passwd = "asdfgh",

db = "Persons")

except MySQLdb.Error,e:

print "Error occured ",e.args[0],e.args[1]

sys.exit (1)




Here on an unsuccessful attempt to make a connection , an exception is raised ( MySQLdb.Error ) , the information about the error is stored in e.args[1] .

 

Step 3) Issuing SQL statements and stored procedures.

Now we need to create a cursor object for the connection between Python and mysql so that all the functions performed by sql are performed within from Python now . We create a cursor object using the ' cursor()' method .

We are all set to execute sql statements in an Object oriented environment , and thats using the 'execute()' function . Any sql statement can be called in from Python using the 'execute()' function.

Consider you want to create a new table in our database 'Persons' .

cursor.execute("""

CREATE TABLE PERSON

(

ID int,

lastname CHAR(40),

firstname CHAR(40),

City CHAR(40)

)

""")

You have created a table named 'PERSON ' with fields as mentioned above .

As you would imagine , any other statements could be performed as such , for eg.

cursor.execute ("""

INSERT INTO PERSON (ID, lastname,firstname,City)

VALUES

(1,'KUMAR','SUNIL','KANNUR'),

(2,'JOHN','HARI','KOTTAYAM')

""")

or

cursor.execute ("SELECT * FROM PERSON WHERE City like 'K%'")

and any of the sql statements .

Step 4) Closing the connection

conn.close()

Here we have terminated the connection after all our need with the DB-API has been done with . The DB-API allows us to update , insert , retrieve and modify within a database in a simple and elegant way .

We have tried and demonstrated a simple example of how to use the Python DB-API .

Using Python with Sql,we have found an object-relational mapping where the object-oriented programming paradigm of Python meets the relational paradigm of Sql. An object-relational mapping is a bridge between the two worlds. As we saw , it lets us define classes that correspond to the tables of a database. Later , we use methods on those classes and their instances to interact with the database .

Implementing the Avl Tree

AVL Tree is a self-balancing binary search tree and it was the first such structure to be invented. The tree is said to be balanced because the difference in the heights of the child subtrees differ by atmost one. The operations Insertion, Deletion and Lookup on an Avl tree is of the order of  Log n because of this balancing act. Here we take a look into the implementation of an AVL tree .

First we need to give a thought on the term 'balance Factor' and on the major operations that are involved in the making of such a tree.

Balance Factor:Balance factor is associated with each node of the Avl tree. Its the difference between the heights of the left subtree and right subtree of that particular node.

Balance factor = height of left subtree – height of right subtree.

A balance Factor of 0 , +1 or -1 for each and every node of the tree indicates that its balanced. Whenever the balance Factor of any of the nodes equals – or + 2 , the tree becomes unbalanced and needs to undergo balancing.

Now lets just peep into the major operations that are involved in the build up of the tree.

There are 3 of them

1) Insertion:2) Deletion:3) Rotation:

Insertion is the usual process. There is nothing special in inserting a node into an Avl tree than in inserting it to a normal binary search tree.

Deletion is again the same with a minor difference which we will look in to as we continue.

Rotation is the balancing act- The operation that distinguishes an Avl tree from the normal binary search tree. Rotation needs to be performed whenever the tree goes out of balance – this could happen as a result of the first two operations ( Insertion and Deletion ). The Balance factor may go beyond 1 and hence the tree will have to be balanced so that it remains as an Avl tree. Each of the three operations , specially that of rotation will have to be given due care in building up an Avl tree.

You could sum it up this way :

Each insertion in an Avl tree is a combination of normal insertion into a binary search tree added  with finding out whether the tree is unbalanced or not followed by rotation if necessary.

Each deletion in an Avl tree is a combination of normal deletion into a binary search tree added with  finding out whether the tree is unbalanced or not followed by rotation if necessary.

Before we get into more details of each of them , we will have a look into the way each node is implemented in the Avl tree.

Each and every node in the Avl tree is implemented as a structure .This is same as what is done in an ordinary BST , since Avl tree is itself a BST.

struct node{

int data;

struct node *parent,*left,*right;

}*p,*root=0;

The field 'data' contains the actual data that is to be stored in the node .There are three pointers of the type 'struct node*'.

*left –> points to the left child of the node

*right –> points to the right child.

*parent –> points to the parent node .



Now lets get into the details of the different operations performed on the Avl tree.

Inserting into an Avl Tree can pictorially be represented as follows:



Obviously , there are other functions that are involved in the process, but the ones shown in figure are the significant ones.

avl_insert : As discussed earlier insertion into an avl tree consists of the normal insertion followed by the checks for balancing and rotation if necessary. Normal insertion is performed first . Then the function self_bal() is called :

self_bal() : The newly inserted node would obviously be balanced since it wont have any children. Therefore the balance factors of the nodes that come above the inserted node in the tree ( starting from the parent ,right upto the root ) is to be checked. The function 'self_bal' invoked 'balance()' which performs the further tasks. Again, since a newly created tree is always balanced and since parent of the root points to NULL , the function 'balance()' should not be called if the newly inserted node is the root itself.

balance() : Invokes the function bal_fac() and checks if the balance factor is equal to +or- 2 . If yes , calls the appropriate rotate function.

bal_fac() : Finds out the balance factor for each node.

rotate() : Here rotate() is the just the cohesive name for the two types of rotate functions . According to the balance factor , the appropriate 'rotate' functions are called. We will discuss them in detail later.

The pictorial representation of 'delete()' would be no different.



By now you would have understood that the central aspect in building up the whole Avl tree is the rotate() function, but before we get into implementing the 'rotate()' function , its of prime importance that we give a little more thought into implementing the 'delete()' function in the Avl tree. As mentioned above , there is just a minor change that needs to be made , due to the self balancing nature of the Avl tree.

While performing a 'delete()' function in a normal BST, we need to look into 5 different cases of how a particular node could be deleted and replaced with another one. Just peeping into them:

1)The victim node being a leaf node.

2)The victim node having a right child.

2.1) The victim node having a right child with a left subtree.

2.2) The victim node having a right child with no left subtree.

3)The victim node not having a right child.

3.1) The victim node having a left child with a right subtree.

3.2) The victim node having a left-child with no right subtree.

Certainly , from what we have discussed until now, its clear that one of these conditions never happens. You might have guessed it by now.

Case 3.1) would never happen in an Avl tree. This could be explained with the following figure.

Consider you want to delete the node '10' after adding '9' to the tree , but adding '9' to the tree would leave it unbalanced.



Hence the tree will be rotated so that it becomes balanced ( how?, we will come to know shortly) before you could delete '10' . Hence there will never be a case of a victim node have a 'left child with a right subtree' and does not have a right child of its own.

Now , its time that we move into the  in the creation of an Avl Tree, the 'rotate() ' function.

Rotation ,as mentioned ,follows up a deletion from or an insertion into an Avl tree in such a way that it destroys the balanced nature of the Tree.

There are 4 kinds of rotation which are implemented using 2 different rotation functions.

Its crucial at this stage that the following points are understood.

Balance factor of a node = +2 implies that the node ( and ultimately the tree) is unbalanced because of the left subtree of the node and there will be one right rotation for sure.

Balance factor of a node = -2 implies that the node ( and ultimately the tree) is unbalanced because of the right subtree of the node and there will be one left rotation for sure.

Whether a single rotation needs to be done or whether the tree needs to be rotated twice depends upon the balance factor of the child of the root of the subtree that is unbalanced. You needn't scratch your head on this , stuffs that follow would lighten up things.

Let 'point' be the root of the subtree which has made the tree go out of balance . The 4 kinds of rotation are:

1)left – left rotation: If balance factor(BF) of point is 2 and the BF of the left child is > 0 , then a single 'right' rotation would do it for you.

2)left – right rotation: If BF of point is 2 and the BF of the left child is < 0 , then a 'left' rotation followed by a 'right' rotation would do it for you.

3)right – left rotation: If BF of point is -2 and the BF of the left child is > 0 , then a 'right' rotation followed by a 'left' rotation makes the tree balanced.

4)right – right rotation: If BF of point is -2 and the BF of the left child is < 0 , then a single 'left' rotation would be enough.

We will discuss rotation which happens as a result of the tree being unbalanced after an insertion or a deletion has been performed. The 'rotation' function is independent of whether the previous function was a deletion or an insertion , it depends only on the current structure of the tree.

Left-Right Rotation & Left-Left Rotation

Consider the figure :

Here the point of imbalance is '23' and the reason for imbalance is the left subtree of '23'. Hence performing a 'right' rotation is essential . Now the left child of '23' has a BF of -1 ( < 0 ) . Hence a left rotation also needs to be performed. This leads to a left-right rotation .

left rotation : Left rotation is performed by invoking the rotate_left() function. The two parameters that are to passed to the function are 'root' and 'pivot' .

Root ---> point of imbalance , I.e '17'

Pivot ---> right-child of the point of imbalance I.e '19'.

 

The left rotation has been performed.

Now our problem has been reduced to performing a left-left rotation , you could see that from the figure .That is ,we need to perform a single 'right rotation':

right rotation : The right rotation is performed by invoking the rotate_right() function. The two parameters would be :

Root ---> point of imbalance : I.e 23

Pivot ---> left-child of the point of imbalance I.e '19'.

 

 

 

The right rotation also has been performed. Now you may have a look at the tree and would find out that its balanced .

Right-Left Rotation & Right-Right Rotation.

Consider the figure above :

Here the point of imbalance is '17' and the reason for imbalance is the right subtree of '17'. Hence performing a 'left' rotation is essential . Now the right child of '17' has a BF of 1( > 0 ) . Hence a 'right' rotation also needs to be performed. This leads to a right-left rotation .

right rotation : right rotation, as mentioned above is performed by invoking the rotate_right() function. The two parameters that are to passed to the function are 'root' and 'pivot' .

Root ---> point of imbalance , I.e '23'

Pivot ---> left-child of the point of imbalance I.e '19'.

The right rotation has been performed.

Now our problem has been reduced to performing a right-right rotation .That is ,we need to perform a single 'left rotation':

left rotation : We have seen that left rotation is performed by invoking the rotate_left() function. The two parameters would be :

Root ---> point of imbalance : I.e '17'

Pivot ---> right-child of the point of imbalance I.e '23'.

The left rotation also has been performed. The tree has been balanced .We have found out how a tree could be balanced through rotation.

There is another issue that we need to deal with while performing rotation. Two questions that we need to consider here are...

1)What happens to the left node of the pivot during a left rotation.?

2)What happens to the right node of the pivot during the right rotation.?

Consider the following figure .

The tree as you could see is unbalanced with the root ('23') being the point of imbalance, the left subtree being the reason for the imbalance.. Since the BF of the left child of the root = -1 ( < 0 ) , we need to perform a left – right rotation . I.e a left rotation followed by a right rotation . For performing the left rotation , the root is '17' and the pivot is '19'. As you could see from the figure ,the left child of the pivot is marked 'L' . Our question is what exactly happens to this 'L' after the left rotation has been performed. ? The answer is right there in our next figure .

L has become the right child of '17 ' . To be more precise ,after a left rotation, 'L'( the left child of the pivot) has become the 'right child' of the node which was the parent of the 'pivot' before the rotation was performed.

As you could see, the tree still remains unbalanced as we have not performed the 2^nd phase of our left-right rotation . We perform the right rotation and make the tree balanced .

I think , by now you would be able to guess out the solution for the second question that we had asked .

What happens to the right node of the pivot during the right rotation.?

The answer is certain , this is exactly the complement of what happens after a left rotation that we have just seen . After performing a right rotation , the right child of the pivot becomes the left child of the node that was its parent before the rotation was performed.

Here , I have tried and dealt with almost all issues that come up in the implementation of an Avl tree. You could download the complete source code here

GNU make

The make utility determines which pieces of the program needs to be recompiled and issues instructions to recompile them.GNU make is the most popular make available. Lets get into the working of make with a simple example but please do read THIS before moving into further details.

By reading that, you would have understood that our ultimate aim is to produce a file '_avl.so' so that the C module 'avl.c' could be extended into Python.
Lets check what exactly do we need to do here.

We begin with 2 files namely 'avl.c' and 'avl.i'. We need to create a wrapper file at first . This is done by:

$: swig -python avl.i

Next what we need to do is that we need to create 2 object files for the respective C files- i.e we need to produce 'avl.o' and 'avl_wrap.o' from 'avl.c' and 'avl_wrap.c' respectively.
We do this by:

$: gcc -c avl.c avl_wrap.c -I /usr/include/python2.5/

The last and final step is to create '_avl.so' from the 2 object files.

$: ld -shared avl.o avl_wrap.o -o _avl.so

The dependencies and actions are quite clear now.


Typing in these commands time and again would be a tedious and ineffective job for anyone. We could automate the whole process by writing a file called Makefile and use the 'make' utility.

The Makefile for performing the above steps would be as follows:



A Makefile has the following format.



Its important to note that the 'ACTIONS' line begins with a TAB as it is a part of the syntax of a Makefile. Anything other than TAB would be harmful.

Lets check out how things work out.

$: make

This would cause GNU make to start executing the commands in Makefile.GNU make starts from the very beginning of the Makefile. The first set of 'TARGET-DEPENDENCIES-ACTIONS are checked in.

The TARGET is '_avl.so' : The DEPENDENCIES are 'avl.o and avl_wrap.o' and the ACTION that needs to be performed is

ld -shared avl.o avl_wrap.o -o _avl.so

But at present 'avl.o' and 'avl_wrap.o' are not available. To Generate them the next set of the Makefile is to be checked. The same problem exists there as well . Hence the 3rd set in the Makefile is reached where the DEPENDENCY is 'avl.i' which exists at present. Hence the action

swig -python avl.i

is executed , the target 'avl_wrap.c' is generated .
Now the second set in the Makefile can be compiled followed by the compilation of the first set. The procedure that takes place here is recursive .All the three actions are executed , the TARGETS are generated from the ACTIONS and DEPENDENCIES and finally we obtain '_avl.so'.

You could see another line in the Makefile that has not been mentioned upto now.
make remove
make remove is the TARGET and the ACTION that needs to be performed is
rm avl.o avl_wrap.o avl.py _avl.so avl_wrap.c avl.pyc

$: make remove

will remove all the unnecessary files in the directory when you are planning to start from the beginning.

If you would like to have a test on the intelligence of 'make' , you would be pretty surprised.

Lets deal that case with an example as well.

DO:

$: swig -python avl.i

We have executed the first command manually.
Now do:

$: make

and you will find that make executes only the other two commands that is included in the Makefile.
This again shows the recursive nature of the make process. The Makefile is read from the top. On reaching the second set , GNU make realizes that both the dependencies 'avl.c' and 'avl_wrap.c' are available and executes the ACTION to produce the TARGET 'avl.o' and 'avl_wrap.o'.

Now once again do
$: make

You would get a message as follows:
make: `_avl.so' is up to date.

This again brings to the fort-light the power of make. The final target '_avl.so' has been found to be 'up to date' and hence there is no question of having to execute the commands in the Makefile . GNU make, Richard Stallman and Rolland Mcgrath's creation, has recognized this.

SWIG(Simplified Wrapper and Interface Generator).

Scripting languages like python presents a lot of ease to the programmer while coding , but the fact remains that there are certain tasks that would screw you up when attempted in Python. So the coding is done in a more flexible language like C and the modules are imported in Python. SWIG is a tool that is used for extending your C programs into python and make the functions callable from Python.

Here we discuss how to import a C module into Python using SWIG.
Installing SWIG in your system ,if you haven't already, is the first task.

$:apt-get install swig

would do that for you.

Now its better you create a directory for the entire purpose and setup yourself within it.
Consider you have a C file ,avl.c , as our example (Avl is a height balanced Tree ,avl.c is an implementation of such a tree.) You could download the source code for avl.c here.

Our first step is to create an interface file 'avl.i' for setting up the interface. 'avl.i ' consists of the declarations of the various functions and global variables that are used in the file 'avl.c' and are prefixed with 'extern'.

%module avl

%{

extern struct node *root;

extern struct node *p;

%}


extern void insert(struct node* move,int item);

...
...
...
...

The 'avl.i ' file would like as above:
Now we have two files in our directory ,

avl.c & avl.i

This is all that we have to code for the task of extending a C module in Python. Now its all about SWIG.


Lets move further: Do the following.

$:swig -python avl.i

now have have a look into your directory and you will find two more files there .

avl.py & avl_wrap.c
avl_wrap.c is the wrapper file that has been created for the purpose of extension . Wrapper functions act as a glue layer between languages.

$: gcc -c avl.c avl_wrap.c -I /usr/include/python2.5/

You could now see 2 more files present in your directory.
avl.o & avl_wrap.o

These two are the object files that have been created for avl.c and avl_wrap.c respectively.

$: ld -shared avl.o avl_wrap.o -o _avl.so

This is the last thing you need to do before you could use start using your C module in Python.
Check your directory and you could see a new file , '_avl.so'. This is the shared object file that has been created .
If you create a make file for these , then obviously you wont have to go doing these tasks repeatedly.
Now ,the python module corresponding to the C module avl.c has been created which means that now you could start using it.

$: python

>>>import avl
>>>avl.my_insert(10)
>>>avl.my_insert(20)
>>>avl.traverse(1)

The source code can be downloaded here.

Evaluation of Scheme in Python

Those who have ever gone through the SICP ( Structure and interpretation of computer programs) , would have come across the implementation of a Metacircular evaluator ( an evaluator written in a language that it evaluates) for scheme in the 4rth Chapter.


Motivated by that , and drawing ideas from the wizard book , an evaluator for Scheme is created in Python, so that Scheme statements evaluated in Python.

The creation of a metacircular evaluator for scheme contains prominently of two steps:

1) Eval: To evaluate a combination (a compound expression other than a special form), evaluate the subexpressions and then apply the value of the operator subexpression to the values of the operand subexpressions.
2) Apply : To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment.



Implementation of the Evaluator in Python:

Before getting into the creation and implementation details of the evaluator , please read this.
Now that you have got an idea about the concepts of environment , lets get into further details of creation of the evaluator.

The first process is basically to parse the user Input and use it in a way so as to evaluate it. After parsing ,the user input is provided to the function gravity().This particular function performs the task of classifying the user input and route them to appropriate functions. This is similar to 'eval' in the scheme metacircular evaluator implemented in SICP.
According to the user input , the appropriate functions are performed.
Different functions implemented in the evaluator.

evaluate():
This function could be compared with the 'apply' procedure implemented in SICP. The function checks for different operator and its corresponding operands. The operator is applied to the operands and the result returned.

opdet():
The function is called from 'evaluate()' , it takes in a list and returns the operator that has to be applied to the operands.



If a simple expression is provided just to perform basic arithmetic and logical operations , only these two functions are invoked after the gravity () function and we obtain the result. The situation, as is obvious would be a little different when relatively complex tasks are give ( such a processing of an 'if' statement , a function , an assignment operation, a recursive function and so on.


Processing of an 'if' statement involves invoking many more functions.

if_begin_eval():
This function involves the presence of any variables involved in the 'if' statement and fetches the value of such variables from the environment.

if_eval() :
This particular function is used to evaluate the 'predicate ' of the 'if' statement and returns the result of the 'if' statement. The function invokes the 'evaluate()' function and would process the entire 'if' statement according to the value returned by 'evaluate()' .
If a simple 'if' statement'
( if ( > 4 5 ) 4 5 ) is inputted:
if_eval() would pass the predicate part ( > 4 5 ) to 'evaluate()' and process the if statement according to the returned value. Here the value returned by 'evaluate()' would be 0, since the condition ( 4 > 5 ) is not true. The value returned by the 'if_eval()' would be 5.

if_cons_alt():
The function evaluates the consequent and alternative of the 'if' condition'. A separate function for the process would be specially helpful when the if statement consists of larger expressions and values.
The function would return back a 2 element list of the final values obtained after evaluation of the consequent and alternative.



Evaluation of procedures would take us through a different path. We need functions that can extract, evaluate and execute a function. We also need a function to test whether the inputted procedure is recursive or non-recursive.

exec_call():
Checks whether the function is a simple function of the sort :
( define ( lambda ( square ( x ) ( * x x ) ) ) non-recursive
or of the sort:
( define ( lambda ( fact ( x ) ( if ( = x 1 ) 1 ( * x fac ( - x 1 ) ) ) ) ) ) recursive :
executes the procedure if non-recursive.

extract_funcbody():
extracts the body of the function. Passes the body of the function to evaluate_funcbody .

evaluate_funcbody():
Fetches the value of the variables in the function body and returns back the function body to extract_funcbody(). This function is invoked only when the procedure is non-recursive.

exec_func_body():
Fetch the value of the variables in the function body . This function is invoked only when the inputted procedure is recursive.



Use of the module ops().
You would see a module named ' ops' being imported. This module consists of certain functions that can be performed on lists. The module is imported so as to get a feel of the way programming is done in scheme , any operation on lists can be performed on lists using 5 basic functions. The attempt has been made to stick to the combination of these basic operations rather than using the full functionality of Python.

The source code of the project can be obtained here.

Concept and creation of Environment

One of the most important thing you need to grasp while doing a project on interpreters and evaluator is the idea of an environment. Within the program the environment is a collection of the names(whether variables or functions) and its corresponding values. While using such names you will need an environment where you can store the value of those names so that you could fetch it for further use. While implementing the evaluator for scheme in python , the concept of environment was implemented using associative arrays in python. 3 dictionaries were used to implement the concept of environment. Lets go through a bit of details on the creation and use of environments.

Consider writing the scheme statements:

scheme>>>( define n 7 )
scheme>>>( define s 6 )
scheme>>>( if ( > n s ) n s )

In our 'if' statement we have not specified the exact value , but instead we have used variables. The question comes then that from where do we retrieve the values of those variables.
The answer is simple: 'Here the variables are global variables and are accessible from anywhere within the program'. Hence we need create a dictionary which consists of 'n' and 's' as its keys and their values as the values of the dictionary. This dictionary is created when the statement 'define ( not followed by a parenthesis) is inputted.

1)dict={'s':'7','n':'6'}

Obviously we cannot use this dictionary for all our purpose. We also need a dictionary where we could store variables and values that are local to a function. We have created another dictionary for this very purpose .

Consider the following:
scheme>>>( define ( sq ( lambda ( x ) ( * x x ) ) ) -----> statement 1
scheme>>>( sq 4 ) -----> statement 2

When the second statement is executed ,a dictionary 'local_dict' is created where this value 4 is associated with the variable 'x'.

2)local_dict={'x':'4'}

We use the 3rd dictionary for associating a function with its body. When the 'statement 1' above is inputted , a dictionary 'func_dict' is created which contains the 'function name' as its key and the 'body' as its value.

3)func_dict={'sq','( lambda ( x ) ( * x x ) )' }

We have functions 'create_env ()' and 'create_localenv()' for creating the first and third dictionaries that we have mentioned above. The second dictionary is created within the function 'exec_call()' where the processing of each function is started. Hence its appropriate to create the dictionary needed only for the local use of that function within exec_call().

Analyzing the Tinypy Virtual Machine

The major task in tinypy is to analyze the working of the virtual machine. Analyzing and understanding its source code is, obviously, the major challenge that is faced. The code itself is not well arranged and the lack of proper documentation makes the challenge even bigger. Proper use of the GNU debugger, 'gdb', and the indexing tool, Ctags makes the process of analysis of the VM a lot simpler. Perhaps the best way to understand the working of the VM is to use the VM to execute the byte code of a simple python program and see and understand the actual flow of control. Here a sample program 'sample.py' is used:

def add(a,b):
c = a + b
return(c)
print(add(1,9))


Note that the use of the parentheses for built-in functions too is a part of the syntax in TinyPy. Obtaining sample.tpc is explained here.

cc vmmain.c -1m
./a.out sample.tpc

gives you the output:
10

Understanding the flow of control for this program would give an idea of the working of a segment of the virtual machine.
Each time the VM is invoked, a new instance of the VM is created .
tp_vm *tp =tp_init(argc,argv);

The key point to be understood in the analysis of VM is that each object in tinypy is stored as a union in the C API.
Lets get into the details: tp_obj is the tinypy's object representation.

typedef union tp_obj {
int type;
tp_number_ number;
struct{int type;int *data;}gci;
tp_string_ string;
tp_dict_ dict;
tp_list_ list;
tp_fnc_ fnc;
tp_data_ data;
} tp_obj;

The union tp_obj with its fields are shown. The field 'type' of the union indicates the type of the object. A type value of 1 indicates that a number is being used, type = 2 indicates object is a string and type = 4 indicates a list. In our sample program, our objective is to add two numbers 'a' and 'b' and print their output. A function in the virtual machine 'tp_add' does the job of adding two arguments that is passed to the function as input. The arguments could be numbers, strings or lists. Lets analyze the function 'tp_add'.

tp_obj tp_add(TP,tp_obj a,tp_obj b)

The Function definition of 'tp_add' contains three arguments:
• TP -> the VM instance
• tp_obj a -> the union variable representing the object 'a' in the sample program
• tp_obj b -> the union variable representing the object 'b' in the sample program

Within the function tp_add, the type of the two objects are checked and the appropriate function is performed. In our example, two numbers are to be added. As we mentioned above, 'a' and 'b' are stored as unions and the union contains fields for types such as number, strings, lists etc. We access the field tp_number_ in the union 'a' as 'a.number'. 'number' is a variable of the structure tp_number_ which contains a variable 'val' that stores the exact value of the number . Therefore a.number.val would give you the actual object . Analyzing the addition of strings would be interesting as well. 'a.string' would give you the union which represents the string object. The union tp_obj contains a field tp_string_ which is a structure and includes the pointer that points to the address where the string 'a' is stored. The structure of tp_string_:

typedef struct tp_string_ {
int type;
struct tp_string_ info*;
char const *val;
int len;
} tp_string_;

An idea about the manipulation of lists would do no harm to our primary objective, the study of the working of the VM. Consider two simple lists in python :
a = [1,2,3] , b = [4,5,6]

Again we start from tp_add which needs us to go back to our function. The VM uses a function 'tp_extend' which returns a union that contains the new (extended) list. You would see that the value of the field 'type' of the union that is returned would be 4 which indicates a list. Access the field 'list' as 'a.list'. 'list' is a structure variable that includes a pointer *val that points to another structure '_tp_list':

typedef struct _tp_list {
int gci;
tp_obj *items;
int len;
int alloc;
} _tp_list;

The pointer *items as you could see is of type tp_obj and de-referencing it would give you the union tp_obj. This union contains a single element of the list. Starting from the function tp_add:

*r.list.val -> items

would give you the union mentioned above. Accessing the field 'val' of the field 'number' (variable of the structure tp_list_) of the union would give you the element of the list. Now , the obvious question is how do we obtain the next element of the list. For this you need to have some idea about the storage of unions.

r.list.val -> items

would give you the address of the union. Suppose the address be '0x96ca048' . Now to obtain the union which contains the next element of the list, you need to add the address of the current union with the size taken by each union (sizeof(union)).
Union containing the next element of the list = Address of the current union + size of each union. For example :
r.list.val -> items = 0x96ca048 + 10
would give you the union that stores the next element of the list . The size of the union is 10, in hexadecimal = 16 bytes.


The path of tp_add can be traced using the 'bt' option in gdb. The path of the function tp_add is as follows:

An Overview of TinyPy

TinyPython is a minimalist implementation of Python in 64K code. It is a parser and byte-code compiler written in TinyPython itself. It is also fully bootstrapped in the sense that initially, TinyPython converts a Python script (.py) into a special TinyPy byte-code format (.tpc), and this generated code is then passed into a subset of the TinyPython source code called the Virtual Machine, where the actual execution takes place.

One can even extend the idea that if the VM is compiled into a low-level format adaptable to a particular micro controller, then the VM will reside inside that chip, and any .tpc files can be downloaded into the chip as its input.

As outlined above, TinyPy comprises of two phases: the byte-code generation, and the execution of the byte-code in the TinyPy Virtual Machine. Out of these, the first phase will not be mentioned here.

Building Up
The TinyPython source code used was downloaded from here. Initially, the file listing will look like the following figure.



You can find that the 'build' folder will be empty. The 'doc', 'examples' and 'modules' folder may or may not contain any documents, Python scripts and batteries (or modules) respectively, depending on the downloaded package. The LICENSE.txt and README.txt are self-explanatory names. The CHANGES.txt contain a record of all the changes that the author of TinyPy thought of making in the source code at some point. The ROADMAP.txt gives a brief description of the features of TinyPy, and an idea about the future developments to be implemented. The 'setup.py' contains the initial code to build the TinyPy from scratch. At the terminal, type as follows:
python setup.py linux

It is implied that you need a Python interpreter available in your system. The 'linux' option is to specify that the code will be compiled so as to make it work in a Linux environment. After running this command, a new executable 'tinypy' will appear in the 'build' folder as shown.



To fully bootstrap and test TinyPy, give the command as,
python setup.py linux boot

Now, in the 'tinypy' folder shown in the above figure, two new executables, 'tinypy' and 'vm' will appear, which are the TinyPy parser, and Virtual Machine respectively. It can be noticed that all the .pyc files for the corresponding .py files have been generated by the Python interpreter. In addition to that, some test scrips - named as Temp - will be invoked too. The most interesting thing will be the presence of new .tpc files for some of the initial .py files. The general usage and some options available are listed below.

python setup.py command [option] [module]
• 64 k - build a a64k version of TinyPy source code
• blob - build a single tinypy.c and tinypy.h

The tinypy folder will now have the following contents: Out of these, the 'py2bc.py' script is used to convert a user-generated Python script into its corresponding .tpc file. The format will be:
py2bc.py sample.py sample.tpc

Here, tinypy_path is the path (relative to current position) of either the tinypy executable in the 'build' folder, or the one in the 'tinypy' folder. 'sample.py' is the name of the user-script. 'sample.tpc' is the name given for the byte-code converted file. Or you can simply give it as:
python py2bc.py sample.py sample.tpc

Finally, the generated byte-code (.tpc) is to be passed into the VM for compilation and execution. Assuming the current directory as 'tinypy' folder, it is done as:
vm sample.tpc

Or logically,
gcc vmmain.c -lm ./a.out sample.tpc

The 'vmmain.c' will be present in the 'tinypy' folder. It is the main function of the VM which runs and automatically links to all the other files necessary for the VM. It is necessary to link the math module too, hence the option '-lm'. And now the output is obtained and displayed. For a better picture, the files actually needed for VM are:



Writing and compiling the code only accounts to half of the process. The other half is debugging and understanding the flow of control within the source code. To do that, make use of the GNU debugging tool, 'gdb'.
gcc -g vmmain.c -lm gdb ./a.out

Inside the 'gdb', you can set breakpoint for any function. Then run the process for the byte-code you need. Here, 'sample.tpc' is used as example.

(gdb) run sample.tpc OR r sample.tpc

Another essential tool will be 'ctags'. After its installed, go to the 'tinypy' folder and build the tag stack as follows:

ctags *.c *.h

You can see that a new file named 'tags' is now available. Now when you are inside a .c or a.h file, you can use 'ctrl + ]' and 'ctrl + T' to jump back and forth between cross references spanning different files.

Find the Endianity of your Processor:

Your processors can be of two types:
1)Little Endian : Little Endian means that the low-order byte of the number is stored in memory at the lowest address.For example, a two byte short int would be stored in memory as:
Base address + 0 : Byte 1
Base address + 1: Byte 0

2)Big Endian : 'Big Endian means that the high-order byte of the number is stored in memory at the lowest address. The 'short int' above would be stored
Base address + 0 : Byte 0
Base address + 1 : Byte 1

where Byte 0 and Byte 1 are the first and second bytes of the short integer.

You could verify the endianity of your processors by writing a short and sweet C code as follows:

{
unsigned char *p;

short int i=0x1234;

p=&i;

printf("%x\n",*p);

}
The result you obtain would show you the endianity of your processor.

Lets give a thought on what actually happens.

0x1234 is a hexadecimal number and is stored in a variable 'i' of type short int ( occupies 2 bytes of memory space ).

Address of variable 'i' is stored in a pointer of type unsigned char '*p' ( I.e 'p' points to an object of type 'unsigned char').

Dereferencing the pointer p would result in the access of just a single byte . This obviously would be the lower of the two bytes. This shows the fact that accessing a memory location with a pointer is purely dependent on the type of the pointer and not on the type of the actual value stored in the address being accessed. Note that the types of the' pointer to the memory location' and the 'actual value being stored in the location' differ.

You obtain the value that is stored in the lower byte of the two bytes that is allocated for the 'short integer' with the use of a pointer of type 'unsigned char' ( size = 1 byte). The value stored at the lower byte would indicate to you the endianity.

From our sample program,and from what we know about little and big endians , an output of 34 indicates that your processor is 'little endian' and an output of 12 indicates that its big endian.

Just to mention - 'Intel x86' processors are one common example for little endian processors whereas 'Motorola 6800' is big endian.

Crash your python Virtual machine!!!

Causing a python virtual machine to crash is not what I intended but it just happened so. But since this happened , I would just like to give an explanation about what happened and the reason for it.

While trying out memoization , I tried to increase the maximum recursion limit which was set to 1000 in my system.
To change your maximum recursion limit , what you need to do is :
import sys
sys.setrecursionlimit( MY LIMIT )

This would change the maximum number of times that you could recurse your code segment.
Everything worked fine until I did this:
sys.setrecursionlimit(46765)

Now my recursion limit is set to 46765. I tried to run my python code which displayed a segmentation fault that you wouldn't normally associate with your python code. This tells you that your python virtual machine has crashed.
Lets try and find out the reason behind that:

Recursion consumes the stack size in the system . Setting the recursion limit to 46765 means that now the amount of stacksize that will be consumed is much greater .We know the fact the python virtual machine is written in C . As you increase your recursion limit , a point reaches where there is not enough memory for the C back end to execute our python code and this results in a segmentation fault in C that is back propagated to python and displayed in our terminal.

Memoization:Run your programs faster.

Memoization is an optimization technique to speed up programs . Here the function calls are not required to make repetitive calculations of previously calculated results. The processing time of the program is reduced and the memory consumed is increased. Memoized functions become optimized for speed while they use a higher memory .

Lets go through an analysis of memoization: Consider the code segment for finding out the term of a fibonacci series:


def fib(n):

if n==0:

return 0

if n==1:

return 1

else:

n=fib(n-1)+fib(n-2)

return n


You could find out the time taken to run the code :
$ time python filename.py


You would find out then that the time complexity of your program is O(exp(n)) . Try and find out the 40th term of the fibonacci series . This code segment will make you wait for a considerable amount of time before you view your result in the terminal. Trying to find out the 50th term would cause you to manually interrupt the process because you can not wait any longer. Therefore we need a method whereby we could find out the higher terms of the series in much faster time.

Heres exactly where memoization comes in. Memoization is not any kind of magic. What it does is that is caches the results that have been calculated earlier and stores them in a lookup table so that these don't have to be calculated again. We make use of an associative array as a lookup table here. The following code segment shows the memoized version.

table={0:0,1:1}

def fib1(n):

if not n in table:

table[n]=fib1(n-1)+fib1(n-2)

return table[n]


Here we create an associative array with the first two numbers of the fibonacci series as its keys. Now
upon the call of each function , the lookup table ('table') is checked for the existence of the term . If the term is not present in the associative array , the term is calculated and stored in the associative array. In both cases the resulting term is returned. Now see for yourself , the pace of the results being processed.
Try find out the 100th term of the series:
Do
$ time python myfilename.py
You would see the 100th term of the fibonacci series in 12/1000th of a second.Try them for the 1000th,10000th terms...(provided that you have a higher recursion limit). Did you ever think that it could be this faster.???

Intermezzo:Coding style

When writing long codes , its important that , as a programmer , you write your code in the best possible structure that is readable to others. Most languages can be written in different styles, and one may be better than the other. Choosing an appropriate coding style is important so that reading your code is not itching to the eyes.
PEP8 has emerged as the style guide that most codes adhere to. The most important points that needs to be followed are:
1)Use 4-space indentation and no tabs .

2)Use blank lines to separate functions and classes and large blocks of code within functions

3)Use comments when possible

4)Use docstrings in classes and functions.

5)Use spaces around operators and commas e.g ----- 'c = a + b'

6)Naming your classes and functions consistently. Always use 'self' as the name for the first argument a method in the class.

7)Wrap lines so that they don't exceed 79 characters.

Try using all of the above listed particulars and make you code eye-pleasing and obviously easy to understand.

The import search path in Python

As a python programmer, i feel it necessary to mention about the library search path in python. Python looks in several places in your system when we try and import a module in python.
Precisely , it searches in all directories mentioned in sys.path. Just try and see the directories in sys.path.
>>>import sys
>>>sys.path
This returns you a list of the directories where python does a 'look in' to import your module. This list may vary from system to system and depends on the python version that you use.For me, sys.path is :

['', '/usr/lib/python2.5', '/usr/lib/python2.5/plat-linux2', '/usr/lib/python2.5/lib-tk', '/usr/lib/python2.5/lib-dynload', '/usr/local/lib/python2.5/site-packages', '/usr/lib/python2.5/site-packages', '/usr/lib/python2.5/site-packages/Numeric', '/usr/lib/python2.5/site-packages/PIL', '/usr/lib/python2.5/site-packages/gst-0.10', '/var/lib/python-support/python2.5', '/usr/lib/python2.5/site-packages/gtk-2.0', '/var/lib/python-support/python2.5/gtk-2.0']

A few points about sys.path:

Importing the sys module makes all the attributes and functions of the module available to you.

sys.path as i mentioned gives you the current search path.

You could add a new directory to the python path by appending the list 'sys.path'
sys.path.append(/my_directory/my_setup)
Again view sys.path and you will find the directory mentioned above in the new search path.

Functions in Python.

Just like most other languages , Python also has functions in it. Lets go through some of the aspects of functions in python.

def my_function(var1,var):
This is how you declare a function in Python.
The keyword def, the function name ,the arguments separeted by commas in parenthesis. Its important to understand that functions in python specify no return type. Each and every function returns something. Either the value returned or else 'none' , the python 'null value'. The arguments dont specify a type either , the type is made out from the values that are passed in .
Python is a :
dynamically typed language: The types are discovered at run time.
strongly typed language: One particular type cannot converted to another type without explicit type conversion.

Higher order functions in python: Functions that operate on other functions, (functions that can take other functions as its arguments).
Eg: filter(my_function,list_1) is a built in higher order function , which takes the function 'my_function' as one of its arguments.

Functions in python are first class:
Consider :
def my_function2(var1):
We have defined a function 'my_function2'
Now we could do this:
var=my_function.
Now try printing the value of 'var'
Its the address of the function 'my_function2' that will be printed because assigning a function name to a variable assigns it address to the variable.
Now we could invoke the function as:
var(my_parameter)
Just check out the glob module in python (/usr/lib/python2.5/glob.py) for a good example of the first class nature of functions in python.
Function composition is perhaps the best way to explain the fact that function are first class in python.
def f(my_funct):

def g(x):

def compose (f(g(x))): ----- function composition....functions are passed in as variables to other functions.
The way variables are used in function in also important . A good knowledge of the use of local and global variables are required to avoid any kind of misperception while using variables in python.

Local and Global variables in python..

Lets see the working of global and local variables in python with the help of a few small examples: What you need to understand is that variables that are declared inside functions are local to that functions (cannot be accessed from outside the function), whereas variables that are declared outside the function are global to that function , they can be accessed within the function.

>>>a=1
>>>def func():
... print a
... a=10
...
>>>func()
would produce an error as:
UnboundLocalError: local variable 'a' referenced before assignment.
This is because the local variable 'a' is used in the 'print' statement before it is being assigned a value.
However ,

>>>a=1
>>>def func():
... global a
... print a
... a=10
...
>>>func()
wouldn't print an error of that sort.
Note the use of the keyword ' global' . This keyword indicates that the variable 'a' that is being printed is a global variable. The python interpreter understands that there is a variable 'a' that has been assigned to '1' outside the function and hence prints the value '1'.

Now do the following:

>>>a=1
>>>def func():
... global a
... print a
... a=10
... print a
>>>func()
The result would be:
1
10
Now try and print the value of 'a'.
The value printed would be:
'10'
This is because the value of the variable 'a' has been changed to 10 by the function
'func' because 'a' has been declared as a global variable in the function 'func'.

Now do :
>>>def func():
... print b
... b=10
...
>>>print b
would result in an error :
NameError: name 'b' is not defined

because no variable 'b' has been assigned a value outside the function. The variable 'b' used in the function 'func' is local to that function and cannot be accessed from that outside the function, that is , the variable 'b' is local to the function.

Version control Systems...

Version control is a system that records changes to your files and allows to view specific versions of a file or set of files.VCS is used so that you don't screw up your files or your entire project as a result of the silly , careless mistakes that you have made.
Many people do their own version control by copying their files to another directory.This is a quite simple and easy approach if you are careful enough so that you won't agonize by doing something disastrous so that you may lose all your stuff later.Therefore keeping in mind that such things can happen ,after all we are all humans, we use version control systems.

Centralized VCS and Distributed VCS.
Centralized VCS
CVCS includes a single server that contains different versions of the files and the clients could check into that.The major advantage of this system is that administrators have fine grained control over whats happening ,but it has serious drawbacks as well. They are:
Single point of storage if crash would be fatal.
The clients could pull anything from the repository but they need a commit access to push something into it.This might lead to a client getting frustrated if he/she has not been granted a 'commit access' even after working for a longer period of time. Also there might something political issues related to administration.

Distributed VCS.
In DVCS ,you could push data into the repository with the same ease with which you could pull from it. All the repositories are at the same level and therefore we could collaborate with any of the repositories.Examples of DVCS are Git , mercurial , bazaar..etc...

Shebang lines...

Shebang(also known as 'hashbang') refers to the characters #! when they are the first two characters (occurring at the left most corner, i.e the beginning of the very first line) of your script. The particular line that contains the shebang is the shebang line in your script.
Now what's shebang meant to do.?
In a unix-like operating system , the program loader (part of the operating system thats responsible for loading programs) finds the presence of these two characters(#!) , identifies it as a script and tries to execute it with the interpreter that will be specified using the remaining lines of the script.
For example consider writing a shebang line for a python script..
First and foremost you need to find the location of the interpreter for that particular script...
$which python
/usr/bin/python
Therefore...the shebang line should be set as...
#! /usr/bin/python
Specifying the shebang line would execute your script as follows:
./'script name'.py instead of doing 'python 'script name'.py'
You could try out the use of shebang lines for any of the following types of scripts
'werbel', 'tinypy' ,'perl'.....and many more...

Optimizing your Python code.

Compare python with some of the other languages that are familiar to many of you. The obvious difference that will be caught by you , is the fact that python code, for the same program ,is much shorter than codes written in some of your favorite languages like C ,Java etc.
Understanding the essence of python programming would help you write shorter and interesting codes and are easier to understand. Lets just have a look into some of the core points that need to be followed so that your python program becomes short and effective.

First and foremost, you need to understand the fact that python has got a huge library with functions for almost every activity you would need frequently. The only thing you need to do is to identify whether a function is present that would handle your case and then call the function .There are lots of built in functions that we could call. Other functions that reside in certain modules can also be invoked after the module containing the function has been imported.
As an example , consider the following:
map(sqr,range(1,100)):

'map' is a built -in higher order function that takes two or more arguments and returns you a list,'range' is another built-in which would return a list containing all the elements from the starting element up to the ending element.

This particular function returns a list of squares of all numbers from 1 up to 99 using a single line code. Compare this to a C code to find the squares of this many numbers,certainly ,a single line code wouldn't do that for you.

Python has got a large collection of such built ins which includes functions like 'filter','reduce','hex','cmp' and many more.

Python has got many more functions that are defined in different modules:To use those functions , you just need to import those modules and invoke them. Some of the most commonly invoked ones are :
Module 're' for pattern matching. Contains power full functions like findall' , search' , 'match' etc.
Module 'os' for operating system services. Includes functions 'mkdir' , 'chdir' ,' path.join,' path.abspath'' etc.
Module 'shutil' for shell utilities like copying files.

Module 'urllib' for dealing with 'URLs'.

Module 'sys' :sys.argv[index] would return the input given on the command line at position 'index.'

Identifying the correct functions that are present in these and more modules in python would result in much shorter code length.

A proper knowledge about the use of sequences and variables would do no harm in our purpose of decreasing the code size.

Consider the code to swap the values of two variables. In other languages you would write:
temp=a:
a=b:
b=temp:

Once again, in python all you need is a single line code :

a,b=b,a

The logic behind whats happening is to be understood. Consider the right hand side of the expression -variables are packed into a tuple. On the left hand side, the tuple is unpacked and the values are entered into the variables. Thus the values are swapped in a single line as opposed to three lines taken in other languages.

Use of generator expressions is another way to reduce your code size.
Consider:
xvec=[10,20,30]
yvec=[30,40,50]

The expression sum(x*y for x,y in zip(xvec,yvec)) gives you the dot product of xvec and yvec in a single step where 'sum' is another built in function. Think of writing a C code instead of this and the number of writing you would take.


There are many more such tricks that would decrease the code size considerably . Slicing of lists , usage of the appropriate sequences are all important in producing a short and elegant code. Obviously,the fact remains that to understand the methodology behind decreasing the code size is to keep on coding ,understanding the definitions of the functions and identifying where to use them. But again, compressing your code size heavily might result in your code being hard to digest by others, specially those beginners trying to understand a python code. Therefore its important to develop a skill where you would maintain a balance between decreasing the code size and the readability of your code. This can be achieved only through rigorous coding.

Garbage collection in Python.

In C, once the memory allocated becomes garbage , that chunk of memory is gone wasted. Nothing more is possible on it.
Consider
int a[10];
Some amount of memory would be allocated for the array 'a'. Now if do a='some value' , the memory that was allocated to the array becomes garbage because 'a' no longer uses it as it is pointing to something else now. The memory is gone wasted and is no more usable.
The bugs that create loss of memory are hard to detect as well ,simply because of the fact that they cannot be seen. Its only after executing the particular code for some amount of times that you might actually get to see the effects of the bug .By the time your system may have crashed.

In python ,the interpreter is smart enough to do 'garbage collection'. That is the memory which is unused is collected by the interpreter and is not gone wasted. The process of garbage collection is done by using a method called ref counting. Understand ref counting as :
Consider a=[1,2,3]
'a' points to a particular block of memory. At the end of the block of memory ,there would be a count that indicates the number of variables that point to the same block of memory. So now the count would be 1.

Now if we do,

b=a......means that now b points to same block of memory. Therefore the count becomes 2.

Now consider doing

b=0.

The count in the block of memory where b was pointing earlier reduces by 1. , hence count is now 1.
Do

'a=0'

and the count in that block becomes 0.Now the python interpreter can allot the chunk of memory to some other variable as it may feel. The significant thing that you need to understand is the fact that the memory is not gone wasted as in C .

Garbage collection keeps track of the variables that point to a block of memory and collects the unused memory accordingly. There is never a shortage of memory space. But there are obvious disadvantages with the process of garbage collection.

One drawback , as you would except would be the matter of speed which would decrease.
But the more significant drawback would be the non-deterministic behavior of the interpreter.
Consider the two statements.
.i=0
.j=0
You would expect the statement j=0 to be executed immediately after the statement i=0 has been executed. But as a result of this process of garbage collection ,this is not a guarantee. There might be a certain time delay in executing the second statement if the interpreter feels like doing some 'garbage collection' after the first statement has been executed . This results in the delay.

Therefore its clear that its not best to use python over languages like C when it comes to real time systems.