Lab 11 - Interpreters

This lab is aimed at getting you familiar with the parts of a simple Python interpreter.

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab11/

The first question is non-coding and tests your general knowledge of interpreter functionality.

Q2: Evaluating Names

The first type of PyCombinator expression that we want to evaluate are names. In our program, a name is an instance of the Name class. Each instance has a string attribute which is the name of the variable -- e.g. "x".

Recall that the value of a name depends on the current environment. In our implementation, an environment is represented by a dictionary that maps variable names (strings) to their values (instances of the Value class).

The method Name.eval takes in the current environment as the parameter env and returns the value bound to the Name's string in this environment. Implement it as follows:

• If the name exists in the current environment, look it up and return the value it is bound to.

• If the name does not exist in the current environment, raise a NameError with an appropriate error message:

  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 ***"

Q2: Solution

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 in env:
        return env[self.string]
    
    raise NameError('{var} is not defined'.format(var=self.string))

Q3: Evaluating Call Expressions

Now, let's add logic for evaluating call expressions, such as add(2, 3). Remember that a call expression consists of an operator and 0 or more operands.

In our implementation, a call expression is represented as a CallExpr instance. Each instance of the CallExpr class has the attributes operator and operands. operator is an instance of Expr, and, since a call expression can have multiple operands, operands is a list of Expr instances.

For example, in the CallExpr instance representing add(3, 4):

• self.operator would be Name('add')

• self.operands would be the list [Literal(3), Literal(4)]

In CallExpr.eval, implement the three steps to evaluate a call expression:

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

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 ***"

Q3: Solution

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 ***"
    func = self.operator.eval(env)
    operands = []
    
    for operand in self.operands:
        operands.append(operand.eval(env))
    
    return func.apply(operands)

Extra

Q4: Applying Lambda Functions

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab11/#q4

Q4: Solution

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 ***"
    p_env_cp = self.parent.copy()

    for par, arg in zip(self.parameters, arguments):
        p_env_cp[par] = arg

    return self.body.eval(p_env_cp)

Q5: Handling Exceptions

Specs: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab11/#q5

Q5: Solution

Add the following "catch" lines into the try-except block in the loop in repl.py

        except (SyntaxError, NameError, ZeroDivisionError, OverflowError, TypeError) as err:
lab11 files added
            print(type(err).__name__ + ':', err)