pep-material: comparison cws/cw05.tex

equal deleted inserted replaced

-:7e00d2b13b04
+:25d9c3b2bc99
 \begin{document}
 \section*{Part 10 (Scala)}
-\mbox{}\hfill\textit{``If there's one feature that makes Scala,}\\
+\mbox{}\hfill\textit{``If there's one feature that makes Scala, `Scala',}\\
-\mbox{}\hfill\textit{`Scala', I would pick implicits.''}\smallskip\\
+\mbox{}\hfill\textit{ I would pick implicits.''}\smallskip\\
-\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\medskip
+\mbox{}\hfill\textit{ --- Martin Odersky (creator of the Scala language)}\bigskip\bigskip
 \noindent
-This part is about a small programming
+This part is about a small (esotheric) programming language called
-language called brainf***. The part is worth 10\% and you need to
+brainf***. Actually, we will implement an interpreter for our own version
-submit on \cwTEN{} at 4pm.\bigskip
+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
 maximum of 30 seconds on my laptop.
 Coming from Java or C++, you might think Scala is a rather esoteric
 programming language.  But remember, some serious companies have built
 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
+Urban M\"uller developed the original version of brainf*** in 1993.  A close
-language was already introduced in 1964 by Corado B\"ohm, an Italian
+relative of this language was already introduced in 1964 by Corado
-computer pioneer. The main feature of brainf*** is its minimalistic
+B\"ohm, an Italian computer pioneer. The main feature of brainf*** is
-set of instructions---just 8 instructions in total and all of which
+its minimalistic set of instructions---just 8 instructions in total
-are single characters. Despite the minimalism, this language has been
+and all of which are single characters. Despite the minimalism, this
-shown to be Turing complete\ldots{}if this doesn't ring any bell with
+language has been shown to be Turing complete\ldots{}if this doesn't
-you: it roughly means that every(!) algorithm can, in principle,
+ring any bell with you: it roughly means that every(!) algorithm can,
-be implemented in brainf***. It just takes a lot of determination and
+in principle, be implemented in brainf***. It just takes a lot of
-quite a lot of memory resources. Some relatively sophisticated sample
+determination and quite a lot of memory resources.
-programs in brainf*** are given in the file \texttt{bf.scala}, including
-a brainf*** program for the Sierpinski triangle and the Mandelbrot set.
+Some relatively sophisticated sample programs in brainf*** are given
-There seems to be even a dedicated Windows IDE for bf programs, though
+in the file \texttt{bf.scala}, including a brainf*** program for the
-I am not sure whether this is just an elaborate April fools' joke---judge
+Sierpinski triangle and the Mandelbrot set.  There seems to be even a
-yourself:
+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}
 \end{center}  \bigskip
 \noindent
-As mentioned above, brainf*** has 8 single-character commands, namely
+As mentioned above, the original brainf*** has 8 single-character
-\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},
+commands. Our version of bf++ will contain the commands \texttt{'>'},
-\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is
+\texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'}, \texttt{'['}
-considered a comment.  Brainf*** operates on memory cells containing
+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
+the memory pointer currently points to. The command for output is
-are \texttt{','} and \texttt{'.'}. Output works by reading the content
+\texttt{'.'} whereby output works by reading the content of the memory
-of the memory cell to which the memory pointer points to and printing
+cell to which the memory pointer points to and printing it out as an
-it out as an ASCII character. Input works the other way, taking some
+ASCII character.\footnote{In the originial version of bf, there is also a
-user input and storing it in the cell to which the memory pointer
+command for input, but we omit it here. All our programs will be
-points to. The commands \texttt{'['} and \texttt{']'} are looping
+``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:
 \begin{center}
 +++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
 \end{verbatim}
 \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)}
 \begin{itemize}
 \item[(1)]  Write a function that takes a filename (a string) 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.\\
 \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
 memory location \texttt{0}, and at \texttt{2} it stores \texttt{3}. The
 convention is that if we query the memory at a location that is
 with the same data, except the new value is stored at the given memory
 pointer.\hfill[1 Mark]
 \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,
 then \texttt{jumpLeft} is supposed to jump to just after the opening
 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
 level by one whenever you find an opening bracket and decrease by
 one for a closing bracket. Then in \texttt{jumpRight} you are looking
 for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you
 do the opposite. In this way you can find \textbf{matching} brackets
 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
 \texttt{jumpLeft} is outside the string in cases where there are
 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
 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{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
 \begin{center}
 \url{https://esolangs.org/wiki/Brainfuck}
 \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
 $\bullet$ & $\texttt{pc} + 1$\\
 $\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@{}}
+%\hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
-$\bullet$ & $\texttt{pc} + 1$\\
+%                 $\bullet$ & $\texttt{pc} + 1$\\
-$\bullet$ & $\texttt{mp}$ unchanged\\
+%                 $\bullet$ & $\texttt{mp}$ unchanged\\
-$\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
+%                 $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
-\multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
+%                 \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
-\end{tabular}\\\hline
+%               \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)}$\\
 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
 \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\
 $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\
 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
 \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\
 $\bullet$ & $\texttt{pc} + 1$\\
 $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
 \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
 \end{tabular}\\
 \hline

changeset 336	25d9c3b2bc99
parent 325	ca9c1cf929fa
child 337	c0d9e6548b08