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"); 
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 compiledefinition 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 definevariable!) (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 compilelambda, 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 makecompiledprocedure) (label entry2) (reg env)) (goto (label afterlambda1)) entry2 (assign env (op compiledprocedureenv) (reg proc)) (assign env (op extendenvironment) (const (n)) (reg argl) (reg env)) $\langle compilation\ of\ procedure\ body\rangle$ afterlambda1 (perform (op definevariable!) (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 compilelambdabody) 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. 
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 
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 falsebranch4)) truebranch5 $\langle compilation\ of\ true\ branch, target$ val$,\ linkage$ return$\rangle$ falsebranch4 $\langle compilation\ of\ false\ branch, target$ val$,\ linkage$ return$\rangle$ afterif3  $\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 aftercall 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 lookupvariablevalue) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookupvariablevalue) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitiveprocedure?) (reg proc)) (branch (label primitivebranch17)) compiledbranch16 (assign continue (label aftercall15)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch17 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) aftercall15  $\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")), 
Original  JavaScript 
;; construct the procedure and skip over code for the procedure body (assign val (op makecompiledprocedure) (label entry2) (reg env)) (goto (label afterlambda1)) entry2 ; calls to factorial will enter here (assign env (op compiledprocedureenv) (reg proc)) (assign env (op extendenvironment) (const (n)) (reg argl) (reg env)) ;; begin actual procedure body (save continue) (save env) ;; compute (= n 1) (assign proc (op lookupvariablevalue) (const =) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookupvariablevalue) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitiveprocedure?) (reg proc)) (branch (label primitivebranch17)) compiledbranch16 (assign continue (label aftercall15)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch17 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) aftercall15 ; val now contains result of (= n 1) (restore env) (restore continue) (test (op false?) (reg val)) (branch (label falsebranch4)) truebranch5 ; return 1 (assign val (const 1)) (goto (reg continue)) falsebranch4 ;; compute and return $\texttt{(* (factorial ( n 1)) n)}$ (assign proc (op lookupvariablevalue) (const *) (reg env)) (save continue) (save proc) ; save * procedure (assign val (op lookupvariablevalue) (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 lookupvariablevalue) (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 
Original  JavaScript 
;; $\texttt{compute ( n 1)}$, which is the argument for $\texttt{factorial}$ (assign proc (op lookupvariablevalue) (const ) (reg env)) (assign val (const 1)) (assign argl (op list) (reg val)) (assign val (op lookupvariablevalue) (const n) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitiveprocedure?) (reg proc)) (branch label primitivebranch8)) compiledbranch7 (assign continue (label aftercall6)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch8 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) aftercall6 ; val now contains result of $\texttt{( n 1)}$ (assign argl (op list) (reg val)) (restore proc) ; restore factorial ;; apply factorial (test (op primitiveprocedure?) (reg proc)) (branch (label primitivebranch11)) compiledbranch10 (assign continue (label aftercall9)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch11 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) aftercall9 ; 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 primitiveprocedure?) (reg proc)) (branch (label primitivebranch14)) compiledbranch13 ;; note that a compound procedure here is called tailrecursively (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch14 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) (goto (reg continue)) aftercall12 afterif3 afterlambda1 ;; assign the procedure to the variable factorial (perform (op definevariable!) (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 tailrecursively 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)) 
Original  JavaScript 
(define (factorialalt n) (if (= n 1) 1 (* n (factorialalt ( n 1)))))  function factorial_alt(n) { return n === 1 ? 1 : n * factorial_alt(n  1); } 
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); } 
Original  JavaScript 
(assign val (op makecompiledprocedure) label entry16) (reg env)) (goto (label afterlambda15)) entry16 (assign env (op compiledprocedureenv) (reg proc)) (assign env (op extendenvironment) (const (x)) (reg argl) (reg env)) (assign proc (op lookupvariablevalue) (const +) (reg env)) (save continue) (save proc) (save env) (assign proc (op lookupvariablevalue) (const g) (reg env)) (save proc) (assign proc (op lookupvariablevalue) (const +) (reg env)) (assign val (const 2)) (assign argl (op list) (reg val)) (assign val (op lookupvariablevalue) (const x) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (test (op primitiveprocedure?) (reg proc)) (branch (label primitivebranch19)) compiledbranch18 (assign continue (label aftercall17)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch19 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) aftercall17 (assign argl (op list) (reg val)) (restore proc) (test (op primitiveprocedure?) (reg proc)) (branch (label primitivebranch22)) compiledbranch21 (assign continue (label aftercall20)) (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch22 (assign val (op applyprimitiveprocedure) (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")), 
Original  JavaScript 
aftercall20 (assign argl (op list), (reg val)) (restore env) (assign val (op lookupvariablevalue) (const x) (reg env)) (assign argl (op cons) (reg val) (reg argl)) (restore proc) (restore continue) (test (op primitiveprocedure?) (reg proc)) (branch label primitivebranch25)) compiledbranch24 (assign val (op compiledprocedureentry) (reg proc)) (goto (reg val)) primitivebranch25 (assign val (op applyprimitiveprocedure) (reg proc) (reg argl)) (goto (reg continue)) aftercall23 afterlambda15 (perform (op definevariable!) (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)) 
Original  JavaScript 
(assign val (op lookupvariablevalue) (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))) 
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 opencode them. 
Original  JavaScript  
