Due at 11:59pm on Friday, 11/04/2016.

Starter Files

Download lab10.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.


By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

  • Questions 1, 2, and 3 must be completed in order to receive credit for this lab.
  • Questions 4 and 5 are optional. It is recommended that you complete these problems on your own time.


Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.


An interpreter is a program that allows you to interact with the computer in a certain language. It understands the expressions that you type in through that language, and perform the corresponding actions in some way, usually using an underlying language.

In lecture, you saw an interpreter for the Calculator language, implemented in Python. In Project 4, you will use Python to implement an interpreter for Scheme. The Python interpreter that you've been using all semester is written (mostly) in the C programming language. The computer itself uses hardware to interpret machine code (a series of ones and zeros that represent basic operations like adding numbers, loading information from memory, etc).

When you talk about an interpreter, there are two languages at work:

  1. The language being interpreted/implemented. In this lab, you will implement the PyCombinator language.
  2. The underlying implementation language. In this lab, you will use Python to implement the PyCombinator language.

Note that the underlying language need not be different from the implemented language. In fact, in this lab we are going to implement a smaller version of Python (PyCombinator) using Python! This idea is called Metacircular Evaluation.

Many interpreters use a Read-Eval-Print Loop (REPL), which you can find in repl.py. This loop waits for user input, and then processes it in three steps:

  • Read: The interpreter takes the user input (a string) and passes it through a lexer and parser.

    • The lexer turns the user input string into atomic pieces (tokens) that are like "words" of the implemented language.
    • The parser takes the tokens and organizes them into data structures that the underlying language can understand.
  • Eval: Mutual recursion between eval and apply evaluate the expression to obtain a value.

    • Eval takes an expression and evaluates it according to the rules of the language. Evaluating a call expression involves calling apply to apply an evaluated operator to its evaluated operands.
    • Apply takes an evaluated operator, i.e., a function, and applies it to the call expression's arguments. Apply may call eval to do more work in the body of the function, so eval and apply are mutually recursive.
  • Print: Display the result of evaluating the user input.

Here's how all the pieces fit together:

         |                                                 |
         |  +-------+   +--------+   +-------+   +-------+ |
Input ---+->| Lexer |-->| Parser |-->| Eval  |-->| Print |-+--> Output
         |  +-------+   +--------+   +-------+   +-------+ |
         |                              ^  |               |
         |                              |  v               |
         ^                           +-------+             v
         |                           | Apply |             |
         |    REPL                   +-------+             |

PyCombinator Interpreter

Today we will build PyCombinator, our own basic Python interpreter. By the end of this lab, you will be able to use a bunch of primitives such as add, mul, and sub (you can see the entire list at the bottom of expr.py), and even more excitingly, we will be able to create and call lambda functions -- all through your own homemade interpreter!

You will implement some of the key parts that will allow us to evaluate the following commands and more:

> add(3, 4)
> mul(4, 5)
> sub(2, 3)
> (lambda: 4)()
> (lambda x, y: add(y, x))(3, 5)
> (lambda x: lambda y: mul(x, y))(3)(4)
> (lambda f: f(0))(lambda x: pow(2, x))

Here is an overview of each of the REPL components in our interpreter.

  • Read: The function read in reader.py calls the following two functions to parse user input.

    • The lexer is the function tokenize in reader.py which splits the user input string into tokens.
    • The parser is the function read_expr in reader.py which parses the tokens and turns expressions into instances of subclasses of the class Expr in expr.py, e.g. CallExpr.
  • Eval: Expressions (represented as Expr objects) are evaluated to obtain values (represented as Value objects, also in expr.py).

    • Eval: Each type of expression has its own eval method which is called to evaluate it.
    • Apply: Call expressions are evaluated by calling the operator's apply method on the arguments. For lambda procedures, apply calls eval to evaluate the body of the function.
  • Print: The __str__ representation of the obtained value is printed.

In this lab, you will only be implementing the Eval and Apply steps in expr.py.

If you want a better idea of how user input is read, you can use the following command to try out some expressions:

$ python3 repl.py --read
> lambda x: mul(x, x)
LambdaExpr(['x'], CallExpr(Name('mul'), [Name('x'), Name('x')]))
> lambda f: f(0)
LambdaExpr(['f'], CallExpr(Name('f'), [Literal(0)]))

To exit the interpreter, type Ctrl-C or Ctrl-D.

Required Questions

Question 1: Prologue

Remember, expr.py contains our interpreter's representation of expressions and values. Read through the provided code and docstrings in this file.

Use OK to test your knowledge with the following questions:

python3 ok -q prologue -u

You can open your interpreter using the command:

$ python3 repl.py

If you try to type in some commands, you will see that we don't really get any interesting output. Let's fix that now!

Question 2: Evaluating Names

The first type of expression that we want to evaluate are Names. As we know from our environment diagrams, it is important which environment (sequence of frames) we are in when we evaluate a name. Therefore, Name.eval takes an environment as an argument. In our implementation, an environment is represented by a dictionary that maps variable names (strings) to their values (instances of the Value class).

Each instance of the Name class has a string instance attribute which is the name of the variable -- e.g. "x". We want Name.eval to return the right value bound to this name if it exists in the current environment.

If the name does not exist in the current environment, we want to elegantly handle this by outputting an error message similar to the ones you've seen in regular Python. As you've seen in lecture, we can raise errors. In Name.eval, raise a NameError with an appropriate error message if the name you are evaluating does not exist in env:

raise NameError('your error message here (a string)')
def eval(self, env):
    >>> env = {
    ...     'a': Number(1),
    ...     'b': LambdaFunction([], Literal(0), {})
    ... }
    >>> Name('a').eval(env)
    >>> Name('b').eval(env)
    LambdaFunction([], Literal(0), {})
    >>> try:
    ...     print(Name('c').eval(env))
    ... except NameError:
    ...     print('Exception raised!')
    Exception raised!
"*** YOUR CODE HERE ***"
if self.string not in env: raise NameError("name '{}' is not defined".format(self.string)) return env[self.string]

Use OK to test your code:

python3 ok -q Name.eval

Question 3: Evaluating Call Expressions

Now, let's implement CallExpr.eval. Remember that a call expression consists of an operator and 0 or more operands. Notice that each instance of the CallExpr class has a self.operator and a self.operands instance attribute. self.operator is an Expr, and, since there might be multiple operands -- e.g. lambda x, y: add(x,y) -- self.operands is a list of Exprs.

For example, for add(3, 4):

  • self.operator would be Name('add') since this is the operator we want to apply to the operands.
  • self.operands would be [Literal(3), Literal(4)]

There are three steps to evaluating call expressions:

  1. Evaluate the operator in the current environment.
  2. Evaluate the operand(s) in the current environment.
  3. Apply the value of the operator, a function, to the value(s) of the operand(s). You can apply a function by calling its apply method.
def eval(self, env):
    >>> from reader import read
    >>> new_env = global_env.copy()
    >>> new_env.update({'a': Number(1), 'b': Number(2)})
    >>> add = CallExpr(Name('add'), [Literal(3), Name('a')])
    >>> add.eval(new_env)
    >>> new_env['a'] = Number(5)
    >>> add.eval(new_env)
    >>> read('max(b, a, 4, -1)').eval(new_env)
    >>> read('add(mul(3, 4), b)').eval(new_env)
"*** YOUR CODE HERE ***"
function = self.operator.eval(env) arguments = [operand.eval(env) for operand in self.operands] return function.apply(arguments)

Use OK to test your code:

python3 ok -q CallExpr.eval

Now that you have implemented the evaluation of call expressions, we can use our interpreter for simple like sub(3, 4) and add(mul(4, 5), 4). You can see a full list of primitive math operators at the bottom of expr.py in the global_env dictionary. Open your interpreter to do some cool math:

$ python3 repl.py

Optional Questions

Question 4: Applying Lambda Functions

We can do some basic math now, but it would be a bit more fun if we could also define our own functions. So let's make sure that we can do that!

A lambda function is represented as an instance of the LambdaFunction class. If you look in LambdaFunction.__init__, you will see that each lambda function has three instance attributes: parameters, body and parent. As an example, consider the lambda function lambda f, x: f(x). For the corresponding LambdaFunction instance, we would have the following attributes:

  • parameters -- a list of strings, e.g. ['f', 'x']
  • body -- an Expr, e.g. CallExpr(Name('f'), [Name('x')])
  • parent -- the parent environment in which we want to look up our variables. Notice that this is the environment the lambda function was defined in. LambdaFunctions are created in the LambdaExpr.eval method, and the current environment then becomes this LambdaFunction's parent environment.

You are now going to implement the LambdaFunction.apply method. This function takes a list arguments which is -- not surprisingly -- a list of the argument Values that are passed to the function. When evaluating the lambda function, you will want to make sure that the lambda function's formal parameters are correctly bound to the arguments it is passed. To do this, you will have to modify the environment you evaluate the function body in.

There are three steps to applying a LambdaFunction:

  1. Make a copy of the parent environment. You can make a copy of a dictionary d with d.copy().
  2. Update the copy with the parameters of the LambdaFunction and the arguments passed into the method.
  3. Evaluate the body using the newly created environment.
def apply(self, arguments):
    >>> from reader import read
    >>> add_lambda = read('lambda x, y: add(x, y)').eval(global_env)
    >>> add_lambda.apply([Number(1), Number(2)])
    >>> add_lambda.apply([Number(3), Number(4)])
    >>> sub_lambda = read('lambda add: sub(10, add)').eval(global_env)
    >>> sub_lambda.apply([Number(8)])
    >>> add_lambda.apply([Number(8), Number(10)]) # Make sure you made a copy of env
    >>> read('(lambda x: lambda y: add(x, y))(3)(4)').eval(global_env)
    >>> read('(lambda x: x(x))(lambda y: 4)').eval(global_env)
    if len(self.parameters) != len(arguments):
        raise TypeError("Cannot match parameters {} to arguments {}".format(
            comma_separated(self.parameters), comma_separated(arguments)))
"*** YOUR CODE HERE ***"
env = self.parent.copy() for parameter, argument in zip(self.parameters, arguments): env[parameter] = argument return self.body.eval(env)

Use OK to test your code:

python3 ok -q LambdaFunction.apply

You should try out your new feature! Open your interpreter using

$ python3 repl.py

and create your own lambda functions.

Question 5: Handling Exceptions

The interpreter we have so far is pretty cool. It seems to be working, right? Actually, there is one case we haven't covered. Can you think of a very simple calculation that is undefined (maybe involving division)? Try to see what happens if you try to compute it using your interpreter. It's pretty ugly, right? We get a long error message and exit our interpreter -- but really, we want to handle this elegantly.

Try opening up the interpreter again and see what happens if you do something ill defined like add(3, x). We just get a nice error message saying that x is not defined, and we can then continue using our interpreter. This is because our code handles the NameError exception, preventing it from crashing our program. Let's talk about how to handle exceptions:

In lecture, you learned how to raise exceptions. But it's also important to catch exceptions when necessary. Instead of letting the exception propagate back to the user and crash the program, we can catch it using a try/except block and allow the program to continue.

    <try suite>
except <ExceptionType 0> as e:
    <except suite 0>
except <ExceptionType 1> as e:
    <except suite 1>

We put the code that might raise an exception in the <try suite>. If an exception is raised, then the program will look at what type of exception was raised and look for a corresponding <except suite>. You can have as many except suites as you want.

    1 + 'hello'
except NameError as e:
    print('hi')  # NameError except suite
except TypeError as e:
    print('bye') # TypeError except suite

In the example above, adding 1 and 'hello' will raise a TypeError. Python will look for an except suite that handles TypeErrors -- the second except suite. Generally, we want to specify exactly which exceptions we want to handle, such as OverflowError or ZeroDivisionError (or both!), rather than handling all exceptions.

Notice that we can define the exception as e. This assigns the exception object to the variable e. This can be helpful when we want to use information about the exception that was raised.

>>> try:
...     x = int("cs61a rocks!")
... except ValueError as e:
...     print('Oops! That was no valid number.')
...     print('Error message:', e)

You can see how we handle exceptions in your interpreter in repl.py. This might also be a really good place to handle the exception you triggered with your ill-defined arithmetic. Go ahead and try it out!