The art and science of C(C语言的科学和艺术)－源代码

Loop Exits and Structured Programming: Reopening the Debate Eric S. Roberts Department of Computer Science Stanford University NOTE This paper has been submitted to the Twenty-sixth SIGCSE Technical Symposium on Computer Science Education. Copyright is retained by the authors prior to publication release. ABSTRACT Internal exits from loops represent a critically important control structure that should be taught in the introductory CS1 curriculum. Without access to those facilities, students are often incapable of solving simple programming problems that occur frequently in applications. This paper reviews the existing evidence in support of such facilities and argues that it is important to reconsider our traditional pedagogical approach as we adopt new languages of instruction. 1. INTRODUCTION Twenty-five years ago, a fierce debate raged within the computer science community over the issue of structured programming. At its essence, structured programming represents a disciplined approach to software development based on abstraction, stepwise refinement, and a formal approach to program correctness [Dahl72]. Unfortunately, as the debate progressed, attention was focused less on the general issues raised by structured programming than on a relatively small detail: whether or not it is ever appropriate to use the goto statement in a well-structured program. Launched by a letter from Edsger Dijkstra in 1968 [Dijkstra68], the goto controversy raged back and forth over the next several years, often resembling a religious war in emotional intensity. In the late 1970s, the debate died down, and a period of relative peace ensued. The underlying controversy, however, has not gone away, and the question of which control structures are acceptable remains a source of passionate concern. The intensity of that concern has been demonstrated by some of the reactions I have received to the new CS1/CS2 curriculum at Stanford and to my textbook, The Art and Science of C: A Library- Based Approach [Roberts95], which reflects the curricular revisions we have undertaken at Stanford. When we converted the curriculum from Pascal to C [Roberts93], I decided -- on the basis of many years of classroom experience -- that we should move beyond the limited control structures available in Pascal and allow students to exit from the interior of a loop in the following two cases: 1. When the structure of a loop requires some preparation (such as reading an input value) before making the test for termination, I encourage students to use the break statement to force explicit exit from the interior of a loop. This strategy, which is discussed in Section 3, allows students to solve what Dijkstra calls the loop-and-a-half problem in a way that both appeals to the student's intuition and avoids duplication of code. 2. In the context of a function, I encourage students to use the return statement as soon as the value of the function becomes known, even if that return statement would force an early exit from a loop within the function. Allowing return to be used in this way makes it much easier for students to solve a variety of problems, as illustrated in Section 4. Although the response to my text has been quite favorable, the decision to allow internal loop exits in these restricted cases has elicited some negative response. One reviewer, for example, wrote that using break "is akin to using the proverbial goto." Another charged that my approach violates the basic tenets of structured programming. A third declared that my use of break to exit from a while loop is simply "unacceptable," ruling out any further consideration. The negative reactions expressed in such reviews underscore the continued existence of controversy over what control structures are acceptable for academic use. This paper summarizes the evidence supporting the use of internal loop exits and embedded return statements, and examines the dangers associated with restricting students to a more tightly constrained control model. For many years, it was easy to discount the evidence in favor of internal loop exits. As long as Pascal was overwhelmingly accepted as the best language for teaching introductory programming, the issue had little practical relevance. In Pascal, internal loop exits are simply not available, and those who adhere to the standard version of the language are therefore forced to accept the control structures that Pascal provides. In the last few years, however, many schools have abandoned Pascal for more modern languages. For the most part, the new languages -- even those that follow directly in the Pascal tradition such as Modula-2 and Ada -- include both a structured mechanism for exiting from the interior of a loop and an active return statement. The availability of these facilities gives new relevance to the underlying pedagogical question of how to teach control structures at the introductory level. It is time to reopen the debate. 2. SUFFICIENCY VERSUS PRACTICAL UTILITY Before exploring the accumulated evidence that supports the use of internal loop exits, it is important to acknowledge that the control structures provided by Pascal have a sound theoretical basis. In their 1966 paper, Boehm and Jacopini proved that it is possible to code any flowchart program using four control structures: atomic actions, sequential composition, if-then-else, and while-do. These structures became known as D structures, after Edsger Dijkstra, and were soon extended to form a larger set of control primitives called D' structures [Ledgard75] that also includes the if-then, repeat-until, and case statements as they exist in Standard Pascal. Thus, the statements provided by Pascal indeed constitute a sufficient set of control primitives, in the theoretical sense. The key point, however, is that theoretical sufficiency is not in itself the principal criterion for program language design. After all, the arithmetic if and goto statements provided by Fortran II also constitute a sufficient set by this definition, but no one would seriously advocate using those statements as the basis for control structures in this day and age. The discipline encouraged by the use of D structures leads empirically to more reliable and more easily maintained programs than Fortran's primitives support. Thus, although the evolution of D structures represented an important practical advance for programming language design, theoretical sufficiency was not the primary reason for its success. If it were, language designers would have seen no need to augment the set of D structures with the extremely useful D' forms. A similar illustration can be drawn from the standard set of Boolean operators. Most languages define and, or, and not as the primitive operations on Boolean data. If one's primary concern is linguistic economy, this set could easily be considered wasteful, because the single operator nand (or, equivalently, the operator nor) would be sufficient in theoretical terms. This theoretical result is critical for hardware designers, who are able to exploit the sufficiency of a single operator to achieve greater regularity in the design of integrated circuits. For programmers, on the other hand, the fact that nand is by itself sufficient has little practical relevance. The average applications programmer has no intuition regarding the behavior of nand and therefore would not know how to use it effectively. Programming problems tend to be phrased in terms of the traditional logical connectives, and it is for this reason -- the admittedly subjective criterion of "naturalness" in the sense of being consistent with intuition -- that and, or, and not form the basis of Boolean calculation. The question of wh