SUNY Geneseo, Department of Computer Science

Lab 10

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, November 5

Purpose

Background

Such tools as pre- and postconditions, induction, etc. are usually treated as ways of specifying precisely what an algorithm should do and of verifying that it does it. However, they can also be good guides to debugging a program.

The most obvious example is postconditions -- they are generally taken as specifications for what an algorithm is supposed to produce, so any algorithm that runs without producing its postconditions (assuming that its preconditions were met) must contain a bug. This alone can help you isolate a bug in a large program, if you can step through it and determine exactly which statement or message fails to establish its advertised postconditions. That statement, or the method invoked by that message, must be a place where a bug lies.

Preconditions can help you identify bugs too. Preconditions are conditions that must hold before sending a message, so if you can find code that sends some message without the preconditions for that message holding, there is by definition a bug in the code leading up to the message. Note that quite possibly the message will produce an incorrect result in this situation, and so checking the preconditions can help you "assign blame" -- determine whether the method that handles the message is responsible for the error, or whether the client that sent the message is.

Correctness proofs in general can also be helpful, since a correctness proof should be a careful, fairly detailed, exposition of the conditions that hold at various points in an algorithm. If you have a correctness proof for an algorithm in mind as you step through it, you can compare the conditions that actually hold at each point in the program to those that the proof says need to hold -- the place where the two first differ is probably where the first bug lies.

All of the above ideas have some special overtones when used with recursive algorithms. For example, sometimes a recursive algorithm will produce incorrect results only from its base case, or only from its recursive case -- but it may not be obvious from outside the algorithm which is which, because an incorrect result returned to a client may be due to a bug in a recursive case, or it may just be due to correct recursive cases working with incorrect results from the base cases. In other words, recursive cases will usually look incorrect even if the blame really lies with the base case. Testing the algorithm on data that cause it to execute only its base case, and noting whether the base case establishes the right postconditions, can help you determine whether the bug is in the base case or not. Comparing what the algorithm's base case does to what the base case in the correctness proof says it should do can also help. Similarly, the correctness proof can provide a lot of guidance in what to look for in the algorithm's recursive cases -- do recursive invocations correspond to the conditions assumed in the proof's induction hypothesis? Do conditions deduced in the proof really hold in the program? etc. Finally, because a recursive algorithm is its own client, many bugs arise from not establishing preconditions prior to a recursive message. So checking preconditions carefully before each recursion can help you discover bugs.

Exercise

I have written a Java class named BuggyList, which is a subclass of List. BuggyList provides a collection of new messages for lists, the most important of which are

bringToFront

A message that takes an integer, i, as its parameter, and returns a list that contains the same items as the original, except that the item that was in the i-th position is now at the head of the list.

bubble

A parameterless message that returns a list that contains the same items as the original, except that the largest has moved to the end of the list (i.e., it has floated up like a bubble, thus the name of the message).

isOrdered

A parameterless message that returns true if all the items in a list are in ascending order (i.e., the first item is smaller than the second, which is smaller than the third, and so on), and false if the list is not in ascending order.

Unfortunately, none of my methods for these messages work. Your job is to find the bugs and correct them.

My BuggyList class includes a main method that exercises each of the buggy methods. All the bugs show themselves in the tests that main does. However, once you think you have corrected a bug, you should test your correction on data beyond that already used by main, because an incorrect fix can make the symptoms of a bug go away in some tests without completely fixing the bug. You can use any of the sample list files that you used in Lab 9 ("AnimalList", "ColorList", or "EmptyList") to test BuggyList. I have also put a fourth sample list file that you can use, named "InstrumentList", on the "Course Materials" server.

As far as I know, there is only one bug in each of the above methods.

BuggyList also defines a handful of other methods not listed above. These methods should be familiar to you from Lab 9 -- they include constructors for BuggyList objects, including one that copies a regular list into a BuggyList, etc. To the best of my knowledge, none of these other methods contain bugs.

You can get BuggyList in the file named "BuggyList.java" in our course folder on the "Course Materials" file server, or you can Download It from the Web (http://www.cs.geneseo.edu/~baldwin/csci141/fall2003/BuggyList.java).

As distributed from these sources, BuggyList's main method reads a list from the file "InstrumentList", and exercises each of the buggy methods on that list. In order for main to be able to read the list, you should put a copy of "InstrumentList" in whatever directory will be the working directory when your BuggyList program runs (the project's "build" folder if you use Project Builder). Alternatively, you can edit the argument to the restore message near the beginning of main to be a full path name to "InstrumentList".

Follow-Up