CS61A Lab 10: Exceptions and Calc

Week 12, 2013

You can get the starter files by typing this into your termianl:

cp -r ~cs61a/lib/lab/lab10/starters/* .

Don't forget the dot at the end!

Exceptions!

We've already seen exceptions in discussion, but let's do a quick review. Exceptions allow us to try a chunk of code, and then catch any exceptions that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

try:
    <try suite>
except Exception as e:
    <except suite>
else:
    <else suite>
finally:
    <finally suite>

Notice that we can catch the exception as e. This assigns e to the exception object. This can be helpful when we want to give extra information on what happened. For example, we can print(e).

Also, we have an optional else case. The else suite is executed if the try suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

Q1

For practice, let's use exceptions to create a safe Bank (you can find it in your starter file), which only stores numerical amounts of money. Fill in the deposit and withdraw methods. These methods should only take non-negative numerical values.

Side note: we can also define our own exceptions! You will see an example of this in project 4, where a SchemeError class has been defined for you.

Calc: our first interpreter!

NOTE: Solutions for the rest of the problems can all be found in these two files.

Solutions:
calc.py
scheme_reader.py

We're beginning our journey into the world of interpreters! You may have seen an interpreter before. (Hint: that thing you've been running all of your Python in? Yeah, that's an interpreter). In fact, the Python interpreter we've been using all semester long is really nothing but a program, albeit a very complex one. You can think of it as a program that takes strings as input and produces their evaluated result as output.

There's nothing magical about interpreters, though! They're programs, just like the one's you've been writing throughout the entire semester. In fact, it's possible to write a Python interpreter in Python; PyPy is proof of that. However, because Python is a complex language, writing an interpreter for it would be a very daunting project. Instead, we'll play around with an interpreter for a calculator language.

In lecture, you were introduced to our first interpreter program, calc, which acts as a simple calculator. You should have already copied the starter files (scheme_reader.py, calc.py, etc.) at the start of the lab.

You can also find the code in a zip file here. You can try running calc by running this command in the terminal:

python3 calc.py

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

Q2

Trace through the code in calc.py that would be evaluated when you type the following into calc.

> 2
> (+ 2 3)
> (+ 2 3 4)
> (+ 2 3)
> (+ 2)
> (+ 2 (* 4 5))

Infix notation

While prefix notation (+ 2 3) is easy for computers to interpret, it's not very natural for humans. We'd much prefer infix notation (2 + 3). Let's implement this in our version of calc!

To do this, you need to fill in the following functions, which are in the scheme_reader.py file.

Q3

Implement read_infix. This function takes two arguments: first, the first expression in the infix expression; and src, the Buffer of tokens that contains the rest of the infix expression (and possibly more). For example, to construct 3 + 4 5 (note: the 5 will be ignored, so it's really just 3 + 4), we call

read_infix(3, Buffer(tokenize_lines('+ 4 5')))

The return value should be an expression which is mathematically the same as the infix notation expression (e.g. + 3 4), but written using Scheme style Pairs. See the doctests for simple examples. Follow these steps:

  1. First, check if there are more tokens left in the Buffer (hint: the Buffer class in the buffer.py file has a more_on_line property method). If there aren't, we should just return nil. (Why?)
  2. Next, figure out what the operator and second half of the infix expression should be.
  3. Finally, return a Scheme-style expression which represents the same thing as the infix notation expression you parsed.

Q4

Implement next_is_op. This function returns True if the next token in the given Buffer is an operator, and False otherwise.

Hint: don't forget to check if there are any tokens in the buffer first. Also, don't remove any tokens from the Buffer (i.e. don't use pop).

Q5

Modify scheme_read to parse infix expressions. This requires modifying two parts of the code:

  1. First, we need to determine if we're dealing with an expression like "2 + 3". To do this, check if the first item in the Buffer is a float or a int. If it is, then check that the next token is an operator. If it is, read it like an infix expression. Otherwise, just return the value.
  2. Next, we have to deal with the case of infix notation inside parentheses. Without parentheses, 2 + 2 * 3 and 2 * 3 + 2 should produce the exact same result, but in calc, they don't! calc doesn't implement order of operations, because prefix notation naturally takes care of operator precedence (why?).

    Instead of solving the real problem, we'll implement a quick fix. If we allow expressions to be surrounded by parentheses, we can write expressions like 2 + (2 * 3), which will evaluate to the same thing as (2 * 3) + 2.

    To do this, we need to change how we parse lists. This logic should be very similar to what you did in the previous part of scheme_read.

And that's it! We have infix notation! The following inputs to calc should work.

> (+ 2 2 * 3)
8
> 2 + (- 5 2)
5
> (+ 1 3 * 4 (* 7 4))
41
> (2 * 3) + 6
12
> 6 + (2 * 3)
12

Defining Variables

Now we're going to add the ability to define variables. For example:

> (define x 3)
x
> (+ x 2)
5
> (* x (+ 2 x))
15

For this part, we will be modifying the calc.py file. Do we need to change calc_eval? calc_apply? Is define a special form?

Q6

Implement do_define_form. This function takes in a Pair that contains 2 items: the variable name, and the expression to which it should be assigned. do_define_form should modify the global environment, env (a dictionary) to contain the name/value binding. It should also return the name of the variable you're defining.

Q7

Finally, implement the lookup procedure in calc_eval. You should check if the given identifier is in the environment. If it is, then simply return the value associated with it. If not, you should raise an exception to signal that the user did something wrong.

And that's it! There you have basic variable declaration. Isn't that cool!??