Guide to the Scheme Interpreter Project (BYU CS 111) Part 1

part 2

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.

The Frame class in

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 so don’t worry about it.

bindings is a python dictionary that represents variables in scheme and their associated values.

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.


(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.

Interpreter raises an error if variable is not found (

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.

For more help

Problem 2: Procedures

This time we are going to be implementing a function in 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

The Procedure class in

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.

The CS 111 site gives pretty much step-by-step instructions on implementing this function properly.

Hint: Scheme List to Python List

Hint: Try Except Syntax

For more help

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()

For more help

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.


(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 +).

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()

For more help

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.

From the CS 111 Website Problem 5 Description

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

For more help


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.

on to part 2


Leave a Reply

Your email address will not be published. Required fields are marked *