"bad press" for a number of reasons. There is no reason that procedure calls must be expensive. I intend 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 which can save space and time.
(B) Procedure calls are 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 for 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 of the relationship between programming concepts and language constructs.
A. Procedure Calls as GOTO
Statements
In studying the nature of procedure calls, it is appropriate to study the LISP language. LISP, more than any other language, uses procedure calls as the primary means of expression; in particular, the arbitrary distinction between built-in operators (like multiplication) and user functions is almost completely nonexistent. What would appear 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 way 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 every program is a function which returns a value (but this value may be ignored - many programs produce interesting side effects and then return NIL
). It differs from other expression languages such as BLISS [Wul7l] [Wu175], 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, a return address is pushed onto the stack; when a function is done, it pops a return address and goes there (after stashing the value to be returned in a register). This is in fact how procedure calls are