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 |
18 \section*{Main Part 5 (Scala, 9 Marks)} |
18 \section*{Main Part 5 (Scala, 10 Marks)} |
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 |
87 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
87 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
88 \end{lstlisting}%$ |
88 \end{lstlisting}%$ |
89 |
89 |
90 \newpage |
90 \newpage |
91 |
91 |
92 \subsection*{Part A (5 Marks)} |
92 \subsection*{Part A (6 Marks)} |
93 |
93 |
94 Coming from Java or C++, you might think Scala is a rather esoteric |
94 Coming from Java or C++, you might think Scala is a rather esoteric |
95 programming language. But remember, some serious companies have built |
95 programming language. But remember, some serious companies have built |
96 their business on |
96 their business on |
97 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} |
97 Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} |
107 its minimalistic set of instructions---just 8 instructions in total |
107 its minimalistic set of instructions---just 8 instructions in total |
108 and all of which are single characters. Despite the minimalism, this |
108 and all of which are single characters. Despite the minimalism, this |
109 language has been shown to be Turing complete\ldots{}if this doesn't |
109 language has been shown to be Turing complete\ldots{}if this doesn't |
110 ring any bell with you: it roughly means that every(!) algorithm can, |
110 ring any bell with you: it roughly means that every(!) algorithm can, |
111 in principle, be implemented in brainf***. It just takes a lot of |
111 in principle, be implemented in brainf***. It just takes a lot of |
112 determination and quite a lot of memory resources. |
112 determination and quite a lot of memory and time. |
113 |
113 |
114 Some relatively sophisticated sample programs in brainf*** are given |
114 Some relatively sophisticated sample programs in brainf*** are given |
115 in the file \texttt{bf.scala}, including a brainf*** program for the |
115 in the file \texttt{bf.scala}, including a brainf*** program for the |
116 Sierpinski triangle and the Mandelbrot set. There seems to be even a |
116 Sierpinski triangle and the Mandelbrot set. There seems to be even a |
117 dedicated Windows IDE for bf programs, though I am not sure whether |
117 dedicated Windows IDE for bf programs, though I am not sure whether |
389 \end{center} |
389 \end{center} |
390 \caption{The rules for how commands in the brainf*** language update the |
390 \caption{The rules for how commands in the brainf*** language update the |
391 program counter \texttt{pc}, |
391 program counter \texttt{pc}, |
392 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}} |
393 \end{figure} |
393 \end{figure} |
394 \end{itemize}\bigskip |
394 |
395 |
395 |
|
396 \item[(5)] Let us also generate some BF programs ourselves: |
|
397 Write a function |
|
398 \texttt{generate} which takes a list of characters as input and generates |
|
399 a corresponding BF program that prints out this list of characters. One |
|
400 way to generate such a program is to consider each character in the list, |
|
401 add as many \texttt{"+"} given by the ASCII code of the character, then add the |
|
402 \texttt{"."} command for printing and add the loop \texttt{"[-]"} for ``zero-ing'' the memory |
|
403 cell; then go to the next character in the list. For example |
|
404 the list \texttt{"ABC".toString} produces (as a single string) |
|
405 |
|
406 \begin{center} |
|
407 \texttt{+++++++++++++++++++++++++++++++++++++++++++++++++++++} |
|
408 \texttt{++++++++++++.[-]+++++++++++++++++++++++++++++++++++++} |
|
409 \texttt{+++++++++++++++++++++++++++++.[-]++++++++++++++++++++} |
|
410 \texttt{+++++++++++++++++++++++++++++++++++++++++++++++.[-]} |
|
411 \end{center}\mbox{}\hfill[1 Mark] |
|
412 |
|
413 \end{itemize}\bigskip |
396 %%\newpage |
414 %%\newpage |
397 |
415 |
398 \subsection*{Part B (4 Marks)} |
416 \subsection*{Part B (4 Marks)} |
399 |
417 |
400 I am sure you agree while it is fun to marvel at bf-programs, like the |
418 I am sure you agree while it is fun to marvel at bf-programs, like the |
403 |
421 |
404 |
422 |
405 \subsubsection*{Tasks (file bfc.scala)} |
423 \subsubsection*{Tasks (file bfc.scala)} |
406 |
424 |
407 \begin{itemize} |
425 \begin{itemize} |
408 \item[(5)] Compilers, in general, attempt to make programs run |
426 \item[(6)] Compilers, in general, attempt to make programs run |
409 faster by precomputing as much information as possible |
427 faster by precomputing as much information as possible |
410 before running the program. In our case we can precompute the |
428 before running the program. In our case we can precompute the |
411 addresses where we need to jump at the beginning and end of |
429 addresses where we need to jump at the beginning and end of |
412 loops. |
430 loops. |
413 |
431 |
446 and \texttt{jumpRight} was called previously, you should look |
464 and \texttt{jumpRight} was called previously, you should look |
447 up the jump address in the \texttt{jtable}. Feel free to reuse |
465 up the jump address in the \texttt{jtable}. Feel free to reuse |
448 the function \texttt{jumpLeft} and \texttt{jumpRight} for |
466 the function \texttt{jumpLeft} and \texttt{jumpRight} for |
449 calculating the \texttt{jtable}.\hfill{[1 Mark]} |
467 calculating the \texttt{jtable}.\hfill{[1 Mark]} |
450 |
468 |
451 \item[(6)] Compilers try to eliminate any ``dead'' code that could |
469 \item[(7)] Compilers try to eliminate any ``dead'' code that could |
452 slow down programs and also perform what is often called |
470 slow down programs and also perform what is often called |
453 \emph{peephole |
471 \emph{peephole |
454 optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} |
472 optimisations}.\footnote{\url{https://en.wikipedia.org/wiki/Peephole_optimization}} |
455 For the latter consider that it is difficult for compilers to |
473 For the latter consider that it is difficult for compilers to |
456 comprehend what is intended with whole programs, but they are very good |
474 comprehend what is intended with whole programs, but they are very good |
474 not a bf-command. Similarly, the |
492 not a bf-command. Similarly, the |
475 regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}. By using the Scala method \pcode{.replaceAll} you can replace substrings |
493 regular expression \pcode{"""\\[-\\]"""} finds all occurrences of \pcode{[-]}. By using the Scala method \pcode{.replaceAll} you can replace substrings |
476 with new strings.\\ |
494 with new strings.\\ |
477 \mbox{}\hfill{[1 Mark]} |
495 \mbox{}\hfill{[1 Mark]} |
478 |
496 |
479 \item[(7)] Finally, real compilers try to take advantage of modern |
497 \item[(8)] Finally, real compilers try to take advantage of modern |
480 CPUs which often provide complex operations in hardware that can |
498 CPUs which often provide complex operations in hardware that can |
481 combine many smaller instructions into a single faster instruction. |
499 combine many smaller instructions into a single faster instruction. |
482 |
500 |
483 In our case we can optimise the several single increments performed at a |
501 In our case we can optimise the several single increments performed at a |
484 memory cell, for example \pcode{++++}, by a single ``increment by |
502 memory cell, for example \pcode{++++}, by a single ``increment by |