12. 12
Go To Statement Considered Harmful
(By E. Dijkstra)
Go To Statement Considered Harmful
Key Words and Phrases: go to statement, jump instruction,
branch instruction, conditional clause, alternative clause, repet-
itive clause, program intelligibility, program sequencing
CR Categories: 4.22, 5.23, 5.24
EDITOR :
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 state-
ment should be abolished from all "higher level" programming
languages (i.e.everything except, perhaps, plain machine Code).
At'that time I did not attach too much importance to this dis-
covery; I now submit my considerations for publication because
in very recent discussions in which the subject turned up, I have
been urged to do so.
My firstremark is that, although the programmer's activity
ends when he has constructed a correct program, the process
taking place under control of his program is the true subject
matter of his activity,for it is this process that has to accomplish
the desired effect;it is this process that in its dynamic behavior
has to satisfythe desired specifications.Yet, once the program has
been made, the "making" of the corresponding process is dele-
gated to the machine.
My second remark is that our intellectualpowers are rather
geared to master staticrelations and that our powers to visualize
processes evolving in time are relatively poorly developed. For
that reason we should do (as wise programmers aware of our
limitations) our utmost to shorten the conceptual gap between
the static program and the dynamic process, to make the cor-
respondence between the program (spread out in text space) and
the process (spread out in time) as trivialas possible.
Let us now consider how we can characterize the progress of a
process. (You may think about this question in a very concrete
manner: suppose that a process, considered as a time succession
of actions, is stopped after an arbitrary action, what data do we
have to fix in order that we can redo the process until the very
same point?) If the program text is a pure concatenation of, say,
assignment statements (forthe purpose of thisdiscussion regarded
as the descriptions of single actions) it issufficientto point in the
program text to a point between two successive action descrip-
tions. (In the absence of go to statements I can permit myself the
syntactic ambiguity in the last three words of the previous sen-
tence: if we parse them as "successive (action descriptions)" we
mean successive in text space; if we parse as "(successive action)
descriptions" we mean successive in time.) Let us call such a
pointer to a suitable place in the text a "textual index."
When we include conditional clauses (ifB then A), alternative
clauses (if B then AZ else A2), choice clauses as introduced by
C. A. R. Hoare (case[i]of(At, A2, ... ,An)), or conditional expres-
sions as introduced by J. McCarthy (Bi -~ El, B2 --~E2, ... ,
Bn ---~En), the fact remains that the progress of the process re-
mains characterized by a single textual index.
As soon as we include in our language procedures we must admit
that a single textual index is no longer sufficient.In the case that
a textual index points to the interior of a procedure body the
dynamic progress isonly characterized when we alsogive to which
call of the procedure we refer.With the inclusion of procedures
we can characterize the progress of the process via a sequence of
textual indices, the length of this sequence being equal to the
dynamic depth of procedure calling.
Let us now consider repetitionclauses (like,while B repeat A
or repeat A until B). Logically speaking, such clauses are now
superfluous, because we can express repetition with the aid of
recursive procedures. For reasons of realism I don't wish to ex-
clude them: on the one hand, repetition clauses can be imple-
mented quite comfortably with present day finite equipment; on
the other hand, the reasoning pattern known as "induction"
makes us well equipped to retain our intellectual grasp on the
processes generated by repetition clauses. With the inclusion of
the repetition clauses textual indices are no longer sufficient to
describe the dynamic progress of the process. With each entry into
a repetition clause, however, we can associate a so-called "dy-
namic index," inexorably counting the ordinal number of the
corresponding current repetition. As repetition clauses (just as
procedure calls) may be applied nestedly, we find that now the
progress of the process Can always be uniquely characterized by a
(mixed) sequence of textual and/or dynamic indices.
The main point is that the values of these indices are outside
programmer's control; they are generated (either by the write-up
of his program or by the dynamic evolution of the process) whether
he wishes or not. They provide independent coordinates in which
to describe the progress of the process.
Why do we need such independent coordinates? The reason
is--and this seems to be inherent to sequentiM processes--that
we can interpret the value of a variable only with respect to the
progress of the process. If we wish to count the number, n say, of
people in an initially empty room, we can achieve this by increas-
ing n by one whenever we see Someone entering the room. In the
in-between moment that we have observed someone entering the
room but have not yet performed the subsequent increase of n,
its value equals the number of people in the room minus one!
The unbridled use of the go to statement has an immediate
consequence that it becomes terribly hard to find a meaningful set
of coordinates in which to describe the process progress. Usually,
people take into account as well the values of some well chosen
variables, but this is out of the question because it is relative to
the progress that the meaning of these values is to be understood l
With the go to statement one can, of course, still describe the
progress uniquely by a counter counting the number of actions
performed since program start (viz. a kind of normalized clock).
The difficulty is that such a coordinate, although unique, is utterly
unhelpful. In such a coordinate system it becomes an extremely
complicated affair to define all those points of progress where,
say, n equals the number of persons in the room minus onet
The go to statement as it stands is just too primitive; it is too
much an invitation to make a mess of one's program. One can
regard and appreciate the clauses considered as bridling its use. I
do not claim that the clauses mentioned are exhaustive in the sense
that/hey will satisfy all needs, but whatever clauses are suggested
(e.g. abortion clauses) they should satisfy the requirement that a
programmer independent coordinate system can be maintained to
describe the process in a helpful and manageable way.
It is hard to end this with a fair acknowledgment. Am I to
Volume 11 / Number 3 / March, 1968 Communieations of the ACM I47
HTMLバージョンあり ?
http://www.u.arizona.edu/ rubinson/
copyright_violations/
Go_To_Considered_Harmful.html
15. 15
Multics implemented a single level store for
data access, discarding the clear distinction
between ?les and process memory.
. . .
To read or write to them, the process simply
used normal CPU instructions, and the
operating system took care of making sure
that all the modi?cations were saved to disk.
Multics Segmentation
Wikipedia: Multics
19. Task = space
Thread = computation
Memory object = memory
Port = I/O and IPC
Message = communication
& Microkernel
Mach (1985-):
2nd ultimate virtualization
20. Machの前身:Accent
Robert P. Fitzgerald, Richard F. Rashid: The Integration of Virtual Memory
Management and Interprocess Communication in Accent. ACM Trans.
Comput. Syst. 4(2): 147-177 (1986)
!
Robert P. Fitzgerald, Richard F. Rashid: The Integration of Virtual Memory
Management and Interprocess Communication in Accent (Abstract). SOSP
1985: 13-14
!
Richard F. Rashid, George G. Robertson: Accent: A Communication Oriented
Network Operating System Kernel. SOSP 1981: 64-75
21. 理想と現実(Mach & Accent編)
なぜOS研究者しか知らないのか?
another unixとして広まった。(Unix互換が活きた)
(Cf. OSF/1 and Mac OS X)
高度なintegrationはOSレベルよりWebレベルで。?
マルチスレッドは今やどのOSでも。(CF. Win, Linux,
Java)
マイクロカーネル技術の礎となった。
プロセスマイグレーションはどこに行った?
VMマイグレーション技術として生きている。
22. Distributed Shared Repository: A Uni?ed
Approach to Distribution and Persistency
(Kato et al., ICDCS 1993)
分散環境におけるセグメンテーション。
スレッドまで永続化&マイグレーション可能。
23. Planet (←DSR)
VM-integrated (native) mobile objects
23
K. Kato, et al.: An Approach to Mobile Software Robots for the WWW, IEEE Transactions
on Knowledge and Data Engineering, Vol. 11, No. 4, pp. 526?548, 1999 July.
24. 異機種オブジェクトモビリティ(1/2)
Machine architecture A
Machine A?
native
Compiler?
front-end
Canonical-code?
generator
Source?
program Machine architecture B
Converter
Canonical
Converter
Canonical Converter
Unloading ...
Object repository
34. 高階関数&多相型RPC
import TWICE : ?t.(t → t) → t → t in
let
addone = λx.x + 1
in
((TWICE addone) 3)
export
λf. λx.(f (f x))
as TWICE
[Ohori and Kato, POPL93]
56. BitVisor as Research Platform
? HyperSafe [Wang et al., IEEE S&P ‘10]
? Integrity of hypervisor itself, i.e., modi?cation
disabled.
? “Return-less” VMM [Li et al., EuroSys ‘10]
? Against ROR (Return-Oriented Rootkit)
? TCVisor [Rezaei et al., ICITST ‘10]
? Limited storage area can be seen by each user.
56