Consider what happens in even a simple Python dialog:
>>> 2+3*4 14
The Python system had to examine the expression the user typed in and uncover that its structure is a sum, with the right operand of the sum being a product. (In particular, the expression is not a product with a sum as its left operand.) This process of finding the structure is known as parsing. Parsing provides a structural understanding of the Python expression that is the first step toward understanding what computation it specifies and carrying out that computation. Speaking generally, carrying out a specified computation is known as interpretation. For example, interpreting an assignment statement would entail changing the value associated with a variable. In the particular case where the program text to interpret is an expression, so that interpretation entails computing the expression's value, we can also call the process evaluation rather than interpretation.
In this project you will be working with a Python version of the shift-reduce evaluator from Section 13.2 of Concrete Abstractions. Your primary objective is to add one additional feature to the evaluator: the use of exclamation point as a factorial operation. You will work individually.
The evaluator is contained in evaluate.py, which makes use of RA_stack.py. I will demonstrate how you can work with this system, not only evaluating entire expressions, but also testing out individual components in isolation, such as seeing how a single reduction modifies the evaluation stack. We may do some of this in class; to the extent we don't have time then, I'll take time for it at the beginning of the first lab day.
You should work Exercise 13.28 on pages 478-479. This problem concerns the addition of the factorial operation to the evaluator, at the conceptual level of adding it to the table, rather than at the detailed level of adding it to the Python code. Because this will serve as the foundation of your lab, you should check your work carefully. Start by checking your work yourself, but then cross-check with other students or me.
One item you will specifically want to check, because I
have frequently seen students get it wrong, is that you correctly
handle factorials of factorials, such as "3!!".
If you are for some reason held up on this design problem, the first two sections of coding can be done without any dependence on it.
Add a procedure to evaluate.py that takes an integer argument and
returns its factorial. For now, you can assume that the argument is
nonnegative and small enough that its factorial can be represented as
an ordinary integer. (Extra credit problems address these issues.)
You will receive partial credit if you have a working procedure that
calls itself recursively (as a Scheme version normally would). For
full credit, you need to write a version that uses a
while or for loop to carry out an iteration.
Be sure to test your procedure on its own.
Modify the reduce procedure, which corresponds to the
Scheme procedure reduce!, so as to perform the
appropriate kind of reduction if the top of the stack contains an
exclamation point and a number. This should make use of your
procedure for computing factorials. You should test your modified
reduce outside the context of the evaluator, by directly
invoking it on an RA stack onto which you have pushed appropriate tokens.
Your table from Exercise 13.28 needs to be translated into Python.
Make the appropriate additions to the should_reduce and
should_shift procedures, which are the Python equivalents of the
Scheme procedures reduce? and shift?.
One topic to think about is whether the exclamation point should be counted as an "operator" for the purpose of procedures such as is_operator. Does it play a sufficiently similar role in the structure of expressions to lump it in with the others?
Be
sure to test your modified procedures on their own to
verify that they correspond to your table.
At this point, you should have all the pieces in place to test evaluating expressions that contain exclamation points. Do so.
You can do any of these, or more than one if you like. They are mostly independent of each other, though there is some interaction between the third and fourth.
You can add variables to the language. To avoid changing tokenize, you can stick to variables with single-letter names. Think about what sort of data structure you will use to store variables' values. Change the evaluator to handle two new kinds of expressions: a variable (which evaluates to the variable's current value) and an assignment statement (which changes the variable's value as well as evaluating to that new value). Before you start writing code, going back to the table to understand the shift and reduce actions would be smart.
The program is currently light on error checking. Change your
factorial procedure so that it raises an
Exception if asked to compute the factorial of a negative
number. Also, the RA_stack class has one error check already in place,
but really should have another one as well. Find that second place
and introduce the error check.
If you take the factorial of a reasonably large integer, you'll find that the evaluation fails because the answer is a long integer, whereas the evaluator is only prepared for normal integers. You can fix this by using Python's long integer type. (Starting in Python 3.0, this is no longer an issue.) Because large integers can arise even without factorials, you shouldn't limit yourself just to factorials: you should use long integers consistently throughout the whole evaluator.
What happens if you evaluate an expression like "7/2"?
Explain why. Design and program a modification to the evaluator so
that it will provide more precise answers in cases like this than the original version does under Python 2.x, and doesn't fail entirely, unlike what would happen using the original version with Python 3.x.
You should write a report that uses your table from Exercise 13.28 as the focal point for explaining your modifications to the evaluator. Your target audience should be people who are familiar with the original evaluator but who don't know what feature you were adding or how you were doing so.
Your report should include the code for all modified or newly added procedures. However, don't include any procedures that are left unchanged.
You need not comment upon testing unless there is some bug that you found in the course of testing but were unable to fix. In that case, it is important for you to report what you found to be not working. Otherwise, you will lose double points: one loss of points for the programming difficulty, and another for (apparently) not having done adequate enough testing to uncover the existence of the bug.
If you take any of the extra credit opportunities, be sure to specifically mention them in your report, rather than relying on me to spot them in your code.
The gradesheet shows how the report will be graded.