Assignment page: http://www.cs.ust.hk/~dekai/151/assignments/a3/html/
Course page: http://www.cs.ust.hk/~dekai/151/
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.
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.
After this step,
parse() and any other functions that made proper use of the interface encapsulated by
Cell.hpp should all still work.
Take advantage of your cleaner polymorphic implementation of
eval() implementation to neatly add the capability to define symbols. (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 is to be the same as the value resulting from evaluating the second operand (which is
30 in this example), but that is not really the point of the
define operator. Instead, the real point is that after evaluating the expression
(define x (* (+ 2 3) 6)) the symbol
x will be bound to
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.
To accomplish this, you are to implement a global symbol table usi ng 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.)
See the examples under step 3 for additional clarification.
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
Here's an extended example session with a correct implementation:
> (define a 3)
> (define asquared (* a a))
> (define b 4.0)
> (define csquared (+ asquared (define bsquared (* b b))))
> (+ csquared 1)
> (define foo "hello")
> (* foo asquared)
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.
The only difference between a3.tar.gz and a2.tar.gz is a new version of
parse.cpp that recognizes the
define operator (and of course, these
README instructions). Again, remember that we're only giving you the source code of
parse.cpp for your convenience, in case you want to build your assignment on some other machine outside the lab. You still shouldn't look inside
parse.cpp at all. (In the real world, you would only get the separately-compiled
parse.o, so you couldn't look inside
parse.cpp even if you wanted to!)
Otherwise, we are not including any new code at all. The implementation is up to you. Except for the new version of
parse.cpp, you should start from your Assignment 2 implementation and extend it. But be careful! You still may not break any of the encapsulation rules from Assignment 2.
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 best possible use of templates - 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!