# HG changeset patch # User Christian Urban # Date 1601194532 -3600 # Node ID 6718ef6143b8fbc8f2d17428c0608571528263ac # Parent 4e628958c01a25a9166b3afd59c1e1efd5ef35f1 updated diff -r 4e628958c01a -r 6718ef6143b8 LINKS --- 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 diff -r 4e628958c01a -r 6718ef6143b8 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 4e628958c01a -r 6718ef6143b8 handouts/ho02.tex --- 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) \] diff -r 4e628958c01a -r 6718ef6143b8 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 4e628958c01a -r 6718ef6143b8 handouts/ho03.tex --- 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: diff -r 4e628958c01a -r 6718ef6143b8 progs/app5.scala --- 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)) diff -r 4e628958c01a -r 6718ef6143b8 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 4e628958c01a -r 6718ef6143b8 slides/slides02.tex --- 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}