diff -r 9476aee44eed -r cccdae0fccc7 cws/cw05.tex --- a/cws/cw05.tex Wed Aug 12 00:56:20 2020 +0100 +++ b/cws/cw05.tex Sun Aug 23 14:39:58 2020 +0100 @@ -17,17 +17,17 @@ \section*{Part 10 (Scala)} -\mbox{}\hfill\textit{``If there's one feature that makes Scala,}\\ -\mbox{}\hfill\textit{`Scala', I would pick implicits.''}\smallskip\\ -\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\medskip +\mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\ +\mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\ +\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\bigskip \noindent -This part is about a small programming -language called brainf***. The part is worth 10\% and you need to -submit on \cwTEN{} at 4pm.\bigskip +This part is about a small (esotheric) programming language called +brainf***. Actually, we will implement an interpreter for our own version +of this language called brainf*ck++.\bigskip -\IMPORTANT{} +\IMPORTANT{This part is worth 10\% and you need to submit on \cwTEN{} at 4pm.} \noindent Also note that the running time of each part will be restricted to a @@ -94,24 +94,27 @@ their business on Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}} I claim functional programming is not a fad. And there are far, far -more esoteric languages out there. One is called \emph{brainf***}. You +more esoteric languages out there. One is called \emph{brainf***}. +\here{https://esolangs.org/wiki/Brainfuck} +You are asked in this part to implement an interpreter for -this language. +a slight extension of 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 -computer pioneer. The main feature of brainf*** is its minimalistic -set of instructions---just 8 instructions in total and all of which -are single characters. Despite the minimalism, this language has been -shown to be Turing complete\ldots{}if this doesn't ring any bell with -you: it roughly means that every(!) algorithm can, in principle, -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 the Mandelbrot set. -There seems to be even a dedicated Windows IDE for bf programs, though -I am not sure whether this is just an elaborate April fools' joke---judge -yourself: +Urban M\"uller developed the original version of brainf*** in 1993. A close +relative of this language was already introduced in 1964 by Corado +B\"ohm, an Italian computer pioneer. The main feature of brainf*** is +its minimalistic set of instructions---just 8 instructions in total +and all of which are single characters. Despite the minimalism, this +language has been shown to be Turing complete\ldots{}if this doesn't +ring any bell with you: it roughly means that every(!) algorithm can, +in principle, 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 the Mandelbrot set. There seems to be even a +dedicated Windows IDE for bf programs, though I am not sure whether +this is just an elaborate April fools' joke---judge yourself: \begin{center} \url{https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5} @@ -119,21 +122,26 @@ \noindent -As mentioned above, brainf*** has 8 single-character commands, namely -\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, -\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is -considered a comment. Brainf*** operates on memory cells containing +As mentioned above, the original brainf*** has 8 single-character +commands. Our version of bf++ will contain the commands \texttt{'>'}, +\texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['} +and \texttt{']'} from the original, and in addition the commands +\texttt{'@'}, \texttt{'*'} and \texttt{'\#'}. Every other character +is considered a comment. + +Our interpreter for bf++ operates on memory cells containing integers. For this it uses a single memory pointer that points at each stage to one memory cell. This pointer can be moved forward by one memory cell by using the command \texttt{'>'}, and backward by using \texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase, respectively decrease, by 1 the content of the memory cell to which -the memory pointer currently points to. The commands for input/output -are \texttt{','} and \texttt{'.'}. Output works by reading the content -of the memory cell to which the memory pointer points to and printing -it out as an ASCII character. Input works the other way, taking some -user input and storing it in the cell to which the memory pointer -points to. The commands \texttt{'['} and \texttt{']'} are looping +the memory pointer currently points to. The command for output is +\texttt{'.'} whereby output works by reading the content of the memory +cell to which the memory pointer points to and printing it out as an +ASCII character.\footnote{In the originial version of bf, there is also a + command for input, but we omit it here. All our programs will be + ``autonomous''.} The +commands \texttt{'['} and \texttt{']'} are looping constructs. Everything in between \texttt{'['} and \texttt{']'} is repeated until a counter (memory cell) reaches zero. A typical program in brainf*** looks as follows: @@ -146,7 +154,9 @@ \end{center} \noindent -This one prints out Hello World\ldots{}obviously ;o) +This one prints out Hello World\ldots{}obviously \texttt{;o)} We also +add 3 new commands to the bf++ langauge, whose purpose we explain later. + \subsubsection*{Tasks (file bf.scala)} @@ -157,7 +167,7 @@ the function should return the empty string.\\ \mbox{}\hfill[1 Mark] -\item[(2)] Brainf*** memory is represented by a \texttt{Map} from +\item[(2)] Brainf**k++ memory is represented by a \texttt{Map} from integers to integers. The empty memory is represented by \texttt{Map()}, that is nothing is stored in the memory; \texttt{Map(0 -> 1, 2 -> 3)} stores \texttt{1} at @@ -178,21 +188,21 @@ \item[(3)] Write two functions, \texttt{jumpRight} and \texttt{jumpLeft}, that are needed to implement the loop constructs - in brainf***. They take a program (a \texttt{String}) and a program + in brainf**k++. They take a program (a \texttt{String}) and a program counter (an \texttt{Int}) as arguments and move right (respectively left) in the string in order to find the \textbf{matching} opening/closing bracket. For example, given the following program with the program counter indicated by an arrow: \begin{center} - \texttt{--[\barbelow{.}.+>--],>,++} + \texttt{--[\barbelow{.}.+>--].>.++} \end{center} then the matching closing bracket is in 9th position (counting from 0) and \texttt{jumpRight} is supposed to return the position just after this \begin{center} - \texttt{--[..+>--]\barbelow{,}>,++} + \texttt{--[..+>--]\barbelow{.}>.++} \end{center} meaning it jumps to after the loop. Similarly, if you are in 8th position, @@ -200,21 +210,21 @@ bracket (that is jumping to the beginning of the loop): \begin{center} - \texttt{--[..+>-\barbelow{-}],>,++} + \texttt{--[..+>-\barbelow{-}].>.++} \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad - \texttt{--[\barbelow{.}.+>--],>,++} + \texttt{--[\barbelow{.}.+>--].>.++} \end{center} Unfortunately we have to take into account that there might be other opening and closing brackets on the `way' to find the - matching bracket. For example in the brainf*** program + matching bracket. For example in the brain*ck++ program \begin{center} - \texttt{--[\barbelow{.}.[+>]--],>,++} + \texttt{--[\barbelow{.}.[+>]--].>.++} \end{center} we do not want to return the index for the \texttt{'-'} in the 9th - position, but the program counter for \texttt{','} in 12th + position, but the program counter for \texttt{'.'} in 12th position. The easiest to find out whether a bracket is matched is by using levels (which are the third argument in \texttt{jumpLeft} and \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the @@ -225,13 +235,13 @@ in strings such as \begin{center} - \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++} + \texttt{--[\barbelow{.}.[[-]+>[.]]--].>.++} \end{center} for which \texttt{jumpRight} should produce the position: \begin{center} - \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++} + \texttt{--[..[[-]+>[.]]--]\barbelow{.}>.++} \end{center} It is also possible that the position returned by \texttt{jumpRight} or @@ -239,15 +249,15 @@ no matching brackets. For example \begin{center} - \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++} + \texttt{--[\barbelow{.}.[[-]+>[.]]--.>.++} \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad - \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}} + \texttt{--[..[[-]+>[.]]-->.++\barbelow{\;\phantom{+}}} \end{center} \hfill[2 Marks] \item[(4)] Write a recursive function \texttt{compute} that runs a - brainf*** program. It takes a program, a program counter, a memory + brain*u*k++ 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{compute} returns the memory. If the program counter is inside the string, it reads the @@ -255,14 +265,14 @@ memory pointer \texttt{mp} and memory \texttt{mem} according to the rules shown in Figure~\ref{comms}. It then calls recursively \texttt{compute} with the updated data. The most convenient way to - implement the brainf**k rules in Scala is to use pattern-matching + 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{run} that calls \texttt{compute} with a - given brainfu** program and memory, and the program counter and memory pointer + given brainfu*k++ program and memory, and the program counter and memory pointer 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 + 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 @@ -299,12 +309,12 @@ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ $\bullet$ & print out \,\texttt{mem(mp)} as a character\\ \end{tabular}\\\hline - \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} - $\bullet$ & $\texttt{pc} + 1$\\ - $\bullet$ & $\texttt{mp}$ unchanged\\ - $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ - \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} - \end{tabular}\\\hline + %\hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} + % $\bullet$ & $\texttt{pc} + 1$\\ + % $\bullet$ & $\texttt{mp}$ unchanged\\ + % $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ + % \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} + % \end{tabular}\\\hline \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\ $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\ @@ -321,7 +331,25 @@ \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\ $\bullet$ & $\texttt{pc} + 1$\\ $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\ - \end{tabular}\\\hline + \end{tabular}\\\hline + \hfill\texttt{'@'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} + $\bullet$ & $\texttt{pc} + 1$\\ + $\bullet$ & $\texttt{mp}$ unchanged\\ + $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ + \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} + \end{tabular}\\\hline + \hfill\texttt{'*'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} + $\bullet$ & $\texttt{pc} + 1$\\ + $\bullet$ & $\texttt{mp}$ unchanged\\ + $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ + \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} + \end{tabular}\\\hline + \hfill\texttt{'\#'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} + $\bullet$ & $\texttt{pc} + 1$\\ + $\bullet$ & $\texttt{mp}$ unchanged\\ + $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\ + \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}} + \end{tabular}\\\hline any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}} $\bullet$ & $\texttt{pc} + 1$\\ $\bullet$ & \texttt{mp} and \texttt{mem} unchanged