This page needs to be proofread.
Guy L. Steele Jr. 4 LAMBDA: The Ultimate Declarative

BAR: ...

PUSHJ G

BAR1: ...

PUSHJ H

BAR2: ...

PUSHJ F

BAR3: POPJ

F: ...

POPJ

G: ...

POPJ

H: ...

POPJ

We have labeled not only the entry points to the functions, but also a few key points within BAR, for expository purposes.

We are justified in putting no ellipsis between the PUSHJ F and the POPJ in BAR, because we assume that no cleanup other than the POPJ is necessary, and because the value returned by F (in the assumed RESULT register) will be returned from BAR also.

Let us depict a pushdown stack as a list growing towards the right.

On arrival at BAR, the caller of BAR has left a return address on the stack.

..., <return address for BAR>

On executing the PUSHJ G, we enter the function G after leaving a return address BAR1 on the stack:

..., <return address for BAR>, BAR1

The function G may call other functions in turn, adding other return addresses to the stack, but these other functions will pop them again on exit, and so on arrival at the POPJ in G the stack is the same.

The POPJ pops the address BAR1 and jumps there, leaving the stack like this:

..., <return address for BAR>

In a similar manner, the address BAR2 is pushed when H is called, and H pops this address on exit.

The same is true of F and BAR3.

On return from F, the POPJ in BAR is executed, and the turn address supplied by BAR's caller is popped and jumped to.

Notice that during the execution of F the stack looks like this:

..., <return address for BAR>, BAR3, ...

Suppose that at the end of BAR we replaced the PUSHJ F, POPJ by GOTO F.

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

..., <return address for BAR>

The stack would look this way on arrival at the POPJ in F, and so F would pop this return address and return to BAR's caller.

The net effect is as before.

The value returned by F has been returned to BAR's caller, and the stack was left the same.

The only different was that one fewer stack slot was consumed during the execution of F, because we did not push the address BAR3.

Thus we see that F may be invoked in a manner different from the way in which G and H are invoked.

This fact is somewhat disturbing.

We would like our function invocation mechanism to be uniform, not only for aesthetic reasons, but so that functions may be compiled separately and linked up at run time with a minimum of special-case interfacing.

Uniformity is achieved in some LISPs by always using PUSHJ and never GOTO, but this is as the expense of using more stack space than logically necessary.

At the end of every function