9/16 Recitation 2 - Writing Specifications is Hard

1. Specfields
2. 6.170 Javadoc Tags
3. Strong Versus Weak Specifications
4. Blackbox Versus Glassbox Example
5. Some Quick Notes About Java Collections

1. Specfields

/**
 * <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);

}

• Note that the specfields appear in the public Javadoc. Thus, they are part of the published specification for the code.
• The types of the specfields are listed as types that are not Java types. This is to make these fields more abstract and to decouple the internal representation of the data from the public specification. For example, one implementor may represent balance as a Double; however, a more astute Java programmer would use BigDecimal for better precision. Representing the types of the specfields in an abstract way allows for either implementation.

• Note that numTrans is referred to as a derivedField rather than a specfield. This is because its value can be derived from the other specfields, suggesting that this value should not be stored directly in the ADT, but rather it should be derived from other fields when accessed. Depending on how often the derivedfield is accessed and how much effort is required to calculate it, this is usually the case as doing so reduces the amount of information that needs to be stored and therefore reduces the chance of the ADT reaching an inconsistent state.

• By declaring specfields at the top of the class (by specfields, we are referring to the collective @specfield and @derivedfield members), we can use them to talk about the ADT in the specifications for methods such as transferTenBucksTo().

2. 6.170 Javadoc Tags

Precondition	@requires	determines the conditions under which the method may be invoked
Frame Condition	@modifies	a list of specfields identifying what might be modified by the method
Postcondition	@returns	describes the value that gets returned, if any
	@throws	each of these lists an exception and the conditions under which it will be thrown
	@effects	any side effects that may result from invoking the method

You may wonder why we have separate the @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 Specifications

A	@requires x >= 0 @return y such that |y^2 - x| <= 1
B	@return y such that |y^2 - x| <= 1 @throws IllegalArgumentException if x < 0
C	@requires x >= 0 @return y such that |y^2 - x| <= 0.1

We can make the following comparisons between specifications:

• B is a stronger specification than A because it requires less than A does.
• A is a weaker specification than C because it promises less than A does.
• B and C are incomparable because neither is strictly stronger nor weaker than the other.

4. Blackbox Versus Glassbox Example

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:

• null sentences get ignored
• the length of the array returned by getTopTen is always 10
• the empty spaces in the string array are null
• the elements in the array are the top 10 messages sent
• the elements in the array are sorted from most frequently sent to least
• if two elements have the same frequency, the one sent more recently comes first

TopTen.java:

/**
 * 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();

}

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.

TopTenImpl.java:

/**
 * 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 Collections

Interface	Commonly Used Implementation	Description
Map	HashMap (unsynchronized) Hashtable (synchronized)	maps keys to values
List	ArrayList (unsynchronized) Vector (synchronized)	a sequence of values (may contain duplicate values)
Set	HashSet	a collection with no duplicates

Although these data structures can hold anything that extends 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;
  }

}

return (Deck)cards.remove(0);

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.5

private List/*<Card>*/ cards = new ArrayList();

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.