Implementation of Scheme Evaluator in Python
The idea of the project came from reading the book Structure and Interpretation of Computer Programs (SICP). The book contains the code of Metacircular Evaluator of Scheme. Metacircular Evaluator is the evaluator written in the same language that it evaluates. Thus Metacircular Evaluator of Scheme is implemented in the language Scheme. I’m trying to implement the same code in Python.
In Scheme the idea of implementing the evaluator prominently contain two methods: eval and apply.
- Eval: To evaluate a combination, evaluate the subexpressions and then apply the value of operator subexpressions to the operand subexpressions.
- Apply: To apply a compound procedure to a set of arguments, evaluate the body of the procedure in a new environment.
An environment is a set of variable bindings. Anew environment can be created by extending an existing environment with a set of new bindings.
Implementation of Scheme Evaluator in Python
In the implementation of the evaluator I’ve slightly deviated from the original implementation described in the SICP. It’s only a minimal form of the original evaluator. Most of the basic operations performed in Scheme can be evaluated using this implementation.
This implementation, prominently depend on two methods: calculate and turningpoint. calculate is doing functions similar to original apply andturningpoint is similar to eval. The similarity is only to a small extend.
The implementation is built on three modules: interpreter, readexp and listops. In a jist, interpreter executes the methods calculate and turningpoint,readexp takes the user input and convert it to a Python list and listops performs some basic list operations like first().
The readexp Module
The main function of this method is to take input from the user in the Scheme format and convert it to list and return it to the the interpreter module. In the main method of the the module interpretor the call to this module occurs. Its an infinite loop running in the main which terminates only when the end of file is reached or when the process is killed. This module does the job of printing the prompt “$$$:’ for the user.
When the call to this module occur, the call is coming to the getExp method. The getExp method converts the user input to a Python list and send it back to the interpreter module. The getExp method calls the getToken method which return each elements in the input seperated by space. In getToken method, the nextChar and getChar methods are called which respectively return a single character from user input and a single character from the globally stored value. The nextChar method works according to the content of the global value char. If the content of char is empty, the prompt to take user input is initiated, else a single character from char is returned. In getChar method the value from nextChar is taken and stored in char. It returns a character from char and deletes the character from char too.
Thus the readexp module returns a Python list form of user input.
The interpreter Module
This module contains two methods: turningpoint and calculate. After receiving the user input as a Python list from readexp module, the list, here with name elements, is give to the method turningpoint.
The turningpoint itself is decomposed into three methods which are selected according to simple if-else condition. turningpoint checks whether the comming expression is a condition or a value assigignment or a procedure or simply an expression, and take needed steps accordingly.
If the expression is a condition, turningpoint will call the method condition. In condition, the first check is for multiple conditions. If an and statement is present, single condition is taken and is passed to the calculate method. If the answer returning is ‘true’, the rest of the conditions are given one by one similarly. Once any of the returning value is ‘false’ the rest of conditions remain unchecked and ‘else’ expression of the condition is passed to thecalculate method, and necessary evaluation are done and the answer is returned. Else the condition expression is passed to calculate and according to the returning value the ‘then’ or ‘else’ part is passed to the calculate module.
If the expression is a simple assignment, the variable is added to a global dictionary, which act as the environment, as a key and the value to the key is obtained after passing the third subexpression of the list to the calculate method.
If the expression is a procedure, the procedure body along with the parameters is added to the dictionary as a list with key, the name of the procedure. When the call to the function occurs the interpreter first check whether the name is present in the environment. If the procedure name is present, the value of the item is retrieved to a local varaiable. The local variable is then calculated. If the first element is ‘lamda’, then the paremeter list is given value according to the user input. Then the parameters are stored to the environment. After that, the third element, that’s an expression (procedure body), is passed to calculate method. In case of recurssion, when the procedure call again occurs the procedure is passed to turningpoint. I’ve only designed this project to work for tail recursion
If the expression is a mathematical operation, the expression is simply passed to the calculate method.
This method computes all the calculations needed. In this method, if the argument coming is simply an element, it returns the integer if its an integer or it returns a string if the coming element is a string. If the coming argument is a list type element, the first element is taken as the operator using the methodfirst(). It is stored as the operator and again calculate method is called to obtain the rest of the values in the list. After obtaining the complete list elements ther operator is applied on each of the operand.
The working can be explained using the following example:
If the user inputs the scheme command ‘(+ 4 5)’, the control flow is shown below:
The listops Module
I used a single feature from listops module. The first() method is used to get the first element of a list. It is used in the calculate method ofinterpretermodule.
The code of the project is avalilabe in the link, http://github.com/odolshinu/scheme_interpreter. The code can run all the basic operation done in Scheme in a prompt provided in Python and is evaluated using the evaluator implemented in Python.