| 6.170 | Laboratory in Software Engineering
Spring 2004 Problem Set 2: Representation Invariants, Specifications, and Immutable Data Types Due: Thursday, February 19, at 9pm |
Quick links:
Contents:
We recommend that you read the entire problem set before you begin work. Also, note that Problem 5 DOES NOT DEPEND on earlier parts. If you get stuck on earlier parts, you should attempt Problem 5.
To complete this problem set, you will need to know:
Make sure you have followed the instructions on the tools handout relevant to directory setup before you begin development. Furthermore, be sure you have read the problem set procedure handout before you begin.
You can get the source files for problem set 2 by using CVS. Follow
the problem set checkout
instructions and checkout the ps2 module from your
repository.
Your code MUST work on Athena, so if you choose to work on a non-Athena machine, please take a few minutes before submitting your solution to ensure that it runs correctly on Athena. Once everything is in order, read the Problem Set Submission instructions for how to run a final check of your code and turn it in.
Answer the following questions, writing your answers in the file problem1.txt
// Rep Invariant for every RatNum r: ( r.denom >= 0 )
Which method or constructor implementations would have to change? For each changed piece of code, describe the changes informally, and indicate how much more or less complex the result would be (both in terms of code clarity, and also in terms of execution efficiency). Note that the new implementations must still adhere to the given spec; in particular, RatNum.unparse() needs to output fractions in reduced form.
this.numer = numerExpr;
this.denom = denomExpr;
return this;
Give two reasons why the above changes would not meet the specifications of the function.
Read through the provided skeletal implementation of RatPoly.java. The most significant parts of the provided file are the comments describing how you are to use the provided fields to implement this class. The Representation Invariant is an especially important comment to understand, because what invariants you define can have a drastic effect on which implementations will be legal for the methods of RatPoly.
You'll notice that all of the methods that you need to implement
currently have this method body:
throw new RuntimeException("Method is not yet implemented!");
For more about what this means, see Problem Set 1.
Fill in an implementation for the methods in the specification of RatPoly. You may define new private helper methods as you like; we have suggested a few ourselves, complete with specifications, but you are not obligated to use them. (The staff believes that doing so will drastically simplify your implementation, however.)
We have provided a checkRep method in RatPoly that tests whether or not a RatPoly instance violates the representation invariant. We highly recommend you use checkRep in the code you write when implementing the unfinished methods.
We have provided a fairly rigorous test suite in RatPolyTest.java. You can run the given test suite with JUnit as you program and evaluate your progress and the correctness of your code.
The test suite depends heavily on the implementation of the RatPoly.unparse() method; if the test suite claims that all or many of the tests are failing, the source of the problem could be a bug in your implementation of unparse().
We have provided a test suite in RatPolyStackTest.java. You can run the given test suite with JUnit as you program and evaluate your progress and the correctness of your code. Again, the test suite relies heavily on RatPoly.unparse().
To run PolyCalc, type the following command:
athena% cd ~/6.170/workspace/ps2/src athena% java -cp .:$CLASSPATH ps2.PolyCalcFrame
A window will pop up with a stack on the left, a graph display on the right, a text area to input polynomials into, and a set of buttons along the bottom. Click the buttons to input polynomials and to perform manipulations of the polynomials on the stack. The graph display will update on the fly, graphing the top four elements of the stack.
Submit your four favorite polynomial equations, in the RatPoly.unparse format, in the file problem4.txt inside the doc/ directory. Make sure to add the file to CVS and commit it. Follow the Problem Set Submission instructions.
BasicList.
The implementation that is provided to you contains several
implementations errors, where the programmer did not adhere to the
specification. Your task is to create a test driver that isolates
the implementation errors in this class. You are only given the
specification for this class; you are not given the source of the
implentation. You are only given the binary class file so you can use
the BasicList class in your JUnit test driver. Using the Black Box
testing techniques discussed in lecture, you should create test cases
that test that the given implementation satisfies the specification.
The specification for the BasicList class can be found here. Note that this specification is very similar to the ArrayList class that is part of the Java API.
The purpose of this assignment is to create a test driver that tests a given implementation against a given specification. You will need to carefully read the specifications of all methods and constructors for BasicList and construct test cases. Also, you might want to look over the provided JUnit test files from both this problem set and the previous assignment (e.g. RatPolyTest, CardTest).
You will fill in BasicListTest.java,
which is a skeleton for the test driver. Remember to thoroughly test
that ALL public methods and public constructors satisfy the
specification. Finally, in
problem5.txt give a description of all errors you
uncovered in your test driver. Place the file in the doc/ directory
and add and commit it to CVS.
The following classes are all provided for you, in compiled form, by the staff:
(If you have run the 6.170
setup scripts, the compiled code should already be in your classpath;
you can just use the provided classes according to the HTML Documentation specification.)
Think before you code! The polynomial arithmetic functions are not difficult, but if you begin implementation without a specific plan, it is easy to get yourself into a terrible mess.
JUnit is integrated with Eclipse, so you can run the test suite from within the IDE.
RatPoly, you should select RatPolyTest from the
ps2 classes.If you are not using Eclipse, you can invoke JUnit from the command
line. To run the RatPolyTest test suite, type the following
command:
athena% java junit.swingui.TestRunner ps2.RatPolyTest
For a non-graphical alternative method of running JUnit, use junit.textui.TestRunner
instead of junit.swingui.TestRunner.
Remember that in order for this to work, ps2-lib.jar,
junit.jar and the directory containing your class files
must all be in the Java VM's classpath (i.e. part of the CLASSPATH
environment variable or you may need to explicity use the
-classpath parameter for the Java VM).
@requires vec != null && sorted(vec) && newTerm.coeff != ZERO && newTerm.expt >= 0
Note that strengthening the precondition actually weakens a specification. Make sure you understand why (Hint: think about substitutability).
ps2-lib.jar file. The CVS update
will not overwrite any code you have written, nor does it change any
of the specifications in the problem set. ps2-lib.jar is
checked out to ps2/lib/This section will list clarifications and answers to common questions about problem sets. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully rereading the problem set handout and the specifications) when you have a problem.