
diff -r 316f9c6cc2ff -r e7f8e3d2e09a 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  
 
 




