
diff -r f1d4d582ac29 -r 81377a3eb717 handouts/ho09.tex
--- 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}
 
 




