% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input ./6001mac.tex

{\obeyspaces\gdef {\ }}


\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Wednesday, May 6}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Student Presentations}

{\bf First presentation:}
Please briefly summarize the key points from yesterday's lecture. Do
not worry about details of the compiler, but rather focus on the
relationship between the explicit control evaluator and the compiler.


{\bf Second presentation:}
(Taken from Exercise 5.31 in the book, page 574).  For each of the
following combinations, say which of these save and restore operations
are superfluous and thus could be eliminated by the compiler's
``preserving'' mechanism:

\beginlisp
(f 'x 'y)
((f) 'x 'y)
\endlisp

\vskip .08in

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 2. Compilers}

Here are some important ideas to understand about compilers.

\begin{enumerate}

\item What is a compiler and how does it work?

A compiler takes in a program in one language and produces a program
in another language that does the same thing the original code did.

One (simple but inefficient) way it can work is to just paste together
code from an evaluator for the input language that is written in the
output language.

\item Why are some processes iterative and some recursive?

If all procedures restore all the registers they save before making a
call, it will lead to an iterative process.

If a procedure calls itself while it has saved but not restored some
registers, then it will lead to a recursive process.

\item  How does a compiler ``optimize'' the output program in ways that
an interpreter cannot? 

The interpreter must both figure out what to do and also do it.  This
means the interpreter uses instructions to do the figuring out that
the compiler does before the program runs.

Also, the compiler can analyze the code sequences before combining
them, so it can ``look into the future'' in a way that an interpreter
cannot.  (For example, it can figure out what registers do and don't
need saved.)

\item  Given some compiled code, figure out what the original scheme
expression was.

We'll do an example of this later on.

\end{enumerate}

{\Large\bf 3. Compiling IFs}

Here is the code from the evaluator for dealing with {\tt if}s.  

\beginlisp
ev-if
  (assign unev (reg exp))
  (save unev) 
  (save env) 
  (save continue) 
  (assign continue (label ev-if-decide)) 
  (assign exp (op if-predicate) (reg unev)) 
  (goto (label eval-dispatch))
ev-if-decide
  (restore continue)
  (restore env)
  (restore unev)
  (test (op false?) (reg val))
  (branch (label ev-if-consequent))
ev-if-alternative
  (assign exp (op if-alternative) (reg unev))
  (goto (label eval-dispatch))
ev-if-consequent
  (assign exp (op if-consequent) (reg unev))
  (goto (label eval-dispatch))
\endlisp

A naive compiler would simply collect the used instructions. For
example, compiling {\tt (if a b c)} would yield:

\beginlisp
  (save env)
  (save continue)
  (assign continue (label after-pred28))  
  (assign val (op lookup-variable-value) (const a) (reg env))
  (goto (reg continue))
after-pred28
  (restore continue)
  (restore env)
  (test (op false?) (reg val))
  (branch (label false-branch27))
  (assign val (op lookup-variable-value) (const b) (reg env))
  (goto (reg continue))
false-branch27
  (assign val (op lookup-variable-value) (const c) (reg env))
  (goto (reg continue))
\endlisp

By using stack discipline and targetting, we can create much more
efficient registration machine code.  Basic idea is to keep track of
what registers are needed by an expression and what registers are
changed by an expression, and combine these to decide what stack
manipulations are actually necessary.

Compiling {\tt (if a b c)}: 

\beginlisp
  (assign val (op lookup-variable-value) (const a) (reg env))
  (test (op false?) (reg val))
  (branch (label false-branch25))
true-branch26
  (assign val (op lookup-variable-value) (const b) (reg env))
  (goto (reg continue))
false-branch25
  (assign val (op lookup-variable-value) (const c) (reg env))
  (goto (reg continue))
after-if24
\endlisp

\newpage

{\Large\bf 4. Decompiling Code - Short Examples}

The following code results from the compilation of {\tt (define x 3)}.

\beginlisp
  (assign val (const 3))
  (perform (op define-variable!) (const x) (reg val) (reg env))
  (assign val (const ok))
  (goto (reg continue))
\endlisp

\vspace{0.1in} 

The following code results from the compilation of {\tt (- x 2)}.
For the evaluation of a combination, look for the procedure to be put
into the {\tt proc} register and the {\tt cons}ing up of the argument
list in the {\tt argl} register.  {\bf Remember that the arguments are
evaluated right to left!}

\beginlisp
  (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-branch14))
compiled-branch13
  (assign continue (label after-call12))
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))
primitive-branch14
  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
after-call12
  (goto (reg continue))
\endlisp

\vspace{0.1in} 

The following code results from the compilation of {\tt (if a b c)}.
When you see labels like {\tt true-branch} and {\tt false-branch}, you
should think {\tt if}.

\beginlisp
  (assign val (op lookup-variable-value) (const a) (reg env))
  (test (op false?) (reg val))
  (branch (label false-branch16))
true-branch17
  (assign val (op lookup-variable-value) (const b) (reg env))
  (goto (label after-if15))
false-branch16
  (assign val (op lookup-variable-value) (const c) (reg env))
after-if15
  (goto (reg continue))
\endlisp

\vspace{0.1in} 

The following code results from the compilation of {\tt (lambda (x)
x)}.  Note that the body of the lambda (lines 3-7) are not evaluated.
The label is just saved along with the current environment to make the
procedure object.

\beginlisp
1.   (assign val (op make-compiled-procedure) (label entry19) (reg env))
2.   (goto (label after-lambda18))
3. entry19
4.   (assign env (op compiled-procedure-env) (reg proc))
5.   (assign env (op extend-environment) (const (x)) (reg argl) (reg env))
6.   (assign val (op lookup-variable-value) (const x) (reg env))
7.   (goto (reg continue))
8. after-lambda18
9.   (goto (reg continue))
\endlisp

\newpage

{\Large\bf 5. More Decompiling Code}


Below is a listing of code produced by the compiler used in Problem
Set 12. For each of the following sections of compiled code, determine
the Scheme expression that produced it.

% ANSWER: 
% (define (f a)
%    (if (> a 0)
%        a
%        (- a)))

\beginlisp
 1.    (assign val (op make-compiled-procedure) (label entry2) (reg env))
 2.    (goto (label after-lambda1))
 3.  entry2
 4.    (assign env (op compiled-procedure-env) (reg proc))
 5.    (assign env (op extend-environment) (const (a)) (reg argl) (reg env))
 6.    (save continue)
 7.    (save env)
 8.    (assign proc (op lookup-variable-value) (const >) (reg env))
 9.    (assign val (const 0))
10.    (assign argl (op list) (reg val))
11.    (assign val (op lookup-variable-value) (const a) (reg env))
12.    (assign argl (op cons) (reg val) (reg argl))
13.    (test (op primitive-procedure?) (reg proc))
14.    (branch (label primitive-branch11))
15.  compiled-branch10
16.    (assign continue (label after-call9))
17.    (assign val (op compiled-procedure-entry) (reg proc))
18.    (goto (reg val))
19.  primitive-branch11
20.    (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
21.  after-call9
22.    (restore env)
23.    (restore continue)
24.    (test (op false?) (reg val))
25.    (branch (label false-branch4))
26.  true-branch5
27.    (assign val (op lookup-variable-value) (const a) (reg env))
28.    (goto (reg continue))
29.  false-branch4
30.    (assign proc (op lookup-variable-value) (const -) (reg env))
31.    (assign val (op lookup-variable-value) (const a) (reg env))
32.    (assign argl (op list) (reg val))
33.    (test (op primitive-procedure?) (reg proc))
34.    (branch (label primitive-branch8))
35.  compiled-branch7
36.    (assign val (op compiled-procedure-entry) (reg proc))
37.    (goto (reg val))
38.  primitive-branch8
39.    (assign val (op apply-primitive-procedure) (reg proc) (reg argl))
40.    (goto (reg continue))
41.  after-call6
42.  after-if3
43.  after-lambda1
44.    (perform (op define-variable!) (const f) (reg val) (reg env))
45.    (assign val (const ok)))
46.    (goto (reg continue))
\endlisp

Lines 8--20: 
% (> a 0)

\vspace{0.1in}

Lines 30--40: 
% (- a)

\vspace{0.1in}

Lines 8--40: 
% (if (> a 0)
%     a
%     (- a))

\vspace{0.2in}

Lines 1--46: 
% (define (f a)
%    (if (> a 0)
%        a
%        (- a)))


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}


{\Large\bf 3. Evaluating a Combination}

If we watched the evaluation of the combination {\tt (F X)}, we would
see the following sequence of register operations:

\beginlisp
(assign unev (op cdr) (reg exp))
(assign exp (op car) (reg exp))
(save continue)
(save env)
(save unev)
(assign val (op lookup-var-val) (reg exp) (reg env))
(restore unev)
(restore env)
(assign proc (reg val))
(save proc)
(assign argl (op empty-arglist))
(save argl)
(assign exp (op car) (reg unev))
(assign continue (label ev-appl-accum-last-arg))
(assign val (op lookup-var-val) (reg exp) (reg env))
(restore argl)
(assign argl (op cons) (reg val) (reg argl))
(restore proc)
;; computation proceeds at apply-dispatch
\endlisp

With a compiler, we can build the pieces of the expression directly
into the register operations.  Thus, we do not need to worry about
saving {\tt exp} or {\tt unev}.  We can also ignore the continuations
generated during evaluation of the pieces of the express (thus we
needn't do the initial save of {\tt continue} in the third line
above).  So simply taking advantage of the fact that the form of the
exprssion can be compiled into the flow of the evaluation gives the
following alternative to the above code.

\beginlisp
1.  (save env)
2.  (assign val (op lookup-var-val) (const f) (reg env))
3.  (restore env)
4.  (assign proc (reg val))
5.  (save proc)
6.  (assign argl (op empty-arglist))
7.  (save argl)
8.  (assign val (op lookup-var-val) (const x) (reg env))
9.  (restore argl)
10. (assign argl (op cons) (reg val) (reg argl))
11. (restore proc)
;; computation proceeds at apply-dispatch
\endlisp

With more cleverness, we can note some optimizations:

\begin{itemize}

\item the instruction in line 2 doesn't clobber {\tt env}, so we
needn't save and restore it;

\item line 2 might as well move the result directly to {\tt proc};

\item lines 6, 7, and 9 are unnecessary, since the only thing being
save and restored is the empty list;


\item the argument evaluation doesn't clobber {\tt proc}, so the save
in line 5 and the restore in line 11 are unnecessary. 

\end{itemize}

Thus a smarter compiler would generate the following code:

\beginlisp
(assign proc (op lookup-var-val) (const f) (reg env))
(assign val (op lookup-var-val) (const x) (reg env))
(assign argl (op cons) (reg val) (op empty-arglist))
;; computation proceeds at apply-dispatch
\endlisp

\newpage
