\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage{tikz}

\usepackage{pgf}

\usepackage{pgfplots}

\usepackage{stackengine}

\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

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-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{document}

\section*{Coursework 8 (Regular Expressions and Brainf***)}

This coursework is worth 10\%. It is about regular expressions,

pattern matching and an interpreter. The first part is due on 30

November at 11pm; the second, more advanced part, is due on 21

December at 11pm. In the first part, you are asked to implement a

regular expression matcher based on derivatives of regular

expressions. The reason is that regular expression matching in Java

and Python can sometimes be extremely slow. The advanced part is about

an interpreter for a very simple programming language.\bigskip

\noindent

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

\subsection*{Part 1 (6 Marks)}

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^*$       & can match zero or more times $r$\\

\end{tabular}

\end{center}

\noindent 

Why? Knowing how to match regular expressions and strings will let you

solve a lot of problems that vex other humans. Regular expressions are

one of the fastest and 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 recently reported at

{\small

\begin{itemize}

\item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}

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

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

\end{itemize}}

\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 document matches up

with the code in the file 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^*$ & $\mapsto$ &  \texttt{STAR(r)} & \texttt{r.\%}

\end{tabular}    

\end{center}  

\begin{itemize}

\item[(1a)] 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^*)$ & $\dn$ & $\textit{true}$\\

\end{tabular}

\end{center}~\hfill[1 Mark]

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

  regular expressions. It takes a character and a regular expression

  as arguments and calculates the derivative 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 \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^*)$\\

\end{tabular}

\end{center}

For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives

w.r.t.~the characters $a$, $b$ and $c$ are

\begin{center}

  \begin{tabular}{lcll}

    $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & ($= r'$)\\

    $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\

    $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$

  \end{tabular}

\end{center}

Let $r'$ stand for the first derivative, then taking the derivatives of $r'$

w.r.t.~the characters $a$, $b$ and $c$ gives

\begin{center}

  \begin{tabular}{lcll}

    $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\

    $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & ($= r''$)\\

    $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$

  \end{tabular}

\end{center}

One more example: Let $r''$ stand for the second derivative above,

then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$

and $c$ gives

\begin{center}

  \begin{tabular}{lcll}

    $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\

    $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\

    $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &

    (is $\textit{nullable}$)                      

  \end{tabular}

\end{center}

Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\

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

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

  traverses a regular expression from the inside to the outside, and

  on the way simplifies every regular expression on the left (see

  below) to the regular expression on the right, except it does not

  simplify inside ${}^*$-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$\\ 

\end{tabular}

  \end{center}

  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$. \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

  sometimes also called post-order traversal. Furthermore,

  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

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

\item[(1d)] 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[1 Mark]

\item[(1e)] 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}{lcl}

$\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)$\\

$\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\

$\textit{size}(r^*)$ & $\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

according the letter $a$ without simplification and then compare it to

taking the derivative, but simplify the result.  The sizes

are given in \texttt{re.scala}. \hfill[1 Mark]

\end{itemize}

\subsection*{Background}

Although easily implementable in Scala, the idea behind the derivative

function might not so easy to be seen. To understand its purpose

better, assume a regular expression $r$ can match strings of the form

$c\!::\!cs$ (that means strings which start with a character $c$ and have

some rest, or tail, $cs$). If you take the derivative of $r$ with

respect to the character $c$, then you obtain a regular expression

that can match all the strings $cs$.  In other words, the regular

expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$

that can be matched by $r$, except that the $c$ is chopped off.

Assume now $r$ can match the string $abc$. If you take the derivative

according to $a$ then you obtain a regular expression that can match

$bc$ (it is $abc$ where the $a$ has been chopped off). If you now

build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you

obtain a regular expression that can match the string $c$ (it is $bc$

where $b$ is chopped off). If you finally build the derivative of this

according $c$, that is

$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain

a regular expression that can match the empty string. You can test

whether this is indeed the case using the function nullable, which is

what your matcher is doing.

The purpose of the $\textit{simp}$ function is to keep the regular

expressions small. Normally the derivative function makes the regular

expression bigger (see the SEQ case and the example in (1b)) and the

algorithm would be slower and slower over time. The $\textit{simp}$

function counters this increase in size and the result is that the

algorithm is fast throughout.  By the way, this algorithm is by Janusz

Brzozowski who came up with the idea of derivatives in 1964 in his PhD

thesis.

\begin{center}\small

\url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}

\end{center}

If you want to see how badly the regular expression matchers do in

Java\footnote{Version 8 and below; Version 9 does not seem to be as

  catastrophic, but still worse than the regular expression matcher

based on derivatives.} and in Python with the `evil' regular

expression $(a^*)^*\cdot b$, then have a look at the graphs below (you

can try it out for yourself: have a look at the file

\texttt{catastrophic.java} and \texttt{catastrophic.py} on

KEATS). Compare this with the matcher you have implemented. How long

can the string of $a$'s be in your matcher and still stay within the

30 seconds time limit?

\begin{center}

\begin{tabular}{@{}cc@{}}

\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings 

           $\underbrace{a\ldots a}_{n}$}\bigskip\\

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    y label style={at={(0.06,0.5)}},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=33,

    ymax=45,

    ytick={0,5,...,40},

    scaled ticks=false,

    axis lines=left,

    width=6cm,

    height=5.5cm, 

    legend entries={Python, Java 8},  

    legend pos=north west]

\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};

\end{axis}

\end{tikzpicture}

  & 

\begin{tikzpicture}

\begin{axis}[

    xlabel={$n$},

    x label style={at={(1.05,0.0)}},

    ylabel={time in secs},

    y label style={at={(0.06,0.5)}},

    %enlargelimits=false,

    %xtick={0,5000,...,30000},

    xmax=65000,

    ymax=45,

    ytick={0,5,...,40},

    scaled ticks=false,

    axis lines=left,

    width=6cm,

    height=5.5cm, 

    legend entries={Java 9},  

    legend pos=north west]

\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};

\end{axis}

\end{tikzpicture}

\end{tabular}  

\end{center}

\newpage

\subsection*{Part 2 (4 Marks)}

Coming from Java or C++, you might think Scala is a quite esoteric

programming language.  But remember, some serious companies have built

their business on

Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}

And there are far, far more esoteric languages out there. One is

called \emph{brainf***}. You are asked in this part to implement an

interpreter for this language.

Urban M\"uller developed brainf*** in 1993.  A close relative of this

language was already introduced in 1964 by Corado B\"ohm, an Italian

computer pioneer, who unfortunately died a few months ago. The main

feature of brainf*** is its minimalistic set of instructions---just 8

instructions in total and all of which are single characters. Despite

the minimalism, this language has been shown to be Turing

complete\ldots{}if this doesn't ring any bell with you: it roughly

means that every algorithm we know can, in principle, be implemented in

brainf***. It just takes a lot of determination and quite a lot of

memory resources. Some relatively sophisticated sample programs in

brainf*** are given in the file \texttt{bf.scala}.\bigskip

\noindent

As mentioned above, brainf*** has 8 single-character commands, namely

\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},

\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is

considered a comment.  Brainf*** operates on memory cells containing

integers. For this it uses a single memory pointer that points at each

stage to one memory cell. This pointer can be moved forward by one

memory cell by using the command \texttt{'>'}, and backward by using

\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,

respectively decrease, by 1 the content of the memory cell to which

the memory pointer currently points to. The commands for input/output

are \texttt{','} and \texttt{'.'}. Output works by reading the content

of the memory cell to which the memory pointer points to and printing

it out as an ASCII character. Input works the other way, taking some

user input and storing it in the cell to which the memory pointer

points to. The commands \texttt{'['} and \texttt{']'} are looping

constructs. Everything in between \texttt{'['} and \texttt{']'} is

repeated until a counter (memory cell) reaches zero.  A typical

program in brainf*** looks as follows:

\begin{center}

\begin{verbatim}

 ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++

 ..+++.>>.<-.<.+++.------.--------.>>+.>++.

\end{verbatim}

\end{center}  

\noindent

This one prints out Hello World\ldots{}obviously. 

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

\begin{itemize}

\item[(2a)] Brainf*** memory is represented by a \texttt{Map} from

  integers to integers. The empty memory is represented by

  \texttt{Map()}, that is nothing is stored in the

  memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at

  memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The

  convention is that if we query the memory at a location that is

  \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write

  a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and

  a memory pointer (an \texttt{Int}) as argument, and safely reads the

  corresponding memory location. If the \texttt{Map} is not defined at

  the memory pointer, \texttt{sread} returns \texttt{0}.

  Write another function \texttt{write}, which takes a memory, a

  memory pointer and an integer value as argument and updates the

  \texttt{Map} with the value at the given memory location. As usual

  the \texttt{Map} is not updated `in-place' but a new map is created

  with the same data, except the value is stored at the given memory

  pointer.\hfill[1 Mark]

\item[(2b)] Write two functions, \texttt{jumpRight} and

  \texttt{jumpLeft} that are needed to implement the loop constructs

  of brainf***. They take a program (a \texttt{String}) and a program

  counter (an \texttt{Int}) as argument and move right (respectively

  left) in the string in order to find the \textbf{matching}