299 The main difficulty of generating instructions in SSA format is that

   299 CPS stands for Continuation-Passing-Style. It is a kind of programming

   300 large compound expressions need to be broken up into smaller pieces and

   300 technique often used in advanced functional programming. Before we delve

   301 into the CPS-translation for our Fun language, let us look at 

   302 CPS-versions of some well-known functions. Consider

   303 

   304 \begin{lstlisting}[language=Scala, numbers=none]

   305 def fact(n: Int) : Int = 

   306   if (n == 0) 1 else n * fact(n - 1) 

   307 \end{lstlisting}

   308 

   309 \noindent 

   310 This is clearly the usual factorial function. But now consider the

   311 following version of the factorial function:

   312 

   313 \begin{lstlisting}[language=Scala, numbers=none]

   314 def factC(n: Int, ret: Int => Int) : Int = 

   315   if (n == 0) ret(1) 

   316   else factC(n - 1, x => ret(n * x)) 

   317 

   318 factC(3, identity)

   319 \end{lstlisting}

   320 

   321 \noindent

   322 This function is called with the number, in this case 3, and the

   323 identity-function (which returns just its input). The recursive

   324 calls are:

   325 

   326 \begin{lstlisting}[language=Scala, numbers=none]

   327 factC(2, x => identity(3 * x))

   328 factC(1, x => identity(3 * (2 * x)))

   329 factC(0, x => identity(3 * (2 * (1 * x))))

   330 \end{lstlisting}

   331 

   332 \noindent

   333 Having reached 0, we get out of the recursion and apply 1 to the

   334 continuation (see if-branch above). This gives

   335 

   336 \begin{lstlisting}[language=Scala, numbers=none]

   337 identity(3 * (2 * (1 * 1)))

   338 = 3 * (2 * (1 * 1))

   339 = 6

   340 \end{lstlisting}

   341 

   342 \noindent

   343 which is the expected result. If this looks somewhat familiar, then this

   344 is not a 1000 miles off, because functions with continuations can be

   345 seen as a kind of generalisation of tail-recursive functions. Anyway

   346 notice how the continuations is ``stacked up'' during the recursion and

   347 then ``unrolled'' when we apply 1 to the continuation. Interestingly, we

   348 can do something similar to the Fibonacci function where in the traditional

   349 version we have two recursive calls. Consider the following function

   350 

   351 \begin{lstlisting}[language=Scala, numbers=none]

   352 def fibC(n: Int, ret: Int => Int) : Int = 

   353   if (n == 0 || n == 1) ret(1) 

   354   else fibC(n - 1,

   355              r1 => fibC(n - 2,

   356                r2 => ret(r1 + r2)))

   357 \end{lstlisting}

   358 

   359 \noindent

   360 Here the continuation is a nested function essentially wrapping up 

   361 the second recursive call. Let us check how the recursion unfolds

   362 when called with 3 and the identity function:

   363 

   364 \begin{lstlisting}[language=Scala, numbers=none]

   365 fibC(3, id)

   366 fibC(2, r1 => fibC(1, r2 => id(r1 + r2)))

   367 fibC(1, r1 => 

   368    fibC(0, r2 => fibC(1, r2a => id((r1 + r2) + r2a))))

   369 fibC(0, r2 => fibC(1, r2a => id((1 + r2) + r2a)))

   370 fibC(1, r2a => id((1 + 1) + r2a))

   371 id((1 + 1) + 1)

   372 (1 + 1) + 1

   373 3

   374 \end{lstlisting}

   375 

   376 Let us now come back to the CPS-translations for the Fun language. The

   377 main difficulty of generating instructions in SSA format is that large

   378 compound expressions need to be broken up into smaller pieces and

   305 \code{KVal} to \code{KExp}. They can be seen as a sequence of \code{KLet}s

   383 \code{KVal} to \code{KExp}. They can be seen as a sequence of

   306 where there is a ``hole'' that needs to be filled. Consider for example

   384 \code{KLet}s where there is a ``hole'' that needs to be filled. Consider

   385 for example