\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 programming+
−
language called brainf***. The first part is due on 13 December at+
−
11pm; the second, more advanced part, is due on 20 December at+
−
11pm.\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}+
−
+
−
As usual, this Scala assignment comes with a reference implementation in form of+
−
two \texttt{jar}-files. You can download them from KEATS. 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 bf.jar} and then query any function from the+
−
\texttt{bf.scala} template file. You have to+
−
prefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example+
−
+
−
+
−
\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]+
−
$ scala -cp bf.jar+
−
scala> 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 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}}+
−
I claim functional programming is not a fad.  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. 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}, including+
−
a brainf*** program for the Sierpinski triangle and the Mandelbrot set.\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 ;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 Mandelbrot+
−
program, 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: +
−