Lab 11: Interpreters
Due at 11:59pm on 7/28/2016.
Starter Files
Download lab11.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.
- 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.
Topics
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.
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.
- 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, soeval
andapply
are mutually recursive.
- Eval takes an expression and evaluates it according to the rules of the
language. Evaluating a call expression involves calling
- 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)
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
Here is an overview of each of the REPL components in our interpreter.
Read: The function
read
inreader.py
calls the following two functions to parse user input.- The lexer is the function
tokenize
inreader.py
which splits the user input string into tokens. - The parser is the function
read_expr
inreader.py
which parses the tokens and turns expressions into instances of subclasses of the classExpr
inexpr.py
, e.g.CallExpr
.
- The lexer is the function
Eval: Expressions (represented as
Expr
objects) are evaluated to obtain values (represented asValue
objects, also inexpr.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
callseval
to evaluate the body of the function.
- Eval: Each type of expression has its own
- 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 Name
s. 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)
Number(1)
>>> 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 Expr
s.
For example, for add(3, 4)
:
self.operator
would beName('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:
- Evaluate the operator in the current environment.
- Evaluate the operand(s) in the current environment.
- 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)
Number(4)
>>> new_env['a'] = Number(5)
>>> add.eval(new_env)
Number(8)
>>> read('max(b, a, 4, -1)').eval(new_env)
Number(5)
>>> read('add(mul(3, 4), b)').eval(new_env)
Number(14)
"""
"*** 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
— anExpr
, 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.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 have to modify the
environment you evaluate the function body in.
There are three steps to applying a LambdaFunction
:
- Make a copy of the parent environment. You can make a copy of a dictionary
d
withd.copy()
. - Update the copy with the
parameters
of theLambdaFunction
and thearguments
passed into the method. - 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)])
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)
>>> read('(lambda x: lambda y: add(x, y))(3)(4)').eval(global_env)
Number(7)
>>> read('(lambda x: x(x))(lambda y: 4)').eval(global_env)
Number(4)
"""
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:
<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!