\documentstyle [11pt,mysecs,course]{article}
\input local
\problemset 2
\date{April 15, 1993}
\due{April 22, 1993}
\title{The Stack Machine}

\begin{document}
\maketitle

\problem
Adapt the stack machine given in class to use an ``unframed stack''
representation, which would be given by the following grammar:

\ttnoi
;;; action ::= ()       ; empty list represents halt
;;;        |   (incr-opcode . action)
;;;        |   (read-opcode . action)
;;;        |   (push-opcode value . action)
;;;        |   (add-opcode . action)
;;;        |   (zero?-opcode action . action)
\endtt%
This dotted-pair notation is discussed on pages 15--16 of {\it EOPL\/}.  In
this representation, a typical action would look like:

\ttnoi
(read-opcode read-opcode add-opcode)
\endtt%
You can modify the files found in {\tt\libdir/machine*.s}

\problem
Stack machines are ideally suited for executing expressions in so-called
``reverse Polish'' (or postfix) notation, in which one writes
$$
e_1 \ e_2 \term{+}
$$
instead of the infix notation
$$e_1 + e_2$$
or the prefix notation
$$
\lparen \term{+}\ e_1 \ e_2 \rparen
$$

Write  a program which takes a list of the following form:
$$
\begin{array}{r@{{}}l}
\nt{exp}&::=\nt{number} \\
&::=\lparen \term{+}\ \nt{exp}\ \nt{exp} \rparen\\
\end{array}
$$
and translates it into postfix code suitable for execution on your stack
machine.  Test your translator by executing its output on your stack machine.
You can use whichever of the machine representations you prefer.  For example,
if you used the unframed-stack representation from the preceding problem, your
program might translate {\tt {(+ (* 3 4) 5)}} to something like

\ttnoi 
(const-opcode 3 const-opcode 4 mult-opcode const-opcode 5 add-opcode)
\endtt

Add enough opcodes to the stack machine to make your translation
usable for toy problems like this.

\problem (Extra credit) Extend your prefix-to-postfix translator to include
loops.  For example, you should be able to write a loop that does
multiplication by repeated additions.  This is an exercise in design
as well as programming.

\end{document}
