Author: Dekai Wu
Date: Due 2012.10.28 at 23:00 by CASS
Download: http://www.cs.ust.hk/~dekai/3031/assignments/a3.tar.gz
Assignment page: http://www.cs.ust.hk/~dekai/3031/assignments/a3/html/
Course page: http://www.cs.ust.hk/~dekai/3031/
In this third piece of your programming project, 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.
The first step is to fix your program so that whenever it encounters an error condition, it follows more solid software engineering practice by throwing an exception, instead of ungracefully printing an error message and exiting.
To support this, the main.cpp driver program we give you has been modified so that the read-eval-print loop catches all runtime_exception objects you might throw. Our exception handler will print "ERROR: " followed by the specific message string obtained by calling the what() member function on the runtime_exception object you threw (so try to supply useful, meaningful error messages). Then, instead of clumsily exiting the program, it will go back to the beginning of the read-eval-print loop and await another input expression.
The next step is to add the capability to define symbols, i.e., symbolic variables. (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 from a define expression is always nil, i.e., the empty list (), so the return value is irrelevant. Instead, the real point is that after evaluating the expression (define x (* (+ 2 3) 6)) the symbol x will be bound to 30.
In C++, this is roughly analogous to a variable definition with an initial value, as in int x((2 + 3) * 6).
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. (This is roughly analogous in C++ to saying that all variable definitions must be constant, as in const int x((2 + 3) * 6). Later on, we'll explore the possibility of allowing existing variables to be rebound via an assignment operator.)
To accomplish this, you are to implement a global symbol table using the map container template.
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.)
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.
Note that in this step, we are changing the specification of what it means to evaluate a symbol! Unlike in Assignments 1 and 2, evaluating a symbol foo no longer simply returns foo. Instead, you need to look up the symbol name foo in the symbol table, and return the value bound to that symbol name.
Here's an extended example session with a correct implementation:
% main
> (define a 3)
()
> a
3
> (define asquared (* a a))
()
> asquared
9
> (define b 4.0)
()
> b
4.0
> (define csquared (+ asquared (* b b)))
()
> csquared
25.0
> (+ csquared 1)
26.0
> csquared
25.0
> (define foo (quote hello))
()
> foo
hello
> bar
ERROR: attempt to reference an undefined symbol "bar"
> (define baz hello)
ERROR: attempt to reference an undefined symbol "hello"
>
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.
Add boolean expressions using the less than < and not operators, both of which return either 0 or 1 int values, representing false and true respectively.
The < operator accepts zero or more operands, each of which can be either int or double, returning 0 if any two consecutive operands are not monotonically increasing, and 1 otherwise.
> (< 3 4)
1
> (< 4.2 3)
0
> (< 3 3.0)
0
> (<)
1
> (< 3)
1
> (< 3 4 6 8 9)
1
> (< 3 6 4 8 9)
0
The not operator accepts exactly one operand, returning 1 if the operand is zero (either int or double), and 0 otherwise.
> (not 0)
1
> (not (- 3.2 3.2))
1
> (not 1)
0
> (not 4.2)
0
> (not (< 7 8))
0
Your boolean expressions will be especially useful in conjunction with your existing if operator which, recall, evaluates the first argument, and then evalutes and returns the second argument if the first argument evaluated to a non-zero value, otherwise evaluating and returning the third argument (remember that this short-circuit evaluation method is critically important):
> (if (< 4 3) 66 77)
77
Recall that the behavior of if is analogous to the <bool> ? <then> : <else> operator in C++.
print and eval in Scheme
Finally, you will expose your existing C++ implementation of print and eval so that they can be called from Scheme, just like you already did in Assignment 2 for the cons, car, cdr, and nullp operators.
The print operator accepts one operand, which it evaluates, printing the resulting value onto the cout output stream. The return value from a print expression is always nil, i.e., the empty list ().
> (print (+ 1 2))
3
()
> (print (quote (+ 1 2)))
(+ 1 2)
()
The eval operator accepts one operand, and returns the result of evaluating the operand:
> (cons (quote +) (quote (1 2)))
(+ 1 2)
> (eval (cons (quote +) (quote (1 2))))
3
> (quote (cons (quote +) (quote (1 2))))
(cons (quote +) (quote (1 2)))
> (eval (quote (cons (quote +) (quote (1 2)))))
(+ 1 2)
> (eval (eval (quote (cons (quote +) (quote (1 2))))))
3
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.
Except for the modified version of main.cpp, all other source files in a3.tar.gz are identical to those from a2.tar.gz.
So you should start from your Assignment 2 implementation and extend it, replacing only the old main.cpp with the new one. Be careful! You still may not break any of the encapsulation rules from Assignment 2.
The a3.tar.gz tarball contains many development test cases to help you with testing your implementation. They are broken into three categories: easy cases (testinput.dev.easy.txt), general cases (testinput.dev.general.txt, and exception cases (testinput.dev.exception.txt). All the correct outputs are also given to you for both the easy cases (testinput.dev.easy.ref.txt) and the general cases (testinput.dev.general.ref.txt).
Your submitted implementation will be graded using a similar (but different) set of test cases.
In addition, the tarball contains the binary executable of a reference solution (compiled for the Linux lab machines you are supposed to be using). You can run this program to see the possible behavior of a correct solution. (Note that your implementation might give different results for some error cases, because for all operators other than if, we have deliberately avoided specifying what order the operands are evaluated and checked. This could lead to different errors being discovered first, causing evaluation to be prematurely aborted when the exception is thrown.)
Remember, 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.
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 - 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.5.8