diff -r 5549016ab10f -r bebe34c975a8 cws/cw05.tex --- a/cws/cw05.tex Thu Dec 06 13:15:28 2018 +0000 +++ b/cws/cw05.tex Thu Dec 06 13:52:50 2018 +0000 @@ -30,6 +30,54 @@ \DISCLAIMER{} +\subsection*{Reference Implementation} + +As usual, this Scala assignment comes with a reference implementation in form of +two \texttt{jar}-files. You can download them from KEATS. This allows you to run any +test cases on your own computer. For example you can call Scala on the command line with the +option \texttt{-cp bf.jar} and then query any function from the +\texttt{bf.scala} template file. You have to +prefix the calls with \texttt{CW10a} and \texttt{CW10b}, respectively. For example + + +\begin{lstlisting}[language={},xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] +$ scala -cp bf.jar +scala> import CW10a._ +scala> run(load_bff("sierpinski.bf")) + * + * * + * * + * * * * + * * + * * * * + * * * * + * * * * * * * * + * * + * * * * + * * * * + * * * * * * * * + * * * * + * * * * * * * * + * * * * * * * * + * * * * * * * * * * * * * * * * + * * + * * * * + * * * * + * * * * * * * * + * * * * + * * * * * * * * + * * * * * * * * + * * * * * * * * * * * * * * * * + * * * * + * * * * * * * * + * * * * * * * * + * * * * * * * * * * * * * * * * + * * * * * * * * + * * * * * * * * * * * * * * * * + * * * * * * * * * * * * * * * * +* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * +\end{lstlisting}%$ + \subsection*{Part 1 (6 Marks)} @@ -38,9 +86,10 @@ programming language. But remember, some serious companies have built their business on Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} -And there are far, far more esoteric languages out there. One is -called \emph{brainf***}. You are asked in this part to implement an -interpreter and compiler for this language. +I claim functional programming is not a fad. And there are far, far +more esoteric languages out there. One is called \emph{brainf***}. You +are asked in this part to implement an interpreter for +this language. Urban M\"uller developed brainf*** in 1993. A close relative of this language was already introduced in 1964 by Corado B\"ohm, an Italian @@ -52,7 +101,7 @@ be implemented in brainf***. It just takes a lot of determination and quite a lot of memory resources. Some relatively sophisticated sample programs in brainf*** are given in the file \texttt{bf.scala}, including -a brainf*** program for the Sierpinski triangle and Mandelbot set.\bigskip +a brainf*** program for the Sierpinski triangle and the Mandelbrot set.\bigskip \noindent As mentioned above, brainf*** has 8 single-character commands, namely @@ -76,18 +125,18 @@ \begin{center} \begin{verbatim} - ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ - ..+++.>>.<-.<.+++.------.--------.>>+.>++. + ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.++ + +++++..+++.>>.<-.<.+++.------.--------.>>+.>++. \end{verbatim} \end{center} \noindent -This one prints out Hello World\ldots{}obviously. +This one prints out Hello World\ldots{}obviously ;o) \subsubsection*{Tasks (file bf.scala)} \begin{itemize} -\item[(1)] Write a function that takes a file name as argument and +\item[(1)] Write a function that takes a file name 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.\\ @@ -182,22 +231,22 @@ \hfill[2 Marks] -\item[(4)] Write a recursive function \texttt{run} that executes a +\item[(4)] Write a recursive function \texttt{compute} that runs a brainf*** program. It takes a program, a program counter, a memory pointer and a memory as arguments. If the program counter is outside - the program string, the execution stops and \texttt{run} returns the + the program string, the execution stops and \texttt{compute} returns the memory. If the program counter is inside the string, it reads the corresponding character and updates the program counter \texttt{pc}, memory pointer \texttt{mp} and memory \texttt{mem} according to the rules shown in Figure~\ref{comms}. It then calls recursively - \texttt{run} with the updated data. The most convenient way to - implement the rules in \texttt{run} is to use pattern-matching - and calculating a triple consisting of the new \texttt{pc}, + \texttt{compute} with the updated data. The most convenient way to + implement the brainf**k rules in Scala is to use pattern-matching + and to calculate a triple consisting of the updated \texttt{pc}, \texttt{mp} and \texttt{mem}. - Write another function \texttt{start} that calls \texttt{run} with a + Write another function \texttt{run} that calls \texttt{compute} with a given brainfu** program and memory, and the program counter and memory pointer - set to~$0$. Like \texttt{run} it returns the memory after the execution + set to~$0$. Like \texttt{compute}, it returns the memory after the execution of the program finishes. You can test your brainf**k interpreter with the Sierpinski triangle or the Hello world programs (they seem to be particularly useful for debugging purposes), or have a look at @@ -208,7 +257,7 @@ \begin{figure}[p] \begin{center} - \begin{tabular}{|@{}p{0.8cm}|l|} + \begin{tabular}{|@{\hspace{0.5mm}}p{0.8cm}|l|} \hline \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} $\bullet$ & $\texttt{pc} + 1$\\ @@ -266,7 +315,7 @@ \end{tabular} \end{center} \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc}, - memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}} + the memory pointer \texttt{mp} and the memory \texttt{mem}.\label{comms}} \end{figure} \end{itemize}\bigskip