equal
deleted
inserted
replaced
13 \begin{document} |
13 \begin{document} |
14 |
14 |
15 % BF IDE |
15 % BF IDE |
16 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5 |
16 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5 |
17 |
17 |
18 \section*{Coursework 9 (Scala)} |
18 \section*{Coursework 10 (Scala)} |
19 |
19 |
20 This coursework is worth 10\%. It is about a small programming |
20 This coursework is worth 10\%. It is about a small programming |
21 language called brainf***. The first part is due on 13 December at |
21 language called brainf***. The first part is due on 13 December at |
22 11pm; the second, more advanced part, is due on 20 December at |
22 11pm; the second, more advanced part, is due on 20 December at |
23 11pm.\bigskip |
23 11pm.\bigskip |
31 \DISCLAIMER{} |
31 \DISCLAIMER{} |
32 |
32 |
33 \subsection*{Reference Implementation} |
33 \subsection*{Reference Implementation} |
34 |
34 |
35 As usual, this Scala assignment comes with a reference implementation in form of |
35 As usual, this Scala assignment comes with a reference implementation in form of |
36 two \texttt{jar}-files. You can download them from KEATS. This allows you to run any |
36 two \texttt{jar}-files. You can download them from KEATS. They allow you to run any |
37 test cases on your own computer. For example you can call Scala on the command line with the |
37 test cases on your own computer. For example you can call Scala on the command line with the |
38 option \texttt{-cp bf.jar} and then query any function from the |
38 option \texttt{-cp bf.jar} and then query any function from the |
39 \texttt{bf.scala} template file. You have to |
39 \texttt{bf.scala} template file. You have to |
40 prefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example |
40 prefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example |
41 |
41 |
377 \item[(6)] Compilers try to eliminate any ``dead'' code that could |
377 \item[(6)] Compilers try to eliminate any ``dead'' code that could |
378 slow down programs and also perform what is often called |
378 slow down programs and also perform what is often called |
379 \emph{peephole |
379 \emph{peephole |
380 optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} |
380 optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} |
381 For the latter consider that it is difficult for compilers to |
381 For the latter consider that it is difficult for compilers to |
382 comprehend what is intended with whole programs, they are very good |
382 comprehend what is intended with whole programs, but they are very good |
383 at finding out what small snippets of code do, and then try to |
383 at finding out what small snippets of code do, and then try to |
384 generate faster code for such snippets. |
384 generate faster code for such snippets. |
385 |
385 |
386 In our case, dead code is everything that is not a bf-command. |
386 In our case, dead code is everything that is not a bf-command. |
387 Therefore write a function \texttt{optimise} which deletes such |
387 Therefore write a function \texttt{optimise} which deletes such |
460 |
460 |
461 \begin{center} |
461 \begin{center} |
462 \pcode{>++[<+++++++++++++>-]<[[}\hspace{3mm}\ldots |
462 \pcode{>++[<+++++++++++++>-]<[[}\hspace{3mm}\ldots |
463 \end{center} |
463 \end{center} |
464 |
464 |
465 As you can see, the compiler bets on saving so much time on the |
465 As you can see, the compiler bets on saving a lot of time on the |
466 \pcode{+B} and \pcode{+M} steps such that the optimisations is |
466 \pcode{+B} and \pcode{+M} steps so that the optimisations is |
467 worthwhile overall (of course for the \pcode{>A}'s and so on, the compiler incurs a |
467 worthwhile overall (of course for the \pcode{>A}'s and so on, the compiler incurs a |
468 penalty). Luckily, after you have performed all |
468 penalty). Luckily, after you have performed all |
469 optimisations in (5) - (7), you can expect that the |
469 optimisations in (5) - (7), you can expect that the |
470 \pcode{benchmark.bf} program runs four to five times faster. |
470 \pcode{benchmark.bf} program runs four to five times faster. |
471 You can also test whether your compiler produces the correct result |
471 You can also test whether your compiler produces the correct result |