\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{7}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{11/7/90}

\prob{1: {\em G-machine code familiarity}}

\subprob{A} The immediate ({\bf imm}) addressing mode is used to specify
an immediate, or instruction-stream constant, source operand. {\bf imm}
is actually derived from the postincrement {\bf posti} addressing mode
with an argument of 15, which specifies the program counter. If this
addrssing mode is used as a destination operand things would get
hopelessly muddled since effective address would be the contents of the
program counter, which is pointing at the {\bf imm} argument. Thus, it
would take its source operands and put them where the program counter is
pointing (since that's the effective address). Therefore, the next
``instruction'' to be executed wouldn't make any sense, since it would
have been either partially or wholly written over.

\subprob{B} {\bf gjmp dir(3)} is fine. {\bf gjmp imm4(3)} doesn't work,
since {\bf imm} can't be used as a destination operand (as explained in
A). {\bf gjmp r(3)} won't work, since register 3 isn't the same as main
memory location 3. The PC points to main memory, not to registers. {\bf
gmove1 imm1(3) r(15)} won't work, since addresses are 4 bytes, not just
1. {\bf gmove4 imm4(3) r(15)} is fine. {\bf gmove1 dir(3) pred(15)}
won't work because {\bf dir(3)} is used as a source operand and
therefore the contents, not the address, is moved into the PC (not to
mention the strange things done by {\bf pred} to the contents of the PC
beforehand). 

\subprob{C} In regular S-machine code, we have no explicit way to
manipulate the stack. Therefore, we can't just pop off the top of the
stack and put it somewhere until we're ready to use it. {\bf slta}
allows us to explicitly specify a location in the stack, using the stack
pointer as a reference. Thus, the S-machine code that corresponds to the
given G-machine code looks something like this:

\begin{verbatim}
sc4(1000)                    
sl4                          | i(1000) --> destination
slta(-8)                     | location of old TOS 
sl4                          | value of old TOS; effectively pop()
sc4(23)                      | imm4(23) --> constant
sadd4                        | pop() + 23
ss4                          | <1000> <- pop() + 23
\end{verbatim}

\prob{2: {\em S Machine Extension}}

\begin{verbatim}
hsswap@:    pop@(Op1)
            pop@(Op2)
            push@(Op1)
            push@(Op2)
            rtn()
\end{verbatim}

\mynewpage

\prob{3: {\em S to G Translation}}

\subprob{A}

\begin{verbatim}
FACT-N: gmove4 imm4(0) push()      | set up termination flag
        gmove4 r(1) push()         | get the argument

LOOP:   gmove4 ix(-4,14) r(2)      | put running count <TOS> in register 2
        gsub4 r(2) imm4(1) r(3)    | decrement running count; put in r3
	gmove4 r(3) push()         | put decremented <TOS> on stack
        gtest4 r(3)                | is it zero?
        gjg dir(LOOP)              | no, continue with loop

MULT:   gmul4 pop() pop() push()   | form product of top two values
        gtest4 ix(-8,14)           | is next val zero (i.e. time to stop)?
        gjg dir(MULT)              | no, continue with multiplying

DONE:   gmove4 pop() r(0)          | put result in register 1
        grtn
\end{verbatim}

\subprob{B} The G-machine code only uses 5 fewer instructions than the
S-machine code. However, the G-machine code accesses the main memory
less frquently. This is because G-machine instructions don't depend on
the stack for their arguments or for where to put their results, whereas
S-machine instructions have to pop their arguments off the stack and
push their results onto the stack each time. For those who are used to
the concept of reverse polish notation for functions and who aren't
bothered by having to make sure not to inadvertently destroy needed data
on the stack, the S-machine is fairly easy to deal with. For those who
prefer prefix instead of suffix notation for functions and who like
having some place other than a stack to store intermediate results, the
G-machine is a much better machine to work with. However, the S-machine
is much easier to design since all it has to deal with is the stack. The
G-machine has fancy addressing modes since it has two namespaces to
address. It seems the G-machine would be much tougher to design.

\prob{4: {\em Lexical Scoping}}

\subprob{A}

\begin{verbatim}
13. saa(1,8) sl4     | delta-y
    slla(0) sl4      | x
    saa(1,4) sl4     | delta-x
    sadd4            | x + delta-x
    saa(1,0) sl4     | pointer to f
    scall(8)         | call f with 8 bytes of args
    sadd4            | delta-y + f(x + delta-x)
    srtn4
\end{verbatim}

\mynewpage

\begin{verbatim}
15. slla(0)          | address of g function
    sc4(L1)          | address of plot function
    scall(4)         | plot(g)

16. slaa(4)          | address of delta-x
    sdup4 sl4        | duplicate it and get delta-x
    sc4(0)           | arg of 0          
    slla(0)          | address of g function
    scall(4)         | g(0)
    sadd4            | delta-x + g(0)
    ss4              | delta-x <- delta-x + g(0)
\end{verbatim}

\subprob{B} No, because any arbitrary length of code (or rather, any
arbitrary amount of memory) could intervene between the given variable
and different points in a given lexical level.

\prob{5: {\em G Machine Calling Conventions}}

\subprob{A}
\begin{verbatim}
gmove4 r(14) r(1)            | save the old SP before pushing args
gmove4 imm4(23) push()       | push a=23 onto stack
gmove4 imm4(37) push()       | push b=37 onto stack
gmove4 r(1) push()           | push old SP onto stack
gmove4 r(13) push()          | push old B value (kept in r13) onto stack
gcall dir(f)                 | call f

gmove4 pop() r(13)           | restore old B value
gmove4 pop() posti(14)       | restore old stack pointer + 4 bytes for result
\end{verbatim}

\subprob{B}
\begin{verbatim}
gmove4 r(13) pred(14)        | set B to SP - 4 bytes, i.e. TOS
salloc(+8)                   | allocate space for locals
...                          | actual code of f
gmove4 pop() ir(1)           | old TOS <- result; old SP still in r1
salloc(-8)                   | deallocating the local space
grtn
\end{verbatim}


\end{document}
