iterative code, almost without even trying, for it is more a matter of the code generation strategy than of a specific attempt to remove recursions.(For more discussion of this, see [Ste76b]. For an interesting comparison between GOTO and the APL execute operator, see [Syk77].)
B. Procedure Calls Can be Fast
The above examples have shown procedure calls encoded as a simple JUMP, or at worst as a PUSHJ. These simple instructions are not time-consuming, even on computers which must simulate PUSHJ because it is not a primitive instruction. What then makes procedure calls so expensive?
The answer seems to be that most implementations are rather thoughtless or careless in this regard. It is usual for a compiler to slap standard "prologue" and "epilogue" code around every procedure; this code typically sets up complex procedure frame structures, allocates all declared variables, and sometimes even saves and restores all registers. Auslander and Strong [Aus76] report that one simple procedure call, compiled by the OS/360 PL/I optimizing compiler, pushes 336 bytes onto the stack! 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]:
"... one might expect CANAL, SAC-1, ALTRAN, and TRIGNAN to run the fastest, because they make efficient use of special-purpose data structures and because they are written either in FORTRAN or machine language; and present versions of MACSYMA, REDUCE, and SCRATCHPAD to run slower -- because of their more general expression handling ability and because of the frequency and generality of function calling in LISP."
In that same editorial comparative running times were given for the systems, and indeed the LISP-based systems were five to ten times slower than the others -- except MACSYMA, which was comparable to the FORTRAN and machine-language systems! Clearly this contradicts the cited intuitive belief about procedure calls.
A reply by Fateman [Fat73] further emphasized this point. In actual timing tests conducted on numerical code using the MacLISP compiler and the then current DEC FORTRAN compiler, the MacLISP code was faster! Fateman comments:
"... 'the frequency and generality of function calling in LISP' is a high cost only in inappropriately designed computers (or poorly designed LISP systems). ... The point we wish to make is that compiled properly, LISP may be as efficient a vehicle for conveying algorithms, even numerical ones, as any other higher-level language, e.g. FORTRAN. An examination of the machine code produced by the two compilations shows that the inner-loop arithmetic compilations are virtually identical, but that LISP subroutine calls are less expensive."
(For a discussion of the techniques used to achieve FORTRAN-like arithmetic ability in LISP, see [Ste77b].)
