Download: http://www.cs.ust.hk/~dekai/151/assignments/a3.tar.gz
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 IntCell and 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 cons.hpp or 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 30.
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 70.
Here's an extended example session with a correct implementation:
% main
> (define a 3)
3
> (define asquared (* a a))
9
> (define b 4.0)
4.0
> (define csquared (+ asquared (define bsquared (* b b))))
25.0
> b
4.0
> bsquared
16.0
> (+ csquared 1)
26.0
> csquared
25.0
> (define foo "hello")
"hello"
> (* foo asquared)
"hellohellohellohellohellohellohellohellohello"
>
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 parse.hpp, parse.cpp, cons.hpp, eval.hpp, or 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!
1.4.6