The problem of understanding code written by others is ever-present. Automated assistance would be a valuable achievement for large real-world programs. However, finding a solution takes at least two steps. The problem must first be correctly formulated--not a trivial undertaking. As a second step, a method of solution must be found.

The problem of program understanding that Woods, Quilici, and Yang attempt to solve is presented in chapter 1. In chapter 2, they present some attempts to solve this problem using the idea of program plans. The first two attempts are based on abstract syntax trees and the last two are based on graph theory. The authors assert that none of these approaches scale to practical problems.

All of the solutions use constraints, however. This suggests another approach--treating the problem of deriving plans as a constraint satisfaction problem. In chapter 3, the problem is broken into two steps, namely plan matching and plan ordering. Drawing on previous graph theory, algorithms are proposed. The problem is NP-hard, so attention is switched to finding suitable heuristics for the problem--the second step of the problem.

Chapter 4 records the results of experiments using the heuristics on artificial programs. Chapter 5 extends the results to real programs. These latter experiments suggest that actual time taken to search for a particular plan is polynomial for constraints evaluated versus program size when the plan size is small. This sets the scene for an appreciation that searching for something small is much easier than searching for something large because the combinatorial explosion slows the solution. Thus, if the something large is a gross plan, it can be attacked much more conveniently if the gross plan is hierarchical. By starting at the bottom of the hierarchy, small plans that are building blocks for the gross plan can be recognized.

However, the plan recognized as the gross plan must be exact. As a result, standard AI approaches must be modified. Chapter 6 covers these issues in general, and chapter 7 applies them to the authors’ algorithm. Chapter 8 provides a summary and a tempting list of open questions.

The book is aimed at a fairly selective audience of advanced undergraduate or graduate students; researchers in software engineering, reverse engineering, or reengineering; or possibly AI people wanting a fresh approach. However, I could see myself using it as a text in a course on the epistemology of computing. It is not difficult to understand, yet it clearly shows the social effects of a subdiscipline group on theory and experimentation.