Binary file cws/cw05.pdf has changed
--- 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
Binary file solutions5/bf.jar has changed
--- a/solutions5/bf.scala Thu Dec 06 13:15:28 2018 +0000
+++ b/solutions5/bf.scala Thu Dec 06 13:52:50 2018 +0000
@@ -1,7 +1,7 @@
// Part 1 about an Interpreter for the Brainf*** language
//========================================================
-object CW10a {
+object CW10a { // only for generating the Jar file
type Mem = Map[Int, Int]
@@ -70,15 +70,15 @@
//jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside)
//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
-// (4) Complete the compute function that interpretes (runs) a brainf***
-// program: the arguments are a program (represented as a string), a program counter,
-// a memory counter and a brainf*** memory. It Returns the
-// memory at the stage when the excution of the brainf*** program
+// (4) Complete the compute function that interprets (runs) a brainf***
+// program: the arguments are a program (represented as a string), a program
+// counter, a memory counter and a brainf*** memory. It Returns the
+// memory at the stage when the execution of the brainf*** program
// finishes. The interpretation finishes once the program counter
// pc is pointing to something outside the program string.
// If the pc points to a character inside the program, the pc,
// memory pointer and memory need to be updated according to
-// rules of the brainf*** language. Then, recursively, run
+// rules of the brainf*** language. Then, recursively, the compute
// function continues with the command at the new program
// counter.
// Implement the run function that calls compute with the program
@@ -200,6 +200,8 @@
// a Mandelbrot set generator in brainf*** written by Erik Bosman
+// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
+
run(load_bff("mandelbrot.bf"))
@@ -220,5 +222,4 @@
time_needed(1, run(b1))
*/
-
}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/templates5/bf.scala Thu Dec 06 13:52:50 2018 +0000
@@ -0,0 +1,194 @@
+// Part 1 about an Interpreter for the Brainf*** language
+//========================================================
+
+
+// representation of Bf memory
+
+type Mem = Map[Int, Int]
+
+
+// (1) Write a function that takes a file name as argument and
+// 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.
+
+import io.Source
+import scala.util._
+
+//def load_bff(name: String) : String = ...
+
+
+
+// (2) Complete the functions for safely reading
+// and writing brainf*** memory. Safely read should
+// Return the value stored in the Map for a given memory
+// pointer, provided it exists; otherwise it Returns 0. The
+// writing function generates a new Map with the
+// same data, except at the given memory pointer the
+// value v is stored.
+
+
+//def sread(mem: Mem, mp: Int) : Int = ...
+
+//def write(mem: Mem, mp: Int, v: Int) : Mem = ...
+
+
+
+// (3) Implement the two jumping instructions in the
+// brainf*** language. In jumpRight, given a program and
+// a program counter move the program counter to the right
+// until after the *matching* ]-command. Similarly,
+// jumpLeft implements the move to the left to just after
+// the *matching* [-command.
+
+//def jumpRight(prog: String, pc: Int, level: Int) : Int = ...
+
+//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ...
+
+
+// testcases
+//jumpRight("""--[..+>--],>,++""", 3, 0) // => 10
+//jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3
+//jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12
+//jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18
+//jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside)
+//jumpLeft("""[******]***""", 7, 0) // => -1 (outside)
+
+
+
+// (4) Complete the compute function that interprets (runs) a brainf***
+// program: the arguments are a program (represented as a string), a program
+// counter, a memory counter and a brainf*** memory. It Returns the
+// memory at the stage when the execution of the brainf*** program
+// finishes. The interpretation finishes once the program counter
+// pc is pointing to something outside the program string.
+// If the pc points to a character inside the program, the pc,
+// memory pointer and memory need to be updated according to
+// rules of the brainf*** language. Then, recursively, the compute
+// function continues with the command at the new program
+// counter.
+//
+// Implement the run function that calls compute with the program
+// counter and memory counter set to 0.
+
+
+//def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ...
+
+//def run(prog: String, m: Mem = Map()) = ...
+
+
+/*
+
+// some sample bf-programs collected from the Internet
+//=====================================================
+
+
+// first some contrived (small) programs
+
+// clears the 0-cell
+run("[-]", Map(0 -> 100)) // Map will be 0 -> 0
+
+// copies content of the 0-cell to 1-cell
+run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10
+
+
+// copies content of the 0-cell to 2-cell and 4-cell
+run("[>>+>>+<<<<-]", Map(0 -> 42))
+
+
+// prints out numbers 0 to 9
+run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""")
+
+
+// some more "useful" programs
+
+// hello world program 1
+run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+// hello world program 2
+run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+
+ +.<<+++++++++++++++.>.+++.------.--------.>+.>.""")
+
+
+// draws the Sierpinski triangle
+run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]""")
+
+run(load_bff("sierpinski.bf"))
+
+
+//fibonacci numbers below 100
+run("""+++++++++++
+ >+>>>>++++++++++++++++++++++++++++++++++++++++++++
+ >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>
+ +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-
+ <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<
+ -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]
+ >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++
+ +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++
+ ++++++++++++++++++++++++++++++++++++++++++++.[-]<<
+ <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<
+ [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""")
+
+
+//outputs the square numbers up to 10000
+run("""++++[>+++++<-]>[<+++++>-]+<+[
+ >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
+ >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
+ <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""")
+
+//collatz numbers (needs a number to be typed in)
+run(""">,[[----------[
+ >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
+ ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[
+ <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
+ >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
+ >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
+ ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""")
+
+
+// infinite collatz (never stops)
+run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[<
+ <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++
+ +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+<
+ [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>->
+ [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[
+ <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+
+ ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<
+ +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<-
+ ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<-
+ >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>
+ -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++
+ +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[<
+ <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++
+ +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-<
+ <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-
+ [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""")
+
+
+
+// a Mandelbrot set generator in brainf*** written by Erik Bosman
+// (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/)
+
+run(load_bff("mandelbrot.bf"))
+
+
+// a benchmark program (counts down from 'Z' to 'A')
+val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+ [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+ ++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+ +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++."""
+
+
+def time_needed[T](n: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (i <- 0 until n) code
+ val end = System.nanoTime()
+ (end - start)/1.0e9
+}
+
+time_needed(1, run(b1))
+*/
+