Page:AIM-443.djvu/5

This page has been validated.

Guy L. Steele Jr.

4

Debunking the "Expensive ..." Myth

Suppose that at the end of BAR we changed the sequence

	`PUSHJ F`	to `JUMP F`
`BAR3`:	`POPJ`

Then on arrival at the JUMP the stack would look like this:

FOO5

...

Instead of a PUSHJ to push BAR3, we have a JUMP to F. Thus on arrival at F, the stack has only FOO5 on top. When F is done, it will return to FOO5 instead of BAR3. But this is all right! F has put the correct value in the result register, and this value will be transmitted to FOO5, with the stack properly adjusted. All that has changed is the useless pushing of BAR3, and the encoding of a procedure call as a JUMP (that is, a GOTO!).

This approach is quite general. The idea is obscured by algebraic syntax, but if we rewrite a program in LISP notation, it is clear that the last thing that program does is a procedure call of some kind. To prove this, we note that the outermost construct in the program body must fall into one of a limited number of cases:

A call to an "intrinsic" function which is compiled open. In this case that function is simply compiled open. That function may compile open as one or more arithmetic instructions followed by a POPJ, or else it must recursively fall into some other case.
A call to an external function. In this case, as argued above, we can simply JUMP to the new function, as there is no need to return to the caller.
A conditional. The argument applies recursively to the branches of the conditional.
A sequential block. The argument applies recursively to the last component of the block.
A looping construct. The argument applies recursively to the expression which gives the value of the loop (which may be assumed to fall into the first case if the value is to be ignored).

Other constructs are handled similarly. In this way, if the last thing a procedure does is call another (external) procedure, that call can be compiled as a GOTO. Such a call is called tail-recursive, because the call appears to be recursive, but is not, since it appears at the tail end of the caller.

This approach can be made even more uniform by compiling every procedure call as a GOTO. The idea is that a return address is pushed on commencement of the evaluation of an argument, rather than application of a function. This provides a uniform compilation discipline. For example, consider the BAR function used above:

(DEFINE (BAR X Y)
        (F (G X) (H Y)))

In order to compile the body, we must first compile the argument forms (G X) and (H Y). Since (G X) is an argument form, we push a return address, then set up the arguments for G, then call G. (H Y) is treated similarly. Now that the arguments for F are available, we set them up and call F: