\input 6001mac

\begin{document}
\addtolength{\textheight}{0.5cm}

\psetheader{Spring Semester, 1996}{Anatomy of Compiled Code}

Consider the following compiled code:

\addtolength{\linewidth}{1in}
\begin{lisp}
{\rm 1.}   (assign val (op make-compiled-procedure) (label entry17) (reg env))
{\rm 2.}   (goto (label after-lambda16))
{\rm 3.}  entry17
{\rm 4.}   (assign env (op compiled-procedure-env) (reg proc)))
{\rm 5.}   (assign env (op extend-binding-environment) (const (x y)) (reg argl) (reg env))
{\rm 6.}   (assign proc (op lookup-variable-value) (const *) (reg env))
{\rm 7.}   (assign val (op lookup-variable-value) (const y) (reg env))
{\rm 8.}   (assign argl (op list) (reg val))
{\rm 9.}   (assign val (op lookup-variable-value) (const x) (reg env))
{\rm 10.}  (assign argl (op cons) (reg val) (reg argl))
{\rm 11.}  (assign val (const 2))
{\rm 12.}  (assign argl (op cons) (reg val) (reg argl))
{\rm 13.}  {\it $<$apply-dispatch$>$}
{\rm 14.} after-lambda16
{\rm 15.}  (perform (op define-variable!) (const f) (reg val) (reg env))
{\rm 16.}  (assign val (const (the-unspecified-value)))
{\rm 17.}  (goto (reg continue))
\end{lisp}
\addtolength{\linewidth}{-1in}

Compilation is like translation: Given some Scheme code, how do we say
the same thing in register machine language?  The compiler is simply a
box that translates from Scheme to register machine language; it
doesn't actually run either code.  The result of the compiler is a
translation of the Scheme code: a register machine program which, {\it
if\/} run, should produce the same behavior as running the original
Scheme program.  

Compiled Scheme code can be read line by line, but this is {\it
extremely\/} difficult.  It is much easier to group register machine
code and understand the entire program as a sequence of code blocks,
each of which can be understood more easily.

The goal of an evaluation is to get some appropriate value into the
{\tt val} register.  Much of the register machine code you will see is
simply trying to generate that ``appropriate'' value.

\bigskip
\begin{lisp}
{\rm 1.}  (assign val (op make-compiled-procedure) (label entry17) (reg env))
\end{lisp}

This line should make you think {\tt lambda}.  It is a
register-machine command to create the {\it procedure object\/}
containing the wrapped-up code ({\tt entry17}) and the environment
({\tt env}).  The machine then jumps to {\tt after-lambda16} to
bind the name of the procedure to the procedure object in {\tt val}.

Together with line {\rm 1}, the compiler needs to generate the
translation of the lambda's body.  This is because the body can't just
be stored as Scheme code---if it were, then when some register machine
tried to apply the lambda, it would have to run Scheme code.  So the
compiler has to translate the lambda body, too.  For example, the
compilation for {\tt (lambda (x y) (* 2 x y))} {\it generates\/} code for
{\tt (* 2 x y)}, but executing the resulting register machine code for
{\tt (lambda (x y) (* 2 x y))} does {\it not\/} execute the code for {\tt
(* 2 x y)}.

Again, when we see a line like 1, we should write {\tt lambda}.  To find
out {\tt lambda} {\it of what\/}, look at the code at the {\tt entry}.

\addtolength{\linewidth}{1in}
\begin{lisp}
{\rm 3.} entry17
{\rm 4.}  (assign env (op compiled-procedure-env) (reg proc))
{\rm 5.}  (assign env (op extend-binding-environment) (const (x y)) (reg argl) (reg env))
\end{lisp}
\addtolength{\linewidth}{-1in}

This code gets executed when, and only when, the procedure object is
{\it applied\/}.  That is, not when evaluating {\tt (lambda (x y) (* 2
x y))}, but when applying {\tt (lambda (x y) (* 2 x y))} to something (say,
when evaluating {\tt ((lambda (x y) (* 2 x y)) 2 3)}, which yields {\tt 12}).
The {\tt entry17} code is called by someone else once it is 
discovered that the procedure object to be applied (the value in the
{\tt val} register returned in {\tt after-lambda16}) 
is a compiled procedure.  
An invariant that is true when we enter {\tt entry17} is that
the procedure object (the value returned by {\tt (op make-compiled-procedure)
$\langle{\sl entry}\rangle$ $\langle{\sl env}\rangle$}) is in {\tt
proc}, and the list of already-evaluated arguments to the procedure are
in {\tt argl}.

Lines 4 and 5 extend the Scheme procedure's environment by building a
new frame in which the procedure's formal parameters are bound to the
arguments.  They always occur together; the first line is always {\it
identical\/} to line 4; the second is identical to 5 {\it except\/}
that the list of formal parameters varies from one procedure to the
next.  The formal parameters to the {\tt lambda} can be read off the
{\tt extend-binding-environment} command on line 5.  In this case, the
formal parameters are {\tt x} and {\tt y}.

The remainder of this code block (in this case, up to and including
line 13) constitutes the compilation of the body of the procedure.
Since this can be arbitrary Scheme code, its compilation can look like
the compilation of any legitimate Scheme code.  In this example, we
simply insert the following code (lines 13.1 to 13.7) to dispatch
to the correct apply handler for the procedure {\tt *}.  

\begin{lisp}
{\rm 13.1}  (test (op primitive-procedure?) (reg proc))
{\rm 13.2}  (branch (label prim-branch11))
{\rm 13.3}  (assign val (op compiled-procedure-entry) (reg proc))
{\rm 13.4}  (goto (reg val))
{\rm 13.5} prim-branch11
{\rm 13.6}  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
{\rm 13.7}  (goto (reg continue))
\end{lisp}

Note that we have not preserved the state of any
registers before this call.  In general, we would want to {\tt save}
needed registers before the call and {\tt restore} them after the call
returns, if those registers are needed for further computation.

One thing that makes compilation easier than interpretation is that we
don't have to handle arbitrary code.  At any time, you're only
compiling one specific piece of Scheme code.  Compiler optimization is
the art of taking advantage of that knowledge.

The numbers after compiler-generated labels are meaningless except for
identification purposes.  They may provide hints, or they may be
misleading!  The compiler has to generate many distinct labels; it
uses numbers to ensure that no two labels have the same name.

\end{document}
