The Scheme Interpreter project is the most daunting and if you’re me, by far the longest assignment (14 hours) in CS 111. In the project, you program bits and pieces of an interpreter for scheme in python. The project details and files can be found on the CS 111 website. Before beginning the project, I recommend reading the following chapters from Composing Programs: 3.2: Functional Programming, 3.4: Interpreters for Languages with Combination, and 3.5: Interpreters for Languages with Abstraction. Berkeley’s CS61a Youtube channel also has videos with helpful hints for specific questions from the scheme project.
The project is divided into four parts: The Evaluator, Procedures, Special Forms, and Write Some Scheme. I will not be going over the last part, because I do not really like writing code in scheme.
Problem 1: Define and Lookup
The frame is the current environment of a program in which variables are defined. Calling a function creates a new child frame with its own variables and values. In this problem we will be creating the functions in python that will allow us to make variables and bind values to them.
Our scheme interpreter (all of the python files) has a class, Frame, which will be where we make frames and control what variables and values are stored in them.
When we initialize a frame object (__init__(self, parent)), it creates two instance variables: parent and bindings. Parent lets us know from which frame the newly initialized frame is being made. The first frame is the global frame so its parent is None. This is taken care of by the function create_global_frame() in scheme.py so don’t worry about it.
bindings is a python dictionary that represents variables in scheme and their associated values.
Scheme
(define a 3)
To Python
self.bindings = {‘a’: 3}
When we initialize a frame object, Bindings is an empty dictionary. To populate it, we need to implement the method define(self, symbol, value). The argument symbol is simply the variable name and value is the value to which symbol is being bound.
Scheme
(define a 3)
symbol = ‘a’
To Python
define(‘a’, 3)
value = 3
To populate the dictionary, you could use the update({a: b}) method of python dictionaries.
Now we need to implement the method lookup(self, symbol) which searches the frame object in bindings to see if the variable (symbol) is in there. If it is, it will return the value that the variable is bound to. If it is not in there, then it does the same search process but in the parent frame. Once we are to the global frame, meaning env.parent = None, if the variable is not found, the interpreter raises an error.
You can get the value of a dictionary key using the built-in .get(key_name) method. You can use python’s in to see if a key is in a dictionary.
Problem 2: Procedures
This time we are going to be implementing a function in scheme_eval_apply.py called scheme_apply(). This function takes in a scheme list (args) and then applies the correct procedure (like addition or a lambda function) to args. The function returns a call to the correct procedure on args. Procedures are handled by the Procedure class in schemeclasses.py.
In Problem 2, we will be handling Built-in Procedures. Everytime a BuiltinProcedure is initialized, it creates three instance variables: name, py_func, and expect_env.
py_func is a function in python that will handle the operation/procedure needing to be done in Scheme
expect_env is a boolean (True or False) telling us if the built-in procedure needs the current environment information to run
In scheme_apply(), args is a scheme list, meaning it is represented by the Pair class which is basically just a linked list.
Scheme
(2 2)
In Python
args = Pair(2, Pair(2, nil))
The CS 111 site gives pretty much step-by-step instructions on implementing this function properly.
Hint: Scheme List to Python List
To convert the scheme list to a python list of arguments you could write a function that makes an empty list and then has a helper function inside recursively go through the linked-list (args) and append the first value to the python list. The needed values in Pair are accessed with .first and the rest of the list is gotten with .rest.
Hint: Try Except Syntax
Problem 3: scheme_eval()
In problem 3 we are going to evaluate the operator, then the operands (the arguments to the operator), and then apply the operator to all of the operands. This will be done in the function scheme_eval(expr). expr is a scheme expression represented by a Pair object.
From Scheme
(+ 2 2)
The operator is (+) addition
To Python
expr = Pair(‘+’, Pair(2, Pair(2, nil)))
The operands are 2 and 2
The scheme_eval() function takes in expr. Your job is to get the operator in expr and recursively evaluate it using scheme_eval(). Then recursively evaluate all of the operands (the rest of expr after the operator) using scheme_eval(). Scheme_eval() is pre-programmed to be able to handle the operators and individual operands.
The evaluation of the operator, will be a procedure. The final step is to apply the procedure on the operands using scheme_apply() from the last problem and return the result of that.
Hint: Evaluating the Operands Using map()
The Pair class has a method called map(). map(func) takes a function in and makes a new scheme list by applying func to all of the elements.
The challenge is that map() only takes in one argument, but we want to evaluate all of the operands using scheme_eval(), which takes two arguments: expr and env. So we need to make an equivalent version of scheme_eval() that takes only 1 argument. Hint: Lambda
Problem 4: Define Special Form
In Problem 4, we will be tackling the do_define_form() function. This function takes two arguments: expr and env. expr is a scheme expression represented by Pair class objects.
Scheme
(define size 2)
To Python
expr = Pair(‘size’, Pair(2, nil))
The first part of expr, ‘size‘, is the variable name. Whatever else that comes after is the expression or value to which the variable name will be bound. If it is an operation being defined, then the second part of expr, will start with an operator (like +).
Scheme
(define x (+ 2 3))
To Python
expr = Pair(‘x’, Pair(Pair(‘+’, Pair(2, Pair(3, nil))), nil))
The variable pre-defined for us, signature = expressions.first, is just the name of the variable in scheme that we want to bind to a value. (In the above example, ‘x’) Your job is to write the code that takes the rest of the Scheme list (the Pair objects) and evaluates it to a value in Python. Then assign that value to signature in the current environment. Finally remember to return signature.
Hint: Environment Class Method define()
We created the method for variable creation in problem 1
Problem 5: quote
In problem 5 we are going to handle the quote feature of scheme. If we call quote on an operand in scheme, then the operand will be returned, unevaluated.
All you need to do is just return the unevaluated operand. All it takes is a very short line of code. Personally, I spent about half an hour on this before I realized it, but I was also tired.
If expressions = Pair(3, nil)
Then return 3
</end>
Hopefully this was a sufficient help. Please submit any corrections or questions in the comments below. I will try my best to answer and update the article accordingly.
