Author: Dekai Wu

Date: Due 2014.11.26 at 23:00 by CASS

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

Assignment page: http://www.cs.ust.hk/~dekai/2012H/assignments/a6/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, specifically to replace the standard map you've been using for your symbol tables, instead using your own new hashtablemap implementation of a dictionary data structure based on hash tables).

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

Step 1: Implement hashtablemap

Look at hashtablemap.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 hash table, supporting exactly this interface. To handle collisions, you may choose either open addressing or separate chaining. If you use separate chaining, then for each bucket you may use either the standard linked list approach, or (if you wish) a binary search tree instead, re-using your bstmap implementation.

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 hashtablemap 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 hashtablemap.hpp and any other supporting files, all other source files in a6.tar.gz are identical to those from a3.tar.gz.

So you should start from your Assignment 4 (or Lab Assignment 5) 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 hashtablemap.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 hashtablemap.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!