Author: Dekai Wu
Date: Due 2009.04.21 at 23:00 by CASS
Assignment page: http://www.cs.ust.hk/~dekai/151H/assignments/a3/html/
Course page: http://www.cs.ust.hk/~dekai/151H/
In this third piece of your programming project, you are assigned to maintain and extend the expression evaluator code built in Assignment 2. Your job this time is to take the following steps.
The first step is to fix your program so that whenever it encounters an error condition, it follows more solid software engineering practice by throwing an exception, instead of ungracefully printing an error message and exiting.
To support this, the
main.cpp driver program we give you has been modified so that the read-eval-print loop catches all
runtime_exception objects you might throw. Our exception handler will print "ERROR: " followed by the specific message string obtained by calling the
what() member function on the
runtime_exception object you threw (so try to supply useful, meaningful error messages). Then, instead of clumsily exiting the program, it will go back to the beginning of the read-eval-print loop and await another input expression.
The next step is to add the capability to define symbols, i.e., symbolic variables. (In the next step, you will add the capability to use the symbols that have been defined.)
Here's how to proceed. In addition to all the operators from Assignments 1 and 2, you are to add a new
define operator. This operator accepts exactly two operands, as for example in
(define x (* (+ 2 3) 6)). The first operand must be a symbol, while the second operand can be of any type. The return value from a
define expression is always nil, i.e., the empty list
(), so the return value is irrelevant. Instead, the real point is that after evaluating the expression
(define x (* (+ 2 3) 6)) the symbol
x will be bound to
In C++, this is roughly analogous to a variable definition with an initial value, as in
int x((2 + 3) * 6).
Note that symbols may not be redefined. So if
x has already been defined as above, then evaluating
(define x 42) should generate an error. (This is roughly analogous in C++ to saying that all variable definitions must be constant, as in
const int x((2 + 3) * 6). Later on, we'll explore the possibility of allowing existing variables to be rebound via an assignment operator.)
To accomplish this, you are to implement a global symbol table using the
map container template you learned about in lab. You will use the
map container to remember what values have been bound to what symbols. The
map container gives you a dictionary data structure, so the interface is slightly more powerful than the sequence containers we discussed in lecture. You are to instantiate the
map container using the template parameters
map<string, Cell*>. The string is to be used hold a symbol name, while the Cell is to be used to hold a copy of the value that the symbol is bound to. (To learn how to use
map, consult your textbook, the lab pages, and/or the reference pages mentioned in the lecture slides.)
Next, you should extend your evaluator so that if
eval() is called on a previously defined symbol, then it will return the value that the symbol has been bound to. So assuming
x has been defined as in the foregoing example, then later on, evaluating the expression
(- 100 x) should return the value
Note that in this step, we are changing the specification of what it means to evaluate a symbol! Unlike in Assignments 1 and 2, evaluating a symbol
foo no longer simply returns
foo. Instead, you need to look up the symbol name
foo in the symbol table, and return the value bound to that symbol name.
Here's an extended example session with a correct implementation:
> (define a 3)
> (define asquared (* a a))
> (define b 4.0)
> (define csquared (+ asquared (* b b)))
> (+ csquared 1)
> (define foo (quote hello))
ERROR: attempt to reference an undefined symbol "bar"
> (define baz hello)
ERROR: attempt to reference an undefined symbol "hello"
Note that evaluating a symbol that has not already been defined should generate an error.
Also note that it results in undefined behavior if you try to evaluate an expression containing both a
(define x ...) and also some use of the value of
x. For example,
(+ x (define x 4)) does not result in well-defined behavior. This is because
eval() does not guarantee what order the operands are evaluated, so we cannot predict what value (if any)
x will have at the time it is evaluated.
Add boolean expressions using the less than
not operators, both of which return either 0 or 1 int values, representing false and true respectively.
< operator accepts zero or more operands, each of which can be either int or double, returning 0 if any two consecutive operands are not monotonically increasing, and 1 otherwise.
> (< 3 4)
> (< 4.2 3)
> (< 3 3.0)
> (< 3)
> (< 3 4 6 8 9)
> (< 3 6 4 8 9)
not operator accepts exactly one operand, returning 1 if the operand is zero (either int or double), and 0 otherwise.
> (not 0)
> (not (- 3.2 3.2))
> (not 1)
> (not 4.2)
> (not (< 7 8))
Your boolean expressions will be especially useful in conjunction with your existing
if operator which, recall, evaluates the first argument, and then evalutes and returns the second argument if the first argument evaluated to a non-zero value, otherwise evaluating and returning the third argument (remember that this short-circuit evaluation method is critically important):
> (if (< 4 3) 66 77)
Recall that the behavior of
if is analogous to the <bool>
: <else> operator in C++.
Finally, you will expose your existing C++ implementation of
eval so that they can be called from Scheme, just like you already did in Assignment 2 for the
cout output stream. The return value from a
> (print (+ 1 2))
> (print (quote (+ 1 2)))
(+ 1 2)
eval operator accepts one operand, and returns the result of evaluating the operand:
> (cons (quote +) (quote (1 2)))
(+ 1 2)
> (eval (cons (quote +) (quote (1 2))))
> (quote (cons (quote +) (quote (1 2))))
(cons (quote +) (quote (1 2)))
> (eval (quote (cons (quote +) (quote (1 2)))))
(+ 1 2)
> (eval (eval (quote (cons (quote +) (quote (1 2))))))
Use function templates to eliminate the redundancy in your previous implementation of the evaluator. You should have noticed that your previous implementation of the addition, subtraction, multiplication, and division functions looked almost identical for both
DoubleCell operands. You probably did a lot of "reuse by copying". This seems wasteful, ugly, bug-prone, and hard to maintain. Really you should be able to use function templates so that you only have one copy of the code, that can be instantiated for all the different cases.
Please note that you should not remove the polymorphism from your Assignment 2 implementation. The use of function templates is in addition to your existing virtual functions, and is just to make your existing functions more concise.
Except for the modified version of
main.cpp, all other source files in
a3.tar.gz are identical to those from
So you should start from your Assignment 2 implementation and extend it, replacing only the old
main.cpp with the new one. Be careful! You still may not break any of the encapsulation rules from Assignment 2.
The a3.tar.gz tarball contains many development test cases to help you with testing your implementation. They are broken into three categories: easy cases (
testinput.dev.easy.txt), general cases (
testinput.dev.general.txt, and exception cases (
testinput.dev.exception.txt). All the correct outputs are also given to you for both the easy cases (
testinput.dev.easy.ref.txt) and the general cases (
Your submitted implementation will be graded using a similar (but different) set of test cases.
In addition, the tarball contains the binary executable of a reference solution (compiled for the Linux lab machines you are supposed to be using). You can run this program to see the possible behavior of a correct solution. (Note that your implementation might give different results for some error cases, because for all operators other than
if, we have deliberately avoided specifying what order the operands are evaluated and checked. This could lead to different errors being discovered first, causing evaluation to be prematurely aborted when the exception is thrown.)
Remember, the objective of this programming project is for you to train your skills, by practicing correct software engineering techniques enabling you to build, maintain, and extend a non-trivial piece of well-engineered code.
You must follow the design approach outlined in this document. Do not just implement the required functionality using a different design.
This time you must use templates. In this assignment, you are expected to make good use of the STL
map - but neatly, without messing up the polymorphic approach you built in Assignment 2.
Remember we are focusing on proper use of encapsulation. So you still should not edit the files
main.cpp. Again, the programming assignments are mini-exercises in how multiple programmers are supposed to interact and communicate in the real world; these files are owned and maintained by the other author(s).
You will need to turn in your own improved and extended implementation of
eval.cpp. Depending on your approach, you may or may not also wish to add more files.
Depending on your approach, you may or may not need to change the
Makefile. Whether you changed it or not, always make sure you include whatever
Makefile is needed to build your program, when you submit assignment. Otherwise, the graders cannot build your program.
You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.
Your programming style (how clearly and how well you speak C++) is what will be graded. Correct functioning of your program is necessary but not sufficient!