# HG changeset patch # User Christian Urban # Date 1447771503 0 # Node ID a052a83f562e122af43455b9842ab7ac90ee47d6 # Parent af65ffff9cdd6f575e0dc8d68c6b81ef792eeb49 update diff -r af65ffff9cdd -r a052a83f562e handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r af65ffff9cdd -r a052a83f562e handouts/ho07.tex --- a/handouts/ho07.tex Tue Nov 17 13:31:19 2015 +0000 +++ b/handouts/ho07.tex Tue Nov 17 14:45:03 2015 +0000 @@ -398,7 +398,7 @@ \begin{lstlisting}[mathescape,language={}] ldc 1 - ldc 2 + ldc 1 if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$ ldc 2 istore 0 @@ -414,23 +414,23 @@ \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 +\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; +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. +environment $E$ is threaded through the recursive 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 needs to +be returned as part of the answer. 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 +the condition is true and we need to do another iteration, +and the control-flow needs to be as follows \begin{center} \begin{tikzpicture}[node distance=2mm and 4mm, @@ -452,7 +452,7 @@ \end{tikzpicture} \end{center} -\noindent While if the condition is \emph{not} true we +\noindent Whereas if the condition is \emph{not} true, we need to jump out of the loop, which gives the following control flow. @@ -478,7 +478,7 @@ \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}$). +end of the loop (label $L_{wend}$ below). \begin{center} \begin{tabular}{lcl} @@ -489,18 +489,47 @@ \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{(}@\; \text{goto}\;L_{wbegin}$}\\ \multicolumn{3}{l}{$\qquad\phantom{(}@\;L_{wend}:, E')$}\\ \end{tabular} \end{center} +\noindent I let you go through how this clause works. As an example +you can consider the while-loop + +\begin{lstlisting}[mathescape,numbers=none,language={}] +while x <= 10 do x := x + 1 +\end{lstlisting} + +\noindent yielding the following code + +\begin{lstlisting}[mathescape,language={}] +L_wbegin: $\quad\tikz[remember picture] \node[] (LB) {\mbox{}};$ + iload 0 + ldc 10 + if_icmpgt L_wend $\quad\tikz[remember picture] \node (LC) {\mbox{}};$ + iload 0 + ldc 1 + iadd + istore 0 + goto L_wbegin $\quad\tikz[remember picture] \node (LA) {\mbox{}};$ +L_wend: $\quad\tikz[remember picture] \node[] (LD) {\mbox{}};$ +\end{lstlisting} + +\begin{tikzpicture}[remember picture,overlay] \draw[->,very thick] (LA) edge [->,to path={-- ++(10mm,0mm) + -- ++(0mm,17.3mm) |- (\tikztotarget)},line width=1mm] (LB.east); + \draw[->,very thick] (LC) edge [->,to path={-- ++(10mm,0mm) + -- ++(0mm,-17.3mm) |- (\tikztotarget)},line width=1mm] (LD.east); \end{tikzpicture} + + Next we need to consider the statement \pcode{write x}, which -can be used to write out the content of a variable. For this +can be used to print 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 argument (which needs to be placed on the -stack). The code is as follows. +\pcode{write}-command, we use a separate helper-method and +just call this method with an argument (which needs to be +placed onto the stack). The code of the helper-method is as +follows. \begin{lstlisting}[language=JVMIS] @@ -527,12 +556,12 @@ print out onto the stack. In the next line we call the method \pcode{println} (from the class \pcode{java/io/PrintStream}). We want to print out an integer and do not expect anything -back (that is why the type annotation \pcode{(I)V}). The +back (that is why the type annotation is \pcode{(I)V}). The \pcode{return}-instruction in the next line changes the control-flow back to the place from where \pcode{write} was called. This method needs to be part of a header that is -included in any code we generate. The method \pcode{write} can -be invoked with the two instructions +included in any code we generate. The helper-method +\pcode{write} can be invoked with the two instructions \begin{lstlisting}[mathescape,language=JVMIS] iload $E(x)$ @@ -540,9 +569,9 @@ \end{lstlisting} \noindent where we first place the variable to be printed on -the stack and then call \pcode{write}. The \pcode{XXX} need to -be replaced by appropriate class name (this will be explained -shortly). +top of the stack and then call \pcode{write}. The \pcode{XXX} +need to be replaced by an appropriate class name (this will be +explained shortly). \begin{figure}[t] @@ -572,17 +601,19 @@ By generating code for a While-program, we end up with a list of (JVM assembly) instructions. Unfortunately, there is a bit more boilerplate code needed before these instructions can be -run. The code is shown in Figure~\ref{boiler}. This -boilerplate code is very specific to the JVM. Lines 4 to 8 -contains a method for object creation in the JVM and is called -\emph{before} the \pcode{main}-method in Lines 10 to 17. -Interesting are the Lines 11 and 12 where we hardwire that the -stack of our program will never be larger than 200 and that -the maximum number of variables is also 200. This seem -conservative default values that allow is to run some simple -While-programs. In a real compiler, we would of course need to -work harder and find out appropriate values for the stack and -local variables. +run. The complete code is shown in Figure~\ref{boiler}. This +boilerplate code is very specific to the JVM. If we target any +other virtual machine or a machine language, then we would +need to change this code. Lines 4 to 8 in Figure~\ref{boiler} +contain a method for object creation in the JVM; this method +is called \emph{before} the \pcode{main}-method in Lines 10 to +17. Interesting are the Lines 11 and 12 where we hardwire that +the stack of our programs will never be larger than 200 and +that the maximum number of variables is also 200. This seem to +be conservative default values that allow is to run some +simple While-programs. In a real compiler, we would of course +need to work harder and find out appropriate values for the +stack and local variables. To sum up, in Figure~\ref{test} is the complete code generated for the slightly non-sensical program @@ -593,13 +624,16 @@ \end{lstlisting} \noindent Having this code at our disposal, we need the -assembler to translate the generated code into bytecode (a -class file) that can be understood by the JVM. +assembler to translate the generated code into JVM bytecode (a +class file). This bytecode is understood by the JVM and can be +run by just invoking the \pcode{java}-program. \begin{figure}[p] \lstinputlisting{../progs/test-small.j} -\caption{Generated code for a test program.\label{test}} +\caption{Generated code for a test program. This code can be +processed by an Java assembler producing a class-file, which +can be run by the \pcode{java}-program.\label{test}} \end{figure} \end{document}