Archive for category SICP

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.

Advertisements

Leave a comment

Scheme to Python Compiler for Android OS

                 My B.tech major project was to implement a ‘Scheme-to-Python Compiler for Android’ where the language used was Scheme (a variant of lisp ).The project aimed at developing a compiler which would translate application program written in Scheme to Python which in turn can be run on Android platform.  Here I used the concept of ‘Meta-circular Evaluator’  from SICP (Structure and Interpretation of Computer Program )  the ‘wizard book’,  to recognize each expression and then ,instead of evaluating it, my program generated the corresponding the Python expression.
                   The Python program generated was stored in the SDcard of Android SDK.
Now for Python programs to be supported on Android platform, SL4A was to be installed on Android SDK . This platform enabled python generated program to be run on the SDK providing many of the API’s provided to a full-fledged Android applications . I demonstrated my project by using a “text-to-speech” API available to Python which would process the text message to generate the corresponding speech.

     The Graphical User Interface for the compiler was designed with GTK(Gnome Tool KIt) programming tool named ‘Glade’ 

As seen above,there are two text columns.  The scheme code to be compiled is to be written in the first column.  There are four buttons to this interface. 
  1. The first button when pressed invokes the ‘DrScheme’ with the Scheme code in it.The code in scheme can be checked for correctness and run with it.
  2. The second button when pressed invokes the ‘Compiler code‘,proceeses the input scheme program and generates the correspoding python program.
  3. The third button when pressed invokes ‘IDLE’ ( a python IDE) for validating the generated python code.
  4. The fourth button with an icon of ‘Android’ copies the generated python code into the SDCard s(memory card) and starts the Android SDK. 

The source code for the above project can be downloaded from my git hub => git@github.com:rohitnjan88/S-T-A.git

  The application in Android SDK can be invoked by clicking on the SL4A  icon in the menu.  

Leave a comment