--- a/testing3/bf.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,457 +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 =
- mem.getOrElse(mp, 0)
-
-def write(mem: Mem, mp: Int, v: Int) : Mem =
- mem.updated(mp, v)
-
-
-// (2b) 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 = {
- if (prog.length <= pc) pc
- else (prog(pc), level) match {
- case (']', 0) => pc + 1
- case (']', l) => jumpRight(prog, pc + 1, l - 1)
- case ('[', l) => jumpRight(prog, pc + 1, l + 1)
- case (_, l) => jumpRight(prog, pc + 1, l)
- }
-}
-
-def jumpLeft(prog: String, p: Int, level: Int) : Int = {
- if (p < 0) p
- else (prog(p), level) match {
- case ('[', 0) => p + 1
- case ('[', l) => jumpLeft(prog, p - 1, l - 1)
- case (']', l) => jumpLeft(prog, p - 1, l + 1)
- case (_, l) => jumpLeft(prog, p - 1, l)
- }
-}
-
-//jumpLeft("[******]***", 7, 0)
-
-// (2c) Complete the run function that interpretes (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 excution 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
-// 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 = {
- if (0 <= pc && pc < prog.length) {
- val (new_pc, new_mp, new_mem) = prog(pc) match {
- case '>' => (pc + 1, mp + 1, mem)
- case '<' => (pc + 1, mp - 1, mem)
- case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
- case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
- case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
- case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
- case '[' =>
- if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
- case ']' =>
- if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem)
- case _ => (pc + 1, mp, mem)
- }
- run(prog, new_pc, new_mp, new_mem)
- }
- else mem
-}
-
-def start(prog: String, m: Mem) = run(prog, 0, 0, m)
-
-// some sample 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))
-
-
-// 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())
-
-
-start("""+++++[>+++++++++<-],[[>--.++>+<<-]>+.->[<.>-]<<,]""", Map())
-
-*/
-
-
-def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
- case (Nil, acc) => acc
- case (c :: cs, Nil) => splice(cs, List((c, 1)))
- case (c :: cs, (d, n) :: acc) =>
- if (c == d) splice(cs, (c, n + 1) :: acc)
- else splice(cs, (c, 1) :: (d, n) :: acc)
-}
-
-def spl(s: String) = splice(s.toList, Nil).reverse
-
-
-// simple instructions
-def instr(c: Char) : String = c match {
- case '>' => "ptr++;"
- case '<' => "ptr--;"
- case '+' => "(*ptr)++;"
- case '-' => "(*ptr)--;"
- case '.' => "putchar(*ptr);"
- case ',' => "*ptr = getchar();\n"
- case '[' => "while(*ptr){"
- case ']' => "}"
- case _ => ""
-}
-
-def instrs(prog: String) : String =
- prog.toList.map(instr(_)).mkString
-
-
-//optimised instructions
-
-def instr2(c: Char, n: Int) : String = c match {
- case '>' => "ptr += " + n.toString + ";"
- case '<' => "ptr -= " + n.toString + ";"
- case '+' => "(*ptr) += " + n.toString + ";"
- case '-' => "(*ptr) -= " + n.toString + ";"
- case '.' => "putchar(*ptr);" * n
- case ',' => "*ptr = getchar();\n" * n
- case '[' => "while(*ptr){" * n
- case ']' => "}" * n
- case _ => ""
-}
-
-def instrs2(prog: String) : String =
- spl(prog).map{ case (c, n) => instr2(c, n) }.mkString
-
-
-// peephole optimisers are at
-// https://github.com/Wilfred/bfc#peephole-optimisations
-// http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html
-
-def compile_str(prog: String) : String = {
- "#include <string.h>\n" ++
- "#include <stdio.h>\n" ++
- "char field[30000];\n" ++
- "char *ptr = &field[15000];" ++
- "int main()\n{\n" ++
- "memset(field, '\\0', 30000);\n" ++
- instrs2(prog) ++
- "\n return 0;\n}"
-}
-
-def compile(name: String, prog: String) = {
- val fw = new java.io.FileWriter(name + ".c")
- val is = compile_str(prog)
- println(is)
- fw.write(is)
- fw.close()
-}
-
-import sys.process._
-
-def compile_run(prog: String) = {
- compile("tmp", prog)
- "gcc -O3 -o tmp tmp.c".!
- "./tmp".!
- ()
-}
-
-
-compile("test.bf", """++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
- ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
-
-compile_run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
- ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
- ]>.>+[>>]>+]""")
-
-compile_run(""" A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
-+++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
->>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
-<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
->+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
->>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
->>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
->>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
-[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
-<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
->>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
->+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
--<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
-<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
-[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
->>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
-<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
->>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
-+>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
-<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
->>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
->>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
-<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
-<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
->>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
-<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
-+++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
-<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
-[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
-<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
-<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
-<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
->>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
-[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
-<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
->>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
-[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
-[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
-+++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
->>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
--]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
-<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
-[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
-+>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
-<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
-[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
-<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
-<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
-<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
-<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
-<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
-]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
-[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
-+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
-<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
-<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
-[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
-[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
-[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
-<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
->[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
->>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
->>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
-<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
-<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
->>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
-[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
-+>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
-[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
->>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
->>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
-]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
-<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
->]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
-<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
-<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
-<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
-<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
-<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
-<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
-]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
->>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
-->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
->>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
->>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
-<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
-<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
->>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
-]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
->>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
->>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
->>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
-[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
-[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
-<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
->>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
->>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
-<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
->>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
->]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
->>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
-]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
-<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
->>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
-->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
->[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
-[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
-<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
-<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
-<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
->+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
-<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
-+<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
->>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
-<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
-<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
-<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
-<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
-<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
-<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
-<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
->+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
-<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
->]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
-<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
->>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
-<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
->>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
-<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
-+>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
-<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
-<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
--<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
->>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
-+[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
-<<<<<]]>>>]""")
-
-compile_run("""
->+>+>+>+>++<[>[<+++>-
-
- >>>>>
- >+>+>+>+>++<[>[<+++>-
-
- >>>>>
- >+>+>+>+>++<[>[<+++>-
-
- >>>>>
- >+>+>+>+>++<[>[<+++>-
-
- >>>>>
- +++[->+++++<]>[-]<
- <<<<<
-
- ]<<]>[-]
- <<<<<
-
- ]<<]>[-]
- <<<<<
-
- ]<<]>[-]
- <<<<<
-
-]<<]>.""")
-
-// benchmarks
-compile_run(""">++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
-[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
-++++++++[>++++++++++[>++++++++++[>++++++++++[>+
-+++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""")
-
-//
-compile_run("""++++[>++++<-]>[>+>++>[+++++++>]+++[<]>-]>>>>>>>>-.
-<<<<.<..+++.<.>>>>.<<<.+++.------.>-.<<+.<------.""")
-
-compile_run("""++++++++[->-[->-[->-[-]<]<]<]
->++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>""")
-
-
-
-
-// register to BF compiler
-// https://gergo.erdi.hu/blog/2010-09-06-from_register_machines_to_brainfuck,_part_1/
-}
--- a/testing3/bf1a_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,17 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-//lazy val f = Future {
- import CW8b._
-
- assert(sread(Map(), 2) == 0)
- assert(sread(Map(2 -> 1), 2) == 1)
- assert(write(Map(), 1, 2) == Map(1 -> 2))
- assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2))
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/bf1b_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,21 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-//lazy val f = Future {
- import CW8b._
-
- assert(jumpRight("[******]***", 1, 0) == 8)
- assert(jumpRight("[**[*]*]***", 1, 0) == 8)
- assert(jumpRight("[**[*]*]***", 1, 0) == 8)
- assert(jumpRight("[**[***]***", 1, 0) == 11)
- assert(jumpRight("[*[][]*]***", 1, 0) == 8)
- assert(jumpLeft("[******]***", 6, 0) == 1)
- assert(jumpLeft("[******]***", 7, 0) == -1)
- assert(jumpLeft("[*[][]*]***", 6, 0) == 1)
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/bf1c_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,19 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-//lazy val f = Future {
- import CW8b._
-
- assert(start("[-]", Map(0 -> 100)) == Map(0 -> 0))
- assert(start("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10))
- assert(start("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42))
- assert(start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]
- <-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) == Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87))
-
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/bf_test.sh Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,120 +0,0 @@
-#!/bin/bash
-set -e
-
-out=${1:-output}
-
-echo "" > $out
-
-echo "Below is the feedback for your submission of CW 8, Part 2." >> $out
-echo "" >> $out
-
-
-# compilation tests
-
-function scala_compile {
- (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out)
-}
-
-# functional tests
-
-function scala_assert {
- (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
-}
-
-# purity test
-
-function scala_vars {
- (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
-}
-
-
-# var, return, ListBuffer test
-#
-echo "bf.scala does not contain vars, returns etc?" >> $out
-
-if (scala_vars bf.scala)
-then
- echo " --> fail" >> $out
- tsts0=$(( 1 ))
-else
- echo " --> success" >> $out
- tsts0=$(( 0 ))
-fi
-
-
-# compilation test
-if [ $tsts0 -eq 0 ]
-then
- echo "bf.scala runs?" >> $out
-
- if (scala_compile bf.scala)
- then
- echo " --> success" >> $out
- tsts1=$(( 0 ))
- else
- echo " --> scala bf.scala did not run successfully" >> $out
- tsts1=$(( 1 ))
- fi
-else
- tsts1=$(( 1 ))
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " sread(Map(), 2) == 0" >> $out
- echo " sread(Map(2 -> 1), 2) == 1" >> $out
- echo " write(Map(), 1, 2) == Map(1 -> 2)" >> $out
- echo " write(Map(1 -> 0), 1, 2) == Map(1 -> 2)" >> $out
-
- if (scala_assert "bf.scala" "bf1a_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " jumpRight(\"[******]***\", 1, 0) == 8" >> $out
- echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out
- echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out
- echo " jumpRight(\"[**[***]***\", 1, 0) == 11" >> $out
- echo " jumpRight(\"[*[][]*]***\", 1, 0) == 8" >> $out
- echo " jumpLeft(\"[******]***\", 6, 0) == 1" >> $out
- echo " jumpLeft(\"[******]***\", 7, 0) == -1" >> $out
- echo " jumpLeft(\"[*[][]*]***\", 6, 0) == 1" >> $out
-
- if (scala_assert "bf.scala" "bf1b_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " start(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" >> $out
- echo " start(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" >> $out
- echo " start(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" >> $out
- echo " start({{hello world prg 1}}, Map()) == " >> $out
- echo " Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87)" >> $out
-
- if (scala_assert "bf.scala" "bf1c_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-
-
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing3/knight1_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,5 @@
+
+assert(CW7a.is_legal(8, Nil)(3, 4) == true)
+assert(CW7a.is_legal(8, List((4, 1), (1, 0)))(4, 1) == false)
+assert(CW7a.is_legal(2, Nil)(0, 0) == true)
+
--- a/testing3/mark Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-#!/bin/sh
-###set -e
-
-trap "exit" INT
-
-./re_test.sh output1
-./bf_test.sh output2
-
--- a/testing3/re.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,159 +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
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
-case class STAR(r: Rexp) extends Rexp
-
-// 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
-
-def nullable (r: Rexp) : Boolean = r match {
- case ZERO => false
- case ONE => true
- case CHAR(_) => false
- case ALT(r1, r2) => nullable(r1) || nullable(r2)
- case SEQ(r1, r2) => nullable(r1) && nullable(r2)
- case STAR(_) => true
-}
-
-// (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 = r match {
- case ZERO => ZERO
- case ONE => ZERO
- case CHAR(d) => if (c == d) ONE else ZERO
- case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
- case SEQ(r1, r2) =>
- if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
- else SEQ(der(c, r1), r2)
- case STAR(r1) => SEQ(der(c, r1), STAR(r1))
-}
-
-// (1c) Complete the function der according to
-// the specification given in the coursework; this
-// function simplifies a regular expression;
-// however it does not simplify inside STAR-regular
-// expressions
-
-def simp(r: Rexp) : Rexp = r match {
- case ALT(r1, r2) => (simp(r1), simp(r2)) match {
- case (ZERO, r2s) => r2s
- case (r1s, ZERO) => r1s
- case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
- }
- case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
- case (ZERO, _) => ZERO
- case (_, ZERO) => ZERO
- case (ONE, r2s) => r2s
- case (r1s, ONE) => r1s
- case (r1s, r2s) => SEQ(r1s, r2s)
- }
- case r => r
-}
-
-// (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 = s match {
- case Nil => r
- case c::s => ders(s, simp(der(c, r)))
-}
-
-// main matcher function
-def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r))
-
-// (1e) Complete the size function for regular
-// expressions according to the specification
-// given in the coursework.
-
-def size(r: Rexp): Int = r match {
- case ZERO => 1
- case ONE => 1
- case CHAR(_) => 1
- case ALT(r1, r2) => 1 + size(r1) + size (r2)
- case SEQ(r1, r2) => 1 + size(r1) + size (r2)
- case STAR(r1) => 1 + size(r1)
-}
-
-
-
-// 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))))
-}
-*/
-
-}
--- a/testing3/re1a_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,21 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-//lazy val f = Future {
- import CW8a._
-
- assert(nullable(ZERO) == false)
- assert(nullable(ONE) == true)
- assert(nullable(CHAR('a')) == false)
- assert(nullable(ZERO | ONE) == true)
- assert(nullable(ZERO | CHAR('a')) == false)
- assert(nullable(ONE ~ ONE) == true)
- assert(nullable(ONE ~ CHAR('a')) == false)
- assert(nullable(STAR(ZERO)) == true)
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/re1b_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,18 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-
-//lazy val f = Future {
- import CW8a._
-
- assert(der('a', ZERO | ONE) == (ZERO | ZERO))
- assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE))
- assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
- assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/re1c_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,24 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-
-//lazy val f = Future {
- import CW8a._
-
- assert(simp(ZERO | ONE) == ONE)
- assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE))
- assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a'))
- assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO)
- assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a'))
- assert(simp(CHAR('a') | CHAR('a')) == CHAR('a'))
- assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a')))
- assert(simp(ALT((CHAR('a') | ZERO) ~ ONE,
- ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a'))
-
-//}
-
-//Await.result(f, 30 second)
--- a/testing3/re1d_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,41 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-
-
-//lazy val f = Future {
- import CW8a._
-
- val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-
- //println("1")
- assert(ders(List.fill(5)('a'), EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b')))
- //println("2")
- assert(ders(List('b'), EVIL_urban) == ONE)
- //println("3")
- assert(ders(List('b','b'), EVIL_urban) == ZERO)
- //println("4")
- assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
- //println("5")
- assert(matcher(EVIL_urban, "b") == true)
- //println("6")
- assert(matcher(EVIL_urban, "bb") == false)
- //println("7")
- assert(matcher("abc", "abc") == true)
- //println("8")
- assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
- //println("9")
- assert(matcher(ONE, "") == true)
- //println("10")
- assert(matcher(ZERO, "") == false)
- //println("11")
- assert(matcher(ONE | CHAR('a'), "") == true)
- //println("12")
- assert(matcher(ONE | CHAR('a'), "a") == true)
-//}
-
-//Await.result(f, 90 second)
--- a/testing3/re1e_test.scala Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,19 +0,0 @@
-
-//import scala.concurrent._
-//import scala.concurrent.duration._
-//import ExecutionContext.Implicits.global
-//import scala.language.postfixOps
-//import scala.language.reflectiveCalls
-
-//lazy val f = Future {
- import CW8a._
-
- val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
-
- assert(size(der('a', der('a', EVIL_urban))) == 28)
- assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58)
-
- assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8)
-//}
-
-//Await.result(f, 120 second)
--- a/testing3/re_test.sh Thu Nov 22 17:20:32 2018 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,162 +0,0 @@
-#!/bin/bash
-set -e
-
-out=${1:-output}
-
-echo "" > $out
-
-echo "Below is the feedback for your submission of CW 8, Part 1." >> $out
-echo "" >> $out
-
-
-# compilation tests
-
-function scala_compile {
- (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out)
-}
-
-# functional tests
-
-function scala_assert {
- (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
-}
-
-# purity test
-
-function scala_vars {
- (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
-}
-
-
-# var, return, ListBuffer test
-#
-echo "re.scala does not contain vars, returns etc?" >> $out
-
-if (scala_vars re.scala)
-then
- echo " --> fail" >> $out
- tsts0=$(( 1 ))
-else
- echo " --> yes" >> $out
- tsts0=$(( 0 ))
-fi
-
-
-# compilation test
-if [ $tsts0 -eq 0 ]
-then
- echo "re.scala runs?" >> $out
-
- if (scala_compile re.scala)
- then
- echo " --> yes" >> $out
- tsts1=$(( 0 ))
- else
- echo " --> scala re.scala did not run successfully" >> $out
- tsts1=$(( 1 ))
- fi
-else
- tsts1=$(( 1 ))
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " nullable(ZERO) == false" >> $out
- echo " nullable(ONE) == true" >> $out
- echo " nullable(CHAR('a')) == false" >> $out
- echo " nullable(ZERO | ONE) == true" >> $out
- echo " nullable(ZERO | CHAR('a')) == false" >> $out
- echo " nullable(ONE ~ ONE) == true" >> $out
- echo " nullable(ONE ~ CHAR('a')) == false" >> $out
- echo " nullable(STAR(ZERO)) == true" >> $out
-
- if (scala_assert "re.scala" "re1a_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " der('a', ZERO | ONE) == (ZERO | ZERO)" >> $out
- echo " der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)" >> $out
- echo " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" >> $out
- echo " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" >> $out
-
- if (scala_assert "re.scala" "re1b_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " simp(ZERO | ONE) == ONE" >> $out
- echo " simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)" >> $out
- echo " simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')" >> $out
- echo " simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO" >> $out
- echo " simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')" >> $out
- echo " simp(CHAR('a') | CHAR('a')) == CHAR('a')" >> $out
- echo " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" >> $out
- echo " simp(ALT((CHAR('a') | ZERO) ~ ONE," >> $out
- echo " ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')" >> $out
- if (scala_assert "re.scala" "re1c_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out
- echo " ders(List.fill(5)('a'),EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" >> $out
- echo " ders(List('b'),EVIL) == ONE" >> $out
- echo " ders(List('b','b'),EVIL) == ZERO" >> $out
- echo " matcher(EVIL, \"a\" * 5 ++ \"b\") == true" >> $out
- echo " matcher(EVIL, \"b\") == true" >> $out
- echo " matcher(EVIL, \"bb\") == false" >> $out
- echo " matcher(\"abc\", \"abc\") == true" >> $out
- echo " matcher((\"ab\" | \"a\") ~ (ONE | \"bc\"), \"abc\") == true" >> $out
- echo " matcher(ONE, \"\") == true" >> $out
- echo " matcher(ZERO, \"\") == false" >> $out
- echo " matcher(ONE | CHAR('a'), \"\") == true" >> $out
- echo " matcher(ONE | CHAR('a'), \"a\") == true" >> $out
-
- if (scala_assert "re.scala" "re1d_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
-if [ $tsts1 -eq 0 ]
-then
- echo " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out
- echo " size(der('a', der('a', EVIL))) == 28" >> $out
- echo " size(der('a', der('a', der('a', EVIL)))) == 58" >> $out
- echo " size(ders(\"aaaaaa\".toList, EVIL)) == 8" >> $out
-
- if (scala_assert "re.scala" "re1e_test.scala")
- then
- echo " --> success" >> $out
- else
- echo " --> test failed" >> $out
- fi
-fi
-
-
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/bf.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,457 @@
+// 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 =
+ mem.getOrElse(mp, 0)
+
+def write(mem: Mem, mp: Int, v: Int) : Mem =
+ mem.updated(mp, v)
+
+
+// (2b) 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 = {
+ if (prog.length <= pc) pc
+ else (prog(pc), level) match {
+ case (']', 0) => pc + 1
+ case (']', l) => jumpRight(prog, pc + 1, l - 1)
+ case ('[', l) => jumpRight(prog, pc + 1, l + 1)
+ case (_, l) => jumpRight(prog, pc + 1, l)
+ }
+}
+
+def jumpLeft(prog: String, p: Int, level: Int) : Int = {
+ if (p < 0) p
+ else (prog(p), level) match {
+ case ('[', 0) => p + 1
+ case ('[', l) => jumpLeft(prog, p - 1, l - 1)
+ case (']', l) => jumpLeft(prog, p - 1, l + 1)
+ case (_, l) => jumpLeft(prog, p - 1, l)
+ }
+}
+
+//jumpLeft("[******]***", 7, 0)
+
+// (2c) Complete the run function that interpretes (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 excution 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
+// 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 = {
+ if (0 <= pc && pc < prog.length) {
+ val (new_pc, new_mp, new_mem) = prog(pc) match {
+ case '>' => (pc + 1, mp + 1, mem)
+ case '<' => (pc + 1, mp - 1, mem)
+ case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1))
+ case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1))
+ case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) }
+ case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte))
+ case '[' =>
+ if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case ']' =>
+ if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem)
+ case _ => (pc + 1, mp, mem)
+ }
+ run(prog, new_pc, new_mp, new_mem)
+ }
+ else mem
+}
+
+def start(prog: String, m: Mem) = run(prog, 0, 0, m)
+
+// some sample 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))
+
+
+// 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())
+
+
+start("""+++++[>+++++++++<-],[[>--.++>+<<-]>+.->[<.>-]<<,]""", Map())
+
+*/
+
+
+def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match {
+ case (Nil, acc) => acc
+ case (c :: cs, Nil) => splice(cs, List((c, 1)))
+ case (c :: cs, (d, n) :: acc) =>
+ if (c == d) splice(cs, (c, n + 1) :: acc)
+ else splice(cs, (c, 1) :: (d, n) :: acc)
+}
+
+def spl(s: String) = splice(s.toList, Nil).reverse
+
+
+// simple instructions
+def instr(c: Char) : String = c match {
+ case '>' => "ptr++;"
+ case '<' => "ptr--;"
+ case '+' => "(*ptr)++;"
+ case '-' => "(*ptr)--;"
+ case '.' => "putchar(*ptr);"
+ case ',' => "*ptr = getchar();\n"
+ case '[' => "while(*ptr){"
+ case ']' => "}"
+ case _ => ""
+}
+
+def instrs(prog: String) : String =
+ prog.toList.map(instr(_)).mkString
+
+
+//optimised instructions
+
+def instr2(c: Char, n: Int) : String = c match {
+ case '>' => "ptr += " + n.toString + ";"
+ case '<' => "ptr -= " + n.toString + ";"
+ case '+' => "(*ptr) += " + n.toString + ";"
+ case '-' => "(*ptr) -= " + n.toString + ";"
+ case '.' => "putchar(*ptr);" * n
+ case ',' => "*ptr = getchar();\n" * n
+ case '[' => "while(*ptr){" * n
+ case ']' => "}" * n
+ case _ => ""
+}
+
+def instrs2(prog: String) : String =
+ spl(prog).map{ case (c, n) => instr2(c, n) }.mkString
+
+
+// peephole optimisers are at
+// https://github.com/Wilfred/bfc#peephole-optimisations
+// http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html
+
+def compile_str(prog: String) : String = {
+ "#include <string.h>\n" ++
+ "#include <stdio.h>\n" ++
+ "char field[30000];\n" ++
+ "char *ptr = &field[15000];" ++
+ "int main()\n{\n" ++
+ "memset(field, '\\0', 30000);\n" ++
+ instrs2(prog) ++
+ "\n return 0;\n}"
+}
+
+def compile(name: String, prog: String) = {
+ val fw = new java.io.FileWriter(name + ".c")
+ val is = compile_str(prog)
+ println(is)
+ fw.write(is)
+ fw.close()
+}
+
+import sys.process._
+
+def compile_run(prog: String) = {
+ compile("tmp", prog)
+ "gcc -O3 -o tmp tmp.c".!
+ "./tmp".!
+ ()
+}
+
+
+compile("test.bf", """++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.""")
+
+compile_run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[
+ ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<<
+ ]>.>+[>>]>+]""")
+
+compile_run(""" A mandelbrot set fractal viewer in brainf*** written by Erik Bosman
++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+
+<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>>
+>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>>
+>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>>
+>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>>
+>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>
+[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<
+<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[
+>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[
+>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[
+-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<
+<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<
+[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>
+>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+
+<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>
+>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<
++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<
+<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<
+<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->
+>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<
+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++
++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>-
+<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>>
+[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<<
+<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[-
+]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<<
+<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]<
+<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>>
+>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>>
+[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-<
+<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>>
+]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
+]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++
++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+
+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[
+-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-<
+<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<<
+[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]
++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<<
+<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<
+[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<
+<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<
+<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<<
+<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<<
+<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<<
+]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<<
+[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<<
++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<<
+<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<
+<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[
+[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>
+[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<
+<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[
+>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[
+>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>
+>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<
+<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<
+<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-
+<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>
+>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>>
+[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<<
++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]>
+[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>
+>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>>
+>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<<
+]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<<
+<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>
+>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<<
+<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<
+<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]<
+<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<
+<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+
+<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<<
+]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+>
+>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>-
+<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[
+->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>>
+>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<
+<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<
+<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+
+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>>
+]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>
+>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>
+>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+
+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>
+[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-
+]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>>
+[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<
+<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>
+>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>>
+>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+
+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
+>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>
+>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<]
+>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<<
+]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+<
+<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>
+>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<<
+->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[
+>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<<
+[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<<
+<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<<
+<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<<
+<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>>
+>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<
+<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]<
++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>>
+>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<
+<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<<
+<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<<
+<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-<
+<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<<
+<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<
+<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<<
+<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>>
+>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<<
+<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>>
+>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<<
+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>>
+>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<-
+>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<
+<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>>
+>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<
+<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>
++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+<
+<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<<
+<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>
+-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>
+>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++
++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<<
+<<<<<]]>>>]""")
+
+compile_run("""
+>+>+>+>+>++<[>[<+++>-
+
+ >>>>>
+ >+>+>+>+>++<[>[<+++>-
+
+ >>>>>
+ >+>+>+>+>++<[>[<+++>-
+
+ >>>>>
+ >+>+>+>+>++<[>[<+++>-
+
+ >>>>>
+ +++[->+++++<]>[-]<
+ <<<<<
+
+ ]<<]>[-]
+ <<<<<
+
+ ]<<]>[-]
+ <<<<<
+
+ ]<<]>[-]
+ <<<<<
+
+]<<]>.""")
+
+// benchmarks
+compile_run(""">++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
+[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
+++++++++[>++++++++++[>++++++++++[>++++++++++[>+
++++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""")
+
+//
+compile_run("""++++[>++++<-]>[>+>++>[+++++++>]+++[<]>-]>>>>>>>>-.
+<<<<.<..+++.<.>>>>.<<<.+++.------.>-.<<+.<------.""")
+
+compile_run("""++++++++[->-[->-[->-[-]<]<]<]
+>++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>""")
+
+
+
+
+// register to BF compiler
+// https://gergo.erdi.hu/blog/2010-09-06-from_register_machines_to_brainfuck,_part_1/
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/bf1a_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,17 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+ import CW8b._
+
+ assert(sread(Map(), 2) == 0)
+ assert(sread(Map(2 -> 1), 2) == 1)
+ assert(write(Map(), 1, 2) == Map(1 -> 2))
+ assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2))
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/bf1b_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,21 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+ import CW8b._
+
+ assert(jumpRight("[******]***", 1, 0) == 8)
+ assert(jumpRight("[**[*]*]***", 1, 0) == 8)
+ assert(jumpRight("[**[*]*]***", 1, 0) == 8)
+ assert(jumpRight("[**[***]***", 1, 0) == 11)
+ assert(jumpRight("[*[][]*]***", 1, 0) == 8)
+ assert(jumpLeft("[******]***", 6, 0) == 1)
+ assert(jumpLeft("[******]***", 7, 0) == -1)
+ assert(jumpLeft("[*[][]*]***", 6, 0) == 1)
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/bf1c_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,19 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+ import CW8b._
+
+ assert(start("[-]", Map(0 -> 100)) == Map(0 -> 0))
+ assert(start("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10))
+ assert(start("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42))
+ assert(start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]
+ <-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) == Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87))
+
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/bf_test.sh Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,120 @@
+#!/bin/bash
+set -e
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback for your submission of CW 8, Part 2." >> $out
+echo "" >> $out
+
+
+# compilation tests
+
+function scala_compile {
+ (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out)
+}
+
+# functional tests
+
+function scala_assert {
+ (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+# purity test
+
+function scala_vars {
+ (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+# var, return, ListBuffer test
+#
+echo "bf.scala does not contain vars, returns etc?" >> $out
+
+if (scala_vars bf.scala)
+then
+ echo " --> fail" >> $out
+ tsts0=$(( 1 ))
+else
+ echo " --> success" >> $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo "bf.scala runs?" >> $out
+
+ if (scala_compile bf.scala)
+ then
+ echo " --> success" >> $out
+ tsts1=$(( 0 ))
+ else
+ echo " --> scala bf.scala did not run successfully" >> $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " sread(Map(), 2) == 0" >> $out
+ echo " sread(Map(2 -> 1), 2) == 1" >> $out
+ echo " write(Map(), 1, 2) == Map(1 -> 2)" >> $out
+ echo " write(Map(1 -> 0), 1, 2) == Map(1 -> 2)" >> $out
+
+ if (scala_assert "bf.scala" "bf1a_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " jumpRight(\"[******]***\", 1, 0) == 8" >> $out
+ echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out
+ echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out
+ echo " jumpRight(\"[**[***]***\", 1, 0) == 11" >> $out
+ echo " jumpRight(\"[*[][]*]***\", 1, 0) == 8" >> $out
+ echo " jumpLeft(\"[******]***\", 6, 0) == 1" >> $out
+ echo " jumpLeft(\"[******]***\", 7, 0) == -1" >> $out
+ echo " jumpLeft(\"[*[][]*]***\", 6, 0) == 1" >> $out
+
+ if (scala_assert "bf.scala" "bf1b_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " start(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" >> $out
+ echo " start(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" >> $out
+ echo " start(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" >> $out
+ echo " start({{hello world prg 1}}, Map()) == " >> $out
+ echo " Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87)" >> $out
+
+ if (scala_assert "bf.scala" "bf1c_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/mark Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,8 @@
+#!/bin/sh
+###set -e
+
+trap "exit" INT
+
+./re_test.sh output1
+./bf_test.sh output2
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,159 @@
+// 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
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+case class STAR(r: Rexp) extends Rexp
+
+// 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
+
+def nullable (r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ case STAR(_) => true
+}
+
+// (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 = r match {
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
+ case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+ else SEQ(der(c, r1), r2)
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
+}
+
+// (1c) Complete the function der according to
+// the specification given in the coursework; this
+// function simplifies a regular expression;
+// however it does not simplify inside STAR-regular
+// expressions
+
+def simp(r: Rexp) : Rexp = r match {
+ case ALT(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, r2s) => r2s
+ case (r1s, ZERO) => r1s
+ case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+ }
+ case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ZERO, _) => ZERO
+ case (_, ZERO) => ZERO
+ case (ONE, r2s) => r2s
+ case (r1s, ONE) => r1s
+ case (r1s, r2s) => SEQ(r1s, r2s)
+ }
+ case r => r
+}
+
+// (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 = s match {
+ case Nil => r
+ case c::s => ders(s, simp(der(c, r)))
+}
+
+// main matcher function
+def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r))
+
+// (1e) Complete the size function for regular
+// expressions according to the specification
+// given in the coursework.
+
+def size(r: Rexp): Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALT(r1, r2) => 1 + size(r1) + size (r2)
+ case SEQ(r1, r2) => 1 + size(r1) + size (r2)
+ case STAR(r1) => 1 + size(r1)
+}
+
+
+
+// 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))))
+}
+*/
+
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re1a_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,21 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+ import CW8a._
+
+ assert(nullable(ZERO) == false)
+ assert(nullable(ONE) == true)
+ assert(nullable(CHAR('a')) == false)
+ assert(nullable(ZERO | ONE) == true)
+ assert(nullable(ZERO | CHAR('a')) == false)
+ assert(nullable(ONE ~ ONE) == true)
+ assert(nullable(ONE ~ CHAR('a')) == false)
+ assert(nullable(STAR(ZERO)) == true)
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re1b_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,18 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+
+//lazy val f = Future {
+ import CW8a._
+
+ assert(der('a', ZERO | ONE) == (ZERO | ZERO))
+ assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE))
+ assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))))
+ assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))))
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re1c_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,24 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+
+//lazy val f = Future {
+ import CW8a._
+
+ assert(simp(ZERO | ONE) == ONE)
+ assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE))
+ assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a'))
+ assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO)
+ assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a'))
+ assert(simp(CHAR('a') | CHAR('a')) == CHAR('a'))
+ assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a')))
+ assert(simp(ALT((CHAR('a') | ZERO) ~ ONE,
+ ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a'))
+
+//}
+
+//Await.result(f, 30 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re1d_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,41 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+
+
+//lazy val f = Future {
+ import CW8a._
+
+ val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+ //println("1")
+ assert(ders(List.fill(5)('a'), EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b')))
+ //println("2")
+ assert(ders(List('b'), EVIL_urban) == ONE)
+ //println("3")
+ assert(ders(List('b','b'), EVIL_urban) == ZERO)
+ //println("4")
+ assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true)
+ //println("5")
+ assert(matcher(EVIL_urban, "b") == true)
+ //println("6")
+ assert(matcher(EVIL_urban, "bb") == false)
+ //println("7")
+ assert(matcher("abc", "abc") == true)
+ //println("8")
+ assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true)
+ //println("9")
+ assert(matcher(ONE, "") == true)
+ //println("10")
+ assert(matcher(ZERO, "") == false)
+ //println("11")
+ assert(matcher(ONE | CHAR('a'), "") == true)
+ //println("12")
+ assert(matcher(ONE | CHAR('a'), "a") == true)
+//}
+
+//Await.result(f, 90 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re1e_test.scala Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,19 @@
+
+//import scala.concurrent._
+//import scala.concurrent.duration._
+//import ExecutionContext.Implicits.global
+//import scala.language.postfixOps
+//import scala.language.reflectiveCalls
+
+//lazy val f = Future {
+ import CW8a._
+
+ val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+ assert(size(der('a', der('a', EVIL_urban))) == 28)
+ assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58)
+
+ assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8)
+//}
+
+//Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/testing4/re_test.sh Thu Nov 22 17:35:30 2018 +0000
@@ -0,0 +1,162 @@
+#!/bin/bash
+set -e
+
+out=${1:-output}
+
+echo "" > $out
+
+echo "Below is the feedback for your submission of CW 8, Part 1." >> $out
+echo "" >> $out
+
+
+# compilation tests
+
+function scala_compile {
+ (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out)
+}
+
+# functional tests
+
+function scala_assert {
+ (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null)
+}
+
+# purity test
+
+function scala_vars {
+ (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null)
+}
+
+
+# var, return, ListBuffer test
+#
+echo "re.scala does not contain vars, returns etc?" >> $out
+
+if (scala_vars re.scala)
+then
+ echo " --> fail" >> $out
+ tsts0=$(( 1 ))
+else
+ echo " --> yes" >> $out
+ tsts0=$(( 0 ))
+fi
+
+
+# compilation test
+if [ $tsts0 -eq 0 ]
+then
+ echo "re.scala runs?" >> $out
+
+ if (scala_compile re.scala)
+ then
+ echo " --> yes" >> $out
+ tsts1=$(( 0 ))
+ else
+ echo " --> scala re.scala did not run successfully" >> $out
+ tsts1=$(( 1 ))
+ fi
+else
+ tsts1=$(( 1 ))
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " nullable(ZERO) == false" >> $out
+ echo " nullable(ONE) == true" >> $out
+ echo " nullable(CHAR('a')) == false" >> $out
+ echo " nullable(ZERO | ONE) == true" >> $out
+ echo " nullable(ZERO | CHAR('a')) == false" >> $out
+ echo " nullable(ONE ~ ONE) == true" >> $out
+ echo " nullable(ONE ~ CHAR('a')) == false" >> $out
+ echo " nullable(STAR(ZERO)) == true" >> $out
+
+ if (scala_assert "re.scala" "re1a_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " der('a', ZERO | ONE) == (ZERO | ZERO)" >> $out
+ echo " der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)" >> $out
+ echo " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" >> $out
+ echo " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" >> $out
+
+ if (scala_assert "re.scala" "re1b_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " simp(ZERO | ONE) == ONE" >> $out
+ echo " simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)" >> $out
+ echo " simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')" >> $out
+ echo " simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO" >> $out
+ echo " simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')" >> $out
+ echo " simp(CHAR('a') | CHAR('a')) == CHAR('a')" >> $out
+ echo " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" >> $out
+ echo " simp(ALT((CHAR('a') | ZERO) ~ ONE," >> $out
+ echo " ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')" >> $out
+ if (scala_assert "re.scala" "re1c_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out
+ echo " ders(List.fill(5)('a'),EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" >> $out
+ echo " ders(List('b'),EVIL) == ONE" >> $out
+ echo " ders(List('b','b'),EVIL) == ZERO" >> $out
+ echo " matcher(EVIL, \"a\" * 5 ++ \"b\") == true" >> $out
+ echo " matcher(EVIL, \"b\") == true" >> $out
+ echo " matcher(EVIL, \"bb\") == false" >> $out
+ echo " matcher(\"abc\", \"abc\") == true" >> $out
+ echo " matcher((\"ab\" | \"a\") ~ (ONE | \"bc\"), \"abc\") == true" >> $out
+ echo " matcher(ONE, \"\") == true" >> $out
+ echo " matcher(ZERO, \"\") == false" >> $out
+ echo " matcher(ONE | CHAR('a'), \"\") == true" >> $out
+ echo " matcher(ONE | CHAR('a'), \"a\") == true" >> $out
+
+ if (scala_assert "re.scala" "re1d_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" >> $out
+ echo " size(der('a', der('a', EVIL))) == 28" >> $out
+ echo " size(der('a', der('a', der('a', EVIL)))) == 58" >> $out
+ echo " size(ders(\"aaaaaa\".toList, EVIL)) == 8" >> $out
+
+ if (scala_assert "re.scala" "re1e_test.scala")
+ then
+ echo " --> success" >> $out
+ else
+ echo " --> test failed" >> $out
+ fi
+fi
+
+