\documentclass[12pt]{report}

\usepackage{amsmath}
\usepackage{eepic}

\newcommand{\assign}{\mathrel{:=}}

\begin{document}
\begin{center}
        {\bf Com Sci 221 --- Programming Languages}\\
        {\bf Take-Home Midterm Exam, Autumn 2000}\\
        Due Monday, 6 November, 1:30 PM in class\\
        5 problems on pages 2--7
\end{center}

\begin{itemize}
  
\item This is a self-timed exam.  Please limit yourself to 3 working
  hours from the time that you open the paper, until you complete the
  solutions that you hand in. You may take a break up to 30 minutes
  during the exam, but you should neither work on the problems nor
  study the class material during the break.
  
\item You may use the textbook, my class materials, any other
  published material, and notes of your own.

\item There are 5 problems. They cover material in Chapters 1--4 of
  the text, and the class lectures through datatypes. Each numbered
  problem is weighted equally for grading purposes.
  
\item The problem statements are a bit wordy, since I will not be
  nearby to answer questions. The wordiness does \emph{not} not
  indicate subtlety.
  
\item You may use whatever sort of paper you find convenient, but
  please make your answers legible, and write your name on every
  sheet.
  
\item Please deliver your finished exam to me on paper at the
  beginning of class.

\end{itemize}

\newpage

\subsection*{Problem 1: abstract syntax, postfix, evaluation}

Draw the abstract syntax tree and postfix forms for the expressions
%
\begin{enumerate}
%
\item $a+(b*((c+d)*e))$
%
\item $(((a+b)*c)+d)*e$
%
\item $a+((b*(c+d))*e)$
%
\item $a+(b*(c+(d*e)))$
%
\end{enumerate}

The values of $a$, \dots, $e$ are in memory, but our machine can only
do arithmetic operations on registers. Suppose that we are committed
to evaluating all expressions simple-mindedly from left to right. We
can construct machine code to evaluate the expression by following the
left-to-right sequence in the postfix form. Here is the machine code
for expression 1, using $4$ registers:
%
\begin{align*}
%
R_1 & \assign a \\
R_2 & \assign b \\
R_3 & \assign c \\
R_4 & \assign d \\
R_3 & \assign R_3+R_4 \\
R_4 & \assign e \\
R_3 & \assign R_3*R_4 \\
R_2 & \assign R_2*R_3 \\
R_1 & \assign R_1+R_2
%
\end{align*}
%
Every operation is done in an assignment of the form $R_i\assign
R_i\circ R_{i+1}$ ($\circ$ stands for $+$ or $*$). The value of the
whole expression always ends up in $R_1$. We reuse registers as much
as possible while keeping strictly to the left-to-right evaluation
dictated by the postfix expression. Depending on the form of the
abstract syntax tree, an expression with $n\geq 2$ operands may
require anything from $2$ to $n$ registers.

Translate the postfix expressions for 2, 3, and 4 into pure
left-to-right evaluation code in the same way.

Explain very briefly how to determine the number of registers required
for this sort of evaluation from the shape of the abstract syntax
tree. Look for a very simple property of the paths from root to leaf
in the tree.

\pagebreak

\subsection*{Problem 2: context-free grammar}

Recall the context-free grammar for arithmetic expressions that gives
precedence to $*$ and $/$ over $+$ and $-$:
%
\begin{align*}
%
E &  \rightarrow E + T \\
%
E & \rightarrow E - T \\
%
E & \rightarrow T \\
%
T &  \rightarrow T * F \\
%
T & \rightarrow T / F \\
%
T & \rightarrow F \\
%
F & \rightarrow C \\
%
F & \rightarrow V \\
%
F & \rightarrow ( E )
%
\end{align*}
%
Assume that $C$ derives numerical constants and $V$ derives variable
symbols. Modify the grammar to allow a single unary minus sign before
any subexpression. For example, $x+-y$, $x--y$, $-w*z$, $-x+y$,
$-(x-y)$, $-(-x)$, are allowed, but not $x+--y$, nor $x-+y$. A unary
$-$ has the highest precedence. (It should go without saying that your
grammar must be unambiguous, and its parse trees must correspond
sensibly to abstract syntax.)

\pagebreak

\subsection*{Problem 3: structured programs}

Here is a simple program with its abstract syntax tree:

\vfil

\begin{quote}

$\mathord{\mbox{read}}(i)$;\\
\textbf{while} $i>1$ \textbf{do begin}\\
\hspace*{3em}$\mathord{\mbox{print}}(i)$;\\
\hspace*{3em}\textbf{if} $\mathord{\mbox{odd}}(i)$ \textbf{then begin}\\
\hspace*{6em}$i\assign 3*i+1$\\
\hspace*{3em}\textbf{end else begin}\\
\hspace*{6em}$i\assign i/2$\\
\hspace*{3em}\textbf{end}\\
\textbf{end}

\end{quote}

\vfil

\begin{quote}
\setlength{\unitlength}{0.0006in}
%\setlength{\unitlength}{0.00083333in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{
\begin{picture}(9167,4998)(0,-10)
\thicklines
\path(2700,4200)(3150,3900)
\path(3075,3600)(2550,3300)
\path(1425,3600)(1875,3300)
\path(1200,3600)(825,3300)
\put(1275,3675){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}$>$}}}}}
\put(675,3075){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(1875,3075){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}1}}}}}
\path(150,4125)(150,3900)
\put(75,3675){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\path(525,4725)(150,4500)
\path(900,4725)(2475,4500)
\path(3375,3600)(5775,3225)
\path(5625,2850)(3825,2025)
\path(3750,1725)(3750,1425)
\path(5850,2850)(5025,2025)
\path(4800,1650)(4425,1425)
\path(5100,1650)(6150,1425)
\path(6000,1050)(5625,825)
\path(5400,450)(5025,225)
\path(5700,450)(6075,225)
\path(6300,1050)(6675,825)
\path(7800,1725)(7425,1425)
\path(8100,1725)(8475,1425)
\path(8400,1050)(8025,825)
\path(8700,1050)(9075,825)
\path(6075,2850)(7800,2025)
\path(2400,4200)(1350,3900)
\path(2550,2925)(2550,2700)
\put(0,4275){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}read}}}}}
\put(2325,4275){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\bfdefault}{\updefault}while}}}}}
\put(525,4875){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\bfdefault}{\updefault}comp}}}}}
\put(3000,3675){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\bfdefault}{\updefault}comp}}}}}
\put(3600,1800){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}odd}}}}}
\put(3675,1200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(4275,1200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(4800,1800){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}:=}}}}}
\put(5475,600){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}*}}}}}
\put(6075,1200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}+}}}}}
\put(6675,600){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}1}}}}}
\put(7875,600){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(9075,600){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}2}}}}}
\put(8475,1200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}/}}}}}
\put(7875,1800){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}:=}}}}}
\put(4875,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}3}}}}}
\put(6075,0){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(7275,1200){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\put(5775,3000){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\bfdefault}{\updefault}if}}}}}
\put(2400,3075){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}print}}}}}
\put(2475,2475){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\itdefault}i}}}}}
\end{picture}
}


\end{quote}

\vfil

  \begin{enumerate}
    
  \item Draw the flowchart for the program. Draw a box around the
    portion of the flowchart that corresponds to each subtree in the
    abstract syntax tree (that is, to the whole \textbf{while} loop,
    the body of the \textbf{while} loop, and the whole
    \textbf{if-then-else} statement---the read, print, and assignment
    commands are already in boxes). How many flowchart edges go into
    each box? How many go out of each box? \emph{(problem continued on the
    next page)}

\pagebreak
    
\item Draw abstract syntax tree and flowchart for the following
  variant of the program above, with boxes around the portions of
  flowchart corresponding to the subtrees of the abstract syntax tree.

\begin{quote}

$\mathord{\mbox{read}}(i)$;\\
\textbf{while} \textbf{true} \textbf{do begin}\\
\hspace*{3em}\textbf{if} $i\leq 1$ \textbf{then break};\\
\hspace*{3em}$\mathord{\mbox{print}}(i)$;\\
\hspace*{3em}\textbf{if} $\mathord{\mbox{odd}}(i)$ \textbf{then begin}\\
\hspace*{6em}$i\assign 3*i+1$\\
\hspace*{3em}\textbf{end else begin}\\
\hspace*{6em}$i\assign i/2$\\
\hspace*{3em}\textbf{end}\\
\textbf{end}

\end{quote}

\item Explain very briefly (2--5 sentences should do it) the reason
  that pure structured programming does not allow \textbf{goto}s nor
  \textbf{break}s, in terms of the structural difference between the
  two examples above.

  \end{enumerate}

\pagebreak

\subsection*{Problem 4: reasoning with invariants}

Consider the usual iterative program fragment to reverse a list $s_0$:

\begin{quote}

$s\assign s_0$;\\
$r\assign \mathord{\mbox{\textit{empty}}}$;\\
{\bf while} $s\neq\mathord{\mbox{\textit{empty}}}$ {\bf do begin}\\
\hspace*{3em}$r$ := $\mathord{\mbox{\textit{cons}}}(\mathord{\mbox{\textit{head}}}(s),r)$;\\
\hspace*{3em}$s$ := $\mathord{\mbox{\textit{tail}}}(s)$\\
{\bf end}

\end{quote}
%
\textit{cons} adds a new first element to a list, \textit{head}
returns the first element of a list, and \textit{tail} returns all but
the first element of a list.

Give appropriate precondition, postcondition, and loop invariant that
could be used to show that the program fragment is correct (but don't
do the proof). Use the mathematical primitives $p^R$ (reversal of $p$)
and $p\mathrel{.}q$ ($p$ concatenated with $q$---equivalently $q$
appended to the end of $p$) to express your assertions. The invariant
is one very simple equation using the reversal and concatenation
operations.

\pagebreak

\subsection*{Problem 5: datatypes}

In \emph{C} the following two assignments are precisely equivalent:
%
\begin{quote}
%
$*C[i]=(*B[j]).first$\\[3ex]
$*C[i]=B[j]\mathord{\text{\texttt{->}}}first$
%
\end{quote}
%
I list both of them since some of you may be more familiar with one
form rather than the other. Describe the execution of the assignment
above briefly but precisely, mentioning every l value and every r
value involved, and every way in which an l value is treated as an r
value or vice versa. You don't need to give the formula for
calculating addresses of array components---merely mention that such a
calculation must be done. Here are the first 3 steps to get you
started. I'll abbreviate `l value of \dots' by `$l(\dots)$' and `r
value of \dots' by `$r(\dots)$'.
%
\begin{enumerate}
%
\item dereference $l(j)$ to $r(j)$
%
\item calculate $l(B[j])$ from $l(B)$ and $r(j)$
%
\item dereference $l(B[j])$ to $r(B[j])$
%
\item \dots
%
\end{enumerate}
%
There are 11 steps total (including the 3 that I wrote above). If you
follow the second version of the assignment, keep in mind that the
`\texttt{->}' operator corresponds to a combination of a `$.$' and a
`$*$'.

\end{document}