Due at 11:59pm on 11/05/2015.

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.

Submission

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.

• To receive credit for this lab, you must complete the prologue and Questions 1, 2, and 3 in expr.py and submit through OK.

Introduction

Today we will build PyCombinator, our own basic Python interpreter. By the end of this lab, you will be able 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!

Interpreters

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.

    In your interpreter, the function tokenize in reader.py takes care of this step.

  • The parser takes the tokens and organizes them into data structures that the underlying language can understand.

    In your interpreter, the functions read and read_expr in reader.py take care of this step. The data structures that we use are classes in expr.py (e.g. CallExpr). (In Project 4, we will use deep linked lists, linked lists whose elements can also be linked lists, to represent hierarchy and recursion.)

• Eval: Mutual recursion between eval and apply evaluate the expression to a value.

  • Eval takes in an expression (represented with the aforementioned data structure) 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 applies the operator to the argument values. Apply may call the evaluator to do more work... (This is possibly the most important example of Mutual Recursion. Ever.)
• Print: Uses __str__ to display the result.

Here's how all the pieces fit together:

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

Now let's explore how these parts work together in our mini-Python interpreter!

PyCombinator Interpreter

As mentioned above, you are going to implement a Python interpreter that can perform addition, multiplication, subtraction, and both create and call lambda functions. You will implement some of the key parts that will allow us to evaluate the following commands and more:

> add(3, 4)
7
> mul(4, 5)
20
> sub(2, 3)
-1
> (lambda: 4)()
4
> (lambda x, y: add(y, x))(3, 5)
8
> (lambda x: lambda y: mul(x, y))(3)(4)
12
> (lambda f: f(0))(lambda x: pow(2, x))
1

As you could see in the overview of interpreters above, an actual interpreter consists of many parts. In this lab, we will only ask you to implement the Eval and Apply steps as outlined in expr.py. Take a closer look at the other parts to understand how the lexer and parser, found in reader.py, and the read-eval-print-loop in repl.py all work together.

Run the following command to see how your input gets read into a Python representation:

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

Use OK to test your knowledge with the following questions:

python3 ok -q prologue -u

There is a lot of code in expr.py, and it might seem overwhelming to have to write your own interpreter. But don't worry! We will walk you through it all, step by step.

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!

Note: in addition to the descriptions written here in the spec, you should read the docstrings written for you in expr.py.

Question 1: Evaluating Names

As the first thing, we want to be able to evaluate Names. Names would be variable names like x and y in the above examples. As we know from our environment diagrams, it is important which environment (frame) 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 (as strings) to their values (which are 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 of this name if the name is bound. For instance, consider this case:

$ python3 repl.py
> (lambda x: x + y)(3)

How do we know what y is? We don't! 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)')

You should think about how you can tell if a certain name is bound in env. Now implement Name.eval.

def eval(self, env):
    """
    >>> env = {'a': Number(1), 'b': Number(2)}
    >>> Name('a').eval(env)
    Number(1)
    >>> Name('b').eval(env)
    Number(2)
    >>> try:
    ...     print(Name('c').eval(env))
    ... except NameError:
    ...     print('Exception raised!')
    Exception raised!
    """
    "*** YOUR CODE HERE ***"
    pass # REPLACE THIS LINE
    if self.string not in env:
        raise NameError("name '{}' is not defined".format(self.string))
    return env[self.string]

Toggle Solution

Use OK to test your code:

python3 ok -q Name.eval

Question 2: 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 self.operands instance attribute. Since there might be multiple operands — e.g. lambda x, y: add(x, y) — self.operands will be a list. That is, self.operator will be an Expr, and 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 operand.
• self.operands would be [Literal(3), Literal(4)]

Now, implement CallExpr.eval. Recall that when we evaluate a call expression, we first evaluate the operator and then the operands, and finally apply the operator to the operands. This will only work for primitive expressions right now; we'll implement lambdas later. Take a look at the bottom of the expr.py file where the global frame with all the primitives is defined.

Also, check out the definition of the PrimitiveFunction class which inherits from Value. All Values have an apply method that takes a list arguments of the Values you pass to the function, and outputs the resulting Value of applying the operator to the operands. In the documentation for the Value class, you will see that we use three different types (subclasses) of Value. Each of these implements its own 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)
    Number(4)
    >>> new_env['a'] = Number(5)
    >>> add.eval(new_env)
    Number(8)
    >>> CallExpr(Name('max'), [Name('b'), Literal(4)]).eval(new_env)
    Number(4)
    >>> read('add(mul(3, 4), b)').eval(new_env)
    Number(14)
    """
    "*** YOUR CODE HERE ***"
    pass # REPLACE THIS LINE
    function = self.operator.eval(env)
    arguments = [operand.eval(env) for operand in self.operands]
    return function.apply(arguments)

Toggle Solution

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

Question 3: 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 : f(0). For the corresponding LambdaFunction instance, we would have the following attributes:

• parameters — a list of strings, e.g. ['f']
• body — an Expr, e.g. CallExpr(Name('f'), [Literal(0)]) (the Literal will be turned into a Number in the Literal.eval method).
• 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 probably have to modify the environment you evaluate the function body on. Because our environments are represented with mutable dictionaries, make sure that you modify a copy of your parent environment. If you have a dictionary d, you can make a copy of it by saying d_copy = d.copy().

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)])
    Number(3)
    >>> add_lambda.apply([Number(3), Number(4)])
    Number(7)
    >>> sub_lambda = read('lambda add: sub(10, add)').eval(global_env)
    >>> sub_lambda.apply([Number(8)])
    Number(2)
    >>> add_lambda.apply([Number(8), Number(10)]) # Make sure you made a copy of env
    Number(18)
    """
    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)

Toggle Solution

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.

Extra Question

Question 4: Handling Exceptions

It's a pretty cool interpreter we have right now. 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:
    <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.

try:
    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!