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.