--- a/handouts/ho09.tex Thu May 25 21:22:23 2023 +0100
+++ b/handouts/ho09.tex Tue May 30 13:27:54 2023 +0100
@@ -4,12 +4,9 @@
\usepackage{../langs}
\usepackage{../graphics}
\usepackage{../grammar}
-%%\usepackage{multicol}
-
-%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}
\begin{document}
-\fnote{\copyright{} Christian Urban, King's College London, 2019}
+\fnote{\copyright{} Christian Urban, King's College London, 2019, 2023}
% CPS translations
@@ -22,27 +19,35 @@
Reflecting on our two tiny compilers targetting the JVM, the code
generation part was actually not so hard, no? Pretty much just some
-post-traversal of the abstract syntax tree, yes? One of the reasons for
-this ease is that the JVM is a stack-based virtual machine and it is
-therefore not hard to translate deeply-nested arithmetic expressions
-into a sequence of instructions manipulating the stack. The problem is
-that ``real'' CPUs, although supporting stack operations, are not really
-designed to be \emph{stack machines}. The design of CPUs is more like,
-here is a chunk of memory---compiler, or better compiler writers, do
-something with it. Consequently, modern compilers need to go the extra
-mile in order to generate code that is much easier and faster to process
-by CPUs. To make this all tractable for this module, we target the LLVM
-Intermediate Language. In this way we can take advantage of the tools
-coming with LLVM. For example we do not have to worry about things like
-register allocations.\bigskip
+post-traversal of the abstract syntax tree, yes? One of the reasons
+for this ease is that the JVM is a stack-based virtual machine and it
+is therefore not hard to translate deeply-nested arithmetic
+expressions into a sequence of instructions manipulating the
+stack. The problem is that ``real'' CPUs, although supporting stack
+operations, are not really designed to be \emph{stack machines}. The
+design of CPUs is more like: Here are some operations and a chunk of
+memory---compiler, or better compiler writers, do something with
+them. Consequently, modern compilers need to go the extra mile in
+order to generate code that is much easier and faster to process by
+actual CPUs, rather than running code on virtual machines that
+introduce an additional layer of indirection. To make this all
+tractable for this module, we target the LLVM Intermediate
+Language. In this way we can take advantage of the tools coming with
+LLVM.\footnote{\url{http://llvm.org}} For example we do not have to
+worry about things like register allocations. By using LLVM, however,
+we also have to pay price in the sense that generating code gets
+harder\ldots{}unfortunately.
-\noindent LLVM\footnote{\url{http://llvm.org}} is a beautiful example
+\subsection*{LLVM and LLVM-IR}
+
+\noindent LLVM is a beautiful example
that projects from Academia can make a difference in the World. LLVM
started in 2000 as a project by two researchers at the University of
Illinois at Urbana-Champaign. At the time the behemoth of compilers was
-gcc with its myriad of front-ends for other languages (C++, Fortran,
+gcc with its myriad of front-ends for different programming languages (C++, Fortran,
Ada, Go, Objective-C, Pascal etc). The problem was that gcc morphed over
-time into a monolithic gigantic piece of m\ldots ehm software, which you
+time into a monolithic gigantic piece of m\ldots ehm complicated
+software, which you
could not mess about in an afternoon. In contrast, LLVM is designed to
be a modular suite of tools with which you can play around easily and
try out something new. LLVM became a big player once Apple hired one of
@@ -54,44 +59,51 @@
We will target the LLVM Intermediate Language, or LLVM Intermediate
Representation (short LLVM-IR). The LLVM-IR looks very similar to the
-assembly language of Jasmin and Krakatau. It will also allow us to
-benefit from the modular structure of the LLVM compiler and let for
-example the compiler generate code for different CPUs, like X86 or ARM.
-That means we can be agnostic about where our code actually runs. We can
-also be ignorant about optimising code and allocating memory
-efficiently.
+assembly language of Jasmin and Krakatau. Targetting LLVM-IR will also
+allow us to benefit from the modular structure of the LLVM compiler
+and we can let, for example, the compiler generate code for different
+CPUs, say X86 or ARM. That means we can be agnostic about where our
+code is actually going to run.\footnote{Anybody want to try to run our
+ programs on Android phones?} We can also be somewhat ignorant about
+optimising our code and about allocating memory efficiently: the LLVM
+tools will take care of all this.
-However, what we have to do for LLVM is to generate code in \emph{Static
-Single-Assignment} format (short SSA), because that is what the LLVM-IR
-expects from us. A reason why LLVM uses the SSA format, rather than
-JVM-like stack instructions, is that stack instructions are difficult to
-optimise---you cannot just re-arrange instructions without messing about
-with what is calculated on the stack. Also it is hard to find out if all
-the calculations on the stack are actually necessary and not by chance
-dead code. The JVM has for all these obstacles sophisticated machinery
-to make such ``high-level'' code still run fast, but let's say that for
-the sake of argument we do not want to rely on it. We want to generate
-fast code ourselves. This means we have to work around the intricacies
-of what instructions CPUs can actually process fast. This is what the
-SSA format is designed for.
+However, what we have to do in order to make LLVM to play ball is to
+generate code in \emph{Static Single-Assignment} format (short SSA),
+because that is what the LLVM-IR expects from us. A reason why LLVM
+uses the SSA format, rather than JVM-like stack instructions, is that
+stack instructions are difficult to optimise---you cannot just
+re-arrange instructions without messing about with what is calculated
+on the stack. Also it is hard to find out if all the calculations on
+the stack are actually necessary and not by chance dead code. The JVM
+has for all these obstacles sophisticated machinery to make such
+``high-level'' code still run fast, but let's say that for the sake of
+argument we do not want to rely on it. We want to generate fast code
+ourselves. This means we have to work around the intricacies of what
+instructions CPUs can actually process fast. This is what the SSA
+format is designed for.
The main idea behind the SSA format is to use very simple variable
-assignments where every tmp-variable is assigned only once. The assignments
-also need to be primitive in the sense that they can be just simple
-operations like addition, multiplication, jumps, comparisons and so on.
-Say, we have an expression $((1 + a) + (3 + (b * 5)))$, then the
-corresponding SSA format is
+assignments where every tmp-variable is assigned only once. The
+assignments also need to be primitive in the sense that they can be
+just simple operations like addition, multiplication, jumps,
+comparisons, function calls and so on. Say, we have an expression
+$((1 + a) + (foo(3 + 2) + (b * 5)))$, then the corresponding SSA format is
\begin{lstlisting}[language=LLVMIR,numbers=left]
-let tmp0 = add 1 a in
-let tmp1 = mul b 5 in
-let tmp2 = add 3 tmp1 in
-let tmp3 = add tmp0 tmp2 in tmp3
+let tmp0 = add 1 a in
+let tmp1 = add 3 2 in
+let tmp2 = call foo(tmp1)
+let tmp3 = mul b 5 in
+let tmp4 = add tmp2 tmp3 in
+let tmp5 = add tmp0 tmp4 in
+ return tmp5
\end{lstlisting}
-\noindent where every variable is used only once (we could not write
-\texttt{tmp1 = add 3 tmp1} in Line 3 for example).
+\noindent where every tmp-variable is used only once (we could, for
+example, not write \texttt{tmp1 = add tmp2 tmp3} in Line 5 even if this
+would not change the overall result).
There are sophisticated algorithms for imperative languages, like C,
that efficiently transform a high-level program into SSA format. But
@@ -103,18 +115,18 @@
\subsection*{LLVM-IR}
-Before we start, let's first have a look at the \emph{LLVM Intermediate
+Before we start, let's however first have a look at the \emph{LLVM Intermediate
Representation} in more detail. The LLVM-IR is in between the frontends
and backends of the LLVM framework. It allows compilation of multiple
source languages to multiple targets. It is also the place where most of
the target independent optimisations are performed.
-What is good about our toy Fun language is that it basically only
+What is good about our toy Fun-language is that it basically only
contains expressions (be they arithmetic expressions, boolean
expressions or if-expressions). The exception are function definitions.
Luckily, for them we can use the mechanism of defining functions in the
LLVM-IR (this is similar to using JVM methods for functions in our
-earlier compiler). For example the simple Fun program
+earlier compiler). For example the simple Fun-program
\begin{lstlisting}[language=Scala,numbers=none]
@@ -131,26 +143,28 @@
}
\end{lstlisting}
-\noindent First notice that all variable names, in this case \texttt{x}
-and \texttt{tmp}, are prefixed with \texttt{\%} in the LLVM-IR.
-Temporary variables can be named with an identifier, such as
-\texttt{tmp}, or numbers. In contrast, function names, since they are ``global'',
-need to be prefixed with an @-symbol. Also, the LLVM-IR is a fully typed
-language. The \texttt{i32} type stands for 32-bit integers. There are
-also types for 64-bit integers (\texttt{i64}), chars (\texttt{i8}),
-floats, arrays and even pointer types. In the code above, \texttt{sqr}
-takes an argument of type \texttt{i32} and produces a result of type
-\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, for the moment \texttt{i32} everywhere will do. We do not have to generate
-any other types, but obviously this is a limitation in our Fun language.
+\noindent First notice that all ``local'' variable names, in this case
+\texttt{x} and \texttt{tmp}, are prefixed with \texttt{\%} in the
+LLVM-IR. Temporary variables can be named with an identifier, such as
+\texttt{tmp}, or numbers. In contrast, function names, since they are
+``global'', need to be prefixed with an @-symbol. Also, the LLVM-IR is
+a fully typed language. The \texttt{i32} type stands for 32-bit
+integers. There are also types for 64-bit integers (\texttt{i64}),
+chars (\texttt{i8}), floats, arrays and even pointer types. In the
+code above, \texttt{sqr} takes an argument of type \texttt{i32} and
+produces a result of type \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, for the moment \texttt{i32}
+everywhere will do. We do not have to generate any other types, but
+obviously this is a limitation in our Fun-language (and which we
+lift in the final CW).
There are a few interesting instructions in the LLVM-IR which are quite
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
+condition? In the LLVM-IR, branching if-conditions are implemented
differently: there is a separate \texttt{br}-instruction as follows:
\begin{lstlisting}[language=LLVM]
@@ -158,10 +172,13 @@
\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 it jumps to the else-branch, again with its own label. This allows us
-to keep the meaning of the boolean expression ``as is'' when compiling if's---thanks god no more negating the boolean.
+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 it jumps to the else-branch, again with its own
+label. This allows us to keep the meaning of the boolean expression
+``as is'' when compiling if's---thanks god no more negating of
+booleans.
+
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
@@ -175,7 +192,8 @@
\noindent
Note that in some operations the LLVM-IR distinguishes between signed and
-unsigned representations of integers.
+unsigned representations of integers. I assume you know what this means,
+otherwise just ask.
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
@@ -187,7 +205,7 @@
\end{lstlisting}
\noindent
-where the arguments can only be simple variables, not compound
+where the arguments can only be simple variables and numbers, but not compound
expressions.
Conveniently, you can use the program \texttt{lli}, which comes with
@@ -195,13 +213,13 @@
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 entry point
-for the program (see Figure~\ref{lli} for a complete listing). Again
+for the program (see Figure~\ref{lli} for a complete listing of the square function). 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
-the \texttt{llc}-compiler and then \texttt{gcc}, whereby \texttt{llc} generates
-an object file and \texttt{gcc} (that is clang) generates the
+the \texttt{llc}-compiler and then \texttt{gcc}/\texttt{clang}, whereby \texttt{llc} generates
+an object file and \texttt{gcc} (that is actually \texttt{clang} on my Mac) generates the
executable binary:
\begin{lstlisting}[language=bash,numbers=none]
@@ -214,90 +232,124 @@
\begin{figure}[t]\small
\lstinputlisting[language=LLVM,numbers=left]{../progs/sqr.ll}
\caption{An LLVM-IR program for calculating the square function. It
-calls this function in \texttt{@main} with the argument \texttt{5}. The
-code for the \texttt{sqr} function is in Lines 13 -- 16. The main
-function calls \texttt{sqr} and then prints out the result. The other
-code is boilerplate for printing out integers.\label{lli}}
+ calls the sqr-function in \texttt{@main} with the argument \texttt{5}
+ (Line 20). The
+ code for the \texttt{sqr} function is in Lines 13 -- 16. It stores
+ the result of sqr in the variable called \texttt{\%i} and then
+ prints out the contents of this variable in Line 21. The other
+ code is boilerplate for printing out integers.\label{lli}}
\end{figure}
\subsection*{Our Own Intermediate Language}
-Remember compilers have to solve the problem of bridging the gap between
-``high-level'' programs and ``low-level'' hardware. If the gap is too
-wide for one step, then a good strategy is to lay a stepping stone
-somewhere in between. The LLVM-IR itself is such a stepping stone to
-make the task of generating and optimising code easier. Like a real
-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. 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 in SSA that arithmetic
-expressions such as $((1 + a) + (3 + (b * 5)))$ need to be broken up
-into smaller ``atomic'' steps, like so
+Let's get back to our compiler: Remember compilers have to solve the
+problem of bridging the gap between ``high-level'' programs and
+``low-level'' hardware. If the gap is too wide for one step, then a
+good strategy is to lay a stepping stone somewhere in between. The
+LLVM-IR itself is such a stepping stone to make the task of generating
+and optimising code easier. Like a real compiler we will use our own
+stepping stone which I call the \emph{K-language}.
+
+\begin{center}
+ \begin{tikzpicture}[scale=0.9,font=\bf,
+ node/.style={
+ rectangle,rounded corners=3mm,
+ ultra thick,draw=black!50,minimum height=16mm,
+ minimum width=20mm,
+ top color=white,bottom color=black!20}]
+
+ %\node (0) at (-3,0) {};
+ \node (A) at (0.0,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}source}] {Fun-Language};
+ \node (B) at (3.5,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}stepping stone}] {K-Language};
+ \node (C) at (7.0,0) [node,text width=1.6cm,text centered,label=above:{\small\it{}target}] {LLVM-IR};
+
+ \draw [->,line width=2.5mm] (A) -- node [above,pos=0.35] {} (B);
+ \draw [->,line width=2.5mm] (B) -- node [above,pos=0.35] {} (C);
+ \end{tikzpicture}
+ \end{center}
+
+ \noindent
+ To see why we need a stepping stone for generating code in SSA-format,
+ considder again arithmetic expressions such as
+ $((1 + a) + (3 + (b * 5)))$. They need to be broken up 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
let tmp3 = add tmp0 tmp2 in
- tmp3
+ return tmp3
+\end{lstlisting}
+
+\noindent
+Here \texttt{tmp3} will contain the result of what the whole
+expression stands for. In each individual step we can only perform an
+``atomic'' or ``trival'' operation, like addition or multiplication of
+a number or a variable. We are not allowed to have for example a
+nested addition or an if-condition on the right-hand side of an
+assignment. Such constraints are forced upon us because of how the SSA
+format works in the LLVM-IR. To simplify matters we represent
+assignments with two kinds of syntactic entities, namely
+\emph{K-values} and \emph{K-expressions}. K-values are all ``things''
+that can appear on the right-hand side of an equal. Say we have
+the following definition for K-values:
+
+\begin{lstlisting}[language=Scala,numbers=none]
+enum KVal {
+ case KVar(s: String)
+ case KNum(n: Int)
+ case KAop(op: String, v1: KVal, v2: KVal)
+ case KCall(fname: String, args: List[KVal])
+}
\end{lstlisting}
\noindent
-Here \texttt{tmp3} will contain the result of what the whole expression
-stands for. In each individual step we can only perform an ``atomic''
-operation, like addition or multiplication of a number and a variable.
-We are not allowed to have for example an if-condition on the right-hand
-side of an equals. Such constraints are enforced upon us because of how
-the SSA format works in the LLVM-IR. By having in \texttt{KLet} taking
-first a string (standing for an intermediate result) and second a value,
-we can fulfil this constraint ``by construction''---there is no way we
-could write anything else than a value.
-
-To sum up, K-values are the atomic operations that can be on the
-right-hand side of equal-signs. The K-language is restricted such that
-it is easy to generate the SSA format for the LLVM-IR.
-
+where a K-value can be a variable, a number or a ``trivial'' binary
+operation, such as addition or multiplication. The two arguments of a
+binary operation need to be K-values as well. Finally, we have
+function calls, but again each argument of the function call needs to
+be a K-value. One point we need to be careful, however, is that the
+arguments of the binary operations and function calls are in fact only
+variables or numbers. To encode this constraint into the type-system
+of Scala would make things too complicated---to satisfy this
+constraint is therefore on us. For our Fun-language, we will later on
+consider some further K-values.
-\begin{figure}[p]\small
-\begin{lstlisting}[language=Scala,numbers=none]
-// Fun language (expressions)
-abstract class Exp
-abstract class BExp
+Our K-expressions will encode the \texttt{let} and the \texttt{return}
+from the SSA-format (again for the moment we only consider these two
+constructors---later on we will have if-branches as well).
-case class Call(name: String, args: List[Exp]) extends Exp
-case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
-case class Write(e: Exp) extends Exp
-case class Var(s: String) extends Exp
-case class Num(i: Int) extends Exp
-case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
-case class Sequence(e1: Exp, e2: Exp) extends Exp
-case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
-
-
+\begin{lstlisting}[language=Scala,numbers=none]
+enum KExp {
+ case KLet(x: String, v: KVal, e: KExp)
+ case KReturn(v: KVal)
+}
+\end{lstlisting}
-// K-language (K-expressions, K-values)
-abstract class KExp
-abstract class KVal
+\noindent
+By having in \texttt{KLet} taking first a string (standing for an
+intermediate variable) and second a value, we can fulfil the SSA
+constraint in assignments ``by construction''---there is no way we
+could write anything else than a K-value. Note that the third
+argument of a \texttt{KLet} is again a K-expression, meaning either
+another \texttt{KLet} or a \texttt{KReturn}. In this way we can
+construct a sequence of computations and return a final result. Of
+course we also have to ensure that all intermediary computations are
+given (fresh) names---we will use an (ugly) counter for this.
-case class KVar(s: String) extends KVal
-case class KNum(i: Int) extends KVal
-case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
-case class KCall(o: String, vrs: List[KVal]) extends KVal
-case class KWrite(v: KVal) extends KVal
+To sum up, K-values are the atomic operations that can be on the
+right-hand side of assignemnts. The K-language is restricted such that
+it is easy to generate the SSA format for the LLVM-IR. What remains to
+be done is a translation of our Fun-language into the K-language. The
+main difficulty is that we need to order the computationa---in teh
+K-language we only have linear sequence of instructions to need to be
+followed. Before we explain this, we have a look at some
+CPS-translation.
-case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
-case class KLet(x: String, v: KVal, e: KExp) extends KExp
-case class KReturn(v: KVal) extends KExp
-\end{lstlisting}
-\caption{Abstract syntax trees for the Fun language.\label{absfun}}
-\end{figure}
@@ -305,7 +357,7 @@
CPS stands for Continuation-Passing-Style. It is a kind of programming
technique often used in advanced functional programming. Before we delve
-into the CPS-translation for our Fun language, let us look at
+into the CPS-translation for our Fun-language, let us look at
CPS-versions of some well-known functions. Consider
\begin{lstlisting}[language=Scala, numbers=none]
@@ -349,7 +401,9 @@
\noindent
which is the expected result. If this looks somewhat familiar to you,
than this is because functions with continuations can be
-seen as a kind of generalisation of tail-recursive functions. Anyway
+seen as a kind of generalisation of tail-recursive functions.
+So far we did not look at this generalisation in earnest.
+Anyway
notice how the continuations is ``stacked up'' during the recursion and
then ``unrolled'' when we apply 1 to the continuation. Interestingly, we
can do something similar to the Fibonacci function where in the traditional
@@ -380,31 +434,83 @@
3
\end{lstlisting}
-Let us now come back to the CPS-translations for the Fun language. The
+\noindent
+The point of this section is that you are playing around with these
+simple definitions and make sure they calculate the expected result.
+In the next step, you should understand \emph{how} these functions
+calculate the result with the continuations.
+
+
+\section*{Worked Example}
+
+Let us now come back to the CPS-translations for the Fun-language. 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
+this conveniently, we use the CPS-translation mechanism. What continuations
+essentially solve is the following problem: Given an expressions
+
+\begin{equation}\label{exp}
+(1 + 2) * (3 + 4)
+\end{equation}
+
+\noindent
+which of the subexpressions should be calculated first? We just arbitrarily
+going to decide that it will be from left to right. This means we have
+to tear the expression shown in \eqref{exp} apart as follows:
+
+\[
+(1 + 2) \qquad\text{and}\qquad \Box * (3 + 4)
+\]
+
+\noindent
+The first one will give us a result, but the second one is not
+really an expression that makes sense. It will only make sense
+as the next step in the computation when we fill-in the result of
+$1+2$ into the ``hole'' indicated by $\Box$. Such incomplete
+expressions can be represented in Scala as functions
+
+\begin{lstlisting}[language=Scala, numbers=none]
+r => r * (3 + 4)
+\end{lstlisting}
+
+\noindent
+where \texttt{r} is any result that has been computed earlier. By the
+way in lambda-calculus notation we would write
+$\lambda r.\, r * (3 + 4)$ for the same function. To sum up, we use
functions (``continuations'') to represent what is coming next in a
-sequence of instructions. In our case, 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
+sequence of instructions. In our case, 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
+ retrun 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 an argument to the continuation (remember they are functions)
-we essentially fill something into the corresponding hole. The code
-of the CPS-translation is
+we essentially fill something into the corresponding hole.
+
+Lets look at concrete code. To simplify matters first,
+suppose our source language consists just of three kinds of expressions
+
+\begin{lstlisting}[language=Scala,numbers=none]
+enum Expr {
+ case Num(n: Int)
+ case Bop(op: String, e1: Expr, e2: Expr)
+ case Call(fname: String, args: List[Expr])
+}
+\end{lstlisting}
+
+\noindent
+The code of the CPS-translation is then of the form
\begin{lstlisting}[language=Scala,numbers=none]
def CPS(e: Exp)(k: KVal => KExp) : KExp =
@@ -412,28 +518,159 @@
\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
+where \code{k} is the continuation and \code{e} is the expression to
+be compiled. In case we have numbers, we can just pass them to the
+continuations because numbers need not be further teared apart as they
+are already atomic. Passing the number to the continuation means we
apply the continuation like
-\begin{center}
-\code{k(KNum(n))} \qquad \code{k(KVar(x))}
-\end{center}
+\begin{lstlisting}[language=Scala,numbers=none]
+ case Num(i) => k(KNum(i))
+\end{lstlisting}
\noindent This would just fill in the $\Box$ in a \code{KLet}-expression.
-More interesting is the case for an arithmetic expression.
+There is no need to create a temporary variable for simple numbers.
+More interesting is the case for arithmetic operations.
+
+\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
+case Aop(op, e1, e2) => {
+ val z = Fresh("tmp")
+ CPS(e1)(r1 =>
+ CPS(e2)(r2 => KLet(z, KAop(op, r1, r2), k(KVar(z)))))
+}
+\end{lstlisting}
+
+\noindent
+What we essentially have to do in this case is the following: compile
+the subexpressions \texttt{e1} and \texttt{e2}. They will produce some
+result that is stored in two temporary variables (assuming they are more
+complicated than just numbers). We need to use these two temporary
+variables and feed them into a new assignment of the form
+
+\begin{lstlisting}[language=LLVMIR,numbers=none,escapeinside={(*@}{@*)}]
+let z = op (*@$\Box_\texttt{r1}$@*) (*@$\Box_\texttt{r2}$@*) in
+...
+\end{lstlisting}
-\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)))))
+\noindent
+Note that this assignment has two ``holes'', one for the left
+subexpression and one for the right subexpression. We can fill both
+holes by calling the CPS function twice---this is a bit of the black
+art in CPS. We can use the second call of CPS as the continuation
+of the first call: The reason is that
+
+\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
+r1 => CPS(e2)(r2 => KLet(z, KAop(op, r1, r2), k(KVar(z))))
+\end{lstlisting}
+
+\noindent is a function from \code{KVal} to \code{KExp}. Once
+we created the assignment with the fresh temporary variable
+\texttt{z}, we need to ``communicate'' that the result of the
+computation of the arithmetic expression is stored in \texttt{z} to the
+computations that follow. In this way we apply the continuation \texttt{k} with this
+new variable (essentially we are plugging in a hole further down the line).
+
+The last case we need to consider in our small expression language are
+function calls.
+
+\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=0mm]
+case Call(fname, args) => {
+ def aux(args: List[Expr], vs: List[KVal]): KExp = args match {
+ case Nil => {
+ val z = Fresh("tmp")
+ KLet(z, KCall(fname, vs), k(KVar(z)))
+ }
+ case a::as => CPS(a)(r => aux(as, vs ::: List(r)))
+ }
+ aux(args, Nil)
}
\end{lstlisting}
\noindent
-For more such rules, have a look to the code of the fun-llvm
-compiler.
+For them we introduce an auxiliary function that compiles first all
+function arguments---remember in our source language we can have calls
+such as $foo(3 + 4, g(3))$ where we first have to create temporary
+variables (and computations) for each argument. Therefore \texttt{aux}
+analyses the arguments from left to right. In case there is an argument
+\texttt{a} on the front of the list (the case \texttt{a::as}), we call
+CPS recursively for the corresponding subexpression. The temporary variable
+containing the result for this argument we add to the end of the K-values we
+have already analysed before. Again very conveniently we can use the
+recursive call to \texttt{aux} as the continuation for the computations
+that follow. If we reach the end of the argument list (the \texttt{Nil}-case),
+then we collect all the K-values \texttt{v1} to \texttt{vn} and call the
+function in the K-language like so
+
+
+\begin{lstlisting}[language=LLVMIR,numbers=none,escapeinside={(*@}{@*)}]
+let z = call foo(v1,...,vn) in
+...
+\end{lstlisting}
+
+\noindent
+Again we need to communicate the result of the function call, namely the
+fresh temporary variable \texttt{z}, to the rest of the computation. Therefore
+we apply the continuation \texttt{k} with this variable.
+
+
+
+\begin{figure}[p]\small
+ \lstinputlisting[numbers=left,firstline=1,lastline=24]{../progs/fun/simple-cps.sc}
+ \hspace{10mm}...
+ \lstinputlisting[numbers=left,firstline=32,firstnumber=32,lastline=51]{../progs/fun/simple-cps.sc}
+\caption{CPS-translation for a simple expression language.\label{cps}}
+\end{figure}
+
+The last question we need to answer in the code (see Figure~\ref{cps}) is how we
+start the CPS-translation function, or more precisely with which continuation we
+should start CPS? It turns out that this initial continuation will be the last one that is
+called. What should be the last step in the computation? Yes, we need to return the
+temporary variable where the last result is stored (if it is a simple number, then we can
+just return this number). Therefore we cal CPS with the code
+
+\begin{lstlisting}[language=Scala,numbers=none]
+def CPSi(e: Expr) : KExp = CPS(e)(KReturn(_))
+\end{lstlisting}
+
+\noindent
+where we give the function \code{KReturn(_)}.
+
+
+\begin{figure}[p]\small
+\begin{lstlisting}[language=Scala,numbers=none]
+// 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
+case class Write(e: Exp) extends Exp
+case class Var(s: String) extends Exp
+case class Num(i: Int) extends Exp
+case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
+case class Sequence(e1: Exp, e2: Exp) extends Exp
+case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
+
+
+
+// K-language (K-expressions, K-values)
+abstract class KExp
+abstract class KVal
+
+case class KVar(s: String) extends KVal
+case class KNum(i: Int) extends KVal
+case class Kop(o: String, v1: KVal, v2: KVal) extends KVal
+case class KCall(o: String, vrs: List[KVal]) extends KVal
+case class KWrite(v: KVal) extends KVal
+
+case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp
+case class KLet(x: String, v: KVal, e: KExp) extends KExp
+case class KReturn(v: KVal) extends KExp
+\end{lstlisting}
+\caption{Abstract syntax trees for the Fun-language.\label{absfun}}
+\end{figure}
+
+
\noindent
\end{document}