diff -r d6af4b1239de -r b018234c9126 handouts/ho07.tex --- a/handouts/ho07.tex Tue Nov 17 01:58:50 2015 +0000 +++ b/handouts/ho07.tex Tue Nov 17 04:02:08 2015 +0000 @@ -359,19 +359,153 @@ \begin{center} \begin{tabular}{lcl} $\textit{compile}(\pcode{if}\;b\;\pcode{then}\; cs_1\;\pcode{else}\; cs_2, E)$ & $\dn$\\ -\multicolumn{3}{l}{$\qquad l_\textit{ifelse}\;$ (fresh label)}\\ -\multicolumn{3}{l}{$\qquad l_\textit{ifend}\;$ (fresh label)}\\ +\multicolumn{3}{l}{$\qquad L_\textit{ifelse}\;$ (fresh label)}\\ +\multicolumn{3}{l}{$\qquad L_\textit{ifend}\;$ (fresh label)}\\ \multicolumn{3}{l}{$\qquad (is_1, E') = \textit{compile}(cs_1, E)$}\\ \multicolumn{3}{l}{$\qquad (is_2, E'') = \textit{compile}(cs_2, E')$}\\ -\multicolumn{3}{l}{$\qquad(\textit{compile}(b, E, l_\textit{ifelse})$}\\ +\multicolumn{3}{l}{$\qquad(\textit{compile}(b, E, L_\textit{ifelse})$}\\ \multicolumn{3}{l}{$\qquad\phantom{(}@\;is_1$}\\ -\multicolumn{3}{l}{$\qquad\phantom{(}@\; \pcode{goto}\;l_\textit{ifend}$}\\ -\multicolumn{3}{l}{$\qquad\phantom{(}@\;l_\textit{ifelse}:$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\; \pcode{goto}\;L_\textit{ifend}$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifelse}:$}\\ \multicolumn{3}{l}{$\qquad\phantom{(}@\;is_2$}\\ -\multicolumn{3}{l}{$\qquad\phantom{(}@\;l_\textit{ifend}:, E'')$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_\textit{ifend}:, E'')$}\\ \end{tabular} \end{center} +\noindent In the first two lines we generate two fresh labels +for the jump addresses (just before the else-branch and just +after). In the next two lines we generate the instructions for +the two branches, $is_1$ and $is_2$. The final code will +be first the code for $b$ (including the label +just-before-the-else-branch), then the \pcode{goto} for after +the else-branch, the label $L_\textit{ifesle}$, followed by +the instructions for the else-branch, followed by the +after-the-else-branch label. Consider for example the +if-statement: + +\begin{lstlisting}[mathescape,numbers=none,language={}] +if 1 = 1 then x := 2 else y := 3 +\end{lstlisting} + +\noindent +The generated code is as follows: + +\begin{lstlisting}[mathescape,language={}] + ldc 1 + ldc 2 + if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$ + ldc 2 + istore 0 + goto L_ifend $\quad\tikz[remember picture] \node (A) {\mbox{}};$ +L_ifelse: $\quad\tikz[remember picture] \node[] (D) {\mbox{}};$ + ldc 3 + istore 1 +L_ifend: $\quad\tikz[remember picture] \node[] (B) {\mbox{}};$ +\end{lstlisting} + +\begin{tikzpicture}[remember picture,overlay] \draw[->,very thick] (A) edge [->,to path={-- ++(10mm,0mm) + -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (B.east); + \draw[->,very thick] (C) edge [->,to path={-- ++(10mm,0mm) + -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (D.east); \end{tikzpicture} + +\noindent The first three lines correspond to the the boolean +expression $1 = 1$. The jump for when this boolean expression +is false is in Line~3. Lines 4-6 corresponds to the if-branch; +the else-branch is in Lines 8 and 9. Note carefully how the +environment $E$ is threaded through the calls of +\textit{compile}. The function receives an environment $E$, +but it might extend it when compiling the if-branch, yielding +$E'$. This happens for example in the if-statement above +whenever the variable \code{x} has not been used before. +Similarly with the environment $E''$ for the second call +to \textit{compile}. $E''$ is also the environment that need +to be returned. + +The compilation of the while-loops, say +\pcode{while} $b$ \pcode{do} $cs$, is very similar. In case +the condition is true and we need to do another iteration, the +control-flow needs to be as follows + +\begin{center} +\begin{tikzpicture}[node distance=2mm and 4mm, + block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, + point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, + skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] +\node (A0) [point, left=of A1] {}; +\node (A1) [point] {}; +\node (b) [block, right=of A1] {code of $b$}; +\node (A2) [point, right=of b] {}; +\node (cs1) [block, right=of A2] {code of $cs$}; +\node (A3) [point, right=of cs1] {}; +\node (A4) [point, right=of A3] {}; + +\draw (A0) edge [->, black, line width=1mm] (b); +\draw (b) edge [->, black, line width=1mm] (cs1); +\draw (cs1) edge [->, black, line width=1mm] (A3); +\draw (A3) edge [->,skip loop] (A1); +\end{tikzpicture} +\end{center} + +\noindent While if the condition is \emph{not} true we +need to jump out of the loop, which gives the following +control flow. + +\begin{center} +\begin{tikzpicture}[node distance=2mm and 4mm, + block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, + point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, + skip loop/.style={black, line width=1mm, to path={-- ++(0,-10mm) -| (\tikztotarget)}}] +\node (A0) [point, left=of A1] {}; +\node (A1) [point] {}; +\node (b) [block, right=of A1] {code of $b$}; +\node (A2) [point, right=of b] {}; +\node (cs1) [block, right=of A2] {code of $cs$}; +\node (A3) [point, right=of cs1] {}; +\node (A4) [point, right=of A3] {}; + +\draw (A0) edge [->, black, line width=1mm] (b); +\draw (b) edge [->, black, line width=1mm] (A2); +\draw (A2) edge [skip loop] (A3); +\draw (A3) edge [->, black, line width=1mm] (A4); +\end{tikzpicture} +\end{center} + +\noindent Again we can use the \textit{compile}-function for +boolean expressions to insert the appropriate jump to the +end of the loop (label $L_{wend}$). + +\begin{center} +\begin{tabular}{lcl} +$\textit{compile}(\pcode{while}\; b\; \pcode{do} \;cs, E)$ & $\dn$\\ +\multicolumn{3}{l}{$\qquad L_{wbegin}\;$ (fresh label)}\\ +\multicolumn{3}{l}{$\qquad L_{wend}\;$ (fresh label)}\\ +\multicolumn{3}{l}{$\qquad (is, E') = \textit{compile}(cs_1, E)$}\\ +\multicolumn{3}{l}{$\qquad(L_{wbegin}:$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\;\textit{compile}(b, E, L_{wend})$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\;is$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\; \text{goto}\;l_{wbegin}$}\\ +\multicolumn{3}{l}{$\qquad\phantom{(}@\;L_{wend}:, E')$}\\ +\end{tabular} +\end{center} + +Next we need to consider the statement \pcode{write x}, which +can be used to write out the content of a variable. For this +we need to use a Java library function. In order to avoid +having to generate a lot of code for each +\pcode{write}-command, we use a separate method and just call +this method with an appropriate stack. + +\begin{lstlisting}[language=JVMIS] +.method public static write(I)V + .limit locals 5 + .limit stack 5 + getstatic java/lang/System/out Ljava/io/PrintStream; + iload 0 + invokevirtual java/io/PrintStream/println(I)V + return +.end method +\end{lstlisting} + \end{document} %%% Local Variables: