
diff -r 9476aee44eed -r cccdae0fccc7 cws/cw05.tex
--- a/cws/cw05.tex	Wed Aug 12 00:56:20 2020 +0100
+++ b/cws/cw05.tex	Sun Aug 23 14:39:58 2020 +0100
@@ -17,17 +17,17 @@
 
 \section*{Part 10 (Scala)}
 
-\mbox{}\hfill\textit{``If there's one feature that makes Scala,}\\
-\mbox{}\hfill\textit{`Scala', I would pick implicits.''}\smallskip\\
-\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\medskip
+\mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\
+\mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\
+\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\bigskip
 
 
 \noindent
-This part is about a small programming
-language called brainf***. The part is worth 10\% and you need to 
-submit on \cwTEN{} at 4pm.\bigskip
+This part is about a small (esotheric) programming language called
+brainf***. Actually, we will implement an interpreter for our own version
+of this language called brainf*ck++.\bigskip
 
-\IMPORTANT{}
+\IMPORTANT{This part is worth 10\% and you need to submit on \cwTEN{} at 4pm.}
 
 \noindent
 Also note that the running time of each part will be restricted to a
@@ -94,24 +94,27 @@
 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
+more esoteric languages out there. One is called \emph{brainf***}. 
+\here{https://esolangs.org/wiki/Brainfuck}
+You
 are asked in this part to implement an interpreter for
-this language.
+a slight extension of 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 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.
-There seems to be even a dedicated Windows IDE for bf programs, though
-I am not sure whether this is just an elaborate April fools' joke---judge
-yourself:
+Urban M\"uller developed the original version of 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 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.  There seems to be even a
+dedicated Windows IDE for bf programs, though I am not sure whether
+this is just an elaborate April fools' joke---judge yourself:
 
 \begin{center}
 \url{https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5}
@@ -119,21 +122,26 @@
 
 
 \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
+As mentioned above, the original brainf*** has 8 single-character
+commands. Our version of bf++ will contain the commands \texttt{'>'},
+\texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['}
+and \texttt{']'} from the original, and in addition the commands
+\texttt{'@'}, \texttt{'*'} and \texttt{'\#'}.  Every other character
+is considered a comment.
+
+Our interpreter for bf++ 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
+the memory pointer currently points to. The command for output is
+\texttt{'.'} whereby 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.\footnote{In the originial version of bf, there is also a
+  command for input, but we omit it here. All our programs will be
+  ``autonomous''.}  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:
@@ -146,7 +154,9 @@
 \end{center}  
 
 \noindent
-This one prints out Hello World\ldots{}obviously ;o) 
+This one prints out Hello World\ldots{}obviously \texttt{;o)} We also
+add 3 new commands to the bf++ langauge, whose purpose we explain later.
+
 
 \subsubsection*{Tasks (file bf.scala)}
 
@@ -157,7 +167,7 @@
   the function should return the empty string.\\
   \mbox{}\hfill[1 Mark]
   
-\item[(2)] Brainf*** memory is represented by a \texttt{Map} from
+\item[(2)] Brainf**k++ 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
@@ -178,21 +188,21 @@
 
 \item[(3)] Write two functions, \texttt{jumpRight} and
   \texttt{jumpLeft}, that are needed to implement the loop constructs
-  in brainf***. They take a program (a \texttt{String}) and a program
+  in brainf**k++. They take a program (a \texttt{String}) and a program
   counter (an \texttt{Int}) as arguments 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{.}.+>--],>,++}
+  \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{,}>,++}
+  \texttt{--[..+>--]\barbelow{.}>.++}
   \end{center}
 
   meaning it jumps to after the loop. Similarly, if you are in 8th position,
@@ -200,21 +210,21 @@
   bracket (that is jumping to the beginning of the loop):
 
   \begin{center}
-    \texttt{--[..+>-\barbelow{-}],>,++}
+    \texttt{--[..+>-\barbelow{-}].>.++}
     \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad
-    \texttt{--[\barbelow{.}.+>--],>,++}
+    \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
+  matching bracket. For example in the brain*ck++ program
 
   \begin{center}
-  \texttt{--[\barbelow{.}.[+>]--],>,++}
+  \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, 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
@@ -225,13 +235,13 @@
   in strings such as
 
   \begin{center}
-  \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}
+  \texttt{--[\barbelow{.}.[[-]+>[.]]--].>.++}
   \end{center}
 
   for which \texttt{jumpRight} should produce the position:
 
   \begin{center}
-  \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}
+  \texttt{--[..[[-]+>[.]]--]\barbelow{.}>.++}
   \end{center}
 
   It is also possible that the position returned by \texttt{jumpRight} or
@@ -239,15 +249,15 @@
   no matching brackets. For example
 
   \begin{center}
-  \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}
+  \texttt{--[\barbelow{.}.[[-]+>[.]]--.>.++}
   \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
-  \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
+  \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
+  brain*u*k++ 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
@@ -255,14 +265,14 @@
   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
+  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
+  given brainfu*k++ 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
+  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
 
@@ -299,12 +309,12 @@
                        $\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@{}}
+      %                 $\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)}$\\
@@ -321,7 +331,25 @@
                        \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\
                        $\bullet$ & $\texttt{pc} + 1$\\
                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
-                     \end{tabular}\\\hline   
+                           \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@{}}
+                       $\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@{}}
+                       $\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  
       any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
                          $\bullet$ & $\texttt{pc} + 1$\\
                          $\bullet$ & \texttt{mp} and \texttt{mem} unchanged




