\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: + −