pep-material: comparison cws/cw04.tex

equal deleted inserted replaced

-:3020f8c76baa
+:9e7897f25e13
 24  1.70251
 25  3.36112
 26  6.63998
 27  13.35120
 28  29.81185
+\end{filecontents}
+\begin{filecontents}{re-js.data}
+5   0.061
+10  0.061
+15  0.061
+20  0.070
+23  0.131
+25  0.308
+26  0.564
+28  1.994
+30  7.648
+31  15.881
+32  32.190
 \end{filecontents}
 \begin{filecontents}{re-java9.data}
 1000  0.01410
 2000  0.04882
 \begin{document}
 % BF IDE
 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-\section*{Coursework 8 (Regular Expressions and Brainf***)}
+\section*{Coursework 9 (Scala)}
-This coursework is worth 10\%. It is about regular expressions,
+This coursework is worth 10\%. It is about a regular expression
-pattern matching and an interpreter. The first part is due on 30
+matcher and the shunting yard algorithm by Dijkstra. The first part is
-November at 11pm; the second, more advanced part, is due on 21
+due on 6 December at 11pm; the second, more advanced part, is due on
-December at 11pm. In the first part, you are asked to implement a
+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
+expressions. The background is that regular expression matching in
-and Python can sometimes be extremely slow. The advanced part is about
+languages like Java, JavaScript and Python can sometimes be excruciatingly
-an interpreter for a very simple programming language.\bigskip
+slow. The advanced part is about the shunting yard algorithm that
+transforms the usual infix notation of arithmetic expressions into the
+postfix notation, which is for example used in compilers.\bigskip
 \IMPORTANT{}
 \noindent
 Also note that the running time of each part will be restricted to a
 maximum of 30 seconds on my laptop.
 \DISCLAIMER{}
+\subsection*{Reference Implementation}
+This Scala assignment comes with three reference implementations in form of
+\texttt{jar}-files. This allows you to run any test cases on your own
+computer. For example you can call Scala on the command line with the
+option \texttt{-cp re.jar} and then query any function from the
+\texttt{re.scala} template file. As usual you have to
+prefix the calls with \texttt{CW9a}, \texttt{CW9b} and \texttt{CW9c}.
+Since some tasks are time sensitive, you can check the reference
+implementation as follows: if you want to know how long it takes
+to match strings of $a$'s using the regular expression $(a^*)^*\cdot b$
+you can querry as follows:
+\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
+$ scala -cp re.jar
+scala> import CW9a._
+scala> for (i <- 0 to 5000000 by 500000) {
+| println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.")
+| }
+0 0.00002 secs.
+500000 0.10608 secs.
+1000000 0.22286 secs.
+1500000 0.35982 secs.
+2000000 0.45828 secs.
+2500000 0.59558 secs.
+3000000 0.73191 secs.
+3500000 0.83499 secs.
+4000000 0.99149 secs.
+4500000 1.15395 secs.
+5000000 1.29659 secs.
+\end{lstlisting}%$
 \subsection*{Part 1 (6 Marks)}
 The task is to implement a regular expression matcher that is based on
 &   $|$ & $\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$\\
+&   $|$ & $r^*$       & can match a string with zero or more copies of $r$\\
 \end{tabular}
 \end{center}
 \noindent
-Why? Knowing how to match regular expressions and strings will let you
+Why? Regular expressions are
-solve a lot of problems that vex other humans. Regular expressions are
+one of the simplest ways to match patterns in text, and
-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
 \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}}
+% Knowing how to match regular expressions and strings will let you
+% solve a lot of problems that vex other humans.
 \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
 \end{tabular}
 \end{center}
 \begin{itemize}
-\item[(1a)] Implement a function, called \textit{nullable}, by
+\item[(1)] 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:
 $\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
+\item[(2)] 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}
 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}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= r'$)\\
 $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\
 $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$
 \end{tabular}
 \end{center}
 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}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= 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,
 \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
+\item[(3)] 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.
 \[(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,
+sometimes also called post-order traversal'' you traverse inside the
+tree and on the way up, you apply simplification rules.
+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]
+rule should be applied next.\hfill[1 Mark]
-\item[(1d)] Implement two functions: The first, called \textit{ders},
+\item[(4)] 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}
 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
+\item[(5)] 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}
 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]
+\item[(6)] You do not have to implement anything specific under this
+task.  The purpose here is that you will be marked for some ``power''
+test cases. For example can your matcher decide within 30 seconds
+whether the regular expression $(a^*)^*\cdot b$ matches strings of the
+form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification
+simplify the regular expression
+\[
+\texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)}
+\]
+\noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested
+50 or more times.\\
+\mbox{}\hfill[1 Mark]
 \end{itemize}
 \subsection*{Background}
 Although easily implementable in Scala, the idea behind the derivative
 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
+expression bigger (see the SEQ case and the example in (2)) 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.
 \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
+Java\footnote{Version 8 and below; Version 9 and above does not seem to be as
-catastrophic, but still worse than the regular expression matcher
+catastrophic, but still much worse than the regular expression
-based on derivatives.} and in Python with the `evil' regular
+matcher based on derivatives.}, JavaScript and Python with the
-expression $(a^*)^*\cdot b$, then have a look at the graphs below (you
+`evil' regular expression $(a^*)^*\cdot b$, then have a look at the
-can try it out for yourself: have a look at the file
+graphs below (you can try it out for yourself: have a look at the file
-\texttt{catastrophic.java} and \texttt{catastrophic.py} on
+\texttt{catastrophic9.java}, \texttt{catastrophic.js} and
-KEATS). Compare this with the matcher you have implemented. How long
+\texttt{catastrophic.py} on KEATS). Compare this with the matcher you
-can the string of $a$'s be in your matcher and still stay within the
+have implemented. How long can the string of $a$'s be in your matcher
-30 seconds time limit?
+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\\
 ytick={0,5,...,40},
 scaled ticks=false,
 axis lines=left,
 width=6cm,
 height=5.5cm,
-legend entries={Python, Java 8},
+legend entries={Python, Java 8, JavaScript},
 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};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
 \end{axis}
 \end{tikzpicture}
 &
 \begin{tikzpicture}
 \begin{axis}[
 \end{center}
 \newpage
 \subsection*{Part 2 (4 Marks)}
-Coming from Java or C++, you might think Scala is a quite esoteric
+The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra,
-programming language.  But remember, some serious companies have built
+an influential computer scientist who developed many well-known
-their business on
+algorithms. This algorithm transforms the usual infix notation of
-Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}
+arithmetic expressions into the postfix notation, sometimes also
-And there are far, far more esoteric languages out there. One is
+called reverse Polish notation.
-called \emph{brainf***}. You are asked in this part to implement an
-interpreter for this language.
+Why on Earth do people use the postfix notation? It is much more
+convenient to work with the usual infix notation for arithmetic
-Urban M\"uller developed brainf*** in 1993.  A close relative of this
+expressions. Most modern calculators (as opposed to the ones used 20
-language was already introduced in 1964 by Corado B\"ohm, an Italian
+years ago) understand infix notation. So why on Earth? \ldots{}Well,
-computer pioneer, who unfortunately died a few months ago. The main
+many computers under the hood, even nowadays, use postfix notation
-feature of brainf*** is its minimalistic set of instructions---just 8
+extensively. For example if you give to the Java compiler the
-instructions in total and all of which are single characters. Despite
+expression $1 + ((2 * 3) + (4 - 3))$, it will generate for it the Java Byte
-the minimalism, this language has been shown to be Turing
+code
-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
+\begin{lstlisting}[language=JVMIS,numbers=none]
-brainf***. It just takes a lot of determination and quite a lot of
+ldc 1
-memory resources. Some relatively sophisticated sample programs in
+ldc 2
-brainf*** are given in the file \texttt{bf.scala}.\bigskip
+ldc 3
+imul
+ldc 4
+ldc 3
+isub
+iadd
+iadd
+\end{lstlisting}
 \noindent
-As mentioned above, brainf*** has 8 single-character commands, namely
+where the command \texttt{ldc} loads a constant onto a stack, and \texttt{imul},
-\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},
+\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this
-\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is
+is the arithmetic expression in postfix notation.\bigskip
-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.
+The shunting yard algorithm processes an input token list using an
+operator stack and an output list. The input consists of numbers,
-\subsubsection*{Tasks (file bf.scala)}
+operators ($+$, $-$, $*$, $/$) and parentheses, and for the purpose of
+the assignment we assume the input is always a well-formed expression
+in infix notation.  The algorithm uses information about the
+precedences of the operators (given in the template file). The
+algorithm processes the input token list as follows:
 \begin{itemize}
-\item[(2a)] Brainf*** memory is represented by a \texttt{Map} from
+\item If there is a number as input token, then this token is
-integers to integers. The empty memory is represented by
+transferred to the output list. Then the rest of the input is
-\texttt{Map()}, that is nothing is stored in the
+processed.
-memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at
+\item If there is an operator as input token, then you need to check
-memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The
+what is on top of the operator stack. If there are operators with
-convention is that if we query the memory at a location that is
+a higher or equal precedence, these operators are first popped off
-\emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
+the stack and moved to the output list. Then the operator from the input
-a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
+is pushed onto the stack and the rest of the input is processed.
-a memory pointer (an \texttt{Int}) as argument, and safely reads the
+\item If the input is a left-parenthesis, you push it on to the stack
-corresponding memory location. If the \texttt{Map} is not defined at
+and continue processing the input.
-the memory pointer, \texttt{sread} returns \texttt{0}.
+\item If the input is a right-parenthesis, then you move all operators
+from the stack to the output list until you reach the left-parenthesis.
-Write another function \texttt{write}, which takes a memory, a
+Then you discharge the $($ and $)$ from the input and stack, and continue
-memory pointer and an integer value as argument and updates the
+processing.
-\texttt{Map} with the value at the given memory location. As usual
+\item If the input is empty, then you move all remaining operators
-the \texttt{Map} is not updated `in-place' but a new map is created
+from the stack to the output list.
-with the same data, except the value is stored at the given memory
+\end{itemize}
-pointer.\hfill[1 Mark]
+\subsubsection*{Tasks (file postfix.scala)}
-\item[(2b)] Write two functions, \texttt{jumpRight} and
-\texttt{jumpLeft} that are needed to implement the loop constructs
+\begin{itemize}
-of brainf***. They take a program (a \texttt{String}) and a program
+\item[(7)] Implement the shunting yard algorithm outlined above. The
-counter (an \texttt{Int}) as argument and move right (respectively
+function, called \texttt{syard}, takes a list of tokens as first
-left) in the string in order to find the \textbf{matching}
+argument. The second and third arguments are the stack and output
-opening/closing bracket. For example, given the following program
+list represented as Scala lists. The most convenient way to
-with the program counter indicated by an arrow:
+implement this algorithm is to analyse what the input list, stack
+and output look like in each step using pattern-matching. The
-\begin{center}
+algorithm transforms for example the input
-\texttt{--[\barbelow{.}.+>--],>,++}
-\end{center}
+\[
+\texttt{List(3, +, 4, *, (, 2, -, 1, ))}
-then the matching closing bracket is in 9th position (counting from 0) and
+\]
-\texttt{jumpRight} is supposed to return the position just after this
+into the postfix output
+\[
+\texttt{List(3, 4, 2, 1, -, *, +)}
+\]
-\begin{center}
+You can assume the input list is always a  list representing
-\texttt{--[..+>--]\barbelow{,}>,++}
+a well-formed infix arithmetic expression.\hfill[1 Mark]
-\end{center}
+\item[(8)] Implement a compute function that takes a postfix expression
-meaning it jumps to after the loop. Similarly, if you are in 8th position
+as argument and evaluates it generating an integer as result. It uses a
-then \texttt{jumpLeft} is supposed to jump to just after the opening
+stack to evaluate the postfix expression. The operators $+$, $-$, $*$
-bracket (that is jumping to the beginning of the loop):
+are as usual; $/$ is division on integers, for example $7 / 3 = 2$.
-\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]
+\end{itemize}
-\item[(2c)] Write a recursive function \texttt{run} that executes a
+\subsubsection*{Task (file postfix2.scala)}
-brainf*** program. It takes a program, a program counter, a memory
-pointer and a memory as arguments. If the program counter is outside
+\begin{itemize}
-the program string, the execution stops and \texttt{run} returns the
+\item[(9)] Extend the code in (7) and (8) to include the power
-memory. If the program counter is inside the string, it reads the
+operator.  This requires proper account of associativity of
-corresponding character and updates the program counter \texttt{pc},
+the operators. The power operator is right-associative, whereas the
-memory pointer \texttt{mp} and memory \texttt{mem} according to the
+other operators are left-associative.  Left-associative operators
-rules shown in Figure~\ref{comms}. It then calls recursively
+are popped off if the precedence is bigger or equal, while
-\texttt{run} with the updated data.
+right-associative operators are only popped off if the precedence is
+bigger. The compute function in this task should use
-Write another function \texttt{start} that calls \texttt{run} with a
+\texttt{Long}s, rather than \texttt{Int}s.\hfill[2 Marks]
-given brainfu** program and memory, and the program counter and memory pointer
+\end{itemize}
-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}

changeset 221	9e7897f25e13
parent 218	22705d22c105
child 222	e52cc402caee