pep-material: comparison cws/cw05.tex

equal deleted inserted replaced

-:25d9c3b2bc99
+:c0d9e6548b08
 \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 (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
 maximum of 30 seconds on my laptop.
 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
+integers. For this it uses a single memory pointer, called
-stage to one memory cell. This pointer can be moved forward by one
+\texttt{mp}, that points at each stage to one memory cell.
-memory cell by using the command \texttt{'>'}, and backward by using
-\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,
+\begin{center}
-respectively decrease, by 1 the content of the memory cell to which
+\begin{tikzpicture}
-the memory pointer currently points to. The command for output is
+\draw [line width=1mm, rounded corners] (0,0) rectangle (5, 0.5);
-\texttt{'.'} whereby output works by reading the content of the memory
+\draw (0.5, 0) -- (0.5, 0.5);
-cell to which the memory pointer points to and printing it out as an
+\draw (1.0, 0) -- (1.0, 0.5);
-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
+\draw (2.5, 0) -- (2.5, 0.5);
-``autonomous''.}  The
+\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
 program in brainf*** looks as follows:
 \end{verbatim}
 \end{center}
 \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)}
 \begin{itemize}
 \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
 integers to integers. The empty memory is represented by
 \texttt{Map()}, that is nothing is stored in the
 Sierpinski triangle or the Hello world programs (they seem to be particularly
 useful for debugging purposes), or have a look at
 \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}
 \begin{tabular}{|@{\hspace{0.5mm}}p{0.8cm}|l|}
 \hline
 $\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@{}}
+$\bullet$ & $\texttt{pc} + 1$\\
+$\bullet$ & $\texttt{mp}$ unchanged\\
+$\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{mp -> \textrm{input}}\\
+$\bullet$ & \texttt{mem} updated with
-\multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
+\texttt{mem(mp) -> mem(mp - 1)}\\
-\end{tabular}\\\hline
+\multicolumn{2}{@{}l}{this updates the memory cell having the index stored at \texttt{mem(mp)},}\\
-\hfill\texttt{'*'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+\multicolumn{2}{@{}l}{with the value stored at \texttt{mem(mp - 1)},}
-$\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{mp}$ and \texttt{mem} unchanged\\
-$\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
+$\bullet$ & print out \,\texttt{mem(mp)} as a number\\
-\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
 \end{tabular}\\
 \hline
 \end{tabular}
-\end{center}
+\\\mbox{}\\[-10mm]\mbox{}
-\caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},
+\end{center}
+\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
 %%\newpage
 \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{]}',
 to which pc-position do we need to jump next?
 For the latter consider that it is difficult for compilers to
 comprehend what is intended with whole programs, but they are very good
 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
+expression \pcode{"""[^<>+-.\\[\\]@\#*]"""}, which recognises everything that is
-not a bf-command. Similarly, the
+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
+\item[(7)] Finally, real compilers try to take advantage of modern
-provide complex operations in hardware that can combine many smaller
+CPUs which often provide complex operations in hardware that can
-instructions into a single faster instruction.
+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
 4''. For this optimisation we just have to make sure these single
 increments are all next to each other. Similar optimisations should apply
 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}
 original bf-cmds & replacement\\
 \hline
 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
+26 copies of a single bf++-command in a row is a rare occurrence in
-actual bf-programs). Similar replacements apply
+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
 \begin{center}
 \pcode{combine(optimise(load_bff("benchmark.bf")))}
 worthwhile overall (of course for the \pcode{>A}'s and so on, the compiler incurs a
 penalty). Luckily, after you have performed all
 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"))}
 \end{center}

changeset 337	c0d9e6548b08
parent 336	25d9c3b2bc99