Laboratory Exercise

Debugging

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Purpose

This exercise teaches students how formal tools for describing and analyzing algorithms’ correctness also help one debug concrete programs.

Prerequisites

Familiarity with the simulated robot described in chapter 2 of Algorithms and Data Structures: The Science of Computing.

Understanding of recursion, as described in chapter 6 of Algorithms and Data Structures: The Science of Computing.

Understanding of the notion of a correctness proof for an algorithm, particularly inductive proofs for recursive algorithms, and the roles of preconditions and postconditions in such proofs. Chapter 3 and section 7.1.2 of Algorithms and Data Structures: The Science of Computing deal with these ideas.

Background

This lab asks students to find and correct bugs in a subclass of the robot from chapter 2 of Algorithms and Data Structures: The Science of Computing. The lab encourages students to use the formal tools of correctness — preconditions, postconditions, and proofs — to help find and fix bugs. These tools are usually treated as ways of specifying precisely what an algorithm should do and of verifying that it does it, but they are also valuable in debugging a program.

Postconditions

Postconditions are generally taken as specifications for what an algorithm is supposed to produce, so any algorithm that executes without producing its postconditions (assuming that its preconditions were met) must contain a bug. This idea alone can help isolate bugs in a large program: step through the program and identify statements or messages whose preconditions hold, but that fail to establish their advertised postconditions. Such statements, or the methods invoked by such messages, must be places where bugs lie.

Preconditions

Preconditions are conditions that must hold before sending a message. Therefore, any code that sends some message without the preconditions for that message holding is by definition incorrect. The bug must lie in the code leading up to the sending of the message.

Violated preconditions will probably cause a message to produce an incorrect result, just as if the method that handled the message were incorrect. Checking preconditions helps determine where the problem really lies — if preconditions hold but a message produces an incorrect result, then the method that handles the message is to blame, but if the preconditions don’t hold then the client that sends the message is to blame.

Proofs

Correctness proofs offer general frameworks for debugging. A correctness proof should include a careful, detailed, exposition of the conditions that hold at various points in an algorithm. Comparing conditions that actually hold at each point in a program to those that a proof says need to hold can uncover bugs. In particular, the place where actual conditions and required ones first differ is probably where the first bug lies.

Debugging Recursion

All of the above ideas have some special implications 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 received by a client may be due to a bug in a recursive case, or it may 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 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 establish the conditions assumed in the proof’s induction hypothesis? Do conditions deduced in the proof really hold in the program?

A recursive algorithm is its own client, so many bugs arise from not establishing preconditions prior to a recursive message, or misunderstanding postconditions produced by a recursive message. Carefully checking preconditions before each recursion, and postconditions afterwards, can uncover many bugs.

Exercise

A BuggyRobot subclass of Robot contains a collection of methods that don’t quite work. Find and correct the bug(s) in each method.

The BuggyRobot class is defined in file BuggyRobot.java. The class contains a main method that tests the other methods fairly thoroughly. Creating a complete program that tests BuggyRobot thus only requires compiling and linking BuggyRobot.java with the files that define the robot and its rooms (Robot.java and RobotRoom.java). The main class for this program will be BuggyRobot. The “Final Details” section of this document explains where to find BuggyRobot.java and the other robot files.

Comments inside BuggyRobot.java explain to some extent what each method does and how it works. These comments concentrate on preconditions and postconditions rather than the detailed logic inside each method, however, since that detailed logic is evidently flawed to begin with.

plusSign

This is a parameterless message that makes a robot draw a red “plus” sign against a yellow background, like this:

The preconditions for this message are that the robot is standing on the upper left tile of what will be the background region, facing to the right, and there are no obstructions in the five-by-five tile area that the figure will occupy.

Postconditions for this message are that the figure has been drawn and the robot is standing on its lower right tile.

pointyShape

This message makes a robot draw a pair of blue lines, n tiles long, with a one-tile point at the end between the lines. n is an integer parameter to the message. For example, here is the shape that should be drawn when n = 3:

The preconditions for this message are that n => 0, and the robot is standing on what will be the first tile (the one furthest from the point) of the upper or lefthand line, facing towards the end that will have the point (e.g., the robot would start in the lower left corner of the picture above, facing up). Furthermore, there are no obstructions on the tiles that will be colored, or on the tiles adjacent to the point.

Postconditions for this message are that the pointy shape has been drawn, and the robot is standing on the tile furthest from the point on the lower or righthand line, facing away from the point.

tree

This message causes a robot to draw a green “robot tree,” where “robot tree” is defined as follows:

In the definition of “robot tree,” recall that “floor” is a mathematical operator that rounds its argument down to the nearest integer if the argument is not an integer to begin with.

The preconditions for this message are that n >= 1, and the robot is standing at the base of the future trunk (i.e., the end of the trunk opposite the fork), facing towards the fork. Furthermore, there are no obstructions on the tiles that will be covered by or adjacent to the tree.

Postconditions for this message are that the tree has been drawn, and the robot is standing at the base of the trunk, facing away from the fork.

freeSpace

This message returns the total number of unobstructed tiles a robot can reach by moving forward or backward, including the tile the robot starts on.

The message’s postconditions are that the returned value is the number of tiles the robot can reach by moving forward or backward from its initial tile, including that initial tile, and that the robot is standing on the initial tile, facing in its original direction.

Final Details

The BuggyRobot Class

A copy of BuggyRobot.java is available on the Web. As mentioned above, documentation for BuggyRobot is in comments in this file.

The Robot.java and RobotRoom.java files that BuggyRobot needs are also available from the Web, as is their Documentation. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.