# HG changeset patch # User Christian Urban # Date 1708687896 0 # Node ID 1a51207780e6bafc59d460fdd2e386f03369bf2a # Parent 769bda18a43dcd17dc1f667b2f2b7a5204215751 updated diff -r 769bda18a43d -r 1a51207780e6 cws/calculation.pdf Binary file cws/calculation.pdf has changed diff -r 769bda18a43d -r 1a51207780e6 cws/main_cw03.pdf Binary file cws/main_cw03.pdf has changed diff -r 769bda18a43d -r 1a51207780e6 cws/main_cw03.tex --- a/cws/main_cw03.tex Mon Dec 25 01:10:55 2023 +0100 +++ b/cws/main_cw03.tex Fri Feb 23 11:31:36 2024 +0000 @@ -574,11 +574,130 @@ \end{tikzpicture} \end{tabular} \end{center} + +%\end{document} \newpage +\noindent +For the calculation below, I prefer to use the more ``mathematical'' +notation for regular expressions. Therefore let us first look at this +notation and the corresponding Scala code. + +\begin{center} +\begin{tabular}{r@{\hspace{10mm}}l} + ``mathematical'' notation & \\ + for regular expressions & Scala code\smallskip\\ + $\ZERO$ & \texttt{ZERO}\\ + $\ONE$ & \texttt{ONE}\\ + $c$ & \texttt{CHAR(c)}\\ + $\sum rs$ & \texttt{ALTs(rs)}\\ + $\prod rs$ & \texttt{SEQs(rs)}\\ + $r^*$ & \texttt{STAR(r)} +\end{tabular} +\end{center} + +\noindent +My own convention is that \texttt{rs} stands for a list of regular +expressions. Also of note is that these are \textbf{all} regular +expressions in Main 3 and the template file defines them as the +(algebraic) datatype \texttt{Rexp}. A confusion might arise from the +fact that there is also some shorthand notation for some regular +expressions, namely + +\begin{lstlisting}[xleftmargin=10mm,numbers=none] +def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) +def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2)) +\end{lstlisting} + +\noindent +Since these are functions, everything of the form \texttt{ALT(r1, r2)} +will immediately be translated into the regular expression +\texttt{ALTs(List(r1, r2))} (similarly for \texttt{SEQ}). Maybe even +more confusing is that Scala allows one to define +\textit{extensions} that provide an even shorter notation for +\texttt{ALT} and \texttt{SEQ}, namely + +\begin{center} +\begin{tabular}{lclcl} + \texttt{r1} $\sim$ \texttt{r2} & $\dn$ & \texttt{SEQ(r1, r2)} & $\dn$ & \texttt{SEQs(List(r1, r2))}\\ + \texttt{r1} $|$ \texttt{r2} & $\dn$ & \texttt{ALT(r1, r2)} & $\dn$ & \texttt{ALTs(List(r1, r2))}\\ +\end{tabular} +\end{center} + +\noindent +The right hand sides are the fully expanded definitions. +The reason for this even shorter notation is that in the mathematical +notation one often writes + +\begin{center} +\begin{tabular}{lcl} + $r_1 \;\cdot\; r_2$ & $\dn$ & $\prod\;[r_1, r_2]$\\ + $r_1 + r_2$ & $\dn$ & $\sum\;[r_1, r_2]$ +\end{tabular} +\end{center} + +\noindent +The first one is for binary \textit{sequence} regular expressions and +the second for binary \textit{alternative} regular expressions. +The regex in question in the shorthand notation is $(a + 1)\cdot a$, +which is the same as + +\[ +\prod\; [\Sigma\,[a, 1], a] +\] + +\noindent +or in Scala code + +\[ +\texttt{(CHAR('a') | ONE)} \;\sim\; \texttt{CHAR('a')} +\] + +\noindent +Using the mathematical notation, the definition of $\textit{der}$ is +given by the rules: + +\begin{center} +\begin{tabular}{llcl} +(1) & $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\ +(2) & $\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\ +(3) & $\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\ +(4) & $\textit{der}\;c\;(\sum\;[r_1,..,r_n])$ & $\dn$ & $\sum\;[\textit{der}\;c\;r_1,..,\textit{der}\;c\;r_n]$\\ +(5) & $\textit{der}\;c\;(\prod\;[])$ & $\dn$ & $\ZERO$\\ +(6) & $\textit{der}\;c\;(\prod\;r\!::\!rs)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r)$\\ + & & & $\textit{then}\;(\prod\;(\textit{der}\;c\;r)\!::\!rs) + (\textit{der}\;c\;(\prod rs))$\\ + & & & $\textit{else}\;(\prod\;(\textit{der}\;c\;r)\!::\! rs)$\\ +(7) & $\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\ +\end{tabular} +\end{center} + +\noindent +Let's finally do the calculation for the derivative of the regular +expression with respect to the letter $a$ (in red is in each line which +regular expression is ana-lysed): +\begin{center} +\begin{tabular}{cll} + & $\textit{der}(a, \textcolor{red}{(a + 1) \cdot a})$ & by (6) and since $a + 1$ is nullable\\ +$\dn$ & $(\textit{der}(a, \textcolor{red}{a + 1})\cdot a) + \textit{der}(a, \,\prod\,[a])$ & by (4)\\ +$\dn$ & $((\textit{der}(a, \textcolor{red}{a}) + \texttt{der}(a, \ONE))\cdot a) + \textit{der}(a, \,\prod\,[a])$& by (3)\\ +$\dn$ & $((\ONE + \texttt{der}(a, \textcolor{red}{1}))\cdot a) + \textit{der}(a, \,\prod\,[a])$ & by (2)\\ +$\dn$ & $((\ONE + \ZERO)\cdot a) + \textit{der}(a, \textcolor{red}{\prod\,[a]})$ & by (6) and $a$ not being nullable\\ +$\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\texttt{der}(a, \textcolor{red}{a})]$ & by (3)\\ +$\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\ONE]$ \\ +\end{tabular} +\end{center} + +\noindent +Translating this result back into Scala code gives you + +\[ +\texttt{ALT(\,} \underbrace{\texttt{(ONE | ZERO)} \sim \texttt{CHAR('a')}}_{(\textbf{1} + \textbf{0})\,\cdot\, a}\;,\;\underbrace{\texttt{SEQs(List(ONE))}}_{\prod\,[\textbf{1}]}\texttt{)} +\] + + \end{document} diff -r 769bda18a43d -r 1a51207780e6 handouts/pep-ho.pdf Binary file handouts/pep-ho.pdf has changed diff -r 769bda18a43d -r 1a51207780e6 handouts/pep-ho.tex --- a/handouts/pep-ho.tex Mon Dec 25 01:10:55 2023 +0100 +++ b/handouts/pep-ho.tex Fri Feb 23 11:31:36 2024 +0000 @@ -124,7 +124,7 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019, 2020, 2021, 2022, 2023} +\fnote{\copyright{} Christian Urban, King's College London, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024} %\begin{tcolorbox}[breakable,size=fbox,boxrule=1pt,pad at break*=1mm,colback=cellbackground,colframe=cellborder] % abd @@ -152,7 +152,8 @@ the myriads of Java libraries. Unlike Java, however, Scala often allows programmers to write very concise and elegant code. Some therefore say ``Scala is the better Java''.\footnote{from -\url{https://www.slideshare.net/maximnovak/joy-of-scala}} + \url{https://www.slideshare.net/maximnovak/joy-of-scala}, though this might +be outdated as latest versions of Java are catching up somewhat} A number of companies---the Guardian, Dualingo, Coursera, FourSquare, Netflix, LinkedIn, ITV to name a few---either use Scala exclusively in @@ -1937,10 +1938,12 @@ \subsection*{Conclusion} -I hope you liked the short journey through the Scala language---but remember we -like you to take on board the functional programming point of view, -rather than just learning another language. There is an interesting -blog article about Scala by a convert: +I hope you liked the short journey through the Scala language---but +remember we like you to take on board the functional programming point +of view, rather than just learning another language: Immutable +functions are easier to trust, because they the same output on the +same input. For the same reason they are easier to test and debug. +There is an interesting blog article about Scala by a convert: \begin{center} \url{https://www.skedulo.com/tech-blog/technology-scala-programming/} diff -r 769bda18a43d -r 1a51207780e6 main_testing5/bfc.scala --- a/main_testing5/bfc.scala Mon Dec 25 01:10:55 2023 +0100 +++ b/main_testing5/bfc.scala Fri Feb 23 11:31:36 2024 +0000 @@ -1,5 +1,6 @@ -// Part 2 about a "Compiler" for the Brainf*** language -//====================================================== +// Main Part 5 about a "Compiler" for the Brainf*** language +//============================================================ + object M5b { @@ -10,6 +11,15 @@ // templates below. +// DEBUGGING INFORMATION FOR COMPILERS!!! +// +// Compiler, even real ones, are fiendishly difficult to get +// to produce correct code. One way to debug them is to run +// example programs ``unoptimised''; and then optimised. Does +// the optimised version still produce the same result? + + +// for timing purposes def time_needed[T](n: Int, code: => T) = { val start = System.nanoTime() for (i <- 0 until n) code @@ -17,296 +27,149 @@ (end - start)/(n * 1.0e9) } + type Mem = Map[Int, Int] - -import io.Source +import scala.io.Source import scala.util._ -def load_bff(name: String) : String = - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") - -def sread(mem: Mem, mp: Int) : Int = - mem.getOrElse(mp, 0) - -def write(mem: Mem, mp: Int, v: Int) : Mem = - mem.updated(mp, v) - -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) - } -} +// ADD YOUR CODE BELOW +//====================== -def jumpLeft(prog: String, pc: Int, level: Int) : Int = { - if (pc < 0) pc - else (prog(pc), level) match { - case ('[', 0) => pc + 1 - case ('[', l) => jumpLeft(prog, pc - 1, l - 1) - case (']', l) => jumpLeft(prog, pc - 1, l + 1) - case (_, l) => jumpLeft(prog, pc - 1, l) - } -} +def sread(mem: Mem, mp: Int) : Int = mem.getOrElse(mp, 0) -def compute(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 '[' => 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) - } - compute(prog, new_pc, new_mp, new_mem) - } - else mem -} - -def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) - +def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) -// The baseline to what we can compare our "compiler" -// implemented below. It should require something like -// 60 seconds for the calculation on my laptop -// -//time_needed(1, run(load_bff("benchmark.bf"))) - - - -// DEBUGGING INFORMATION!!! -// -// Compiler, even real ones, are fiedishly difficult to get -// to prduce correct code. The point is that for example for -// the sierpinski program, they need to still generate code -// that displays such a triangle. If yes, then one usually -// can take comfort that all is well. If not, then something -// went wrong during the optimisations. - - - -// (5) Write a function jtable that precomputes the "jump -// table" for a bf-program. This function takes a bf-program -// as an argument and Returns a Map[Int, Int]. The -// purpose of this map is to record the information -// that given on the position pc is a '[' or a ']', -// then to which pc-position do we need to jump next? -// -// For example for the program -// -// "+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]" -// -// we obtain the map -// -// Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) -// -// This states that for the '[' on position 5, we need to -// jump to position 20, which is just after the corresponding ']'. -// Similarly, for the ']' on position 19, we need to jump to -// position 6, which is just after the '[' on position 5, and so -// on. The idea is to not calculate this information each time -// we hit a bracket, but just look up this information in the -// jtable. You can use the jumpLeft and jumpRight functions -// from Part 1 for calculating the jtable. -// -// Then adapt the compute and run functions from Part 1 in order -// to take advantage of the information stored in the jtable. -// This means whenever jumpLeft and jumpRight was called previously, -// you should look up the jump address in the jtable. - - -def jtable(pg: String) : Map[Int, Int] = - (0 until pg.length).collect { pc => pg(pc) match { - case '[' => (pc -> jumpRight(pg, pc + 1, 0)) - case ']' => (pc -> jumpLeft(pg, pc - 1, 0)) - }}.toMap - +// (6) +def empty_stack(len : Int, st : List[Int]) : Map[Int, Int] = st match { + case Nil => Map() + case n :: tail => empty_stack(len, tail) + (n -> len) +} +def jtable_helper(pg : List[Char], st : List[Int] = List(), index : Int = 0) : Map[Int, Int] = pg match { + case Nil => empty_stack(pg.length, st) + case '[' :: tail => jtable_helper(tail, index :: st, index + 1) + case ']' :: tail => st match { + case Nil => jtable_helper(tail, st, index + 1) + (index -> -1) + case n :: stail => jtable_helper(tail, stail, index + 1) + (n -> (index + 1)) + (index -> (n + 1)) + } + case _ :: tail => jtable_helper(tail, st, index + 1) +} +def jtable(pg: String) : Map[Int, Int] = jtable_helper(pg.toList) // testcase +// // jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") // => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) -def compute2(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { - if (0 <= pc && pc < pg.length) { - val (new_pc, new_mp, new_mem) = pg(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 '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute2(pg, tb, new_pc, new_mp, new_mem) - } - else mem +def compute2(prog: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = + if (pc < 0 || pc >= prog.length) mem else prog.charAt(pc) match { + case '>' => compute2(prog, tb, pc+1, mp+1, mem) + case '<' => compute2(prog, tb, pc+1, mp-1, mem) + case '+' => compute2(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) + 1))) + case '-' => compute2(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) - 1))) + case '.' => print(sread(mem, mp).toChar); compute2(prog, tb, pc+1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute2(prog, tb, tb.getOrElse(pc, -2), mp, mem) + else compute2(prog, tb, pc+1, mp, mem) + case ']' => if (sread(mem, mp) == 0) compute2(prog, tb, pc+1, mp, mem) + else compute2(prog, tb, tb.getOrElse(pc, -2), mp, mem) + case _ => compute2(prog, tb, pc+1, mp, mem) } - -def run2(pg: String, m: Mem = Map()) = - compute2(pg, jtable(pg), 0, 0, m) - -//time_needed(1, run2(load_bff("benchmark.bf"))) - - - -// (6) Write a function optimise which deletes "dead code" (everything -// that is not a bf-command) and also replaces substrings of the form -// [-] by a new command 0. The idea is that the loop [-] just resets the -// memory at the current location to 0. In the compute3 and run3 functions -// below you implement this command by writing the number 0 to mem(mp), -// that is write(mem, mp, 0). -// -// The easiest way to modify a string in this way is to use the regular -// expression """[^<>+-.\[\]""", which recognises everything that is -// not a bf-command and replace it by the empty string. Similarly the -// regular expression """\[-\]""" finds all occurences of [-] and -// by using the Scala method .replaceAll you can repplace it with the -// string "0" standing for the new bf-command. - -def optimise(s: String) : String = { - s.replaceAll("""[^<>+-.\[\]]""","") - .replaceAll("""\[-\]""", "0") -} - - -def compute3(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { - if (0 <= pc && pc < pg.length) { - val (new_pc, new_mp, new_mem) = pg(pc) match { - case '0' => (pc + 1, mp, write(mem, mp, 0)) - 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 '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute3(pg, tb, new_pc, new_mp, new_mem) - } - else mem -} - -def run3(pg: String, m: Mem = Map()) = { - val pg_opt = optimise(pg) - compute3(pg_opt, jtable(pg_opt), 0, 0, m) -} - +def run2(prog: String, m: Mem = Map()) = compute2(prog, jtable(prog), 0, 0, m) // testcases - -//println(optimise(load_bff("collatz.bf"))) -//optimise(load_bff("benchmark.bf")) // should have inserted 0's -//optimise(load_bff("mandelbrot.bf")).length // => 11203 - -//time_needed(1, run3(load_bff("benchmark.bf"))) +// time_needed(1, run2(load_bff("benchmark.bf"))) +// time_needed(1, run2(load_bff("sierpinski.bf"))) -// (7) Write a function combine which replaces sequences -// of repated increment and decrement commands by appropriate -// two-character commands. For example for sequences of + -// -// orig bf-cmds | replacement -// ------------------------------ -// + | +A -// ++ | +B -// +++ | +C -// | -// ... | -// | -// +++....+++ | +Z -// (where length = 26) -// -// Similar for the bf-command -, > and <. All other commands should -// be unaffected by this change. -// -// Adapt the compute4 and run4 functions such that they can deal -// appropriately with such two-character commands. +// (7) + +def optimise(s: String) : String = + s.filter(List('>', '<', '+', '-', '[', ']', '.').contains(_)).replaceAllLiterally("[-]", "0") -def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { - case (Nil, acc) => acc - case ('[' :: cs, acc) => splice(cs, ('[', 1) :: acc) - case (']' :: cs, acc) => splice(cs, (']', 1) :: acc) - case ('.' :: cs, acc) => splice(cs, ('.', 1) :: acc) - case ('0' :: cs, acc) => splice(cs, ('0', 1) :: acc) - case (c :: cs, Nil) => splice(cs, List((c, 1))) - case (c :: cs, (d, n) :: acc) => - if (c == d && n < 26) splice(cs, (c, n + 1) :: acc) - else splice(cs, (c, 1) :: (d, n) :: acc) +def compute3(prog: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = + if (pc < 0 || pc >= prog.length) mem else prog.charAt(pc) match { + case '>' => compute3(prog, tb, pc+1, mp+1, mem) + case '<' => compute3(prog, tb, pc+1, mp-1, mem) + case '+' => compute3(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) + 1))) + case '-' => compute3(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) - 1))) + case '.' => print(sread(mem, mp).toChar); compute3(prog, tb, pc+1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute3(prog, tb, tb.getOrElse(pc, -2), mp, mem) + else compute3(prog, tb, pc+1, mp, mem) + case ']' => if (sread(mem, mp) == 0) compute3(prog, tb, pc+1, mp, mem) + else compute3(prog, tb, tb.getOrElse(pc, -2), mp, mem) + case '0' => compute3(prog, tb, pc+1, mp, mem + (mp -> 0)) + case _ => compute3(prog, tb, pc+1, mp, mem) } -def spl(s: String) = splice(s.toList, Nil).reverse - -//spl(load_bff("benchmark.bf")) - -def combine(s: String) : String = { - (for ((c, n) <- spl(s)) yield c match { - case '>' => List('>', (n + '@').toChar) - case '<' => List('<', (n + '@').toChar) - case '+' => List('+', (n + '@').toChar) - case '-' => List('-', (n + '@').toChar) - case _ => List(c) - }).flatten.mkString -} +def run3(prog: String, m: Mem = Map()) = + val optimized = optimise(prog) + compute3(optimized, jtable(optimized), 0, 0, m) -//combine(load_bff("benchmark.bf")) +// testcases +// +// optimise(load_bff("benchmark.bf")) // should have inserted 0's +// optimise(load_bff("mandelbrot.bf")).length // => 11205 // this is wrong, it's 11203! +// +// time_needed(1, run3(load_bff("benchmark.bf"))) -def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { - if (0 <= pc && pc < pg.length) { - val (new_pc, new_mp, new_mem) = pg(pc) match { - case '0' => (pc + 1, mp, write(mem, mp, 0)) - case '>' => (pc + 2, mp + (pg(pc + 1) - '@'), mem) - case '<' => (pc + 2, mp - (pg(pc + 1) - '@'), mem) - case '+' => (pc + 2, mp, write(mem, mp, sread(mem, mp) + (pg(pc + 1) - '@'))) - case '-' => (pc + 2, mp, write(mem, mp, sread(mem, mp) - (pg(pc + 1) - '@'))) - case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } - case '[' => if (sread(mem, mp) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (sread(mem, mp) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute4(pg, tb, new_pc, new_mp, new_mem) - } - else mem +// (8) +def combine_helper(c : String, s : String) : String = + val temp1 = s.replaceAllLiterally(c*26, c ++ "Z").replaceAllLiterally(c*25, c ++ "Y").replaceAllLiterally(c*24, c ++ "X").replaceAllLiterally(c*23, c ++ "W") + val temp2 = temp1.replaceAllLiterally(c*22, c ++ "V").replaceAllLiterally(c*21, c ++ "U").replaceAllLiterally(c*20, c ++ "T").replaceAllLiterally(c*19, c ++ "S") + val temp3 = temp2.replaceAllLiterally(c*18, c ++ "R").replaceAllLiterally(c*17, c ++ "Q").replaceAllLiterally(c*16, c ++ "P").replaceAllLiterally(c*15, c ++ "O") + val temp4 = temp3.replaceAllLiterally(c*14, c ++ "N").replaceAllLiterally(c*13, c ++ "M").replaceAllLiterally(c*12, c ++ "L").replaceAllLiterally(c*11, c ++ "K") + val temp5 = temp4.replaceAllLiterally(c*10, c ++ "J").replaceAllLiterally(c*9, c ++ "I").replaceAllLiterally(c*8, c ++ "H").replaceAllLiterally(c*7, c ++ "G") + val temp6 = temp5.replaceAllLiterally(c*6, c ++ "F").replaceAllLiterally(c*5, c ++ "E").replaceAllLiterally(c*4, c ++ "D").replaceAllLiterally(c*3, c ++ "C") + val temp7 = temp6.replaceAllLiterally(c*2, c ++ "B").replaceAllLiterally(c ++ ">", c ++ "A>").replaceAllLiterally(c ++ "<", c ++ "A<") + val temp8 = temp7.replaceAllLiterally(c ++ "+", c ++ "A+").replaceAllLiterally(c ++ "-", c ++ "A-").replaceAllLiterally(c ++ "[", c ++ "A[") + temp8.replaceAllLiterally(c ++ "]", c ++ "A]").replaceAllLiterally(c ++ ".", c ++ "A.").replaceAllLiterally(c ++ "0", c ++ "A0") +def combine(s: String) : String = + val temp1 = combine_helper(">", s) + val temp2 = combine_helper("<", temp1) + val temp3 = combine_helper("+", temp2) + val temp4 = combine_helper("-", temp3) + temp4 + +// testcase +// combine(load_bff("benchmark.bf")) + +def compute4(prog: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = if (pc < 0 || pc >= prog.length) mem else prog.charAt(pc) match { + case '>' => val n = (prog.charAt(pc+1).toInt - 64) + compute4(prog, tb, pc+1, mp+n, mem) + case '<' => val n = (prog.charAt(pc+1).toInt - 64) + compute4(prog, tb, pc+1, mp-n, mem) + case '+' => val n = (prog.charAt(pc+1).toInt - 64) + compute4(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) + n))) + case '-' => val n = (prog.charAt(pc+1).toInt - 64) + compute4(prog, tb, pc+1, mp, mem + (mp -> (sread(mem, mp) - n))) + case '.' => print(sread(mem, mp).toChar); compute4(prog, tb, pc+1, mp, mem) + case '[' => if (sread(mem, mp) == 0) compute4(prog, tb, tb.getOrElse(pc, -2), mp, mem) + else compute4(prog, tb, pc+1, mp, mem) + case ']' => if (sread(mem, mp) == 0) compute4(prog, tb, pc+1, mp, mem) + else compute4(prog, tb, tb.getOrElse(pc, -2), mp, mem) + case '0' => compute4(prog, tb, pc+1, mp, mem + (mp -> 0)) + case _ => compute4(prog, tb, pc+1, mp, mem) } -def run4(pg: String, m: Mem = Map()) = { - val pg_opt = combine(optimise(pg)) - compute4(pg_opt, jtable(pg_opt), 0, 0, m) -} - -// testcases -//println(combine(optimise(load_bff("mandelbrot.bf").drop(123)))) - -//combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[A-A] """>A+B[A-A]