--- a/LINKS	Sat Sep 26 23:45:40 2020 +0100
+++ b/LINKS	Sun Sep 27 09:15:32 2020 +0100
@@ -22,6 +22,10 @@
 https://flix.github.io/#/research/
 https://flix.github.io/#/principles/
 
+================
+Compiler course in Edinburgh
+
+http://www.inf.ed.ac.uk/teaching/courses/ct/19-20/
 
 =================
 General tail call elimination on the JVM

Binary file handouts/ho02.pdf has changed

--- a/handouts/ho02.tex	Sat Sep 26 23:45:40 2020 +0100
+++ b/handouts/ho02.tex	Sun Sep 27 09:15:32 2020 +0100
@@ -32,7 +32,7 @@
 regular expression $(a^*)^*\cdot b$ and strings composed of $n$
 \pcode{a}s, like
 \[
-\pcode{"}\!\underbrace{\pcode{a}\ldots\pcode{a}}_{n}\!\pcode{"}  
+\underbrace{\pcode{a}\ldots\pcode{a}}_{n} 
 \]
 
 \noindent
@@ -480,14 +480,14 @@
 algorithm:
 
 \[
-\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r)
+\textit{matcher}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r)
 \]
 
 \noindent
 and we can claim that
 
 \[
-\textit{matches}\,r\,s\quad\text{if and only if}\quad s\in L(r)
+\textit{matcher}\,r\,s\quad\text{if and only if}\quad s\in L(r)
 \]
 
 \noindent holds, which means our algorithm satisfies the
@@ -508,7 +508,7 @@
 implemented in a functional programming language, like Scala.
 Given the implementation of regular expressions in Scala shown
 in the first lecture and handout, the functions and subfunctions
-for \pcode{matches} are shown in Figure~\ref{scala1}.
+for \pcode{matcher} are shown in Figure~\ref{scala1}.
 
 \begin{figure}[p]
   \lstinputlisting[numbers=left,linebackgroundcolor=
@@ -1045,16 +1045,16 @@
 \textit{nullable}(\textit{ders}\,s\,r)
 \] 
 
-\noindent But this is just the definition of $matches$
+\noindent But this is just the definition of $matcher$
 
 \[
-matches\,s\,r \dn nullable(\textit{ders}\,s\,r)
+matcher\,s\,r \dn nullable(\textit{ders}\,s\,r)
 \]
 
 \noindent In effect we have shown
 
 \[
-matches\,s\,r\;\;\text{if and only if}\;\;
+matcher\,s\,r\;\;\text{if and only if}\;\;
 s\in L(r)
 \]
 

Binary file handouts/ho03.pdf has changed

--- a/handouts/ho03.tex	Sat Sep 26 23:45:40 2020 +0100
+++ b/handouts/ho03.tex	Sun Sep 27 09:15:32 2020 +0100
@@ -1560,40 +1560,68 @@
 
 \subsection*{Where Have Derivatives Gone?}
 
-Still to be done\bigskip
+%%Still to be done\bigskip
+
+\noindent
+By now you are probably fed up with this text. It is now way too long
+for one lecture, but there is still one aspect of the
+automata-regular-expression-connection I like to describe:\medskip
 
-%\noindent
-%By now you are probably fed up with this text. It is now way too long
-%for one lecture, but there is still one aspect of the
-%automata-regular-expression-connection I like to describe. Perhaps by
-%now you are asking yourself: Where have the derivatives gone? Did we
-%just forget them?  Well, they have a place in the picture of
-%calculating a DFA from the regular expression.
+\noindent
+Where have the derivatives gone? Did we just forget them?  Well, they
+actually do play a role of generating a DFA from a regular expression.
+And we can also see this in our implementation\ldots{}because there is
+one flaw in our representation of automata and transitions as partial
+functions. We can represent automata with infinite states, which is
+actually forbidden by the definition of what an automaton is. We can
+exploit this flaw as follows: Suppose our alphabet consists of the
+characters $c_1$ to $c_n$. Then we can generate an ``automaton''
+(it is not really one because it has infinite states) by taking
+as starting state the regular expression $r$ for which we
+want to generate an automaton. There are $n$ next-states which
+corresponds to the derivatives of $r$ according to $c_1$ to $c_n$.
+Implementing this in our slightly ``flawed'' representation is
+not too difficult. This will give a picture for the ``automaton''
+looking something like this, except that it extends infinitely
+far to the right:
+
 
-%To be done
-%
-%\begin{center}
-%\begin{tikzpicture}
-%  [level distance=25mm,very thick,auto,
-%   level 1/.style={sibling distance=30mm},
-%   level 2/.style={sibling distance=15mm},
-%   every node/.style={minimum size=30pt,
-%                    inner sep=0pt,circle,draw=blue!50,very thick,
-%                    fill=blue!20}]
-%  \node {$r$} [grow=right]
-%  child[->] {node (cn) {$d_{c_n}$}
-%    child { node {$dd_{c_nc_n}$}}
-%    child { node {$dd_{c_nc_1}$}}
-%    %edge from parent node[left] {$c_n$}
-%  }
-%  child[->] {node (c1) {$d_{c_1}$}
-%    child { node {$dd_{c_1c_n}$}}
-%    child { node {$dd_{c_1c_1}$}}
-%    %edge from parent node[left] {$c_1$}
-%  };
-%  %%\draw (cn) -- (c1) node {\vdots}; 
-%\end{tikzpicture}  
-%\end{center}
+\begin{center}
+\begin{tikzpicture}
+ [level distance=25mm,very thick,auto,
+  level 1/.style={sibling distance=30mm},
+  level 2/.style={sibling distance=15mm},
+  every node/.style={minimum size=30pt,
+                   inner sep=0pt,circle,draw=blue!50,very thick,
+                   fill=blue!20}]
+ \node {$r$} [grow=right]
+ child[->] {node (cn) {$d_{c_n}$}
+   child { node {$dd_{c_nc_n}$}}
+   child { node {$dd_{c_nc_1}$}}
+   %edge from parent node[left] {$c_n$}
+ }
+ child[->] {node (c1) {$d_{c_1}$}
+   child { node {$dd_{c_1c_n}$}}
+   child { node {$dd_{c_1c_1}$}}
+   %edge from parent node[left] {$c_1$}
+ };
+ %%\draw (cn) -- (c1) node {\vdots}; 
+\end{tikzpicture}  
+\end{center}
+
+\noindent
+I let you implement this ``automaton''.
+
+While this makes all sense (modulo the flaw with the infinite states),
+does this automaton teach us anything? The answer is no, because it
+boils down to just another implementation of the Brzozowski
+algorithm. There \emph{is} something interesting in this construction
+which Brzozowski already cleverly found out, because there is
+a way to restrict the number of states to something finite.
+However, this would lead us far, far away from what we should
+discuss here.
+
+
 
 %\section*{Further Reading}
 
@@ -1601,7 +1629,6 @@
 %regular expression $a\cdot (b + c)^*$ and what the Thomson
 %algorithm generates.
 
-%http://www.inf.ed.ac.uk/teaching/courses/ct/
 \end{document}
 
 %%% Local Variables: 

--- a/progs/app5.scala	Sat Sep 26 23:45:40 2020 +0100
+++ b/progs/app5.scala	Sun Sep 27 09:15:32 2020 +0100
@@ -23,5 +23,5 @@
   case c::s => ders(s, der(c, r))
 }
 
-def matches(r: Rexp, s: String) : Boolean = 
+def matcher(r: Rexp, s: String) : Boolean = 
   nullable(ders(s.toList, r))

Binary file slides/slides02.pdf has changed

--- a/slides/slides02.tex	Sat Sep 26 23:45:40 2020 +0100
+++ b/slides/slides02.tex	Sun Sep 27 09:15:32 2020 +0100
@@ -5,6 +5,13 @@
 \usepackage{../langs}
 \usepackage{../data}
 
+\usepackage{tcolorbox}
+\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+
+
+
 \hfuzz=220pt 
 
 \lstset{language=Scala,
@@ -244,6 +251,44 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification Example}
+
+%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}  
+\begin{tabular}{@{}lcl}
+  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+    & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification Example}
+
+%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}  
+\begin{tabular}{@{}lcl}
+  \bl{$((\ZERO \cdot b) + \ZERO) \cdot r$}
+    & \bl{$\Rightarrow$} & \bl{$((\underline{\ZERO \cdot b}) + \ZERO) \cdot r$}\\
+    & \bl{$=$} & \bl{$(\underline{\ZERO + \ZERO}) \cdot r$}\\
+    & \bl{$=$} & \bl{$\ZERO \cdot r$}\\
+    & \bl{$=$} & \bl{$\ZERO$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
@@ -377,14 +422,43 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\mbox{The Brzozowski Algorithm}}
+\frametitle{Derivative Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
 
 \begin{center}
-\begin{tabular}{l} 
-\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}  
+\def\arraystretch{1.5}  
+\begin{tabular}{@{}lcl}
+  \bl{$\der\,a\,((a \cdot b) + b)^*$}
+    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
 \end{tabular}
 \end{center}
 
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{The Brzozowski Algorithm}}
+
+%\begin{center}
+%\begin{tabular}{l} 
+%\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}  
+%\end{tabular}
+%\end{center}
+
+\begin{center}
+\begin{mybox3}{}
+\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}
+\end{mybox3}
+\end{center}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%
@@ -431,6 +505,22 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Idea with Derivatives}
+  
+Input: string \bl{$abc$} and regular expression \bl{$r$}\medskip 
+
+\begin{enumerate}
+\item \bl{$der\,a\,r$}
+\item \bl{$der\,b\,(der\,a\,r)$}
+\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
+\item finally check whether the last regular expression can match the empty string
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -776,15 +866,15 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Coursework}
+\frametitle{Coursework 1}
 
-\underline{Strand 1:}
+%%\underline{Strand 1:}
 
 \begin{itemize}
-\item Submission on Friday 11 October\\accepted until Monday 14 @ 18:00\medskip
+\item Submission on Friday 16 October @ 18:00\medskip
 \item source code needs to be submitted as well\medskip
 \item you can re-use my Scala code from KEATS \\
-  or use any programming language you like\medskip
+  and use any programming language you like\medskip
 \item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
 \end{itemize}  
 
@@ -792,7 +882,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 \begin{frame}[t]
 \frametitle{Proofs about Rexps}
 
@@ -893,7 +983,7 @@
 \begin{tabular}{rp{4cm}}
 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
-\bl{$\dn$} & \bl{$matches\,s\,r$}
+\bl{$\dn$} & \bl{$matcher\,s\,r$}
 \end{tabular}
 \end{center}
 
@@ -951,7 +1041,7 @@
 We can finally prove
 
 \begin{center}
-\bl{$matches\,s\,r$}  if and only if  \bl{$s \in L(r)$} 
+\bl{$matcher\,s\,r$}  if and only if  \bl{$s \in L(r)$} 
 \end{center}
 
 
@@ -1042,10 +1132,10 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
 
-\bigskip
-homework (written exam 80\%)\\
-coursework (20\%; first one today)\\
-submission Fridays @ 18:00 -- accepted until Mondays
+%\bigskip
+%homework (written exam 80\%)\\
+%coursework (20\%; first one today)\\
+%submission Fridays @ 18:00 -- accepted until Mondays
 \mbox{}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
@@ -1062,7 +1152,7 @@
 started with the proving part though)
 
 \begin{center}
-\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
+\bl{$matcher\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
 \end{center}\bigskip\bigskip 
 
 \small
@@ -1071,86 +1161,11 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Derivative of a Rexp}
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
-  \bl{$der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\
-  \bl{$der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\
-  \bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
-  \bl{$der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
-  \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
-  & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 
-  & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
-  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
-
-  \bl{$\textit{ders}\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
-  \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
-  \end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Example}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
-
-\begin{center}
-\def\arraystretch{1.5}  
-\begin{tabular}{@{}lcl}
-  \bl{$\der\,a\,((a \cdot b) + b)^*$}
-    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
-    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
-    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
-    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
-    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
-    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
 
-Input: string \bl{$abc$} and regular expression \bl{$r$} 
-
-\begin{enumerate}
-\item \bl{$der\,a\,r$}
-\item \bl{$der\,b\,(der\,a\,r)$}
-\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
-\item finally check whether the last regular expression can match the empty string
-\end{enumerate}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Simplification}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
-
-\begin{center}
-\def\arraystretch{2}  
-\begin{tabular}{@{}lcl}
-  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
-    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
-    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
-    & \bl{$=$} & \bl{$b \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+ 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -1230,7 +1245,7 @@
   \begin{tabular}{rp{4cm}}
   \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
   \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
-  \bl{$\dn$} & \bl{$matches\,s\,r$}
+  \bl{$\dn$} & \bl{$matcher\,s\,r$}
   \end{tabular}
   \end{center}