\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.0335 0.03610 0.03415 0.03618 0.05919 0.084 20 0.14121 0.24822 0.48523 0.87824 1.7125 3.4026 7.0827 14.1228 26.69\end{filecontents}\begin{filecontents}{re-java.data}5 0.0029810 0.0041815 0.0099616 0.0171017 0.0349218 0.0330319 0.0508420 0.1017721 0.1996022 0.4115923 0.8223424 1.7025125 3.3611226 6.6399827 13.3512028 29.81185\end{filecontents}\begin{filecontents}{re-java9.data}1000 0.014102000 0.048823000 0.106094000 0.174565000 0.275306000 0.411167000 0.537418000 0.702619000 0.9398110000 0.9741911000 1.2869712000 1.5138714000 2.0707916000 2.6984620000 4.4182324000 6.4607726000 7.6437330000 9.9944634000 12.96688538000 16.28162142000 19.18022846000 21.98472150000 26.95020360000 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 30November at 11pm; the second, more advanced part, is due on 21December at 11pm. In the first part, you are asked to implement aregular expression matcher based on derivatives of regularexpressions. The reason is that regular expression matching in Javaand Python can sometimes be extremely slow. The advanced part is aboutan interpreter for a very simple programming language.\bigskip\IMPORTANT{}\noindentAlso note that the running time of each part will be restricted to amaximum of 360 seconds on my laptop.\DISCLAIMER{}\subsection*{Part 1 (6 Marks)}The task is to implement a regular expression matcher that is based onderivatives of regular expressions. Most of the functions are defined byrecursion over regular expressions and can be elegantly implementedusing Scala's pattern-matching. The implementation should deal with thefollowing 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 yousolve a lot of problems that vex other humans. Regular expressions areone of the fastest and simplest ways to match patterns in text, andare endlessly useful for searching, editing and analysing data in allsorts of places (for example analysing network traffic in order todetect security breaches). However, you need to be fast, otherwise youwill 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 regularexpressions and also defines some handy shorthand notation forregular expressions. The notation in this document matches upwith 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 derivativesw.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 onlytakes a single character.The second function, called \textit{matcher}, takes a string and aregular expression as arguments. It builds first the derivativesaccording to \textit{ders} and after that tests whether the resultingderivative regular expression can match the empty string (using\textit{nullable}). For example the \textit{matcher} will producetrue 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' regularexpression $(a^*)^* \cdot b$ grows when taking successive derivativesaccording the letter $a$ without simplification and then compare it totaking the derivative, but simplify the result. The sizesare given in \texttt{re.scala}. \hfill[1 Mark]\end{itemize}\subsection*{Background}Although easily implementable in Scala, the idea behind the derivativefunction might not so easy to be seen. To understand its purposebetter, assume a regular expression $r$ can match strings of the form$c\!::\!cs$ (that means strings which start with a character $c$ and havesome rest, or tail, $cs$). If you take the derivative of $r$ withrespect to the character $c$, then you obtain a regular expressionthat can match all the strings $cs$. In other words, the regularexpression $\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 derivativeaccording to $a$ then you obtain a regular expression that can match$bc$ (it is $abc$ where the $a$ has been chopped off). If you nowbuild the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ youobtain a regular expression that can match the string $c$ (it is $bc$where $b$ is chopped off). If you finally build the derivative of thisaccording $c$, that is$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtaina regular expression that can match the empty string. You can testwhether this is indeed the case using the function nullable, which iswhat your matcher is doing.The purpose of the $\textit{simp}$ function is to keep the regularexpressions small. Normally the derivative function makes the regularexpression bigger (see the SEQ case and the example in (1b)) and thealgorithm would be slower and slower over time. The $\textit{simp}$function counters this increase in size and the result is that thealgorithm is fast throughout. By the way, this algorithm is by JanuszBrzozowski who came up with the idea of derivatives in 1964 in his PhDthesis.\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 inJava\footnote{Version 8 and below; Version 9 does not seem to be as catastrophic, but still worse than the regular expression matcherbased on derivatives.} and in Python with the `evil' regularexpression $(a^*)^*\cdot b$, then have a look at the graphs below (youcan try it out for yourself: have a look at the file\texttt{catastrophic.java} and \texttt{catastrophic.py} onKEATS). Compare this with the matcher you have implemented. How longcan the string of $a$'s be in your matcher and still stay within the30 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 esotericprogramming language. But remember, some serious companies have builttheir business onScala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}And there are far, far more esoteric languages out there. One iscalled \emph{brainf***}. You are asked in this part to implement aninterpreter for this language.Urban M\"uller developed brainf*** in 1993. A close relative of thislanguage was already introduced in 1964 by Corado B\"ohm, an Italiancomputer pioneer, who unfortunately died a few months ago. The mainfeature of brainf*** is its minimalistic set of instructions---just 8instructions in total and all of which are single characters. Despitethe minimalism, this language has been shown to be Turingcomplete\ldots{}if this doesn't ring any bell with you: it roughlymeans that every algorithm we know can, in principle, be implemented inbrainf***. It just takes a lot of determination and quite a lot ofmemory resources. Some relatively sophisticated sample programs inbrainf*** are given in the file \texttt{bf.scala}.\bigskip\noindentAs mentioned above, brainf*** has 8 single-character commands, namely\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character isconsidered a comment. Brainf*** operates on memory cells containingintegers. For this it uses a single memory pointer that points at eachstage to one memory cell. This pointer can be moved forward by onememory 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 whichthe memory pointer currently points to. The commands for input/outputare \texttt{','} and \texttt{'.'}. Output works by reading the contentof the memory cell to which the memory pointer points to and printingit out as an ASCII character. Input works the other way, taking someuser input and storing it in the cell to which the memory pointerpoints to. The commands \texttt{'['} and \texttt{']'} are loopingconstructs. Everything in between \texttt{'['} and \texttt{']'} isrepeated until a counter (memory cell) reaches zero. A typicalprogram in brainf*** looks as follows:\begin{center}\begin{verbatim} ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ ..+++.>>.<-.<.+++.------.--------.>>+.>++.\end{verbatim}\end{center} \noindentThis 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: