needed, provided lexical scoping is used (as in ALGOL) or a subset of lexical scoping (as is largely true of FORTRAN and COBOL). Even languages with dynamic scoping rules, such as APL and some LISP dialects, can use this technique in situations where dynamic references are not involved.
Procedure calls permit an extraordinarily powerful style of programming which, even though it is completely "structured", includes most rat's nests of GOTO statements as a subset. This style merely involves writing a procedure call where one would ordinarily write a GOTO at the end of a procedure. (The technique will not reproduce the "escape expression" effect of writing a GOTO from inside a loop to outside the loop, however.) This style is sufficiently powerful to represent any flowchart without introducing flag variables or GOTO statements. Furthermore, this style of programming is a natural way to write certain kinds of commonly occurring programs. The use of this style does not depend on procedure calls being cheap or being compiled as tail-recursive branches, though if they are so compiled running time is reduced and less stack is consumed, which are desirable characteristics apart from the issue of style.
We might wonder why such rat's nests are not written using procedure calls in practice, when they are certainly possible and violate no rules of "structured" programming. The answer is probably that GOTO statements, being "cheap", are used freely enough to produce rat's nests, while procedure calls, being "expensive", are used sparingly. We therefore come to the paradoxical conclusion that improving the implementation of procedure calls is a mixed blessing;
we can improve our programs both in time and space, but we may bring on the same problems we had with GOTO by encouraging the use of procedure calls in stylistically diverse ways. We could simply ignore the whole thing, and go on letting procedure calls be expensive, in order to discourage their use;
but this would not be intellectually honest. It is appropriate that we should have a healthy respect for procedure calls, and use them sparingly;
but we should respect them because they are powerful, and not because they are "expensive".
Acknowledgements
Discussions with Mike Genesereth, Richard Stallman, and Richard Zippel illuminated many key points. Johan DeKleer, Jon Doyle, Tom Knight, and Richard Greenblatt also provided useful comments. Gerry Sussman was, as always, a great source of enlightenment.
Carl Hewitt and Richard Stallman provided additional useful comments which led to the notes, which were added after final submission of the paper to ACM '77.
