diff -r 57b3ae5ba5e2 -r 6d9c960a2b26 handouts/ho09.tex
--- a/handouts/ho09.tex	Wed Dec 04 14:39:32 2019 +0000
+++ b/handouts/ho09.tex	Sat Dec 07 00:57:23 2019 +0000
@@ -296,14 +296,93 @@
 
 \subsection*{CPS-Translations}
 
-The main difficulty of generating instructions in SSA format is that
-large compound expressions need to be broken up into smaller pieces and
+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 
+CPS-versions of some well-known functions. Consider
+
+\begin{lstlisting}[language=Scala, numbers=none]
+def fact(n: Int) : Int = 
+  if (n == 0) 1 else n * fact(n - 1) 
+\end{lstlisting}
+
+\noindent 
+This is clearly the usual factorial function. But now consider the
+following version of the factorial function:
+
+\begin{lstlisting}[language=Scala, numbers=none]
+def factC(n: Int, ret: Int => Int) : Int = 
+  if (n == 0) ret(1) 
+  else factC(n - 1, x => ret(n * x)) 
+
+factC(3, identity)
+\end{lstlisting}
+
+\noindent
+This function is called with the number, in this case 3, and the
+identity-function (which returns just its input). The recursive
+calls are:
+
+\begin{lstlisting}[language=Scala, numbers=none]
+factC(2, x => identity(3 * x))
+factC(1, x => identity(3 * (2 * x)))
+factC(0, x => identity(3 * (2 * (1 * x))))
+\end{lstlisting}
+
+\noindent
+Having reached 0, we get out of the recursion and apply 1 to the
+continuation (see if-branch above). This gives
+
+\begin{lstlisting}[language=Scala, numbers=none]
+identity(3 * (2 * (1 * 1)))
+= 3 * (2 * (1 * 1))
+= 6
+\end{lstlisting}
+
+\noindent
+which is the expected result. If this looks somewhat familiar, then this
+is not a 1000 miles off, because functions with continuations can be
+seen as a kind of generalisation of tail-recursive functions. 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
+version we have two recursive calls. Consider the following function
+
+\begin{lstlisting}[language=Scala, numbers=none]
+def fibC(n: Int, ret: Int => Int) : Int = 
+  if (n == 0 || n == 1) ret(1) 
+  else fibC(n - 1,
+             r1 => fibC(n - 2,
+               r2 => ret(r1 + r2)))
+\end{lstlisting}
+
+\noindent
+Here the continuation is a nested function essentially wrapping up 
+the second recursive call. Let us check how the recursion unfolds
+when called with 3 and the identity function:
+
+\begin{lstlisting}[language=Scala, numbers=none]
+fibC(3, id)
+fibC(2, r1 => fibC(1, r2 => id(r1 + r2)))
+fibC(1, r1 => 
+   fibC(0, r2 => fibC(1, r2a => id((r1 + r2) + r2a))))
+fibC(0, r2 => fibC(1, r2a => id((1 + r2) + r2a)))
+fibC(1, r2a => id((1 + 1) + r2a))
+id((1 + 1) + 1)
+(1 + 1) + 1
+3
+\end{lstlisting}
+
+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
 functions (``continuations'') to represent what is coming next in a
 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
+\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