Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!mailrus!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsb!kenny
From: kenny@uiucdcsb.cs.uiuc.edu
Newsgroups: comp.lang.c
Subject: Re: Put your code... (was Re: gotos
Message-ID: <165600038@uiucdcsb>
Date: 25 Apr 88 21:34:00 GMT
References: <2597@ttrdc.UUCP>
Lines: 64
Nf-ID: #R:ttrdc.UUCP:2597:uiucdcsb:165600038:000:3025
Nf-From: uiucdcsb.cs.uiuc.edu!kenny    Apr 25 16:34:00 1988


[Part 0: Introduction]

Ozan Yigit, Dan Levy, and Henry Spencer have all been flinging about a
reference to Donald Knuth's paper, ACM Computing Surveys 6:4, 262-301
(1974).

In particular, Mr. Levy challenges Messrs. Spencer and Yigit to remove
the GO TOs from each of Knuth's examples, and to comment on the
elegance and utility of the result.

In this article, and its several sequelae, I intend to put in my two
cents on the subject, and to clarify some of the issues, I hope.
Wherever I refer to EXAMPLE n, it is to be understood that I am citing
the corresponding displayed example in Knuth's paper.

Incidentally, I learned quite a bit in reviewing the paper; it was
several years since I last encountered it.  Knuth has a number of
points which have still not been addressed; most of them represent
concepts other than the goodness or evilness of the GO TO, however,
when applied to today's programming languages.  I strongly recommend
that anyone who is entering this discussion, on either side of the
fence, get a copy of the paper and study it.  Both sides can learn
from it.

Knuth's examples can be classified into the following set of general
topics:

  * Double-exit loops and double decisions.  In general, these
    constructs arise when some conditional or looping construct is
    necessary to calculate the condition for another conditional or
    looping construct.  EXAMPLES 1-3, dealing with table searching,
    fall into this category.  EXAMPLE 4 can be treated in this
    category, as well; I choose, however, to discuss it by itself.

  * Finite-state recognizers and the `pushback' concept.  EXAMPLE 4
    uses the GO TO to represent, in the program's control structure,
    the concept of `pushing back' data on an input stream.

  * Parallel data structures.  EXAMPLE 5 shows a program that uses a
    set of GO TO statements to represent carrying out the same
    operation on one of several variables.  It is also reasonable to
    consider EXAMPLE 5 as if it were a recursive algorithm.

  * Recursion elimination.  Knuth demonstrates the use of GO TO to
    eliminate the use of recursive procedure calls.  EXAMPLE 6 is the
    most obvious example of this use of GO TO; EXAMPLES 7 and 8 can be
    considered in this context as well.

  * The `set of actions' construct.  Knuth points out that many
    applications involving interpreters or simulators have a multi-way
    branch (a _switch_ in C) that selects one of a set of cases.
    Frequently, these cases have common code, and a procedure call may
    be too expensive when executing the common code.

Knuth does not mention the `panic exit' form of GO TO; I shall discuss
this one as well, as I find it of some interest.

Many uses of GO TO can be considered under more than one of these
categories.  To some extent, this is inevitable: in particular, the
ones that arise from the elimination of recursion can be used to model
any of the others, since all control structures can be modeled by
recursive functions.

[End of part 0]