Fictitious implementations revisited

Recall from last time that a fictitious implementation of an interface is a legal implementation that fails to satisfy certain unchecked aspects of the interface's specification. We considered the following interface for stacks, along with the many invariants that are not captured by its type signatures alone:

public interface Stack {
  public Object pop();
  public void push(Object top);
  public boolean isEmpty();
}

Consider, for example, the following rules that we would like any stack implementation to follow:

• If an object o is pushed on a stack s, and the next operation performed on the stack is pop, then the return value of that operation will be o.
  
  
• If, for a given stack s, the return value of s.isEmpty() is true, and the next operation performed on the stack is pop, then that call to pop will throw a RuntimeException.

Despite the Java language's restrictions on the specification of interface invariants, it is possible to specify added invariants of interfaces like these. As we'll see, you can specify these invariants in such a way that you can automatically check to see if an implementation of the interface satisfies them.

Back to top

Assertions

The addition of assertions to a program is an old but good idea that is underused. The idea is to put in boolean checks for certain conditions at various stages in the execution of the program. According to the idea of design by contract, assertions should be included in the agreement the implementation of an interface makes with outside clients. Usually, assertions come in one of three varieties:

• A precondition checks that some condition holds just before entering a code block.
  
  
• A postcondition checks that some condition holds when exiting a code block.
  
  
• An invariant checks that some condition holds during the execution of a code block. Because of their expense, assertions of this category are rarely supported in their most general form. Instead, the programmer is allowed to check that various conditions hold at a certain point in the code block's execution.

In the case of interface specifications, where no implementation code is given, the first two categories are most useful.

With the introduction of Java-based preprocessors such as iContract, it is possible to place assertions into your source code and have them automatically converted into Java code that checks to ensure that the assertions are never violated. Because the assertions processed by these tools are specified as Javadoc comments in the original file, it is easy to compile this file without running the preprocessor, making a "production" copy of the code in which none of the assertions are checked. But assertions are removed in this way too often. In all but the most performance-critical sections of a program, the overhead of assertion checking will not be significant. Leaving assertions in makes it easier to diagnose bug reports from end users (and there will be bug reports).

In our stack example, we could add an assertion to pop that ensures that it is never called on an empty stack:

public interface Stack {
  /**
   *@pre ! this.isEmpty()
   */
  public Object pop();
  public void push(Object top);
  public boolean isEmpty();
}

Adding assertions such as these to the interface code can help ensure that such additional invariants hold when the methods of an implementation are called. Because they can be compiled into the code, they are a powerful way to diagnose the occurrence of fictitious implementations quickly. What's more, they serve as added documentation for the interface. But, because they are strictly functional boolean expressions, they are limited in their expressiveness -- how would we encode our first rule for stacks into an assertion, for instance? Like types, assertions are not expressive enough by themselves to capture all of the rules we may want to specify on an interface. For this reason, they are best used in tandem with unit tests.

Back to top

Unit tests

Another specification that a programmer can provide for an interface is a suite of unit tests. Using a unit testing framework such as JUnit (see Resources), you can easily check that such unit tests hold for any implementation of the interface. The extent to which unit testing can aid in eliminating occurrences of fictitious implementations cannot be overemphasized. In fact, unit tests are an excellent way to provide limited specification of these extra invariants. An interface that comes with an accompanying set of unit tests gives the implementer a means to check that the extra invariants of the interface are satisfied. I highly recommend providing such tests with any interface that will be used by outside clients; they'll thank you for it. Even in-house interfaces will be much easier to implement with an accompanying test suite.

Of course, unlike type declarations, a finite set of tests cannot check an implementation over all possible inputs. But unit tests can be thorough enough that we can reasonably expect them to catch most violations of the invariants. And they are, of course, much more expressive than type signatures.

A suite of unit tests for an interface can also be viewed as a form of documentation for that interface. You can be much more precise in describing invariants in a unit test than you can be in prose. For example, consider the following tests to check our invariants on stacks:

  public void testPushAndPop() {
    Stack s = new MyStack();
    Object o = new Object();
    s.push(o);
    assertTrue(o == s.pop());
  }
  public void testPopOnEmpty() {
    Stack s = new MyStack();
    assertTrue(s.isEmpty());
    try {
      s.pop();
    }
    catch (RuntimeException e) {
      return;
    }
    throw new RuntimeException("pop on empty stack does not fail");
  }

Compare these tests to the invariants for stacks as we originally specified them in English. Unlike the unit tests, these English descriptions leave many things open for interpretation. For example, when the first rule states that "the return value of that operation will be o," does this mean that the return value will satisfy an equals test with the pushed object, or that it will actually satisfy ==? The unit test makes this very clear.

A few more things to notice about these tests:

• They are small and straightforward. Because the unit tests for an interface should also serve as documentation, it is essential that they be as easy to read as possible.
  
  
• Because they can be arbitrary Java code, they allow us to test complex behaviors of an implementation. For example, notice that the second method actually tests that an exception is thrown when it should be; if the exception isn't thrown, the test fails!

The fact that unit tests are so expressive certainly has advantages. It allows us to capture the essence of any rule for an interface that we would want to specify. But this expressiveness also has a disadvantage: we can specify examples of a rule, but, as noted, can't use unit tests to check that a rule holds for all possible inputs to a program.

We can now consider the three languages for the specification of an interface (that is, the unit testing language, the assertion language, and the type system) to form a hierarchy of expressiveness. Each step up in the hierarchy is achieved at the expense of a decrease in the testability of the language. As is often the case, there is a fundamental tension between expressiveness and testability. By incorporating several such specification languages for our interfaces, it is possible to get the best of both worlds.

Back to top

Conclusion

As these examples have shown, assertions and unit tests are powerful ways to avoid fictitious implementations, providing checkable specifications for an interface. What's more, the kinds of invariants that they check are complementary. Ideally, an interface would include both.

Notice that the inclusion of such specifications doesn't just catch errors in completed implementations; it actually helps the would-be implementer to ensure that he is correctly implementing the interface while he is programming. Not only can this improve productivity, but it can also make for happier programmers. It's always nice to send one's code through an automated checking tool -- and watch it pass.

Resources

• Read more about Design by Contract.
  
  
• Clemens Szyperski discusses the distinction between interface and implementation inheritance in his excellent book Component Software: Beyond Object-Oriented Programming.
  
  
• The JUnit home page provides links to many interesting articles discussing program testing methods, as well as the latest version of JUnit.
  
  
• The IBM Redbook WebSphere Version 4 Application Development Handbook explains how to unit test WebSphere applications.
  
  
• Take the Java debugging tutorial (developerWorks, February 2001) for help with general debugging techniques.
  
  
• Read all of Eric's Diagnosing Java Code articles, many of which focus on bug patterns.
  
  
• Find more Java resources on the developerWorks Java technology zone.
  
  

About the author

Rate this article

Comments

Back to top

Table of contents

• Fictitious implementations revisited
• Assertions
• Unit tests
• Conclusion
• Resources
• About the author
• Comments