324 While it is fun to look at bf-programs, like the Sierpinski triangle or the Mandelbrot

   326 I am sure you agree while it is fun to look at bf-programs, like the

   325 program, being interpreted, it is much more fun to write a compiler for the bf-language.

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

   326 

   328 is much more fun to write a compiler for the bf-language.

   329 

   330 

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

   332 

   333 \begin{itemize}

   334 \item[(5)] Compilers in general attempt to make programs run

   335   faster by precomputing as much information as possible

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

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

   338   loops. 

   339 

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

   341   table'' for a bf-program. This function takes a bf-program 

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

   343   purpose of this Map is to record the information

   344   that given on the pc-position $pc$ is a '\texttt{[}' or a '\texttt{]}',

   345   then to which pc-position do we need to jump next?

   346  

   347   For example for the program

   348     

   349   \begin{center}

   350     \texttt{+++++[->++++++++++<]>--<+++[->>++++++++++}

   351     \texttt{<<]>>++<<----------[+>.>.<+<]}

   352   \end{center}

   353 

   354   we obtain the Map (note the precise numbers might differ depending on white

   355   spaces etc.~in the bf-program):

   356 

   357   \begin{center}

   358   \texttt{Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)}

   359   \end{center}  

   360   

   361   This Map states that for the '\texttt{[}' on position 5, we need to

   362   jump to position 20, which is just after the corresponding '\texttt{]}'.

   363   Similarly, for the '\texttt{]}' on position 19, we need to jump to

   364   position 6, which is just after the '\texttt{[}' on position 5, and so

   365   on. The idea is to not calculate this information each time

   366   we hit a bracket, but just look up this information in the 

   367   \texttt{jtable}. 

   368 

   369   Then adapt the \texttt{compute} and \texttt{run} functions

   370   from Part 1 in order to take advantage of the information

   371   stored in the \texttt{jtable}. This means whenever \texttt{jumpLeft}

   372   and \texttt{jumpRight} was called previously, you should look

   373   up the jump address in the \texttt{jtable}. Feel free to reuse

   374   the function \texttt{jumpLeft} and \texttt{jumpRight} for

   375   calculating the \texttt{jtable}.\hfill{[1 Mark]}

   376 

   377 \item[(6)] Compilers try to eliminate any ``dead'' code that could slow

   378   down programs and also perform what is often called

   379   \emph{peephole optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} While it is difficult for compilers to comprehend what

   380   is intended with whole programs, they are very good at finding out

   381   what small snippets of code do, and then try to generate

   382   faster code for such snippets.

   383 

   384   In our case, dead code is everything that is not a bf-command.

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

   386   dead code. Moreover this function should replace every substring

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

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

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

   390   to do this in a single step, rather than incrementally as in

   391   the original bf-programs.

   392 

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

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

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

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

   397   expression \pcode{"""[^<>+-.,\\[\\]]"""}, which recognises everything that is 

   398   not a bf-command. Similarly, the

   399   regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]} and 

   400   by using the Scala method \pcode{.replaceAll} you can replace it with the 

   401   string \pcode{"0"} standing for the new bf-command.\hfill{[1 Mark]}

   402 

   403 \item[(7)] Finally, real compilers try to take advantage of CPUs which often

   404   provide complex operations in hardware that can combine many smaller

   405   instructions into a single faster instruction.

   406 

   407   In our case we can optimise the several single increments of a

   408   memory cell, for example \pcode{++++}, by a single ``increment by

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

   410   increments are all next to each other. Similarly optimisations should apply

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

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

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

   414   this by introducing two-character bf-commands. For example

   415 

   416   \begin{center}

   417     \begin{tabular}{l|l}

   418       original bf-cmds & replacement\\

   419       \hline

   420       \pcode{+} & \pcode{+A}\\

   421       \pcode{++} & \pcode{+B}\\

   422       \pcode{+++} & \pcode{+C}\\

   423       \ldots{} & \ldots{}\\

   424       \pcode{+++....++} & \pcode{+Z}\\

   425       \hspace{5mm}(these are 26 \pcode{+}'s)\\

   426     \end{tabular} 

   427   \end{center}  

   428 

   429 

   430   Similarly for \pcode{-}, \pcode{<} and \pcode{>}. If there are more

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

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

   433   26 copies of a single bf-command in a row is a rare occurrence in

   434   actual bf-programs). All other bf-commands should be unaffected by this

   435   change. 

   436 

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

   438   of repeated increment and decrement commands by appropriate

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

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

   441   be performed. Make sure that when a two-character bf-command is

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

   443   order to process the next command. For example

   444 

   445   \begin{center}

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

   447   \end{center}  

   448 

   449   generates the improved program

   450 

   451   \begin{center}

   452   \pcode{>A+B[<A+M>A-A]<A[[}\hspace{3mm}\ldots{}

   453   \end{center}  

   454 

   455   for the original benchmark program

   456 

   457   \begin{center}

   458     \pcode{>++[<+++++++++++++>-]<[[}\hspace{3mm}\ldots

   459   \end{center}    

   460 

   461   As you can see, the compiler bets on saving so much time on the

   462   \pcode{+B} and \pcode{+M} steps so that the optimisations is

   463   worthwhile overall (of course for the \pcode{>A}'s and so on, the compiler incurs a

   464   penalty). Luckily, after you have performed all

   465   optimisations in (5) - (7), you can expect that the

   466   \pcode{benchmark.bf} program runs four to five times faster.\hfill{[2 Marks]}

   467 \end{itemize}