% !TEX program = xelatex

\documentclass{article}

\usepackage{../styles/style}

\usepackage{../styles/langs}

\usepackage{disclaimer}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{pgfplots}

\usepackage{stackengine}

\usepackage{scalerel}

\DeclareMathOperator*{\amp}{\scalerel*{\&}{\sum}}

%% \usepackage{accents}

\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}

\begin{filecontents}{re-python2.data}

1 0.033

5 0.036

10 0.034

15 0.036

18 0.059

19 0.084 

20 0.141

21 0.248

22 0.485

23 0.878

24 1.71

25 3.40

26 7.08

27 14.12

28 26.69

\end{filecontents}

\begin{filecontents}{re-java.data}

5  0.00298

10  0.00418

15  0.00996

16  0.01710

17  0.03492

18  0.03303

19  0.05084

20  0.10177

21  0.19960

22  0.41159

23  0.82234

24  1.70251

25  3.36112

26  6.63998

27  13.35120

28  29.81185

\end{filecontents}

\begin{filecontents}{re-js.data}

5   0.061

10  0.061

15  0.061

20  0.070

23  0.131

25  0.308

26  0.564

28  1.994

30  7.648

31  15.881 

32  32.190

\end{filecontents}

\begin{filecontents}{re-java9.data}

1000  0.01410

2000  0.04882

3000  0.10609

4000  0.17456

5000  0.27530

6000  0.41116

7000  0.53741

8000  0.70261

9000  0.93981

10000 0.97419

11000 1.28697

12000 1.51387

14000 2.07079

16000 2.69846

20000 4.41823

24000 6.46077

26000 7.64373

30000 9.99446

34000 12.966885

38000 16.281621

42000 19.180228

46000 21.984721

50000 26.950203

60000 43.0327746

\end{filecontents}

\begin{filecontents}{re-swift.data}

5   0.001

10  0.001

15  0.009

20  0.178

23  1.399

24  2.893

25  5.671

26  11.357

27  22.430

\end{filecontents}

\begin{filecontents}{re-dart.data}

20 0.042

21 0.084

22 0.190

23 0.340

24 0.678

25 1.369

26 2.700

27 5.462

28 10.908

29 21.725

30 43.492

\end{filecontents}

\begin{document}

% BF IDE

% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5

\section*{Main Part 3 (Scala, 6 Marks)}

\mbox{}\hfill\textit{``Java is the most distressing thing to happen to computing since MS-DOS.''}\smallskip\\

\mbox{}\hfill\textit{ --- Alan Kay, the inventor of object-oriented programming}\bigskip\medskip

\noindent

This part is about a regular expression matcher described by

Brzozowski in 1964.  The

background is that ``out-of-the-box'' regular expression matching in

mainstream languages like Java, JavaScript and Python can sometimes be

excruciatingly slow.  You are supposed to implement a regular

expression matcher that is much, much faster. \bigskip

\IMPORTANTNONE{}

\noindent

Also note that the running time of each part will be restricted to a

maximum of 30 seconds on my laptop.  

\DISCLAIMER{}

\subsection*{Reference Implementation}

This Scala assignment comes with a reference implementation in form of

a \texttt{jar}-file. This allows you to run any test cases on your own

computer. For example you can call \texttt{scala} on the command

line with the option \texttt{--extra-jars re.jar} and then query any function

from the \texttt{re.scala} template file. As usual you have to prefix

the calls with \texttt{M3} or import this object.  Since some tasks

are time sensitive, you can check the reference implementation as

follows: if you want to know, for example, how long it takes to match

strings of $a$'s using the regular expression $(a^*)^*\cdot b$ you can

query as follows:

\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

$ scala --extra-jars re.jar

scala> import M3._  

scala> for (i <- 0 to 5000000 by 500000) {

  println(s"$i: ${time_needed(2, matcher(EVIL, "a" * i))}")

}

0: 0.00002 secs.

500000: 0.10608 secs.

1000000: 0.22286 secs.

1500000: 0.35982 secs.

2000000: 0.45828 secs.

2500000: 0.59558 secs.

3000000: 0.73191 secs.

3500000: 0.83499 secs.

4000000: 0.99149 secs.

4500000: 1.15395 secs.

5000000: 1.29659 secs.

\end{lstlisting}%$

\noindent

For this you need to copy the \texttt{time\_needed} function and the \texttt{EVIL} regular

expression from the comments given in \texttt{re.scala}.

\subsection*{Preliminaries}

The task is to implement a regular expression matcher that is based on

derivatives of regular expressions. Most of the functions are defined by

recursion over regular expressions and can be elegantly implemented

using Scala's pattern-matching. The implementation should deal with the

following regular expressions, which have been predefined in the file

\texttt{re.scala}:

\begin{center}

\begin{tabular}{lcll}

  $r$ & $::=$ & $\ZERO$     & cannot match anything\\

      &   $|$ & $\ONE$      & can only match the empty string\\

      &   $|$ & $c$         & can match a single character (in this case $c$)\\

      &   $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\

      &   $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\

          &  & & then the second part with $r_2$\\

      &   $|$ & $r_1 \,\&\, r_2$ & has to match a string with both $r_1$ and $r_2$\\

      &   $|$ & $r^*$       & can match a string with zero or more copies of $r$\\

      &   $|$ & $r^{\{n\}}$  & can match a string with exactly n copies of $r$\\

\end{tabular}

\end{center}

\noindent 

Why? Regular expressions are

one of the simplest ways to match patterns in text, and

are endlessly useful for searching, editing and analysing data in all

sorts of places (for example analysing network traffic in order to

detect security breaches). However, you need to be fast, otherwise you

will stumble over problems such as reported in

{\small

\begin{itemize}

\item[$\bullet$] \url{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019}  

\item[$\bullet$] \texttt{\href{https://web.archive.org/web/20160801163029/https://www.stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}}

\item[$\bullet$] \url{https://vimeo.com/112065252}

\item[$\bullet$] \url{https://davidvgalbraith.com/how-i-fixed-atom}  

\end{itemize}}

% Knowing how to match regular expressions and strings will let you

% solve a lot of problems that vex other humans.

\subsubsection*{Tasks (file re.scala)}

The file \texttt{re.scala} has already a definition for regular

expressions and also defines some handy shorthand notation for regular

expressions. The notation in this coursework description matches up

with the code as follows:

\begin{center}

  \begin{tabular}{rcl@{\hspace{10mm}}l}

    & & code: & shorthand:\smallskip \\ 

  $\ZERO$ & $\mapsto$ & \texttt{ZERO}\\

  $\ONE$  & $\mapsto$ & \texttt{ONE}\\

  $c$     & $\mapsto$ & \texttt{CHAR(c)}\\

  $r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\

  $r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\

  $r_1 \,\&\, r_2$ & $\mapsto$ & \texttt{AND(r1, r2)}\\

  $r^*$ & $\mapsto$ &  \texttt{STAR(r)} & \texttt{r.\%}\\

  $r^{\{n\}}$ & $\mapsto$ &  \texttt{REP(r, n)} & 

\end{tabular}    

\end{center}  

\begin{itemize}

\item[(1)] Implement a function, called \textit{nullable}, by

  recursion over regular expressions. This function tests whether a

  regular expression can match the empty string. This means given a

  regular expression, it either returns true or false. The function

  \textit{nullable}

  is defined as follows:

\begin{center}

\begin{tabular}{lcl}

$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\

$\textit{nullable}(\ONE)$  & $\dn$ & $\textit{true}$\\

$\textit{nullable}(c)$     & $\dn$ & $\textit{false}$\\

$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee  \textit{nullable}(r_2)$\\

$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge  \textit{nullable}(r_2)$\\

$\textit{nullable}(r_1 \& r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge  \textit{nullable}(r_2)$\\

$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\

$\textit{nullable}(r^{\{n\}})$ & $\dn$ & 

$\begin{cases}\textit{true} & n = 0\\

\textit{nullable}(r) & \textit{otherwise}

\end{cases}$\\

\end{tabular}

\end{center}~\hfill[0.5 Marks]

\item[(2)] Implement a function, called \textit{der}, by recursion over

  regular expressions. It takes a character and a regular expression

  as arguments and calculates the \emph{derivative} of a regular expression according

  to the rules:

\begin{center}

\begin{tabular}{lcl}

$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\

$\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\

$\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\

$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\

$\textit{der}\;c\;(r_1 \& r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) \,\&\, (\textit{der}\;c\;r_2)$\\

$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\

      & & $\textit{then}\;(\textit{der}\;c\;r_1)\cdot r_2 \,+\, (\textit{der}\;c\;r_2)$\\

      & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\

$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\

$\textit{der}\;c\;(r^{\{n\}})$ & $\dn$ & 

$\begin{cases}\ZERO & n = 0\\

(der\,c\,r)\cdot (r^{\{n-1\}}) & \textit{otherwise}

\end{cases}$\\

\end{tabular}

\end{center}

\mbox{}\hfill\mbox{[1.5 Marks]}

% \item[(3)] We next want to simplify regular expressions: essentially

%   we want to remove $\ZERO$ in regular expressions like $r + \ZERO$

%   and $\ZERO + r$.  However, our n-ary alternative takes a list of

%   regular expressions as argument, and we therefore need a more general

%   ``denesting'' function, which deletes $\ZERO$s and ``spills out'' nested

%   $\sum$s.  This function, called \texttt{denest}, should analyse a

%   list of regular expressions, say $rs$, as follows:

%   \begin{center}

%     \begin{tabular}{lllll}

%       1) &$rs = []$                & $\dn$ & $[]$ & (empty list)\\

%       2) &$rs = \ZERO :: rest$     & $\dn$ & $\texttt{denest}\;rest$ & (throw away $\ZERO$)\\

%       3) &$rs = (\sum rs) :: rest$ & $\dn$ & $rs ::: \texttt{denest}\;rest$ & (spill out $\sum$)\\

%       4) &$rs = r :: rest$         & $\dn$ & $r :: \texttt{denest}\;rest$ & (otherwise)\\

%     \end{tabular}  

%   \end{center}  

%   The first clause states that empty lists cannot be further

%   denested. The second removes the first $\ZERO$ from the list and recurses.

%   The third is when the first regular expression is an \texttt{ALTs}, then

%   the content of this alternative should be spilled out and appended

%   with the denested rest of the list. The last case is for all other

%   cases where the head of the list is not $\ZERO$ and not an \texttt{ALTs},

%   then we just keep the head of the list and denest the rest.\\

%   \mbox{}\hfill\mbox{[1 Mark]}

\item[(3)] Implement the function \textit{simp}, which recursively

  traverses a regular expression, and on the way up simplifies every

  regular expression on the left (see below) to the regular expression

  on the right, except it does not simplify inside ${}^*$ and ${}^{\{n\}}$-regular

  expressions.

  \begin{center}

\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}

$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ 

$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ 

$r \cdot \ONE$ & $\mapsto$ & $r$\\ 

$\ONE \cdot r$ & $\mapsto$ & $r$\\ 

$r + \ZERO$ & $\mapsto$ & $r$\\ 

$\ZERO + r$ & $\mapsto$ & $r$\\ 

$r + r$ & $\mapsto$ & $r$\\ 

$r \,\&\, \ZERO$ & $\mapsto$ & $\ZERO$\\ 

$\ZERO \,\&\, r$ & $\mapsto$ & $\ZERO$\\ 

$r \,\&\, r$ & $\mapsto$ & $r$\\ 

\end{tabular}

  \end{center}

  For example the regular expression

  \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \,\&\, (r_4 \cdot \ZERO)\]

  simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be

  seen as trees and there are several methods for traversing

  trees. One of them corresponds to the inside-out traversal, which is also

  sometimes called post-order tra\-versal: you traverse inside the

  tree and on the way up you apply simplification rules.

  \textbf{Another Hint:}

  Remember numerical expressions from school times---there you had expressions

  like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$

  and simplification rules that looked very similar to rules

  above. You would simplify such numerical expressions by replacing

  for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then

  look whether more rules are applicable. If you organise the

  simplification in an inside-out fashion, it is always clear which

  simplification should be applied next.\hfill[2 Marks]

% \item[(4)] Implement the function \texttt{flts} which flattens our

%   n-ary sequence regular expression $\prod$. Like \texttt{denest}, this

%   function is intended to delete $\ONE$s and spill out nested $\prod$s.

%   Unfortunately, there is a special case to do with $\ZERO$: If this function encounters a $\ZERO$, then

%   the whole ``product'' should be $\ZERO$. The problem is that the $\ZERO$ can be anywhere

%   inside the list. The easiest way to implement this function is therefore by using an

%   accumulator, which when called is set to \texttt{Nil}. This means \textit{flts} takes

%   two arguments (which are both lists of regular expressions)

%   \[

%   \texttt{flts}\;rs\;acc  

%   \]

%   This function analyses the list $rs$ as follows

%   \begin{center}

%     \begin{tabular}{@{}lllll@{}}

%       1) &$rs = []$                   & $\dn$ & $acc$ & (empty list)\\

%       2) &$rs = \ZERO :: rest$        & $\dn$ & $[\ZERO]$ & (special case for $\ZERO$)\\

%       3) &$rs = \ONE :: rest$         & $\dn$ & $\texttt{flts}\,rest\,acc$ & (throw away $\ONE$)\\

%       4) &$rs = (\prod rs) :: rest$ & $\dn$ & $\texttt{flts}\;rest\,(acc ::: rs)$ & (spill out $\prod$)\\

%       5) &$rs = r :: rest$            & $\dn$ & $\texttt{flts}\;rest\,(acc ::: [r])$& (otherwise)\\

%     \end{tabular}  

%   \end{center}

%   In the first case we just return whatever has accumulated in

%   $acc$. In the fourth case we spill out the $rs$ by appending the

%   $rs$ to the end of the accumulator. Similarly in the last case we

%   append the single regular expression $r$ to the end of the

%   accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]}

% \item[(5)] Before we can simplify regular expressions, we need what is often called

%   \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors

%   \texttt{ALTs} and \texttt{SEQs} give us alternatives and sequences, respectively, \emph{smart}

%   constructors might return something different depending on what list of regular expressions

%   they are given as argument.

%   \begin{center}

%   \begin{tabular}{@{}c@{\hspace{9mm}}c@{}}

%     \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}

%       & $\sum^{smart}$\smallskip\\

%       1) & $rs = []$  & $\dn$ & $\ZERO$\\ 

%       2) & $rs = [r]$ & $\dn$ & $r$\\ \\

%       3) & otherwise  & $\dn$ & $\sum\,rs$

%     \end{tabular} &

%     \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}

%         & $\prod^{smart}$\smallskip\\              

%         1) & $rs = []$ & $\dn$ & $\ONE$\\

%         2a) & $rs = [\ZERO]$ & $\dn$ & $\ZERO$\\

%         2b) & $rs = [r]$ & $\dn$ & $r$\\

%         3) & otherwise  & $\dn$ & $\prod\,rs$

%     \end{tabular}              

%   \end{tabular}    

%   \end{center}

%   \mbox{}\hfill\mbox{[0.5 Marks]}

% \item[(6)] Implement the function \textit{simp}, which recursively

%   traverses a regular expression, and on the way up simplifies every

%   regular expression on the left (see below) to the regular expression

%   on the right, except it does not simplify inside ${}^*$-regular

%   expressions and also does not simplify $\ZERO$, $\ONE$ and characters.

%   \begin{center}

%     \begin{tabular}{@{}l@{\hspace{3mm}}c@{\hspace{3mm}}ll@{}}

%       LHS: & & RHS:\smallskip\\

% $\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum^{smart}\;(\texttt{(denest + distinct)}[simp(r_1),..,simp(r_n)])$\\

%       $\prod\;[r_1,..,r_n]$ & $\mapsto$ & $\prod^{smart}\;(\texttt{(flts)}[simp(r_1),..,simp(r_n)])$\\

%       $r$ & $\mapsto$ & $r$ \quad (all other cases)

% \end{tabular}

% \end{center}

% The first case is as follows: first apply $simp$ to all regular

% expressions $r_1,.. ,r_n$; then denest the resulting list using

% \texttt{denest}; after that remove all duplicates in this list (this can be

% done in Scala using the function

% \texttt{\_.distinct}). Finally, you end up with a list of (simplified)

% regular expressions; apply the smart constructor $\sum^{smart}$ to this list.

% Similarly in the $\prod$ case: simplify first all regular

% expressions $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts} and apply the

% smart constructor $\prod^{smart}$ to the result. In all other cases, just return the

% input $r$ as is.

%   For example the regular expression

%   \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]

%   simplifies to just $r_1$. \mbox{}\hfill\mbox{[1 Mark]}

\item[(4)] Implement two functions: The first, called \textit{ders},

  takes a list of characters and a regular expression as arguments, and

  builds the derivative w.r.t.~the list as follows:

\begin{center}

\begin{tabular}{lcl}

$\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\

  $\textit{ders}\;(c::cs)\;r$  & $\dn$ &

    $\textit{ders}\;cs\;(\textit{simp}\,(\textit{der}\;c\;r))$\\

\end{tabular}

\end{center}

Note that this function is different from \textit{der}, which only

takes a single character.

The second function, called \textit{matcher}, takes a string and a

regular expression as arguments. It builds first the derivatives

according to \textit{ders} and after that tests whether the resulting

derivative regular expression can match the empty string (using

\textit{nullable}).  For example the \textit{matcher} will produce

true for the regular expression $(a\cdot b)\cdot c$ and the string

$abc$, but false if you give it the string $ab$. \hfill[0.5 Mark]

\item[(5)] Implement a function, called \textit{size}, by recursion

  over regular expressions. If a regular expression is seen as a tree,

  then \textit{size} should return the number of nodes in such a

  tree. Therefore this function is defined as follows:

\begin{center}

\begin{tabular}{lcll}

$\textit{size}(\ZERO)$ & $\dn$ & $1$\\

$\textit{size}(\ONE)$  & $\dn$ & $1$\\

$\textit{size}(c)$     & $\dn$ & $1$\\

$\textit{size}(r_1 \,?\, r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$ & where $? \in \{\cdot, +, \&\}$\\

$\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\

$\textit{size}(r^{\{n\}})$ & $\dn$ & $1 + \textit{size}(r)$\\

\end{tabular}

\end{center}

You can use \textit{size} in order to test how much the ``evil'' regular

expression $(a^*)^* \cdot b$ grows when taking successive derivatives