\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*{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}}
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 and compiler 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 Mandelbot 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. 

\subsubsection*{Tasks (file bf.scala)}

\begin{itemize}
\item[(1)]  Write a function that takes a file name as argument and
  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{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. The most convenient way to
  implement the rules in \texttt{run} is to use pattern-matching
  and calculating a triple consisting of the new \texttt{pc},
  \texttt{mp} and \texttt{mem}.

  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 (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}{|@{}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  

\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: