afl-material: comparison handouts/ho09.tex

equal deleted inserted replaced

-:52263ffd17b9
+:681c36b2af27
 \texttt{i32} (the result type is in front of the function name, like in
 C). Each arithmetic operation, for example addition and multiplication,
 are also prefixed with the type they operate on. Obviously these types
 need to match up\ldots{} but since we have in our programs only
 integers, \texttt{i32} everywhere will do. We do not have to generate
-any other types, but obviously this is a limitation in our Fun-language.
+any other types, but obviously this is a limitation in our Fun language.
 There are a few interesting instructions in the LLVM-IR which are quite
-different than in the JVM. Can you remember the kerfuffle we had to go
+different than what we have seen in the JVM. Can you remember the
-through with boolean expressions and negating the condition? In the
+kerfuffle we had to go through with boolean expressions and negating the
-LLVM-IR, branching  if-conditions is implemented differently: there
+condition? In the LLVM-IR, branching  if-conditions is implemented
-is a separate \texttt{br}-instruction as follows:
+differently: there is a separate \texttt{br}-instruction as follows:
 \begin{lstlisting}[language=LLVM]
 br i1 %var, label %if_br, label %else_br
 \end{lstlisting}
 \noindent
 The type \texttt{i1} stands for booleans. If the variable is true, then
 this instruction jumps to the if-branch, which needs an explicit label;
 otherwise to the else-branch, again with its own label. This allows us
-to keep the meaning of the boolean expression as is.  A value of type
+to keep the meaning of the boolean expression as is when compiling if's.
-boolean is generated in the LLVM-IR by the \texttt{icmp}-instruction.
+A value of type boolean is generated in the LLVM-IR by the
-This instruction is for integers (hence the \texttt{i}) and takes the
+\texttt{icmp}-instruction. This instruction is for integers (hence the
-comparison operation as argument. For example
+\texttt{i}) and takes the comparison operation as argument. For example
 \begin{lstlisting}[language=LLVM]
 icmp eq i32  %x, %y     ; for equal
 icmp sle i32 %x, %y     ;   signed less or equal
 icmp slt i32 %x, %y     ;   signed less than
 \noindent
 In some operations, the LLVM-IR distinguishes between signed and
 unsigned representations of integers.
+It is also easy to call another function in LLVM-IR: as can be
+seen from Figure~\ref{lli} we can just call a function with the
+instruction \texttt{call} and can also assign the result to
+a variable. The syntax is as follows
+\begin{lstlisting}[language=LLVM]
+%var = call i32 @foo(...args...)
+\end{lstlisting}
+\noindent
+where the arguments can only be simple variables, not compound
+expressions.
 Conveniently, you can use the program \texttt{lli}, which comes with
 LLVM, to interpret programs written in the LLVM-IR. So you can easily
 check whether the code you produced actually works. To get a running
 program that does something interesting you need to add some boilerplate
-about printing out numbers and a main-function that is the entrypoint
+about printing out numbers and a main-function that is the entry point
 for the program (see Figure~\ref{lli} for a complete listing). Again
 this is very similar to the boilerplate we needed to add in our JVM
 compiler.
 You can generate a binary for the program in Figure~\ref{lli} by using
 compiler we will use our own stepping stone which I call the
 \emph{K-language}. For what follows recall the various kinds of
 expressions in the Fun language. For convenience the Scala code of the
 corresponding abstract syntax trees is shown on top of
 Figure~\ref{absfun}. Below is the code for the abstract syntax trees in
-the K-language. There are two kinds of syntactic entities, namely
+the K-language. In K, here are two kinds of syntactic entities, namely
 \emph{K-values} and \emph{K-expressions}. The central constructor of the
-K-language is \texttt{KLet}. For this recall that arithmetic expressions
+K-language is \texttt{KLet}. For this recall in SSA that arithmetic
-such as $((1 + a) + (3 + (b * 5)))$ need to be broken up into smaller
+expressions such as $((1 + a) + (3 + (b * 5)))$ need to be broken up
-``atomic'' steps, like so
+into smaller ``atomic'' steps, like so
 \begin{lstlisting}[language=LLVMIR,numbers=none]
 let tmp0 = add 1 a in
 let tmp1 = mul b 5 in
 let tmp2 = add 3 tmp1 in
 \begin{figure}[p]\small
 \begin{lstlisting}[language=Scala,numbers=none]
-// Fun-language (expressions)
+// Fun language (expressions)
 abstract class Exp
 abstract class BExp
 case class Call(name: String, args: List[Exp]) extends Exp
 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
 The main difficulty of generating instructions in SSA format is that
 large compound expressions need to be broken up into smaller pieces and
 intermediate results need to be chained into later instructions. To do
 this conveniently, CPS-translations have been developed. They use
 functions (``continuations'') to represent what is coming next in a
-sequence of instructions.
+sequence of instructions. Continuations are functions of type
+\code{KVal} to \code{KExp}. They can be seen as a sequence of \code{KLet}s
+where there is a ``hole'' that needs to be filled. Consider for example
+\begin{lstlisting}[language=LLVMIR,numbers=left,escapeinside={(*@}{@*)}]
+let tmp0 = add 1 a in
+let tmp1 = mul (*@$\Box$@*) 5 in
+let tmp2 = add 3 tmp1 in
+let tmp3 = add tmp0 tmp2 in
+tmp3
+\end{lstlisting}
+\noindent
+where in the second line is a $\Box$ which still expects a \code{KVal}
+to be filled in before it becomes a ``proper'' \code{KExp}. When we
+apply and argument to the continuation (remember they are functions)
+we essentially fill something into the corresponding hole. The code
+of the CPS-translation is
+\begin{lstlisting}[language=Scala,numbers=none]
+def CPS(e: Exp)(k: KVal => KExp) : KExp =
+e match { ... }
+\end{lstlisting}
+\noindent
+where \code{k} is the continuation and \code{e} is the expression
+to be compiled. In case we have numbers or variables, we can just
+apply the continuation like
+\begin{center}
+\code{k(KNum(n))} \qquad \code{k(KVar(x))}
+\end{center}
+\noindent This would just fill in the $\Box$ in a \code{KLet}-expression.
+More interesting is the case for an arithmetic expression.
+\begin{lstlisting}[language=Scala,numbers=none]
+case Aop(o, e1, e2) => {
+val z = Fresh("tmp")
+CPS(e1)(y1 =>
+CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z)))))
+}
+\end{lstlisting}
+\noindent
 \end{document}
 %%% Local Variables:
 %%% mode: latex

changeset 701	681c36b2af27
parent 700	52263ffd17b9
child 704	6d9c960a2b26