The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I

Incremental ADT Development Using Stubs

Background

Often, a software developer is called upon to develop an abstract data type (ADT), or similar reusable software component. In Ada such components are called packages; other common terms are modules, units or classes. 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 Ada syntax and terminology, but the technique is entirely language-independent.

An ADT package will normally provide a data structure type and a set of operations (sometimes called methods). The type allows a client program to declare variables or objects of the type; the operations allow a client to manipulate objects in various ways. Suppose the type provides a way to create a collection of data -- a table or list of data elements in some form. The operations 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 the structure, "visiting" each element exactly once, and displaying each element's value as it is visited.

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 Ada package interface (".ads file") for the desired component, and your job is to develop and test the implementation, in the form of a package body (".adb file"). How should you go about this?

Many students seem to assume they're required to develop and test the entire package 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 package 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 operations at a time. Limiting your work to just a few key operations ensures that you really understand those operations. Once that small set of operations passes your tests for them, you add an operation or two to the package, then extend your test program to handle the new operations. If something goes wrong in the tests, it's probably in the operations you just added. It's also possible that executing the new operations "breaks" something in the old operations, so you must be careful to keep testing the old ones.

You continue to develop in stages, until, eventually, the entire package is completed. A nice aspect of this is that if you reach the deadline with an incomplete package, 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 package to be partially tested without requiring that all operations be fully coded. A stub is simply a “framework” for an operation. All we require of a stub is that it be legally compilable and executable. Generally this means that a stub must either For example, look in the data structures book at Program 2.2, the body for a rational-number package. The "-" and ">" operations are shown as stubs. The first operation returns a known rational value as its result; the second always returns True.

FUNCTION "-"(R1 : Rational; R2 : Rational) RETURN Rational IS
BEGIN -- stub
  RETURN 1/1;
END "-";

FUNCTION ">" (R1 : Rational; R2 : Rational) RETURN Boolean IS
BEGIN -- stub
  RETURN True;
END ">";

Let's assume you start with correct and compilable package specification. Here's how to proceed:

  1. Compile the spec to make sure it will compile. If you get compilation errors, correct them immediately.
  2. Copy the spec into a new file, with a file name corresponding to the package body.
  3. Edit this package body to make it compilable as a body. Delete any type declarations; delete the PRIVATE part, if any. Add stubs for all the operations.
  4. Develop and test a few operations by replacing the stubs will full subprogram 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 call Display to make sure an empty collection is displayed properly. Then call  Insert several times; after each Insert, call Display to ensure the insertion was done correctly (and also that Display 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!