StructuredProgrammingwithgotoStatements资源-CSDN文库

Structured

Programming

需积分: 9 194 浏览量 2008-09-28 16:02:04 上传评论 1 收藏 2.88MB PDF 举报

资源推荐

资源详情

资源评论

Structured Programming with go to Statements

DONALD E. KNUTH

Stanford University, Stanford, California 9~S05

A consideration of several different examples sheds new light on the problem of ereat-

ing reliable, well-structured programs that behave efficiently. This study focuses

largely on two issues: (a) improved syntax for iterations and error exits, making it

possible to write a larger class of programs clearly and efficiently without

go to

state-

ments; (b) a methodology of program design, beginning with readable and correct,

but possibly inefficient programs that are systematically transformed if necessary into

efficient and correct, but possibly less readable code. The discussion brings out op-

posing points of view about whether or not

go to

statements should be abolished;

some merit is found on both sides of this question. Fina!ly, an attempt is made to

define the true nature of structured programming, and to recommend fruitful direc-

tions for further study.

Keywords and phrases:

structured programming,

go to

statements, language design,

event indicators, recursion, Boolean variables, iteration, optimization of programs,

program transformations, program manipulation systems searching, Quieksort,

efficiency

CR categories:

4.0, 4.10, 4.20, 5.20, 5.5, 6.1 (5.23, 5.24, 5.25, 5.27)

You may go when you will go,

And I will stay behind.

--Edna St. Vincent Millay

[66]

Most likely you go your way and I'll go mine.

--Song title by Bob Dylan

[33]

Do you suffer from painful elimination?

--Advertisement, J. B. Williams Co.

INTRODUCTION

A revolution is taking place in the way we

write programs and teach programming, be-

cause we are beginning to understand the

associated mental processes more deeply. It

is impossible to read the recent book

Struc-

tured programming

[17; 55] without having it

This research was supported in part by the Na-

tional Science Foundation under grant number

GJ 36473X, and by IBM Corporation.

change your life. The reasons for this revolu-

tion and its future prospects have been aptly

described by E. W. Dijkstra in his 1972 Tur-

ing Award Lecture, "The Humble Program-

mer" [27l.

As we experience this revolution, each of

us naturally is developing strong feelings one

way or the other, as we agree or disagree

with the revolutionary leaders. I must admit

to being a nomhumble programmer, egotisti-

but

not for profit, all or part of this material is granted, provided that ACM's copyright notice is

given and that reference is made to this publication, to its date of issue, and to the fact that reprint-

ing privileges were granted by permission of the Association for Computing Machinery.

Computing Surveys, V?L 6, No. 4, Dee, ember 1974

262 ,

Donald E. Knuth

CONTENTS

INTRODUCTION

1. ELIMINATION OF

so to

STATEMENTS

Historical Background

A Searching Example

Efficiency

Error

Exits

Subscript Checking

Hash Coding

Text Scanning

A Confession

Tree Searching

Systematic Elimination

Event

Indicators

Comparison of Features

Simple Iterations

2. INTRODUCTION OF

so to

STATEMENTS

Recursion Elimination

Program Manipulation Systems

Reeursion vs. Iteration

Boolean Variable Elimination

Coroutines

Quicksort : A Digression

Axiomatics of Jumps

Reduction of Complication

3. CONCLUSIONS

Structured Programming

With

go to

Statements

Efficiency

The

Future

ACKNOWLEDGMENTS

APPENDIX

BIBLIOGRAPHY

eal enough to believe that my own opinions

of the current treads are not a waste of the

reader's time. Therefore I want to express in

this article several i of the things that struck

me most forcefully as I have been thinking

about structured programming during the

last year; several of my blind spots were re-

moved as I ivas learning these things, and I

hope I can convey some of my excitement to

the reader. Hardly any of the ideas I will

discuss are my own; they are nearly all the

work of others, but perhaps I may be pre-

senting them in a new light. I write this

article in the first person to emphasize the

fact that what I'm saying is just one man's

opinion; I don't expect to persuade everyone

that my present views are correct.

Before beginning a more technical discus-

sion. I should confess that the title of this

article was chosen primarily to generate

attention. There are doubtless some readers

who are convinced that abolition of go

statements is merely a fad. and they may see

this title and think, "Aha! Knuth is rehabili-

tating the go to statement, and we can go

back to our old ways of programming

again." Another class of readers will see the

heretical title and think, "When are die-

hards like Knuth going to get with it?" I

hope that both classes of people will read on

and discover that what I am really doing is

striving for a reasonably well balanced view-

point about the proper role of go to state-

ments. I argue for the elimination of go to's

in certain cases, and for their introduction in

others.

I believe that by presenting such a view I

am not in fact disagreeing sharply with

Dijkstra's ideas, since he recently wrote the

following: "Please don't fall into the trap of

believing that I am terribly dogmatical

about [the go to statement]. I have the

uncomfortable feeling that others are making

a religion out of it, as if the conceptual

problems of programming could be solved by

a single trick, by a simple form of coding

discipline!" [29]. In other words, it, seems

that fanatical advocates of the New Pro-

gramming are going overboard in their strict

enforcement of morality and purity in

programs. Sooner or later people are going

to find that their beautifully-structured

Computing

Surveys, Vol. 6, No. 4, December 1974

Structured Programming with go to Sta~ment~

programs are running at only half the speed

--or worse--of the dirty old programs they

used to write, and they will mistakenly blame

the structure instead of recognizing what is

probably the real culprit--the system over-

head caused by typical compiler implementa-

tion of Boolean variables and procedure calls.

Then we'll have an unfortunate counter-

revolution, something like the current rejec-

tion of the "New Mathematics" in reaction

to its over-zealous reforms.

It may be helpful to consider a further

analogy with mathematics. In 1904, Bert-

rand Russell published his famous paradox

about the set of all sets which aren't mem-

bers of themselves. This antinomy shook the

foundations of classical mathematical rea-

soning, since it apparently brought very

simple and ordinary deductive methods into

question. The ensuing crisis led to the rise

of "intuitionist logic", a school of thought

championed especially by the Dutch mathe-

matician, L. E. J. Brouwer; intuitionism

abandoned all deductions that were based on

questionable nonconstructive ideas. For a

while it appeared that intuitionist logic

would cause a revolution in mathematics.

But the new approach angered David Hil-

bert, who was perhaps the leading mathema-

tician of the time; Hilbert said that "For-

bidding a mathematician to make use of the

principle of the excluded middle is like

forbidding an astronomer his telescope or a

boxer the use of his fists." He characterized

the intuitionist approach as seeking "to

save mathematics by throwing overboard

all that is troublesome .... They would chop

up and mangle the science. If we would

follow such a reform as they suggest, we

could run the risk of losing a great part of our

most valuable treasures" [80, pp. 98-99,

148-150, 154-157, 184-185, 268-270].

Something a little like this is happening

in computer science. In the late 1960's we

witnessed a "software crisis", which many

people thought was paradoxical because

programming was supposed to be so easy.

As a result of the crisis, people are now be-

ginning to renounce every feature of pro-

gramming that can be considered guilty by

virtue of its association with difficulties. Not

only go to statements are being questioned;

* 263

we also hear complaints about floating-point

calculations, global variables, semaphores,

pointer variables, and even assignment

statements. Soon we might be restricted to

only a dozen or so programs that are suffi-

ciently simple to be allowable; then we will

be almost certain that these programs

cannot lead us into any trouble, but of

course we won't be able to solve many

problems.

In the mathematical ease, we know what

happened: The intuitionists taught the other

mathematicians a great deal about deductive

methods, while the other mathematicians

cleaned up the classical methods and even-

tually "won" the battle. And a revolution

did, in fact, take place. In the computer

science case, I imagine that a similar thing

will eventually happen: purists will point the

way to clean constructions, and others will

find ways to purify their use of floating-point

arithmetic, pointer variables, assignments,

etc., so that these classical tools can be used

with comparative safety.

Of course all analogies break down, includ-

ing this one, especially since I'm not yet

conceited enough to compare myself to

David Hilbert. But I think it's an amusing

coincidence that the present programming

revolution is being led by another Dutchman

(although he doesn't have extremist views

corresponding to Brouwer's); and I do

consider assignment statements and pointer

variables to be among computer science's

"most valuable treasures!'.

At the present time I think we are on the

verge of discovering at last what program-

ming languages should really be like. I look

forward to seeing many responsible experi-

ments with language design during the next

few years; and my dream is that by 1984 we

will see a consensus developing for a really

good programming language (or, more likely,

a coherent family of languages). Further-

more, I'm guessing that people will become

so disenchanted with the languages they are

now using--even COBOL and FORTrAN--

that this new language, UTOPXA 84, will have

a chance to take over. At present we are far

from that goal, yet there are indications

that such a language is very slowly taking

shape.

Computing Surveys, Vol. 6, No. 4, December 1974

264 •

Donald E. Knuth

Will UTOPIA 84, or perhaps we should call

it NEWSPEAK, contain go to statements? At

the moment, unfortunately, there isn't even

a consensus about this apparently trivial

issue, and we had better not be hung up on

the question too much longer since there are

only ten years left.

I will try in what follows to give a reason-

ably comprehensive survey of the go to

controversy, arguing both pro and con, with-

out taking a strong stand one way or the

other until the discussion is nearly complete.

In order to illustrate different uses of go to

statements, I will discuss many example

programs, some of which tend to negate the

conclusions we might draw from the others.

There are two reasons why I have chosen to

present the material in this apparently

vacillating manner. First, since I have the

opportunity to choose all the examples, I

don't think it's fair to load the dice by select-

ing only program fragments which favor one

side of the argument. Second, and perhaps

most important, I tried this approach when I

lectured on the subject at UCLA in Feb-

ruary, 1974, and it worked beautifully:

nearly everybody in the audience had the

illusion that I was largely supporting his or

her views, regardless of what those views

were !

1. ELIMINATION OF go to STATEMENTS

Historical Background

At the IFIP Congress in 1971 I had the

pleasure of meeting Dr. Eiichi Goto of

Japan, who cheerfully complained that he

was always being eliminated. Here is the

history of the subject, as far as I have been

able to trace it.

The first programmer who systematically

began to avoid all labels and go to state-

ments was perhaps D. V. Schorre, then of

UCLA. He has written the following account

of his early experiences [85]:

Since the summer of 1960, I have been writing

programs in outline form, using conventions of

indentation to indicate the flow of control. I

have never found it necessary to take excep-

tion to these conventions by using

go state-

ments.

I used to keep these outlines as original

documentation of a program, instead of using

flow charts... Then I would code the pro-

gram in assembly language from the outline.

Everyone liked these outlines better than

the

flow charts I had drawn before, which

were

not very neat--my flow charts had been

nick-named "balloon-o-grams".

He reported that this method made programs

easier to plan, to modify and to check out.

When I met Schorre in 1963, he told me of

his radical ideas, and I didn't believe they

would work. In fact, I suspected that it was

really his rationalization for not finding an

easy way to put labels and go to statements

into his META-II subset of ALGOL [84], a

language which I liked very much except for

this omission. In 1964 I challenged him to

write a program for the eight-queens prob-

lem without using go to statements, and he

responded with a program using recursive

procedures and Boolean variables, very much

like the program later published independ-

ently by Wirth [96].

I was still not convinced that all go

statements could or should be done away

with, although I fully subscribed to Peter

Naur's observations which had appeared

about the same time [73]. Since Naur's

comments were the first published remarks

about harmful go to's, it is instructive to

quote some of them here:

If you look carefully you will find that surpris-

ingly often a

go to

statement which looks back

really is a concealed for statement. And you

will be pleased to find how the clarity of the

algorithm improves when you insert the

for

clause where it belongs .... If the purpose [of

a programming course] is to teach ALGOL pro-

gramming, the use of flow diagrams will do

more harm than good, in my opinion.

The next year we find George Forsythe

also purging go to statements from algo-

rithms submitted to

Communications of the

ACM

(cf. [53]). Incidentally. the second

example program at the end of the original

ALGOL 60 report [72] contains four go

statements, to labels named AA, BB, CC,

and DD, so it is clear that the advantages of

ALGOL'S control structures weren't fully

perceived in 1960.

In 1965, Edsger Dijkstra published the

following instructive remarks [21]:

Two programming department managers from

Computing Surveys, Vol. 6, No. 4,

December 1974

Structured Programming with go to Statements

different countries and different backgrounds

--the one mainly scientific, the other mainly

commercial--have communicated to me, in-

dependently of each other and on their own

initiative, their observation that the quality

of their programmers was inversely propor-

tional to the density of goto statements in

their programs .... I have done various pro-

gramming experiments.., in modified ver-

sions of ALGOL 60 in which the goto statement

was abolished .... The latter versions were

more difficult to make: we are so familiar with

the jump order that it requires some effort to

forget it! In all cases tried, however, the

program without the goto statement turned

out to be shorter and more lucid.

A few months later, at the ACM Pro-

gramming Languages and Pragmatics Con-

ference, Peter Landin put it this way [59]:

There is a game sometimes played with ALGOL

60 programs--rewriting them so as to avoid

using

go to

statements. It is part of a more

embracing game--reducing the extent to

which the program conveys its information by

explicit sequencing .... The game's signifi-

cance lies in that it frequently produces a

more "transparent" program---easier to

understand, debug, modify, and incorporate

into a larger program.

Peter Naur reinforced this opinion at the

same meeting [74, p. 179].

The next chapter in the story is what many

people regard as the first, because it made the

most waves. Dijkstra submitted a short

article to Communications of the ACM, de-

voted entirely to a discussion of go to state-

meats. In order to speed publication, the

editor decided to publish Dijkstra's article

as a letter, and to supply a new title, "Go to

statement considered harmful". This note

[23] rapidly became well-known; it expressed

Dijkstra's conviction that go to's "should

be abolished from all 'higher level' program-

ming languages (i.e., everything except,

perhaps, plain machine code) .... The go

statement as it stands is just too primitive;

it is too much an invitation to make a mess of

one's program." He encouraged looking for

alternative constructions which may be

necessary to satisfy all needs. Dijkstra also

recalled that Heinz Zemanek had expressed

doubts about go to statements as early as

1959; and that Peter Landin, Christopher

Strachey, C. A. R. Hoare and others had

been of some influence on his thinking.

• 265

By 1967, the entire XPL compiler had

been written by McKeeman, Homing, and

Wortman, using go to :only once ([65], pp.

365-458; the go to is on page 385). In 1971,

Christopher Strachey [87] reported that "It

is my aim to write programs with no labels.

I am doing quite well. I have got the operat-

ing system down to 5 labels and I am plan-

ning to write a compiler with no labels at

all." In 1972, an entire session of the ACM

National Conference was devoted to the

subject [44; 60; 100]. The December, 1973,

issue of Datamation featured five articles

about structured programming and elimina-

tion of go to's [3; 13; 32; 64; 67]. Thus, it is

clear that sentiments against go to state-

ments have been building up. In fact, the

discussion has apparently caused some

people to feel threatened; Dijkstra once told

me that he actually received '% torrent of

abusive letters" after publication of his

article.

The tide of opinion first hit me personally

in 1969, when I was teaching an introductory

programming course for the first time. I

remember feeling frustrated on several

occasions, at not seeing how to write pro-

grams in the new style; I would run to Bob

Floyd's office asking for help, and he usually

showed me what to do. This was the genesis

of our article [52] in which we presented two

types of programs which did not submit

gracefully to the new prohibition. We found

that there was no way to implement certain

simple constructions wit h while and condi-

tional gtatemeats substituted for go to's,

unless extra computation was specified.

During the last few years several languages

have appeared in which the designers

proudly announced that they have abolished

the go to statement. Perhaps the most

prominent of these is Brass [98], which

originally replaced go to's by eight so-called

"escape" statements. And the eight weren't

even enough; the authors wrote, "Our

mistake was in assuming that there is no

need for a label once the go to is removed,"

and they later [99, 100] added a new state-

ment "leave (label)

with

(expression)"

which goes to the place after the statement

identified by the (label). Other go to-less

languages for systems programming have

Computing Surveys, VoL 6, No. 4,

December 1974

剩余40页未读，继续阅读

评论收藏

内容反馈

zhengbaozhong

粉丝: 0
资源: 12

Structured Programming with go to Statements

Structured Programming with C++ 无水印pdf

Structured Programming with C++ (2015年，英文版）

05 - Structured Programming vs Obejct Oriented Programming.pdf

Structured Programming

Structured Programming Function

Structured Parallel Programming - Patterns for Efficient

Erlang - Structured Programming Using Processes

使用C ++进行结构化编程（Kjell Backman）Structured Programming with C++ (Kjell Backman)

Professional XMPP Programming with JavaScript and jQuery.pdf

Object- Oriented Programming with Ansi-C

Modular Programming with Python

Basic Structured Grid Generation With an Introduction to Unstructured Grid Generation

Guideline for structured programming in C

structured parallel programming

C++ by Example UnderC Learning Edition.pdf

Structured Parallel Programming - Patterns for Efficient Computation

Practical C++ Programming C++编程实践

课程3--Structured Programming.ppt

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）