# HG changeset patch # User Christian Urban # Date 1542908130 0 # Node ID 438459a8e48b3036b642015398251bc96fd0df19 # Parent bc131735c9408346040972d7a5619d779c47495f updated diff -r bc131735c940 -r 438459a8e48b testing3/bf.scala --- 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 \n" ++ - "#include \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/ -} diff -r bc131735c940 -r 438459a8e48b testing3/bf1a_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/bf1b_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/bf1c_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/bf_test.sh --- 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 - - - - diff -r bc131735c940 -r 438459a8e48b testing3/knight1_test.scala --- /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) + diff -r bc131735c940 -r 438459a8e48b testing3/mark --- 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 - diff -r bc131735c940 -r 438459a8e48b testing3/re.scala --- 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)))) -} -*/ - -} diff -r bc131735c940 -r 438459a8e48b testing3/re1a_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/re1b_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/re1c_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/re1d_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/re1e_test.scala --- 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) diff -r bc131735c940 -r 438459a8e48b testing3/re_test.sh --- 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 - - diff -r bc131735c940 -r 438459a8e48b testing4/bf.scala --- /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 \n" ++ + "#include \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/ +} diff -r bc131735c940 -r 438459a8e48b testing4/bf1a_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/bf1b_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/bf1c_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/bf_test.sh --- /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 + + + + diff -r bc131735c940 -r 438459a8e48b testing4/mark --- /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 + diff -r bc131735c940 -r 438459a8e48b testing4/re.scala --- /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)))) +} +*/ + +} diff -r bc131735c940 -r 438459a8e48b testing4/re1a_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/re1b_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/re1c_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/re1d_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/re1e_test.scala --- /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) diff -r bc131735c940 -r 438459a8e48b testing4/re_test.sh --- /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 + +