The Design Checklist: A Method for Designing Abstractions

Norman Ramsey
Fall 2012

When faced with a difficult engineering problem or homework assignment, you may find that you don't know how to get started, or you get stuck trying to get your program to work. In these situations, it is helpful to have systematic methods to fall back on. This handout describes a method developed at Rice University and tested at over 20 universities around the world. I have adapted the method for use in COMP 40.

A wise man once said that we don't need to use systematic methods on every problem, just on problems that are hard. An even wiser man said that it is sometimes useful to practice systematic methods on easy problems, so that when confronted with a hard problem, you can focus on the problem, not the method.

The design checklist for abstract data types

If you have difficulty designing an abstract data type, please complete the following checklist. If completing the checklist does not get you unstuck, take your completed checklist to a member of the course staff and ask for help. Similarly, if you find yourself unable to complete the checklist, ask for help. The course staff will not answer substantive questions for students without checklists.

  1. [*] What is the abstract thing you are trying to represent? Often the answer will be in terms of sets, sequences, finite maps, and/or objects in the world. Always the answer is client-oriented.
  2. What functions will you offer, and what are the contracts those functions must meet?
  3. What examples do you have of what the functions are supposed to do?
  4. What representation will you use, and what invariants will it satisfy? (This question is especially important to answer precisely.)
  5. How does an object in your representation correspond to an object in the world of ideas? That is, what is the inverse mapping from any particular representation to the abstraction that it represents. This question is also especially important to answer precisely.)
  6. What test cases have you devised?
  7. What programming idioms will you need?

A detailed example

Let's suppose you've decided to implement an abstraction that maintains a set of future events with a time for each event, and you want to efficiently find the next event that is scheduled to occur. Here's the checklist:

  1. What is the abstract thing you are trying to represent?

    A set of events, each of which has a time. We'll call it an event queue, or eventq in C.

  2. What functions will you offer, and what are the contracts of that those functions must meet?

    We'll want these functions:

    These functions and contracts make it clear that eventq is a mutable abstraction.

  3. What examples do you have of what the functions are supposed to do?
  4. What representation will you use, and what invariants will it satisfy?

    I'll use a binary heap, which is either

  5. How does an object in your representation correspond to an object in the world of ideas? You will usually answer by refering to components of your data structure and explaining how a particular collection of values for those components correspond to an element of the abstraction you are implementing.
  6. What test cases have you devised?

    Test cases are left as an exercise for the reader. [This phrase sounds academically respectable, but unless the exercise is carefully crafted, it's really just a way of dodging work. I'm~dodging work.]

  7. What programming idioms will you need?