diff -r 4383809c176a -r 39c6b93718f0 cws/cw03.tex --- a/cws/cw03.tex Thu Nov 23 10:56:47 2017 +0000 +++ b/cws/cw03.tex Fri Nov 24 01:26:01 2017 +0000 @@ -4,6 +4,9 @@ \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 @@ -45,7 +48,8 @@ \begin{document} -\section*{Coursework 8 (Scala, Regular Expressions, Brainf***)} + +\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 @@ -328,7 +332,7 @@ at the graphs below (you can try it out for yourself: have a look at the file \texttt{catastrophic.java} on KEATS). Compare this with the matcher you have implemented. How long can the string of $a$'s be -in your matcher and stay within the 30 seconds time limit? +in your matcher and still stay within the 30 seconds time limit? \begin{center} \begin{tikzpicture} @@ -358,29 +362,225 @@ \subsection*{Part 2 (4 Marks)} -Comming from Java or C++, you might think Scala is a quite -esotheric programming language. But remember, some serious companies -have built their business on Scala. And there are far more esotheric -languages out there. One is called \emph{brainf***}. Urban M\"uller -developed this language in 1993. A close relative was already -introduced in ... by Corado B\"ohm, an Italian computer pionier, who -unfortunately died a few months ago. One feature of brainf*** is its -minimalistic set of instructions. It has just 8 instructions, all of -which are single characters. Despite this minimalism, this language, -given enough memory, has been shown to be Turing complete. In this -part you will implement an interpreter for this language. +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 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 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 example 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)] +\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 has stored \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 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 map is not + defined at the memory pointer it returns \texttt{0}. + + Write another function \texttt{write}, which takes a memory, a + memory pointer and a integer value as argument and updates the map + with the value at the given memory location. As usual the 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 after the loop. Similarly, if you 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 + another opening and closing bracket 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 to + use 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 -\item[(2b)] + \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 + counter 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 the calls recursively \texttt{run} with the updated + data. -\item[(2c)] - + Write another function \texttt{start} that calls \texttt{run} with a + given brainfu** program and memory, and the program counter and memory counter + 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.\\\mbox{}\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}{input 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 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, + memory counter and memory.\label{comms}} + \end{figure} \end{itemize}\bigskip