# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1575680243 0
# Node ID 6d9c960a2b26df4ad34c23664b88e4e1c8ea90c7
# Parent  57b3ae5ba5e212209026f1ca80236c50eb59a4fa
updated

diff -r 57b3ae5ba5e2 -r 6d9c960a2b26 handouts/ho09.pdf
Binary file handouts/ho09.pdf has changed
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   
diff -r 57b3ae5ba5e2 -r 6d9c960a2b26 progs/compile-lexer.scala
--- a/progs/compile-lexer.scala	Wed Dec 04 14:39:32 2019 +0000
+++ b/progs/compile-lexer.scala	Sat Dec 07 00:57:23 2019 +0000
@@ -449,10 +449,10 @@
     else env
   case WriteS(s: String) => { println(s); env }
   case Write(s: String) => { println(env(s)); env }
-  case Read(s: String) => tokenizer(Console.readLine) match {
-    case List(T_NUM(n)) => env + (s -> n.toInt)
-    case _ => { println("not a number"); eval_stmt(Read(s: String), env) }
-  }
+  //case Read(s: String) => tokenizer(Console.readLine) match {
+  //  case List(T_NUM(n)) => env + (s -> n.toInt)
+  //  case _ => { println("not a number"); eval_stmt(Read(s: String), env) }
+  //}
 }
 
 def eval_bl(bl: Block, env: Env) : Env = bl match {
@@ -671,5 +671,6 @@
 //examples
 //println(compile("test", p9))
 //compile_run("loops.while")
-compile_run("p.while")
+//compile_run("p.while")
+compile_run("fib.while")
 //compile_run("test.while")
diff -r 57b3ae5ba5e2 -r 6d9c960a2b26 slides/slides10.pdf
Binary file slides/slides10.pdf has changed
diff -r 57b3ae5ba5e2 -r 6d9c960a2b26 slides/slides10.tex
--- a/slides/slides10.tex	Wed Dec 04 14:39:32 2019 +0000
+++ b/slides/slides10.tex	Sat Dec 07 00:57:23 2019 +0000
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
 \documentclass[dvipsnames,14pt,t]{beamer}
 \usepackage{../slides}
 \usepackage{../langs}
@@ -50,20 +51,62 @@
   \normalsize
   \begin{center}
   \begin{tabular}{ll}
-  Email:  & christian.urban at kcl.ac.uk\\
-  Office: & N7.07 (North Wing, Bush House)\\
-  Slides: & KEATS (also home work is there)\\
+    Email:  & christian.urban at kcl.ac.uk\\
+    Office Hours: & Thursdays 12 -- 14\\
+    Location: & N7.07 (North Wing, Bush House)\\
+    Slides \& Progs: & KEATS (also homework is there)\\  
   \end{tabular}
   \end{center}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+\begin{frame}[c,fragile]
+
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
+def fact(n: Int) : Int = {
+  if (n == 0) 1 else n * fact(n - 1) 
+}
+
+
+def factC(n: Int, ret: Int => Int) : Int = {
+  if (n == 0) ret(1) 
+  else factC(n - 1, x => ret(n * x)) 
+}
+
+fact(10)
+factC(10, identity)
+\end{lstlisting}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+\begin{frame}[c,fragile]
+
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-6mm]
+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)))
+}
+
+fibC(10, identity)
+\end{lstlisting}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 
-  \Large\bf Are there more strings in \bl{$L(a^*)$} or
+  \Large\bf Are there more strings in \\ \hfill\bl{$L(a^*)$} or
   \bl{$L((a + b)^*)$}?
 
 \end{frame}
@@ -71,6 +114,25 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{Can you remember this HW?}
+
+  \begin{itemize}
+  \item (1) How many basic regular expressions are there to match
+      the string \bl{$abcd$}? 
+  \item (2) How many if they cannot include
+      \bl{$\ONE$} and \bl{$\ZERO$}? 
+  \item (3) How many if they are also not
+      allowed to contain stars? 
+  \item (4) How many if they are also
+      not allowed to contain \bl{$\_ + \_$}?
+   \end{itemize}  
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 
 \Large\bf There are more problems, than there are
 programs.\bigskip\bigskip\pause\\