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 declaration of a recursive factorial factorial procedure function by calling compile: by passing as first argument to compile the result of applying parse to a string representation of the program (here using back quotes `$\ldots$`, which work like single and double quotation marks but allow the string to span multiple lines):

Original	JavaScript
(compile '(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) 'val 'next)	compile(parse(` function factorial(n) { return n === 1 ? 1 : factorial(n - 1) * n; } `), "val", "next");

We have specified that the value of the define expression declaration should be placed in the val register. We don't care what the compiled code does after executing the define, declaration, so our choice of next "next" as the linkage descriptor is arbitrary.

Compile determines that the expression is a definition, so it The function compile determines that it was given a function declaration, so it transforms it to a constant declaration and then calls compile-definition to compile compile_declaration. This compiles code to compute the value to be assigned (targeted to val), followed by code to install the definition, declaration, followed by code to put the value of the define (which is the symbol ok) declaration (which is the value undefined) into the target register, followed finally by the linkage code. Env The env register is preserved around the computation of the value, because it is needed in order to install the definition. declaration. Because the linkage is next, "next", there is no linkage code in this case. The skeleton of the compiled code is thus

Original	JavaScript
$\langle save$ env $if\ modified\ by\ code\ to\ compute\ value\rangle$ $\langle compilation\ of\ definition\ value, target$ val$, linkage$ next$\rangle$ $\langle restore$ env $if\ saved\ above\rangle$ (perform (op define-variable!) (const factorial) (reg val) (reg env)) (assign val (const ok))	$\langle{}$save env if modified by code to compute value$\rangle$ $\langle{}$compilation of declaration value, target val, linkage "next"$\rangle$ $\langle{}$restore env if saved above$\rangle$ perform(list(op("assign_symbol_value"), constant("factorial"), reg("val"), reg("env"))), assign("val", constant(undefined))

The expression that is to be compiled to produce the value for the variable name factorial is a lambda lambda expression whose value is the procedure function that computes factorials. Compile The function compile handles this by calling compile-lambda, compile_lambda_expression, which compiles the procedure function body, labels it as a new entry point, and generates the instruction that will combine the procedure function body at the new entry point with the runtime environment and assign the result to val. The sequence then skips around the compiled procedure function code, which is inserted at this point. The procedure function code itself begins by extending the procedure's definition function's declaration environment by a frame that binds the formal parameter n to the procedure function argument. Then comes the actual procedure function body. Since this code for the value of the variable name doesn't modify the env register, the optional save and restore shown above aren't generated. (The procedure function code at entry2entry1 isn't executed at this point, so its use of env is irrelevant.) Therefore, the skeleton for the compiled code becomes

Original

JavaScript

(assign val (op make-compiled-procedure) (label entry2) (reg env)) (goto (label after-lambda1)) entry2 (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (n)) (reg argl) (reg env)) $\langle compilation\ of\ procedure\ body\rangle$ after-lambda1 (perform (op define-variable!) (const factorial) (reg val) (reg env)) (assign val (const ok))

$\texttt{ }\texttt{ }$assign("val", list(op("make_compiled_function"), label("entry1"), reg("env"))), go_to(label("after_lambda2")), "entry1", assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(list("n")), reg("argl"), reg("env"))), $\langle{}$compilation of function body$\rangle$ "after_lambda2", perform(list(op("assign_symbol_value"), constant("factorial"), reg("val"), reg("env"))), assign("val", constant(undefined))

A procedure function body is always compiled (by compile-lambda-body) compile_lambda_body) as a sequence with target val and linkage return. "next". The sequence body in this case consists of a single if expression: return statement:[1]

Original	JavaScript
(if (= n 1) 1 (* (factorial (- n 1)) n))	return n === 1 ? 1 : factorial(n - 1) * n;

Original		JavaScript
		The function compile_return_statement generates code to revert the stack using the marker and to restore the continue register, and then compiles the return expression with target val and linkage "return", because its value is to be returned from the function.

Compile-if The return expression is a conditional expression, for which compile_conditional 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 Registers env and continue are preserved around the predicate code, since they may be needed for the rest of the if conditional expression.

Original		JavaScript
Since the if expression is the final expression (and only expression) in the sequence making up the procedure body, its target is val and its linkage is return, so the		The

true and false branches are both compiled with target val and linkage return. "return". (That is, the value of the conditional, which is the value computed by either of its branches, is the value of the procedure.) function.)

Original

JavaScript

$\langle save$ continue, env $if\ modified\ by\ predicate\ and\ needed\ by\ branches\rangle$ $\langle compilation\ of\ predicate, target$ val$,\ linkage$ next$\rangle$ $\langle restore$ continue, env $if\ saved\ above\rangle$ (test (op false?) (reg val)) (branch (label false-branch4)) true-branch5 $\langle compilation\ of\ true\ branch, target$ val$,\ linkage$ return$\rangle$ false-branch4 $\langle compilation\ of\ false\ branch, target$ val$,\ linkage$ return$\rangle$ after-if3

$\texttt{ }\texttt{ }$revert_stack_to_marker(), restore("continue"), $\langle{}$save continue, env if modified by predicate and needed by branches$\rangle$ $\langle{}$compilation of predicate, target val, linkage "next"$\rangle$ $\langle{}$restore continue, env if saved above$\rangle$ test(list(op("is_falsy"), reg("val"))), branch(label("false_branch4")), "true_branch3", $\langle{}$compilation of true branch, target val, linkage "return"$\rangle$ "false_branch4", $\langle{}$compilation of false branch, target val, linkage "return"$\rangle$ "after_cond5",

The predicate (= n 1) n === 1 is a procedure call. function application (after transformation of the operator combination). This looks up the operator (the symbol =) function expression (the symbol "===") and places this value in proc. fun. It then assembles the arguments 1 and the value of n into argl. Then it tests whether proc fun contains a primitive or a compound procedure, function, and dispatches to a primitive branch or a compound branch accordingly. Both branches resume at the after-call after_call label. The compound branch must set up continue to jump past the primitive branch and push a marker to the stack to match the revert operation in the compiled return statement of the function. The requirements to preserve registers around the evaluation of the operator and operands function and argument expressions don't result in any saving of registers, because in this case those evaluations don't modify the registers in question.

Original

JavaScript

(assign proc (op lookup-variable-value) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookup-variable-value) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch17)) compiled-branch16 (assign continue (label after-call15)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch17 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call15

$\texttt{ }\texttt{ }$assign("fun", list(op("lookup_symbol_value"), constant("==="), reg("env"))), assign("val", constant(1)), assign("argl", list(op("list"), reg("val"))), assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))), assign("argl", list(op("pair"), reg("val"), reg("argl"))), test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch6")), "compiled_branch7", assign("continue", label("after_call8")), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch6", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call8",

The true branch, which is the constant 1, compiles (with target val and linkage return) "return") to

Original	JavaScript
(assign val (const 1)) (goto (reg continue))	$\texttt{ }\texttt{ }$assign("val", constant(1)), go_to(reg("continue")),

The code for the false branch is another procedure function call, where the procedure function is the value of the symbol *, "*", and the arguments are n and the result of another procedure function call (a call to factorial). Each of these calls sets up proc fun and argl and its own primitive and compound branches. Figure 5.22 shows the complete compilation of the definition declaration of the factorial procedure. 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 procedure function call in the predicate and needed for the procedure function call and the return "return" linkage in the branches.

Exercise 5.37 Consider the following declaration of a factorial procedure, function, which is slightly different from the one given above:

Original	JavaScript
(define (factorial-alt n) (if (= n 1) 1 (* n (factorial-alt (- n 1)))))	function factorial_alt(n) { return n === 1 ? 1 : n * factorial_alt(n - 1); }

Compile this procedure function and compare the resulting code with that produced for factorial. Explain any differences you find. Does either program execute more efficiently than the other?

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.38 Compile the iterative factorial procedure function

Original	JavaScript
(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))	function factorial(n) { function iter(product, counter) { return counter > n ? product : iter(product * counter, counter + 1); } return iter(1, 1); }

Annotate the resulting code, showing the essential difference between the code for iterative and recursive versions of factorial that makes one process build up stack space and the other run in constant stack space.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.39 What expression program was compiled to produce the code shown in figure 5.24?

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.40 What order of evaluation does our compiler produce for operands of a combination? arguments of an application? Is it left-to-right (as mandated by the ECMAScript specification), right-to-left, or some other order? Where in the compiler is this order determined? Modify the compiler so that it produces some other order of evaluation. (See the discussion of order of evaluation for the explicit-control evaluator in section 5.4.1.) How does changing the order of operand argument evaluation affect the efficiency of the code that constructs the argument list?

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.41 One way to understand the compiler's preserving mechanism for optimizing stack usage is to see what extra operations would be generated if we did not use this idea. Modify preserving so that it always generates the save and restore operations. Compile some simple expressions and identify the unnecessary stack operations that are generated. Compare the code to that generated with the preserving mechanism intact.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 5.42 Our compiler is clever about avoiding unnecessary stack operations, but it is not clever at all when it comes to compiling calls to the primitive procedures functions of the language in terms of the primitive operations supplied by the machine. For example, consider how much code is compiled to compute (+ a 1): a + 1: The code sets up an argument list in argl, puts the primitive addition procedure function (which it finds by looking up the symbol + "+" in the environment) into proc, fun, and tests whether the procedure function is primitive or compound. The compiler always generates code to perform the test, as well as code for primitive and compound branches (only one of which will be executed). We have not shown the part of the controller that implements primitives, but we presume that these instructions make use of primitive arithmetic operations in the machine's data paths. Consider how much less code would be generated if the compiler could open-code primitives—that is, if it could generate code to directly use these primitive machine operations. The expression (+ a 1) a + 1 might be compiled into something as simple as[2]

Original	JavaScript
(assign val (op lookup-variable-value) (const a) (reg env)) (assign val (op +) (reg val) (const 1))	assign("val", list(op("lookup_symbol_value"), constant("a"), reg("env"))), assign("val", list(op("+"), reg("val"), constant(1)))

In this exercise we will extend our compiler to support open coding of selected primitives. Special-purpose code will be generated for calls to these primitive procedures functions instead of the general procedure-application function-application code. In order to support this, we will augment our machine with special argument registers arg1 and arg2. The primitive arithmetic operations of the machine will take their inputs from arg1 and arg2. The results may be put into val, arg1, or arg2.

The compiler must be able to recognize the application of an open-coded primitive in the source program. We will augment the dispatch in the compile procedure function to recognize the names of these primitives in addition to the reserved words (the special forms) it currently recognizes.[3] syntactic forms it currently recognizes. For each special syntactic form our compiler has a code generator. In this exercise we will construct a family of code generators for the open-coded primitives.

1. The open-coded primitives, unlike the special syntactic forms, all need their operands argument expressions evaluated. Write a code generator spread-arguments spread_arguments for use by all the open-coding code generators. Spread-arguments The function spread_arguments should take an operand list a list of argument expressions and compile the given operands argument expressions targeted to successive argument registers. Note that an operand argument expression may contain a call to an open-coded primitive, so argument registers will have to be preserved during operand argument-expression evaluation.

2. Original		JavaScript
   		The JavaScript operators ===, *, -, and +, among others, are implemented in the register machine as primitive functions and are referred to in the global environment with the symbols "===", "*", "-", and "+". In JavaScript, it is not possible to redeclare these names, because they do not meet the syntactic restrictions for names. This means it is safe to open-code them.

   For each of the primitive procedures functions =, ===, *, -, and +, write a code generator that takes a combination with that operator, an application with a function expression that names that function, together with a target and a linkage descriptor, and produces code to spread the arguments into the registers and then perform the operation targeted to the given target with the given linkage. You need only handle expressions with two operands. Make compile dispatch to these code generators.
3. Try your new compiler on the factorial example. Compare the resulting code with the result produced without open coding.

Original		JavaScript
Extend your code generators for + and * so that they can handle expressions with arbitrary numbers of operands. An expression with more than two operands will have to be compiled into a sequence of operations, each with only two inputs.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.