Re: Software landmines (loops)

["Robert Martin" <rmartin@oma.com>]

Matthew Heaney wrote in message ...
>
>The best answer to the question "What is structured programming?" was
>provided by David Gries, in Chap 6, On Structured Programming, of his
>book Programming Methodology (Springer-Verlag, 1978).
>
>The chapter begins with the statement:
>
>"The term structured programming has been used with many different
>meanings since Edsger W. Dijkstra first coined the term.  Actually, the
>term appeared in the title of his monograph Notes On Structured
>Programming [that's the "little black book" - matt], but as far as I can
>determine not in the monograph itself!"
>
>So Dijkstra never precisely defined the term "structured programming."

If one looks at the little black book, one sees on its cover the words
"Structured Programming" writtin in Gold.  When one opens the book, one sees
that the first section was written by Dijkstra and is entitled "Notes on
Structured Programmin".    In part 7 of this first section we find the flow
charts which describe the four cannonical control flows; the term "single
entry at the top and a single exit at the bottom", and a discussion of the
benefits of constructing programs from these four single-entry/single-exit
forms.

In light of this it seems that Gries was incorrect when he asserted that
Dijkstra never precisely defined "structured programming".  It is probably
true that the book nowhere says: "Structured Programming is..."; but I think
that requiring such a statement is unecessary.  The contents of the book
*is* the definition of Structured Programming.
>
>Next sentence in Gries:
>
>"The lack of a precise definition has allowed, even encouraged, people
>to use it as they wished, to attribute to sp ["sp" is how Gries
>abbreviates "structured programming" - matt] what they themselves
>learned from reading Notes On Structures Programming, however different
>this might have been from Dijkstra's intent."

I don't believe it was a lack of precision that caused this.  I think it was
a lack of study.  There are plenty of folks, even now, who will simply
assume that they know what a technique is without taking the time to study
it.  This has happened with structured programming, and it has happeded with
object oriented programming.
>
>Now we're getting warm.  Ed Yourdon other authors have stated that
>structured programming means single entry/single exit modules, but did
>Dijkstra say this specifically?  The answer would appear to be no.

I quite disagree.  Dijkstra very clearly recommended that programs be
constructed from his four single-entry/single-exit control structures in his
"notes on structured programming".

>(I myself have the little black book around, and I'm going to make it a
>point to re-read it.  Sadly, this classic text is long out of print, but
>I was able to find one in a used bookstore.)

I lost my first copy about ten years ago; but I was able to find another
without too much trouble.  They are around.
>

>
>10. A major function of the structuring of the program is to keep a
>correctness proof feasible [this one comes from Dijkstra, in Notes On
>Structured Programming]

>Take a close look at item 10, from Dijkstra himself.  Dijkstra stated in
>his original ACM letter is that there is a "conceptual gap between the
>static program and the dynamic process."  His complaint was that an
>_unstructured_ program made it hard to reason about the program's
>behavior.

This is also a major theme running through his section of the book.

>What some advocates of the se/se policy seem to be forgetting is that
>the whole point is being able to mentally reason about behavior.  By
>reading the program text, can you figure out what this program does?

Yes, this was the point.  But the *mechanism* named "structured programming"
was Dijkstra's way of addressing that point.  There may be lots and lots of
different ways to address the point, but the only one that can be called
"structured programming" is the one that uses Dijkstra's four cannonical
control flows.

>I provided a couple of simple examples, one of them an idiom for using a
>special input value to terminate a loop:
>
>loop
>   Get (N);
>   exit when N = 0;
>   <process N>
>end loop;
>
>Is there anyone who doesn't understand what this code fragment does?
>
>Structured programming means keeping the code simple, where "simple"
>means "being able to easily tell what it does."  It means being able to
>prove that it's correct.  See item 7.

That list was pretty funny.  I especially like item 1. "A return to common
sense".  Or item 8 "controlling complexity through theory and discipline."
Most of those definitions are either wrong or meaningless.  Item 7. is no
different.  It certainly describes an attribute of structured programming
"easy to read and understand" but does not tell you *how* you made the code
easy to read and understand.

By the definition in Item 7. If my code is easy to read and understand, it
must be structured.  I believe that statisticians call that a "type one
error".  i.e. given that A implies B, it is a type one error to assume that
B implies A.  If we accept as a given that structured programs are easy to
read and understand, we cannot therefore assume that all programs that are
easy to read and understand are structured programs.
>
>In spite of the fact that this loop exits from the middle, I would argue
>that it does indeed fit the defination of a "structured" program.

Whether it fits Dijkstra's definition is a matter of debate.  It can be
rewritten as:

while (Get(N), N != 0)
  Process(N);

Which certainly appears close to a top-exit loop.  But this begs a question
that I don't think Dijkstra really every answered.  Must the condition in a
loop be nothing but a pure condition?  Or can it be a series of process
steps that result in a testable condition?  I prefer the latter.

I think that, as long as we treat the code that prepares the looping
condition (i.e. Get(N)) as atomic with the loop condition itself, then we
really have a top-exit loop.

Thus, after giving this some thought, I would agree with you that the code
you wrote above fits the definition of  "structured programming".  On the
other hand I disagree with your reasoning.  It is not structured because it
is easy to read.  It is structured because it is a form of top-exit loop.

Does this mean that all mid-exit loops are suddenly conformant to structured
programming?  I don't think so.  I think that when the code leading up to
the looping condition cannot be considered atomic,  (i.e. it contains
statements that do not impact the looping condition, or will change in ways
that are independent of the looping condition) then the resultant code is
not conformant to Dijkstra's rules.

For example:

for(;;)
{
  Get(N);
  if (N == 0) break;
  Process(N);
}

The above is structured because the first two statements of the loop body
are part of the loop condition. However:

for (;;)
{
  char* buf = malloc(80);
  int n = Get(buf,80);
  if (n == 0)
  {
    free(buf);
    break;
  }
  Process(buf, n);
  free(buf);
}

[Please, no complaints about the way the heap memory is being managed..
Presume that there is some good reason why its being managed that way.]

This is not a structured program because the code preceeding the loop
condition is not atomic.  It is not directly part of the loop condition, and
has side-effect that must be dealt with later.

On the other hand:

for (;;)
{
  char* buf = malloc(80);
  int n = Get(buf, 80);
  if (n != 0)
  {
    Process(buf, n);
  }
  free(buf);
  if (n == 0) break;
}

This is a structured program because it conforms to a bottom-exit looping
structure.

>
>We've been debating whether a program that terminates a loop from the
>middle, or does an early return, is really a "structured" program, but I
>think this misses the point.

It may miss some point somewhere, but it does not miss the point when the
point is the definition of structured programming.

There is another type one error we can make.  If we assume that structured
programming is "good", we cannot therefore assume that "good" implies
structured programming.  There may be many different kinds of good programs,
some of them having mid loop exits.  Such programs are not structured
programs, but that doesn't mean that they are not good programs.
>
>We should instead be asking, Can I mentally reason about this program's
>behavior?  Am I able to write a correctness proof for this program?  Am
>I confident that this program works?
>
>That's the real meaning of "structured."

I'll agree that that was Dijkstra's motivation.  But if we go no further
than the above statement then *every* program is structured, at least in the
author's eyes.  *Every* program can be reasoned about.  Every program can be
proven correct (given enough time), every program can be worked into a shape
that inspires confidence in its correctness.

Dijkstra's contribution was more than the above simple statement.
Dijkstra's contribution was a *technique* for helping to create programs
that are easy to reason about, easier to prove correct, easier to be
confident in.

>Two more lines I'd like to quote from Gries:
>
>"I would add to this that one should always strive for simplicity and
>elegance.  The simplest solution is always the easiest to understand."


This is often true but, unfortunately, simplicity is often subjective.

Robert C. Martin    | Design Consulting   | Training courses offered:
Object Mentor       | rmartin@oma.com     |   Object Oriented Design
14619 N Somerset Cr | Tel: (800) 338-6716 |   C++
Green Oaks IL 60048 | Fax: (847) 918-1023 | http://www.oma.com

"One of the great commandments of science is:
    'Mistrust arguments from authority.'" -- Carl Sagan