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