# HG changeset patch # User Christian Urban # Date 1595811305 -3600 # Node ID 923b946347e6f58f57e7b0ef0dd8c70757dff189 # Parent 220aea0e5517957668dade8cae46ec359d56b7ab updated diff -r 220aea0e5517 -r 923b946347e6 handouts/graphs.pdf Binary file handouts/graphs.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho05.pdf Binary file handouts/ho05.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho07.pdf Binary file handouts/ho07.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho09.pdf Binary file handouts/ho09.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/ho10.pdf Binary file handouts/ho10.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r 220aea0e5517 -r 923b946347e6 progs/bf/benchmark.bf --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/bf/benchmark.bf Mon Jul 27 01:55:05 2020 +0100 @@ -0,0 +1,4 @@ +>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ +[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ +++++++++[>++++++++++[>++++++++++[>++++++++++[>+ ++++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++. \ No newline at end of file diff -r 220aea0e5517 -r 923b946347e6 progs/bf/bfc0.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/bf/bfc0.sc Mon Jul 27 01:55:05 2020 +0100 @@ -0,0 +1,71 @@ +// A Transpiler for the Brainf*** language to C +//=============================================== +// +// Call with +// +// amm bfc0.sc <> +// +// +// Note: An interesting exercise is to call +// gcc with -O3 instead of -O0 + +// simple instructions +def instr(c: Char) : String = c match { + case '>' => "ptr++;" + case '<' => "ptr--;" + case '+' => "(*ptr)++;" + case '-' => "(*ptr)--;" + case '.' => "putchar(*ptr);" + case ',' => "*ptr = getchar();" + case '[' => "while(*ptr){" + case ']' => "}" + case _ => "" +} + +def instrs(prog: String) : String = + prog.toList.map(instr(_)).mkString + +// adding the boilerplate +def compile(prog: String) : String = + s"""#include + #include + char field[30000]; + char *ptr = &field[15000]; + int main() { + memset(field, '\\0', 30000); + ${instrs(prog)} + return 0;}""" + +def compile_file(name: String, prog: String) = + os.write.over(os.pwd / name, compile(prog)) + + +// running the c-compiler over the transpiled +// BF program and running the resulting binary + +def compile_run(prog: String) = { + val tn = "tmp" + compile_file(s"${tn}.c", prog) + os.proc("gcc", "-O0", "-o", tn, s"${tn}.c").call() // call gcc + os.proc("./tmp").call(stdout = os.Inherit) // run binary +} + +// Running Testcases +//=================== + +def time_needed[T](n: Int, code: => T) = { + val start = System.nanoTime() + for (i <- 0 until n) code + val end = System.nanoTime() + (end - start)/(n * 1.0e9) +} + +@doc(" the argument should be a BF program ") +@main +def main(fname: String) = { + val bf_str = os.read(os.pwd / fname) + println(s"${time_needed(1, compile_run(bf_str))} secs") +} + + + diff -r 220aea0e5517 -r 923b946347e6 progs/bf/bfc0.scala --- a/progs/bf/bfc0.scala Fri Jul 24 13:06:09 2020 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,83 +0,0 @@ -// A Transpiler for the Brainf*** language to C -//=============================================== -// -// Call with -// -// amm bfc0.sc <> -// - - -import scala.util._ - - -// loding a bf-file -def load_bff(name: String) : String = - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") - - -// 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 - - -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" ++ - instrs(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() -} - -// running the c-compiler over the transpiled -// BF program and running the result -import sys.process._ - -def compile_run(prog: String) = { - compile("tmp", prog) - "gcc -O3 -o tmp tmp.c".! - "./tmp".! - () -} - -def time_needed[T](n: Int, code: => T) = { - val start = System.nanoTime() - for (i <- 0 until n) code - val end = System.nanoTime() - (end - start)/(n * 1.0e9) -} - -// Running Testcases -//=================== - -@doc(" the argument should be a BF program ") -@main -def main(fname: String) = { - val bf_str = os.read(os.pwd / fname) - println(s"${time_needed(1, run(bf_str))} secs") -} - - - diff -r 220aea0e5517 -r 923b946347e6 progs/bf/bfc1.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/bf/bfc1.sc Mon Jul 27 01:55:05 2020 +0100 @@ -0,0 +1,84 @@ +// A Transpiler for the Brainf*** language +//========================================= +// +// This version "optimises" the code by replacing +// for example +++ by (*ptr) += 3, instead of +// (*ptr)++, (*ptr)++, (*ptr)++ +// +// Call with +// +// amm bfc1.sc <> +// + + +// generating "compound" c-instructions +def instr2(c: Char, n: Int) : String = c match { + case '>' => s"ptr += $n ;" + case '<' => s"ptr -= $n ;" + case '+' => s"(*ptr) += $n ;" + case '-' => s"(*ptr) -= $n ;" + case '.' => "putchar(*ptr);" * n + case ',' => "*ptr = getchar(); " * n + case '[' => "while(*ptr){" * n + case ']' => "}" * n + case _ => "" +} + +// "splicing" a BF program into "spans" +// and counting the number of occurrences in +// each span; then generate the new intruction +// accordingly + +def splice(cs: List[Char], acc: List[String]) : List[String] = cs match { + case Nil => acc + case hd :: _ => { + val (hds, rest) = cs.span(_ == hd) + splice(rest, instr2(hd, hds.length) :: acc) + } +} + +def instrs2(prog: String) : String = + splice(prog.toList, Nil).reverse.mkString + +// adding the boilerplate +def compile(prog: String) : String = + s"""#include + #include + char field[30000]; + char *ptr = &field[15000]; + int main() { + memset(field, '\\0', 30000); + ${instrs2(prog)} + return 0;}""" + +def compile_file(name: String, prog: String) = + os.write.over(os.pwd / name, compile(prog)) + + +// running the c-compiler over the transpiled +// BF program and running the resulting binary + +def compile_run(prog: String) = { + val tn = "tmp" + compile_file(s"${tn}.c", prog) + os.proc("gcc", "-O0", "-o", tn, s"${tn}.c").call() // call gcc + os.proc("./tmp").call(stdout = os.Inherit) // run binary +} + +// Running Testcases +//=================== + +def time_needed[T](n: Int, code: => T) = { + val start = System.nanoTime() + for (i <- 0 until n) code + val end = System.nanoTime() + (end - start)/(n * 1.0e9) +} + +@doc(" the argument should be a BF program ") +@main +def main(fname: String) = { + val bf_str = os.read(os.pwd / fname) + println(s"${time_needed(1, compile_run(bf_str))} secs") +} + diff -r 220aea0e5517 -r 923b946347e6 progs/bf/bfc1.scala --- a/progs/bf/bfc1.scala Fri Jul 24 13:06:09 2020 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,91 +0,0 @@ -// A Transpiler for the Brainf*** language -//========================================= - -import io.Source -import scala.util._ - - -// loding a bf-file -def load_bff(name: String) : String = - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") - -// "splicing" a BF program counting occurrences -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 - -// generating "compound" c-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 - - -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 -O0 -o tmp tmp.c".! - "./tmp".! - () -} - -def time_needed[T](n: Int, code: => T) = { - val start = System.nanoTime() - for (i <- 0 until n) code - val end = System.nanoTime() - (end - start) / (n * 1.0e9) -} - -// the mandelbrot program -val b0 = load_bff("mandelbrot.bf") - -println(s"${time_needed(1, compile_run(b0))} secs") - - - -// a benchmark program (counts down from 'Z' to 'A') -val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ - [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ - ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ - +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" - -println(s"${time_needed(1, compile_run(b1))} secs") - -