Structured programming -- a useful heuristics that became a religious cult

This was one of the first cases of interplay between management wishes and religious zealotry.  In the process a useful heuristic that states that the quality of  a program is usually inversely correlated with the number of goto statements in it was converted into primitive techno cult.

In 1967 a letter from Dijkstra appeared in Communications of the ACM with the title "Goto statement considered harmful." (actually coined by Nicholas Wirth, who was at the time the editor of CACM).  The letter, which cited the idiotic (or more correctly meaningless) Böhm and Jacopini proof, called for the abolishment of unconstrained GOTO from high-level languages in the interest of improving code quality. This letter is usually cited as the beginning of the structured programming cult. The opening sentences of that letter clearly illustrate its purpose and style:

"For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of GO TO statements in the programs they produce. More recently I discovered why the use of the GO TO statement has such disastrous effects, and I became convinced that the GO TO statement should be abolished from all 'higher level' programming languages (i.e. everything except, perhaps, plain machine code)." (Dijkstra '68a, pg. 147).

In essence, Dijkstra proposed a taboo without any scientific justification, just on the base of some vague (abeit valuable at the time) heuristic. He has no clue about problem of enumeration of simple three and four node directed graphs and never tried to explore the problem under this angle. Later this taboo approach became popular and lead to the phrase "considered harmful", especially in the title of the article,  considered harmful ;-)  In “Considered Harmful” Essays Considered Harmful

It is not uncommon, in the context of academic debates over computer science and Web standards topics, to see the publication of one or more “considered harmful” essays. These essays have existed in some form for more than three decades now, and it has become obvious that their time has passed. Because “considered harmful” essays are, by their nature, so incendiary, they are counter-productive both in terms of encouraging open and intelligent debate, and in gathering support for the view they promote. In other words, “considered harmful” essays cause more harm than they do good.

What Are “Considered Harmful” Essays?

The Jargon File has a short entry on “considered harmful” that encapsulates the genesis of such essays:

Edsger W. Dijkstra’s note in the March 1968 Communications of the ACM, “Go To Statement Considered Harmful,” fired the first salvo in the structured programming wars…. As it turns out, the title under which the letter appeared was actually supplied by CACM’s editor, Niklaus Wirth.

The controversy resulting from the article’s publication became so heated that the CACM subsequently decided to never again publish pieces with such assertive positions.

The seeds of conflict were already in the ground, however, and in the years since 1968 there have been thousands of pieces published with the general title format of “[something] Considered Harmful.” A search of Google at the end of 2002 turned up more than 4,700 Web pages with the exact phrase “considered harmful” in the document title. A similar search which looked for the exact phrase “considered harmful” in all document content yielded approximately 46,600 results.

All of this content is the more wasteful because “considered harmful” essays have become something of a joke. In some cases, these essays are written as jokes, but more often they are serious statements of opposition to a practice, idea, or technology. The problem is that “considered harmful” essays rarely, if ever, have the intended effect of weakening support for whatever it is they consider harmful.

Why Do People Write “Considered Harmful” Essays?

There are those cases where such essays are written because the author enjoys grandstanding, and knows that use of the “considered harmful” format will get them noticed. A piece of this type is usually so over the top that it is easy to spot. For example, a piece titled “‘Considered Harmful’ Essays Considered Harmful” would very likely be a case of using the “considered harmful” format to draw attention for its own sake. We will ignore such essays in this commentary.

Typically, “considered harmful” essays gets written because someone has an axe to grind, and they feel like making that grinding process both public and dogmatic. This is a form of grandstanding, of course, but it is done with a purpose beyond simple publicity seeking. Usually such “considered harmful” essays are intended to draw attention to a little-known subject about which the author is passionate, or to highlight what the author feels to be a poor decision by someone else.

In addition, there are those “considered harmful” essays that are written as part of a long-running argument that has gradually escalated. Indeed, debates over W3C standards seem to be particularly susceptible to this trend. Instead of being the opening salvos, these essays are more like doomsday devices in the eyes of their authors. The idea is that the arguments presented will be so devastating to the opposing side that capitulation will immediately follow, thus securing victory for the essay’s author and right-minded people the world over. Following in the footsteps of Godwin’s Law, we can draw a similar maxim: As a theoretical debate grows longer, the probability of a “considered harmful” essay approaches one.

In the main, however, it often seems that “considered harmful” essays get written simply because an author can’t think of a better way to express his point of view. This is a sad commentary on both the authors in question and the level of debate most often present in our societies.

How Do “Considered Harmful” Essays Cause Harm?

There are three primary ways in which these essays cause harm.

• The writing of a “considered harmful” essay often serves to inflame whatever debate is in progress, and thus makes it that much harder for a solution to be found through any means. Those who support the view that the essay attacks are more likely to dig in and defend their views by any means necessary, and are less receptive to reasoned debate. By pushing the opposing views further apart, it becomes more likely that the essay will cause a permanent break between opposing views rather than contribute to a resolution of the debate.
• “Considered harmful” essays are most harmful to their own causes. The publication of a “considered harmful” essay has a strong tendency to alienate neutral parties, thus weakening support for the point of view the essay puts forth. A sufficiently dogmatic “considered harmful” essay can end a debate in favor of the viewpoint the essay considers harmful.
• They’ve become boring clichés. Nobody really wants to read “considered harmful” essays any more, because we’ve seen them a thousand times before and didn’t really learn anything from them, since we were too busy being annoyed to really listen to the arguments presented.

Is There An Alternative to “Considered Harmful” Essays?

Absolutely. The most basic alternative is not to write them at all, but to instead engage in reasoned debate without resorting to dogmatic assertions or distractive tactics (e.g., ad hominem attacks and straw man arguments). In those cases where some sort of document is needed outside of the debate, there are a number of superior alternatives.

• A description of the strong and weak aspects of one’s own point of view; we might call it a “benefits and weaknesses of” essay. This is a positive contribution to the debate, and allows the debating parties to take the best parts of each view and more readily find a compromise solution. Knowing both the benefits and weaknesses of all views makes it easier to cover the weaknesses in one view with the strengths in another.
• A description of the strong and weak aspects of another point of view; we might call it a “perceived benefits and weaknesses of” essay. This allows the author to evaluate what he believes to be good and bad about another point of view. Authors must be careful to avoid slanting the piece too far toward the weaknesses, lest they end up writing a “considered harmful” essay by another name.
• An essay that compares different viewpoints in the same piece; in other words, a “compare and contrast” essay. These essays attempt to objectively evaluate multiple views and point out how they are both alike and dissimilar, thus highlighting both common ground and areas that need work. The benefits of such essays are fairly self-evident.

The Considered Conclusion

“Considered harmful” essays are not only a sad cliché at this stage of the game, they are counter-productive to reasoned debate and most often do far more harm than good to whatever cause they promote. It would therefore seem obvious that the only intelligent course of action is to abandon their use entirely, and instead look to more constructive forms of essay writing in the support of debate positions.

Naive version of structured programming proposed by Edsger W. Dijkstra was convincingly refuted by Donald Knuth in his 1974 paper, "Structured Programming with Goto Statements". He pointed out that idea of abolishing the GOTO statement is meaningless, what we should strive for is codifying typical control graphs into relevant programming language control structures.  Planar graphs for obvious reasons are preferable to non-planar.  The paper contains several example where using goto leads to clearer and more efficient code without sacrificing provability. One classic example is the case of multiple selections coming out of the loop (and each selection need to break the loop). Knuth proposed an interesting constraint for programming languages control structures: it should be possible to draw a program's flow chart with all forward branches on the left, all backward branches on the right, and no branches crossing each other.

But as happens with religious doctrines it did little to diminish attractiveness of the cult both to believers and charlatans who wanted to parasite of this new bonanza by writing useless books, giving useless lectures and otherwise enjoying high life of the priest of a popular cult.

The cult like other cults that thrived because it was naive and primitive and gave an answer to an important problem that was concise, easily understandable and wrong.   There was never any scientific ground and empirical testing of the claim. the 1970s after IBM researcher Harlan Mills  experiment when he used his naive interpretation of structured programming theory to the development of an indexing system for the New York Times. This experiment was unconvincing and very dirty. The project involved small number of "super-star" programmers which would probably succeed with any stupid methodology enforced on them ;-).  Here is the style of reporting about this programming project ('Revolution in Programming, 1973):

"Then came the IBM work for the New York Times, with reports of greatly increased programmer productivity and very greatly reduced coding error rates (one detected error per 10.000 lines of coding, or one per man year)! Absolutely incredible, but these were the facts."

(McCracken '73, pg. 51).

Critics pointed out:

 "- Many of the early successful projects were run by experienced organizations using top-level staff - how do the new techniques work in practice in everyday installations?

 - The very fact that an organization attempts to introduce new techniques suggests a commitment to improving software production - how much of the reported improvement is due to that commitment, and how much to the new techniques?" (Infotech, letter R377, Nov. 1978).

The latest victim of the cult was Java, where designers decided to make a "revolutionary" decision to get rid of goto statement but failed to read programming languages literature and see the limitations of this approach. And as one knows from history revolutions usually lead to sufferings... Also it would be very true and objective to state that in this case Java designers never read or understood Donald Knuth's article on the subject.

Generally in order to check the quality of a chapter about control structures in any programming book you can use a simple test:

• if the book mentions that any program can be written using only three control structures -- recycle it -- it's a trivial fact that any program can be written using only three control structures and it's really easy(and very stupid) to do so. Don't be fooled by references about the C. Böhm and G. Jacopini theorem, which supposedly proves that any control structure can be represented by an equivalent control structure with just three basic control blocks - while loop, if statement and sequential composition. From the mathematical point of view, the result is trivial since any program can be represented in a form like: 

  
  while(stmt > 0)
      if (stmt==1) { ... ; stmt = 3;   }
      if (stmt==2) { ... ; stmt = 4; }
      if (stmt==3) { ... ; stmt = 5;  }

  ...

  ...

  ...
  }

• whether it mentions Donald Knuth's article "Structured programming with goto statements." If not probably it's better to get another or additional book.
• whether it discuss short-circuit and and or operation in if statements and while loops. If not the chapter is superficial.
• whether if shows how to program loops with two index variables.
• whether it contains an example of programming in Java of some classic algorithm -- at least simple search. If not, it's probably an introductory book.
• contains at least some diagrams clarifying complex issues such as multilevel break and continue.

The problem with Java is that IMHO Java designers did not understand issues of safety of control structures well. IMHO they made three important mistakes:

• they fail to make the use of curly braces mandatory after "if" "do", "while", "for" (that can be probably compensated by warning in the compiler). 
• Suffix after closing curly braces greatly increase safety of nesting as and decent PL/1 programmer knows. That feature can be imitated with comments and some kind of postprocessor.
• They omitted useful shortcut for else if (elif). Yet another important safety feature is so called foreach loop that prevents a lot subtle errors with indexing of an array when one just need to process all elements in some way.

The only extension that I see from rather Spartan set of C control structures is a multilevel break/continue with the label. It's useful bit its insufficient to compensate for the absence of goto.

As a result Java is neither well suited to writing complex algorithms like algorithms from the Art of Computer Programming by D.Knuth nor it represent the state of the art in safe control structure. There is no such thing as a free lunch and if one drops goto from the programming language one needs to add a lot of additional specialized "structured" statements to compensate for that. Or the language will remain crippled. Bruce Eckel recognize that the decision to drop rather than restrict goto was probably a mistake (p.137). But he does not provide any recommendations for compensating Java weaknesses.

Here I would like to stress  again that one should consider Java as a better VB, not a better C++.  But it's really unfortunate that Java did not benefit from additional control structures found in other modern languages, for example Perl and Icon.

The author correctly includes a discussion of the return statement into the control structure section as in Java the return statement can sometimes compensate for the absence of a goto statement.

Studying of control structures in programming languages is often provided under the umbrella of so called structured programming. The idea of "real" structured programming, or "structured programming with goto statements" is that one could write, understand and modify the program much more easily by organizing and coding computer programs in which all control structures have a single entry and a single exit point. It is this idea that constitute rational, useful part of the whole structured programming movement.

The idea of the cult is to limit yourself with three or four contiorl statements and enjoy nirnanna :-). Edsger W. Dijkstra was the prophet of the cult.

But there is a lot of religious junk around this sound idea (as around many other sound ideas). Some authors go too  far and declare that just three types of control flow are allowed: sequential, test, and iteration (kosher control constructs ;-).

Those who are interested in the study of a history of programming probably know that structured programming created probably the first strong religious movement in programming as scientific ground of usefulness of just three kosher control structures are very weak, if exist at all. Here I would like to cite Edsger W. Dijkstra -- a high priest of structured programming and verification (unlike many of his "structured" followers Dijkstra is a real computer scientist; before initiating structured programming movement, he invented several useful algorithms including semaphore synchronization; currently he is a professor at the University of Texas at Austin):

Summarizing: as a slow-witted human being I have a very small head and I had better learn to live with it and to respect my limitations and give them full credit, rather than try to ignore them, for the latter vain effort will be punished by failure.

Edsger W. Dijkstra, Structured Programming.

 

Like a lot of slogans, it looks appealing, but it was often used for the advocacy of "structured primitivism" writing of any program using only the "kosher"  control structures mentioned above. This "orthodox" structured programming movement now looks a little bit strange (much like an idea to verify each and every program instead of testing), but in the early 70es a lot people jumped on this bandwagon and tried to do what the apostles of the movement preached.  The remnant of this days is an entry in the famous Jargon File:

considered harmful

adj. Edsger W. Dijkstra's note in the March 1968 "Communications of the ACM", "GOTO Statement Considered Harmful", fired the first salvo in the structured programming wars. Amusingly, the ACM considered the resulting acrimony sufficiently harmful that it will (by policy) no longer print an article taking so assertive a position against a coding practice. In the ensuing decades, a large number of both serious papers and parodies have borne titles of the form "X considered Y". The structured-programming wars eventually blew over with the realization that both sides were wrong, but use of such titles has remained as a persistent minor in-joke (the `considered silly' found at various places in this lexicon is related).

 

Java control structures do not provide the possibility of programming each and every one-entry one-exit control structure without goto, so generally some additional computation needs to be specified. But again clever use of return and exceptions sometimes can compensate for this drawback.

Java has the following two statements to improve the control of execution of loops:

• continue -- start the next iteration of the loop (unlike Perl. Java allows no possibility of specifying a special block that is a part of the loop and that will be executed each iteration even if the continue statement was used).
• break  -- break out of loop; in Perl the same semantic has last.

Each of these statements can have suffix that should correspond to a loop label. In this case it applies to the loop labeled with the same label. So multilevel breaks are possible. 

Note on the structure of the for loop

For people who did not program in C the easiest way to remember the correct sequence of components in the for loop is by remembering the magic word "STAB" that corresponds to the following general scheme of the for statement"

       for (start; test; action) { body }

One can see that for loop consist of four parts. The for loop works well where the number of iterations of the loop is known before the loop is entered. The head of the loop consists of three parts separated by semicolons.  I recommend always to use the braces for the body of the for loop, even if the body consist of a single statement.

• The first or start part is run before the loop is entered. This is usually the initialization of the loop variable. The start part is executed only ones when the flow of control reach the loop.
• The second test part is a logical expression that returns true of false. The loop is exited when it returns false.   The test part  is evaluated at the beginning of each iteration and determine when to transfer control to the statement following the loop.
• The third is action part -- a statement to be run every time the loop body is completed. This is often an increment/decrement of the loop counter. The action part is executed on each iteration just before test part of the loop.

The continue statement

Java continue statement is used to start next iteration immediately without executing the rest of the of body of the loop. Use of continue in Java helps to avoid excessive nesting in the loop. For example:

One can see that the loop at the left is more difficult to understand that the loop at the right.

NEWS CONTENTS

• 20110907 : Code Complete, First Edition by Steven C. McConnell ( 1993 , First edition of Code Complete )
• 20110907 : Code Reads #5 Knuth's "Structured Programming with go to Statements" - Scott Rosenbergs Wordyard ( Code Reads #5 Knuth's "Structured Programming with go to Statements" - Scott Rosenberg's Wordyard, )

Old News ;-)

[Sep 07, 2011] Code Complete, First Edition by Steven C. McConnell

"The primary feature of most goto discussions is a shallow approach to the question. People on the "gotos are evil" side usually present a trivial code fragment that uses gotos, then show how easy it is to rewrite the code fragment without gotos. This proves mainly that it's easy to write trivial code without gotos. On the other hand, people on the "I can't live without gotos" side usually present a case in which eliminating a goto results in an extra comparison or two lines of duplicated code. The significance of the gain is questionable, and this proves mainly that there's a case in which using a goto results in one less comparison, rarely a significant gain on today's computers. "

1993 | First edition of Code Complete

16.1 Using gotos

Computer scientists are zealous in their beliefs, and when the discussion turns to gotos, they get out their jousting poles, armor, and maces, mount their horses, and charge through the gates of Camelot to the holy wars.

No one quarrels with using gotos to emulate structured constructs in languages that don't support structured control constructs directly. The debate is about languages that support structured constructs, in which gotos are theoretically not needed. Here's a summary of the points on each side.

The Argument Against gotos

The general argument against gotos is that code without gotos is higher-quality code. The famous letter that sparked the original controversy was Edsger Dijkstra's "Go To Statement Considered Harmful" in the March 1968 Communications of the ACM. Dijkstra observed that the quality of a programmer's code was inversely proportional to the number of gotos the programmer used. In subsequent work, Dijkstra has argued that code without gotos can more easily be proven correct.

Code containing gotos is hard to format. Indentation should be used to show logical structure and gotos have an effect on logical structure. Trying to use indentation to show the logical structure of a goto, however, is difficult or impossible.

Use of gotos defeats compiler optimizations. Some optimizations depend on a program's flow of control remaining within a few statements. An unconditional goto makes the flow harder to analyze and reduces the ability of the compiler to optimize it. Thus, even if introducing a goto produces an efficiency at the source-language level, it may well reduce overall efficiency by thwarting compiler optimizations.

Proponents of gotos sometimes argue that they make code faster or smaller. But code with gotos is rarely the fastest or smallest possible. Donald Knuth's marvelous article, "Structured Programming with go to Statements," gives several examples of cases in which using gotos is slower and larger (Knuth 1974).

In practice, use of gotos tends to violate structured programming principles. Even if gotos aren't confusing when used carefully, once gotos are allowed, they spread through the code like termites in a rotting house and aren't used carefully. If any gotos are allowed, the bad creep in with the good, so it's better not to allow any of them.

Overall, in the two decades since publication of Dijkstra's original letter, experience has shown the badness of goto-laden code. In a survey of the literature, Ben Shneiderman concluded that the evidence supports the badness of the goto (Shneiderman 1980).

The Argument for gotos

The argument for the goto is characterized by advocating its use in specific circumstances rather than its indiscriminate use. Most arguments against gotos are based on indiscriminate use, rather than careful use. The goto controversy began when Fortran was the most popular language. Fortran lacked any presentable loop structures, and, in the absence of any good advice on programming structured loops with gotos, programmers wrote a lot of spaghetti code. Such code undoubtedly was correlated with low quality programs but has little to do with careful use of a goto to make up for a gap in a structured language's capabilities.

A well-placed goto can eliminate duplicate code. Duplicate code leads to problems with the two sets of code being modified differently. It increases the size of source and executable files. The bad effect of the goto is outweighed in such a case by the worse effect of duplicate code.

The gotos is useful in a routine that allocates resources, performs operations on those resources, then deallocates the resources. With gotos, you can cleanup in one section of code, and they reduce the danger of forgetting to deallocate the resources in each place you detect an error.

In some cases, gotos can result in faster and smaller code. Knuth's marvelous 1974 article cited a few cases in which gotos produce a legitimate gain (Knuth 1974).

Good programming doesn't mean eliminating gotos. Methodical decomposition, refinement, and selection of control structures automatically leads to goto-free programs in most cases. gotolessness is not the aim, but the outcome, and putting the focus on no gotos isn't helpful.

Two decades worth of research with gotos has been inconclusive in demonstrating their badness. In a survey of the literature, B. A. Sheil concluded that unrealistic test conditions, poor data analysis, and inconclusive results failed to support the claim that the number of bugs was proportional to the number of gotos (Sheil 1981). That criticism applies to Shneiderman's survey of the literature, cited in the argument against gotos, as well as other studies. Sheil did not conclude that gotos were good, rather that experimental evidence against them was not conclusive.

Finally, goto was included as part of the Ada language, the most carefully engineered programming language in history. Ada was developed long after both sides of the goto debate were fully developed, and, after considering all sides of the issue, included the goto.

The Phony goto Debate

The primary feature of most goto discussions is a shallow approach to the question. People on the "gotos are evil" side usually present a trivial code fragment that uses gotos, then show how easy it is to rewrite the code fragment without gotos. This proves mainly that it's easy to write trivial code without gotos. On the other hand, people on the "I can't live without gotos" side usually present a case in which eliminating a goto results in an extra comparison or two lines of duplicated code. The significance of the gain is questionable, and this proves mainly that there's a case in which using a goto results in one less comparison, rarely a significant gain on today's computers.

Most textbooks don't help since they merely provide a trivial example of rewriting code without a goto and think they're done. Here's an example of a trivial piece of code from such a textbook:

Pascal Example of Code that's Supposed to be Easy to Rewrite Without gotos

repeat 
   GetData( InputFile, Data ); 
   if eof( InputFile ) then 
      goto LOOP_EXIT; 
   DoSomething( Data );
until ( Data = -1 );
LOOP_EXIT:

The book quickly replaces this with gotoless code:

Pascal Example of Supposedly Equivalent Code, Rewritten Without gotos

GetData( InputFile, Data );
while ( not eof( InputFile ) and ( Data <> -1 ) do 
   begin 
   DoSomething( Data ); 
   GetData( InputFile, Data ) 
   end;

This "trivial" example is disguised because it contains an error. In the case in which Data equals -1, the translation detects the -1 and exits the loop before executing DoSomething(). The original code executes DoSomething() before the -1 is detected. In other words, a programming book trying to show how easy coding is using only structured programming techniques translated its own example incorrectly! The author of that book shouldn't feel too bad, however, because other books make similar mistakes! Even the pros have difficulty achieving gotoless nirvana.

Here's a faithful translation of the code with no gotos:

Pascal Example of Truly Equivalent Code, Rewritten Without gotos

repeat 
   GetData( InputFile, Data ); 
   if ( not eof( InputFile )) then 
      DoSomething( Data );
until ( Data = -1 or eof( InputFile ) );

Even with a correct translation of the code, the debate is still phony because it trivializes the case in which a goto is needed. Cases like this are not the ones in which thoughtful programmers choose a goto as the preferred form of control.

It would be hard by now to add anything worthwhile to the theoretical debate about gotos. One level of discussion isn't usually addressed, however, and that's the situation in which a programmer who is fully aware of gotoless alternatives chooses to use a goto on the basis of its readability and maintainability.

The following sections present cases in which some experienced programmers argue for using gotos. The sections provide examples of rewriting the code without gotos, and discuss the tradeoffs between the various versions.

Error Processing and gotos

Writing highly interactive code creates additional programming demands. In particular, it demands that you pay a lot of attention to error processing and cleaning up resources when errors occur. Here's an example of code that purges a group of files. It first gets a group of files to purge, then finds each file, opens it, overwrites it, and erases it. It checks for errors at each step:

Pascal Example of Code with gotos that Processes Errors and Cleans up Resources

PROCEDURE PurgeFiles( var ErrorState: ERROR_CODE );
{ This routine purges a group of files }
var
   FileIndex:        Integer;
   FileHandle:       FILEHANDLE_T;
   FileList:         FILELIST_T;
   NumFilesToPurge:  Integer;

label
   END_PROC;

begin
   MakePurgeFileList( FileList, NumFilesToPurge );

   ErrorState := Success;
   FileIndex   := 0;
   while ( FileIndex < NumFilesToPurge ) do
      begin
      FileIndex := FileIndex + 1;

      if not FindFile( FileList[ FileIndex ], FileHandle ) then
         begin
         ErrorState := FileFindError;
         goto END_PROC
         end;

      if not OpenFile( FileHandle ) then
         begin
         ErrorState := FileOpenError;
         goto END_PROC
         end;

      if not OverwriteFile( FileHandle ) then 
         begin
         ErrorState := FileOverwriteError;
         goto END_PROC
         end;

      if Erase( FileHandle ) then
         begin
         ErrorState := FileEraseError;
         goto END_PROC
         end

      end; { while }

   END_PROC:

   DeletePurgeFileList( FileList, NumFilesToPurge )

end; { PurgeFiles }

This routine is typical of circumstances in which experienced programmers select a goto. Other, similar cases occur when a routine needs to allocate and clean up resources such as memory or handles to fonts, windows, brushes, and printers. The alternative to gotos in those cases is usually duplicating code to clean up resources. In such cases, a programmer might balance the evil of the goto against the maintenance headache of duplicate code and decide that the goto is the lesser evil.

You can rewrite the above routine in a couple of ways that avoid gotos, and you make tradeoffs in both cases. Here are the possible rewrite strategies:

Rewrite with Nested if Statements. To rewrite with nested if statements, nest the if statements so that each is executed only if the previous test succeeds. This is the standard, textbook, structured-programming approach to eliminating gotos. Here's a rewrite of the routine using the standard approach:

Pascal Example of Code that Avoids gotos by using Nested ifs

PROCEDURE PurgeFiles( var ErrorState: ERROR_CODE );

{ This routine purges a group of files }

var
   FileIndex:        Integer;
   FileHandle:       FILEHANDLE_T;
   FileList:         FILELIST_T;
   NumFilesToPurge:  Integer;

begin
   MakePurgeFileList( FileList, NumFilesToPurge );

   ErrorState  := Success;
   FileIndex    := 0;

   while ( FileIndex < NumFilesToPurge and ErrorState = Success ) do
      begin
      FileIndex := FileIndex + 1;

      if FindFile( FileList[ FileIndex ], FileHandle ) then
         begin
         if OpenFile( FileHandle ) then
            begin
            if OverwriteFile( FileHandle ) then 
               begin
               if not Erase( FileHandle ) then
                  begin
                  ErrorState := FileEraseError
                  end
               end 
            else { couldn't overwrite file }
               begin
               ErrorState := FileOverwriteError
               end
            end 
         else { couldn't open file }
            begin
            ErrorState := FileOpenError
            end
         end 
      else { couldn't find file }
         begin
         ErrorState := FileFindError
         end

      end; { while }

   DeletePurgeFileList( FileList, NumFilesToPurge )

end; { PurgeFiles }

For people used to programming without gotos, this code might be easier to read than the goto version, and if you use it, you won't have to face an inquisition from the goto goon squad.

The main disadvantage of this approach is that the nesting level is deep. Very deep. Deeeeeeeep. With nesting like this, to understand the code, you have to keep the whole set of nested ifs in your mind at once. Moreover, the distance between error-processing code and code that invokes it is too far: the code that sets ErrorState to FileFindError, for example, is 23 lines from the if statement that invokes it.

With the goto version, no statement is more than four lines from the condition that invokes it. Moreover, it doesn't require that you keep the whole structure in your mind at once. You can essentially ignore any preceding conditions that were successful and focus on the next operation. For these reasons, in this case, the goto version is more readable and more maintainable than the nested-if version.

Rewrite with a Status Variable. To rewrite with a status variable (also called a state variable), create a variable that indicates whether the routine is in an error state or not. In this case, the routine already uses the ErrorState status variable, so you can use that:

Pascal Example of Code that Avoids gotos by Using a Status Variable

PROCEDURE PurgeFiles( var ErrorState: ERROR_CODE );

{ This routine purges a group of files }

var
   FileIndex:        Integer;
   FileHandle:       FILEHANDLE_T;
   FileList:         FILELIST_T;
   NumFilesToPurge:  Integer;

begin
   MakePurgeFileList( FileList, NumFilesToPurge );

   ErrorState := Success;
   FileIndex  := 0;
   while ( FileIndex < NumFilesToPurge ) and ( ErrorState = Success ) do
      begin
      FileIndex := FileIndex + 1;

      if not FindFile( FileList[ FileIndex ], FileHandle ) then
         begin
         ErrorState := FileFindError
         end;

      if ( ErrorState = Success ) then
         begin
         if not OpenFile( FileHandle ) then
            begin
            ErrorState := FileOpenError
            end
         end;

      if ( ErrorState = Success ) then
         begin
         if not OverwriteFile( FileHandle ) then 
            begin
            ErrorState := FileOverwriteError
            end
         end;

      if ( ErrorState = Success ) then
         begin
         if not Erase( FileHandle ) then
            begin
            ErrorState := FileEraseError
            end
         end

      end; { while }

   DeletePurgeFileList( FileList, NumFilesToPurge )

end; { PurgeFiles }

The advantage of the status-variable approach is that it avoids the deeply nested if-then-else structures of the first rewrite, so it's easier to understand. It also places the action following the if-then-else test closer to the test than the first rewrite and completely avoids else clauses.

Understanding the nested-if version requires substantial mental gymnastics, but this version is easier to understand because it closely models the way people think about the problem. You find the file. If everything is OK, you open the file. If everything is still OK, you overwrite the file. If everything is still OK, ...

The disadvantage of this approach is that the using status variables isn't as common a practice as it should be. Document it carefully, or some programmers might not understand the general approach. In this example, the use of well-named enumerated types helps significantly.

Comparison of Approaches

Each of the three methods has something to be said for it. The first avoids unnecessary tests and deep nesting but has gotos. The second avoids gotos but is deeply nested and gives an exaggerated picture of the logical complexity of the routine. The third avoids gotos and deep nesting but introduces extra tests.

The last approach is slighty preferable to the first two because it's more readable and models the problem better, but that doesn't make it the best approach in all circumstances. Any of these techniques works well when applied consistently to all the code in a project. Consider all the factors that have been presented, then make a project-wide decision about which method to favor in your programs.

gotos and Sharing Code in an else Clause

One challenging case in which some programmers would use a goto is the case in which you have two conditional tests and an else clause, and want to execute code in one of the conditions and the other else clause. Here's an example of a case that could drive someone to goto:

C Example of Sharing Code in an else Clause with a goto

if ( StatusOK )
   {
   if ( DataAvail )
      {
      ImportantVar = x;
      goto MID_LOOP;
      }
   }
else
   {
   ImportantVar = GetVal();

   MID_LOOP: 

   /* lots of code */
   ...
   }

This is a good example because it's logically tortuous-it's nearly impossible to read as it stands and one of the hardest cases to rewrite correctly without a goto. If you think you can easily rewrite it without gotos, ask someone to review your code! Several expert programmers have rewritten it erroneously.

You can rewrite it in several ways. You can duplicate code, put the common code in a routine and call it from two places, or retest the conditions. The rewrite won't be as fast as the original in most languages, but it will be almost as fast. Unless the code is in a really hot loop, rewrite it without thinking about efficiency.

The best rewrite is to put the /* lots of code */ part in its own routine. You can then call the routine in the places you would otherwise have used as the origin or destination of a goto and preserve the original structure of the conditional. Here's how it looks:

C Example of Sharing Code in an else Clause by Putting Common Code in a Routine

if ( StatusOK )
   {
   if ( DataAvail )
      {
      ImportantVar = x;
      DoLotsOfCode( ImportantVar );
      }
   }
else
   {
   ImportantVar = GetVal();
   DoLotsOfCode( ImportantVar );
   }

Normally, writing a new routine (or a macro in C) is the best approach. Sometimes, however, it's not practical to put duplicated code in its own routine. In this case you can work around it by restructuring the conditional so that you keep the code in it rather than in a new routine. Here's how it looks:

C Example of Sharing Code in an else Clause Without a goto

if ( (StatusOK && DataAvail) || ! StatusOK )
   {
   if ( StatusOK && DataAvail )
      ImportantVar = x;
   else
      ImportantVar = GetVal();

   /* lots of code */
   ...
   }

This is a faithful and mechanical translation of the logic in the goto version. It tests StatusOK two extra times and DataAvail one, but the code is equivalent. If retesting the conditionals bothers you, notice that the value of StatusOK doesn't need to be tested twice in the first if test. You can also drop the test for DataAvail in the second if test. Try rewriting it yourself if you want the practice.

Summary of Guidelines for Using gotos

Use of gotos is a matter of religion. My dogma is that in modern languages, you can easily replace nine out of ten gotos with equivalent structured constructs. In these simple cases, you should replace gotos out of habit. In the hard cases, you can still exorcise the goto in nine out of ten cases. In these cases, you can break the code into smaller routines; use nested ifs; test and retest a status variable; or restructure a conditional. Eliminating the goto is harder in these cases, but it's good mental exercise, and the techniques discussed in this section give you the tools to do it.

In the remaining one case out of 100 in which a goto is a legitimate solution to the problem, document it clearly and use it. If you have your rain boots on, it's not worth walking around the block to avoid a mud puddle. But keep your mind open to gotoless approaches suggested by other programmers. They might see something that you don't.

Here's a summary of guidelines for using gotos:

• Use gotos to emulate structured control constructs in languages that don't support them directly. When you emulate structured constructs, emulate them exactly. Don't abuse the extra flexibility the goto gives you.
• Don't use gotos when an equivalent structured construct is available.
• Measure the performance of any goto used to improve efficiency. In most cases that use gotos, you can recode them without gotos with improved readability and no loss in efficiency. If your case is the exception, document the efficiency improvement so that gotoless evangelists won't remove it when they see it.
• Limit yourself to one goto label per routine, unless you're emulating structured constructs.
• Limit yourself to gotos that go forward, not backward, unless you're emulating structured constructs.
• Make sure all goto labels are used. They might be a symptom of missing code, namely the code that goes to them. If they're not used, delete them.
• Make sure a goto doesn't create unreachable code.
• If you're a manager, adopt the perspective that a battle over a single goto isn't worth the loss of the war. If the programmer is aware of the alternatives and is willing to argue, the goto is probably OK.

Further Reading

These articles contain the whole goto debate. It erupts from time to time in most workplaces, textbooks, and magazines, but you won't hear anything that wasn't fully explored 20 years ago.

Dijkstra, E. "GOTO Statement Considered Harmful," Communications of the ACM, v. 11, no. 3, March 1968, pp. 147-8. This is the classic paper in which Dijkstra put the match to the paper and ignited a controversy that shows no signs of abating.

Wulf, W. A. "A Case Against the GOTO," Proceedings of the 25th National ACM Conference, August 1972, pp. 791-97. This paper was another argument against the indiscriminate use of gotos. Wulf argued that if programming languages provided adequate control structures, gotos would become largely unnecessary. Since the paper was written in 1972, languages such as Pascal, C, and Ada have proven him correct.

Knuth, Donald. "Structured Programming with go to Statements," 1974, in (Yourdon 1979), pp. 259-321. This long paper isn't entirely about gotos, but it includes a horde of examples of code that's made more efficient by eliminating gotos and another horde of examples of code that's made more efficient by adding them.

Rubin, Frank. "'GOTO Considered Harmful' Considered Harmful" (letter to the editor), Communications of the ACM, vol. 30, no. 3 (March 1987), pp. 195-6. In this rather hot-headed letter to the editor, Rubin asserts that gotoless programming has cost businesses "hundreds of millions of dollars." He then offers a code fragment that uses a goto and argues that it's superior to gotoless alternatives.

The response that the letter generated was more interesting than the letter itself. For five months, the CACM published letters that offered different versions of Rubin's original 7-line program. The letters were evenly divided between those defending gotos and those castigating them. Readers suggested roughly 17 different rewrites, and the rewritten code fully covered the spectrum of approaches to avoiding gotos. The editor of Communications of the ACM noted that the letter had generated more response by far than any other issue ever considered in pages of the CACM.

For the follow-up letters, see:

Communications of the ACM, vol. 30, no. 5 (May 1987), pp. 351-355.
Communications of the ACM, vol. 30, no. 6 (June 1987), pp. 475-478.
Communications of the ACM, vol. 30, no. 7 (July 1987), pp. 632-4.
Communications of the ACM, vol. 30, no. 8 (August 1987), pp. 659-62.
Communications of the ACM, vol. 30, no. 12 (December 1987), pp. 997, 1085.

This material is Copyright © 1993 by Steven C. McConnell. All Rights Reserved.

Code Reads #5 Knuth's "Structured Programming with go to Statements" - Scott Rosenberg's Wordyard

November 17, 2006 by Scott Rosenberg 9 Comments

This is the fifth edition of Code Reads, a weekly discussion of some of the central essays, documents and texts in the history of software. You can go straight to the comments and post something if you like. Here's the full Code Reads archive.

I have felt for a long time that a talent for programming consists largely of the ability to switch readily from microscopic to macroscopic views of things, i.e., to change levels of abstraction fluently.
– Donald Knuth, "Structured Programming with go to Statements"

We've been looking at Edsger Dijkstra's principles of structured programming for some time now. Today we'll conclude that phase of this series with a look at Donald Knuth's "Structured Programming with go to Statements" (1974). Since "Go To Statement Considered Harmful" was the most famous declaration of the structured programming ethos, Knuth's title itself was a kind of provocative joke - like naming a paper "Judaism with Idols" or "Vegetarianism with Pork Chops." And that combination of playfulness and attentive humor extends throughout the article, from the epigraphic references to Bob Dylan (and a laxative advertisement!) on. In the middle of a complex analysis of an algorithm in ALGOL, in which Knuth is reviewing ideas for new ways to notate a particular kind of loop, he interjects:

Readers who remember 1967 will also appreciate [this] second suggestion,
turn on begin S; when B drop out; T; end.

The levity's a good thing, because, I confess, as a non-mathematician and only a rudimentary programmer I approached Knuth's formula-laden text with trepidation. And there remain parts of "Structured Programming with go to Statements" that are beyond me. But for the most part, this text bears out Knuth's reputation for brilliant clarity - it's surprisingly accessible.

Knuth walks us through the history of the "go to" controversy and explores cases where eliminating "go to" doesn't really work - particularly in efforts to optimize the efficiency of little loops of code that a program must frequently repeat. A short way into the discussion, Knuth admits his own "vested interest in go to statements": They are a basic building block of the assembler code he uses for examples throughout his famous series of books on The Art of Computer Programming. Still, he's fundamentally sympathetic to Dijkstra's argument about structured programming; he just insists that the "go to" issue is a symptom, not the heart of the problem:

There has been far too much emphasis on go to elimination instead of on the really important issues; people have a natural tendency to set up an easily understood quantitative goal like the abolition of jumps, instead of working directly for a qualitative goal like good program structure…. Probably the worst mistake any one can make with respect to the subject of go to statements is to assume that "structured programming" is achieved byt writing programs as we always have and then eliminating the go to's. Most go to's shouldn't be there in the first place! What we really want is to conceive of our program in such a w3ay that we rarely even think about go to statements, because the real need for them hardly ever arises. The language in which we express our ideas has a strong influence on our thought processes. Therefore, Dijkstra asks for more new language features - structures which encourage clear thinking - in order to avoid the go to's temptations toward complications.

I appreciated Knuth's argument, but even more, his attention to the expressive power and comprehensibility of different ways of writing programs ("The word do as used in ALGOL has never sounded quite right to native speakers of English; it has always been rather quaint for us to say 'do read (A[i])' or 'do begin'!"). This sensitivity leads Knuth, in the latter part of the paper, towards the principle he would later expound in his advocacy of "literate programming": "A programmer should create a program P which is readily understood and well-documented, and then he should optimize it into a program Q which is very efficient." A go to at the second, optimized stage would be acceptable, he says, because the programmer has already expressed the program in terms that make its structure clear and allow for the removal of errors and bugs.

I don't know how widely Knuth is read today (or ever was); his attention to assembler-level code may feel distant from the concerns of the everyday developer focused on getting some mundane job done. But it seems to me that the habits of thought you can observe at work in "Structured Programming with go to Statements" - patience, precision, a willingness to examine principles from all angles and an openness to being amused - are of interest and value to anyone, in any field.

BONUS LINK: In this anecdote from Andy Hertzfeld's Macintosh Folklore site, Knuth calls Steve Jobs on his claim to have read "all" Knuth's books.

Comments

1. Amos Anan says:

   November 17, 2006 at 3:04 pm

   Reading this post I couldn't help but get the sense that the key theme was the significance of "microscopic to macroscopic," which you rightly lead (lede??) with but then don't really examine in depth.

   I've described programming to people that have never done it and think it's only for nerds or eggheads or very deep thinkers (when they're trying to be kind) as comparable to architecture, whether it be building homes or skyscrapers. I've also described programming to programmers as comparable to knitting. You may make beautiful sweaters with incredibly creative designs and patterns but after the hundredth sweater it's hard not to think of the next sweater without considering the thousands of knit 1, pearl 2′s involved. Micro versus macro applies on multiple levels of micro and macro.

   Considering the time frame of the early to mid seventies, Knuth's description of an advantage of the use of gotos was well understood. In fact C language which was created in the late '60s had already dealt with the problem you've given as an example. With nested loops and conditions calling for exiting those loops from deep within the nesting, gotos are more efficient and even more elegant than multiple test flags and testing statements. So C incorporated the "break" statement to handle that problem. Redefining "goto" in a situation where its use is valuable to something more restricted and directed to the problem was the answer. An answer given years before.

   Expertise in handling macro and micro also comes with experience, in programming and in all areas where knowledge gained is knowledge valued. Apprenticeship I think it was once called. I once taught Pascal 100 or whatever beginner's Pascal is called. I also taught a C course for students who had already had some programming experience. I was more of a free form teacher usually going into a lecture with a loose outline for the day (which I'd put on the "black board"). From there I'd let the class and lecture go where ever the interaction took it. One day in a C class I did the bubble sort. I had the class provide much of the input trying to get from them the sense of constructing an algorithm rather than looking one up. Not surprisingly, given that the base language of the school at that time was Pascal, the C sort looked like a Pascal routine. That is, it could only be used on one particular type of array. At the end of the class, when I was done, I looked at the resulting program and said, "Damn! That's a Pascal sort. It has all the weaknesses and restrictions of Pascal and none of the strengths of C. Next class we'll write a true C sort that'll sort anything of any size." Original Pascal was a teaching language. It was micro as was its intent. C was a professional language. It was macro, though it could be micro.

   But if programming is like knitting a sweater or building a home or a skyscraper, what are the differences in those levels? Micro and macro. But on many levels within there are micro and macro considerations. I was never a big fan of top down programming. I often found that the top down method was really just an outline that often was easily understood inherently and if that outline was made more detailed it still couldn't get to the core problems that would be encountered only when directly approached. This I see as the interface between the micro and macro of a problem and program. It was the same for bottom up. One built the tools to handle a problem and then one integrated them into a larger program to deal in a coordinated manner with the multiple needs the tools were built for. That integration is again the micro-macro interface.

   You describe Knuth's use of generic assembly language, but assembly language itself has evolved and has more high level language structures. And in cases where those structures aren't at a high enough level, macros can be used. The original Lotus 1-2-3 was written in assembly language but apparently a heavily macro based version. This might be thought of as a custom high level language or as an assembly language with many pre-built tools to handle the tasks involved.

   I also taught 80×86 assembly language. One of the things I described for late in the course was recursion. It was ironic for me in that when I first took programming there was a part of the course that involved simulation of recursion (Augenstein and Tenenbaum's Data Structures text – the PL/I version in those days).

   I don't think I ever got a good understanding of simulation of recursion, probably because any important "forests" were lost in the "tree" tools needed to handle the problem. The stack that had to be created and the program methods needed to use the stack and handle the simulated code were not trivial to a fairly beginner programmer.

   Ironically, the low level assembly had a stack structure built-in and so in teaching the use of that built-in structure it seemed easier to implement recursion and understand that implementation and at the same time gain some insight into the power and flexibility of assembly language. The stack structure within a chip architecture I believe was an early Intel advancement.

   An aside: I once converted the C standard library to assembly language (not that difficult in that C has assembly language output as an option). I then wrote macros to implement scanf and printf (the fundamental I/O methods in C). It was an excerise after writing an equivalent to the mainframe assembler's "Printout *" macro.

   I think all of these things I've mentioned involve the interface between micro and macro and the complexity involved. It doesn't break down into a single problem though it may involve a single method of approach to a micro-macro interface problem at hand. The gotos that Knuth doesn't like seem to be the ones that traverse the micro-macro interface – that go from one micro to another micro making the macro involved linked by spaghetti.

   …

   The other day I saw a link at Digg.com to visual demonstrations of sorting algorithms. These are excellent views of the macro of sorting where the algorithms themselves often are obscured by their micro nature.

   Visual demonstration of various sorting algorithms:
   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

   And:
   http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

   I remember years ago writing a program that printed out the swapping of rings for the Towers of Hanoi problem. This was on a main frame line printer with each page showing a swapped ring. A sort of flip card animation. :P

   Micro versus macro. Giving people a clear understanding of the intricacies of programming and the skyscrapers they can create – with escalators and high speed elevators.

2. David Carlton says:

   November 17, 2006 at 10:04 pm

   I read this (along with other articles collected in his Literate Programming volume) a bit over a year ago; it was fascinating. Really interesting, well thought out, well written, but I could only dimly imagine the context he was coming from. There seemed to be strange restrictions at play that I could only guess at – otherwise, the arguments made very little sense to me. So my main reaction was "I hope programming languages change for the better as much over the next thirty years as they have over the last thirty".

   But, despite that, there were some wonderful hints of the world to come. My favorite was the possibility of automated refactoring tools, which took a couple of decades to appear, and which still aren't as widely available as I'd like.

3. Brian Slesinsky says:

   November 18, 2006 at 12:48 am

   It was pretty obvious why you'd picked the earlier articles in this series, but I wasn't so sure about this one. It's a well-written account of what it was like during the transition to structured programming, but at first it seemed to be concerned with things we've largely moved beyond.

   One claim to fame is that this seems to be the paper where Knuth famously repeated that "premature optimization is the root of all evil." His criticism of programmers who over-optimize at the expense of readability makes as much sense today as then, as does his warning that one shouldn't guess at what part of the program needs to be optimized.

   But ironically, much of the paper is about techniques that we now consider premature optimization. Improvements to compilers have made many optimizations obsolete. The tradeoff is that they also make it very difficult to reason with much accuracy about what effect a change in a program will make to its performance. Instead, we write benchmarks and do experiments on real machines.

4. Jim Jinkins says:

   November 19, 2006 at 5:21 am

   I enjoyed Knuth's exploration of language features that would help in writing clear and efficient code by taming the generalized goto statement. They are still worth reading today, even after language designers seem to have converged on break and continue statements to control loops.

   I wish he had added a section titled "PL/I exceptions considered harmful." It might have shortened the time until new languages tamed the generalized exception statement.

5. Cleo Saulnier says:

   November 22, 2006 at 12:29 pm

   I like hardware and assembler programming and I thought Knuth's paper was tedious to get through. I read it a while back and from what I remember, it was a constant battle between high level construction and low level optimizations. If there was any way to describe it, I'd apply Joel Spolsky's leaky abstraction where low level details seep up to the top.

   I think Knuth was trying to say that there shouldn't be any reason why you can't use high level constructs, but it shouldn't be at the cost of simple optimizations. Note that this goes beyond what compilers can provide. But current languages are all or nothing. You can't build software and then use the fastest implementations. Current software has both design and implementation together and so we are constantly fighting two extremes. This is the wrong way and Knuth's paper is just another example in the long list of items wrong with software development. (Note that "interfaces" do not solve the implementation vs. design problem. It just makes it worse.)

6. saba says:

   December 16, 2006 at 11:20 pm

   i want a project in pascal language about matrixes.

   please guide me …

   many thanks.

   saba

7. Joel Neely says:

   December 19, 2006 at 10:16 am

   Knuth's paper still has some important lessons, the most important of which is to avoid swinging between extremes and holding on to older ideas, two themes that characterize much of the history of computing (and science in general). I've seen both Paul Dirac and Max Planck credited with the statement that quantum mechanics would become the standard model in physics only when all of the old physicists had died. In one sense we've learned much since 1974, and in another sense we've learned very little.

   In the earliest days of the field, computers were expensive, rare, slow, and limited in capacity. Much effort was spent in micro-optimizing to squeeze the maximum benefit out of the beast. Unfortunately, since the next generation of programmers was taught by the first, that obsession continued even after some of the most severe constraints began to ease. I'm referring here to the mentality that almost instinctively prefers to write the equivalent of "a = b

8. Joel Neely says:

   December 19, 2006 at 10:18 am

   The breakage above occurred when I wrote two consecutive less-than symbols to indicate left_shift. Apparently WordPress doesn't like that. With apologies for the partial duplication, let me re-submit the complete post, with the offending characters replaced by words!

   Knuth's paper still has some important lessons, the most important of which is to avoid swinging between extremes and holding on to older ideas, two themes that characterize much of the history of computing (and science in general). I've seen both Paul Dirac and Max Planck credited with the statement that quantum mechanics would become the standard model in physics only when all of the old physicists had died. In one sense we've learned much since 1974, and in another sense we've learned very little.

   In the earliest days of the field, computers were expensive, rare, slow, and limited in capacity. Much effort was spent in micro-optimizing to squeeze the maximum benefit out of the beast. Unfortunately, since the next generation of programmers was taught by the first, that obsession continued even after some of the most severe constraints began to ease. I'm referring here to the mentality that almost instinctively prefers to write the equivalent of "a = b left_shift 2 + b" instead of "a = b * 5″ because "everybody knows that shift-and-add is faster than multiplication". Bottom-up thinking was the order of the day.

   Dijkstra, Hoare, and others encouraged us to think first at a high level about what needed to be accomplished and only afterwards concern ourselves with implementation. Some practitioners dismissed their advice as impractical, while the snake-oil salesmen trivialized their vision into catch-phrases such as "don't use go-to statements".

   Knuth argued eloquently and forcefully that the middle road was more appropriate for the practitioner than pushing to either extreme, but he also argued clearly for applying the right level of hack-the-code-for-speed depending on context. Although the development pattern of "build it, profile it, and only then tweak the critical hot spots" has been on the table now for over thirty years, it still isn't treated as the standard model!

   On the other hand, probably the best measure of how far we've come is to take the code fragments Knuth discusses and rewrite them for oneself in a contemporary language. His anecdote on challenging Val Schorre to write an eight-queens program without go-to statements is fascinating, considering that a good first-year computing science student would be expected to do that as a simple homework assignment these days.

   As a side note, in the early 70s I worked on a system (Burroughs B-1700 series) which was years ahead of its time. We would now refer to that system as a 24-bit RISC processor, with multiple virtual machines as part of the system software (one for each programming language: COBOL, FORTRAN, etc.) The operating system was written in an Algol-like high-level language called SDL. That language's virtual machine had some very interesting ideas which relate to our discussion of Knuth's paper.

   One of these was to recognize that in-line blocks could be transformed into anonymous, no-argument procedures. (Since these procedures were in the same lexical scope as the surrounding code, entry and exit required only a simple stack-based manipulation of the program counter, not the full set of mechanisms required for functions with arguments and returned values.)

   For example (using C/Java-like notation for familarity):

   if (conditional_expression) {
   sequence_of_statements_for_true
   } else {
   sequence_of_statements_for_false
   }

   contains two blocks that would be compiled into these out-of-line lightweight procedures. The if-then-else construct itself was compiled into code that would evaluate the conditional_expression (leaving a boolean on top of the virtual machine stack), followed by a two-argument op-code whose arguments were simply the references to those procedures.

   "Falling through" such a block simply returned to the next instruction past the point of invocation, in similar fashion to falling out of a void function/method in C/Java.

   An interesting consequence of this approach was that the equivalent of the C/Java "break" statement was understood simply as exiting an anonymous procedure! This could be used in any context where one had written a code block: loops, conditionals, or even in-line blocks.

   I still recall the mental shift of thinking of a block as a mechanism intended to accomplish a result, and exiting that block as acknowledging that the result had been achieved (rather than simply as jumping around in the source code). I remain impressed by the extent to which our chosen metaphors both encourage some lines of thought and inhibit others, and by how much we need people such as Dijkstra, Hoare, and Knuth who challenge us to find new metaphors and consider what that shift in thinking might allow us to do.

9. hiutopor says:

Knuth, goto, Python, and OOP by Ben

April 9, 2009, | The Brush Blog

The year was 1973. Real programmers were still using punch-cards and Pascal. C had barely been invented, and object-oriented programming was hardly a twinkle even in the eyes of top computer scientists. Whether or not to use goto was the hot topic of the day.

Knuth It was then that Donald Knuth wrote his famous essay Structured Programming with go to Statements. And some essay it is: he covers everything from the current trends on structured programming to premature optimization being the root of all evil. (I read it in Literate Programming, but it's also available as a scanned PDF here.)

He's responding to Edsger Dijkstra's well-known letter Go To Statement Considered Harmful, but (in typical Knuth fashion) he covers so much related ground it's not funny.

What was striking to me is the context of his discussion. It's clear that structured programming - which we use every day and think is "common sense" - had to be invented, discussed, and refined. Like most inventions, it's obvious … 36 years later.

goto It's also obvious that goto (or "go to" as Knuth calls it) was much more widely used and abused than it is today. This is probably partly because assembly language was so much more common, but also because "they" had to learn that goto isn't usually the right abstraction - in fact, it isn't much of an abstraction at all.

Now it's 2009, and goto is pretty rare. It's still used, of course, but I've usually seen it only in the cases Knuth is talking about: for efficiency, error exits, and for breaking out of certain kinds of loops.

In C you still occassionally need it for cleaning up before error exits, or for breaking out of efficient nested loops, or in generated code, but these days we also have other constructs and other languages that solve 1973′s problems most of the time.

In C, you have the invaluable break as well as the ability to return early. Knuth advocated the equivalent of C's break, implying also that most languages at the time didn't have it.

Compilers are also somewhat better at producing optimized code from non-gotoed source: for example, I can program my virtual machine's opcode dispatcher as a bunch of case statements, knowing the compiler will probably optimize it into a jump table.

And in most modern high-level languages (C++ and up) you have exceptions, which eliminate the need for error-exit gotos, as well as solve several other problems in a really tidy way.

Python Python is important in this discussion not only because Knuth is keen on beautiful code, but because Knuth "predicted" its arrival in several different ways. Here's a quote from the last section of his essay:

It seems clear that languages somewhat different from those in existence today would enhance the preparation of structured programs. We will perhaps eventually be writing only small modules which are identified by name as they are used to build larger ones, so that devices like indentation, rather than delimiters, might become feasible for expressing local structure in the source language.

Of course, many languages now have "small modules which are identified by name as they are used to build larger ones", but Python really took Knuth seriously about using indentation as a delimiter.

What's more, you can always add goto to Python if you really need it. :-)

OOP And it gets even more interesting when he goes on to say:

Although our examples don't indicate this, it turns out that a given level of abstraction often involves several related routines and data definitions; for example, when we decide to represent a table in a certain way, we simultaneously want to specify the routines for storing and fetching information from that table. The next generation of languages will probably take into account such related routines.

Correct me if I'm wrong, but doesn't that sound awfully like OOP? So in a single essay apparently about goto statements, Knuth predicted modules, Python's use of indentation as delimiters, and object-oriented programming. :-)

9 comments and pings (oldest first) Marius 9 Apr 2009, 21:24 link object-oriented programming was hardly a twinkle even in the eyes of top computer scientists

Object oriented programming was invented by Simula in the 1960′s and standardized in 1967.

Jason Dusek 10 Apr 2009, 00:16 link "several related routines and data definitions" sounds like typed programming to me.

How can you in good faith propose that Knuth predicted Python's arrival with indentation and small modules, features that are hardly unique to it? You might as well have said that Knuth predicted Haskell. His prediction would be mighty flexible in that case!

How can you talk about indentation without mentioning Landin's ISWIM (1966)?

Alexander Fairley 10 Apr 2009, 03:11 link That's the way that interpreting prophecy works, Jason. Whatever you have done, claim the prophet foretold it :P .

Ben 10 Apr 2009, 07:53 link Marius, as I mentioned on prog.reddit: I knew about Simula ('67, no less). However, Knuth and other "top computer scientists" don't seem to talk about it. Perhaps it wasn't well-known in the U.S. by 1973. Perhaps OOP was known and used, but not by that name.

Jason, about the "prediction" of Python: I was being fairly tongue-in-cheek about the modules and OOP, hence the quotes around my first "prediction". (I've added a smiley at the end to clarify.) However, I think the indentation thing is quite striking - more or less a prophecy.

Here's an article by Jeremy Hylton about Python, Knuth and indentation which also mentions Landin's ISWIM: Using indentation to represent program structure

Marius 13 Apr 2009, 08:07 link I hate to be the nitpicker here, but I searched for "knuth" and "Simula" and got this paper :-)

http://www.tug.org/TUGboat/Articles/tb23-3-4/tb75knuth.pdf

Quote:

"Professor Knuth has a long-lasting and close relationship relationship to Norway. In '67 he came to an IFIP conference in Oslo where, among other things, SIMULA67 was presented. He spent the academic year '72–73 at the Univerity of Oslo, and this visit was influential for further development of computer science in Norway."

Ben 14 Apr 2009, 08:13 link Thanks Marius, that's very interesting. I definitely stand corrected about it not being well-known in the U.S., particularly by Knuth. I still wonder why he doesn't mention it in his discussion of structured programming. Do you know when the term "object-oriented programming" was invented, or came into common usage?

Marius 15 Apr 2009, 08:21 link I don't know, but I know that it was used when describing Smalltalk.

Ping: LCD Points of Interest Ca… 21 Apr 2009, 14:46 link [...] Finally, one last addition to list of intricacies of the 4DGL language. "Break" statements do not function as in C, where the program jumps out of only the inner-most loop. In 4DGL, "Break" statements exit from all loops, making "Goto" statements necessary if one wishes to only exit the inner-most loop. While I try to avoid "Goto" statements as much as possible, I think Knuth may still approve of my use of "Goto." [...]

Gremnebulin 14 Feb 2011, 05:42 link Occam used indentation a decade before Python.

Recommended Links

Softpanorama Recommended

Top articles

Sites

• considered harmful
• Structured programming - Wikipedia, the free encyclopedia
• Control flow - Wikipedia, the free encyclopedia
• Loop Exits and Structured Programming: Reopening the Debate Eric S. Roberts
  Department of Computer Science
  Stanford University

• STRUCTURED PROGRAMMING CONSIDERED HARMFUL P Abrahams, ACM SIGPLAN Notices - 1975
• Control Flow Statements -- from the official Sun Java Tutorial by Mary Campione and Kathy Walrath
• Flow Control Statements - note on translation of control statements into machine code
• Control statement in programming languages
• Why are some people opposed to using the goto statement?

Some examples of "considered harmful" movement ;-)

• CSH PROGRAMMING CONSIDERED HARMFUL -- A popular "considered harmful" article.
• Interface Pointers Considered Harmful - Don Box -- another example
• mod_perl Archives Re Global variables considered harmful -- now for USENET newsgroup

Other links

• Control Structures
• Why OOP - Contents -- "Why Object-Oriented really is better than Structured" by Gary Warren King

C. Böhm and G. Jacopini, "Flow Diagrams, Turing Machines, and Languages with Only Two Formation Rules", Communications of the ACM 9
(1966), pp. 366-371.

E. W. Dijkstra, "Goto Statement Considered Harmful", Communications of the ACM 11 (1968), pp. 147-148.

E. W. Dijkstra, "Guarded Commands, Nondeterminacy and Formal Derivation of Programs", Communications of the ACM 18, (1975), pp. 453-457.

E. W. Dijkstra, "Notes on Structured Programming", in Dahl, Dijkstra and Hoare, Structured Programming, Academic Press, 1972, pp. 1-82.

• E.W. Dijkstra Archive What led to Notes on Structured Programming (EWD1308)

D. E. Knuth, "Structured Programming with Goto Statements", ACM Computing Surveys 6 (1974), pp. 261-302.

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March, 12, 2019