Guy L. Steele, Jr.

“ Earlier we showed a translation of BAR into "machine language", and noted that there was no code which explicitly popped a return address; the buck was always passed to another function (F, G, or H) . This may seem surprising at first, but it is in fact a necessary consequence of our view of function calls as "GOTOs with a message". We will show by induction that only primitive functions not expressible in our language (SCHEME) perform POPJ; indeed, only this nature of the primitives determines the fact that our language is functionally oriented! ”

“ This is why PUSHJ (and similar instructions on other machines, whether they save the turn adress on a stack, in a register, or in a memory location) works on a subroutine call, and, by extension, why up to now many people have thought of pushing the return address at function call time rather than at form evaluation time.
The use of GOTO to call a function "tail-recursively" (known around MIT as the "JRST hack", from the PDP-10 instruction for GOTO, though the hack itself dates back to the PDP-1) is in fact not just a hack, but rather the most uniform method for invoking functions. ”

“ 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. ”

“ It is, rather, the primitive, built-in operators of the language which pop return addresses. These primitives cannot be directly expressed in the language itself (or, more accurately, there is some bases set of them which cannot be expressed) . It is the constants (which we may temporarily regard as zero-argument functions) , the arithmetic operators, and so forth which pop the return address. (One might note that in the compilation of CURRIED-TRIPLE-ADD above, a POPJ appeared only at the point the primitive "+" function was open-coded as ADD instructions.) ”

“ One can even do without IF-THEN-ELSE, though the technique for eliminating it seems to produce more rather than less complexity. {Note No IF-THEN-ELSE} A minimal set should contain primitives which are not only universal but also easy to describe, simple to implement, and capable of describing more complex constructs in a straightforward manner. This is why the semaphore is still commonly used; its simplicity makes it easy to describe more complex synchronization operators. ”

“ On the other hand, suppose that is (FOO 1 A B) , where FOO is a built-in function which takes its arguments in registers 1, 2, and 3.
Then A's preference class will be targeted on register 2, and B's on register 3 (since these are the only uses of A and B within ) ; this will cause T1 and T2 to have the same respective targets, and at the outer level an attempt will be made to perform the addition in register 2 and the multiplication in register 3. ”

“ 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. ”

“ Environment operations Formal procedure parameters Declarations within blocks Assignments to local variables Pattern matching Side effects Assignments to global (or COMMON) variables Input/output Assignments to array elements Assignments to other data structures Process synchronization Semaphores Critical regions Monitors Path expressions Often attempts are made to reduce the number of operations of each type to some minimal set. ”