Lab 10: Interpreters
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:
- The language being interpreted/implemented. In this lab, you will implement the PyCombinator language.
- 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
inreader.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
andread_expr
inreader.py
take care of this step. The data structures that we use are classes inexpr.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.)
- 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
- 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 Name
s. Name
s 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]
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 Expr
s.
For example, for add(3, 4)
:
self.operator
would beName('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 Value
s have an apply
method that takes a list arguments
of the Value
s 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)
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
— anExpr
, e.g.CallExpr(Name('f'), [Literal(0)])
(theLiteral
will be turned into aNumber
in theLiteral.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.LambdaFunction
s are created in theLambdaExpr.eval
method, and the current environment then becomes thisLambdaFunction
'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
Value
s 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)
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 TypeError
s — 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!