# HG changeset patch # User Christian Urban # Date 1544104370 0 # Node ID bebe34c975a8e49e692ffeab78b3eb645ddb9a33 # Parent 5549016ab10f573166c48826f4d843e0a7db2eaf updated diff -r 5549016ab10f -r bebe34c975a8 cws/cw05.pdf Binary file cws/cw05.pdf has changed 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 diff -r 5549016ab10f -r bebe34c975a8 solutions5/bf.jar Binary file solutions5/bf.jar has changed diff -r 5549016ab10f -r bebe34c975a8 solutions5/bf.scala --- 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)) */ - } diff -r 5549016ab10f -r bebe34c975a8 templates5/bf.scala --- /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)) +*/ +