\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{document}% BF IDE% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5\section*{Coursework 9 (Scala)}This coursework is worth 10\%. It is about a small programminglanguage called brainf***. The first part is due on 13 December at11pm; the second, more advanced part, is due on 20 December at11pm.\bigskip\IMPORTANT{}\noindentAlso note that the running time of each part will be restricted to amaximum of 30 seconds on my laptop.\DISCLAIMER{}\subsection*{Reference Implementation}As usual, this Scala assignment comes with a reference implementation in form oftwo \texttt{jar}-files. You can download them from KEATS. This allows you to run anytest cases on your own computer. For example you can call Scala on the command line with theoption \texttt{-cp bf.jar} and then query any function from the\texttt{bf.scala} template file. You have toprefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]$ scala -cp bf.jarscala> import CW10a._ scala> run(load_bff("sierpinski.bf")) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\end{lstlisting}%$\subsection*{Part 1 (6 Marks)}Coming from Java or C++, you might think Scala is a rather esotericprogramming language. But remember, some serious companies have builttheir business onScala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}I claim functional programming is not a fad. And there are far, farmore esoteric languages out there. One is called \emph{brainf***}. Youare asked in this part to implement an interpreter forthis 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. The main feature of brainf*** is its minimalisticset of instructions---just 8 instructions in total and all of whichare single characters. Despite the minimalism, this language has beenshown to be Turing complete\ldots{}if this doesn't ring any bell withyou: it roughly means that every algorithm we know can, in principle,be implemented in brainf***. It just takes a lot of determination andquite a lot of memory resources. Some relatively sophisticated sampleprograms in brainf*** are given in the file \texttt{bf.scala}, includinga brainf*** program for the Sierpinski triangle and the Mandelbrot set.\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 ;o) \subsubsection*{Tasks (file bf.scala)}\begin{itemize}\item[(1)] Write a function that takes a file name as an argument and requests the corresponding file from disk. It returns the content of the file as a String. If the file does not exists, the function should return the empty string.\\ \mbox{}\hfill[1 Mark]\item[(2)] 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)} stores \texttt{1} at memory location \texttt{0}, and 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[(3)] 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[2 Marks]\item[(4)] Write a recursive function \texttt{compute} that runs 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{compute} 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{compute} with the updated data. The most convenient way to implement the brainf**k rules in Scala is to use pattern-matching and to calculate a triple consisting of the updated \texttt{pc}, \texttt{mp} and \texttt{mem}. Write another function \texttt{run} that calls \texttt{compute} with a given brainfu** program and memory, and the program counter and memory pointer set to~$0$. Like \texttt{compute}, 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 (they seem to be particularly useful for debugging purposes), 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}{|@{\hspace{0.5mm}}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}, the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}} \end{figure}\end{itemize}\bigskip \subsection*{Part 2 (4 Marks)}While it is fun to look at bf-programs, like the Sierpinski triangle or the Mandelbrotprogram, being interpreted, it is much more fun to write a compiler for the bf-language.\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: