afl-material: changeset 864:b5b1bc0a603b

--- a/slides/slides09.tex	Tue Dec 14 11:40:31 2021 +0000
+++ b/slides/slides09.tex	Wed Dec 15 19:00:01 2021 +0000
@@ -58,7 +58,7 @@
 
 \footnotesize
 \begin{textblock}{13}(0.9,3)
-\begin{lstlisting}[]numbers=none]
+\begin{lstlisting}[numbers=none]
 def fib(n) = if n == 0 then 0 
              else if n == 1 then 1 
              else fib(n - 1) + fib(n - 2);

Binary file slides/slides10.pdf has changed

--- a/slides/slides10.tex	Tue Dec 14 11:40:31 2021 +0000
+++ b/slides/slides10.tex	Wed Dec 15 19:00:01 2021 +0000
@@ -73,7 +73,48 @@
     \end{tikzpicture}
   \end{center}
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\tikzstyle{sensor}=[draw, fill=blue!20, text width=3.8em, line width=1mm,
+    text centered, minimum height=2em,drop shadow]
+\tikzstyle{ann} = [above, text width=4em, text centered]
+\tikzstyle{sc} = [sensor, text width=7em, fill=red!20, 
+    minimum height=6em, rounded corners, drop shadow,line width=1mm]
+
+\begin{frame}[fragile,c]
+\frametitle{LLVM: Overview}
+
+\begin{tikzpicture}
+    % Validation Layer is the same except that there are a set of nodes and links which are added
+   
+    \path (0,0) node (IR) [sc] {\textbf{LLVM-IR}\\ Optimisations};
+    \path (IR.west)+(-2.2,1.7) node (sou1) [sensor] {C++};
+    \path (IR.west)+(-2.2,0.5) node (sou2)[sensor] {C};
+    \path (IR.west)+(-2.2,-1.0) node (dots)[ann] {$\vdots$}; 
+    \path (IR.west)+(-2.2,-1.8) node (sou3)[sensor] {Haskell};    
+
+    \path [draw,->,line width=1mm] (sou1.east) -- node [above] {} (IR.160);
+    \path [draw,->,line width=1mm] (sou2.east) -- node [above] {} (IR.180);
+    \path [draw,->,line width=1mm] (sou3.east) -- node [above] {} (IR.200);
+
+    \path (IR.east)+(2.2,2.0)  node (tar1)[sensor] {x86};
+    \path (IR.east)+(2.2,0.8)  node (tar2)[sensor] {ARM};
+    \path (IR.east)+(2.2,-0.4) node (tar3)[sensor] {MIPS}; 
+    \path (IR.east)+(2.2,-1.6) node (tar4)[sensor] {RISC}; 
+    \path (IR.east)+(2.2,-2.8) node (tar5)[sensor] {Power PC};
+    \path (IR.east)+(2.2,-4.2) node (dots2)[ann] {$\vdots$};
+
+    \path [draw,<-,line width=1mm] (tar1.west) -- node [above] {} (IR.10);
+    \path [draw,<-,line width=1mm] (tar2.west) -- node [above] {} (IR.5);
+    \path [draw,<-,line width=1mm] (tar3.west) -- node [above] {} (IR.0);
+    \path [draw,<-,line width=1mm] (tar4.west) -- node [above] {} (IR.-5);
+    \path [draw,<-,line width=1mm] (tar5.west) -- node [above] {} (IR.-10);
+    
+\end{tikzpicture}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[c,fragile]
@@ -99,7 +140,7 @@
 
 \mbox{}\bigskip\bigskip\bigskip
 
-\begin{lstlisting}[language={},numbers=left]
+\begin{lstlisting}[language=llvm,numbers=left]
 define i32 @fact (i32 %n) {
    %tmp_20 = icmp eq i32  %n, 0
    br i1 %tmp_20, label %if_branch_24, label %else_branch_25
@@ -119,6 +160,31 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{LLVM Types}
+
+\tt
+\begin{center}
+\begin{tabular}{ll}
+boolean & i1 \\
+byte    & i8 \\
+short   & i16\\
+char    & i16\\
+integer & i32\\
+long    & i64\\
+float   & float\\
+double  & double\\
+*\_      & pointer to \\
+**\_     & pointer to a pointer to\\
+\mbox{}[\_]    & arrays of\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[c,fragile]
 
@@ -137,6 +203,134 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{Abstract Syntax Trees}
+\footnotesize
+
+\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
+// 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  
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{K-(Intermediate)Language}
+\footnotesize
+
+\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-3mm]
+abstract class KExp
+abstract class KVal
+
+// K-Values
+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
+
+// K-Expressions
+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}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{KLet}
+
+\begin{lstlisting}[language=LLVM]
+tmp0 = add 1 a   
+tmp1 = mul b 5 
+tmp2 = add 3 tmp1 
+tmp3 = add tmp0 tmp2  
+\end{lstlisting}
+
+\begin{lstlisting}[language=LLVMIR]
+  KLet tmp0 , add 1 a in  
+   KLet tmp1 , mul b 5 in
+    KLet tmp2 , add 3 tmp1 in 
+     KLet tmp3 , add tmp0 tmp2 in
+      ...
+\end{lstlisting}
+
+\begin{lstlisting}[language=Scala,numbers=none]
+case class KLet(x: String, e1: KVal, e2: KExp)
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{KLet}
+
+\begin{lstlisting}[language=LLVM]
+tmp0 = add 1 a   
+tmp1 = mul b 5 
+tmp2 = add 3 tmp1 
+tmp3 = add tmp0 tmp2  
+\end{lstlisting}
+
+\begin{lstlisting}[language=LLVMIR]
+  let tmp0 = add 1 a in  
+   let tmp1 = mul b 5 in
+    let tmp2 = add 3 tmp1 in 
+     let tmp3 = add tmp0 tmp2 in
+      ...
+\end{lstlisting}
+
+\begin{lstlisting}[language=Scala,numbers=none]
+case class KLet(x: String, e1: KVal, e2: KExp)
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[fragile,c]
+\frametitle{CPS-Translation}
+\small
+
+\begin{lstlisting}[language=Scala,numbers=none]
+def CPS(e: Exp)(k: KVal => KExp) : KExp = 
+  e match { ... }
+\end{lstlisting}
+\bigskip\bigskip
+
+the continuation \texttt{k} can be thought of:\medskip
+
+\small
+\begin{lstlisting}[language=LLVMIR,numbers=none,xleftmargin=30mm,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
+  KReturn tmp3 
+\end{lstlisting}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 \begin{frame}[c,fragile]
 
@@ -710,7 +904,11 @@
 
   \end{frame}}
   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-  
+
+\begin{frame}<1-20>[c]
+\end{frame}
+
+
 \end{document}
 
 %%% Local Variables:

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw1/matcher.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,325 @@
+// CW1
+
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+
+// extended Rexps
+case class RANGE(s: Set[Char]) extends Rexp
+case class PLUS(r: Rexp) extends Rexp
+case class OPTIONAL(r: Rexp) extends Rexp
+case class NTIMES(r: Rexp, n: Int) extends Rexp 
+case class UPTO(r: Rexp, n: Int) extends Rexp
+case class FROM(r: Rexp, n: Int) extends Rexp
+case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp
+case class NOT(r: Rexp) extends Rexp
+
+// functions
+case class CFUN(f: Char => Boolean) extends Rexp
+
+// abbreviations
+def FCHAR(c: Char) = CFUN((a: Char) => a == c)
+def FSET(s: Set[Char]) = CFUN((a: Char) => s.contains(a))
+val FALL = CFUN(_ => true)
+
+def nullable (r: Rexp) : Boolean = r match {
+  case ZERO => false
+  case ONE => true
+  case CHAR(_) => false
+  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case STAR(_) => true
+
+  case RANGE(_) => false 
+  case PLUS(r1) => nullable(r1)
+  case OPTIONAL(_) => true
+  case NTIMES(r1, i) => if (i == 0) true else nullable(r1)
+  case UPTO(_, _) => true
+  case FROM(r1, i) => if (i == 0) true else nullable(r1)
+  case BETWEEN(r1, i, _) => if (i == 0) true else nullable(r1)
+  case NOT(r1) => !nullable(r1)
+
+  case CFUN(f) => false
+}
+
+
+def der (c: Char, r: Rexp) : Rexp = r match {
+  case ZERO => ZERO
+  case ONE => ZERO
+  case CHAR(d) => if (c == d) ONE else ZERO
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r1) => SEQ(der(c, r1), STAR(r1))
+
+  case RANGE(s) =>
+    if (s.contains(c)) ONE else ZERO 
+  case PLUS(r1) => SEQ(der(c, r1), STAR(r1))
+  case OPTIONAL(r1) => der(c, r1)
+  case NTIMES(r, i) => 
+    if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+  case UPTO(r1, i) => 
+    if (i == 0) ZERO else SEQ(der(c, r1), UPTO(r1, i - 1)) 
+  case FROM(r1, i) =>
+    if (i == 0) SEQ(der(c, r1), FROM(r1, 0)) else
+    SEQ(der(c, r1), FROM(r1, i - 1))
+  case BETWEEN(r1, i, j) => 
+    if (i == 0) {
+      if (j == 0) ZERO else SEQ(der(c, r1), BETWEEN(r1, 0, j - 1))
+    } else SEQ(der(c, r1), BETWEEN(r1, i - 1, j - 1))
+  case NOT(r1) => NOT(der(c, r1))
+
+  case CFUN(f) => if (f(c)) ONE else ZERO
+}
+
+
+def simp(r: Rexp) : Rexp = r match {
+  case ALT(r1, r2) => (simp(r1), simp(r2)) match {
+    case (ZERO, r2s) => r2s
+    case (r1s, ZERO) => r1s
+    case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+  }
+  case SEQ(r1, r2) =>  (simp(r1), simp(r2)) match {
+    case (ZERO, _) => ZERO
+    case (_, ZERO) => ZERO
+    case (ONE, r2s) => r2s
+    case (r1s, ONE) => r1s
+    case (r1s, r2s) => SEQ(r1s, r2s)
+  }
+  case r => r
+}
+
+def ders(s: List[Char], r: Rexp) : Rexp = s match {
+  case Nil => r
+  case c::s => ders(s, simp(der(c, r)))
+}
+
+def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
+
+
+
+val Regex31 = NTIMES(CHAR('a'),3)
+val Regex32 = NTIMES(OPTIONAL(CHAR('a')),3)
+val Regex33 = UPTO(CHAR('a'),3)
+val Regex34 = UPTO(OPTIONAL(CHAR('a')),3)
+val Regex35 = BETWEEN(CHAR('a'),3,5)
+val Regex36 = BETWEEN(OPTIONAL(CHAR('a')),3,5)
+val string31 = ""
+val string32 = "a"
+val string33 = "aa"
+val string34 = "aaa"
+val string35 = "aaaa"
+val string36 = "aaaaa"
+val string37 = "aaaaaa"
+
+
+println("Question3")
+println(matcher(Regex31, string31))
+println(matcher(Regex31, string32))
+println(matcher(Regex31, string33))
+println(matcher(Regex31, string34))
+println(matcher(Regex31, string35))
+println(matcher(Regex31, string36))
+println(matcher(Regex31, string37)); println("")
+println(matcher(Regex32, string31))
+println(matcher(Regex32, string32))
+println(matcher(Regex32, string33))
+println(matcher(Regex32, string34))
+println(matcher(Regex32, string35))
+println(matcher(Regex32, string36))
+println(matcher(Regex32, string37)); println("")
+println(matcher(Regex33, string31))
+println(matcher(Regex33, string32))
+println(matcher(Regex33, string33))
+println(matcher(Regex33, string34))
+println(matcher(Regex33, string35))
+println(matcher(Regex33, string36))
+println(matcher(Regex33, string37)); println("")
+println(matcher(Regex34, string31))
+println(matcher(Regex34, string32))
+println(matcher(Regex34, string33))
+println(matcher(Regex34, string34))
+println(matcher(Regex34, string35))
+println(matcher(Regex34, string36))
+println(matcher(Regex34, string37)); println("")
+println(matcher(Regex35, string31))
+println(matcher(Regex35, string32))
+println(matcher(Regex35, string33))
+println(matcher(Regex35, string34))
+println(matcher(Regex35, string35))
+println(matcher(Regex35, string36))
+println(matcher(Regex35, string37)); println("")
+println(matcher(Regex36, string31))
+println(matcher(Regex36, string32))
+println(matcher(Regex36, string33))
+println(matcher(Regex36, string34))
+println(matcher(Regex36, string35))
+println(matcher(Regex36, string36))
+println(matcher(Regex36, string37)); println("")
+
+
+val RegexX = BETWEEN(CHAR('a'), 0, 5)
+val stringX = ""
+println(matcher(RegexX, stringX))
+
+
+
+val str0 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val str1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val str2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+
+val matchA = (c:Char) => c == 'a'
+
+val reg_1 = SEQ(SEQ(CFUN(matchA), CFUN(matchA)), CFUN(matchA))
+val reg_2 = SEQ(NTIMES(CFUN(matchA), 19), OPTIONAL(CFUN(matchA)))
+
+val reg_1_mod = PLUS(PLUS(reg_1))
+val reg_2_mod = PLUS(PLUS(reg_2))
+
+
+matcher(reg_1_mod, str0)
+matcher(reg_1_mod, str1)
+matcher(reg_1_mod, str2)
+matcher(reg_2_mod, str0)
+matcher(reg_2_mod, str1)
+matcher(reg_2_mod, str2)
+
+
+
+
+
+//Q3: matcher test (table)
+
+// a^{3}
+val re1 = NTIMES(CHAR('a'), 3)
+
+matcher(re1, "")        //false
+matcher(re1, "a")       //false
+matcher(re1, "aa")      //false
+matcher(re1, "aaa")     //true
+matcher(re1, "aaaaa")   //false
+matcher(re1, "aaaaaa")  //false
+
+// (a?)^{3}
+val re2 = NTIMES(OPTIONAL(CHAR('a')), 3)
+
+matcher(re2, "")        //true
+matcher(re2, "a")       //true
+matcher(re2, "aa")      //true
+matcher(re2, "aaa")     //true
+matcher(re2, "aaaaa")   //false
+matcher(re2, "aaaaaa")  //false
+
+// (a)^{..3}
+val re3 = UPTO((CHAR('a')), 3)
+
+matcher(re3, "")        //true
+matcher(re3, "a")       //true
+matcher(re3, "aa")      //true
+matcher(re3, "aaa")     //true
+matcher(re3, "aaaaa")   //false
+matcher(re3, "aaaaaa")  //false
+
+// (a?)^{..3}
+val re4 = UPTO(OPTIONAL(CHAR('a')), 3)
+
+matcher(re4, "")        //true
+matcher(re4, "a")       //true
+matcher(re4, "aa")      //true
+matcher(re4, "aaa")     //true
+matcher(re4, "aaaaa")   //false
+matcher(re4, "aaaaaa")  //false
+
+// (a)^{3..5}
+val re5 = BETWEEN(CHAR('a'), 3, 5)
+
+matcher(re5, "")        //false
+matcher(re5, "a")       //false
+matcher(re5, "aa")      //false
+matcher(re5, "aaa")     //true
+matcher(re5, "aaaaa")   //true
+matcher(re5, "aaaaaa")  //false
+
+// (a?)^{3..5}
+val re6 = BETWEEN(OPTIONAL(CHAR('a')), 3, 5)
+
+matcher(re6, "")        //true
+matcher(re6, "a")       //true
+matcher(re6, "aa")      //true
+matcher(re6, "aaa")     //true
+matcher(re6, "aaaaa")   //true
+matcher(re6, "aaaaaa")  //false
+
+//Q5: regular expression for email addresses
+
+val alphaNum = ('a' to 'z').toSet ++ ('0' to '9')
+val Q5email = SEQ(
+                PLUS(RANGE(alphaNum + '_' + '-' + '.')), 
+                SEQ(
+                    CHAR('@'), 
+                    SEQ(
+                        PLUS(RANGE(alphaNum + '-' + '.')), 
+                        SEQ(
+                            CHAR('.'), 
+                            BETWEEN(RANGE(('a' to 'z').toSet + '.'), 2, 6)
+                            )
+                      )
+                )
+              )
+
+ders("nicolas.volken@kcl.ac.uk".toList, Q5email)
+
+// Q6
+val Q6 = SEQ(CHAR('/'),
+            SEQ(CHAR('*'),
+                SEQ(
+                  
+                    NOT(
+                      SEQ(
+                        STAR(FALL),
+                        SEQ(
+                          CHAR('*'),
+                          SEQ(
+                            CHAR('/'),
+                            STAR(FALL)
+                          )
+                        )
+                      )
+                    )
+                  
+                    ,
+                    SEQ(CHAR('*'),
+                    CHAR('/')
+                    )
+                )
+            )
+        )
+
+matcher(Q6, "/**/")
+matcher(Q6, "/*foobar*/")
+matcher(Q6, "/*test*/test*/")
+matcher(Q6, "/*test/*test*/")
+
+// Q7
+
+val Q7r1 = SEQ(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))
+val Q7r2 = SEQ(BETWEEN(CHAR('a'), 19, 19), OPTIONAL(CHAR('a')))
+
+val Q7str5 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val Q7str6 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val Q7str7 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+
+matcher(PLUS(PLUS(Q7r1)), Q7str5)
+matcher(PLUS(PLUS(Q7r2)), Q7str5)
+
+matcher(PLUS(PLUS(Q7r1)), Q7str6)
+matcher(PLUS(PLUS(Q7r2)), Q7str6)
+
+matcher(PLUS(PLUS(Q7r1)), Q7str7)
+matcher(PLUS(PLUS(Q7r2)), Q7str7)
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/collatz.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,8 @@
+write "Input a number ";
+read n;
+while n > 1 do {
+  if n % 2 == 0 
+  then n := n / 2 
+  else n := 3 * n + 1;
+};
+write "Yes\n";

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/collatz2.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,27 @@
+// Collatz series
+//
+// needs writing of strings and numbers; comments
+
+bnd := 1;
+while bnd < 101 do {
+  write bnd;
+  write ": ";
+  n := bnd;
+  cnt := 0;
+
+  while n > 1 do {
+    write n;
+    write ",";
+    
+    if n % 2 == 0 
+    then n := n / 2 
+    else n := 3 * n+1;
+
+    cnt := cnt + 1
+  };
+
+  write " => ";
+  write cnt;
+  write "\n";
+  bnd := bnd + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/factors.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,14 @@
+// Find all factors of a given input number
+// by J.R. Cordy August 2005
+
+write "Input n please";
+read n;
+write "The factors of n are\n";
+f := 2;
+while n != 1 do {
+    while (n / f) * f == n do {
+        write f; write "\n";
+        n := n / f
+    };
+    f := f + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/fib.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,13 @@
+write "Fib";
+read n;  
+minus1 := 1;
+minus2 := 0;
+while n > 0 do {
+       temp := minus2;
+       minus2 := minus1 + minus2;
+       minus1 := temp;
+       n := n - 1
+};
+write "Result: ";
+write minus2 
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/lexer.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,337 @@
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls
+
+// Rexp
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+case class RECD(x: String, r: Rexp) extends Rexp
+
+case class RANGE(s: Set[Char]) extends Rexp
+case class PLUS(r: Rexp) extends Rexp
+case class OPTIONAL(r: Rexp) extends Rexp
+case class NTIMES(r: Rexp, n: Int) extends Rexp 
+
+// Values
+abstract class Val
+case object Empty extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case class Rec(x: String, v: Val) extends Val
+
+
+// Convenience typing
+def charlist2rexp(s : List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+implicit def string2rexp(s : String) : Rexp = 
+  charlist2rexp(s.toList)
+
+implicit def RexpOps(r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps(s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+  def $ (r: Rexp) = RECD(s, r)
+}
+
+// nullable
+def nullable(r: Rexp) : Boolean = r match {
+  case ZERO => false
+  case ONE => true
+  case CHAR(_) => false
+  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case STAR(_) => true
+
+  case RECD(_, r1) => nullable(r1)
+  case RANGE(_) => false
+  case PLUS(r1) => nullable(r1)
+  case OPTIONAL(_) => true
+  case NTIMES(r1, i) => if (i == 0) true else nullable(r1)
+}
+
+// der
+def der(c: Char, r: Rexp) : Rexp = r match {
+  case ZERO => ZERO
+  case ONE => ZERO
+  case CHAR(d) => if (c == d) ONE else ZERO
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r) => SEQ(der(c, r), STAR(r))
+
+  case RECD(_, r1) => der(c, r1)
+  case RANGE(s) => if (s.contains(c)) ONE else ZERO 
+  case PLUS(r1) => SEQ(der(c, r1), STAR(r1))
+  case OPTIONAL(r1) => der(c, r1)
+  case NTIMES(r, i) => 
+    if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+}
+
+// Flatten
+def flatten(v: Val) : String = v match {
+  case Empty => ""
+  case Chr(c) => c.toString
+  case Left(v) => flatten(v)
+  case Right(v) => flatten(v)
+  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+  case Stars(vs) => vs.map(flatten).mkString
+  case Rec(_, v) => flatten(v)
+}
+
+// Env
+def env(v: Val) : List[(String, String)] = v match {
+  case Empty => Nil
+  case Chr(c) => Nil
+  case Left(v) => env(v)
+  case Right(v) => env(v)
+  case Sequ(v1, v2) => env(v1) ::: env(v2)
+  case Stars(vs) => vs.flatMap(env)
+  case Rec(x, v) => (x, flatten(v))::env(v)
+}
+
+// Mkeps
+def mkeps(r: Rexp) : Val = r match {
+  case ONE => Empty
+  case ALT(r1, r2) => 
+    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+  case STAR(r) => Stars(Nil)
+  case RECD(x, r) => Rec(x, mkeps(r))
+
+  case PLUS(r) => Stars(List(mkeps(r)))   // the first copy must match the empty string
+  case OPTIONAL(r) => if (nullable(r)) Stars(List(mkeps(r))) else Stars(Nil)
+  case NTIMES(r, i) => Stars(List.fill(i)(mkeps(r)))
+}
+
+// Inj
+def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+  case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+  case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+  case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+  case (CHAR(d), Empty) => Chr(c) 
+  case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+
+  case (RANGE(_), Empty) => Chr(c)
+  case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (OPTIONAL(r), v1) => Stars(List(inj(r, c, v1)))
+  case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+}
+
+// Rectification functions
+def F_ID(v: Val): Val = v
+def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
+def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
+def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Right(v) => Right(f2(v))
+  case Left(v) => Left(f1(v))
+}
+def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
+}
+def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(Empty), f2(v))
+def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(v), f2(Empty))
+def F_RECD(f: Val => Val) = (v:Val) => v match {
+  case Rec(x, v) => Rec(x, f(v))
+}
+def F_ERROR(v: Val): Val = throw new Exception("error")
+
+// Simp
+def simp(r: Rexp): (Rexp, Val => Val) = r match {
+  case ALT(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (r2s, F_RIGHT(f2s))
+      case (_, ZERO) => (r1s, F_LEFT(f1s))
+      case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
+                else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
+    }
+  }
+  case SEQ(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (ZERO, F_ERROR)
+      case (_, ZERO) => (ZERO, F_ERROR)
+      case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
+      case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
+      case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
+    }
+  }
+  case r => (r, F_ID)
+}
+
+// Lex
+def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else 
+    { throw new Exception("lexing error") } 
+  case c::cs => {
+    val (r_simp, f_simp) = simp(der(c, r))
+    inj(r, c, f_simp(lex_simp(r_simp, cs)))
+  }
+}
+
+def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))
+
+// Language specific code
+val KEYWORD : Rexp = "while" | "if" | "then" | "else" | "do" | "for" | "to" | "true" | "false" | "read" | "write" | "skip" 
+val OP : Rexp = "+" | "-" | "*" | "%" | "/" | "==" | "!=" | ">" | "<" | ">=" | "<=" | ":=" | "&&" | "||"
+val LET: Rexp = RANGE(('A' to 'Z').toSet ++ ('a' to 'z'))
+val SYM : Rexp = LET | RANGE(Set('.', '_', '>', '<', '=', ';', ',', ':', ')', '('))
+val PARENS : Rexp = "(" | "{" | ")" | "}"
+val SEMI : Rexp = ";"
+val WHITESPACE : Rexp = PLUS(" ") | "\n" | "\t" | "\r"
+val DIGIT : Rexp = RANGE(('0' to '9').toSet)
+val DIGIT1 : Rexp = RANGE(('1' to '9').toSet)
+val STRING : Rexp = "\"" ~ (SYM | " " | "\\n" | DIGIT).% ~ "\""
+val ID : Rexp = LET ~ (LET | "_" | DIGIT).%
+val NUM : Rexp = "0" | (DIGIT1 ~ DIGIT.%)
+val COMMENT : Rexp = "//" ~ (SYM | " " | DIGIT).% ~ ("\n" | "\r\n") 
+
+val WHILE_REGS = (("k" $ KEYWORD) | 
+                  ("o" $ OP) | 
+                  ("str" $ STRING) |
+                  ("p" $ PARENS) |
+                  ("s" $ SEMI) | 
+                  ("w" $ WHITESPACE) | 
+                  ("i" $ ID) | 
+                  ("n" $ NUM) |
+		  ("c" $ COMMENT)).%
+
+def esc(raw: String): String = {
+  import scala.reflect.runtime.universe._
+  Literal(Constant(raw)).toString
+}
+
+def escape(tks: List[(String, String)]) =
+  tks.map{ case (s1, s2) => (s1, esc(s2))}
+
+// Token
+abstract class Token extends Serializable 
+case class T_KEYWORD(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_STRING(s: String) extends Token
+case class T_PAREN(s: String) extends Token
+case object T_SEMI extends Token
+case class T_ID(s: String) extends Token
+case class T_NUM(n: Int) extends Token
+
+val token : PartialFunction[(String, String), Token] = {
+  case ("k", s) => T_KEYWORD(s)
+  case ("o", s) => T_OP(s)
+  case ("str", s) => T_STRING(s)
+  case ("p", s) => T_PAREN(s)
+  case ("s", _) => T_SEMI
+  case ("i", s) => T_ID(s)
+  case ("n", s) => T_NUM(s.toInt)
+}
+
+// Tokenise
+def tokenise(s: String) : List[Token] = 
+  lexing_simp(WHILE_REGS, s).collect(token)
+
+
+// Q2 Tests
+lex_simp(NTIMES("a", 3), "aaa".toList)
+lex_simp(NTIMES(("a" | ONE), 3), "aa".toList)
+
+// Q3 Programs
+
+val prog1 = """write "Fib";
+read n;
+minus1 := 0;
+minus2 := 1;
+while n > 0 do {
+temp := minus2;
+minus2 := minus1 + minus2;
+minus1 := temp;
+n := n - 1
+};
+write "Result";
+write minus2"""
+
+val prog2 = """start := 1000;
+x := start;
+y := start;
+z := start;
+while 0 < x do {
+while 0 < y do {
+while 0 < z do { z := z - 1 };
+z := start;
+y := y - 1
+};
+y := start;
+x := x - 1
+}"""
+
+val prog3 = """write "Input n please";
+read n;
+write "The factors of n are";
+f := 2;
+while n != 1 do {
+while (n / f) * f == n do {
+write f;
+n := n / f
+};
+f := f + 1
+}"""
+
+println(tokenise(prog1))
+println(tokenise(prog2))
+println(tokenise(prog3))
+
+
+println("MY TESTS")
+
+println(lex_simp("x" $ OPTIONAL("a"), "a".toList))
+println(lex_simp("x" $ OPTIONAL("a"), "".toList))
+println(lex_simp("x" $ NTIMES(OPTIONAL("a"),4), "aa".toList))
+println(lex_simp("x" $ OPTIONAL("aa"), "aa".toList))
+println(lex_simp("x" $ OPTIONAL("aa"), "".toList))
+
+
+
+
+//===================
+println("Fib")
+println(tokenise(os.read(os.pwd / "fib.while")))
+
+println("Factors")
+println(tokenise(os.read(os.pwd / "factors.while")))
+
+println("Loops")
+println(tokenise(os.read(os.pwd / "loops.while")))
+
+println("Collatz")
+println(tokenise(os.read(os.pwd / "collatz.while")))
+
+println("Collatz 2")
+println(tokenise(os.read(os.pwd / "collatz2.while")))
+
+println("Primes")
+println(tokenise(os.read(os.pwd / "primes.while")))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/loops.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,14 @@
+start := 1000; 
+x := start;
+y := start;
+z := start;
+while 0 < x do {
+ while 0 < y do {
+  while 0 < z do { z := z - 1 };
+  z := start;
+  y := y - 1
+ };     
+ y := start;
+ x := x - 1
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw2/primes.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,15 @@
+// prints out prime numbers from
+// 2 to 100 (end)
+
+end := 100;
+n := 2;
+while (n < end) do {
+  f := 2;
+  tmp := 0;
+  while ((f < n / 2 + 1) && (tmp == 0)) do {
+    if ((n / f) * f == n) then  { tmp := 1 } else { skip };
+    f := f + 1
+  };
+  if (tmp == 0) then { write(n); write("\n") } else { skip };
+  n  := n + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/collatz.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,8 @@
+write "Input a number ";
+read n;
+while n > 1 do {
+  if n % 2 == 0 
+  then n := n/2 
+  else n := 3*n+1;
+};
+write "Yes\n";

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/collatz2.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,27 @@
+// Collatz series
+//
+// needs writing of strings and numbers; comments
+
+bnd := 1;
+while bnd < 101 do {
+  write bnd;
+  write ": ";
+  n := bnd;
+  cnt := 0;
+
+  while n > 1 do {
+    write n;
+    write ",";
+    
+    if n % 2 == 0 
+    then n := n / 2 
+    else n := 3 * n+1;
+
+    cnt := cnt + 1
+  };
+
+  write " => ";
+  write cnt;
+  write "\n";
+  bnd := bnd + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/factors.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,14 @@
+// Find all factors of a given input number
+// by J.R. Cordy August 2005
+
+write "Input n please";
+read n;
+write "The factors of n are:\n";
+f := 2;
+while n != 1 do {
+    while (n / f) * f == n do {
+        write f; write "\n";
+        n := n / f
+    };
+    f := f + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/fib.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,13 @@
+write "Fib: ";
+read n;  
+minus1 := 0;
+minus2 := 1;
+while n > 0 do {
+       temp := minus2;
+       minus2 := minus1 + minus2;
+       minus1 := temp;
+       n := n - 1
+};
+write "Result: ";
+write minus2 
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/lexer.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,250 @@
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls
+
+// Rexp
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+case class RECD(x: String, r: Rexp) extends Rexp
+
+case class RANGE(s: Set[Char]) extends Rexp
+case class PLUS(r: Rexp) extends Rexp
+case class OPTIONAL(r: Rexp) extends Rexp
+case class NTIMES(r: Rexp, n: Int) extends Rexp 
+
+// Values
+abstract class Val
+case object Empty extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case class Rec(x: String, v: Val) extends Val
+
+
+// Convenience typing
+def charlist2rexp(s : List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+implicit def string2rexp(s : String) : Rexp = 
+  charlist2rexp(s.toList)
+
+implicit def RexpOps(r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps(s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+  def $ (r: Rexp) = RECD(s, r)
+}
+
+// nullable
+def nullable(r: Rexp) : Boolean = r match {
+  case ZERO => false
+  case ONE => true
+  case CHAR(_) => false
+  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case STAR(_) => true
+
+  case RECD(_, r1) => nullable(r1)
+  case RANGE(_) => false
+  case PLUS(r1) => nullable(r1)
+  case OPTIONAL(_) => true
+  case NTIMES(r1, i) => if (i == 0) true else nullable(r1)
+}
+
+// der
+def der(c: Char, r: Rexp) : Rexp = r match {
+  case ZERO => ZERO
+  case ONE => ZERO
+  case CHAR(d) => if (c == d) ONE else ZERO
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r) => SEQ(der(c, r), STAR(r))
+
+  case RECD(_, r1) => der(c, r1)
+  case RANGE(s) => if (s.contains(c)) ONE else ZERO 
+  case PLUS(r1) => SEQ(der(c, r1), STAR(r1))
+  case OPTIONAL(r1) => ALT(der(c, r1), ZERO)
+  case NTIMES(r, i) => 
+    if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+}
+
+// Flatten
+def flatten(v: Val) : String = v match {
+  case Empty => ""
+  case Chr(c) => c.toString
+  case Left(v) => flatten(v)
+  case Right(v) => flatten(v)
+  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+  case Stars(vs) => vs.map(flatten).mkString
+  case Rec(_, v) => flatten(v)
+}
+
+// Env
+def env(v: Val) : List[(String, String)] = v match {
+  case Empty => Nil
+  case Chr(c) => Nil
+  case Left(v) => env(v)
+  case Right(v) => env(v)
+  case Sequ(v1, v2) => env(v1) ::: env(v2)
+  case Stars(vs) => vs.flatMap(env)
+  case Rec(x, v) => (x, flatten(v))::env(v)
+}
+
+// Mkeps
+def mkeps(r: Rexp) : Val = r match {
+  case ONE => Empty
+  case ALT(r1, r2) => 
+    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+  case STAR(r) => Stars(Nil)
+  case RECD(x, r) => Rec(x, mkeps(r))
+
+  case PLUS(r) => Stars(List(mkeps(r)))   // the first copy must match the empty string
+  case OPTIONAL(r) => Right(Empty)
+  case NTIMES(r, i) => Stars(List.fill(i)(mkeps(r)))
+}
+
+// Inj
+def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+  case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+  case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+  case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+  case (CHAR(d), Empty) => Chr(c) 
+  case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+
+  case (RANGE(_), Empty) => Chr(c)
+  case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (OPTIONAL(r), Left(v1)) => Left(inj(r, c, v1))
+  case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+}
+
+// Rectification functions
+def F_ID(v: Val): Val = v
+def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
+def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
+def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Right(v) => Right(f2(v))
+  case Left(v) => Left(f1(v))
+}
+def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
+}
+def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(Empty), f2(v))
+def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(v), f2(Empty))
+def F_RECD(f: Val => Val) = (v:Val) => v match {
+  case Rec(x, v) => Rec(x, f(v))
+}
+def F_ERROR(v: Val): Val = throw new Exception("error")
+
+// Simp
+def simp(r: Rexp): (Rexp, Val => Val) = r match {
+  case ALT(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (r2s, F_RIGHT(f2s))
+      case (_, ZERO) => (r1s, F_LEFT(f1s))
+      case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
+                else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
+    }
+  }
+  case SEQ(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (ZERO, F_ERROR)
+      case (_, ZERO) => (ZERO, F_ERROR)
+      case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
+      case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
+      case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
+    }
+  }
+  case r => (r, F_ID)
+}
+
+// Lex
+def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else 
+    { throw new Exception("lexing error") } 
+  case c::cs => {
+    val (r_simp, f_simp) = simp(der(c, r))
+    inj(r, c, f_simp(lex_simp(r_simp, cs)))
+  }
+}
+
+def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))
+
+// Language specific code
+val KEYWORD : Rexp = "while" | "if" | "then" | "else" | "do" | "for" | "to" | "true" | "false" | "read" | "write" | "skip" 
+val OP : Rexp = "+" | "-" | "*" | "%" | "/" | "==" | "!=" | ">" | "<" | ">=" | "<=" | ":=" | "&&" | "||"
+val LET: Rexp = RANGE(('A' to 'Z').toSet ++ ('a' to 'z'))
+val SYM : Rexp = LET | RANGE(Set('.', '_', '>', '<', '=', ';', ',', ':'))
+val PARENS : Rexp = "(" | "{" | ")" | "}"
+val SEMI : Rexp = ";"
+val WHITESPACE : Rexp = PLUS(" ") | "\n" | "\t"
+val DIGIT : Rexp = RANGE(('0' to '9').toSet)
+val DIGIT1 : Rexp = RANGE(('1' to '9').toSet)
+val STRING : Rexp = "\"" ~ (SYM | " " | "\\n" | DIGIT).% ~ "\""
+val ID : Rexp = LET ~ (LET | "_" | DIGIT).%
+val NUM : Rexp = "0" | (DIGIT1 ~ DIGIT.%)
+val COMMENT : Rexp = "//" ~ (SYM | " " | DIGIT).% ~ "\n" 
+
+val WHILE_REGS = (("k" $ KEYWORD) | 
+                  ("o" $ OP) | 
+                  ("str" $ STRING) |
+                  ("p" $ PARENS) |
+                  ("s" $ SEMI) | 
+                  ("w" $ WHITESPACE) | 
+                  ("i" $ ID) | 
+                  ("n" $ NUM) |
+		  ("c" $ COMMENT)).%
+
+// Token
+abstract class Token extends Serializable 
+case class T_KEYWORD(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_STRING(s: String) extends Token
+case class T_PAREN(s: String) extends Token
+case object T_SEMI extends Token
+case class T_ID(s: String) extends Token
+case class T_NUM(n: Int) extends Token
+
+val token : PartialFunction[(String, String), Token] = {
+  case ("k", s) => T_KEYWORD(s)
+  case ("o", s) => T_OP(s)
+  case ("str", s) => T_STRING(s)
+  case ("p", s) => T_PAREN(s)
+  case ("s", _) => T_SEMI
+  case ("i", s) => T_ID(s)
+  case ("n", s) => T_NUM(s.toInt)
+}
+
+// Tokenise
+def tokenise(s: String) : List[Token] = 
+  lexing_simp(WHILE_REGS, s).collect(token)
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/loops.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,14 @@
+start := 1000; 
+x := start;
+y := start;
+z := start;
+while 0 < x do {
+ while 0 < y do {
+  while 0 < z do { z := z - 1 };
+  z := start;
+  y := y - 1
+ };     
+ y := start;
+ x := x - 1
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/parser.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,240 @@
+// CW3
+
+import $file.lexer
+import lexer._ 
+
+
+case class ~[+A, +B](_1: A, _2: B)
+type IsSeq[A] = A => Seq[_]
+
+abstract class Parser[I : IsSeq, T] {
+  def parse(ts: I): Set[(T, I)]
+
+  def parse_all(ts: I) : Set[T] =
+    for ((head, tail) <- parse(ts); if tail.isEmpty) yield head
+}
+
+class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] {
+  def parse(sb: I) = 
+    for ((head1, tail1) <- p.parse(sb); 
+         (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)
+}
+
+class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
+}
+
+class FunParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+  def parse(sb: I) = 
+    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
+}
+
+// New parser that takes as input a list of tokens
+case class TokenListParser(ts: List[Token]) extends Parser[List[Token], List[Token]] {
+    def parse(tsb: List[Token]) = {
+        val (prefix, suffix) = tsb.splitAt(ts.length)
+        if (prefix == ts) Set((prefix, suffix)) else Set()
+    }
+}
+
+// Implicit definitions to go from a token 
+// or a list of tokens to a TokenListParser
+implicit def token2parser(t: Token) = TokenListParser(List(t))
+implicit def tokenList2parser(ts: List[Token]) = TokenListParser(ts)
+
+implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
+  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
+  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
+  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
+}
+
+implicit def TokenOps(t: Token) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](List(t), q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](List(t), qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](List(t), f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](List(t), q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](List(t), qs)
+}
+
+implicit def TokenListOps(ts: List[Token]) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](ts, q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](ts, qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](ts, f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](ts, q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](ts, qs)
+}
+
+// Abstract Syntax Trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp
+
+type Block = List[Stmt]
+
+case object Skip extends Stmt
+case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
+case class While(b: BExp, bl: Block) extends Stmt
+case class Assign(s: String, a: AExp) extends Stmt
+case class Read(s: String) extends Stmt
+case class WriteId(s: String) extends Stmt  // for printing values of variables
+case class WriteString(s: String) extends Stmt  // for printing words
+
+case class Var(s: String) extends AExp
+case class Num(i: Int) extends AExp
+case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+
+case object True extends BExp
+case object False extends BExp
+case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+case class And(b1: BExp, b2: BExp) extends BExp
+case class Or(b1: BExp, b2: BExp) extends BExp
+
+case class IdParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_ID(id) :: rest => Set((id, rest))
+        case _ => Set()
+    }
+}
+
+case class NumParser() extends Parser[List[Token], Int] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_NUM(n) :: rest => Set((n, rest))
+        case _ => Set()
+    }
+}
+
+case class StringParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_STRING(s) :: rest => Set((s, rest))
+        case _ => Set()
+    }
+}
+
+// WHILE Language Parsing
+lazy val AExp: Parser[List[Token], AExp] = 
+  (Te ~ T_OP("+") ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z): AExp } ||
+  (Te ~ T_OP("-") ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z): AExp } || Te
+lazy val Te: Parser[List[Token], AExp] = 
+  (Fa ~ T_OP("*") ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z): AExp } || 
+  (Fa ~ T_OP("/") ~ Te) ==> { case x ~ _ ~ z => Aop("/", x, z): AExp } || 
+  (Fa ~ T_OP("%") ~ Te) ==> { case x ~ _ ~ z => Aop("%", x, z): AExp } || Fa  
+lazy val Fa: Parser[List[Token], AExp] = 
+   (T_PAREN("(") ~ AExp ~ T_PAREN(")")) ==> { case _ ~ y ~ _ => y } || 
+   IdParser() ==> Var  || 
+   NumParser() ==> Num
+
+lazy val BExp: Parser[List[Token], BExp] = 
+   (AExp ~ T_OP("==") ~ AExp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || 
+   (AExp ~ T_OP("!=") ~ AExp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || 
+   (AExp ~ T_OP("<") ~ AExp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || 
+   (AExp ~ T_OP(">") ~ AExp) ==> { case x ~ _ ~ z => Bop(">", x, z): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("&&")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => And(y, v): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("||")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => Or(y, v): BExp } ||
+   (T_KEYWORD("true") ==> (_ => True: BExp )) || 
+   (T_KEYWORD("false") ==> (_ => False: BExp )) ||
+   (T_PAREN("(") ~ BExp ~ T_PAREN(")")) ==> { case _ ~ x ~ _ => x }
+
+lazy val Stmt: Parser[List[Token], Stmt] =
+    T_KEYWORD("skip") ==> (_ => Skip: Stmt) ||
+    (IdParser() ~ T_OP(":=") ~ AExp) ==> { case id ~ _ ~ z => Assign(id, z): Stmt } ||
+    (T_KEYWORD("if") ~ BExp ~ T_KEYWORD("then") ~ Block ~ T_KEYWORD("else") ~ Block) ==> { case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } ||
+    (T_KEYWORD("while") ~ BExp ~ T_KEYWORD("do") ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) : Stmt } ||
+    (T_KEYWORD("read") ~ IdParser()) ==> { case _ ~ id => Read(id): Stmt} ||
+    (T_KEYWORD("write") ~ IdParser()) ==> { case _ ~ id => WriteId(id): Stmt} ||
+    (T_KEYWORD("write") ~ StringParser()) ==> { case _ ~ s => WriteString(s): Stmt}
+
+lazy val Stmts: Parser[List[Token], Block] =
+    (Stmt ~ T_SEMI ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } ||
+    (Stmt ==> (s => List(s) : Block))
+
+lazy val Block: Parser[List[Token], Block] =
+    (T_PAREN("{") ~ Stmts ~ T_PAREN("}")) ==> { case x ~ y ~ z => y} ||
+    (Stmt ==> (s => List(s)))
+
+// Testing with programs 2 & 3
+
+println("Fibonacci")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "fib.while"))))
+
+println("Loops")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))))
+
+println("Collatz")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))))
+
+
+// Interpreter
+
+// Environment to store values of variables
+type Env = Map[String, Int]
+
+def eval_aexp(a: AExp, env: Env) : Int = a match {
+  case Num(i) => i
+  case Var(s) => env(s)
+  case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
+  case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
+  case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
+  case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)
+  case Aop("%", a1, a2) => eval_aexp(a1, env) % eval_aexp(a2, env)
+}
+
+def eval_bexp(b: BExp, env: Env) : Boolean = b match {
+  case True => true
+  case False => false
+  case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
+  case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
+  case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
+  case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
+  case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)
+  case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)
+}
+
+// Import needed to take int as input from the user
+import scala.io.StdIn.readInt
+
+def eval_stmt(s: Stmt, env: Env) : Env = s match {
+  case Skip => env
+  case Assign(x, a) => env + (x -> eval_aexp(a, env))
+  case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
+  case While(b, bl) => 
+    if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
+    else env
+
+  case WriteId(x) => { print(env(x)) ; env }
+  case WriteString(x) => {
+        print(x.replaceAll("\"", "").replaceAll("""\\n""", "\n")) ;
+        env
+       }
+
+  case Read(x) => { 
+      println("Enter an integer and press ENTER:") ; 
+      val n = readInt() ; // Note: Does not work when using the REPL
+      eval_stmt(Assign(x, Num(n)), env) 
+  }
+}
+
+def eval_bl(bl: Block, env: Env) : Env = bl match {
+  case Nil => env
+  case s::bl => eval_bl(bl, eval_stmt(s, env))
+}
+
+def eval(bl: Block) : Env = eval_bl(bl, Map())
+
+println("Factors eval")
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "factors.while"))).head))
+
+println("Collatz2 eval")
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head))
+
+/*
+println("Loops eval")
+val start = System.nanoTime()
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))).head))
+val end = System.nanoTime()
+println("Time taken in seconds: ")
+println((end - start)/(1.0e9))
+*/

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/parser2.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,251 @@
+// CW3
+
+import $file.lexer
+import lexer._ 
+
+
+case class ~[+A, +B](_1: A, _2: B)
+type IsSeq[A] = A => Seq[_]
+
+abstract class Parser[I : IsSeq, T] {
+  def parse(ts: I): Set[(T, I)]
+
+  def parse_all(ts: I) : Set[T] =
+    for ((head, tail) <- parse(ts); if tail.isEmpty) yield head
+}
+
+class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] {
+  def parse(sb: I) = 
+    for ((head1, tail1) <- p.parse(sb); 
+         (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)
+}
+
+class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
+}
+
+class FunParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+  def parse(sb: I) = 
+    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
+}
+
+// New parser that takes as input a list of tokens
+case class TokenListParser(ts: List[Token]) extends Parser[List[Token], List[Token]] {
+    def parse(tsb: List[Token]) = {
+        val (prefix, suffix) = tsb.splitAt(ts.length)
+        if (prefix == ts) Set((prefix, suffix)) else Set()
+    }
+}
+
+// Implicit definitions to go from a token 
+// or a list of tokens to a TokenListParser
+implicit def token2parser(t: Token) = TokenListParser(List(t))
+implicit def tokenList2parser(ts: List[Token]) = TokenListParser(ts)
+
+implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
+  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
+  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
+  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
+}
+
+implicit def TokenOps(t: Token) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](List(t), q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](List(t), qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](List(t), f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](List(t), q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](List(t), qs)
+}
+
+implicit def TokenListOps(ts: List[Token]) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](ts, q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](ts, qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](ts, f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](ts, q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](ts, qs)
+}
+
+// Abstract Syntax Trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp
+
+type Block = List[Stmt]
+
+case object Skip extends Stmt
+case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
+case class While(b: BExp, bl: Block) extends Stmt
+case class Assign(s: String, a: AExp) extends Stmt
+case class Read(s: String) extends Stmt
+case class WriteId(s: String) extends Stmt  // for printing values of variables
+case class WriteString(s: String) extends Stmt  // for printing words
+
+case class Var(s: String) extends AExp
+case class Num(i: Int) extends AExp
+case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+
+case object True extends BExp
+case object False extends BExp
+case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+case class And(b1: BExp, b2: BExp) extends BExp
+case class Or(b1: BExp, b2: BExp) extends BExp
+
+case class IdParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_ID(id) :: rest => Set((id, rest))
+        case _ => Set()
+    }
+}
+
+case class NumParser() extends Parser[List[Token], Int] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_NUM(n) :: rest => Set((n, rest))
+        case _ => Set()
+    }
+}
+
+case class StringParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_STRING(s) :: rest => Set((s, rest))
+        case _ => Set()
+    }
+}
+
+case class TokParser(s: String) extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_OP(o) :: rest if s == o => Set((o, rest))
+        case T_KWD(k) :: rest if s == k => Set((k, rest))
+        case _ => Set()
+    }
+}
+
+implicit def parser_interpolation(sc: StringContext) = new {
+    def p(args: Any*) = TokParser(sc.s(args:_*))
+}    
+
+
+// WHILE Language Parsing
+lazy val AExp: Parser[List[Token], AExp] = 
+  (Te ~ T_OP("+") ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z): AExp } ||
+  (Te ~ T_OP("-") ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z): AExp } || Te
+lazy val Te: Parser[List[Token], AExp] = 
+  (Fa ~ T_OP("*") ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z): AExp } || 
+  (Fa ~ T_OP("/") ~ Te) ==> { case x ~ _ ~ z => Aop("/", x, z): AExp } || 
+  (Fa ~ T_OP("%") ~ Te) ==> { case x ~ _ ~ z => Aop("%", x, z): AExp } || Fa  
+lazy val Fa: Parser[List[Token], AExp] = 
+   (T_PAREN("(") ~ AExp ~ T_PAREN(")")) ==> { case _ ~ y ~ _ => y } || 
+   IdParser() ==> Var  || 
+   NumParser() ==> Num
+
+lazy val BExp: Parser[List[Token], BExp] = 
+   (AExp ~ T_OP("==") ~ AExp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || 
+   (AExp ~ T_OP("!=") ~ AExp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || 
+   (AExp ~ T_OP("<") ~ AExp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || 
+   (AExp ~ T_OP(">") ~ AExp) ==> { case x ~ _ ~ z => Bop(">", x, z): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("&&")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => And(y, v): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("||")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => Or(y, v): BExp } ||
+   (T_KEYWORD("true") ==> (_ => True: BExp )) || 
+   (T_KEYWORD("false") ==> (_ => False: BExp )) ||
+   (T_PAREN("(") ~ BExp ~ T_PAREN(")")) ==> { case _ ~ x ~ _ => x }
+
+lazy val Stmt: Parser[List[Token], Stmt] =
+    T_KEYWORD("skip") ==> (_ => Skip: Stmt) ||
+    (IdParser() ~ T_OP(":=") ~ AExp) ==> { case id ~ _ ~ z => Assign(id, z): Stmt } ||
+    (T_KEYWORD("if") ~ BExp ~ T_KEYWORD("then") ~ Block ~ T_KEYWORD("else") ~ Block) ==> { case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } ||
+    (T_KEYWORD("while") ~ BExp ~ T_KEYWORD("do") ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) : Stmt } ||
+    (T_KEYWORD("read") ~ IdParser()) ==> { case _ ~ id => Read(id): Stmt} ||
+    (T_KEYWORD("write") ~ IdParser()) ==> { case _ ~ id => WriteId(id): Stmt} ||
+    (T_KEYWORD("write") ~ StringParser()) ==> { case _ ~ s => WriteString(s): Stmt}
+
+lazy val Stmts: Parser[List[Token], Block] =
+    (Stmt ~ T_SEMI ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } ||
+    (Stmt ==> (s => List(s) : Block))
+
+lazy val Block: Parser[List[Token], Block] =
+    (T_PAREN("{") ~ Stmts ~ T_PAREN("}")) ==> { case x ~ y ~ z => y} ||
+    (Stmt ==> (s => List(s)))
+
+// Testing with programs 2 & 3
+
+println("Fibonacci")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "fib.while"))))
+
+println("Loops")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))))
+
+println("Collatz")
+println(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))))
+
+
+// Interpreter
+
+// Environment to store values of variables
+type Env = Map[String, Int]
+
+def eval_aexp(a: AExp, env: Env) : Int = a match {
+  case Num(i) => i
+  case Var(s) => env(s)
+  case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
+  case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
+  case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
+  case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)
+  case Aop("%", a1, a2) => eval_aexp(a1, env) % eval_aexp(a2, env)
+}
+
+def eval_bexp(b: BExp, env: Env) : Boolean = b match {
+  case True => true
+  case False => false
+  case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
+  case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
+  case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
+  case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
+  case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)
+  case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)
+}
+
+// Import needed to take int as input from the user
+import scala.io.StdIn.readInt
+
+def eval_stmt(s: Stmt, env: Env) : Env = s match {
+  case Skip => env
+  case Assign(x, a) => env + (x -> eval_aexp(a, env))
+  case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env) 
+  case While(b, bl) => 
+    if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
+    else env
+
+  case WriteId(x) => { print(env(x)) ; env }
+  case WriteString(x) => {
+        print(x.replaceAll("\"", "").replaceAll("""\\n""", "\n")) ;
+        env
+       }
+
+  case Read(x) => { 
+      println("Enter an integer and press ENTER:") ; 
+      val n = readInt() ; // Note: Does not work when using the REPL
+      eval_stmt(Assign(x, Num(n)), env) 
+  }
+}
+
+def eval_bl(bl: Block, env: Env) : Env = bl match {
+  case Nil => env
+  case s::bl => eval_bl(bl, eval_stmt(s, env))
+}
+
+def eval(bl: Block) : Env = eval_bl(bl, Map())
+
+println("Factors eval")
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "factors.while"))).head))
+
+println("Collatz2 eval")
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head))
+
+println("Loops eval")
+val start = System.nanoTime()
+println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))).head))
+val end = System.nanoTime()
+println("Time taken in seconds: ")
+println((end - start)/(1.0e9))

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw3/primes.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,15 @@
+// prints out prime numbers from
+// 2 to 100 (end)
+
+end := 100;
+n := 2;
+while (n < end) do {
+  f := 2;
+  tmp := 0;
+  while ((f < n / 2 + 1) && (tmp == 0)) do {
+    if ((n / f) * f == n) then  { tmp := 1 } else { skip };
+    f := f + 1
+  };
+  if (tmp == 0) then { write(n); write("\n") } else { skip };
+  n  := n + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw4/collatz2.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,27 @@
+// Collatz series
+//
+// needs writing of strings and numbers; comments
+
+bnd := 1;
+while bnd < 100001 do {
+  write bnd;
+  write ": ";
+  n := bnd;
+  cnt := 0;
+
+  while n > 1 do {
+    write n;
+    write ",";
+    
+    if n % 2 == 0 
+    then n := n / 2 
+    else n := 3 * n+1;
+
+    cnt := cnt + 1
+  };
+
+  write " => ";
+  write cnt;
+  write "\n";
+  bnd := bnd + 1
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw4/compiler.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,277 @@
+// Compiler for JVM
+
+import $file.lexer
+import lexer._
+
+import $file.parser
+import parser._
+
+
+val beginning = """
+.class public XXX.XXX
+.super java/lang/Object
+
+.method public static write(I)V 
+    .limit locals 1 
+    .limit stack 2 
+    getstatic java/lang/System/out Ljava/io/PrintStream; 
+    iload 0
+    invokevirtual java/io/PrintStream/print(I)V 
+    return 
+.end method
+
+.method public static writes(Ljava/lang/String;)V
+    .limit stack 2
+    .limit locals 1
+    getstatic java/lang/System/out Ljava/io/PrintStream;
+    aload 0
+    invokevirtual java/io/PrintStream/print(Ljava/lang/String;)V
+    return
+.end method
+
+.method public static read()I 
+    .limit locals 10 
+    .limit stack 10
+
+    ldc 0 
+    istore 1  ; this will hold our final integer 
+Label1: 
+    getstatic java/lang/System/in Ljava/io/InputStream; 
+    invokevirtual java/io/InputStream/read()I 
+    istore 2 
+    iload 2 
+    ldc 10   ; the newline delimiter 
+    isub 
+    ifeq Label2 
+    iload 2 
+    ldc 32   ; the space delimiter 
+    isub 
+    ifeq Label2
+
+    iload 2 
+    ldc 48   ; we have our digit in ASCII, have to subtract it from 48 
+    isub 
+    ldc 10 
+    iload 1 
+    imul 
+    iadd 
+    istore 1 
+    goto Label1 
+Label2: 
+    ;when we come here we have our integer computed in local variable 1 
+    iload 1 
+    ireturn 
+.end method
+
+.method public static main([Ljava/lang/String;)V
+   .limit locals 200
+   .limit stack 200
+
+; COMPILED CODE STARTS
+
+"""
+
+val ending = """
+; COMPILED CODE ENDS
+   return
+
+.end method
+"""
+
+// Compiler
+
+var counter = -1
+
+def Fresh(x: String) = {
+  counter += 1
+  x ++ "_" ++ counter.toString()
+}
+
+implicit def string_interpolations(sc: StringContext) = new {
+    def i(args: Any*): String = "   " ++ sc.s(args:_*) ++ "\n"
+    def l(args: Any*): String = sc.s(args:_*) ++ ":\n"
+}
+
+type Env = Map[String, Int]
+
+def compile_op(op: String) = op match {
+  case "+" => i"iadd"
+  case "-" => i"isub"
+  case "*" => i"imul"
+  case "/" => i"idiv"
+  case "%" => i"irem"
+}
+
+def compile_aexp(a: AExp, env : Env) : String = a match {
+  case Num(i) => i"ldc $i"
+  case Var(s) => i"iload ${env(s)} \t\t; $s"
+  case Aop(op, a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op)
+}
+
+def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
+  case True => ""
+  case False => i"goto $jmp"
+  case And(b1, b2) => compile_bexp(b1, env, jmp) ++ compile_bexp(b2, env, jmp)
+  case Or(b1, b2) => {
+    val b1_false = Fresh("Or_second");
+    val or_end = Fresh("Or_end");
+    compile_bexp(b1, env, b1_false) ++
+    i"goto $or_end" ++
+    l"$b1_false" ++
+    compile_bexp(b2, env, jmp) ++
+    l"$or_end"
+  }
+  case Bop("==", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp"
+  case Bop("!=", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp"
+  case Bop("<", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp"
+  case Bop(">", a1, a2) => 
+    compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmple $jmp"
+}
+
+def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match {
+  case Skip => ("", env)
+  case Assign(x, a) => {
+    val index = env.getOrElse(x, env.keys.size)
+    (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index))
+  } 
+  case If(b, bl1, bl2) => {
+    val if_else = Fresh("If_else")
+    val if_end = Fresh("If_end")
+    val (instrs1, env1) = compile_block(bl1, env)
+    val (instrs2, env2) = compile_block(bl2, env1)
+    (compile_bexp(b, env, if_else) ++
+     instrs1 ++
+     i"goto $if_end" ++
+     l"$if_else" ++
+     instrs2 ++
+     l"$if_end", env2)
+  }
+  case While(b, bl) => {
+    val loop_begin = Fresh("Loop_begin")
+    val loop_end = Fresh("Loop_end")
+    val (instrs1, env1) = compile_block(bl, env)
+    (l"$loop_begin" ++
+     compile_bexp(b, env, loop_end) ++
+     instrs1 ++
+     i"goto $loop_begin" ++
+     l"$loop_end", env1)
+  }
+  case For(id, lower, upper, code) => {
+      val (assignment_code, env1) = compile_stmt(Assign(id, lower), env)  // id := lower;
+      val while_equivalent = While(
+          Or(Bop("<", Var(id), upper), Bop("==", Var(id), upper)),    // while id <= upper do {
+          code ++                                                     //    code  
+          List(
+            Assign(id, Aop("+", Var(id), Num(1)))                     //    id := id + 1
+          ))                                                          // };
+
+      val (while_code, env2) = compile_stmt(while_equivalent, env1)
+      (assignment_code ++ while_code, env2)
+  }
+  case WriteId(x) => (i"iload ${env(x)} \t\t; $x" ++ 
+     i"invokestatic XXX/XXX/write(I)V", env)
+  case WriteString(x) => (s"   ldc ${x}\n" ++
+     i"invokestatic XXX/XXX/writes(Ljava/lang/String;)V", env)
+  case Read(x) => {
+    val index = env.getOrElse(x, env.keys.size) 
+    (i"invokestatic XXX/XXX/read()I" ++ 
+     i"istore $index \t\t; $x", env + (x -> index))
+  }
+}
+
+def compile_block(bl: Block, env: Env) : (String, Env) = bl match {
+  case Nil => ("", env)
+  case s::bl => {
+    val (instrs1, env1) = compile_stmt(s, env)
+    val (instrs2, env2) = compile_block(bl, env1)
+    (instrs1 ++ instrs2, env2)
+  }
+}
+
+def compile(bl: Block, class_name: String) : String = {
+  val instructions = compile_block(bl, Map.empty)._1
+  (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name)
+}
+
+// Compiling and running
+
+import scala.util._
+import scala.sys.process._
+import scala.io
+
+def compile_tofile(bl: Block, class_name: String) = {
+  val output = compile(bl, class_name)
+  val fw = new java.io.FileWriter(class_name + ".j") 
+  fw.write(output) 
+  fw.close()
+}
+
+def compile_all(bl: Block, class_name: String) : Unit = {
+  compile_tofile(bl, class_name)
+  println("compiled ")
+  val test = ("java -jar jasmin.jar " + class_name + ".j").!!
+  println("assembled ")
+}
+
+def time_needed[T](i: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (j <- 1 to i) code
+  val end = System.nanoTime()
+  (end - start)/(i * 1.0e9)
+}
+
+def compile_run(bl: Block, class_name: String) : Unit = {
+  println("Start compilation")
+  compile_all(bl, class_name)
+  println("running")
+  println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!))
+}
+
+// ---- Q1
+
+// Fibonacci
+
+val fibonacciProgram = """write "Fib";
+read n;
+minus1 := 0;
+minus2 := 1;
+while n > 0 do {
+  temp := minus2;
+  minus2 := minus1 + minus2;
+  minus1 := temp;
+  n := n - 1
+};
+write "Result";
+write minus2"""
+
+//compile_all(Stmts.parse_all(tokenise(fibonacciProgram)).head, "fib")
+
+val factorialProgram = """write "Factorial";
+read n;
+fact := 1;
+
+while n > 0 do {
+  fact := n * fact;
+  n := n - 1
+};
+
+write "Result";
+write fact
+"""
+
+compile_all(Stmts.parse_all(tokenise(factorialProgram)).head, "factorial")
+
+// ---- Q3
+
+/* compile_run(Stmts.parse_all(tokenise("""for i := 1 upto 10 do {
+  for i := 1 upto 10 do {
+    write i
+  }
+}""")).head, "nestedloop") */
+
+
+compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head, "collatz2")

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw4/fib.while	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,13 @@
+write "Fib: ";
+read n;  
+minus1 := 0;
+minus2 := 1;
+while n > 0 do {
+       temp := minus2;
+       minus2 := minus1 + minus2;
+       minus1 := temp;
+       n := n - 1
+};
+write "Result: ";
+write minus2 
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw4/lexer.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,250 @@
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls
+
+// Rexp
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+case class RECD(x: String, r: Rexp) extends Rexp
+
+case class RANGE(s: Set[Char]) extends Rexp
+case class PLUS(r: Rexp) extends Rexp
+case class OPTIONAL(r: Rexp) extends Rexp
+case class NTIMES(r: Rexp, n: Int) extends Rexp 
+
+// Values
+abstract class Val
+case object Empty extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case class Rec(x: String, v: Val) extends Val
+
+
+// Convenience typing
+def charlist2rexp(s : List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+implicit def string2rexp(s : String) : Rexp = 
+  charlist2rexp(s.toList)
+
+implicit def RexpOps(r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps(s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+  def $ (r: Rexp) = RECD(s, r)
+}
+
+// nullable
+def nullable(r: Rexp) : Boolean = r match {
+  case ZERO => false
+  case ONE => true
+  case CHAR(_) => false
+  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case STAR(_) => true
+
+  case RECD(_, r1) => nullable(r1)
+  case RANGE(_) => false
+  case PLUS(r1) => nullable(r1)
+  case OPTIONAL(_) => true
+  case NTIMES(r1, i) => if (i == 0) true else nullable(r1)
+}
+
+// der
+def der(c: Char, r: Rexp) : Rexp = r match {
+  case ZERO => ZERO
+  case ONE => ZERO
+  case CHAR(d) => if (c == d) ONE else ZERO
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r) => SEQ(der(c, r), STAR(r))
+
+  case RECD(_, r1) => der(c, r1)
+  case RANGE(s) => if (s.contains(c)) ONE else ZERO 
+  case PLUS(r1) => SEQ(der(c, r1), STAR(r1))
+  case OPTIONAL(r1) => ALT(der(c, r1), ZERO)
+  case NTIMES(r, i) => 
+    if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+}
+
+// Flatten
+def flatten(v: Val) : String = v match {
+  case Empty => ""
+  case Chr(c) => c.toString
+  case Left(v) => flatten(v)
+  case Right(v) => flatten(v)
+  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+  case Stars(vs) => vs.map(flatten).mkString
+  case Rec(_, v) => flatten(v)
+}
+
+// Env
+def env(v: Val) : List[(String, String)] = v match {
+  case Empty => Nil
+  case Chr(c) => Nil
+  case Left(v) => env(v)
+  case Right(v) => env(v)
+  case Sequ(v1, v2) => env(v1) ::: env(v2)
+  case Stars(vs) => vs.flatMap(env)
+  case Rec(x, v) => (x, flatten(v))::env(v)
+}
+
+// Mkeps
+def mkeps(r: Rexp) : Val = r match {
+  case ONE => Empty
+  case ALT(r1, r2) => 
+    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+  case STAR(r) => Stars(Nil)
+  case RECD(x, r) => Rec(x, mkeps(r))
+
+  case PLUS(r) => Stars(List(mkeps(r)))   // the first copy must match the empty string
+  case OPTIONAL(r) => Right(Empty)
+  case NTIMES(r, i) => Stars(List.fill(i)(mkeps(r)))
+}
+
+// Inj
+def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+  case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+  case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+  case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+  case (CHAR(d), Empty) => Chr(c) 
+  case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+
+  case (RANGE(_), Empty) => Chr(c)
+  case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (OPTIONAL(r), Left(v1)) => Left(inj(r, c, v1))
+  case (NTIMES(r, n), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+}
+
+// Rectification functions
+def F_ID(v: Val): Val = v
+def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
+def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
+def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Right(v) => Right(f2(v))
+  case Left(v) => Left(f1(v))
+}
+def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
+}
+def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(Empty), f2(v))
+def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(v), f2(Empty))
+def F_RECD(f: Val => Val) = (v:Val) => v match {
+  case Rec(x, v) => Rec(x, f(v))
+}
+def F_ERROR(v: Val): Val = throw new Exception("error")
+
+// Simp
+def simp(r: Rexp): (Rexp, Val => Val) = r match {
+  case ALT(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (r2s, F_RIGHT(f2s))
+      case (_, ZERO) => (r1s, F_LEFT(f1s))
+      case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
+                else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
+    }
+  }
+  case SEQ(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (ZERO, F_ERROR)
+      case (_, ZERO) => (ZERO, F_ERROR)
+      case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
+      case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
+      case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
+    }
+  }
+  case r => (r, F_ID)
+}
+
+// Lex
+def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else 
+    { throw new Exception("lexing error") } 
+  case c::cs => {
+    val (r_simp, f_simp) = simp(der(c, r))
+    inj(r, c, f_simp(lex_simp(r_simp, cs)))
+  }
+}
+
+def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))
+
+// Language specific code
+val KEYWORD : Rexp = "while" | "if" | "then" | "else" | "do" | "for" | "to" | "true" | "false" | "read" | "write" | "skip" 
+val OP : Rexp = "+" | "-" | "*" | "%" | "/" | "==" | "!=" | ">" | "<" | ">=" | "<=" | ":=" | "&&" | "||"
+val LET: Rexp = RANGE(('A' to 'Z').toSet ++ ('a' to 'z'))
+val SYM : Rexp = LET | RANGE(Set('.', '_', '>', '<', '=', ';', ',', ':'))
+val PARENS : Rexp = "(" | "{" | ")" | "}"
+val SEMI : Rexp = ";"
+val WHITESPACE : Rexp = PLUS(" ") | "\n" | "\t"
+val DIGIT : Rexp = RANGE(('0' to '9').toSet)
+val DIGIT1 : Rexp = RANGE(('1' to '9').toSet)
+val STRING : Rexp = "\"" ~ (SYM | " " | "\\n" | DIGIT).% ~ "\""
+val ID : Rexp = LET ~ (LET | "_" | DIGIT).%
+val NUM : Rexp = "0" | (DIGIT1 ~ DIGIT.%)
+val COMMENT : Rexp = "//" ~ (SYM | " " | DIGIT).% ~ "\n" 
+
+val WHILE_REGS = (("k" $ KEYWORD) | 
+                  ("o" $ OP) | 
+                  ("str" $ STRING) |
+                  ("p" $ PARENS) |
+                  ("s" $ SEMI) | 
+                  ("w" $ WHITESPACE) | 
+                  ("i" $ ID) | 
+                  ("n" $ NUM) |
+		  ("c" $ COMMENT)).%
+
+// Token
+abstract class Token extends Serializable 
+case class T_KEYWORD(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_STRING(s: String) extends Token
+case class T_PAREN(s: String) extends Token
+case object T_SEMI extends Token
+case class T_ID(s: String) extends Token
+case class T_NUM(n: Int) extends Token
+
+val token : PartialFunction[(String, String), Token] = {
+  case ("k", s) => T_KEYWORD(s)
+  case ("o", s) => T_OP(s)
+  case ("str", s) => T_STRING(s)
+  case ("p", s) => T_PAREN(s)
+  case ("s", _) => T_SEMI
+  case ("i", s) => T_ID(s)
+  case ("n", s) => T_NUM(s.toInt)
+}
+
+// Tokenise
+def tokenise(s: String) : List[Token] = 
+  lexing_simp(WHILE_REGS, s).collect(token)
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw4/parser.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,162 @@
+// CW3
+
+import $file.lexer
+import lexer._ 
+
+
+case class ~[+A, +B](_1: A, _2: B)
+type IsSeq[A] = A => Seq[_]
+
+abstract class Parser[I : IsSeq, T] {
+  def parse(ts: I): Set[(T, I)]
+
+  def parse_all(ts: I) : Set[T] =
+    for ((head, tail) <- parse(ts); if tail.isEmpty) yield head
+}
+
+class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, ~[T, S]] {
+  def parse(sb: I) = 
+    for ((head1, tail1) <- p.parse(sb); 
+         (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)
+}
+
+class AltParser[I : IsSeq, T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
+}
+
+class FunParser[I : IsSeq, T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+  def parse(sb: I) = 
+    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
+}
+
+// New parser that takes as input a list of tokens
+case class TokenListParser(ts: List[Token]) extends Parser[List[Token], List[Token]] {
+    def parse(tsb: List[Token]) = {
+        val (prefix, suffix) = tsb.splitAt(ts.length)
+        if (prefix == ts) Set((prefix, suffix)) else Set()
+    }
+}
+
+// Implicit definitions to go from a token 
+// or a list of tokens to a TokenListParser
+implicit def token2parser(t: Token) = TokenListParser(List(t))
+implicit def tokenList2parser(ts: List[Token]) = TokenListParser(ts)
+
+implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
+  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
+  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
+  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
+}
+
+implicit def TokenOps(t: Token) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](List(t), q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](List(t), qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](List(t), f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](List(t), q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](List(t), qs)
+}
+
+implicit def TokenListOps(ts: List[Token]) = new {
+    def || (q : => Parser[List[Token], List[Token]]) = new AltParser[List[Token], List[Token]](ts, q)
+    def || (qs : List[Token]) = new AltParser[List[Token], List[Token]](ts, qs)
+    def ==>[S] (f: => List[Token] => S) = new FunParser[List[Token], List[Token], S](ts, f)
+    def ~[S](q : => Parser[List[Token], S]) =
+        new SeqParser[List[Token], List[Token], S](ts, q)
+    def ~ (qs : List[Token]) =
+        new SeqParser[List[Token], List[Token], List[Token]](ts, qs)
+}
+
+// Abstract Syntax Trees
+abstract class Stmt
+abstract class AExp
+abstract class BExp
+
+type Block = List[Stmt]
+
+case object Skip extends Stmt
+case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
+case class While(b: BExp, bl: Block) extends Stmt
+case class Assign(s: String, a: AExp) extends Stmt
+case class Read(s: String) extends Stmt
+case class WriteId(s: String) extends Stmt  // for printing values of variables
+case class WriteString(s: String) extends Stmt  // for printing words
+case class For(counter: String, lower: AExp, upper: AExp, code: Block) extends Stmt
+
+
+case class Var(s: String) extends AExp
+case class Num(i: Int) extends AExp
+case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+
+case object True extends BExp
+case object False extends BExp
+case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+case class And(b1: BExp, b2: BExp) extends BExp
+case class Or(b1: BExp, b2: BExp) extends BExp
+
+case class IdParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_ID(id) :: rest => Set((id, rest))
+        case _ => Set()
+    }
+}
+
+case class NumParser() extends Parser[List[Token], Int] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_NUM(n) :: rest => Set((n, rest))
+        case _ => Set()
+    }
+}
+
+case class StringParser() extends Parser[List[Token], String] {
+    def parse(tsb: List[Token]) = tsb match {
+        case T_STRING(s) :: rest => Set((s, rest))
+        case _ => Set()
+    }
+}
+
+// WHILE Language Parsing
+lazy val AExp: Parser[List[Token], AExp] = 
+  (Te ~ T_OP("+") ~ AExp) ==> { case x ~ _ ~ z => Aop("+", x, z): AExp } ||
+  (Te ~ T_OP("-") ~ AExp) ==> { case x ~ _ ~ z => Aop("-", x, z): AExp } || Te
+lazy val Te: Parser[List[Token], AExp] = 
+  (Fa ~ T_OP("*") ~ Te) ==> { case x ~ _ ~ z => Aop("*", x, z): AExp } || 
+  (Fa ~ T_OP("/") ~ Te) ==> { case x ~ _ ~ z => Aop("/", x, z): AExp } || 
+  (Fa ~ T_OP("%") ~ Te) ==> { case x ~ _ ~ z => Aop("%", x, z): AExp } || Fa  
+lazy val Fa: Parser[List[Token], AExp] = 
+   (T_PAREN("(") ~ AExp ~ T_PAREN(")")) ==> { case _ ~ y ~ _ => y } || 
+   IdParser() ==> Var  || 
+   NumParser() ==> Num
+
+lazy val BExp: Parser[List[Token], BExp] = 
+   (AExp ~ T_OP("==") ~ AExp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || 
+   (AExp ~ T_OP("!=") ~ AExp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || 
+   (AExp ~ T_OP("<") ~ AExp) ==> { case x ~ _ ~ z => Bop("<", x, z): BExp } || 
+   (AExp ~ T_OP(">") ~ AExp) ==> { case x ~ _ ~ z => Bop(">", x, z): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("&&")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => And(y, v): BExp } ||
+   (T_PAREN("(") ~ BExp ~ List(T_PAREN(")"), T_OP("||")) ~ BExp) ==> { case _ ~ y ~ _ ~ v => Or(y, v): BExp } ||
+   (T_KEYWORD("true") ==> (_ => True: BExp )) || 
+   (T_KEYWORD("false") ==> (_ => False: BExp )) ||
+   (T_PAREN("(") ~ BExp ~ T_PAREN(")")) ==> { case _ ~ x ~ _ => x }
+
+lazy val Stmt: Parser[List[Token], Stmt] =
+    T_KEYWORD("skip") ==> (_ => Skip: Stmt) ||
+    (IdParser() ~ T_OP(":=") ~ AExp) ==> { case id ~ _ ~ z => Assign(id, z): Stmt } ||
+    (T_KEYWORD("if") ~ BExp ~ T_KEYWORD("then") ~ Block ~ T_KEYWORD("else") ~ Block) ==> { case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w): Stmt } ||
+    (T_KEYWORD("while") ~ BExp ~ T_KEYWORD("do") ~ Block) ==> { case _ ~ y ~ _ ~ w => While(y, w) : Stmt } ||
+    (T_KEYWORD("read") ~ IdParser()) ==> { case _ ~ id => Read(id): Stmt} ||
+    (T_KEYWORD("write") ~ IdParser()) ==> { case _ ~ id => WriteId(id): Stmt} ||
+    (T_KEYWORD("write") ~ StringParser()) ==> { case _ ~ s => WriteString(s): Stmt} ||
+    (T_KEYWORD("for") ~ IdParser() ~ T_OP(":=") ~ AExp ~ T_KEYWORD("upto") ~ AExp ~ T_KEYWORD("do") ~ Block) ==> {
+      case _ ~ id ~ _ ~ lower ~ _ ~ upper ~ _ ~ blck => For(id, lower, upper, blck): Stmt
+    }
+
+lazy val Stmts: Parser[List[Token], Block] =
+    (Stmt ~ T_SEMI ~ Stmts) ==> { case x ~ _ ~ z => x :: z : Block } ||
+    (Stmt ==> (s => List(s) : Block))
+
+lazy val Block: Parser[List[Token], Block] =
+    (T_PAREN("{") ~ Stmts ~ T_PAREN("}")) ==> { case x ~ y ~ z => y} ||
+    (Stmt ==> (s => List(s)))
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/fact.fun	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,21 @@
+// a simple factorial program
+// (including a tail recursive version)
+
+
+def fact(n: Int) : Int =
+  if n == 0 then 1 else n * fact(n - 1);
+
+def facT(n: Int, acc: Int) : Int =
+  if n == 0 then acc else facT(n - 1, n * acc);
+
+def facTi(n: Int) : Int = facT(n, 1);
+
+def top() : Void = {
+  print_int(fact(6));
+  print_char(',');
+  print_int(facTi(6));
+  print_char('\n')
+};
+
+top()
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/fun_llvm.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,412 @@
+// A Small LLVM Compiler for a Simple Functional Language
+// (includes an external lexer and parser)
+//
+//
+// call with                 -- prints out llvm code
+//
+//     amm fun_llvm.sc main fact.fun
+//     amm fun_llvm.sc main defs.fun
+//
+// or                        -- writes llvm code to disk
+//
+//     amm fun_llvm.sc write fact.fun
+//     amm fun_llvm.sc write defs.fun
+//
+//       this will generate an .ll file. 
+//
+// or                       -- runs the generated llvm code via lli
+//
+//     amm fun_llvm.sc run fact.fun
+//     amm fun_llvm.sc run defs.fun
+//
+//
+// You can interpret an .ll file using lli, for example
+//
+//      lli fact.ll
+//
+// The optimiser can be invoked as
+//
+//      opt -O1 -S in_file.ll > out_file.ll
+//      opt -O3 -S in_file.ll > out_file.ll
+//
+// The code produced for the various architectures can be obtain with
+//   
+//   llc -march=x86 -filetype=asm in_file.ll -o -
+//   llc -march=arm -filetype=asm in_file.ll -o -  
+//
+// Producing an executable can be achieved by
+//
+//    llc -filetype=obj in_file.ll
+//    gcc in_file.o -o a.out
+//    ./a.out
+
+
+import $file.fun_tokens, fun_tokens._
+import $file.fun_parser, fun_parser._ 
+
+
+// for generating new labels
+var counter = -1
+
+def Fresh(x: String) = {
+  counter += 1
+  x ++ "_" ++ counter.toString()
+}
+
+// Internal CPS language for FUN
+abstract class KExp
+abstract class KVal
+
+type Ty = String
+type TyEnv = Map[String, Ty]
+
+case class KVar(s: String, ty: Ty = "UNDEF") extends KVal
+case class KLoad(v: KVal) extends KVal
+case class KNum(i: Int) extends KVal
+case class KFNum(i: Float) extends KVal
+case class KChr(c: Int) extends KVal
+case class Kop(o: String, v1: KVal, v2: KVal, ty: Ty = "UNDEF") extends KVal
+case class KCall(o: String, vrs: List[KVal], ty: Ty = "UNDEF") extends KVal
+
+case class KIf(x1: String, e1: KExp, e2: KExp) extends KExp {
+  override def toString = s"KIf $x1\nIF\n$e1\nELSE\n$e2"
+}
+case class KLet(x: String, e1: KVal, e2: KExp) extends KExp {
+  override def toString = s"let $x = $e1 in \n$e2" 
+}
+case class KReturn(v: KVal) extends KExp
+
+// typing K values
+def typ_val(v: KVal, ts: TyEnv) : (KVal, Ty) = v match {
+  case KVar(s, _) => {
+    val ty = ts.getOrElse(s, "TUNDEF")
+    (KVar(s, ty), ty)  
+  }
+  case Kop(op, v1, v2, _) => {
+    val (tv1, ty1) = typ_val(v1, ts)
+    val (tv2, ty2) = typ_val(v2, ts)
+    if (ty1 == ty2) (Kop(op, tv1, tv2, ty1), ty1) else (Kop(op, tv1, tv2, "TMISMATCH"), "TMISMATCH") 
+  }
+  case KCall(fname, args, _) => {
+    val ty = ts.getOrElse(fname, "TCALLUNDEF" ++ fname)
+    (KCall(fname, args.map(typ_val(_, ts)._1), ty), ty)
+  }  
+  case KLoad(v) => {
+    val (tv, ty) = typ_val(v, ts)
+    (KLoad(tv), ty)
+  }
+  case KNum(i) => (KNum(i), "Int")
+  case KFNum(i) => (KFNum(i), "Double")
+  case KChr(c) => (KChr(c), "Int")
+}
+
+def typ_exp(a: KExp, ts: TyEnv) : KExp = a match {
+  case KReturn(v) => KReturn(typ_val(v, ts)._1)
+  case KLet(x: String, v: KVal, e: KExp) => {
+    val (tv, ty) = typ_val(v, ts)
+    KLet(x, tv, typ_exp(e, ts + (x -> ty)))
+  }
+  case KIf(b, e1, e2) => KIf(b, typ_exp(e1, ts), typ_exp(e2, ts))
+}
+
+
+
+
+// CPS translation from Exps to KExps using a
+// continuation k.
+def CPS(e: Exp)(k: KVal => KExp) : KExp = e match {
+  case Var(s) if (s.head.isUpper) => {
+      val z = Fresh("tmp")
+      KLet(z, KLoad(KVar(s)), k(KVar(z)))
+  }
+  case Var(s) => k(KVar(s))
+  case Num(i) => k(KNum(i))
+  case ChConst(c) => k(KChr(c))
+  case FNum(i) => k(KFNum(i))
+  case Aop(o, e1, e2) => {
+    val z = Fresh("tmp")
+    CPS(e1)(y1 => 
+      CPS(e2)(y2 => KLet(z, Kop(o, y1, y2), k(KVar(z)))))
+  }
+  case If(Bop(o, b1, b2), e1, e2) => {
+    val z = Fresh("tmp")
+    CPS(b1)(y1 => 
+      CPS(b2)(y2 => 
+        KLet(z, Kop(o, y1, y2), KIf(z, CPS(e1)(k), CPS(e2)(k)))))
+  }
+  case Call(name, args) => {
+    def aux(args: List[Exp], vs: List[KVal]) : KExp = args match {
+      case Nil => {
+          val z = Fresh("tmp")
+          KLet(z, KCall(name, vs), k(KVar(z)))
+      }
+      case e::es => CPS(e)(y => aux(es, vs ::: List(y)))
+    }
+    aux(args, Nil)
+  }
+  case Sequence(e1, e2) => 
+    CPS(e1)(_ => CPS(e2)(y2 => k(y2)))
+}   
+
+//initial continuation
+def CPSi(e: Exp) = CPS(e)(KReturn)
+
+// some testcases
+val e1 = Aop("*", Var("a"), Num(3))
+CPSi(e1)
+
+val e2 = Aop("+", Aop("*", Var("a"), Num(3)), Num(4))
+CPSi(e2)
+
+val e3 = Aop("+", Num(2), Aop("*", Var("a"), Num(3)))
+CPSi(e3)
+
+val e4 = Aop("+", Aop("-", Num(1), Num(2)), Aop("*", Var("a"), Num(3)))
+CPSi(e4)
+
+val e5 = If(Bop("==", Num(1), Num(1)), Num(3), Num(4))
+CPSi(e5)
+
+val e6 = If(Bop("!=", Num(10), Num(10)), e5, Num(40))
+CPSi(e6)
+
+val e7 = Call("foo", List(Num(3)))
+CPSi(e7)
+
+val e8 = Call("foo", List(Aop("*", Num(3), Num(1)), Num(4), Aop("+", Num(5), Num(6))))
+CPSi(e8)
+
+val e9 = Sequence(Aop("*", Var("a"), Num(3)), Aop("+", Var("b"), Num(6)))
+CPSi(e9)
+
+val e = Aop("*", Aop("+", Num(1), Call("foo", List(Var("a"), Num(3)))), Num(4))
+CPSi(e)
+
+
+
+
+// convenient string interpolations 
+// for instructions, labels and methods
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+
+
+
+implicit def sring_inters(sc: StringContext) = new {
+    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"
+}
+
+def get_ty(s: String) = s match {
+  case "Double" => "double"
+  case "Void" => "void"
+  case "Int" => "i32"
+  case "Bool" => "i2"
+  case _ => s
+}
+
+def compile_call_arg(a: KVal) = a match {
+  case KNum(i) => s"i32 $i"
+  case KFNum(i) => s"double $i"
+  case KChr(c) => s"i32 $c"
+  case KVar(s, ty) => s"${get_ty(ty)} %$s" 
+}
+
+def compile_arg(s: (String, String)) = s"${get_ty(s._2)} %${s._1}" 
+
+
+// mathematical and boolean operations
+def compile_op(op: String) = op match {
+  case "+" => "add i32 "
+  case "*" => "mul i32 "
+  case "-" => "sub i32 "
+  case "/" => "sdiv i32 "
+  case "%" => "srem i32 "
+  case "==" => "icmp eq i32 "
+  case "!=" => "icmp ne i32 "      // not equal 
+  case "<=" => "icmp sle i32 "     // signed less or equal
+  case "<"  => "icmp slt i32 "     // signed less than
+}
+
+def compile_dop(op: String) = op match {
+  case "+" => "fadd double "
+  case "*" => "fmul double "
+  case "-" => "fsub double "
+  case "==" => "fcmp oeq double "
+  case "<=" => "fcmp ole double "   
+  case "<"  => "fcmp olt double "   
+}
+
+// compile K values
+def compile_val(v: KVal) : String = v match {
+  case KNum(i) => s"$i"
+  case KFNum(i) => s"$i"
+  case KChr(c) => s"$c"
+  case KVar(s, ty) => s"%$s" 
+  case KLoad(KVar(s, ty)) => s"load ${get_ty(ty)}, ${get_ty(ty)}* @$s"
+  case Kop(op, x1, x2, ty) => ty match { 
+    case "Int" => s"${compile_op(op)} ${compile_val(x1)}, ${compile_val(x2)}"
+    case "Double" => s"${compile_dop(op)} ${compile_val(x1)}, ${compile_val(x2)}"
+    case _ => Kop(op, x1, x2, ty).toString
+  }
+  case KCall(fname, args, ty) => 
+    s"call ${get_ty(ty)} @$fname (${args.map(compile_call_arg).mkString(", ")})"
+}
+
+// compile K expressions
+def compile_exp(a: KExp) : String = a match {
+  case KReturn(KVar("void", _)) =>
+    i"ret void"
+  case KReturn(KVar(x, ty)) =>
+    i"ret ${get_ty(ty)} %$x"
+  case KReturn(KNum(i)) =>
+    i"ret i32 $i"
+  case KLet(x: String, KCall(o: String, vrs: List[KVal], "Void"), e: KExp) => 
+    i"${compile_val(KCall(o: String, vrs: List[KVal], "Void"))}" ++ compile_exp(e)
+  case KLet(x: String, v: KVal, e: KExp) => 
+    i"%$x = ${compile_val(v)}" ++ compile_exp(e)
+  case KIf(x, e1, e2) => {
+    val if_br = Fresh("if_branch")
+    val else_br = Fresh("else_branch")
+    i"br i1 %$x, label %$if_br, label %$else_br" ++
+    l"\n$if_br" ++
+    compile_exp(e1) ++
+    l"\n$else_br" ++ 
+    compile_exp(e2)
+  }
+}
+
+
+val prelude = """
+declare i32 @printf(i8*, ...)
+
+@.str_nl = private constant [2 x i8] c"\0A\00"
+@.str_star = private constant [2 x i8] c"*\00"
+@.str_space = private constant [2 x i8] c" \00"
+
+define void @new_line() #0 {
+  %t0 = getelementptr [2 x i8], [2 x i8]* @.str_nl, i32 0, i32 0
+  %1 = call i32 (i8*, ...) @printf(i8* %t0)
+  ret void
+}
+
+define void @print_star() #0 {
+  %t0 = getelementptr [2 x i8], [2 x i8]* @.str_star, i32 0, i32 0
+  %1 = call i32 (i8*, ...) @printf(i8* %t0)
+  ret void
+}
+
+define void @print_space() #0 {
+  %t0 = getelementptr [2 x i8], [2 x i8]* @.str_space, i32 0, i32 0
+  %1 = call i32 (i8*, ...) @printf(i8* %t0)
+  ret void
+}
+
+define void @skip() #0 {
+  ret void
+}
+
+@.str_int = private constant [3 x i8] c"%d\00"
+
+define void @print_int(i32 %x) {
+   %t0 = getelementptr [3 x i8], [3 x i8]* @.str_int, i32 0, i32 0
+   call i32 (i8*, ...) @printf(i8* %t0, i32 %x) 
+   ret void
+}
+
+@.str_char = private constant [3 x i8] c"%c\00"
+
+define void @print_char(i32 %x) {
+   %t0 = getelementptr [3 x i8], [3 x i8]* @.str_char, i32 0, i32 0
+   call i32 (i8*, ...) @printf(i8* %t0, i32 %x) 
+   ret void
+}
+
+; END OF BUILD-IN FUNCTIONS (prelude)
+
+"""
+
+def get_cont(ty: Ty) = ty match {
+  case "Int" =>    KReturn
+  case "Double" => KReturn
+  case "Void" =>   { (_: KVal) => KReturn(KVar("void", "Void")) }
+} 
+
+// compile function for declarations and main
+def compile_decl(d: Decl, ts: TyEnv) : (String, TyEnv) = d match {
+  case Def(name, args, ty, body) => { 
+    val ts2 = ts + (name -> ty)
+    val tkbody = typ_exp(CPS(body)(get_cont(ty)), ts2 ++ args.toMap)
+    (m"define ${get_ty(ty)} @$name (${args.map(compile_arg).mkString(",")}) {" ++
+     compile_exp(tkbody) ++
+     m"}\n", ts2)
+  }
+  case Main(body) => {
+    val tbody = typ_exp(CPS(body)(_ => KReturn(KNum(0))), ts)
+    (m"define i32 @main() {" ++
+     compile_exp(tbody) ++
+     m"}\n", ts)
+  }
+  case Const(name, n) => {
+    (m"@$name = global i32 $n\n", ts + (name -> "Int"))
+  }
+  case FConst(name, x) => {
+    (m"@$name = global double $x\n", ts + (name -> "Double"))
+  }
+}
+
+def compile_prog(prog: List[Decl], ty: TyEnv) : String = prog match {
+  case Nil => ""
+  case d::ds => {
+    val (s2, ty2) = compile_decl(d, ty)
+    s2 ++ compile_prog(ds, ty2)
+  }
+}
+// main compiler functions
+def compile(prog: List[Decl]) : String = 
+  prelude ++ compile_prog(prog, Map("new_line" -> "Void", "skip" -> "Void", 
+				    "print_star" -> "Void", "print_space" -> "Void",
+                                    "print_int" -> "Void", "print_char" -> "Void"))
+
+
+import ammonite.ops._
+
+
+@main
+def main(fname: String) = {
+    val path = os.pwd / fname
+    val file = fname.stripSuffix("." ++ path.ext)
+    val tks = tokenise(os.read(path))
+    val ast = parse_tks(tks)
+    val code = compile(ast)
+    println(code)
+}
+
+@main
+def write(fname: String) = {
+    val path = os.pwd / fname
+    val file = fname.stripSuffix("." ++ path.ext)
+    val tks = tokenise(os.read(path))
+    val ast = parse_tks(tks)
+    val code = compile(ast)
+    //println(code)
+    os.write.over(os.pwd / (file ++ ".ll"), code)
+}
+
+@main
+def run(fname: String) = {
+    val path = os.pwd / fname
+    val file = fname.stripSuffix("." ++ path.ext)
+    write(fname)  
+    os.proc("llc", "-filetype=obj", file ++ ".ll").call()
+    os.proc("gcc", file ++ ".o", "-o", file ++ ".bin").call()
+    os.proc(os.pwd / (file ++ ".bin")).call(stdout = os.Inherit)
+    println(s"done.")
+}
+
+
+
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/fun_parser.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,217 @@
+// A parser for the Fun language
+//================================
+//
+// call with 
+//
+//     amm fun_parser.sc fact.fun
+//
+//     amm fun_parser.sc defs.fun
+//
+// this will generate a parse-tree from a list
+// of tokens
+
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls
+
+import $file.fun_tokens, fun_tokens._ 
+
+
+// Parser combinators
+//    type parameter I needs to be of Seq-type
+//
+abstract class Parser[I, T](implicit ev: I => Seq[_]) {
+  def parse(ts: I): Set[(T, I)]
+
+  def parse_single(ts: I) : T = 
+    parse(ts).partition(_._2.isEmpty) match {
+      case (good, _) if !good.isEmpty => good.head._1
+      case (good, err) if err.isEmpty => {
+        println (s"Parse Error\n $good \n $err") ; sys.exit(-1) }
+      case (_, err) => { 
+	println (s"Parse Error\n${err.minBy(_._2.length)}") ; sys.exit(-1) }
+    }
+}
+
+// convenience for writing grammar rules
+case class ~[+A, +B](_1: A, _2: B)
+
+class SeqParser[I, T, S](p: => Parser[I, T], 
+                         q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, ~[T, S]] {
+  def parse(sb: I) = 
+    for ((head1, tail1) <- p.parse(sb); 
+         (head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)
+}
+
+class AltParser[I, T](p: => Parser[I, T], 
+                      q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] {
+  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
+}
+
+class FunParser[I, T, S](p: => Parser[I, T], 
+                         f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] {
+  def parse(sb: I) = 
+    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
+}
+
+// convenient combinators
+implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new {
+  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
+  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
+  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
+}
+
+def ListParser[I, T, S](p: => Parser[I, T], 
+                        q: => Parser[I, S])(implicit ev: I => Seq[_]): Parser[I, List[T]] = {
+  (p ==> ((s) => List(s))) ||
+  (p ~ q ~ ListParser(p, q)) ==> { case x ~ _ ~ z => x :: z : List[T] }
+}
+
+case class TokParser(tok: Token) extends Parser[List[Token], Token] {
+  def parse(ts: List[Token]) = ts match {
+    case t::ts if (t == tok) => Set((t, ts)) 
+    case _ => Set()
+  }
+}
+
+implicit def token2tparser(t: Token) = TokParser(t)
+
+implicit def TokOps(t: Token) = new {
+  def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q)
+  def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f)
+  def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q)
+}
+
+case object EmptyParser extends Parser[List[Token], String] {
+  def parse(ts: List[Token]) = Set(("", ts))
+}
+
+case object NumParser extends Parser[List[Token], Int] {
+  def parse(ts: List[Token]) = ts match {
+    case T_NUM(n)::ts => Set((n, ts)) 
+    case _ => Set ()
+  }
+}
+
+case object FNumParser extends Parser[List[Token], Float] {
+  def parse(ts: List[Token]) = ts match {
+    case T_FNUM(x)::ts => Set((x, ts)) 
+    case _ => Set()
+  }
+}
+
+case object IdParser extends Parser[List[Token], String] {
+  def parse(ts: List[Token]) = ts match {
+    case T_ID(s)::ts => Set((s, ts)) 
+    case _ => Set ()
+  }
+}
+
+case object CharConstParser extends Parser[List[Token], Int] {
+  def parse(ts: List[Token]) = ts match {
+    case T_CHR(c)::ts => Set((c, ts)) 
+    case _ => Set ()
+  }
+}
+
+case object TyParser extends Parser[List[Token], String] {
+  def parse(ts: List[Token]) = ts match {
+    case T_TY(s)::ts => Set((s, ts)) 
+    case _ => Set ()
+  }
+}
+
+
+// Abstract syntax trees for the Fun language
+abstract class Exp 
+abstract class BExp 
+abstract class Decl 
+
+case class Def(name: String, args: List[(String, String)], ty: String, body: Exp) extends Decl
+case class Main(e: Exp) extends Decl
+case class Const(name: String, v: Int) extends Decl
+case class FConst(name: String, x: Float) extends Decl
+
+case class Call(name: String, args: List[Exp]) extends Exp
+case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
+case class Var(s: String) extends Exp
+case class Num(i: Int) extends Exp     // integer numbers
+case class FNum(i: Float) extends Exp  // floating numbers
+case class ChConst(c: Int) extends Exp // char constant
+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
+
+
+// arithmetic expressions (there needs to be an F in the SEMICOLON case)
+lazy val Exp: Parser[List[Token], Exp] = 
+  (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==>
+    { case _ ~ x ~ _ ~ y ~ _ ~ z => If(x, y, z): Exp } ||
+  (F ~ T_SEMI ~ Exp) ==> { case x ~ _ ~ y => Sequence(x, y): Exp } || L
+lazy val L: Parser[List[Token], Exp] = 
+  (T ~ T_OP("+") ~ Exp) ==> { case x ~ _ ~ z => Aop("+", x, z): Exp } ||
+  (T ~ T_OP("-") ~ Exp) ==> { case x ~ _ ~ z => Aop("-", x, z): Exp } || T  
+lazy val T: Parser[List[Token], Exp] = 
+  (F ~ T_OP("*") ~ T) ==> { case x ~ _ ~ z => Aop("*", x, z): Exp } || 
+  (F ~ T_OP("/") ~ T) ==> { case x ~ _ ~ z => Aop("/", x, z): Exp } || 
+  (F ~ T_OP("%") ~ T) ==> { case x ~ _ ~ z => Aop("%", x, z): Exp } || F
+lazy val F: Parser[List[Token], Exp] = 
+  (IdParser ~ T_LPAREN ~ T_RPAREN) ==> 
+    { case x ~ _ ~ _ => Call(x, Nil): Exp } || 
+  (IdParser ~ T_LPAREN ~ T_RPAREN) ==> { case x ~ _ ~ _ => Call(x, Nil): Exp } ||
+  (IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> { case x ~ _ ~ z ~ _ => Call(x, z): Exp } ||
+  (T_LPAREN ~ Exp ~ T_RPAREN) ==> { case _ ~ y ~ _ => y: Exp } || 
+  IdParser ==> { case x => Var(x): Exp } || 
+  NumParser ==> { case x => Num(x): Exp } ||
+  CharConstParser ==> { case x => ChConst(x): Exp } ||
+  FNumParser ==> { case x => FNum(x): Exp }
+
+// boolean expressions
+lazy val BExp: Parser[List[Token], BExp] = 
+  (Exp ~ T_OP("==") ~ Exp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } || 
+  (Exp ~ T_OP("!=") ~ Exp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } || 
+  (Exp ~ T_OP("<") ~ Exp)  ==> { case x ~ _ ~ z => Bop("<",  x, z): BExp } || 
+  (Exp ~ T_OP(">") ~ Exp)  ==> { case x ~ _ ~ z => Bop("<",  z, x): BExp } || 
+  (Exp ~ T_OP("<=") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", x, z): BExp } || 
+  (Exp ~ T_OP("=>") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", z, x): BExp } ||
+  (T_LPAREN ~ BExp ~ T_RPAREN) ==> { case _ ~ b ~ _ => b : BExp } 
+
+lazy val Arg : Parser[List[Token], (String, String)] = 
+  (IdParser ~ T_COLON ~ TyParser) ==> { case x ~ _ ~ ty => (x, ty) }  
+
+lazy val Defn: Parser[List[Token], Decl] = {
+   (T_KWD("def") ~ IdParser ~ T_LPAREN ~ T_RPAREN ~ T_COLON ~ TyParser ~ T_OP("=") ~ Exp) ==>
+     { case _ ~ y ~ _ ~ _ ~ _~ ty ~ _ ~ r => Def(y, Nil, ty, r): Decl } ||
+   (T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(Arg, T_COMMA) ~ T_RPAREN ~ T_COLON ~ TyParser ~ T_OP("=") ~ Exp) ==>
+     { case _ ~ y ~ _ ~ w ~ _ ~ _~ ty ~ _ ~ r => Def(y, w, ty, r): Decl }
+}
+
+lazy val Const_decl: Parser[List[Token], Decl] =
+   (T_KWD("val") ~ Arg ~ T_OP("=") ~ NumParser) ==>
+     { case _ ~ x ~ _ ~ v => Const(x._1, v): Decl } ||
+   (T_KWD("val") ~ Arg ~ T_OP("=") ~ FNumParser) ==>
+     { case _ ~ x ~ _ ~ v => FConst(x._1, v): Decl } 
+
+lazy val Prog: Parser[List[Token], List[Decl]] =
+  (Defn ~ T_SEMI ~ Prog) ==> { case x ~ _ ~ z => x :: z : List[Decl] } ||
+  (Const_decl ~ T_SEMI ~ Prog) ==> { case x ~ _ ~ z => x :: z : List[Decl] } ||
+  (Exp ==> ((s) => List(Main(s)) : List[Decl]))
+
+
+
+// Reading tokens and Writing parse trees
+
+import ammonite.ops._
+
+def parse_tks(tks: List[Token]) : List[Decl] = {
+  //println(Prog.parse(tks))
+  Prog.parse_single(tks)
+}
+
+//@doc("Parses a file.")
+@main
+def main(fname: String) : Unit = {
+  val tks = tokenise(os.read(os.pwd / fname))
+  println(parse_tks(tks))
+}
+
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/fun_tokens.sc	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,280 @@
+// A tokeniser for the Fun language
+//==================================
+//
+// call with 
+//
+//     amm fun_tokens.sc fact.fun
+//
+//     amm fun_tokens.sc defs.fun
+//
+
+
+
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls 
+
+abstract class Rexp 
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+case class RECD(x: String, r: Rexp) extends Rexp
+  
+abstract class Val
+case object Empty extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case class Rec(x: String, v: Val) extends Val
+   
+// some convenience for typing in regular expressions
+def charlist2rexp(s : List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s : String) : Rexp = 
+  charlist2rexp(s.toList)
+
+implicit def RexpOps(r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps(s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+  def $ (r: Rexp) = RECD(s, r)
+}
+
+def nullable (r: Rexp) : Boolean = r match {
+  case ZERO => false
+  case ONE => true
+  case CHAR(_) => false
+  case ALT(r1, r2) => nullable(r1) || nullable(r2)
+  case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+  case STAR(_) => true
+  case RECD(_, r1) => nullable(r1)
+}
+
+def der (c: Char, r: Rexp) : Rexp = r match {
+  case ZERO => ZERO
+  case ONE => ZERO
+  case CHAR(d) => if (c == d) ONE else ZERO
+  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+  case SEQ(r1, r2) => 
+    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+    else SEQ(der(c, r1), r2)
+  case STAR(r) => SEQ(der(c, r), STAR(r))
+  case RECD(_, r1) => der(c, r1)
+}
+
+
+// extracts a string from value
+def flatten(v: Val) : String = v match {
+  case Empty => ""
+  case Chr(c) => c.toString
+  case Left(v) => flatten(v)
+  case Right(v) => flatten(v)
+  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+  case Stars(vs) => vs.map(flatten).mkString
+  case Rec(_, v) => flatten(v)
+}
+
+// extracts an environment from a value;
+// used for tokenise a string
+def env(v: Val) : List[(String, String)] = v match {
+  case Empty => Nil
+  case Chr(c) => Nil
+  case Left(v) => env(v)
+  case Right(v) => env(v)
+  case Sequ(v1, v2) => env(v1) ::: env(v2)
+  case Stars(vs) => vs.flatMap(env)
+  case Rec(x, v) => (x, flatten(v))::env(v)
+}
+
+// The Injection Part of the lexer
+
+def mkeps(r: Rexp) : Val = r match {
+  case ONE => Empty
+  case ALT(r1, r2) => 
+    if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+  case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+  case STAR(r) => Stars(Nil)
+  case RECD(x, r) => Rec(x, mkeps(r))
+}
+
+def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+  case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+  case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+  case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+  case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+  case (CHAR(d), Empty) => Chr(c) 
+  case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+  case _ => { println ("Injection error") ; sys.exit(-1) } 
+}
+
+// some "rectification" functions for simplification
+def F_ID(v: Val): Val = v
+def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
+def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
+def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Right(v) => Right(f2(v))
+  case Left(v) => Left(f1(v))
+}
+def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
+  case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
+}
+def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(Empty), f2(v))
+def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = 
+  (v:Val) => Sequ(f1(v), f2(Empty))
+def F_RECD(f: Val => Val) = (v:Val) => v match {
+  case Rec(x, v) => Rec(x, f(v))
+}
+def F_ERROR(v: Val): Val = throw new Exception("error")
+
+def simp(r: Rexp): (Rexp, Val => Val) = r match {
+  case ALT(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (r2s, F_RIGHT(f2s))
+      case (_, ZERO) => (r1s, F_LEFT(f1s))
+      case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
+                else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
+    }
+  }
+  case SEQ(r1, r2) => {
+    val (r1s, f1s) = simp(r1)
+    val (r2s, f2s) = simp(r2)
+    (r1s, r2s) match {
+      case (ZERO, _) => (ZERO, F_ERROR)
+      case (_, ZERO) => (ZERO, F_ERROR)
+      case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
+      case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
+      case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
+    }
+  }
+  case RECD(x, r1) => {
+    val (r1s, f1s) = simp(r1)
+    (RECD(x, r1s), F_RECD(f1s))
+  }
+  case r => (r, F_ID)
+}
+
+// lexing functions including simplification
+def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
+  case Nil => if (nullable(r)) mkeps(r) else { println ("Lexing Error") ; sys.exit(-1) } 
+  case c::cs => {
+    val (r_simp, f_simp) = simp(der(c, r))
+    inj(r, c, f_simp(lex_simp(r_simp, cs)))
+  }
+}
+
+def lexing_simp(r: Rexp, s: String) = env(lex_simp(r, s.toList))
+
+
+// The Lexing Rules for the Fun Language
+
+def PLUS(r: Rexp) = r ~ r.%
+def OPT(r: Rexp) = r | ONE
+
+val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | 
+          "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | 
+          "w" | "x" | "y" | "z" | "A" | "B" | "C" | "D" |"E" | "F" | "G" |
+          "H" | "I" | "J" | "K" |"L" | "M" | "N" |
+          "O" | "P" | "Q" | "R" |"S" | "T" | "U" |
+          "V" | "W" | "X" | "Y" | "Z" | "_"
+val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val ID = SYM ~ (SYM | DIGIT).% 
+val NUM = PLUS(DIGIT)
+val FNUM = OPT("-") ~ NUM ~ "." ~ NUM 
+val KEYWORD : Rexp = "if" | "then" | "else" | "def" | "val"
+val TYPE : Rexp = "Void" | "Int" | "Double" 
+val SEMI: Rexp = ";"
+val COLON: Rexp = ":"
+val COMMA: Rexp = ","
+val OP: Rexp = "=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"
+val WHITESPACE = PLUS(" " | "\n" | "\t" | "\r")
+val RPAREN: Rexp = ")" | "}"
+val LPAREN: Rexp = "(" | "{"
+val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "-" | "." | "\"" | "=" | "," | "(" | ")" | "{" | "}"
+val ALL2 = ALL | "\n"
+val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n")
+
+val CHR :Rexp = "'" ~ (ALL | "\\n") ~ "'" 
+
+
+val FUN_REGS = (("k" $ KEYWORD) | 
+                ("t" $ TYPE) |
+                ("i" $ ID) | 
+                ("ch" $ CHR) | 
+                ("o" $ OP) | 
+                ("n" $ NUM) | 
+                ("f" $ FNUM) | 
+                ("s" $ SEMI) | 
+                ("co" $ COLON) |
+                ("c" $ COMMA) |
+                ("pl" $ LPAREN) |
+                ("pr" $ RPAREN) |
+                ("w" $ (WHITESPACE | COMMENT))).%
+
+
+
+// The tokens for the Fun language
+
+abstract class Token extends Serializable 
+case object T_SEMI extends Token
+case object T_COMMA extends Token
+case object T_COLON extends Token
+case object T_LPAREN extends Token
+case object T_RPAREN extends Token
+case class T_ID(s: String) extends Token
+case class T_FID(s: String) extends Token
+case class T_OP(s: String) extends Token
+case class T_NUM(n: Int) extends Token
+case class T_FNUM(x: Float) extends Token
+case class T_KWD(s: String) extends Token
+case class T_TY(s: String) extends Token
+case class T_CHR(i: Int) extends Token
+
+val token : PartialFunction[(String, String), Token] = {
+  case ("k", s) => T_KWD(s)
+  case ("t", s) => T_TY(s)
+  case ("i", s) => T_ID(s)
+  case ("o", s) => T_OP(s)
+  case ("n", s) => T_NUM(s.toInt)
+  case ("ch", s) => if (s == "'\\n'") T_CHR(10) else T_CHR(s(1).toInt)
+  case ("f", s) => T_FNUM(s.toFloat) 
+  case ("s", _) => T_SEMI
+  case ("c", _) => T_COMMA
+  case ("co", _) => T_COLON
+  case ("pl", _) => T_LPAREN
+  case ("pr", _) => T_RPAREN
+}
+
+
+def tokenise(s: String) : List[Token] = {
+  val tks = lexing_simp(FUN_REGS, s).collect(token)
+  if (tks.length != 0) tks
+  else { println (s"Tokenise Error") ; sys.exit(-1) }     
+}
+
+import ammonite.ops._
+
+//@doc("Tokenising a file.")
+@main
+def main(fname: String) = {
+  println(tokenise(os.read(os.pwd / fname)))
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/hanoi.fun	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,13 @@
+// Towers of Hanoi in Fun
+
+def hanoi(n: Int, a: Int, b: Int, c: Int) : Void =
+  if n != 0 then {
+    hanoi(n - 1, a, c, b);
+    print_int(a);
+    print_char('-'); print_char('>'); // prints out "->"
+    print_int(b);
+    print_char('\n');
+    hanoi(n - 1, c, b, a)
+  } else skip;
+
+hanoi(4,1,2,3)
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/mand.fun	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,36 @@
+// Mandelbrot program (without character constants)
+
+val Ymin: Double = -1.3;
+val Ymax: Double =  1.3;
+val Ystep: Double = 0.05;  //0.025;
+
+val Xmin: Double = -2.1;
+val Xmax: Double =  1.1;
+val Xstep: Double = 0.02;  //0.01;
+
+val Maxiters: Int = 1000;
+
+def m_iter(m: Int, x: Double, y: Double,
+                   zr: Double, zi: Double) : Void = {
+  if Maxiters <= m
+  then print_star() 
+  else {
+    if 4.0 <= zi*zi+zr*zr then print_space() 
+    else m_iter(m + 1, x, y, x+zr*zr-zi*zi, 2.0*zr*zi+y) 
+  }
+};
+
+def x_iter(x: Double, y: Double) : Void = {
+  if x <= Xmax
+  then { m_iter(0, x, y, 0.0, 0.0) ; x_iter(x + Xstep, y) }
+  else skip()
+};
+
+def y_iter(y: Double) : Void = {
+  if y <= Ymax
+  then { x_iter(Xmin, y) ; new_line() ; y_iter(y + Ystep) }
+  else skip() 
+};    
+
+
+y_iter(Ymin)
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/mand2.fun	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,36 @@
+// Mandelbrot program (with character constants)
+
+val Ymin: Double = -1.3;
+val Ymax: Double =  1.3;
+val Ystep: Double = 0.05;  //0.025;
+
+val Xmin: Double = -2.1;
+val Xmax: Double =  1.1;
+val Xstep: Double = 0.02;  //0.01;
+
+val Maxiters: Int = 1000;
+
+def m_iter(m: Int, x: Double, y: Double,
+                   zr: Double, zi: Double) : Void = {
+  if Maxiters <= m
+  then print_char(' ') 
+  else {
+    if 4.0 <= zi*zi+zr*zr then print_char('0' + (m % 10)) 
+    else m_iter(m + 1, x, y, x+zr*zr-zi*zi, 2.0*zr*zi+y) 
+  }
+};
+
+def x_iter(x: Double, y: Double) : Void = {
+  if x <= Xmax
+  then { m_iter(0, x, y, 0.0, 0.0) ; x_iter(x + Xstep, y) }
+  else skip()
+};
+
+def y_iter(y: Double) : Void = {
+  if y <= Ymax
+  then { x_iter(Xmin, y) ; print_char('\n') ; y_iter(y + Ystep) }
+  else skip() 
+};    
+
+
+y_iter(Ymin)
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/solution/cw5/sqr.fun	Wed Dec 15 19:00:01 2021 +0000
@@ -0,0 +1,12 @@
+val Max : Int = 10;
+
+def sqr(x: Int) : Int = x * x;
+
+def all(n: Int) : Void = {
+  if n <= Max
+  then { print_int(sqr(n)) ; new_line(); all(n + 1) }
+  else skip()
+};
+
+all(0)
+ 
\ No newline at end of file

--- a/style.sty	Tue Dec 14 11:40:31 2021 +0000
+++ b/style.sty	Wed Dec 15 19:00:01 2021 +0000
@@ -78,7 +78,7 @@
 \def\cwONE{18 October}
 \def\cwTWO{\textcolor{red}{11 November}}  % 8 November
 \def\cwTHREE{\textcolor{red}{3 December}} %29 November
-\def\cwFOUR{13 December}
+\def\cwFOUR{\textcolor{red}{17 December}}
 \def\cwFIVE{24 January}
 
 \def\cwISABELLE{11 December}

author	Christian Urban <christian.urban@kcl.ac.uk>
	Wed, 15 Dec 2021 19:00:01 +0000
changeset 864	b5b1bc0a603b
parent 863	d59bcff69998
child 865	bc2a862a00d4

slides/slides09.tex		file \| annotate \| diff \| comparison \| revisions
slides/slides10.pdf		file \| annotate \| diff \| comparison \| revisions
slides/slides10.tex		file \| annotate \| diff \| comparison \| revisions
solution/cw1/matcher.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw2/collatz.while		file \| annotate \| diff \| comparison \| revisions
solution/cw2/collatz2.while		file \| annotate \| diff \| comparison \| revisions
solution/cw2/factors.while		file \| annotate \| diff \| comparison \| revisions
solution/cw2/fib.while		file \| annotate \| diff \| comparison \| revisions
solution/cw2/lexer.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw2/loops.while		file \| annotate \| diff \| comparison \| revisions
solution/cw2/primes.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/collatz.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/collatz2.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/factors.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/fib.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/lexer.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw3/loops.while		file \| annotate \| diff \| comparison \| revisions
solution/cw3/parser.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw3/parser2.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw3/primes.while		file \| annotate \| diff \| comparison \| revisions
solution/cw4/collatz2.while		file \| annotate \| diff \| comparison \| revisions
solution/cw4/compiler.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw4/fib.while		file \| annotate \| diff \| comparison \| revisions
solution/cw4/lexer.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw4/parser.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw5/fact.fun		file \| annotate \| diff \| comparison \| revisions
solution/cw5/fun_llvm.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw5/fun_parser.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw5/fun_tokens.sc		file \| annotate \| diff \| comparison \| revisions
solution/cw5/hanoi.fun		file \| annotate \| diff \| comparison \| revisions
solution/cw5/mand.fun		file \| annotate \| diff \| comparison \| revisions
solution/cw5/mand2.fun		file \| annotate \| diff \| comparison \| revisions
solution/cw5/sqr.fun		file \| annotate \| diff \| comparison \| revisions
style.sty		file \| annotate \| diff \| comparison \| revisions