implemented in many languages.
Let us consider the execution of a call on the LISP function BAR:
(DEFINE (BAR X Y)
(F (G X) (H Y)))
BAR calls G on X, H on Y, and then F on the two results, returning the result of calling F.
For concreteness, we will express the compiled code in a modified form of PDP-10 machine language, using these instructions:
JUMP x |
Branch to (i.e. GOTO) location x.
|
PUSHJ x |
Push the location of the PUSHJ, plus 1, on the stack, then branch to location x.
|
POPJ |
Pop an address from the stack and branch there. |
The code for BAR might look something like this:
BAR: |
<set up arguments for G>
|
PUSHJ G
| |
BAR1: |
<save result from G>
|
<set up arguments for H>
| |
PUSHJ H
| |
BAR2: |
<use results from G and H for F>
|
PUSHJ F
| |
BAR3: |
POPJ
|
We have introduced the labels BAR1, BAR2, BAR3 to aid the exposition. Note that there are no instructions between the PUSHJ F and the POPJ; we shall justify this below.
On arrival at BAR, the arguments X and Y are presumably in registers or some other appropriate place, and a return address (say FOO5) is on the stack. After we execute the PUSHJ G, the stack will look like this:
BAR1
FOO5
...
G may call other functions, and the stack will go up and down, but eventually it will put a value in the result register and do a POPJ, returning to BAR1. This leaves the stack like this:
FOO5
...
In a similar manner, the PUSHJ H will push BAR2 on the stack, and H will eventually pop it when it exits. The same is true of the PUSHJ F and BAR3. When F returns to BAR3 with a value in the result register, the POPJ at BAR3 is performed, returning to FOO5. Since BAR was to return the result of calling F, the correct value is in the result register for FOO5.
Notice that during the execution of F the stack looked like this:
BAR3
FOO5
...
