MASSACHUSETTS INSTITUTE OF TECHNOLOGY
ARTIFICIAL INTELLIGENCE LABORATORY
AI Memo443 October 1997
DEBUNKING THE “EXPENSIVE PROCEDURE CALL” MYTH
or, PROCEDURE IMPLEMENTATIONS CONSIDERED HARMFUL
or, LAMBDA, THE ULTIMATE GOTO
by
Guy Lewis Steele Jr. *
For the past five to ten years (depending on how you count) the computing community has been enbroiled in the dabate over "structured programmubg" and, as a special case, the GOTO statement. On the other hand, many authors have observed that programs wtitten without GOTOs are often more perspicuous than programs written with GOTOs by the same programmer. That is, the avoidance of GOTOs is a discipline which have been observed to produced programs which are easier to understand and maintain.
On the other hand, a certain portion of the computing community has rebelled at this discipline. There are several reasons for this rebellion. Among these are:
(1) Some programmers fear that their expressive power or style will be cramped if GOTO is taken away from them. This is true in such contemporary language as FORTRAN, but in more powerful languages such as ALGOL, PL/I, COBOL, and PASCAL the point is somewhat more debatable. Yourdon comments: Many programmers feel that programming without the GO-TO statement would be awkward, tedious and cumbersome. For the most part, this complaint is due to force of habit." [You75, 178] In all fairness, it should be pointed out that GOTO is a basic, universal primitive with which (in conjunction with a conditional) almost any other control construct can be synthesized if the language designer neglected to include it. {Note Omniscient Implementors} A good example of this is the CASE statement.
(2) some programmers feel that the imposed discipline doesn't make any difference, because one can write incomprehensible programs with GOTO. This piece of logic is slightly false, for while avoiding GOTO does not guarantee comprehensibility, it often does increase the probability of producing comprehensible code, given our current cultural biases in programming style.
(3) There is some feeling that GOTO is a "cheap" statement, while other constructs (DO, CASE, etc) are more "expensive". Everyone konws that a GOTO get compiled into machine instruction (same kind of branch), while DO produce many instuctions. the diffculty here is a misplaced sense of what is "efficient"; and despite the fact that current practitioners of programming discipline tell us not to worry about efficiency, we nevertheless do, at some low unconscious level, whenever we write code. Yourdon tellss 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 programming language constructs as well, and subtly influence our programming style. The exmaple I wish to consider there is the procedure call. Every knows that, unlike goto statments, procedure calls are “expensive”. Indeed, those feelings are not unjustified, given the past and curent programming language implentments.
Because procedure calls are “expensive”, we tend to avoid using them in our code. Unfortunately, this produce an detrimental effect in our programming style, for what Dijkstra said of PL/I holds true of almost any language: “the procedure is one of [the] main vehicles for expressing structure.” [Dij76,8] Recently, practitioners of programming discipline have advised us not to be afraid to use procedure calls, as the readability worth the inefficiency. This is like saying cars with squre wheels because transportation is worth a bumpy ride: we really ought instead to concentrate on improving our wheels.
I would like to suggest here that the procedure calls have been given a “bad press” for a number of reasons. There is no reason that procedure calls must be expensive. I intent to demonstrate here the following points:
(A) Procedure calls are, from a theoretical point of view, glorified GOTO statements; this view leads to interesting compilation techniques where can save space and time.
(B) Procedure calls ar in fact quite fast when implemented properly.
(C) Procedure calls have received a bad reputation for a variety of historical reasons.
(D) As a result, we have been advising programmers to adjust their programming style to compensate poor implementations (or, alternatively, not to adjust but to ignore the poorness of the implementation), while giving little thought to improving these implementations.
(E) 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.
(F) Much of our difficulty with procedure calls and with GOTO statements is that we have a restricted view ogf the relationship between programing concepts and language constructs.
In studying the nature of procedure calls, it is appropriate to study the LISP language. LISP, more than any other language, users procedure calls as the primary means of expression; in particular, the arbitrary distinction between build-in operators (like multiplication) and user functions is almost completely nonexistent. What should apperear in FORTRAN as
function quad(a, b, c)
quad = (-b + sqrt(b**2 -4*a*c)) / (2*a)
return
end
is in (one dialect of) LISP:
(define (quad a b c)
(/ (+ (- b)
(sqrt (- (** b 2) (* 4 a c))))
(* 2 a)))
In this most computations (other than conditionals) can easily be expressed in terms of function calls of the form
(F X1 X2 … Xn)
LISP is an expression language, in that ervery program is a function which returns a value (but this value may be ignored – many programs producing interesting side effects and then return NIL). It differs from other expression languages such as BLISS[Wu 171][Wu 175], however, in its uniformity of notation.
The usual way to implement function calls in LISP is by using a stack. When a function is called,
*NSF fellow