| Guy L. Steele Jr. | 5 | LAMBDA: The Ultimate Declarative |
X the sequence "PUSHJ Y; POPJ" will occur, where Y is the last function invoked by X, requiring a logically unnecessary return address pointing to a POPJ.
{Note Debugging}
An alternate approach is suggested by the implementation of the SCHEME interpreter.
We note that the textdual difference between the calls on F and G is that the call on G is nested as an argument to another function call, whereas the call to F is not.
This suggests that we save a return address on the stack when we begin to evaluate a form (function call) which is to provide an argument for another function, rather than when we invoke the function.
(The SCHEME interpreter works in exactly this way.)
This discipline produces a rather elegant symmetry: evaluation of forms (function invocation) pushes additional control stack, and application of functions (function entry and the consequent binding of variables) pushes additional environment stack.
Thus for BAR we would compile approximately the following code:
BAR: PUSH [BAR1] ;save return address for (G X)
<set up arguments for G>
GOTO G ;call function G
BAR1: <save result of G>
PUSH [BAR2] ;save return address for (H Y)
<set up arguments for H>
GOTO H ;call function H
BAR2: <set up arguments for F>
GOTO F ;call function F
The instruction PUSH [X] pushes the address X on the stack.
Note that no code appears in BAR which ever pops a return address off the stack; it pushes return addresses for G and H, but G and H are responsible for popping them, and BAR passes its own return address implicitly to F without popping it.
The point is extremely important, and we shall return to it later.
Those familiar with the MacLISP compiler will recognize the code of the previous example as being similar to the "LSUBR" calling convention.
Under this convention, more than just return addresses are kept on the control stack; a function receives its arguments on the stack, above the return address.
Thus, when BAR is entered, there are (at least) three items on the stack: the last argument, Y, is on top; below that, the previous (and in fact first) one, X; and below that, the return address.
The complete code for BAR might look like that:
BAR: PUSH [BAR1] ;save return address for (G X)
PUSH -2(P) ;push a copy of X
GOTO G ;call function G
BAR1: PUSH RESULT ;result of G is in RESULT register
PUSH [BAR2] ;save return address for (H Y)
PUSH -2(P) ;push a copy of Y
GOTO H ;call function H
BAR2: POP -2(P) ;clobber X with result of G
MOVEM RESULT,(P) ;clobber Y with result of H
GOTO F ;call function F
There is some tricky code at point BAR2: on return from H the stack looks like:
..., <return address for BAR>, X, Y, <result from G>
