Author: Dekai Wu

Date: Due in lab by CASS

Download: http://www.cs.ust.hk/~dekai/2012H/assignments/a5.tar.gz

Assignment page: http://www.cs.ust.hk/~dekai/2012H/assignments/a5/html/

Course page: http://www.cs.ust.hk/~dekai/2012H/

Your assignment

In this next piece of your programming project, you are assigned to maintain and extend the micro-Scheme interpreter you've built in Assignments 1, 2, 3, and 4, specifically to replace the standard map you've been using for your symbol tables, instead using your own new bstmap implementation of a dictionary data structure based on binary search trees).

For this assignment, we are giving you almost no new code. The tarball a5.tar.gz contains exactly the same files as a3.tar.gz, except for (1) these instructions and (2) a new bstmap.hpp interface, which you will need to implement.

Step 1: Implement bstmap

Look at bstmap.hpp. This is a subset of the standard C++ library's interface for the map dictionary data structure. (To keep your life simple, we have omitted extra niceties such as reverse iterators and memory allocation options.)

Implement a binary search tree, supporting exactly this interface. Since this is template based code, all the new code will need to go into the .hpp file.

Step 2: Replace all uses of std::map

You are now in a position to eliminate the use of the standard map dictionary. Globally replace all uses with your own bstmap instead throughout your code. Make sure that your entire micro-Scheme implementation still does exactly what it used to do.

Putting it all together and testing your implementation

Except for your new bstmap.hpp and any other supporting files, all other source files in a5.tar.gz are identical to those from a3.tar.gz.

So you should start from your Assignment 4 (or Lab Assignment 6) implementation and extend it. Be careful! You still may not break any of the encapsulation rules from Assignment 3.

Remember again, 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.

Important reminders

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 interface for your own new bstmap.hpp - but neatly, without messing up what you already have.

Again, 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).

The tarball you turn in will need to contain your new implementation of bstmap.hpp.

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!