School of Engineering and Applied Science
Department of Computer Science
CSci 133 -- Algorithms and Data Structures I
http://www.seas.gwu.edu/~csci133/fall03
Prof. Michael B. Feldman
mfeldman@gwu.edu

Incremental ADT Development Using Stubs
January 2003

Background

Often, a software developer is called upon to develop an abstract data type (ADT), or similar reusable software component. In Java such components are called classes; other common terms are modules (Modula-2/3), units (Turbo Pascal) or packages (Ada). Intermediate computer science courses therefore often assign projects that require the development of such components. In this note we'll discuss a tried-and-proven technique called incremental development; we'll use Java syntax and terminology, but the technique is entirely language-independent.

An ADT class will normally contain some variables and constants -- which normally are private -- and provide public (and possibly some private) methods. These allow a client program to instantiate (declare) and initialize objects of the class, and to manipulate objects in various ways. Suppose the class provides a way to build a collection of data -- a table or list of data elements in some form. The methods will then allow adding an element to the collection, deleting an element from it, finding and modifying an element in certain ways, and so forth. Generally, at least one operation is provided to traverse,or iterate over the structure, "visiting" each element exactly once, and doing something with each element's value as it is visited. In the Java community, such an iterator is often called toString, and it builds a single string containing the concatenation of all the elements in the collection, in their corect sequence.

Incremental development

In a common type of project assignment, you get a complete specification or interfacefor a component, in ordinary prose, pseudo-code, or (sometimes) in actual, compilable form. For this note, let's assume you're given a compilable Java class file (".java file") for the desired component, and your job is to implement and and test the class. How should you go about this?

Many students seem to assume they're required to develop and test the entire class all at once. This looks like an overwhelming task, and, for beginners, it is! You try to do it; you get overwhelmed; you panic; you make mistakes; you miss the deadline.

The basic assumption is incorrect. It is not necessary to develop the whole class at once! Indeed, it is undesirable to do so, and professional developers generally do not do so.

It is better -- and usually takes less of your time overall -- to develop incrementally.To do this, you build, and thoroughly test, only one or a few methods at a time. Limiting your work to just a few key methods ensures that you really understand those methods. Once that small set of methods passes your tests for them, you add an method or two to the class, then extend your test program to handle the new operations. If something goes wrong in the tests, it's probably in the methods you just added. It's also possible that executing the new methods "breaks" something in the old methods, so you must be careful to keep testing the old ones.

You continue to develop in stages, until, eventually, the entire class is completed. A nice aspect of this is that if you reach the deadline with an incomplete class, at least you can turn in a partial result that works. There may be missing features, but a partial submission is far better than none at all! (This also happens, frequently, in industry!)

Using stubs to facilitate incremental development

Using stubs allows the overall class to be partially tested without requiring that all methods be fully coded. A stub is simply a “framework” for a method. All we require of a stub is that it be legally compilable and executable. Generally this means that a stub must either A stub for a void method can simply do nothing; no executable statements are even necessary. A stub for a value-returning method must contain a valid return statement; if it doesn't, the compiler will reject it. So include a "fake" return statement that returns a legal but meaningless value: 0 or MIN_VALUE for an integer, false for a boolean, " " for a string, etc.

Let's assume you start with a correct and compilable Java source file for the class. Here's how to proceed:

  1. Compile the file to make sure it will compile. If you get compilation errors, correct them immediately.
  2. Add the data declarations (these should always always be private), then compile. Correct any compilation errors
  3. Add stubs for all the methods, then compile and correct errors.
  4. Develop and test a few methods by replacing the stubs will full method bodies, then add and test a few at a time, until all operations are completed.
In your stubs, consider putting a temporary output statement that gives the name of the stub and the message "under construction" (as we often see on the web). That way, calling that operation will result in a predictable message. When you complete each stub, you can change the message to indicate that the stub was called. Once the package is debugged, you can remove all these extra messages.

Deciding which operations to implement

Start with a minimal set of operations. The details here will vary with the type of package, of course. As an example, let's say the package provides a "collection" type, as described above. At a minimum, you'll need to write Start with these two. In your test, first display the result of a toString activation, to make sure an empty collection is displayed properly. Then call add several times; after each add, activate toString and display its result, to ensure the addition was done correctly (and also that toString is working properly for all cases). Since the unimplemented operations are legally stubbed, your package will always be compilable.

By the time this is done, you have a pretty good understanding of how the operations are supposed to work, so you can start adding operations incrementally. At each stage, don't add a new operation until you're sure the current ones are correct!

This process may look time-consuming, but decades of university and industry experience shows that using this technique will almost always save your time. Try it!

(end of article)