From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fac41,9a0ff0bffdf63657 X-Google-Attributes: gidfac41,public X-Google-Thread: 1108a1,9a0ff0bffdf63657 X-Google-Attributes: gid1108a1,public X-Google-Thread: f43e6,9a0ff0bffdf63657 X-Google-Attributes: gidf43e6,public X-Google-Thread: 103376,4b06f8f15f01a568 X-Google-Attributes: gid103376,public From: "Robert Martin" Subject: Re: Software landmines (loops) Date: 1998/09/05 Message-ID: <6ssa6p$brt$1@hirame.wwa.com> X-Deja-AN: 388247148 References: <35f23ce2.7649859@news.erols.com> <6snn1b$c90$1@hirame.wwa.com> <35ef7dff.24318728@news.erols.com> <35f79e53.98130474@news.erols.com> X-MimeOLE: Produced By Microsoft MimeOLE V4.72.2106.4 Organization: WorldWide Access - Midwestern Internet Services - www.wwa.com Newsgroups: comp.lang.eiffel,comp.object,comp.software-eng,comp.lang.ada Date: 1998-09-05T00:00:00+00:00 List-Id: 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; > >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