% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Friday, April 23}

{\Large\bf 1. Register Machines}

A register machine consists of (1) a finite set of {\bf registers},
(2) a fixed set of {\bf operators}, (3) a {\bf controller} (set of
instructions) and (4) a {\bf stack}.  We can represent register
machines using {\bf Data Path} diagrams and {\bf Controller} diagrams
or in a {\bf language} that can be simulated in scheme.

% \vspace{0.06in}


{\Large\bf 2. Register Machine Diagrams}

Early in the semester, we saw some Scheme code to calculate square
root using Newton's method:

\beginlisp
(define (sqrt x) 
  (define (good-enough? ...) ...)
  (define (improve guess) (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1))
\endlisp

Unfortunately, Radio Shack$^{\rm TM}$ was out of square root chips, so we
need to implement square root ourselves.  Luckily they did have an
{\tt improve} chip and a {\tt good-enough?} chip.  Draw the data paths
and control diagram for a square root machine.

\begin{tabular}{p{4in}p{2in}} 
\ANSWERIS{\psfig{figure=r22-1.ps,height=1.8in}}{\vspace{1.8in}}
&
\ANSWERIS{\psfig{figure=r22-2.ps,height=1.8in}}{\vspace{1.8in}}
\end{tabular}

\vspace{-0.2in}

When we connect it all up, we saw that the {\tt improve} chip is
broken, and Radio Shack doesn't have any others.  However, they did
have an {\tt average} chip.  Redraw the data paths and control diagram
{\bf as necessary} to replace the {\tt improve} chip.  Then, convert
the diagrams into a register machine.

\begin{tabular}{p{4in}p{2in}}
\beginlisp
(registers \ANSWER{x guess t})
(operations \ANSWER{/ average good-enough?})
(controller
\ANSWER{
    (assign g (const 1))
  loop 
    (test (op good-enough?) (reg guess) (reg x))
    (branch (label done)) 
    (assign t (op /) (reg guess) (reg x))
    (assign g (op average) (reg t) (reg guess))
    (goto (label loop))
}
  done)
\endlisp
&
\vspace{-0.1in}
\ANSWERIS{\psfig{figure=r22-3.ps,height=1.8in}}{\vspace{1.8in}}
\end{tabular}

\newpage

{\Large\bf 3. Hand-Crafted Register Machines}

What does the following register machine compute if we assume its
input is in register {\tt x} and its output is in register {\tt y}.
In other words, $y = f(x)$.  What's {\tt f}?  
\ANSWER{$f(x) = 3x^2 + 7x + 5$} 

\beginlisp
(registers x y t \ANSWER{k sum})
(operations * + \ANSWER{- =})
(controller
\ANSWER{
    (assign sum (const 0))
  loop
    (test (op =) (reg k) (const 0))
    (branch (label done))
    (assign x (reg k))
}
    (assign y (const 5))
    (assign t (op *) (reg x) (const 7))
    (assign y (op +) (reg t) (reg y))
    (assign t (op *) (reg x) (reg x))
    (assign t (op *) (reg t) (const 3))
    (assign y (op +) (reg t) (reg y))
\ANSWER{
    (assign k (op -) (reg k) (const 1))
    (assign sum (op +) (reg sum) (reg y))
    (goto (label loop))
  done
}
)
\endlisp

Modify the above code so that it computes $y = g(k) = f(1) + f(2) +
\ldots + f(k)$, where {\tt k} is an additional input register.

Below is the code to compute the same $f(x)$ as defined above.  Given
that code, write the code to compute $f(a) / f(b)$, where {\tt a} and
{\tt b} are two input registers.  You may use a {\tt continue}
register and a stack.  (Don't duplicate the code to compute $f(x)$)

\beginlisp
(registers x y t \ANSWER{a b continue})
(operations * + \ANSWER{/})
(controller
\ANSWER{
    (assign x (reg a))
    (assign continue (label f-of-b))
    (goto (label f-of-x))
  f-of-b
    (save y)
    (assign x (reg b)) 
    (assign continue (label divide-em))
    (goto (label f-of-x))
}
\null  
  ; This is the old f(x)
  ; Contract:  input in x, output in y, 
  ;            when done, will jump to reg continue
  f-of-x
    (assign y (const 5))
    (assign t (op *) (reg x) (const 7))
    (assign y (op +) (reg t) (reg y))
    (assign t (op *) (reg x) (reg x))
    (assign t (op *) (reg t) (const 3))
    (assign y (op +) (reg t) (reg y))
    (goto (reg continue))
\null  
\ANSWER{
  divide-em
    (restore t)    ; f(a)
    (assign y (op /) (reg t) (reg y))
}
)
\endlisp



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



\end{document}
