# HG changeset patch # User Christian Urban # Date 1512648546 0 # Node ID 1347bbd86c5289a1187ea84ea90e0f3fd2947d0e # Parent 7ada03135b2e0f579b595ca09462c233524caa62 updated diff -r 7ada03135b2e -r 1347bbd86c52 templates3/bf.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/templates3/bf.scala Thu Dec 07 12:09:06 2017 +0000 @@ -0,0 +1,151 @@ +// Part 2 about an Interpreter for the Brainf*** language +//======================================================== + +object CW8b { + +type Mem = Map[Int, Int] + +// (2a) 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, if 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 = ... + + +// (2b) Implement the two jumping instructions in the +// brainf*** language. In jumpRight, given a program and +// a program counter move the counter to the right +// until the command after the *matching* ]-command. Similarly, +// jumpLeft implements the move to the left to just after +// the *matching* [-command. The levels are used to find the +// *matching* bracket. + +//def jumpRight(prog: String, pc: Int, level: Int) : Int = ... + +//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ... + + + +// (2c) Complete the run function that interprets (runs) a brainf*** +// program: the arguments are a program, 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 run +// function continues with the command at the new program +// counter. +// +// Implement the start function that calls run with the program +// counter and memory counter set to 0. + +//def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ... + +//def start(prog: String, mem: Mem) = ... + + + + + + +// some sample bf programs collected from the Internet +//================================================== + + +/* +// first some contrived (small) programs + +// clears the 0-cell +start("[-]", Map(0 -> 100)) + +// copies content of the 0-cell to 1-cell +start("[->+<]", Map(0 -> 10)) + +// copies content of the 0-cell to 2-cell and 4-cell +start("[>>+>>+<<<<-]", Map(0 -> 42)) + +start("+++[>+++++<-]", Map(0 -> 10)) + + +// prints out numbers 0 to 9 +start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map()) + + +// some more "useful" programs + +// hello world program 1 +start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ + ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) + +// hello world program 2 +start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ + +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map()) + + +// draws the Sierpinski triangle +start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ + ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< + ]>.>+[>>]>+]""", Map()) + +//Fibonacci numbers below 100 +start("""+++++++++++ + >+>>>>++++++++++++++++++++++++++++++++++++++++++++ + >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> + +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- + <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< + -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] + >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ + +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ + ++++++++++++++++++++++++++++++++++++++++++++.[-]<< + <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map()) + + +//outputs the square numbers up to 10000 +start("""++++[>+++++<-]>[<+++++>-]+<+[ + >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ + >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] + <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map()) + + +//Collatz numbers (need to be typed in) +start(""">,[[----------[ + >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] + ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ + <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] + >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] + >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> + ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map()) + + +// infinite Collatz (never stops) +start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< + <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ + +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< + [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> + [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ + <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ + ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< + +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- + ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- + >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> + -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ + +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< + <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ + +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< + <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- + [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map()) + + +*/ + +} diff -r 7ada03135b2e -r 1347bbd86c52 templates3/re.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/templates3/re.scala Thu Dec 07 12:09:06 2017 +0000 @@ -0,0 +1,127 @@ +// Part 1 about Regular Expression Matching +//========================================== + + +object CW8a { + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence +case class STAR(r: Rexp) extends Rexp // star + + +// some convenience for typing in regular expressions + +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +def charlist2rexp(s: List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + +implicit def RexpOps (r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps (s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +// (1a) Complete the function nullable according to +// the definition given in the coursework; this +// function checks whether a regular expression +// can match the empty string and Returns a boolean +// accordingly. + +//def nullable (r: Rexp) : Boolean = ... + + +// (1b) Complete the function der according to +// the definition given in the coursework; this +// function calculates the derivative of a +// regular expression w.r.t. a character. + +//def der (c: Char, r: Rexp) : Rexp = ... + + +// (1c) Complete the simp function according to +// the specification given in the coursework; this +// function simplifies a regular expression from +// the inside out, like you would simplify arithmetic +// expressions; however it does not simplify inside +// STAR-regular expressions. + +//def simp(r: Rexp) : Rexp = ... + + +// (1d) Complete the two functions below; the first +// calculates the derivative w.r.t. a string; the second +// is the regular expression matcher taking a regular +// expression and a string and checks whether the +// string matches the regular expression + +//def ders (s: List[Char], r: Rexp) : Rexp = ... + +//def matcher(r: Rexp, s: String): Boolean = ... + + +// (1e) Complete the size function for regular +// expressions according to the specification +// given in the coursework. + +//def size(r: Rexp): Int = ... + + +// some testing data + +/* +matcher(("a" ~ "b") ~ "c", "abc") // => true +matcher(("a" ~ "b") ~ "c", "ab") // => false + +// the supposedly 'evil' regular expression (a*)* b +val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +matcher(EVIL, "a" * 1000 ++ "b") // => true +matcher(EVIL, "a" * 1000) // => false + +// size without simplifications +size(der('a', der('a', EVIL))) // => 28 +size(der('a', der('a', der('a', EVIL)))) // => 58 + +// size with simplification +size(simp(der('a', der('a', EVIL)))) // => 8 +size(simp(der('a', der('a', der('a', EVIL))))) // => 8 + +// Java needs around 30 seconds for matching 28 a's with EVIL. +// +// Lets see how long it takes to match strings with +// 0.5 Million a's...it should be in the range of some +// seconds. + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + +for (i <- 0 to 5000000 by 500000) { + println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) +} + +*/ + + +} diff -r 7ada03135b2e -r 1347bbd86c52 templates3/template3/bf.scala --- a/templates3/template3/bf.scala Thu Dec 07 12:05:10 2017 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,151 +0,0 @@ -// Part 2 about an Interpreter for the Brainf*** language -//======================================================== - -object CW8b { - -type Mem = Map[Int, Int] - -// (2a) 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, if 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 = ... - - -// (2b) Implement the two jumping instructions in the -// brainf*** language. In jumpRight, given a program and -// a program counter move the counter to the right -// until the command after the *matching* ]-command. Similarly, -// jumpLeft implements the move to the left to just after -// the *matching* [-command. The levels are used to find the -// *matching* bracket. - -//def jumpRight(prog: String, pc: Int, level: Int) : Int = ... - -//def jumpLeft(prog: String, pc: Int, level: Int) : Int = ... - - - -// (2c) Complete the run function that interprets (runs) a brainf*** -// program: the arguments are a program, 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 run -// function continues with the command at the new program -// counter. -// -// Implement the start function that calls run with the program -// counter and memory counter set to 0. - -//def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = ... - -//def start(prog: String, mem: Mem) = ... - - - - - - -// some sample bf programs collected from the Internet -//================================================== - - -/* -// first some contrived (small) programs - -// clears the 0-cell -start("[-]", Map(0 -> 100)) - -// copies content of the 0-cell to 1-cell -start("[->+<]", Map(0 -> 10)) - -// copies content of the 0-cell to 2-cell and 4-cell -start("[>>+>>+<<<<-]", Map(0 -> 42)) - -start("+++[>+++++<-]", Map(0 -> 10)) - - -// prints out numbers 0 to 9 -start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map()) - - -// some more "useful" programs - -// hello world program 1 -start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ - ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) - -// hello world program 2 -start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ - +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map()) - - -// draws the Sierpinski triangle -start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ - ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< - ]>.>+[>>]>+]""", Map()) - -//Fibonacci numbers below 100 -start("""+++++++++++ - >+>>>>++++++++++++++++++++++++++++++++++++++++++++ - >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> - +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- - <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< - -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] - >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ - +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ - ++++++++++++++++++++++++++++++++++++++++++++.[-]<< - <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< - [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map()) - - -//outputs the square numbers up to 10000 -start("""++++[>+++++<-]>[<+++++>-]+<+[ - >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ - >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] - <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map()) - - -//Collatz numbers (need to be typed in) -start(""">,[[----------[ - >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] - ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ - <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] - >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] - >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> - ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map()) - - -// infinite Collatz (never stops) -start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< - <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ - +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< - [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> - [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ - <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ - ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< - +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- - ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- - >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> - -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ - +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< - <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ - +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< - <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- - [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map()) - - -*/ - -} diff -r 7ada03135b2e -r 1347bbd86c52 templates3/template3/re.scala --- a/templates3/template3/re.scala Thu Dec 07 12:05:10 2017 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,127 +0,0 @@ -// Part 1 about Regular Expression Matching -//========================================== - - -object CW8a { - -abstract class Rexp -case object ZERO extends Rexp -case object ONE extends Rexp -case class CHAR(c: Char) extends Rexp -case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative -case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence -case class STAR(r: Rexp) extends Rexp // star - - -// some convenience for typing in regular expressions - -import scala.language.implicitConversions -import scala.language.reflectiveCalls - -def charlist2rexp(s: List[Char]): Rexp = s match { - case Nil => ONE - case c::Nil => CHAR(c) - case c::s => SEQ(CHAR(c), charlist2rexp(s)) -} -implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) - -implicit def RexpOps (r: Rexp) = new { - def | (s: Rexp) = ALT(r, s) - def % = STAR(r) - def ~ (s: Rexp) = SEQ(r, s) -} - -implicit def stringOps (s: String) = new { - def | (r: Rexp) = ALT(s, r) - def | (r: String) = ALT(s, r) - def % = STAR(s) - def ~ (r: Rexp) = SEQ(s, r) - def ~ (r: String) = SEQ(s, r) -} - -// (1a) Complete the function nullable according to -// the definition given in the coursework; this -// function checks whether a regular expression -// can match the empty string and Returns a boolean -// accordingly. - -//def nullable (r: Rexp) : Boolean = ... - - -// (1b) Complete the function der according to -// the definition given in the coursework; this -// function calculates the derivative of a -// regular expression w.r.t. a character. - -//def der (c: Char, r: Rexp) : Rexp = ... - - -// (1c) Complete the simp function according to -// the specification given in the coursework; this -// function simplifies a regular expression from -// the inside out, like you would simplify arithmetic -// expressions; however it does not simplify inside -// STAR-regular expressions. - -//def simp(r: Rexp) : Rexp = ... - - -// (1d) Complete the two functions below; the first -// calculates the derivative w.r.t. a string; the second -// is the regular expression matcher taking a regular -// expression and a string and checks whether the -// string matches the regular expression - -//def ders (s: List[Char], r: Rexp) : Rexp = ... - -//def matcher(r: Rexp, s: String): Boolean = ... - - -// (1e) Complete the size function for regular -// expressions according to the specification -// given in the coursework. - -//def size(r: Rexp): Int = ... - - -// some testing data - -/* -matcher(("a" ~ "b") ~ "c", "abc") // => true -matcher(("a" ~ "b") ~ "c", "ab") // => false - -// the supposedly 'evil' regular expression (a*)* b -val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) - -matcher(EVIL, "a" * 1000 ++ "b") // => true -matcher(EVIL, "a" * 1000) // => false - -// size without simplifications -size(der('a', der('a', EVIL))) // => 28 -size(der('a', der('a', der('a', EVIL)))) // => 58 - -// size with simplification -size(simp(der('a', der('a', EVIL)))) // => 8 -size(simp(der('a', der('a', der('a', EVIL))))) // => 8 - -// Java needs around 30 seconds for matching 28 a's with EVIL. -// -// Lets see how long it takes to match strings with -// 0.5 Million a's...it should be in the range of some -// seconds. - -def time_needed[T](i: Int, code: => T) = { - val start = System.nanoTime() - for (j <- 1 to i) code - val end = System.nanoTime() - (end - start)/(i * 1.0e9) -} - -for (i <- 0 to 5000000 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) -} - -*/ - - -}