\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}
\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: