Original JavaScript
;; construct the procedure and skip over code for the procedure body (assign val (op make-compiled-procedure) (label entry2) (reg env)) (goto (label after-lambda1)) entry2 ; calls to factorial will enter here (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (n)) (reg argl) (reg env)) ;; begin actual procedure body (save continue) (save env) ;; compute (= n 1) (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 ; val now contains result of (= n 1) (restore env) (restore continue) (test (op false?) (reg val)) (branch (label false-branch4)) true-branch5 ; return 1 (assign val (const 1)) (goto (reg continue)) false-branch4 ;; compute and return $\texttt{(* (factorial (- n 1)) n)}$ (assign proc (op lookup-variable-value) (const *) (reg env)) (save continue) (save proc) ; save * procedure (assign val (op lookup-variable-value) (const n) (reg env)) (assign argl (op list) (reg val)) (save argl) ; save partial argument list for * ;; compute $\texttt{(factorial (- n 1))}$, which is the other argument for * (assign proc (op lookup-variable-value) (const factorial) (reg env)) (save proc) ; save factorial procedure // construct the function and skip over the code for the function body assign("val", list(op("make_compiled_function"), label("entry1"), reg("env"))), go_to(label("after_lambda2")), "entry1", // calls to $\texttt{factorial}$ will enter here assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(list("n")), reg("argl"), reg("env"))), // begin actual function body revert_stack_to_marker(), // starts with a return statement restore("continue"), save("continue"), // preserve registers across predicate save("env"), // compute $\texttt{n === 1}$ 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", // $\texttt{val}$ now contains result of $\texttt{n === 1}$ restore("env"), restore("continue"), test(list(op("is_falsy"), reg("val"))), branch(label("false_branch4")), "true_branch3", // return 1 assign("val", constant(1)), go_to(reg("continue")), "false_branch4", // compute and return $\texttt{factorial(n - 1) * n}$ assign("fun", list(op("lookup_symbol_value"), constant("*"), reg("env"))), save("continue"), save("fun"), // save $\texttt{*}$ function assign("val", list(op("lookup_symbol_value"), constant("n"), reg("env"))), assign("argl", list(op("list"), reg("val"))), save("argl"), // save partial argument list for $\texttt{*}$ // compute $\texttt{factorial(n - 1)}$ which is the other argument for $\texttt{*}$ assign("fun", list(op("lookup_symbol_value"), constant("factorial"), reg("env"))), save("fun"), // save $\texttt{factorial}$ function
Figure 5.22 Compilation of the declaration of the factorial procedure function (continued on next page).
Original JavaScript
;; $\texttt{compute (- n 1)}$, which is the argument for $\texttt{factorial}$ (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-branch8)) compiled-branch7 (assign continue (label after-call6)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch8 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call6 ; val now contains result of $\texttt{(- n 1)}$ (assign argl (op list) (reg val)) (restore proc) ; restore factorial ;; apply factorial (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch11)) compiled-branch10 (assign continue (label after-call9)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch11 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call9 ; val now contains result of $\texttt{(factorial (- n 1))}$ (restore argl) ; restore partial argument list for * (assign argl (op cons) (reg val) (reg argl)) (restore proc) ; restore * (restore continue) ;; apply * and return its value (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch14)) compiled-branch13 ;; note that a compound procedure here is called tail-recursively (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch14 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) (goto (reg continue)) after-call12 after-if3 after-lambda1 ;; assign the procedure to the variable factorial (perform (op define-variable!) (const factorial) (reg val) (reg env)) (assign val (const ok)) // compute $\texttt{n - 1}$ which is the argument for $\texttt{factorial}$ 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_branch10")), "compiled_branch11", assign("continue", label("after_call12")), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch10", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call12", // $\texttt{val}$ now contains result of $\texttt{n - 1}$ assign("argl", list(op("list"), reg("val"))), restore("fun"), // restore $\texttt{factorial}$ // apply $\texttt{factorial}$ test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch14")), "compiled_branch15", assign("continue", label("after_call16")), save("continue"), // set up for compiled function $-$ push_marker_to_stack(), // return in function will restore stack assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch14", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call16", // $\texttt{val}$ now contains result of $\texttt{factorial(n - 1)}$ restore("argl"), // restore partial argument list for $\texttt{*}$ assign("argl", list(op("pair"), reg("val"), reg("argl"))), restore("fun"), // restore $\texttt{*}$ restore("continue"), // apply $\texttt{*}$ and return its value test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch18")), "compiled_branch19", // note that a compound function here is called tail-recursively save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch18", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), go_to(reg("continue")), "after_call20", "after_cond5", "after_lambda2", // assign the function to the name $\texttt{factorial}$ perform(list(op("assign_symbol_value"), constant("factorial"), reg("val"), reg("env"))), assign("val", constant(undefined))
Figure 5.23 (continued)
Original JavaScript
(assign val (op make-compiled-procedure) label entry16) (reg env)) (goto (label after-lambda15)) entry16 (assign env (op compiled-procedure-env) (reg proc)) (assign env (op extend-environment) (const (x)) (reg argl) (reg env)) (assign proc (op lookup-variable-value) (const +) (reg env)) (save continue) (save proc) (save env) (assign proc (op lookup-variable-value) (const g) (reg env)) (save proc) (assign proc (op lookup-variable-value) (const +) (reg env)) (assign val (const 2)) (assign argl (op list) (reg val)) (assign val (op lookup-variable-value) (const x) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch19)) compiled-branch18 (assign continue (label after-call17)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch19 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call17 (assign argl (op list) (reg val)) (restore proc) (test (op primitive-procedure?) (reg proc)) (branch (label primitive-branch22)) compiled-branch21 (assign continue (label after-call20)) (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch22 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) $\texttt{ }\texttt{ }$assign("val", list(op("make_compiled_function"), label("entry1"), reg("env"))), "entry1" assign("env", list(op("compiled_function_env"), reg("fun"))), assign("env", list(op("extend_environment"), constant(list("x")), reg("argl"), reg("env"))), revert_stack_to_marker(), restore("continue"), assign("fun", list(op("lookup_symbol_value"), constant("+"), reg("env"))), save("continue"), save("fun"), save("env"), assign("fun", list(op("lookup_symbol_value"), constant("g"), reg("env"))), save("fun"), assign("fun", list(op("lookup_symbol_value"), constant("+"), reg("env"))), assign("val", constant(2)), assign("argl", list(op("list"), reg("val"))), assign("val", list(op("lookup_symbol_value"), constant("x"), reg("env"))), assign("argl", list(op("pair"), reg("val"), reg("argl"))), test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch3")), "compiled_branch4" assign("continue", label("after_call5")), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch3", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call5", assign("argl", list(op("list"), reg("val"))), restore("fun"), test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch7")), "compiled_branch8", assign("continue", label("after_call9")), save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch7", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), "after_call9", assign("argl", list(op("list"), reg("val"))), restore("env"), assign("val", list(op("lookup_symbol_value"), constant("x"), reg("env"))), assign("argl", list(op("pair"), reg("val"), reg("argl"))), restore("fun"), restore("continue"), test(list(op("is_primitive_function"), reg("fun"))), branch(label("primitive_branch11")),
Figure 5.24 An example of compiler output (continued on next page). See exercise 5.39.
Original JavaScript
after-call20 (assign argl (op list), (reg val)) (restore env) (assign val (op lookup-variable-value) (const x) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (restore proc) (restore continue) (test (op primitive-procedure?) (reg proc)) (branch label primitive-branch25)) compiled-branch24 (assign val (op compiled-procedure-entry) (reg proc)) (goto (reg val)) primitive-branch25 (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) (goto (reg continue)) after-call23 after-lambda15 (perform (op define-variable!) (const f) (reg val) (reg env)) (assign val (const ok)) "compiled_branch12", save("continue"), push_marker_to_stack(), assign("val", list(op("compiled_function_entry"), reg("fun"))), go_to(reg("val")), "primitive_branch11", assign("val", list(op("apply_primitive_function"), reg("fun"), reg("argl"))), go_to(reg("continue")), "after_call13", "after_lambda2", perform(list(op("assign_symbol_value"), constant("f"), reg("val"), reg("env"))), assign("val", constant(undefined))
Figure 5.25 (continued)

[1] Because of the append_return_undefined in compile_lambda_body, the body actually consists of a sequence with two return statements. However, the dead-code check in compile_sequence will stop after the compilation of the first return statement, so the body effectively consists of only a single return statement.
[2] We have used the same symbol + here to denote both the source-language procedure function and the machine operation. In general there will not be a one-to-one correspondence between primitives of the source language and primitives of the machine.
[3] Making the primitives into reserved words is in general a bad idea, since a user cannot then rebind these names to different procedures. Moreover, if we add reserved words to a compiler that is in use, existing programs that define procedures with these names will stop working. See exercise 5.49 for ideas on how to avoid this problem.
5.5.5   An Example of Compiled Code