| Guy L. Steele Jr. | 3 | LAMBDA: The Ultimate Declarative |
some primitive which passed some data along while performing a GOTO.
It turns out that almost every high-level programming language already has such a primitive: the functional call!
This construct is almost always completely ignored by those who catalog control constructs; whether it is because function calling is taken for granted, or because it is not considered a true control construct, I do not know.
One might suspect that there is a bias again function calling because it is typically implemented as a complex, slow operation, often involving much saving of registers, allocation of temporary storage, etc.
{Note Expensive Procedures}
Let us consider the claim that a function invocation is equivalent to a GOTO which passes some data.
But what about the traditional view of a function call which expects a returned value?
The standard scenario for a function call runs something like this:
[1] Calculate the arguments and put them where the function expects to find them.
[2] Call the function, saving a return address (on the PDP-10, for example, a PUSHJ instruction is used, which transfers control to the function after saving a return address on a pushdown stack).
[3] The function calculates a value and puts it where its caller can get it.
[4] The function returns to the saved address, throwing the saved address away (on the PDP-10, this is done with a POPJ instruction, which pops an address off the stack and jumps to that address).
It would appear that the saved return address is necessary to the scenario.
If we always compile a function invocation as a pure GOTO instead, how can the function know where to return?
To answer this we must consider carefully the steps logically required in order to compute the value of a function applied to a set of arguments.
Suppose we have a function BAR defined as
(DEFINE BAR
(LAMBDA (X Y)
(F (G X) (H Y))))
In a typical LISP implementation, when we arrive at the code for BAR we expect to have two computed quantities, the arguments, plus a return address, probably on the control stack.
Once we have entered BAR and given the names X and Y to the arguments, we must invoke the three functions denoted by F, G, and H.
When we invoke G or H, it is necessary to supply a return address, because we must eventually return to the code in BAR to complete the computation by invoking F.
But we do not have to supply a return address to F; we can merely perform a GOTO, and F will inherent the return address originally supplied to BAR.
Let us simulate the behavior of a PDP-10 pushdown stack to see why this is true.
If we consistently used PUSHJ for calling a function and POPJ for returning from one, then the code for BAR, F, G, and H would look something like this:
