loopexit.txt

c语言开发方面的经典问题,包括源代码.c语言开发所要注意的问题,以及在嵌入式等各方面的应用

I have looked for other studies that might contradict the findings of
the Soloway study.  Although I have found authors who assert that the
use of internal loop exits is wrong, I have encountered none that
support their claims with objective evidence.

It is also possible to use standard Pascal texts as evidence that the
read/process strategy in fact corresponds to student intuition.  An
examination of at the approach used to solve the read-until-sentinel
problem in the five best-selling Pascal textbooks [Cooper92, Dale92,
Koffman91, Leestma87, Savitch91] reveals that:

   o  In each of the textbooks, the problem is solved by unwinding
      the loop so that the read phase of the operation occurs twice:
      once prior to the loop and once at the end of the loop body.

   o  In every text except Leestma and Nyhoff, the authors derive
      their solution by first presenting the read/process strategy
      and subsequently modifying it to fit the process/read form
      required by Pascal's control structures.

To me, the approach these authors take suggests that they themselves
accept that students find the read/process strategy more intuitive.  To
encourage students to write programs that fit Pascal's restrictions,
these texts teach them -- often at great length -- to abandon their
initial strategy in favor of one that reverses the order of the
operations within the loop.  My own classroom experience certainly
supports this conclusion.  By introducing loop exits and using the
read/process strategy, I find that I can save almost an entire day's
lecture.

The concern, of course, about introducing an internal loop exit form is
that students will end up abusing it, since it is certainly possible to
do so.  Our experience at Stanford, however, suggests that this problem
does not in fact arise.  Students tend to write code based on the models
they are given, using internal loop exits only in the disciplined way
outlined in the class examples.  In the last three years, over 2500
students have completed CS1 at Stanford, and the teaching assistants
have reported no problems with overuse of the break construct.  This
finding is consistent with the results of a study by Sheppard, which
demonstrated that internal loop exits do not in fact compromise program
readability [Sheppard79].

4.  SEQUENTIAL SEARCH

In addition to encouraging the use of an internal loop exit to solve the
loop-and-a-half problem, I also teach students that it is appropriate to
use a return statement at any point in a function where the result value
becomes known, even if the return statement is nested in such a way that
it acts as a nonstandard exit from an enclosing control structure.  The
paradigmatic example that underscores the value of this technique is the
sequential search problem.

In essence, the sequential search problem consists of writing an
implementation for the following function header line:

          function Search(var list: IntList;
                          n, key: integer) : integer;

The parameter list is an array of integers that conforms to the Pascal
type definition

          type
            IntList = array [1..MaxList] of integer;

where MaxList is some constant upper bound on the list size.  The actual
number of elements actively stored in the array is typically smaller and
is given by the parameter value n.  The problem is to implement Search
in such a way that it returns the least index i for which list[i] is
equal to key; if the value key does not appear in list, the function
Search should return 0.  Functions that have this basic structure come
up frequently in programming, even at the introductory level.

If the language includes an active return statement, such as the one
provided by C, Modula-2, or Ada, the Search function has the following
concise and natural implementation:

          function Search(var list: IntList;
                          n, key: integer) : integer;
          var
            i: integer;
          begin
            for i := 1 to n do
              if list[i] = key then return i;
            return 0
          end;

If students are restricted to the facilities available in Standard
Pascal, the Search function, as simple and as fundamental as it is,
turns out to be extremely hard to code -- so difficult in fact that many
of them are incapable of developing a correct solution.  If you haven't
encountered this problem, it is worth spending a few minutes to write
the code on your own.

The difficulty of coding the sequential search algorithm was described
in 1980 in an insightful paper by Henry Shapiro that never received the
attention it deserved.  The statistics he reports are far more
conclusive than those in the Soloway study of internal loop exits.  Of
the students in his study who attempted to use the for loop strategy,
all of them managed to solve the problem correctly, even though they
were forced to use a goto statement to achieve the effect of the return
statement in the preceding example.  In fact, Shapiro notes that

      I have yet to find a single person who attempted a program
      using [this style] who produced an incorrect solution.

Students who attempted to solve the problem without using an explicit
return from the for loop fared much less well: only seven of the 42
students attempting this strategy managed to generate correct solutions.
That figure represents a success rate of less than 20% [Shapiro80].

That students would have difficulty in developing a general solution to
this problem is not really surprising.  When they are limited to
Pascal's control structures, the answer is quite complicated.  To see
just how complicated the solutions can get, it is again useful to
consider how the leading Pascal texts handle the problem.

The following code, adapted from the solution given on page 300 of
Leestma and Nyhoff [Leestma87], illustrates that a correct solution is
indeed possible:

          function Search(var list: IntList;
                          n, key: integer) : integer;
          var
            i: integer;
            found: boolean;
          begin
            i := 1;
            found := FALSE;
            while (i <= n) and not found do
              if list[i] = key then
                found := TRUE
              else
                i := i + 1;
            if found then
              Search := i
            else
              Search := 0
          end;

This solution introduces a Boolean variable and uses 11 lines of code to
do the work accomplished by three in the solution based on the return
statement.  It does, however, return the correct result.  The Dale and
Weems text [Dale92] uses a slight variation of this strategy that also
returns the correct result.

The other leading Pascal texts adopt a different approach.  The code
suggested independently by Cooper, Koffman, and Savitch [Cooper92,
Koffman91, Savitch91] has the following general form:

          function Search(var list: IntList;
                          n, key: integer) : integer;
          var
            i: integer;
          begin
            i := 1;
            while (i < n) and (list[i] <> key) do
              i := i + 1;
            if list[i] = key then
              Search := i
            else
              Search := 0
          end;

These authors have taken great pains to avoid some of Pascal's pitfalls.
The bounds test for the while loop specifies continuation only if i < n,
even though the test i <= n might seem more natural in this context.
The problem with the test i <= n is that Pascal's handling of the and
operator can generate a subscript violation if n is equal to MaxList.
On the last cycle, Pascal evaluates both halves of the condition and
therefore evaluates list[i] even if it has already determined that
i > n.  Fixing this problem also requires that the test in the if
statement check the element value and not the value of the index.
Unfortunately, this change in the final test introduces a new problem:
the function can fail if n is 0.  As written, the implementation tests
the first element in the array against the key even if the array has no
active elements.

In fairness to the authors, it is important to point out that the
original examples are not in fact buggy in the strictest sense.  Koffman
specifically rules out the possibility that n is 0 in the preconditions
of the function, although this relationship is not tested within the
implementation.  In both Cooper and Savitch, the upper bound is a
constant rather than a variable.  Since the constant is not declared to
be zero, the problem does not actually arise.  Even so, the important
point is that the coding from these texts cannot be considered as an
appropriate model for a general-purpose search function.  A student
trying to solve the general case might well do exactly what I did: go
through the functions and replace the constant bound with the
corresponding variable.  At that point, the implementation fails.

The conclusion that the sequential search problem is difficult for
students who use the Pascal strategy is strongly supported by our
experience at Stanford.  When we taught the introductory course in
Pascal, we worked hard to present the sequential search algorithm in a
careful and rigorous way that would ensure correct operation in
special-case situations.  Despite that care, we discovered that even our
best students had trouble regenerating the solution after taking the
course.  The situation is entirely different now that we use a return
statement to implement the sequential search algorithm.  Students who
manage to understand arrays at all understand the sequential search
algorithm immediately; it no longer represents a source of difficulty.

5.  CONCLUSIONS

When students are limited to the control structures available in Pascal,
they tend to have significant difficulty solving certain programming
problems that come up frequently in practical applications.  Allowing
students to use control forms that provide a structured mechanism for
loop exit increases their comprehension along with their ability to
write correctly functioning code.  Although these facilities are absent
from Pascal, they are widely available in modern programming languages
and should be introduced when those languages are used in an
instructional setting.

To a significant extent, the discipline that Pascal encouraged has had a
positive effect on the computer science curriculum.  As we move to new
programming languages, however, it is crucial to analyze our experience
to determine what aspects of traditional practice are predicated more on
the particular nature of Pascal than on some more general principle.  If
our programming methodology can be defended on its own merits, we should
continue to support it.  On the other hand, if our students are unable
to write correct code using the existing paradigms, we must reevaluate
them.  As Dijkstra observed, "the tools we use have a profound (and
devious!) influence on our thinking habits, and, therefore, on our
thinking abilities" [Dijkstra82].  As we adopt new tools, we must be
ready to think in new ways.

REFERENCES

[Boehm66] C. Boehm and G. Jacopini, "Flow diagrams, Turing machines, and
languages with only two formation rules," Communications of the ACM, May
1966.

[Cooper92] Doug Cooper, Oh! Pascal! Turbo Pascal 6.0 (third edition),
New York: Norton, 1992.

[Dahl72] Ole Johan Dahl, Edsger W. Dijkstra, and C.A.R.  Hoare,
Structured Programming, London: Academic Press, 1972.

[Dale92] Nell Dale and Chip Weems, Turbo Pascal (third edition),
Lexington, MA: D.C. Heath, 1992.

[Dijkstra68] Edsger W. Dijkstra, "Goto statement considered harmful,"
letter to the editor, Communications of the ACM, March 1968.

[Dijkstra82] Edsger W. Dijkstra, "How do we tell truths that might
hurt," SIGPLAN Notices, March 1982.

[Knuth74] Donald Knuth, "Structured programming with goto statements,"
Computing Surveys, December 1974.

[Koffman91] Elliot Koffman with Bruce Maxim, Turbo Pascal (third
edition), Reading, MA: Addison-Wesley, 1991.

[Ledgard75] Henry Ledgard and Michael Marcotty, "A genealogy of control
structures," Communications of the ACM, November 1975.

[Leestma87] Sanford Leestma and Larry Nyhoff, Pascal: Programming and
Problem Solving (second edition), New York: Macmillan, 1987.

[Roberts93] Eric S. Roberts, "Using C in CS1: Evaluating the Stanford
Experience," SIGCSE Bulletin, March 1993.

[Roberts95] Eric S. Roberts, The Art and Science of C: A Library-Based
Approach, Reading, MA: Addison-Wesley, 1995.

[Savitch91] Walter Savitch, Pascal: An Introduction to the Art and
Science of Programming (third edition), Redwood City, CA:
Benjamin/Cummings, 1991.

[Shapiro80] Henry Shapiro, "The results of an informal study to evaluate
the effectiveness of teaching structured programming," SIGCSE Bulletin,
December 1980.

[Sheppard79] S. Sheppard, B. Curtis, P. Millman, and J.  Clement,
"Modern coding practices and programmer performance," Computer, December
1979.

[Soloway83] Elliot Soloway, Jeffrey Bonar, and Kate Ehrlich, "Cognitive
strategies and looping constructs: an empirical study," Communications
of the ACM, Vol.  26, No. 11, November 1983.

[Yuen94] C. K. Yuen, "Programming the premature loop exit: from
functional to navigational," SIGPLAN Notices, March 1994.