\documentclass{article}+
−
\usepackage{../style}+
−
\usepackage{../langs}+
−
\usepackage{disclaimer}+
−
\usepackage{tikz}+
−
\usepackage{pgf}+
−
\usepackage{pgfplots}+
−
\usepackage{stackengine}+
−
%% \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-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}+
−
+
−
% BF IDE+
−
% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5+
−
  +
−
\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+
−
+
−
\IMPORTANT{}+
−
+
−
\noindent+
−
Also note that the running time of each part will be restricted to a+
−
maximum of 360 seconds on my laptop.+
−
+
−
\DISCLAIMER{}+
−
+
−
+
−
\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}+
−
  opening/closing bracket. For example, given the following program+
−
  with the program counter indicated by an arrow:+
−
+
−
  \begin{center}+
−
  \texttt{--[\barbelow{.}.+>--],>,++}+
−
  \end{center}+
−
+
−
  then the matching closing bracket is in 9th position (counting from 0) and+
−
  \texttt{jumpRight} is supposed to return the position just after this+
−
  +
−
  \begin{center}+
−
  \texttt{--[..+>--]\barbelow{,}>,++}+
−
  \end{center}+
−
+
−
  meaning it jumps to after the loop. Similarly, if you are in 8th position+
−
  then \texttt{jumpLeft} is supposed to jump to just after the opening+
−
  bracket (that is jumping to the beginning of the loop):+
−
+
−
  \begin{center}+
−
    \texttt{--[..+>-\barbelow{-}],>,++}+
−
    \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad+
−
    \texttt{--[\barbelow{.}.+>--],>,++}+
−
  \end{center}+
−
+
−
  Unfortunately we have to take into account that there might be+
−
  other opening and closing brackets on the `way' to find the+
−
  matching bracket. For example in the brainf*** program+
−
+
−
  \begin{center}+
−
  \texttt{--[\barbelow{.}.[+>]--],>,++}+
−
  \end{center}+
−
+
−
  we do not want to return the index for the \texttt{'-'} in the 9th+
−
  position, but the program counter for \texttt{','} in 12th+
−
  position. The easiest to find out whether a bracket is matched is by+
−
  using levels (which are the third argument in \texttt{jumpLeft} and+
−
  \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the+
−
  level by one whenever you find an opening bracket and decrease by+
−
  one for a closing bracket. Then in \texttt{jumpRight} you are looking+
−
  for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you+
−
  do the opposite. In this way you can find \textbf{matching} brackets+
−
  in strings such as+
−
+
−
  \begin{center}+
−
  \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}+
−
  \end{center}+
−
+
−
  for which \texttt{jumpRight} should produce the position:+
−
+
−
  \begin{center}+
−
  \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}+
−
  \end{center}+
−
+
−
  It is also possible that the position returned by \texttt{jumpRight} or+
−
  \texttt{jumpLeft} is outside the string in cases where there are+
−
  no matching brackets. For example+
−
+
−
  \begin{center}+
−
  \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}+
−
  \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad+
−
  \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}+
−
  \end{center}+
−
  \hfill[1 Mark]+
−
+
−
+
−
\item[(2c)] Write a recursive function \texttt{run} that executes a+
−
  brainf*** program. It takes a program, a program counter, a memory+
−
  pointer and a memory as arguments. If the program counter is outside+
−
  the program string, the execution stops and \texttt{run} returns the+
−
  memory. If the program counter is inside the string, it reads the+
−
  corresponding character and updates the program counter \texttt{pc},+
−
  memory pointer \texttt{mp} and memory \texttt{mem} according to the+
−
  rules shown in Figure~\ref{comms}. It then calls recursively+
−
  \texttt{run} with the updated data.+
−
+
−
  Write another function \texttt{start} that calls \texttt{run} with a+
−
  given brainfu** program and memory, and the program counter and memory pointer+
−
  set to~$0$. Like \texttt{run} it returns the memory after the execution+
−
  of the program finishes. You can test your brainf**k interpreter with the+
−
  Sierpinski triangle or the Hello world programs or have a look at+
−
+
−
  \begin{center}+
−
  \url{https://esolangs.org/wiki/Brainfuck}+
−
  \end{center}\hfill[2 Marks]+
−
  +
−
  \begin{figure}[p]+
−
  \begin{center}+
−
    \begin{tabular}{|@{}p{0.8cm}|l|}+
−
      \hline+
−
      \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp} + 1$\\+
−
                       $\bullet$ & \texttt{mem} unchanged+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp} - 1$\\+
−
                       $\bullet$ & \texttt{mem} unchanged+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{'+'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ unchanged\\+
−
                       $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) + 1}\\+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{'-'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ unchanged\\+
−
                       $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) - 1}\\+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\+
−
                       $\bullet$ & print out \,\texttt{mem(mp)} as a character\\+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ unchanged\\+
−
                       $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\+
−
                       \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}+
−
                     \end{tabular}\\\hline   +
−
      \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\+
−
                       $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\+
−
                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\+
−
                       \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\+
−
                     \end{tabular}+
−
                     \\\hline   +
−
      \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                       \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\+
−
                       $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\+
−
                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\+
−
                       \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\+
−
                       $\bullet$ & $\texttt{pc} + 1$\\+
−
                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\+
−
                     \end{tabular}\\\hline   +
−
      any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}+
−
                         $\bullet$ & $\texttt{pc} + 1$\\+
−
                         $\bullet$ & \texttt{mp} and \texttt{mem} unchanged+
−
                       \end{tabular}\\+
−
      \hline                 +
−
    \end{tabular}+
−
  \end{center}+
−
  \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},+
−
    memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}}+
−
  \end{figure}+
−
\end{itemize}\bigskip  +
−
+
−
+
−
+
−
+
−
\end{document}+
−
+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−