Author: Dekai Wu
Date: Due 2007.03.28 at 23:00 by CASS
Download: http://www.cs.ust.hk/~dekai/151/assignments/a2.tar.gz
Assignment page: http://www.cs.ust.hk/~dekai/151/assignments/a2/html/
Course page: http://www.cs.ust.hk/~dekai/151/
You are assigned to maintain and extend the expression evaluator code built in Assignment 1. Your job this time is to take the following steps.
Completely re-implement the Cell class, to eliminate the use of a tagged union, by instead making use of polymorphism virtual functions. The Cell class is to become an abstract base class (ABC). Derived classes should include IntCell, DoubleCell, SymbolCell, and ConsCell.
After this step, your eval() implementation from Assignment 1 should still work (assuming you didn't break encapsulation!) Note that the interface specified in cons.hpp has not changed. The function definitions in cons.hpp may have changed to fit the new Cell implementation's use of late binding, but the declarations have not. This means that parse() and eval() and any other functions that made proper use of the interface encapsulated by cons.hpp should all still work.
Re-design your eval() implementation to be much cleaner, taking advantage of the polymorphism to get rid of all those ugly if-then-else and/or switch statements from your Assignment 1 version, by instead making appropriate use of function overriding and/or overloading.
To accomplish this step, you will have to extend the interface in Cell.hpp. Because of this, note that after this step, your new eval() implementation may no longer work with your old implementation of the Cell class from Assignment 1.
Take advantage of the cleaner polymorphic implementation, to add more arithmetic operators neatly. Besides the + and ceiling operators from Assignment 1, you should add the -, *, /, and floor arithmetic operators for int and double operands.
Note that the -, *, and / operators are generalized similarly to the + operator. The -, *, and / operators can also be called with more than two arguments; for example, (- 11 2 3) means the same thing as (- (- 11 2) 3). The same holds for the * and / operators, so for example, (* 11 2 3) means the same thing as (* (* 11 2) 3), while (/ 11 2 3) means the same thing as (/ (/ 11 2) 3).
If the * operator is called with zero arguments, then it simply returns 1, which is the identity value for multiplication (just like 0 for the + operator). If the * operator is called with one argument, then it returns the same value.
If the - operator is called with one argument, then it simply returns the negative of the argument. If the / operator is called with one argument, then it simply returns the inverse of the argument.
To avoid ambiguity, the - and / operators cannot be called with zero arguments, unlike the + and * operators. So, for example (-) is considered to be a semantically ill-formed expression.
If you've done things correctly, you should notice how much easier it is to add all these operators, now that you have polymorphism.
Next you will add support for quoted expressions, which allow you to prevent eval() from trying to evaluate s-expressions. The special quote operator takes exactly one operand, which can be any s-expression, and simply returns the exact same expression. The operand is not evaluated, so it just needs to be a syntactically valid tree (including empty lists as well as leaf nodes representing atomic ints, doubles, or symbols). It does not need to be a semantically valid expression. For example:
> (quote (a b c))
(a b c)
> (quote (+ 2 3))
(+ 2 3)
> (quote (if if 5))
(if if 5)
> (quote ())
()
> (quote (quote (a b c)))
(quote (a b c))
> (quote hello)
hello
> (quote 6)
6
> (quote 3.14)
3.14
> (+ 4 (quote 2))
6
> (+ 4 (quote (* 2 3)))
ERROR: operand of + cannot be a list
> (+ 4 (* 2 3))
10
cons, car, cdr, and nullp in Scheme
Finally, you will expose your existing cons.hpp C++ implementation of cons, car, cdr, and nullp so that they can be called from Scheme just like other operators such as ceiling:
> (cons 4 (quote ()))
(4)
> (cons (quote hello) (cons 4 (quote ())))
(hello 4)
> (cons 2 (cons (quote hello) (cons 4 (quote ()))))
(2 hello 4)
> (car (cons 2 (cons (quote hello) (cons 4 (quote ())))))
2
> (cdr (cons 2 (cons (quote hello) (cons 4 (quote ())))))
(hello 4)
> (nullp foo)
0
> (nullp 0)
0
> (nullp 1)
0
> (nullp (quote ()))
1
> (nullp (quote (a b c)))
0
This time, we are not including any dummy implementation of Cell.hpp, Cell.cpp or eval.cpp at all. The implementation is up to you. But be careful! You must make sure your Cell interface fits what cons.hpp expects!
We're again including parse.cpp for your convenience, in case you want to build your assignment on some other machine outside the lab. But remember you 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!)
You must follow the design approach outlined in this document. Do not just implement the required functionality using a different design.
You are expected to make best possible use of polymorphism and virtual functions. For example, of course your old eval() from Assignment 1 should still work, but without making correct use of polymorphism throughout, it will not be considered a solution to Assignment 2 (even if it implements the additional operators).
This time you must use virtual functions in this assignment, but you still may not use templates. This assignment is about dynamic OO support in C++. (You'll get a chance to use templates in the following assignment...)
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 a tar file a2.tar.gz containing all source files including your own implementation of Cell.hpp, Cell.cpp, and eval.cpp. Depending on your approach, you may or may not also wish to add more files. You should also make sure to include all doxygen generated HTML documentation.
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