--- a/handouts/ho09.tex Sun Nov 24 16:30:34 2019 +0000
+++ b/handouts/ho09.tex Thu Nov 28 08:18:57 2019 +0000
@@ -138,13 +138,13 @@
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
-through with boolean expressions and negating the condition? In the
-LLVM-IR, branching if-conditions is implemented differently: there
-is a separate \texttt{br}-instruction as follows:
+different than what we have seen in the JVM. Can you remember the
+kerfuffle we had to go through with boolean expressions and negating the
+condition? In the LLVM-IR, branching if-conditions is implemented
+differently: there is a separate \texttt{br}-instruction as follows:
\begin{lstlisting}[language=LLVM]
br i1 %var, label %if_br, label %else_br
@@ -154,10 +154,10 @@
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
-boolean is generated in the LLVM-IR by the \texttt{icmp}-instruction.
-This instruction is for integers (hence the \texttt{i}) and takes the
-comparison operation as argument. For example
+to keep the meaning of the boolean expression as is when compiling if's.
+A value of type boolean is generated in the LLVM-IR by the
+\texttt{icmp}-instruction. This instruction is for integers (hence the
+\texttt{i}) and takes the comparison operation as argument. For example
\begin{lstlisting}[language=LLVM]
icmp eq i32 %x, %y ; for equal
@@ -170,11 +170,24 @@
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.
@@ -214,11 +227,11 @@
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
-such as $((1 + a) + (3 + (b * 5)))$ need to be broken up into smaller
-``atomic'' steps, like so
+K-language is \texttt{KLet}. For this recall in SSA that arithmetic
+expressions such as $((1 + a) + (3 + (b * 5)))$ need to be broken up
+into smaller ``atomic'' steps, like so
\begin{lstlisting}[language=LLVMIR,numbers=none]
let tmp0 = add 1 a in
@@ -247,7 +260,7 @@
\begin{figure}[p]\small
\begin{lstlisting}[language=Scala,numbers=none]
-// Fun-language (expressions)
+// Fun language (expressions)
abstract class Exp
abstract class BExp
@@ -288,12 +301,51 @@
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}