Midterm #1CMSC 433Programming Language Technologies and ParadigmsSpring 2006March 29, 2006GuidelinesThis exam has 10 pages (including this one); make sure you have them all. Put your name on each pagebefore starting the exam. Write your answers directly on the exam sheets, using the back of the page asnecessary. Bring your exam to the front when you are finished. Please be as quiet as possible.If you have a question, raise your hand. If you feel an exam question assumes som ething that is notwritten, write it down on your exam sheet. Barring some unforeseen error on the exam, however, youshouldn’t need to do this at all, so be careful when making assumptions.You may avail yourself of the punt rule. If you write down punt for any part of a question with aspecifically-assigned point value, you will earn 1/5 of the points for that question (rounded down).Use good test-taking strategy: read through the whole exam first, and first answer the questions thatare easiest for you and are worth the mos t points.Question Points Score1 202 203 204 205 20Total 1001. (Short answer, 20 points)(a) (5 points) Give a reason why JUnit tests could be viewed as black box tests, or alternativelygive a reason why they could be viewed as white box tests.(b) (5 points) A principle underlying many design patterns is “encapsulate what varies.” Givean example of a design pattern that follows this principle and justify your answer.(c) (5 points) Synchronization (i.e., locking) is one way to avoid data races in multi-threadedprograms. Briefly describe another technique for avoiding races.(d) (5 points) Is deadlock a violation of safety or liveness?22. (Generics, 20 points)Below is non-generic interface for a stack:public interface Stack {public void push(Object x);public Object pop() throws EmptyStackException;public bool empty();}The push method adds an element to the stack, and pop removes one, throwing an exce ption ifthe stack is empty. empty returns true if the stack is empty, false otherwise. Here is some codethat uses the stack:Stack s = ...; // some implementation; we don’t care how we got its.push("hello");s.push("there");String x = (String)s.pop();String y = (String)s.pop();(a) (10 points) Rewrite the code for the Stack interface to use generics instead. Rewrite theexample code to use your new generic Stack (or clearly modify the example code above).3(b) (10 points) Suppose we have some classes for defining shapes, where all shapes have a drawmethod:interface Shape { class Square implements Shape { ... }void draw(); class Circle implements Shape { ... }}In Java 1.4, we could write the following method for drawing all shapes stored in a stack:static void popAndDrawAll(Stack shapes) {while (!shapes.empty()) {Shape s = (Shape)shapes.pop()s.draw();}}Rewrite this code to use the generic stack you defined for the first part, implementing eithera polymorphic method or a method using wildcards. You should not need any dynamicdowncasts. Your new code should type check when used as follows:Stack<Shape> s1 = ...;Stack<Square> s2 = ...;popAndDrawAll(s1);popAndDrawAll(s2);43. (Visitor Pattern, 20 points)Background (Problem statement begins on the next page.) Below are some classes that im-plement arithmetic expressions, along with an accept method to implement the visitor pattern.These are exactly the same classes as provided in the lecture notes on the visitor pattern.interface Node { }class Number implements Node { class Plus implements Node {int num; Node lhs;Number(int n) { num = n; } Node rhs;void accept(Visitor v) { Plus(Node l, Node r) { lhs = l; rhs = r; }v.visit(this); void accept(Visitor v) {} v.visit(this);} }}As an example, the code for generating the expression (1+2)+3 would beNode x = new Plus(new Plus(new Number(1),new Number(2)),new Number(3));The visitor pattern is handy in such class hierarchies since it allows one to define data separatelyfrom processors of that data. Here is an implementation of a visitor that calculates the result ofan arithmetic expression (notice how intermediate results are stored on the call stack):interface Visitor { class ComputeVisitor implements Visitor {void visit(Number n); int result = 0;void visit(Plus n); void visit(Number n) {} result = n.num;}void visit(Plus p) {int leftresult;p.lhs.accept(this);leftresult = result;p.rhs.accept(this);result = leftresult + result;}}To use this visitor on x and print the result, we could do the followingComputeVisitor v = new ComputeVisitor();x.accept(v);System.out.println(v.result);(next page)5(a) (5 points) What is the purpose of the accept methods in each of the Node classes? Putanother way, why can we not simply write the ComputeVisitor as follows, which ignores theaccept methods and calls visit directly:class ComputeNotAVisitor implements Visitor {int result = 0;void visit(Number n) {result = n.num;}void visit(Plus n) {int leftresult;this.visit(n.lhs);leftresult = result;this.visit(n.rhs);result = leftresult + result;}}(b) (5 points) Give a concrete, substantive difference between a visitor and an iterator (sayingthat one uses accept me thods and the other doesn’t, or making similar sorts of surface-levelobservations, is not sufficient).6(c) (10 points) A “payload” visitor can be used to separate the computation of a visitor fromits traversal. For example, here is a traversal visitor for our original set of Node classes (notincluding Power):class PostTraverseVisitor implements Visitor {Visitor payload;PostTraverseVisitor(Visitor v) { payload = v; }void visit(Number n) {payload.visit(n);}void visit(Plus n) {n.lhs.accept(this);n.rhs.accept(this);payload.visit(n);}}The calls to accept do the traversal, and the calls to payload.visit() do the processing.We can use this approach to implement visitors like ComputeVisitor a bit more generically.For example, using PostTraverseVisitor, we could implement a ComputePayloadVisitorthat results in a visitor equivalent to ComputeVisitor as follows:ComputePayloadVisitor v2 = new ComputePayloadVisitor();Visitor v3 = new PostTraverseVisitor(v2);x.accept(v); // the original ComputeVisitorx.accept(v3); // one composing v2 and v3assertEquals(v.result,v2.getResult()); // they give the same resultProvide your definition of a the payload visitor on the next page. The getResult methodshould return the final re sult (as shown in the c ode snippet above).7class ComputePayloadVisitor implements Visitor {ComputePayloadVisitor() { // empty constructor }void visit(Number n) {}void
View Full Document
Unlocking...