13 %% change Console to scala.io.StdIn.readByte()

    13 %% change Console to scala.io.StdIn.readByte()

    14 

    14 

    15 

    15 

    16 \begin{document}

    16 \begin{document}

    17 

    17 

    19 

    19 

    20 \mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\

    20 \mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\

    21 \mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\

    21 \mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\

    22 \mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\bigskip

    22 \mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\bigskip

    23 

    23 

    24 

    24 

    25 \noindent

    25 \noindent

    26 This part is about a small (esoteric) programming language called

    26 This part is about a small (esoteric) programming language called

    29 

    29 

    30 \IMPORTANT{This part is worth 10\% and you need to submit it on \cwTEN{} at 5pm.

    30 \IMPORTANT{This part is worth 10\% and you need to submit it on \cwTEN{} at 5pm.

    31 Any 1\% you achieve counts as your ``weekly engagement''.}

    31 Any 1\% you achieve counts as your ``weekly engagement''.}

    32 

    32 

    33 \noindent

    33 \noindent

    42 As usual, this Scala assignment comes with a reference implementation in

    42 As usual, this Scala assignment comes with a reference implementation in

    43 form of two \texttt{jar}-files. You can download them from KEATS. They

    43 form of two \texttt{jar}-files. You can download them from KEATS. They

    44 allow you to run any test cases on your own computer. For example you

    44 allow you to run any test cases on your own computer. For example you

    45 can call Scala on the command line with the option \texttt{-cp bf.jar}

    45 can call Scala on the command line with the option \texttt{-cp bf.jar}

    46 and then query any function from the \texttt{bf.scala} template file.

    46 and then query any function from the \texttt{bf.scala} template file.

    48 respectively. For example

    48 respectively. For example

    49 

    49 

    50 

    50 

    51 \begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

    51 \begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

    52 $ scala -cp bf.jar

    52 $ scala -cp bf.jar

    54 scala> run(load_bff("sierpinski.bf")) ; ()

    54 scala> run(load_bff("sierpinski.bf")) ; ()

    55                                *

    55                                *

    56                               * *

    56                               * *

    57                              *   *

    57                              *   *

    58                             * * * *

    58                             * * * *

    86 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    86 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    87 \end{lstlisting}%$

    87 \end{lstlisting}%$

    88 

    88 

    89 \newpage

    89 \newpage

    90 

    90 

    92 

    92 

    93 Coming from Java or C++, you might think Scala is a rather esoteric

    93 Coming from Java or C++, you might think Scala is a rather esoteric

    94 programming language.  But remember, some serious companies have built

    94 programming language.  But remember, some serious companies have built

    95 their business on

    95 their business on

    96 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}

    96 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}

   122 \end{center}  \bigskip

   122 \end{center}  \bigskip

   123 

   123 

   124 

   124 

   125 \noindent

   125 \noindent

   126 As mentioned above, the original brainf*** has 8 single-character

   126 As mentioned above, the original brainf*** has 8 single-character

   128 \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['}

   128 \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['}

   131 is considered a comment.

   130 is considered a comment.

   132 

   131 

   134 integers. For this it uses a single memory pointer, called

   133 integers. For this it uses a single memory pointer, called

   135 \texttt{mp}, that points at each stage to one memory cell.

   134 \texttt{mp}, that points at each stage to one memory cell.

   136 

   135 

   137 \begin{center}

   136 \begin{center}

   138 \begin{tikzpicture}

   137 \begin{tikzpicture}

   159 \noindent

   158 \noindent

   160 This pointer can be moved forward by one memory cell by using the

   159 This pointer can be moved forward by one memory cell by using the

   161 command \texttt{'>'}, and backward by using \texttt{'<'}. The commands

   160 command \texttt{'>'}, and backward by using \texttt{'<'}. The commands

   162 \texttt{'+'} and \texttt{'-'} increase, respectively decrease, by 1

   161 \texttt{'+'} and \texttt{'-'} increase, respectively decrease, by 1

   163 the content of the memory cell to which the memory pointer currently

   162 the content of the memory cell to which the memory pointer currently

   165 by reading the content of the memory cell to which the memory pointer

   164 by reading the content of the memory cell to which the memory pointer

   166 points to and printing it out as an ASCII character.\footnote{In the

   165 points to and printing it out as an ASCII character.\footnote{In the

   167   original version of bf, there is also a command for input, but we

   166   original version of bf, there is also a command for input, but we

   168   omit it here. All our programs will be ``autonomous''.}  The

   167   omit it here. All our programs will be ``autonomous''.}  The

   169 commands \texttt{'['} and \texttt{']'} are looping

   168 commands \texttt{'['} and \texttt{']'} are looping

   177    +++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

   176    +++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

   178 \end{verbatim}

   177 \end{verbatim}

   179 \end{center}  

   178 \end{center}  

   180 

   179 

   181 \noindent

   180 \noindent

   185 

   182 

   186 

   183 

   187 \subsubsection*{Tasks (file bf.scala)}

   184 \subsubsection*{Tasks (file bf.scala)}

   188 

   185 

   189 \begin{itemize}

   186 \begin{itemize}

   190 \item[(1)]  Write a function that takes a filename (a string) as an argument

   187 \item[(1)]  Write a function that takes a filename (a string) as an argument

   191   and requests the corresponding file from disk. It returns the

   188   and requests the corresponding file from disk. It returns the

   192   content of the file as a string. If the file does not exists,

   189   content of the file as a string. If the file does not exists,

   193   the function should return the empty string.

   190   the function should return the empty string.

   195   

   192   

   197   integers to integers. The empty memory is represented by

   194   integers to integers. The empty memory is represented by

   198   \texttt{Map()}, that is nothing is stored in the

   195   \texttt{Map()}, that is nothing is stored in the

   199   memory; \texttt{Map(0 -> 1, 2 -> 3)} stores \texttt{1} at

   196   memory; \texttt{Map(0 -> 1, 2 -> 3)} stores \texttt{1} at

   200   memory location \texttt{0}, and at \texttt{2} it stores \texttt{3}. The

   197   memory location \texttt{0}, and at \texttt{2} it stores \texttt{3}. The

   201   convention is that if we query the memory at a location that is

   198   convention is that if we query the memory at a location that is

   208   Write another function \texttt{write}, which takes a memory, a

   205   Write another function \texttt{write}, which takes a memory, a

   209   memory pointer and an integer value as arguments and updates the

   206   memory pointer and an integer value as arguments and updates the

   210   \texttt{Map} with the value at the given memory location. As usual,

   207   \texttt{Map} with the value at the given memory location. As usual,

   211   the \texttt{Map} is not updated `in-place' but a new map is created

   208   the \texttt{Map} is not updated `in-place' but a new map is created

   212   with the same data, except the new value is stored at the given memory

   209   with the same data, except the new value is stored at the given memory

   214 

   211 

   215 \item[(3)] Write two functions, \texttt{jumpRight} and

   212 \item[(3)] Write two functions, \texttt{jumpRight} and

   216   \texttt{jumpLeft}, that are needed to implement the loop constructs

   213   \texttt{jumpLeft}, that are needed to implement the loop constructs

   218   counter (an \texttt{Int}) as arguments and move right (respectively

   215   counter (an \texttt{Int}) as arguments and move right (respectively

   219   left) in the string in order to find the \textbf{matching}

   216   left) in the string in order to find the \textbf{matching}

   220   opening/closing bracket. For example, given the following program

   217   opening/closing bracket. For example, given the following program

   221   with the program counter indicated by an arrow:

   218   with the program counter indicated by an arrow:

   222 

   219 

   241     \texttt{--[\barbelow{.}.+>--].>.++}

   238     \texttt{--[\barbelow{.}.+>--].>.++}

   242   \end{center}

   239   \end{center}

   243 

   240 

   244   Unfortunately we have to take into account that there might be

   241   Unfortunately we have to take into account that there might be

   245   other opening and closing brackets on the `way' to find the

   242   other opening and closing brackets on the `way' to find the

   247 

   244 

   248   \begin{center}

   245   \begin{center}

   249   \texttt{--[\barbelow{.}.[+>]--].>.++}

   246   \texttt{--[\barbelow{.}.[+>]--].>.++}

   250   \end{center}

   247   \end{center}

   251 

   248 

   281   \end{center}

   278   \end{center}

   282   \hfill[2 Marks]

   279   \hfill[2 Marks]

   283 

   280 

   284 

   281 

   285 \item[(4)] Write a recursive function \texttt{compute} that runs a

   282 \item[(4)] Write a recursive function \texttt{compute} that runs a

   287   pointer and a memory as arguments. If the program counter is outside

   284   pointer and a memory as arguments. If the program counter is outside

   288   the program string, the execution stops and \texttt{compute} returns the

   285   the program string, the execution stops and \texttt{compute} returns the

   289   memory. If the program counter is inside the string, it reads the

   286   memory. If the program counter is inside the string, it reads the

   290   corresponding character and updates the program counter \texttt{pc},

   287   corresponding character and updates the program counter \texttt{pc},

   291   memory pointer \texttt{mp} and memory \texttt{mem} according to the

   288   memory pointer \texttt{mp} and memory \texttt{mem} according to the

   292   rules shown in Figure~\ref{comms}. It then calls recursively

   289   rules shown in Figure~\ref{comms}. It then calls recursively

   293   \texttt{compute} with the updated data. The most convenient way to

   290   \texttt{compute} with the updated data. The most convenient way to

   295   and to calculate a triple consisting of the updated \texttt{pc},

   292   and to calculate a triple consisting of the updated \texttt{pc},

   296   \texttt{mp} and \texttt{mem}.

   293   \texttt{mp} and \texttt{mem}.

   297 

   294 

   298   Write another function \texttt{run} that calls \texttt{compute} with a

   295   Write another function \texttt{run} that calls \texttt{compute} with a

   300   set to~$0$. Like \texttt{compute}, it returns the memory after the execution

   297   set to~$0$. Like \texttt{compute}, it returns the memory after the execution

   302   Sierpinski triangle or the Hello world programs (they seem to be particularly

   299   Sierpinski triangle or the Hello world programs (they seem to be particularly

   303   useful for debugging purposes), or have a look at

   300   useful for debugging purposes), or have a look at

   304 

   301 

   305   \begin{center}

   302   \begin{center}

   306   \url{https://esolangs.org/wiki/Brainfuck}

   303   \url{https://esolangs.org/wiki/Brainfuck}

   307   \end{center}

   304   \end{center}

   308 

   305 

   310   \mbox{}\hfill[2 Marks]

   307   \mbox{}\hfill[2 Marks]

   311   

   308   

   312   \begin{figure}[p]

   309   \begin{figure}[p]

   313   \begin{center}

   310   \begin{center}

   314     \begin{tabular}{|@{\hspace{0.5mm}}p{0.8cm}|l|}

   311     \begin{tabular}{|@{\hspace{0.5mm}}p{0.8cm}|l|}

   359                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\

   356                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\

   360                        \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\

   357                        \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\

   361                        $\bullet$ & $\texttt{pc} + 1$\\

   358                        $\bullet$ & $\texttt{pc} + 1$\\

   362                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\

   359                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\

   363                            \end{tabular}\\\hline

   360                            \end{tabular}\\\hline

   385       any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   382       any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}

   387                          $\bullet$ & \texttt{mp} and \texttt{mem} unchanged

   384                          $\bullet$ & \texttt{mp} and \texttt{mem} unchanged

   388                        \end{tabular}\\

   385                        \end{tabular}\\

   389       \hline                 

   386       \hline                 

   390     \end{tabular}

   387     \end{tabular}

   391     \\\mbox{}\\[-10mm]\mbox{}

   388     \\\mbox{}\\[-10mm]\mbox{}

   392   \end{center}

   389   \end{center}

   394     program counter \texttt{pc},

   391     program counter \texttt{pc},

   395     the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}}

   392     the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}}

   396   \end{figure}

   393   \end{figure}

   397 \end{itemize}\bigskip  

   394 \end{itemize}\bigskip  

   398 

   395 

   399 %%\newpage

   396 %%\newpage

   400 

   397 

   401 \subsection*{Part B (4 Marks)}

   398 \subsection*{Part B (4 Marks)}

   402 

   399 

   404 Sierpinski triangle or the Mandelbrot program, being interpreted, it

   401 Sierpinski triangle or the Mandelbrot program, being interpreted, it

   406 

   403 

   407 

   404 

   408 \subsubsection*{Tasks (file bfc.scala)}

   405 \subsubsection*{Tasks (file bfc.scala)}

   409 

   406 

   410 \begin{itemize}

   407 \begin{itemize}

   413   before running the program. In our case we can precompute the

   410   before running the program. In our case we can precompute the

   414   addresses where we need to jump at the beginning and end of

   411   addresses where we need to jump at the beginning and end of

   415   loops. 

   412   loops. 

   416 

   413 

   417   For this write a function \texttt{jtable} that precomputes the ``jump

   414   For this write a function \texttt{jtable} that precomputes the ``jump

   419   as an argument and returns a \texttt{Map[Int, Int]}. The 

   416   as an argument and returns a \texttt{Map[Int, Int]}. The 

   420   purpose of this Map is to record the information, in cases

   417   purpose of this Map is to record the information, in cases

   421   a pc-position points to a '\texttt{[}' or a '\texttt{]}',

   418   a pc-position points to a '\texttt{[}' or a '\texttt{]}',

   422   to which pc-position do we need to jump next?

   419   to which pc-position do we need to jump next?

   423  

   420  

   458   For the latter consider that it is difficult for compilers to

   455   For the latter consider that it is difficult for compilers to

   459   comprehend what is intended with whole programs, but they are very good

   456   comprehend what is intended with whole programs, but they are very good

   460   at finding out what small snippets of code do, and then try to

   457   at finding out what small snippets of code do, and then try to

   461   generate faster code for such snippets.

   458   generate faster code for such snippets.

   462 

   459 

   464   Therefore write a function \texttt{optimise} which deletes such

   461   Therefore write a function \texttt{optimise} which deletes such

   466   of the form \pcode{[-]} by a new command \texttt{0}. 

   463   of the form \pcode{[-]} by a new command \texttt{0}. 

   467   The idea is that the loop \pcode{[-]} just resets the

   464   The idea is that the loop \pcode{[-]} just resets the

   468   memory at the current location to 0. It is more efficient

   465   memory at the current location to 0. It is more efficient

   469   to do this in a single step, rather than stepwise in a loop as in

   466   to do this in a single step, rather than stepwise in a loop as in

   471 

   468 

   472   In the extended \texttt{compute3} and \texttt{run3} functions you should

   469   In the extended \texttt{compute3} and \texttt{run3} functions you should

   473   implement this command by writing 0 to \pcode{mem(mp)}, that is use

   470   implement this command by writing 0 to \pcode{mem(mp)}, that is use

   474   \pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}.

   471   \pcode{write(mem, mp, 0)} as the rule for the command \texttt{0}.

   475   The easiest way to modify a string in this way is to use the regular

   472   The easiest way to modify a string in this way is to use the regular

   478   regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}.  By using the Scala method \pcode{.replaceAll} you can replace substrings

   475   regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}.  By using the Scala method \pcode{.replaceAll} you can replace substrings

   479   with new strings.\\

   476   with new strings.\\

   480   \mbox{}\hfill{[1 Mark]}

   477   \mbox{}\hfill{[1 Mark]}

   481 

   478 

   482 \item[(7)] Finally, real compilers try to take advantage of modern

   479 \item[(7)] Finally, real compilers try to take advantage of modern

   488   4''. For this optimisation we just have to make sure these single

   485   4''. For this optimisation we just have to make sure these single

   489   increments are all next to each other. Similar optimisations should apply

   486   increments are all next to each other. Similar optimisations should apply

   490   for the bf-commands \pcode{-}, \pcode{<} and

   487   for the bf-commands \pcode{-}, \pcode{<} and

   491   \pcode{>}, which can all be replaced by extended versions that take

   488   \pcode{>}, which can all be replaced by extended versions that take

   492   the amount of the increment (decrement) into account. We will do

   489   the amount of the increment (decrement) into account. We will do

   494 

   491 

   495   \begin{center}

   492   \begin{center}

   496     \begin{tabular}{l|l}

   493     \begin{tabular}{l|l}

   497       original bf-cmds & replacement\\

   494       original bf-cmds & replacement\\

   498       \hline

   495       \hline

   507 

   504 

   508 

   505 

   509   If there are more

   506   If there are more

   510   than 26 \pcode{+}'s in a row, then more than one ``two-character''

   507   than 26 \pcode{+}'s in a row, then more than one ``two-character''

   511   bf-commands need to be generated (the idea is that more than

   508   bf-commands need to be generated (the idea is that more than

   514   for \pcode{-}, \pcode{<} and \pcode{>}, but

   511   for \pcode{-}, \pcode{<} and \pcode{>}, but

   516   change. 

   513   change. 

   517 

   514 

   518   For this write a function \texttt{combine} which replaces sequences

   515   For this write a function \texttt{combine} which replaces sequences

   519   of repeated increment and decrement commands by appropriate

   516   of repeated increment and decrement commands by appropriate

   520   two-character commands. In the functions \pcode{compute4} and

   517   two-character commands. In the functions \pcode{compute4} and

   521   \pcode{run4}, the ``combine'' and the optimisation from (6) should

   518   \pcode{run4}, the ``combine'' and the optimisation from (6) should

   523   encountered you need to increase the \pcode{pc}-counter by two in

   520   encountered you need to increase the \pcode{pc}-counter by two in

   524   order to progress to the next command. For example

   521   order to progress to the next command. For example

   525 

   522 

   526   \begin{center}

   523   \begin{center}

   527   \pcode{combine(optimise(load_bff("benchmark.bf")))}  

   524   \pcode{combine(optimise(load_bff("benchmark.bf")))}