# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1701553024 0
# Node ID fddf099a82f8265df5e833915ea784562e47a116
# Parent  34b3aeb65fbed3327a4b45c40b48ffe64224c983
updated

diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw01.pdf
Binary file hws/hw01.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw02.pdf
Binary file hws/hw02.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw03.pdf
Binary file hws/hw03.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw04.pdf
Binary file hws/hw04.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw05.pdf
Binary file hws/hw05.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw06.pdf
Binary file hws/hw06.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw07.pdf
Binary file hws/hw07.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw08.pdf
Binary file hws/hw08.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw09.pdf
Binary file hws/hw09.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 hws/hw09.tex
--- a/hws/hw09.tex	Tue Nov 28 11:45:48 2023 +0000
+++ b/hws/hw09.tex	Sat Dec 02 21:37:04 2023 +0000
@@ -13,7 +13,17 @@
 \begin{enumerate}
 \item Describe what is meant by \emph{eliminating tail
       recursion}? When can this optimization be applied and
-      why is it of benefit?
+    why is it of benefit?
+
+    \solution{ Tail-call optimisation replaces a recursive call (in
+      tail-call position) by a jump to the beginning of a function.
+      In this way a recursion is replaced by a loop. This saves stack
+      space because no new stack space needs to be allocated when a
+      function is called recursively.
+
+      Tail-call optimisation can be applied when the recursive call is
+    the last instruction that is run in the function.}
+    
 
 \item A programming language has arithmetic expression. For an
   arithmetic expression the compiler of this language produces the
@@ -34,6 +44,10 @@
   Give the arithmetic expression that produced this code.  Make sure
   you give all necessary parentheses.
 
+  \solution{
+    $1 + ((2 * 3) + (4 - 3))$
+  }
+
 \item Describe what the following JVM instructions do!
 
   
@@ -45,6 +59,11 @@
 if_icmpge label
 \end{lstlisting}
 
+\solution{
+(1) load the constant 3 onto the stack. (2) load the 4th local variable onto the stack. (3) store the top of the stack into the 2nd local variable (deleting the top element from the stack) (4) tests whether the top of the stack is equal to zero (if yes, then jump to label; delete top of the stack) (5) compares the top 2 elements of the stack whether they are greater or equal (if yes jump to label; delete two topmost elements from the stack) 
+  }
+
+
 \item What does the following JVM function calculate?
 
 \begin{lstlisting}[language=JVMIS2,numbers=none]    
@@ -78,6 +97,8 @@
 .end method  
 \end{lstlisting}
 
+\solution{ Fibonacci function..students should be able to read what the instructions do on the stack).}
+
 \item What does the following LLVM function calculate? Give the
   corresponding arithmetic expression .
 
@@ -93,10 +114,22 @@
 }
 \end{lstlisting}
 
-\item As an optimisation technique, a compiler might want to detect `dead code' and
-  not generate anything for this code. Why does this optimisation technique have the
-  potential of speeding up the run-time of a program? (Hint: On what kind of CPUs are programs
-  run nowadays?)
+\solution{ $a^2+a*2*b + b^2$
+  }
+
+
+\item As an optimisation technique, a compiler might want to detect
+  `dead code' and not generate anything for this code. Why does this
+  optimisation technique have the potential of speeding up the
+  run-time of a program? (Hint: On what kind of CPUs are programs run
+  nowadays?)
+
+  \solution{ Modern CPUs use predictive branching (guessing which
+    code-branch is run) and use the cache extensively...any code that
+    isn't in the program helps with guessing the right branch and does
+    not occupy anything in the cache. So in effect the code will run
+    faster.  }
+  
 
 \item In an earlier question, we analysed the advantages of having a lexer-phase
   before running the parser (having a lexer is definitely a good thing to have). But you
@@ -112,9 +145,20 @@
 
   What is wrong with implementing a lexer in this way?
 
+  \solution { There is no problem in terms of which strings are
+    matched (the grammar can be defined such that it matches exactly
+    the same strings. However, CFG do not obey the POSIX rules,
+    meaning they cannot implement ``how regular expressions matc a
+    string'' (for example longest match rule; rule priority).  }
+  
+
 \item What is the difference between a parse tree and an abstract
   syntax tree? Give some simple examples for each of them.
 
+  \solution { Parse-trees follow the grammar rules, therefore the
+    inner nodes correspond to the non-terminal symbols in CFGs. ASTs
+    represent the tree-structure of the programs. }
+
 \item What are the two main features of code in
   static single assignment form (SSA)?
 
diff -r 34b3aeb65fbe -r fddf099a82f8 progs/fun/fun_llvm.sc
--- a/progs/fun/fun_llvm.sc	Tue Nov 28 11:45:48 2023 +0000
+++ b/progs/fun/fun_llvm.sc	Sat Dec 02 21:37:04 2023 +0000
@@ -74,6 +74,35 @@
 }
 case class KReturn(v: KVal) extends KExp
 
+// some functions for drawing KVal-trees 
+// inspired by William Bradford Larcombe
+
+def draw_vals(vs: List[KVal], prefix: String) : String = {
+  val vsi = vs.iterator
+  vsi.map(v => draw_val(v, prefix, vsi.hasNext)).mkString 
+}
+
+def draw_val(k: KVal, prefix: String, more: Boolean) : String = {
+  val full_prefix = s"$prefix${if more then "├" else "└"}"
+  val childPrefix = s"$prefix${if more then "│" else ""}  "
+  s"\n${full_prefix}" ++ 
+  (k match {
+    case KVar(x) => x
+    case KNum(n) => n.toString
+    case Kop(op, v1 , v2) => s"KOp($op) ${draw_vals(List(v1, v2), childPrefix)}" 
+    case KCall(nme, as) => s"KCall($nme) ${draw_vals(as, childPrefix)}" 
+    case KWrite(v) => s"KWrite ${draw_val(v, childPrefix, false)}" 
+  })
+}
+
+def draw(k: KVal) = "│" ++ draw_val(k, "", false)
+
+// val k1 = KVar("foo")
+// val k2 = KNum(1)
+// val k3 = Kop("-", Kop("+", k1, k2), KNum(2))
+// println(draw(k3).mkString)
+// println(draw(KCall("bar", List(k1,k2,k3,k2,k1))).mkString)
+
 
 // CPS translation from Exps to KExps using a
 // continuation k.
@@ -112,6 +141,8 @@
 //initial continuation
 def CPSi(e: Exp) = CPS(e)(KReturn)
 
+
+
 //some testcases:
 // (1 + 2) * 3
 println(CPSi(Aop("*", Aop("+", Num(1), Num(2)), Num(3))).toString)
@@ -184,13 +215,12 @@
 
 
 
-
 // convenient string interpolations 
 // for instructions, labels and methods
 import scala.language.implicitConversions
 import scala.language.reflectiveCalls
 
-implicit def sring_inters(sc: StringContext) = new {
+extension (sc: StringContext) {
     def i(args: Any*): String = "   " ++ sc.s(args:_*) ++ "\n"
     def l(args: Any*): String = sc.s(args:_*) ++ ":\n"
     def m(args: Any*): String = sc.s(args:_*) ++ "\n"
@@ -271,14 +301,6 @@
 def compile(prog: List[Decl]) : String = 
   prelude ++ (prog.map(compile_decl).mkString)
 
-
-// pre-2.5.0 ammonite 
-// import ammonite.ops._
-
-// post 2.5.0 ammonite
-// import os._
-
-
 @main
 def main(fname: String) = {
     val path = os.pwd / fname
diff -r 34b3aeb65fbe -r fddf099a82f8 progs/fun/funt.sc
--- a/progs/fun/funt.sc	Tue Nov 28 11:45:48 2023 +0000
+++ b/progs/fun/funt.sc	Sat Dec 02 21:37:04 2023 +0000
@@ -98,12 +98,12 @@
     compile_expT(a2, env, name) ++
     l"$if_end"
   }
-  case Call(n, args) => if (name == n) { 
+  case Call(n, args) => if (name == n) { // can apply tail-call optimisation
     val stores = args.zipWithIndex.map { case (x, y) => i"istore $y" } 
     args.map(a => compile_expT(a, env, "")).mkString ++
     stores.reverse.mkString ++ 
     i"goto ${n}_Start" 
-  } else {
+  } else { // normal call
     val is = "I" * args.length
     args.map(a => compile_expT(a, env, "")).mkString ++
     i"invokestatic XXX/XXX/${n}(${is})I"
diff -r 34b3aeb65fbe -r fddf099a82f8 progs/while-arrays/compile_arrays.sc
--- a/progs/while-arrays/compile_arrays.sc	Tue Nov 28 11:45:48 2023 +0000
+++ b/progs/while-arrays/compile_arrays.sc	Sat Dec 02 21:37:04 2023 +0000
@@ -7,6 +7,8 @@
 //
 // amm compile_arrays.sc
   
+//> using toolkit latest
+
 
 // the abstract syntax trees for WHILE
 
@@ -234,9 +236,9 @@
 
 
    
-@main def main() = {
-  compile_and_run(array_test, "arr")
-}
+//@main def main() = {
+//  compile_and_run(array_test, "arr")
+//}
 
 
 
diff -r 34b3aeb65fbe -r fddf099a82f8 progs/while-arrays/compile_bfc.sc
--- a/progs/while-arrays/compile_bfc.sc	Tue Nov 28 11:45:48 2023 +0000
+++ b/progs/while-arrays/compile_bfc.sc	Sat Dec 02 21:37:04 2023 +0000
@@ -22,6 +22,9 @@
 // fastparse used in this file is not yet supported
 // under ammonite.
 
+// compile_arrays.sc (no peephole optimisations)
+// compile_arrays2.sc (peephole optimisations applied)
+
 //> using file compile_arrays2.sc
 import compile_arrays2._
 
@@ -64,11 +67,6 @@
   (beginning ++ instructions ++ ending).replace("XXX", class_name)
 }
 
-// automating the above
-
-// pre-2.5.0 ammonite 
-// import ammonite.ops._
-
 // post 2.5.0 ammonite
 import os._
 
diff -r 34b3aeb65fbe -r fddf099a82f8 slides/slides08.pdf
Binary file slides/slides08.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 slides/slides09.pdf
Binary file slides/slides09.pdf has changed
diff -r 34b3aeb65fbe -r fddf099a82f8 slides/slides09.tex
--- a/slides/slides09.tex	Tue Nov 28 11:45:48 2023 +0000
+++ b/slides/slides09.tex	Sat Dec 02 21:37:04 2023 +0000
@@ -5,10 +5,23 @@
 \usepackage{../data}
 \usepackage{../graphicss}
 \usepackage{../grammar}
-\usepackage{soul}
-\usepackage{mathpartir}
+%\usepackage{soul}
+%\usepackage{mathpartir}
 \usetikzlibrary{shapes,arrows,shadows}
 
+\usepackage[most]{tcolorbox}
+
+\newtcbox{\hl}[1][]{%
+     size=fbox,
+    tcbox raise base, nobeforeafter, 
+    enhanced, colframe=gray,
+    colback=gray!30, boxrule=1pt,
+    fontupper=\ttfamily,
+    #1}
+
+
+
+
 % beamer stuff
 \renewcommand{\slidecaption}{CFL 09, King's College London}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
@@ -78,33 +91,80 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c, fragile]
-\frametitle{Stack Estimation}
-\small
-\mbox{}\\[-15mm]
+%\begin{frame}[c, fragile]
+%\frametitle{Stack Estimation}
+%\small
+%\mbox{}\\[-15mm]%
+%
+%\bl{\begin{center}
+%\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+%$\textit{estimate}(n)$ & $\dn$ & $1$\\
+%$\textit{estimate}(x)$ & $\dn$ & $1$\\
+%$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
+%$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+%$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & 
+%$\textit{estimate}(b) +$\\ 
+%& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+%$\textit{estimate}(\pcode{write}(e))$ & $\dn$ & 
+%$\textit{estimate}(e) + 1$\\
+%$\textit{estimate}(e_1 ; e_2)$ & $\dn$ & 
+%$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+%$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & 
+%$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
+%$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
+%$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+%\end{tabular}
+%\end{center}}
+
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+\begin{frame}[c,fragile]
+\frametitle{\mbox{}\hspace{5cm}Factorial}
 
-\bl{\begin{center}
-\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
-$\textit{estimate}(n)$ & $\dn$ & $1$\\
-$\textit{estimate}(x)$ & $\dn$ & $1$\\
-$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
-$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
-$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ & 
-$\textit{estimate}(b) +$\\ 
-& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
-$\textit{estimate}(\pcode{write}(e))$ & $\dn$ & 
-$\textit{estimate}(e) + 1$\\
-$\textit{estimate}(e_1 ; e_2)$ & $\dn$ & 
-$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
-$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ & 
-$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
-$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
-$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
-\end{tabular}
-\end{center}}
+\begin{textblock}{7}(0,1.6)\footnotesize
+\begin{minipage}{6cm}
+\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
+.method public static fact(I)I
+.limit locals 1
+.limit stack 6
+   iload 0
+   ldc 0
+   if_icmpne If_else_0
+   ldc 1
+   goto If_end_1
+If_else_0:
+   iload 0
+   iload 0
+   ldc 1
+   isub
+   invokestatic fact/fact/fact(I)I
+   imul
+If_end_1:
+   ireturn
+.end method
+\end{lstlisting}
+\end{minipage}
+\end{textblock}
+
+\begin{textblock}{7}(6,7)
+\begin{bubble}[7cm]\small
+\begin{lstlisting}[language=Lisp,
+                   basicstyle=\ttfamily, 
+                   numbers=none,
+                   xleftmargin=1mm,linebackgroundcolor=\color{cream}]
+def fact(n) = 
+  if n == 0 then 1 
+  else n * fact(n - 1)
+\end{lstlisting}
+\end{bubble}
+\end{textblock}
 
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 
@@ -148,7 +208,7 @@
                    xleftmargin=1mm,linebackgroundcolor=\color{cream}]
 def facT(n, acc) = 
   if n == 0 then acc 
-  else facT(n - 1, n * acc);
+  else facT(n - 1, n * acc)
 \end{lstlisting}
 \end{bubble}
 \end{textblock}
@@ -159,7 +219,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[fragile]
 
-\begin{textblock}{7}(1,-0.2)\footnotesize
+\begin{textblock}{7}(1,-0.38)\footnotesize
 \begin{minipage}{6cm}
 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none, escapeinside={(*@}{@*)}]
 .method public static facT(II)I 
@@ -263,6 +323,40 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{???}
+
+\small
+\begin{tabular}{cc}
+  \includegraphics[scale=0.2]{basic-code.jpg} &
+  \includegraphics[scale=0.2]{machine-code.jpg}                                
+\end{tabular}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Opcodes}
+
+\small
+\begin{tabular}{cc}
+  \includegraphics[scale=0.3]{machine-code-large.png}      
+\end{tabular}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}<1-2>[t]
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c,fragile]
 \frametitle{Peephole Optimisations}