expressions, call-by-name, procedural data types, etc. The interested reader is referred to [Ste76a] and [Ste76b] for some examples of how this is done.
D. What Are we Doing About It?
Up to now, we have spent more time ignoring or circumventing the problem than solving it. 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. Some of this work is both mathematically interesting and practically applicable. Sometimes, however, it has gone up a garden path under the influence of the "expensive procedure call" myth. One example is a paper by Auslander and Strong [Aus76] which describes a technique for removing recursions from PL/I programs. This involves a set of source-to-source transformations which convert PL/I function calls into GOTO statements. 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!
This seems impressive until we realize that their transformations are almost entirely straightforward and mechanical and could easily be made a part of the PL/I compiler, and furthermore that they are essentially techniques which have been used by the MacLISP compiler and others for almost a decade: turning procedure calls into GOTO when possible, and avoiding pushing variable values unless necessary! Then we are impressed only by the inefficiency of this so-called "optimizing" PL/I compiler!
What is more, Auslander and Strong conclude:
"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."
In other words, we are now so afraid of procedure calls that, rather than fix our compilers, we wish to teach programmers complex techniques for using GOTO to circumvent the shortcomings of our compilers! Such a desire is completely outrageous. Not only does it violate the philosophical principles of clarity in language design and programming style we have slowly been forced to accept, but it is demonstrably ridiculous, because while the complete generality of these techniques has perhaps not been implemented in a compiler, a good part of it has, and has worked for eight to ten years at least. Such is the ludicrous position we have come to.
