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().
Saturday, 25 September 2010
Thursday, 23 September 2010
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:
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.
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_:
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':
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:
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.
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.
Wednesday, 22 September 2010
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:
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.
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.
Tuesday, 14 September 2010
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.
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.???
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.???
Sunday, 5 September 2010
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.
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.
Subscribe to:
Posts (Atom)