afl-material: comparison handouts/ho07.tex

equal deleted inserted replaced

-:bf36664a3196
+:af65ffff9cdd
 \begin{document}
 \section*{Handout 7 (Compilation)}
 The purpose of a compiler is to transform a program, a human
-can write, into code the machine can run as fast as possible.
+can read and write, into code the machine can run as fast as
-The fastest code would be machine code the CPU can run
+possible. The fastest code would be machine code the CPU can
-directly, but it is often enough to improve the speed of a
+run directly, but it is often enough to improve the speed of a
 program by just targeting a virtual machine. This produces not
 the fastest possible code, but code that is fast enough and
-has the advantage that the virtual machine care of things a
+has the advantage that the virtual machine takes care of
-compiler would normally need to take care of (like explicit
+things a compiler would normally need to take care of (like
-memory management).
+explicit memory management).
-As an example we will implement a compiler for the very simple
+As a first example we will implement a compiler for the very
-While-language. We will be generating code for the Java
+simple While-language. It will generate code for the Java
-Virtual Machine. This is a stack-based virtual machine, a fact
+Virtual Machine (JVM). This is a stack-based virtual machine,
-which will make it easy to generate code for arithmetic
+a fact which will make it easy to generate code for arithmetic
 expressions. For example for generating code for the
 expression $1 + 2$ we need to generate the following three
 instructions
 \begin{lstlisting}[numbers=none]
 iadd
 \end{lstlisting}
 \noindent The first instruction loads the constant $1$ onto
 the stack, the next one $2$, the third instruction adds both
-numbers together replacing the top elements of the stack with
+numbers together replacing the top two elements of the stack
-the result $3$. For simplicity, we will throughout consider
+with the result $3$. For simplicity, we will throughout
-only integer numbers and results. Therefore we can use the
+consider only integer numbers and results. Therefore we can
-instructions \code{iadd}, \code{isub}, \code{imul},
+use the JVM instructions \code{iadd}, \code{isub},
-\code{idiv} and so on. The \code{i} stands for integer
+\code{imul}, \code{idiv} and so on. The \code{i} stands for
-instructions in the JVM (alternatives are \code{d} for doubles,
+integer instructions in the JVM (alternatives are \code{d} for
-\code{l} for longs and \code{f} for floats).
+doubles, \code{l} for longs and \code{f} for floats).
 Recall our grammar for arithmetic expressions ($E$ is the
 starting symbol):
 | \meta{Id}
 | \meta{Num}\\
 \end{plstx}
-\noindent where \meta{Id} stands for variables and
+\noindent where \meta{Id} stands for variables and \meta{Num}
-\meta{Num} for numbers. For the moment let us omit variables from
+for numbers. For the moment let us omit variables from
 arithmetic expressions. Our parser will take this grammar and
-produce abstract syntax trees. For
+given an input produce abstract syntax trees. For example for
-example for the expression $1 + ((2 * 3) + (4 - 3))$ it will
+the expression $1 + ((2 * 3) + (4 - 3))$ it will produce the
-produce the following tree.
+following tree.
 \begin{center}
 \begin{tikzpicture}
 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
 \end{tikzpicture}
 expressions will always be on top of the stack. Note, that a
 different bracketing of the expression, for example $(1 + (2 *
 3)) + (4 - 3)$, produces a different abstract syntax tree and
 thus potentially also a different list of instructions.
 Generating code in this fashion is rather easy to implement:
-it can be done with the following \textit{compile}-function,
+it can be done with the following recursive
-which takes the abstract syntax tree as argument:
+\textit{compile}-function, which takes the abstract syntax
+tree as argument:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(n)$ & $\dn$ & $\pcode{ldc}\; n$\\
 $\textit{compile}(a_1 + a_2)$ & $\dn$ &
 index the variable $x$ maps to.
 There is a similar \textit{compile}-function for boolean
 expressions, but it includes a ``trick'' to do with
 \pcode{if}- and \pcode{while}-statements. To explain the issue
-let us explain first the compilation of statements of the
+let us first describe the compilation of statements of the
 While-language. The clause for \pcode{skip} is trivial, since
 we do not have to generate any instruction
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(\pcode{skip}, E)$ & $\dn$ & $([], E)$\\
 \end{tabular}
 \end{center}
-\noindent Note that the \textit{compile}-function for
+\noindent $[]$ is the empty list of instructions. Note that
-statements returns a pair, a list of instructions (in this
+the \textit{compile}-function for statements returns a pair, a
-case the empty list) and an environment for variables. The
+list of instructions (in this case the empty list) and an
-reason for the environment is that assignments in the
+environment for variables. The reason for the environment is
-While-language might change the environment---clearly if a
+that assignments in the While-language might change the
-variable is used for the first time, we need to allocate a new
+environment---clearly if a variable is used for the first
-index and if it has been used before, we need to be able to
+time, we need to allocate a new index and if it has been used
-retrieve the associated index. This is reflected in
+before, we need to be able to retrieve the associated index.
-the clause for compiling assignments:
+This is reflected in the clause for compiling assignments:
 \begin{center}
 \begin{tabular}{lcl}
-$\text{compile}(x := a, E)$ & $\dn$ &
+$\textit{compile}(x := a, E)$ & $\dn$ &
 $(\textit{compile}(a, E) \;@\;\pcode{istore}\;index, E')$
 \end{tabular}
 \end{center}
 \noindent We first generate code for the right-hand side of
 \begin{lstlisting}[mathescape,language={},numbers=none]
 if $b$ then $cs_1$ else $cs_2$
 \end{lstlisting}
-\noindent where $b$ is a boolean expression and the $cs_i$
+\noindent where $b$ is a boolean expression and the $cs_{1/2}$
-are the instructions for each \pcode{if}-branch. Lets assume
+are the statements for each \pcode{if}-branch. Lets assume
 we already generated code for $b$ and $cs_{1/2}$. Then in the
 true-case the control-flow of the program needs to be
 \begin{center}
 \begin{tikzpicture}[node distance=2mm and 4mm,
 if-condition is false) from the end of the code for the
 boolean to the beginning of the instructions $cs_2$. Once we
 are finished with running $cs_2$ we can continue with whatever
 code comes after the if-statement.
-The \pcode{goto} and conditional jumps need addresses to where
+The \pcode{goto} and the conditional jumps need addresses to
-the jump should go. Since we are generating assembly code for
+where the jump should go. Since we are generating assembly
-the JVM, we do not actually have to give addresses, but need
+code for the JVM, we do not actually have to give (numeric)
-to attach labels to our code. These labels specify a target
+addresses, but can just attach (symbolic) labels to our code.
-for a jump. Therefore the labels need to be unique, as
+These labels specify a target for a jump. Therefore the labels
-otherwise it would be ambiguous where a jump should go.
+need to be unique, as otherwise it would be ambiguous where a
-A labels, say \pcode{L}, is attached to code like
+jump should go to. A label, say \pcode{L}, is attached to code
+like
 \begin{lstlisting}[mathescape,numbers=none]
 L:
 $instr_1$
 $instr_2$
 $\vdots$
 \end{lstlisting}
+\noindent where a label is indicated by a colon.
 Recall the ``trick'' with compiling boolean expressions: the
 \textit{compile}-function for boolean expressions takes three
 arguments: an abstract syntax tree, an environment for
 variable indices and also the label, $lab$, to where an conditional
 $\textit{compile}(a_1 = a_2, E, lab)$ & $\dn$\\
 \multicolumn{3}{l}{$\qquad\textit{compile}(a_1, E) \;@\;\textit{compile}(a_2, E)\;@\; \pcode{if_icmpne}\;lab$}
 \end{tabular}
 \end{center}
-\noindent
+\noindent where we are first generating code for the
-We are generating code for the subexpressions $a_1$ and $a_2$.
+subexpressions $a_1$ and $a_2$. This will mean after running
-This will mean after running the corresponding code there will
+the corresponding code there will be two integers on top of
-be two integers on top of the stack. If they are equal, we do
+the stack. If they are equal, we do not have to do anything
-not have to do anything and just continue with the next
+(except for popping them off from the stack) and just continue
-instructions (see control-flow of ifs above). However if they
+with the next instructions (see control-flow of ifs above).
-are \emph{not} equal, then we need to (conditionally) jump to
+However if they are \emph{not} equal, then we need to
-the label $lab$. This can be done with the instruction
+(conditionally) jump to the label $lab$. This can be done with
+the instruction
 \begin{lstlisting}[mathescape,numbers=none]
 if_icmpne $lab$
 \end{lstlisting}
 \noindent Other jump instructions for boolean operators are
 \begin{center}
 \begin{tabular}{l@{\hspace{10mm}}c@{\hspace{10mm}}l}
-$=$ & $\Rightarrow$ & \pcode{if_icmpne}\\
 $\not=$ & $\Rightarrow$ & \pcode{if_icmpeq}\\
 $<$ & $\Rightarrow$ & \pcode{if_icmpge}\\
 $\le$ & $\Rightarrow$ & \pcode{if_icmpgt}\\
 \end{tabular}
 \end{center}
 \noindent and so on. I leave it to you to extend the
 \textit{compile}-function for the other boolean expressions.
 Note that we need to jump whenever the boolean is \emph{not}
-true, which means we have to ``negate'' the jump---equals
+true, which means we have to ``negate'' the jump
-becomes not-equal, less becomes greater-or-equal. If you do
+condition---equals becomes not-equal, less becomes
-not like this design (it can be the source of some nasty,
+greater-or-equal. If you do not like this design (it can be
-hard-to-detect errors), you can also change the layout of the
+the source of some nasty, hard-to-detect errors), you can also
-code and first give the code for the else-branch and then for
+change the layout of the code and first give the code for the
-the if-branch.
+else-branch and then for the if-branch. However in the case
+of while-loops this way of generating code still seems
+the most convenient.
 We are now ready to give the compile function for
-if-statments--remember this function returns for staments a
+if-statments---remember this function returns for staments a
 pair consisting of the code and an environment:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{compile}(\pcode{if}\;b\;\pcode{then}\; cs_1\;\pcode{else}\; cs_2, E)$ & $\dn$\\

changeset 376	af65ffff9cdd
parent 375	bf36664a3196
child 377	a052a83f562e