Put your code... (was Re: gotos

[kenny at uiucdcsb.cs.uiuc.edu]

[Part 4: Eliminating recursive calls.]

In EXAMPLE 6, Knuth gives an example of code that has been processed
to eliminate recursive function calls.  This code contains the
perceived abomination of not only a _goto_, but a _goto_ into an inner
lexical scope.

I suspect, in this case, that even those who, like Mr. Spencer, find
the _goto_ abhorrent will find this case inoffensive.  Nobody is
proposing that code looking like this should ever be coded or
maintained directly.  Knuth himself says that the code results from
automatic translation of the recursive version; I hope that Mr Spencer
will agree that the back end of a compiler or preprocessor is free to
generate code that is as ugly as it wishes.

I personally would prefer that the backend contain some sort of flow
analyzer based on the translation rules to which I alluded in Part 1.
I drew out a flow graph of EXAMPLE 6C, and applied my translation
rules to it.  The resulting graph contained neither double decisions
nor double-exit loops.  Somewhat to my surprise, the resulting code
was nearly identical to EXAMPLE 6E.

Untangling the spaghetti of EXAMPLE 6C with the -O option caused both
the versions to generate very similar obejct code.

I was unable to follow Knuth's argument with EXAMPLES 7 and 8.  It
appears that, while he found the usage of _goto_ gave better
performance in the quicksort described, Sedgewick found a _goto_-less
version that performed better (EXAMPLE 8A).

Moral 1: If it's convenient, let your preprocessor generate _goto_s.
The user won't have to maintain its output, after all.

Moral 2: Compilers should look into optimizing recursive function
calls more aggressively.  Moreover, other procedure calls should also
be optimized more aggressively than they are; most non-recursive ones,
for instance, could be optimized to share the static parent's
activation record, at a nontrivial saving of run time.

I have a paper on this last point by Barry Wolman, entitled `Reducing
the cost of procedure activations in block-structured languages.'  I
have never been able to locate a published version (I have a photocopy
of a typewritten preprint that's nearly illegible); can anyone out
there find me a pointer to it?

[End of part 4]