--- a/cws/cw05.tex Sun Aug 23 14:39:58 2020 +0100
+++ b/cws/cw05.tex Tue Aug 25 01:18:17 2020 +0100
@@ -23,11 +23,11 @@
\noindent
-This part is about a small (esotheric) programming language called
+This part is about a small (esoteric) programming language called
brainf***. Actually, we will implement an interpreter for our own version
of this language called brainf*ck++.\bigskip
-\IMPORTANT{This part is worth 10\% and you need to submit on \cwTEN{} at 4pm.}
+\IMPORTANT{This part is worth 10\% and you need to submit it on \cwTEN{} at 4pm.}
\noindent
Also note that the running time of each part will be restricted to a
@@ -130,17 +130,41 @@
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 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
+integers. For this it uses a single memory pointer, called
+\texttt{mp}, that points at each stage to one memory cell.
+
+\begin{center}
+\begin{tikzpicture}
+ \draw [line width=1mm, rounded corners] (0,0) rectangle (5, 0.5);
+ \draw (0.5, 0) -- (0.5, 0.5);
+ \draw (1.0, 0) -- (1.0, 0.5);
+
+ \draw (2.5, 0) -- (2.5, 0.5);
+ \draw (2.0, 0) -- (2.0, 0.5);
+
+ \draw (4.5, 0) -- (4.5, 0.5);
+ \draw (4.0, 0) -- (4.0, 0.5);
+
+ \draw (1.5,0.25) node {$\cdots$};
+ \draw (3.0,0.25) node {$\cdots$};
+
+ \draw [->, thick] (2.25, -0.5) -- (2.25, -0.15);
+ \draw (2.25,-0.8) node {\texttt{mp}};
+
+ \draw (0.7,0.7) node {\sf\footnotesize memory};
+\end{tikzpicture}
+\end{center}
+
+\noindent
+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 command for output in bf++ 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
+ original 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
@@ -155,7 +179,8 @@
\noindent
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.
+add 3 new commands in the bf++-version of the bf-language. The purpose
+of these commands we explain later.
\subsubsection*{Tasks (file bf.scala)}
@@ -164,7 +189,7 @@
\item[(1)] Write a function that takes a filename (a string) as an argument
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.\\
+ the function should return the empty string.
\mbox{}\hfill[1 Mark]
\item[(2)] Brainf**k++ memory is represented by a \texttt{Map} from
@@ -278,7 +303,10 @@
\begin{center}
\url{https://esolangs.org/wiki/Brainfuck}
- \end{center}\hfill[2 Marks]
+ \end{center}
+
+ \noindent for more bf/bf++-programs and the test cases given in \texttt{bf.scala}.\\
+ \mbox{}\hfill[2 Marks]
\begin{figure}[p]
\begin{center}
@@ -332,23 +360,26 @@
$\bullet$ & $\texttt{pc} + 1$\\
$\bullet$ & $\texttt{mp}$ and \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 -> \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}}
+ $\bullet$ & \texttt{mem} updated with \texttt{mp -> mem(mp) * mem(mp - 1)}\\
+ \multicolumn{2}{@{}l}{this multiplies the content of the memory cells at
+ \texttt{mp} and \texttt{mp - 1}}\\
+ \multicolumn{2}{@{}l}{and stores the result at \texttt{mp}}
+ \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{mem(mp) -> mem(mp - 1)}\\
+ \multicolumn{2}{@{}l}{this updates the memory cell having the index stored at \texttt{mem(mp)},}\\
+ \multicolumn{2}{@{}l}{with the value stored at \texttt{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 -> \textrm{input}}\\
- \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
+ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+ $\bullet$ & print out \,\texttt{mem(mp)} as a number\\
\end{tabular}\\\hline
any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
$\bullet$ & $\texttt{pc} + 1$\\
@@ -356,8 +387,10 @@
\end{tabular}\\
\hline
\end{tabular}
+ \\\mbox{}\\[-10mm]\mbox{}
\end{center}
- \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},
+ \caption{The rules for how commands in the brainf***++ language update the
+ program counter \texttt{pc},
the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}}
\end{figure}
\end{itemize}\bigskip
@@ -366,22 +399,22 @@
\subsection*{Part B (4 Marks)}
-I am sure you agree while it is fun to look at bf-programs, like the
+I am sure you agree while it is fun to marvel 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.
+is much more fun to write a compiler for the bf++-language.
\subsubsection*{Tasks (file bfc.scala)}
\begin{itemize}
-\item[(5)] Compilers in general attempt to make programs run
+\item[(5)] Compilers, in general, attempt to make programs run
faster by precomputing as much information as possible
before running the program. In our case we can precompute the
addresses where we need to jump at the beginning and end of
loops.
For this write a function \texttt{jtable} that precomputes the ``jump
- table'' for a bf-program. This function takes a bf-program
+ table'' for a bf++-program. This function takes a bf++-program
as an argument and returns a \texttt{Map[Int, Int]}. The
purpose of this Map is to record the information, in cases
a pc-position points to a '\texttt{[}' or a '\texttt{]}',
@@ -426,28 +459,28 @@
at finding out what small snippets of code do, and then try to
generate faster code for such snippets.
- In our case, dead code is everything that is not a bf-command.
+ In our case, dead code is everything that is not a bf++-command.
Therefore write a function \texttt{optimise} which deletes such
- dead code from a bf-program. Moreover this function should replace every substring
+ dead code from a bf++-program. Moreover this function should replace every substring
of the form \pcode{[-]} by a new command \texttt{0}.
The idea is that the loop \pcode{[-]} just resets the
memory at the current location to 0. It is more efficient
to do this in a single step, rather than stepwise in a loop as in
- the original bf-programs.
+ the original bf++-programs.
In the extended \texttt{compute3} and \texttt{run3} functions you should
implement this command by writing 0 to \pcode{mem(mp)}, that is use
\pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}.
The easiest way to modify a string in this way is to use the regular
- expression \pcode{"""[^<>+-.,\\[\\]]"""}, which recognises everything that is
- not a bf-command. Similarly, the
+ expression \pcode{"""[^<>+-.\\[\\]@\#*]"""}, which recognises everything that is
+ not a bf++-command. Similarly, the
regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}. By using the Scala method \pcode{.replaceAll} you can replace substrings
with new strings.\\
\mbox{}\hfill{[1 Mark]}
-\item[(7)] Finally, real compilers try to take advantage of CPUs which often
- provide complex operations in hardware that can combine many smaller
- instructions into a single faster instruction.
+\item[(7)] Finally, real compilers try to take advantage of modern
+ CPUs which often provide complex operations in hardware that can
+ combine many smaller instructions into a single faster instruction.
In our case we can optimise the several single increments performed at a
memory cell, for example \pcode{++++}, by a single ``increment by
@@ -456,7 +489,7 @@
for the bf-commands \pcode{-}, \pcode{<} and
\pcode{>}, which can all be replaced by extended versions that take
the amount of the increment (decrement) into account. We will do
- this by introducing two-character bf-commands. For example
+ this by introducing two-character bf++-commands. For example
\begin{center}
\begin{tabular}{l|l}
@@ -475,17 +508,17 @@
If there are more
than 26 \pcode{+}'s in a row, then more than one ``two-character''
bf-commands need to be generated (the idea is that more than
- 26 copies of a single bf-command in a row is a rare occurrence in
- actual bf-programs). Similar replacements apply
+ 26 copies of a single bf++-command in a row is a rare occurrence in
+ actual bf++-programs). Similar replacements apply
for \pcode{-}, \pcode{<} and \pcode{>}, but
- all other bf-commands should be unaffected by this
+ all other bf++-commands should be unaffected by this
change.
For this write a function \texttt{combine} which replaces sequences
of repeated increment and decrement commands by appropriate
two-character commands. In the functions \pcode{compute4} and
\pcode{run4}, the ``combine'' and the optimisation from (6) should
- be performed. Make sure that when a two-character bf-command is
+ be performed. Make sure that when a two-character bf++-command is
encountered you need to increase the \pcode{pc}-counter by two in
order to progress to the next command. For example
@@ -512,7 +545,7 @@
optimisations in (5) - (7), you can expect that the
\pcode{benchmark.bf} program runs four to five times faster.
You can also test whether your compiler produces the correct result
- by for example testing
+ by testing for example
\begin{center}
\pcode{run(load_bff("sierpinski.bf")) == run4(load_bff("sierpinski.bf"))}