Now that we have seen all the elements of the compiler, let us examine an example of compiled code to see how things fit together. We will compile the definition of a recursive factorial function by calling compile:
compile(parse(" \ function factorial(n) { \ return n === 1 \ ? 1" \ : n * factorial(n - 1);\ } "), "val", "next");
We have specified that the value of the define expression should be placed in the val register. We don't care what the compiled code does after executing the define, so our choice of next as the linkage descriptor is arbitrary.
Compile determines that the expression is a definition, so it calls compile_definition to compile code to compute the value to be assigned (targeted to val), followed by code to install the definition, followed by code to put the value of the define (which is the symbol ok) into the target register, followed finally by the linkage code. Env is preserved around the computation of the value, because it is needed in order to install the definition. Because the linkage is next, there is no linkage code in this case. The skeleton of the compiled code is thus $\langle \textit{save}$ env $\textit{if modified by code to compute value}\rangle$ $\langle \textit{compilation of definition value, target}$ val$, \textit{linkage}$ next$\rangle$ $\langle \textit{restore}$ env $\textit{if saved above}\rangle$ perform( op("define_variable"), constant("factorial"), reg("val"), reg("env")); assign("val", constant(ok));
The expression that is to be compiled to produce the value for the variable factorial is a lambda expression whose value is the function that computes factorials. Compile handles this by calling compile_lambda, which compiles the function body, labels it as a new entry point, and generates the instruction that will combine the function body at the new entry point with the run-time environment and assign the result to val. The sequence then skips around the compiled function code, which is inserted at this point. The function code itself begins by extending the function's definition environment by a frame that binds the formal parameter n to the function argument. Then comes the actual function body. Since this code for the value of the variable doesn't modify the env register, the optional save and restore shown above aren't generated. (The function code at entry2 isn't executed at this point, so its use of env is irrelevant.) Therefore, the skeleton for the compiled code becomes assign("val", list(op("make_compiled_function"), label(entry2), reg("env"))), go_to(label("after_lambda1")), "entry2", assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(n), reg("argl"), reg("env"))), $\langle \textit{compilation of procedure body} \rangle$ "after_lambda1", perform(op("define-variable"), constant("factorial"), reg("val"), reg("env")), assign("val", constant(ok)),
A function body is always compiled (by compile_lambda_body) as a sequence with target val and linkage return. The sequence in this case consists of a single if expression:
n === 1 ? 1 : n * factorial(n - 1)
Compile_if generates code that first computes the predicate (targeted to val), then checks the result and branches around the true branch if the predicate is false. Env and continue are preserved around the predicate code, since they may be needed for the rest of the if expression. Since the if expression is the final expression (and only expression) in the sequence making up the function body, its target is val and its linkage is return, so the true and false branches are both compiled with target val and linkage return. (That is, the value of the conditional, which is the value computed by either of its branches, is the value of the function.) $\langle \textit{save}$ continue$,$ env $\textit{if modified by predicate and needed by branches} \rangle$ $\langle \textit{compilation of predicate, target}$ val$, \textit{linkage}$ next$\rangle$ $\langle \textit{restore}$ continue$,$ env $\textit{if saved above}\rangle$ test(op("false"), reg("val")), branch(label("false_branch4")), "true_branch5", $\langle \textit{compilation of true branch, target}$ val$, \textit{linkage}$ return$\rangle$ "false_branch4", $\langle \textit{compilation of false branch, target}$ val$, \textit{linkage}$ return$\rangle$ "after_if3",
The predicate n === 1 is a function call. This looks up the operator (the symbol =) and places this value in fun. It then assembles the arguments 1 and the value of n into argl. Then it tests whether fun contains a primitive or a compound function, and dispatches to a primitive branch or a compound branch accordingly. Both branches resume at the after_call label. The requirements to preserve registers around the evaluation of the operator and operands don't result in any saving of registers, because in this case those evaluations don't modify the registers in question.
assign("fun", list(op("lookup_variable_value"), constant("="), reg("env"))), assign("val", constant(1)), assign("argl", list(op("list"), reg("val"))), assign("val", list(op("lookup_variable_value"), constant(n), reg("env"))), assign("argl", list(op("cons"), reg("val"), reg("argl"))), test(op("primitive_function"), reg("fun")), branch(label("primitive_branch17")), "compiled_branch16", assign("continue", list(label("after_call15"))), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch17", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call15",
The true branch, which is the constant 1, compiles (with target val and linkage return) to
assign("val", constant(1)), go_to(reg("continue")),
The code for the false branch is another a function call, where the function is the value of the symbol *, and the arguments are n and the result of another function call (a call to factorial). Each of these calls sets up fun and argl and its own primitive and compound branches. Figure shows the complete compilation of the definition of the factorial function. Notice that the possible save and restore of continue and env around the predicate, shown above, are in fact generated, because these registers are modified by the function call in the predicate and needed for the function call and the return linkage in the branches.
function factorial_alt(n) { return n === 1 ? 1 : factorial_alt(n - 1) * n; }
function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(product * counter, counter + 1); } return iter(1, 1); }
assign("val", op("lookup-variable-value"), constant("a"), reg("env")), assign("val", op("+"), reg("val"), constant(1)),