Guy L. Steele, Jr.

“ Compiler writers have often simplified their job at the expense of the procedure call by adopting certain standard protocols. One of these is that the called procedure should save all registers that it uses. This is in turn often simplified to "save all registers". It is seldom the case that all of these registers actually need to be saved; indeed, in statement-oriented languages such as FORTRAN with little global optimization by the compiler, often no registers need be saved across a procedure call! ”

“ For example, we decree that procedures are the method of producing modularity; that WHILE-DO loops are the way to iterate; that IF-THEN-ELSE is the way to produce conditionals; that GOTO is the way to produce peculiar program structures.
The fact is that this just isn't so. Consider the notion of modularity, which is indeed a useful concept for organizing programs. While procedure calls are indeed a method of modularizing programs, there are other methods. The PL/I %INCLUDE construct or the COBOL COPY construct are one alternative. ”

“ Recently practitioners of programming discipline have advised us not to be afraid to use procedure calls, as the readability they afford is worth the inefficiency. This is like saying that cars with square wheels are all right because transportation is worth a bumpy ride: we really ought instead to concentrate on improving our wheels.
I would like to suggest here that procedure calls have been given a "bad press" for a number of reasons. There is no reason that procedure calls must be expensive. ”

“ Here we shall consider an example of how expressive procedure calls can be when used freely. The example is taken from Yourdon [You75,233] ; he implies that the program was an actual one in use. He suggests that, rather than using many flag variables to indicate various conditions within a program, one should use a single variable which encodes the state of the program. The motivation behind this is that one should also draw a state diagram showing the valid transitions between states; the programmer is encouraged to think of his program as a finite-state automaton. ”

“ 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 ”

“ We can certainly express all programs in a structured form by introducing flag variables, but the preceding series of reasonable transformations merely renders it unstructured again, demonstrating that we had not really made the program structured in nature, but only in form. ”

“ 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. ”

“ This is as fruitless as eliminating iteration by banning DO-loops would be (people would just use GOTO or procedure calls) , or eliminating recursion by banning procedure calls (people would, and do, simulate it by using an array as a stack) . We need to get a better grasp on organizational concepts and their relationship to the individual constructs which make up our languages. ”

“ It turns out that in most programming languages (COBOL, PL/I, FORTRAN. and LISP in particular) the distinction between lexical and dynamic scoping doesn't matter most of the time anyway. We should leave the compiler free to produce the best possible code; only in cases where structures are explicitly declared to be dynamically referenced should the compiler be forced to leave them on the stack in an otherwise tail-recursive situation.
In general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly encoded as JUMP instructions. ”

“ Extra stacks are introduced in the form of arrays (though in their example they use an already existing array by means of an extremely clever trick) which are used to contain saved values of variables and return addresses. To put it quite simply (though they do not) , they compile the PL/I program into another PL/I program which is more like machine language, and which the real PL/I compiler can therefore process more easily. They report that this technique improves run time by 40%, and space used per level of recursion from 336 bytes to 9, a 97% saving! ”

“ The important point is that for each important programming concept which we have found useful -- modularity, iteration, assignment, conditionals -- there may exist more than one programming language construct which can embody that concept in a reasonably natural manner. Furthermore, it sometimes requires more than one construct to properly embody a given concept. ”

“ All that has changed is the useless pushing of BAR3, and the encoding of a procedure call as a JUMP (that is, a GOTO!) .
This approach is quite general. The idea is obscured by algebraic syntax, but if we rewrite a program in LISP notation, it is clear that the last thing that program does is a procedure call of some kind. To prove this, we note that the outermost construct in the program body must fall into one of a limited number of cases:
A call to an "intrinsic" function which is compiled open. In this case that function is simply compiled open. ”

“ At the source-language level, there are other factors which contribute to the procedure call's poor reputation. Nearly all algebraic computer languages draw a syntactic distinction between operators and user functions, if not also a semantic distinction. Often built-in functions are also distinguished in some silly way from user functions, even though they are used in syntactically similar ways. As an example, you cannot pass "+" as an external function argument in FORTRAN, even though it is mathematically a perfectly good function of two arguments ”

“ Since procedure calling instructions were not planned ahead of time in the way that arithmetic, conditional, and branch operations were, one would assume they were implemented on early computers in a rather clumsy fashion. While the basic arithmetic and conditional jump instructions have changed little in nature over the years, one can trace an evolution of special instructions used for procedure calls. ”

“ Until a much more advanced theory of programming is devised, designers of practical languages are well advised to leave in "ugly hooks" like GOTO, even if also discouraging their use except in emergencies. After all, using GOTO to simulate a peculiar control construct is probably preferable to a convoluted perversion of a more specialized construct.
{Note Shuffle Arguments}
To elucidate this point further, suppose that function arguments are passed on the stack (above the return address) . ”

“ Machines before 1960 (for example the IBM 1620 and 704) typically had only one instruction (if any) for subroutine calling, which saved the instruction counter in a register or in the first memory location of the called subroutine. The PDP-1 had three instructions which were all variants on this theme. The IBM 360 had only one such instruction (with two addressing modes) , but the programmer had the additional choice of which register to store the program counter into. ”

“ One can argue quite strongly that there are so large a number (possibly infinite) of distinct useful control constructs that no one language could embody them all, and that therefore no language designer should be so conceited as to think he has encompassed all desirable constructions in a given language. ”

“ Procedure calls, implemented properly and used freely, allow a stylistic freedom far greater than (and largely inclusive of) that afforded by GOTO. Any flowchart can be implemented as a "structured" program without introducing any extra variables. ”

“ It is quite easy to prove. We assume without loss of generality that the boxes of the flowchart are of two sorts: process boxes with one exit, and conditional boxes with two. A process box may contain any single-exit computation whatsoever (which may be built up from sequencing, conditional, and while-do loops, for example) . ”

“ There is another way out. Let us not use GOTO statements to jump between modules, and let us not use flag variables to signal what are effectively GOTO statements to an outer control loop. Instead, let us consider what a single module does: it performs its bit of processing, and then invokes or otherwise designates another module to complete processing. Suppose therefore that at the end of every module we had a procedure call to the next module:
PROCEDURE MODULE23; BEGIN ; IF THEN PERFORM MODULE10 ELSE IF THEN PERFORM MODULEl5 ELSE PERFORM MODULE2O; END ”

“ Yourdon says "In most cases, a modular approach should not require more than 5-10% extra CPU time; this seems to be a reasonable price to pay..." [You75,99] I would suggest that this price is totally unreasonable when the technology (or, more accurately, the design philosophy) exists to reduce it!
There has been some mathematical work done on recursion removal [Str71] [Dar76] which is aimed both at converting procedure calls to GOTO statements and at transforming programs into other forms requiring less recursion. ”

“ Just as a concept such as modularity may be expressed by diverse constructs, so may a language construct be interpreted in various ways, some of which may lead to superior compilation techniques. {Note Various Optimizations} One example of this is the tail-recursive procedure call ”

“ Yourdon tells of the plight of programmers "whose managers have specifically forbidden them to use such statements because of the overhead involved in subroutine-calling statements." [You75,177]
These misplaced feelings of efficiency are felt for other programing language constructs as well. and subtly influence our programming style. The example I wish to consider here is the procedure call. Everyone knows that, unlike GOTO statements, procedure calls are "expensive". ”

“ Yourdon [You75,98] reports that on a 360/50 a PL/I procedure call costs 198 microseconds. It is no wonder that programmers feel that procedure calls are slow - they are!
That is, they are slow as currently implemented. Unfortunately, our thinking has generally been colored to the point where we simply assume that all procedure calls are inherently slow. Even SIGSAM Bulletin, a journal contributed to in large part by LISP programmers, said in an editorial [Jen72] :
"... ”

“ Allen, Frances E., and Cocke, John. "A Catalogue of Optimizing Transformations." In Rustin, Randall (ed.) , Design and Optimization of Compilers. Proc. Courant Comp. Sci. Symp. 5. Prentice-Hall (Englewood Cliffs, N.J., 1972) . ”