afl-material: comparison handouts/ho07.tex

equal deleted inserted replaced

-:412556272333
+:9ce78065f68d
 \usepackage{../grammar}
 \usepackage{../graphics}
 \begin{document}
+\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019}
 \section*{Handout 7 (Compilation)}
-The purpose of a compiler is to transform a program, a human
+The purpose of a compiler is to transform a program a human can read and
-can read and write, into code the machine can run as fast as
+write into code the machine can run as fast as possible. The fastest
-possible. The fastest code would be machine code the CPU can
+code would be machine code the CPU can run directly, but it is often
-run directly, but it is often enough to improve the speed of a
+good enough for improving the speed of a program to just target a
-program by just targeting a virtual machine. This produces not
+virtual machine. This produces not the fastest possible code, but code
-the fastest possible code, but code that is fast enough and
+that is pretty enough. This way of producing code has the advantage that
-has the advantage that the virtual machine takes care of
+the virtual machine takes care of things a compiler would normally need
-things a compiler would normally need to take care of (like
+to take care of (like explicit memory management). An interesting answer
-explicit memory management). Why study compilers? John Regher
+for why studying compilers is given by John Regher in his compiler
-gives this answer in his compiler blog:\footnote{\url{http://blog.regehr.org/archives/1419}}
+blog:\footnote{\url{http://blog.regehr.org/archives/1419}}
 \begin{quote}\it{}``We can start off with a couple of observations
 about the role of compilers. First, hardware is getting weirder
 rather than getting clocked faster: almost all processors are
 multicores and it looks like there is increasing asymmetry in
 employment act for solid compiler hackers.''
 \end{quote}
 As a first example in this module we will implement a compiler for the
 very simple While-language. It will generate code for the Java Virtual
-Machine (JVM). This is a stack-based virtual machine, a fact which
+Machine (JVM). This is a stack-based virtual machine, a fact which will
-will make it easy to generate code for arithmetic expressions. For
+make it easy to generate code for arithmetic expressions. For example
-example for generating code for the expression $1 + 2$ we need to
+when compiling $1 + 2$ we need to generate the following three
-generate the following three instructions
+instructions
-\begin{lstlisting}[numbers=none]
+\begin{lstlisting}[language=JVMIS,numbers=none]
 ldc 1
 ldc 2
 iadd
 \end{lstlisting}
 \noindent The first instruction loads the constant $1$ onto
-the stack, the next one $2$, the third instruction adds both
+the stack, the next one loads $2$, the third instruction adds both
 numbers together replacing the top two elements of the stack
 with the result $3$. For simplicity, we will throughout
 consider only integer numbers and results. Therefore we can
 use the JVM instructions \code{iadd}, \code{isub},
 \code{imul}, \code{idiv} and so on. The \code{i} stands for
 | \meta{Num}\\
 \end{plstx}
 \noindent where \meta{Id} stands for variables and \meta{Num}
-for numbers. For the moment let us omit variables from
+for numbers. For the moment let us omit variables from arithmetic
-arithmetic expressions. Our parser will take this grammar and
+expressions. Our parser will take this grammar and given an input
-given an input produce abstract syntax trees. For example for
+produce abstract syntax trees. For example we will obtain for the
-the expression $1 + ((2 * 3) + (4 - 3))$ it will produce the
+expression $1 + ((2 * 3) + (4 - 3))$ the following tree.
-following tree.
 \begin{center}
 \begin{tikzpicture}
 \Tree [.$+$ [.$1$ ] [.$+$ [.$*$ $2$ $3$ ] [.$-$ $4$ $3$ ]]]
 \end{tikzpicture}
 \end{center}
-\noindent To generate code for this expression, we need to
+\noindent To generate JVM code for this expression, we need to
 traverse this tree in post-order fashion and emit code for
 each node---this traversal in post-order fashion will produce
 code for a stack-machine (what the JVM is). Doing so for the
 tree above generates the instructions
-\begin{lstlisting}[numbers=none]
+\begin{lstlisting}[language=JVMIS,numbers=none]
 ldc 1
 ldc 2
 ldc 3
 imul
 ldc 4
 isub
 iadd
 iadd
 \end{lstlisting}
-\noindent If we ``run'' these instructions, the result $8$
+\noindent If we ``run'' these instructions, the result $8$ will be on
-will be on top of the stack (I leave this to you to verify;
+top of the stack (I leave this to you to verify; the meaning of each
-the meaning of each instruction should be clear). The result
+instruction should be clear). The result being on the top of the stack
-being on the top of the stack will be a convention we always
+will be a convention we always observe in our compiler, that is the
-observe in our compiler, that is the results of arithmetic
+results of arithmetic expressions will always be on top of the stack.
-expressions will always be on top of the stack. Note, that a
+Note, that a different bracketing of the expression, for example $(1 +
-different bracketing of the expression, for example $(1 + (2 *
+(2 * 3)) + (4 - 3)$, produces a different abstract syntax tree and thus
-3)) + (4 - 3)$, produces a different abstract syntax tree and
+also a different list of instructions. Generating code in this
-thus potentially also a different list of instructions.
+post-order-traversal fashion is rather easy to implement: it can be done
-Generating code in this fashion is rather easy to implement:
+with the following recursive \textit{compile}-function, which takes the
-it can be done with the following recursive
+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$ &
 variables. We will represent them as \emph{local variables} in
 the JVM. Essentially, local variables are an array or pointers
 to memory cells, containing in our case only integers. Looking
 up a variable can be done with the instruction
-\begin{lstlisting}[mathescape,numbers=none]
+\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
 iload $index$
 \end{lstlisting}
 \noindent
 which places the content of the local variable $index$ onto
 the stack. Storing the top of the stack into a local variable
 can be done by the instruction
-\begin{lstlisting}[mathescape,numbers=none]
+\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
 istore $index$
 \end{lstlisting}
 \noindent Note that this also pops off the top of the stack.
 One problem we have to overcome, however, is that local
 \begin{tabular}{lcl}
 $\textit{compile}(\pcode{skip}, E)$ & $\dn$ & $([], E)$\\
 \end{tabular}
 \end{center}
-\noindent $[]$ is the empty list of instructions. Note that
+\noindent whereby $[]$ is the empty list of instructions. Note that
 the \textit{compile}-function for statements returns a pair, a
 list of instructions (in this case the empty list) and an
 environment for variables. The reason for the environment is
 that assignments in the While-language might change the
 environment---clearly if a variable is used for the first
 the environment and assign $x$ with the largest index in $E$
 plus one (that is $E' = E(x \mapsto largest\_index + 1)$).
 That means for the assignment $x := x + 1$ we generate the
 following code
-\begin{lstlisting}[mathescape,numbers=none]
+\begin{lstlisting}[language=JVMIS,mathescape,numbers=none]
 iload $n_x$
 ldc 1
 iadd
 istore $n_x$
 \end{lstlisting}
 \noindent
-where $n_x$ is the index for the variable $x$.
+where $n_x$ is the index for the variable $x$. The code for
+looking-up the index for the variable is as follow:
-More complicated is the code for \pcode{if}-statements, say
+\begin{center}
+\begin{tabular}{lcl}
+$index \;=\; \textit{if}\;(E(x).\textit{isDefind})\;\textit{then}\;E(x)\;\textit{else}\;|E|$
+\end{tabular}
+\end{center}
+\noindent
+In case the environment $E$ contains an index for $x$, we return it.
+Otherwise we ``create'' a new index by returning the size $|E|$ of the
+environment (that will be an index that is guaranteed to be not used
+yet).
+More complicated is the generation of code for \pcode{if}-statements, say
 \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_{1/2}$
+\noindent where $b$ is a boolean expression and the $cs_{1/2}$ are the
-are the statements for each \pcode{if}-branch. Lets assume
+statements for each of the \pcode{if}-branches. Lets assume we already
-we already generated code for $b$ and $cs_{1/2}$. Then in the
+generated code for $b$ and $cs_{1/2}$. Then in the true-case the
-true-case the control-flow of the program needs to be
+control-flow of the program needs to be
 \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},
 \end{lstlisting}
 \noindent
 The generated code is as follows:
-\begin{lstlisting}[mathescape,language={}]
+\begin{lstlisting}[language=JVMIS,mathescape,language={}]
 ldc 1
 ldc 1
 if_icmpne L_ifelse $\quad\tikz[remember picture] \node (C) {\mbox{}};$
 ldc 2
 istore 0
 while x <= 10 do x := x + 1
 \end{lstlisting}
 \noindent yielding the following code
-\begin{lstlisting}[mathescape,language={}]
+\begin{lstlisting}[language=JVMIS,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

changeset 668	9ce78065f68d
parent 601	208b0f67a3d0
child 690	8d57433c7b5e