Michael Bolin's 6.170 Recitation |
www.bolinfest.com |
9/16 Recitation 2 - Writing Specifications is Hard
1. SpecfieldsIn lecture, Professor Jackson mentioned specfields. A specfield is a reference to an abstract field of a data type. For example, consider an abstract data type (ADT) that represents a bank account. Some of the fields, or properties, of the bank account that we would want to keep track of could be the name of the person who owns the account, the amount of money in the account, and the transaction history for the account. We would represent this in our code as follows:/** * <Class Overview Goes Here> * * @specfield name : string // name of account owner * @specfield balance : decimal // balance of account, in US dollars * @specfield transactions : sequence // history of transactions, most recent listed first * @derivedfield numTrans : number // number of transactions made */ public interface Account { /** * @requires this.balance is at least $10 * * @modifies this.balance, this.transactions, a.balance, a.transactions * * @effects decreases this.balance by $10, * increases a.balance by $10, * adds a transaction to both this.transactions and a.transactions * * @throws NotEnoughMoneyException if this.balance is less than $10. * No transaction occurs if this exception is thrown. */ public void transferTenBucksTo(Account a); }Let's explore this notation in greater detail:
@specfield and @derivedfield tags are not part of
Sun's standard set of Javadoc tags; however, they are recognized by our 6.170
doclet which is used when you use the supplied Ant task for generating Javadoc
that we gave you in Problem Set 0.
2. 6.170 Javadoc TagsIn 6.170, we use the following tags in our method specifications. Note that@throws is the only 6.170 tag that is also one
of the Sun Javadoc tags. Sun also provides a @return tag
which is unreasonably close to the 6.170 @returns tag.
We use the @returns tag in 6.170 to be consistent with the
Liskov textbook.
@modifies and @effects
tags since they seem to contain the same information.
One advantage that the @modifies tag provides is that it allows us to
write software that can reason about our program by parsing the contents of the
@modifies tag to determine what could be affected by invoking the method.
Some programming languages, such as Eiffel,
explore this idea in more detail.
As the title of this lesson mentions, writing specifications is hard.
Thus, you may have trouble making your specification to fit into
these five tags. If you find yourself in this situation, do not hesitate
to add text before these tags in your specification.
It is more important that your specification be complete rather than it
fit perfectly into our documentation scheme.
This does not mean that you should ignore these tags and write your specifications
completely in prose. Using this scheme allows clients of your specification
to extract information from it quickly and easily.
3. Strong Versus Weak SpecificationsA strong specification is one that is tolerant on inputs and demanding on outputs whereas a weak specification is one that is demanding on inputs and weak on outputs. In 6.170, we want to produce strong specifications as they are more useful for the clients of our specifications. For example, consider the following three specifications ofdouble sqrt(double x) :
CacheStrategy will be strictly stronger than your specification
for Cache . If this is the case, then you can be sure
that a CacheStrategy can be used wherever a Cache is needed
because it has a stronger specification.
4. Blackbox Versus Glassbox ExampleBlackbox Testing is when you test a module through its specification alone. A good blackbox test should cover the entire domain of inputs as well as boundary conditions.Glassbox Testing is when you test a module's internal program structure. With a glassbox test, you should test different flows of control through the program as well as subdomains that may not have been discoverable from the specification alone. Let's look at how we would test the example below. Recently, I had to augment a jabber chat client so that it would keep track of the ten messages that you sent most frequently. Thus, I needed to create a data structure that would keep track of the frequency of everything that I sent, but that could also return the top 10 mostly frequent messages quickly. Thus, I decided upon the following interface. From its specification, you might consider creating a blackbox test that would check the following:
/** * Keeps track of each sentence that has been sent and * can return the 10 sentences that have been used most often. */ public interface TopTen { /** * Records that the sentence has been sent. * @param sentence the sentence sent, ignored if null */ public void recordSentenceSent(String sentence); /** * @returns an array of length 10 with the sentences * ordered from most frequent to least frequent * If fewer than 10 phrases have been used, the empty * spaces in the array are null * If two sentences have the same frequency, then the one * that was used more recently is listed first. */ public String[] getTopTen(); }If you read the implementation of TopTenImpl carefully, you will see that it keeps track of the minimum frequency required to be in the top 10. Thus, the top 10 only gets resorted when a sentence that exceeds this minimum is added. This is better than an implementation that stores every sentence in a list and resorts it every time a new sentence is added to the ADT because such an implementation would be more expensive in space as well as time. In that scenario, each sentence would have to be wrapped by an object that paired it with its frequency, and then this object would implement Comparable so it could be sorted using Java's collections. But such an implementation would be unlikely to have the boundary case that TopTenImpl has at 10 elements. With this implementation, it is important to test what happens when the size of the Map is 9, 10, and 11. We must ensure that the top 10 is updated correctly when elements get swapped in and out of it. Further, consider the case where there are only 11 sentences that get added to this ADT in this situation, TopTen will be doing its maximum computation for each call to recordSentenceSent. These details are only revealed by looking at the implementation of TopTenImpl. Thus, a blackbox test for TopTenImpl may not have caught bugs (if there were any :) that occurred with 9, 10, or 11 elements. Be sure to consider glassbox as well as blackbox tests when designing your own test suites. At the bottom of TopTenImpl, you will can see the (non-rigorous) tests that I ran to convince myself that TopTenImpl worked as advertised. /** * An ADT that implements TopTen in Java */ import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class TopTenImpl implements TopTen { /* * This ADT works by storing the frequency for each * sentence in a Map and by keeping track of the * frequency of the 10th member of the top 10. * Thus, the top 10 is only sorted when the frequency * of a sentence meets the value of minFreq. */ /** the size of the top 10: should be 10, but can be changed here */ protected static final int SIZE = 10; /** maps a sentence(String) to its frequency of use (Integer) */ private Map/*<String,Integer>*/ sentMap = new HashMap(); /** the current top 10 */ private List topTen = new ArrayList(); /** the frequency to meet to be in the top 10 */ private int minFreq = 0; /** * Records that the sentence has been sent. * @param sentence the sentence sent, ignored if null */ public void recordSentenceSent(String sentence) { if (sentence == null) return; int freq = 1; Object val = sentMap.get(sentence); if (val != null) freq = ((Integer)val).intValue() + 1; sentMap.put(sentence, new Integer(freq)); // if does not exceed minFreq, then does not belong in top 10 if (freq < minFreq) return; // starts searching at index for placement in top 10 int index = topTen.indexOf(sentence); if (index >= 0) { topTen.remove(sentence); } else { index = topTen.size(); } // traverse top 10 until higher freq is found or beginning of list reached while (index > 0) { String phraseAhead = (String)topTen.get(index - 1); int otherFreq = ((Integer)sentMap.get(phraseAhead)).intValue(); if (freq < otherFreq) break; index--; } // add sentence at new position in top 10 topTen.add(index, sentence); int ttSize = topTen.size(); // remove 11th member, if applicable if (ttSize > SIZE) { topTen.remove(SIZE); ttSize--; } // update the minimum frequency required to be in the top 10 if (ttSize == SIZE) { minFreq = ((Integer)sentMap.get(topTen.get(ttSize - 1))).intValue(); } else { minFreq = 0; } } /** * @returns an array of length 10 with the sentences * ordered from most frequent to least frequent * If fewer than 10 phrases have been used, the empty * spaces in the array are null * If two sentences have the same frequency, then the one * that was used more recently is listed first. */ public String[] getTopTen() { String[] tt = new String[SIZE]; tt = (String[])topTen.toArray(tt); return tt; } /** returns the non-null members of the top 10 */ public String toString() { return topTen.toString(); } /** used for testing */ public static void main(String[] argv) { // test to make sure frequency rules are preserved TopTen t1 = new TopTenImpl(); String[] strings1 = { "foo", // foo (1) "foo", // foo (2) "foo", // foo (3) "bar", // foo (3), bar (1) "bar", // foo (3), bar (2) "foo", // foo (4), bar (2) "bar", // foo (4), bar (3) "bar", // bar (4), foo (4) "bar", // bar (5), foo (4) "foo" // foo (5), bar (5) }; TopTenImpl.addAndPrint(strings1, t1); // test to make sure works past 10 args TopTen t2 = new TopTenImpl(); String[] strings2 = { "one", // 1 "two", // 2, 1 "three", // 3, 2, 1 "four", // 4, 3, 2, 1 "five", // 5, 4, 3, 2, 1 "six", // 6, 5, 4, 3, 2, 1 "seven", // 7, 6, 5, 4, 3, 2, 1 "eight", // 8, 7, 6, 5, 4, 3, 2, 1 "nine", // 9, 8, 7, 6, 5, 4, 3, 2, 1 "ten", // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 "one", // 1, 10, 9, 8, 7, 6, 5, 4, 3, 2 "two", // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3 "two", // 2, 1, 10, 9, 8, 7, 6, 5, 4, 3 "eleven", // 2, 1, 11, 10, 9, 8, 7, 6, 5, 4 "eleven", // 2, 11, 1, 10, 9, 8, 7, 6, 5, 4 "eleven" // 11, 2, 1, 10, 9, 8, 7, 6, 5, 4 }; TopTenImpl.addAndPrint(strings2, t2); } /** adds strings to t and prints intermediate top 10 lists */ private static void addAndPrint(String[] strings, TopTen t) { for (int i = 0; i < strings.length; i++) { t.recordSentenceSent(strings[i]); System.out.println(t.toString()); } } } 5. Quick Notes About Java CollectionsJava has a number of classes for common data structures. These classes are in the java.util package and are collectively referred to as the Java Collections Library. Here are some of the commonly used data types:
Object ,
in practice, they often hold a more specific datatype.
For example, if you had a class called Deck that represented
a sequence of Card objects, you might store them internally as a List .
Thus, you might have something like this:
import java.util.ArrayList; import java.util.List; public class Deck { private List/*<Card>*/ cards = new ArrayList(); public void addCard(Card c) { if (c != null) cards.add(c); } public Card drawTopCard() { if (c.size() > 0) return (Card)cards.remove(0); return null; } }As you can see, even though we are only putting Card objects into cards ,
we have to cast everything as a Card when we remove it from the list.
This is tedious for the programmer, adds overhead at runtime, and it is error-prone
because a programmer may accidenally write:
return (Deck)cards.remove(0);but will not discover the error until runtime. Simiarly, there is nothing preventing the programmer from adding something other than a Card to cards. Again, this error will probably
not be detected until the non-Card is removed from the list and is cast as a Card ,
generating a ClassCastException .
The solution to this problem is generics which is a feature that is available in Java 1.5.
In Java 1.5, you would write:
List<Card> cards = new ArrayList<Card>(); Object obj = new Object(); cards.add(obj); // this would not compile in Java 1.5 cards.add(new Card()); Card c = cards.remove(0); // this would not require a cast in Java 1.5This adds more compile-time type-checking, reducing programmer errors, and eliminates runtime casts, making Java run faster. Unfortunately, Sun hasn't worked all the bugs out of Java 1.5 yet, so we have to write things like the following in the meantime: private List/*<Card>*/ cards = new ArrayList();This makes your code ready for Java 1.5 all you have to do is remove the comments once you migrate your code from version 1.4 to 1.5. This also has the advantage of providing a succinct comment describing the contents of the data structure. Also, as a general Java rule, refer to an object through its interface rather than by its class name whenever possible. This allows you to change the class that implements the interface at a later date. This is not as unlikely as it sounds. For example, you may start out by using a HashMap when you need a Map ,
but then you may need to replace it with a Hashtable
if you are using an application where thread-safety is important.
|
©2004 Michael Bolin | www.bolinfest.com |