\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)}

\IMPORTANT{}

\noindent

Also note that the running time of each part will be restricted to a

maximum of 30 seconds on my laptop.

\DISCLAIMER{}

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

Urban M\"uller developed brainf*** in 1993.  A close relative of this

language was already introduced in 1964 by Corado B\"ohm, an Italian

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

  integers to integers. The empty memory is represented by

  \texttt{Map()}, that is nothing is stored in 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

  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]

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

  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

  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

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

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: