Notes
{Note Debugging}
As every machine-language programmer of a stack machine knows, the extra address on the stack is not entirely useless because it contains some redundant information about the history of the process. This information is provided by standard LISP systems in the form of a "backtrace". [McCarthy 62] [Moon 74] [Teitelman 74] This information may give some clues as to "how it got there". One may compare this to the "jump program counter" hardware feature supplied on some machines (notably the PDP-10's at MIT [Holloway 70]) which saves the contents of the program counter before each jump instruction.
{Note Expensive Procedures}
Fateman comments on this difficulty in [Fateman 73]: "...'the frequency and generality of function calling in LISP' is a high cost only in inappropriately designed computers (or poorly designed LISP systems). To illustrate this, we ran the following program in FORTRAN ... [execution time 2.22 sec] ... We then transcribed it into LISP, and achieved the following results: ... [execution time 1.81 sec] ...
"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."
Auslander and String discuss in [Auslander 76] a technique for "removing recursion" from PL/I programs which LISP programmers will recognize as a source-to-source semi-compilation. The technique essentially consists of of introducing an auxiliary array to serve as a stack (though the cited paper manages in the example to use an already existing array by means of a non-trivial subterfuge), and transforming procedure calls into GOTO's plus appropriate stack manipulations to simulate return addresses. What is astounding is that this simple trick shortened the size of the example code by 8% and shortened the run time by a whopping 40%! They make the reason clear: "The implementation of the recursive stack costs PL/I 336 bytes per level of recursive call ..." The GOTO's, on the other hand, presumably compile into single branch instructions, and the stack manipulations are just a few arithmetic instructions.
Even more astounding, particularly in the light of existing compiler technology for LISP and other languages, is that Auslander and Strong do not advocate fixing the PL/I compiler to compile procedure calls using their techniques (as LISP compilers have, to some extent, for years). Instead, they say: "These techniques can be applied to a program without an understanding of its purpose. However, they are complex enough so that we are inclined to teach them as tools for programmers rather than try to mechanize them as an option in an optimizing compiler." The bulk of their transformations are well within the capability of an optimizing compiler. The problem is that historically procedure calls have received little attention from those who design optimizing compilers; Auslander and Strong now suggest that, since this is the case, we should rewrite all procedure calls into other constructs that the compiler understands better! This seems to defeat the entire purpose of having a high-level language.
