The essence of the compilation process is the compilation of function applications. The code for an application compiled with a given target and linkage has the form $\langle{}$compilation of function expression, target fun, linkage "next"$\rangle$ $\langle{}$evaluate argument expressions and construct argument list in argl$\rangle$ $\langle{}$compilation of function call with given target and linkage$\rangle$ The registers env, fun, and argl may have to be saved and restored during evaluation of the function and argument expressions. Note that this is the only place in the compiler where a target other than val is specified.
The required code is generated by compile_application. This recursively compiles the function expression, to produce code that puts the function to be applied into fun, and compiles the argument expressions, to produce code that evaluates the individual argument expressions of the application. The instruction sequences for the argument expressions are combined (by construct_arglist) with code that constructs the list of arguments in argl, and the resulting argument-list code is combined with the function code and the code that performs the function call (produced by compile_function_call). In appending the code sequences, the env register must be preserved around the evaluation of the function expression (since evaluating the function expression might modify env, which will be needed to evaluate the argument expressions), and the fun register must be preserved around the construction of the argument list (since evaluating the argument expressions might modify fun, which will be needed for the actual function application). The continue register must also be preserved throughout, since it is needed for the linkage in the function call.
function compile_application(exp, target, linkage) {
const fun_code = compile(function_expression(exp), "fun", "next");
const argument_codes = map(arg => compile(arg, "val", "next"),
arg_expressions(exp));
return preserving(list("env", "continue"),
fun_code,
preserving(list("fun", "continue"),
construct_arglist(argument_codes),
compile_function_call(target, linkage)));
}The code to construct the argument list will evaluate each argument expression into val and then combine that value with the argument list being accumulated in argl using pair. Since we adjoin the arguments to the front of argl in sequence, we must start with the last argument and end with the first, so that the arguments will appear in order from first to last in the resulting list. Rather than waste an instruction by initializing argl to the empty list to set up for this sequence of evaluations, we make the first code sequence construct the initial argl. The general form of the argument-list construction is thus as follows: $\langle{}$compilation of last argument, targeted to val$\rangle$ assign("argl", list(op("list"), reg("val"))), $\langle{}$compilation of next argument, targeted to val$\rangle$ assign("argl", list(op("pair"), reg("val"), reg("argl"))), $\ldots$ $\langle{}$compilation of first argument, targeted to val$\rangle$ assign("argl", list(op("pair"), reg("val"), reg("argl"))), The argl register must be preserved around each argument evaluation except the first (so that arguments accumulated so far won't be lost), and env must be preserved around each argument evaluation except the last (for use by subsequent argument evaluations).
Compiling this argument code is a bit tricky, because of the special treatment of the first argument expression to be evaluated and the need to preserve argl and env in different places. The construct_arglist function takes as arguments the code that evaluates the individual argument expressions. If there are no argument expressions at all, it simply emits the instruction
assign(argl, constant(null))
function construct_arglist(arg_codes) {
if (is_null(arg_codes)) {
return make_instruction_sequence(null, list("argl"),
list(assign("argl", constant(null))));
} else {
const rev_arg_codes = reverse(arg_codes);
const code_to_get_last_arg =
append_instruction_sequences(
head(rev_arg_codes),
make_instruction_sequence(list("val"), list("argl"),
list(assign("argl",
list(op("list"), reg("val"))))));
return is_null(tail(rev_arg_codes))
? code_to_get_last_arg
: preserving(list("env"),
code_to_get_last_arg,
code_to_get_rest_args(tail(rev_arg_codes)));
}
}
function code_to_get_rest_args(arg_codes) {
const code_for_next_arg =
preserving(list("argl"),
head(arg_codes),
make_instruction_sequence(list("val", "argl"), list("argl"),
list(assign("argl", list(op("pair"),
reg("val"), reg("argl"))))));
return is_null(tail(arg_codes))
? code_for_next_arg
: preserving(list("env"),
code_for_next_arg,
code_to_get_rest_args(tail(arg_codes)));
}After evaluating the elements of a function application, the compiled code must apply the function in fun to the arguments in argl. The code performs essentially the same dispatch as the apply function in the metacircular evaluator of section 4.1.1 or the apply_dispatch entry point in the explicit-control evaluator of section 5.4.1. It checks whether the function to be applied is a primitive function or a compiled function. For a primitive function, it uses apply_primitive_function; we will see shortly how it handles compiled functions. The function-application code has the following form: $\texttt{ }\texttt{ }$test(list(op("primitive_function"), reg("fun"))), branch(label("primitive_branch")), "compiled_branch", $\langle{}$code to apply compiled function with given target and appropriate linkage$\rangle$ "primitive_branch", assign($target$, list(op("apply_primitive_function"), reg("fun"), reg("argl"))), $\langle{}$linkage$\rangle$ "after_call" Observe that the compiled branch must skip around the primitive branch. Therefore, if the linkage for the original function call was "next", the compound branch must use a linkage that jumps to a label that is inserted after the primitive branch. (This is similar to the linkage used for the true branch in compile_conditional.)
function compile_function_call(target, linkage) {
const primitive_branch = make_label("primitive_branch");
const compiled_branch = make_label("compiled_branch");
const after_call = make_label("after_call");
const compiled_linkage = linkage === "next" ? after_call : linkage;
return append_instruction_sequences(
make_instruction_sequence(list("fun"), null,
list(test(list(op("is_primitive_function"), reg("fun"))),
branch(label(primitive_branch)))),
append_instruction_sequences(
parallel_instruction_sequences(
append_instruction_sequences(
compiled_branch,
compile_fun_appl(target, compiled_linkage)),
append_instruction_sequences(
primitive_branch,
end_with_linkage(linkage,
make_instruction_sequence(list("fun", "argl"),
list(target),
list(assign(
target,
list(op("apply_primitive_function"),
reg("fun"), reg("argl")))))))),
after_call));
}The handling of function application and return is the most subtle part of the compiler. A compiled function (as constructed by compile_lambda_expression) has an entry point, which is a label that designates where the code for the function starts. The code at this entry point computes a result in val and ends by executing the instructions from a compiled return statement.
The code for a compiled-function application uses the stack in the same way as the explicit-control evaluator (section 5.4.1): before jumping to the compiled function's entry point, it saves the continuation of the function call to the stack, followed by a mark that allows reverting the stack to the state right before the call with the continuation on top. $\texttt{ }\texttt{ }$// set up for return from function save("continue"), push_marker_to_stack(), // jump to the function's entry point assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), Compiling a return statement (with compile_return_statement) generates corresponding code for reverting the stack and restoring and jumping to continue. $\texttt{ }\texttt{ }$revert_stack_to_marker(), restore("continue"), $\langle{}$evaluate the return expression and store the result in val$\rangle$ go_to(reg("continue")), // $\texttt{"return"}$-linkage code Unless a function enters an infinite loop, it will end by executing the above return code, resulting from either a return statement in the program or one inserted by compile_lambda_body to return undefined.[1]
Straightforward code for a compiled-function application with a given target and linkage would set up continue to make the function return to a local label instead of to the final linkage, to copy the function value from val to the target register if necessary. It would look like this if the linkage is a label: $\texttt{ }\texttt{ }$assign("continue", label("fun_return")), // where function should return to save("continue"), // will be restored by the function push_marker_to_stack(), // allows the function to revert stack to find $\texttt{fun_return}$ assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), // eventually reverts stack, restores and jumps to $\texttt{continue}$ "fun_return", // the function returns to here assign($\mathit{target}$, reg("val")), // included if target is not $\texttt{val}$ go_to(label($linkage$)), // linkage code or like this—saving the caller's continuation at the start in order to restore and go to it at the end—if the linkage is "return" (that is, if the application is in a return statement and its value is the result to be returned): $\texttt{ }\texttt{ }$save("continue"), // save the caller's continuation assign("continue", label("fun_return")), // where function should return to save("continue"), // will be restored by the function push_marker_to_stack(), // allows the function to revert stack to find $\texttt{fun_return}$ assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), // eventually reverts stack, restores and jumps to $\texttt{continue}$ "fun_return", // the function returns to here assign($\mathit{target}$, reg("val")), // included if target is not $\texttt{val}$ restore("continue"), // restore the caller's continuation go_to(reg("continue")), // linkage code This code sets up continue so that the function will return to a label fun_return and jumps to the function's entry point. The code at fun_return transfers the function's result from val to the target register (if necessary) and then jumps to the location specified by the linkage. (The linkage is always "return" or a label, because compile_function_call replaces a "next" linkage for the compound-function branch by an after_call label.) Before jumping to the function's entry point, we save continue and execute push_marker_to_stack() to enable the function to return to the intended location in the program with the expected stack. Matching revert_stack_to_marker() and restore("continue") instructions are generated by compile_return_statement for each return statement in the body of the function.[2]
In fact, if
the target is not val,
the above is
exactly the code our compiler will generate.[3]
Usually, however, the target is val (the only
time the compiler specifies a different register is when targeting the
evaluation of
a function expression
to
fun),
so the
function
result is put directly into
the target register and there is no need to
jump
to a special
location that copies it. Instead we simplify the code by
setting up continue so that the
called function
will
return
directly to the place specified by the caller's linkage:
$\langle{}$set up continue for linkage and push the marker$\rangle$
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
If the linkage is a label, we set up continue
so that the
function
will continue at
that label. (That is, the
go_to(reg("continue"))
the
called function
ends with becomes equivalent to the
go_to(label($linkage$))
at
fun_return
above.)
assign("continue", label($linkage$)),
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),
If the linkage is
"return",
we don't need to
assign continue:
It already holds the desired location.
(That is, the
go_to(reg("continue"))
the
called function
ends with goes directly to the
place where the
go_to(reg("continue"))
at
fun_{\hspace{0pt}}return
would have gone.)
save("continue"),
push_marker_to_stack(),
assign("val", list(op("compiled_function_entry"), reg("fun"))),
go_to(reg("val")),Suppose instead that we had handled the case of a function call with a linkage of "return" and a target of val in the same way as for a non-val target. This would destroy tail recursion. Our system would still return the same value for any function call. But each time we called a function, we would save continue and return after the call to undo the (useless) save. These extra saves would accumulate during a nest of function calls.[4]
The function compile_fun_appl generates the above function-application code by considering four cases, depending on whether the target for the call is val and whether the linkage is "return". Observe that the instruction sequences are declared to modify all the registers, since executing the function body can change the registers in arbitrary ways.[5] function compile_fun_appl(target, linkage) { const fun_return = make_label("fun_return"); return target === "val" && linkage !== "return" ? make_instruction_sequence(list("fun"), all_regs, list(assign("continue", label(linkage)), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")))) : target !== "val" && linkage !== "return" ? make_instruction_sequence(list("fun"), all_regs, list(assign("continue", label(fun_return)), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), fun_return, assign(target, reg("val")), go_to(label(linkage)))) : target === "val" && linkage === "return" ? make_instruction_sequence(list("fun", "continue"), all_regs, list(save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")))) : // $\texttt{target !== "val" \&\& linkage === "return"}$ error(target, "return linkage, target not val -- compile"); }
We have shown how to generate tail-recursive linkage code for a function application when the linkage is "return"—that is, when the application is in a return statement and its value is the result to be returned. Similarly, as explained in section 5.4.1, the stack-marker mechanism used here (and in the explicit-control evaluator) for the call and return produces tail-recursive behavior only in that situation. These two aspects of the code generated for function application combine to ensure that when a function ends by returning the value of a function call, no stack accumulates.
The code for a return statement takes the following form, regardless of the given linkage and target: revert_stack_to_marker(), restore("continue"), // saved by $\texttt{compile\char`_fun\char`_appl}$ $\langle{}$evaluate the return expression and store the result in val$\rangle$ go_to(reg("continue")) // $\texttt{"return"}$-linkage code The instructions to revert the stack using the marker and then restore continue correspond to the instructions generated by compile_fun_appl to save continue and mark the stack. The final jump to continue is generated by the use of the "return" linkage when compiling the return expression. The function compile_return_statement is different from all other code generators in that it ignores the target and linkage arguments—it always compiles the return expression with target val and linkage "return".
function compile_return_statement(stmt, target, linkage) {
return append_instruction_sequences(
make_instruction_sequence(null, list("continue"),
list(revert_stack_to_marker(),
restore("continue"))),
compile(return_expression(stmt), "val", "return"));
}
const all_regs = list("env", "fun", "val", "argl", "continue");