Guy L. Steele, Jr.

“ This general scheme will produce much better code than a scheme which says that all LAMBDA expressions must, like the function FOO, take their arguments in certain registers.
Note too that no code whatsoever is generated for the variable bindings as such; the fact that we assign names to the results of the expressions (+ X Y) and (* Z W) rather than writing
(FOO 1 (* Z W) (+ X Y) )
makes no difference at all, which is as it should be.
Thus, compiler temporaries and simple user variables are treated on a completely equal basis. ”

“ As as example of the use of an escape expression, consider this procedure to compute the harmonic mean of an array of numbers. If any of the numbers is zero, we want the answer to be zero. We have a function harmsum which will sum the reciprocals of numbers in an array, or call an escape function with zero if any of the numbers is zero. (The implementation shown here is awkward because ALGOL requires that a function return its value by assignment.) ”

“ Given the characteristics of lexical scoping and tail-recursive invocations, it is possible to assign a peculiarly imperative interpretation to the applicative constructs of SCHEME, which consists primarily of treating a function call as a GOTO. More generally, a function call is a GOTO that can pass one or more items to its target; the special case of passing no arguments is precisely a GOTO. It is never necessary for a function call to save a return address of any kind. ”

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

“ In pure continuation-passing style, all evaluations are trivial: no combination is nested within another, and therefore no "hidden temporaries" are required. But if X is a combination, say (G P Q) , then we want to think of G as a function, because we want a value from it, and we will need an implicit temporary place to keep the result while evaluating Y and Z. (An interpreter usually keeps these temporary places in the control stack!) On the other hand, we do not necessarily need a value from F This is what we mean by tail-recursion: F is called tail-recursively, whereas G is not. ”

“ For example, WHILE-DO would be utterly useless in expressing iteration if some form of assignment statement (or other side effect) were not also used!
In understanding (a piece of) a program it is necessary to determine not only what construct is being used, but the concept it is intended to express. While we may prefer to think of a procedure call as meaning "go do this other module and then come back", this is only one possible interpretation. We must realize that there are situations where coming back doesn't matter (i.e. the tail-recursive cases) , and these situations may be exploited. ”

“ The current heuristic is that a substitution is desirable if (1) the parameter is referred to only once; or (2) the argument to be substituted in is a constant or variable; or (3) the argument is a LAMBDA-expression whose body is (3a) a constant, or (3b) a variable reference, or (3c) a combination which has no more arguments than the LAMBDA-expression requires and for which the arguments are all constants or variables. This heuristic was designed to be as conservative as possible while handling most cases which arise from typical macro-expansions. ”

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

“ Iteration There are many other ways to compute factorial. One important way is through the use of iteration.
A common iterative construct is the DO loop. The most general form we have seen in any programming language is the MacLISP DO [Moon 74] . It permits the simultaneous initialization of any number of control variables and the simultaneous stepping of these variables by arbitrary functions at each iteration step. ”

“ The only defined operation on a function is invocation. (Note Operations on Functions) we draw this sharp distinction between environment and control constructs on the one hand and data manipulation primitives on the other because only the former are treated in any depth by RABBIT, whereas much of the knowledge of a "real" compiler deals with the latter. A PL/I compiler must have much specific knowledge about numbers, arrays, strings, and so on. ”

“ Extra stacks are introduced in the form of arrays (though in their example they use an already existing array by means of an extremely clever trick) which are used to contain saved values of variables and return addresses. To put it quite simply (though they do not) , they compile the PL/I program into another PL/I program which is more like machine language, and which the real PL/I compiler can therefore process more easily. They report that this technique improves run time by 40%, and space used per level of recursion from 336 bytes to 9, a 97% saving! ”

“ Procedurally defined data structures may compile into code as good as would be expected for data defined by the more usual declarative means. Lambda-calculus-theoretic models of such constructs as GOTO, DO loops, call-by-name, etc. may be used directly as macros, the expansion of which may then compile into code as good as that produced by compilers which are designed especially to handle GOTO, DO, etc. The necessary characteristics of such a compiler designed according to this philosophy are discussed. Such a compiler is to be built in the near future as a testing ground for these ideas. ”

“ In this way one can say that variables are divided by the compiler into two classes: those which are implicitly cells, and those which are not.) A closure (LAMBDA-expression) causes a CONS side-effect. This is not so much because SCHEME programs depend on being able to do EQ on closures (it is unclear whether this is a reasonable thing to specify in the semantics of SCHEME) , as because there is no point in creating two closures when one will suffice. Adjoining CONS to EFFS will prevent the creation of such duplicate code by the optimizer. ”

“ Introduction We catalogue a number of common programming constructs. For each construct we examine "typical" usage in well-known programming languages, and then capture the essence of the semantics of the construct in terms of a common meta-language.
The lambda calculus {Note Alonzowins} is often used as such a meta-language. Lambda calculus offers clean semantics, but it is clumsy because it was designed to be a minimal language rather than a convenient one. All lambda calculus "functions" must take exactly one "argument" ”

“ It also permits one to create non-standard looping constructs which are one-in/one-out, but which have complex relationships among the variables being stepped. An additional observation should be made, of course: in the example above, the use of procedure calls hasn't endowed the program with any more structure than the use of flag variables or PROGRAM-COUNTER did, compared with the GOTO version. All it has done is possibly make the code more palatable. This may be a useful psychological illusion, but it is as much a myth as the belief that procedure calls are inherently expensive. ”

“ On the other hand, such a form will have subforms which do produce values, for example references to variables.
Thus the forms to be dealt with in the code generator can be divided into those which produce values and those which do not. Initially the latter will always be attacked, as the body of a "function"; later the former will be seen.
COMP-BODY takes a valueless form and compiles it. The routine ANALYZE, which we will see later, handles valued forms.
COMP-BODY instantiates a by now familiar theme: it simply dispatches on the type of BODY to some specialist routine. ”

“ Compiler writers have often simplified their job at the expense of the procedure call by adopting certain standard protocols. One of these is that the called procedure should save all registers that it uses. This is in turn often simplified to "save all registers". It is seldom the case that all of these registers actually need to be saved; indeed, in statement-oriented languages such as FORTRAN with little global optimization by the compiler, often no registers need be saved across a procedure call! ”

“ ERASE-NODES is used by the optimizer to destroy nodes which have been removed from the program tree because of some optimization. If ALLP is NIL (ERASE-NODE) , then only the given node is erased; if it is T (ERASE-ALL-NODES) , then the given node and all descendants, direct and indirect, are erased.
Erasing a node may involve removing certain properties from property lists. This is necessary to maintain the consistency of the properties. For example, if a VARIABLE node is erased, then that node must be removed from the READ-REFS property of the variable name. ”

“ It turns out that in most programming languages (COBOL, PL/I, FORTRAN. and LISP in particular) the distinction between lexical and dynamic scoping doesn't matter most of the time anyway. We should leave the compiler free to produce the best possible code; only in cases where structures are explicitly declared to be dynamically referenced should the compiler be forced to leave them on the stack in an otherwise tail-recursive situation.
In general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly encoded as JUMP instructions. ”

“ There is a reasonably direct correspondence between constructs in the CPS language and "machine-language" operations (if one assumes CONS to be a "machine-language" primitive for augmenting environment structure, which we do) . The later passes are complicated only by the desire to handle certain special cases in an optimal manner, most particularly the case of a function call whose function position contains a variable which can be determined to refer to a known LAMBDA-expression. ”

“ Procedure calls permit an extraordinarily powerful style of programming which, even though it is completely "structured", includes most rat's nests of GOTO statements as a subset. This style merely involves writing a procedure call where one would ordinarily write a GOTO at the end of a procedure. (The technique will not reproduce the "escape expression" effect of writing a GOTO from inside a loop to outside the loop, however.) This style is sufficiently powerful to represent any flowchart without introducing flag variables or GOTO statements. ”

“ Imperative constructs are easily modelled by applicative definitions. Anonymous functions make it easy to avoid needless duplication of code and conflict of variable names. A language with these properties is useful not only at the preliminary optimization level, but for expressing the results of decisions about order of evaluation and storage of temporary quantities. These properties make SCHEME as good a candidate as any for an UNCOL. The proper treatment of functions and function calls leads to generation of excellent imperative low-level code. ”

“ Here we shall consider an example of how expressive procedure calls can be when used freely. The example is taken from Yourdon [You75,233] ; he implies that the program was an actual one in use. He suggests that, rather than using many flag variables to indicate various conditions within a program, one should use a single variable which encodes the state of the program. The motivation behind this is that one should also draw a state diagram showing the valid transitions between states; the programmer is encouraged to think of his program as a finite-state automaton. ”

“ META-COMBINATION-TRIVFN performs the standard recursive meta-evaluation of all the arguments, and then checks to see whether the combination can be "folded". This is possible all the arguments are constants, and if the function has no side effects and cannot be affected by side-effects, or has an OKAY-TO-FOLD property. If this is the case, the function is applied to the arguments, the combination node and its descendants are erased, the statistics counter *FOLD-COUNT* is bumped, and a new CONSTANT node containing the result is created and meta-evaluated. ”

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

“ A small number of optimization techniques, coupled with the treatment of function calls as GOTO statements, serve to produce code as good as that produced by more traditional compilers. The macro approach enables speedy implementation of new constructs as desired without sacrificing efficiency in the generated code. A fair amount of analysis is devoted to determining whether environments may be stack-allocated or must be heap-allocated. ”

“ T VALUE: 1 Constants and variables are always trivial, and trivial combinations (involving only MacLISP primitives) are located. As before, in this pass information sifts up from below. One possibility not yet explored in RABBIT is to isolate entire SCHEME functions (for example FNVAR-Z) , determine that it is, as a whole, trivial, compile it as a simple MacLISP SUBR, and reference it as a primitive. ”

“ This is a technique which should be understood quite thoroughly, since it is the key to writing correct macro rules without any possibility of conflicts between names used by the user and those needed by the macro. As another example, let us consider the AND and OR constructs as used by most LISP systems.
OR evaluates its arguments one by one, in order, returning the first non-NIL value obtained (without evaluating any of the following arguments) , or NIL if all arguments produce NIL. AND is the dual to this; it returns NIL if any argument does, and otherwise the value of the last argument. ”

“ If flow analysis determines that a given variable always denotes (a closure of) a given functional (CLANBDA) expression, then a KNOWN-FUNCTION property is created to connect the variable directly to the function for the benefit of the code generator.
BIND-ANALYZE is just a simple dispatch to one of many specialists, one for each type of CNODE. TRIVIAL and CVARIABLE cnodes are handled directly because they are simple. ”

“ If one does, then it is easy to see the effect of expanding a PROG into a giant LABELS as outlined in [Imperative] and elsewhere: normally, a GOTO to a tag at the same level of PROG will involve no adjustment of environment, and so compile into a simple GOTO instruction, whereas a GOTO to a tag at aux outer level of PROG probably will involve adjusting the environment from that of the inner PROG to that of the outer. All of this falls out of the proper imperative treatment of function calls. ”

“ Currently there is not any attempt to perform the inverse of beta-conversion. This process would be that of locating common subexpressions of some single large expression, making that large expression the body of a LAMBDA-expression of one parameter, replacing all occurrences of the common subexpression by a reference to the parameter, and replacing the large expression by a combination whose function position contained the LAMBDA-expression and whose argument was a copy of the common subexpression. ”

“ An important point here is that one can write these rules in terms of other macro constructs such as OR and BLOCK; moreover, any extensions to BLOCK, such as the limited assignment feature described above, are automatically inherited by COND.
Thus with the above definition one could write (COND ( (NUMBERP X) (Y := (SORT X) ) (+ Y (SORT Y) ) ) (T (HACK X) ) ) where the scope of the variable Y is the remainder of the first COND clause.
SCHEME also provides macros for such constructs as DO and PROG, all of which expand into similar kinds of code using LAMBDA, IF, and LABELS (see below) . ”

“ Within the compiler an environment structure is also represented as a simple list, with the name of a variable occupying the position which its value will occupy in the run-time environment.
For every CLANBDA, CONTINUATION, and CLABELS, a slot called CONSENV is filled in, which is a list representing what the environment structure will look like when the closure (s) for that construct are to be constructed, if any. This is done by walking over the cnode-tree and doing to the environment representation precisely what will be done to the real environment at run time. ”

“ One problem in the code generator is that most functions need to be able to return two things: the code generated for a given cnode-tree, and a list of functions encountered in the cnode-tree, for which code is to generated separately later. we solve this problem by a stylistic trick, namely the explicit use of continuation-passing style. Many functions in the code generator take an argument named "C". This argument is itself a function of two arguments: the generated code and the deferred-function list. ”

“ The macro facility and the optimization techniques used by the compiler can be conceptually unified. The same properties which make it easy to write the macros make it easy to define optimizations correctly. In the same way that many programming constructs are defined in terms of a small, well-chosen basis set, so a large number of traditional optimization techniques fall out as special cases of the few used in RABBIT. This is no accident. ”

“ The switch *REANALYZE* may be set to the symbol ALL to force all descendants of a node to be reanalyzed before analyzing the node itself. This ability is provided to test for certain bugs in the optimizer. If the incremental analysis should fail for some reason, then the descendant nodes may not contain correct information (for example, their information slots may be empty!) . The ALL setting ensures that a consistent analysis is obtained. If the optimizer's behavior differs depending on whether *REANALYZE* contains ONCE or ALL, been then a problem with the incremental analysis is implicated. ”

“ Any one advantage of lexical scoping may often be countered with "Yes, but you can do that in this other way in a dynamically scoped LISP." However, we are convinced that lexical scoping in its totality provides all of the advantages to be described in a natural, elegant, and integrated manner, largely as a consequence of its great simplicity.
There are those to whom lexical scoping is nothing new, for example the ALGOL community. For this audience, however, we should draw attention to another important feature of SCHEME, which is that functions are first-class data objects. ”

“ The first level is the fully applicative level, to which most source-language constructs are easily reduced; the second is the continuation-passing style level, which is easily reduced to machine language. We envision building a compiler in three stages: (a) reduction of a user language to basic SCHEME, whether by macros, a parser of algebraic syntax, or some other means; (b) optimization by means of SCHEME-level source-to-source transformations, and conversion to continuation-passing style; and (c) generation of code for a particular machine. ”

“ Preliminary analysis The preliminary analysis ("phase l") is in three passes, each involving a tree-walk of the node structure, filling in information slots at each node. (Two passes would have sufficed, but for reasons of clarity and modularity there is one pass for each type of analysis.) The first pass (ENV-ANALYZE) analyzes variable references. For each node we determine the set of all gag (bound) variables referenced at or below that node. ”

“ The COMPILE function is the main top-level function of the compiler. It is responsible for invoking each phase of the compiler in order. NAME is the name of a function (an atomic symbol) , and LAMBDA-EXP the corresponding lambda-expression; these are easily extracted, for example, from a SCHEME DEFINE-form.
SEE-CRUD is NIL for normal processing, or T for debugging purposes. OPTIMIZE is a switch controlling whether the optimization phase should be invoked; it can be T, NIL, or MAYBE (meaning to ask the (human) debugger) .
The overall flow within COMPILE is as follows: check number of arguments ”

“ EFFECTLESS is a predicate which is true of an empty set of side-effects.
EFFECTLESS-EXCEPT-CONS is a predicate true of a set of side-effects which is empty except possibly for the CONS side-effect.
PASSABLE takes a node and two sets of side-effects, which should be the EFFS and AFFD sets from some other node. PASSABLE is a predicate which is true if the given node, which originally preceded the second in the standard evaluation order, can legitimately be postponed until after the second is evaluated. That is, it is true iff the first node can 'pass' the second during the substitution process. ”