Archive for October, 2010

The Metacircular Evaluator

              While reading one of the classical texts in the field of   computer science,  
‘Structure and Interpretation of Computer Programs’  (also known as the ‘Wizard’ book), I went through the concept of  ‘Metacircular Evaluator ‘ in the fourth chapter of the book ,where a ‘language interpreter’ for lisp is implemented and language used for
 this purpose is lisp itself.That sounded a bit confusing to me at first ….. but as i went through the structure of the program, it really amazed me as here in program the syntactic simplicity of the language ‘lisp ‘ was exploited to its best. As each and every expression in the language lisp was written as an S-expression (in prefix format, where the operation was written at first in the rest of the list),  the expression recognition was made simpler .   
                            The program in the book is the lisp formulation of environmental model of evaluation. There are two main things done here
  •               A complex procedure is evaluated by splitting it up into simpler subexpression which can be evaluated and the value is applied to the operand subexpression.

  •              2) A compound or user defined procedure is evalauted in a new environment, which can be created by extending the current environment by adding a frame.   
                      The environment here means that the variables are bound to a specific environment which helps to diffrentiate the local variables from global one’s. This is a great way to simulate the evaluation environment where a variable is assigned a value in a specific environment . Here the environment is implemented using  list data structure .

The Core of the Evaluator
                     The two main procedures in the evaluation processs are ‘eval‘ and ‘apply’

  •                ‘eval’  procedure is responsible for  evaluating an expression in it’s environment. This procedure takes the expression and the environment as input parameters. It is this function where the determination of type of expression is done and the corresponding action is invoked.
  •                 ‘apply’ procedure takes the operation and the parameters as the input and it applies the operation to it. This procedure diffrentiates between a primitive procedure to apply the primitives and a compound procedure , the body of whose is evaluated sequentially.

Leave a comment

Memory inspection using ‘Valgrind’

            Valgrind is a a programming tool suite used for debugging, profiling and detection of memory leaks which are quiet common in C,C++ programs. Detecting memory leaks is done by ‘memcheck’ tool  ,which by other means is a very difficult task to do .

To detect a memory leak using ‘Valgrind’ ,let us take an example code which does memory leak .For Example

Here in the example
   1)  in function ‘f‘  a char * variable ‘k’ is declared and  memory block of 100 bytes are allocated  to it from the heap. That means , the variable ‘k’  resides  on stack and it contains the  address of a memory block which is there in heap .
   2) the function ‘f’ tries to write in a memory block which has not been allocated to it .That is 
when we write
                                                 k[105] = 10 ;
 we are trying to access the memory byte which lies at an offset of 105 from the ‘k‘ . This memory byte was not allocated to ‘k‘ , hence can lead to serious untrackable bug and mysterious behaviour of the program . When the code is compiled using ‘gcc’ not even a single warning is given , forcing the programmer to believe that the function behaves normally.
                         Apart from this the when the function ‘f’ returns  to the ‘main’ function , the stack frame where the local variables of function ‘f’   (for example ‘k’) gets deallocated, so in this case the value in ‘k‘  ( the address of the 100 byte block) gets lost and thus memory leak occur. For this again, compiler can’t generate error or warning messages.

     So for coping with these kind of problems ,valgrind can be used.  

Using Valgrind  for detecting memory  leaks

    For using Valgrind the program has to be compiled with  ‘-g’  option  

as shown

                    gcc  – g   ‘program_name’.c

then the ‘Valgrind’ program can be used to  generate usefull information 

                    valgrind   –leak-check=yes   ./a.out

For example for the above piece of code it will generate meassages as

Here  in above messages,

   1)  In   ==5124==  , 5124 is the process id .  It is not that important
   2)  Display a stack trace showing where the problem occured. It can be usefull in large complex code.
   3)  Error messages show memory addresses involved as the second component.

Memory leaks  can be analysed by analysing the error messages


            This Dynamic analysis tool is usefull in detecting memory bugs and memory leakage.

Leave a comment

back after a Loong Break

Hiii  Guys!!!  I m back to the blogging world . .  after a long break .
                             Last month I brought a new Dell  n series laptop and installed Ubuntu Lucid Lynx 10.04 on it . To tell about my experience with it (Lucid Lynx) so far.  .  . hmm. . .  . nothing but.. ‘GREAT’. I found it easy to use and for the first time in  my experience with linux systems I found a fully featured and a complete no-hassle desktop .With boot time improved noticeably from the previous versions of the same….. Lucid Lynx seems to give other linux distros a tough competetion .
            This time this blog promises of bringing more geeky technical stuff …hope that everyone finds it interesting .

Leave a comment