# HG changeset patch # User Christian Urban # Date 1698968093 0 # Node ID 59e005dcf1635f59b98e607ceee225fe976a650a # Parent b528d1d3d3c3f85b06ab4011c17a5210894cc483 updated diff -r b528d1d3d3c3 -r 59e005dcf163 cws/core_cw03.pdf Binary file cws/core_cw03.pdf has changed diff -r b528d1d3d3c3 -r 59e005dcf163 cws/core_cw03.tex --- a/cws/core_cw03.tex Thu Nov 02 13:53:37 2023 +0000 +++ b/cws/core_cw03.tex Thu Nov 02 23:34:53 2023 +0000 @@ -64,11 +64,11 @@ \subsection*{Core Part (3 Marks, files postfix.scala, postfix2.scala)} -The \emph{Shunting Yard Algorithm} has been developed by Edsger Dijkstra, +The \textit{Shunting Yard Algorithm} has been developed by Edsger Dijkstra, an influential computer scientist who developed many well-known algorithms. This algorithm transforms the usual infix notation of arithmetic expressions into the postfix notation, sometimes also -called reverse Polish notation. +called \textit{Reverse Polish Notation}. Why on Earth do people use the postfix notation? It is much more convenient to work with the usual infix notation for arithmetic @@ -92,9 +92,9 @@ \end{lstlisting} \noindent -where the command \texttt{ldc} loads a constant onto the stack, and \texttt{imul}, -\texttt{isub} and \texttt{iadd} are commands acting on the stack. Clearly this -is the arithmetic expression in postfix notation.\bigskip +where the command \texttt{ldc} loads a number onto the stack, and \texttt{imul}, +\texttt{isub} and \texttt{iadd} perform arithmetic operations on the stack. Clearly, this +is the arithmetic expression from above but in postfix notation.\bigskip \noindent The shunting yard algorithm processes an input token list using an @@ -123,7 +123,13 @@ processing the input list. \item If the input is empty, then you move all remaining operators from the stack to the output list. -\end{itemize} +\end{itemize} + +\noindent +BTW, the rules above are written ``If\ldots'', but this is because English does not +include very sophisticated pattern matching. But clearly the rules above should be implemented +in Scala using pattern matching. + \subsubsection*{Tasks (file postfix.scala)} diff -r b528d1d3d3c3 -r 59e005dcf163 cws/main_cw02.pdf Binary file cws/main_cw02.pdf has changed diff -r b528d1d3d3c3 -r 59e005dcf163 cws/main_cw02.tex --- a/cws/main_cw02.tex Thu Nov 02 13:53:37 2023 +0000 +++ b/cws/main_cw02.tex Thu Nov 02 23:34:53 2023 +0000 @@ -40,10 +40,10 @@ and apply an automated marking script to them.\medskip \noindent -In addition, the Scala part comes with reference -implementations in form of \texttt{jar}-files. This allows you to run -any test cases on your own computer. For example you can call Scala on -the command line with the option \texttt{-cp wordle.jar} and then +In addition, the Scala part comes with a reference +implementation in form of \texttt{jar}-files. This allows you to run +any test cases on your own computer. For example you can call \texttt{scala-cli} on +the command line with the option \texttt{--extra-jars wordle.jar} and then query any function from the template file. Say you want to find out what the function \texttt{} produces: for this you just need to prefix it with the object name \texttt{M2}. If you want to find out what @@ -51,7 +51,7 @@ you would type something like: \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] -$ scala -cp wordle.jar +$ scala-cli --extra-jars wordle.jar scala> val secretsURL = | """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" @@ -115,10 +115,8 @@ The result should be a list of strings (the lines in the file). In case the url does not produce a file, return the empty list. - \textcolor{red}{ - In what follows we will use \texttt{secrets} to refer to the list of words listed - in \texttt{wordle.txt}. - } + In what follows we will use \texttt{secrets} to refer to the list of words listed + in \texttt{wordle.txt}.\\ \mbox{}\hfill [0.5 Marks] \item[(2)] Implement a polymorphic function \pcode{removeN}, which removes $n$ occurrences of an @@ -218,29 +216,8 @@ where \pcode{secrets} is the list generated under Task 1. In all cases above the iscore of the resulting secrets is 0, but this does not need to be the case -in general. - -\color{red} - Note that the template gives as type for \texttt{evil}: - - \begin{center} - \texttt{def evil(secrets: List[String], word: String) = ???} - \end{center} - - where the return type is left unspecified. This return type is not needed when - functions are not recursive---\texttt{evil} is meant to be just a wrapper that - calls \texttt{lowest} with appropriate default arguments and returns whatever - \texttt{lowest} returns. Therefore a return type is not needed. But a slightly - more accurate template definition for \texttt{evil} is:\medskip\medskip - - \begin{minipage}{1.05\textwidth} - \begin{center} - \texttt{def evil(secrets: List[String], word: String) : List[String] = ???} - \end{center} - \end{minipage}\medskip\medskip - - where also the return type is explicitly given.\\\color{black} - \mbox{}\hfill [1.5 Marks] +in general.\\ +\mbox{}\hfill [1.5 Marks] \item[(6)] The secrets generated in Task 5 are the ones with the lowest score with respect to the word. You can think of these as the secrets that are furthest ``away'' from the @@ -267,8 +244,8 @@ generated set and then filter out the strings that are ranked highest (the ones with the most obscure letters). This list of strings often contains only a single word, but in general there might be more (see below). First implement a function \pcode{rank} that takes a frequency map (from 6) and a string as arguments. - \textcolor{red}{In the testcases, the frequency map is generated for all words in \texttt{secrets}, that is the - whole list in \texttt{wordle.txt}.} The function + In the testcases, the frequency map is generated for all words in \texttt{secrets}, that is the + whole list in \texttt{wordle.txt}. The function generates a rank by summing up all frequencies of the letters in the string. For example \begin{lstlisting}[numbers=none] @@ -277,13 +254,6 @@ rank(frequencies(secrets), "fuzzy") => 4.898735738513722 \end{lstlisting} - \color{red} - The return type for \texttt{rank} is \texttt{Double}: - - \begin{center} - \texttt{def rank(frqs: Map[Char, Double], s: String) : Double = ???} - \end{center} - \color{black} Finally, implement a function \pcode{ranked_evil} that selects from the output of \pcode{evil} the string(s) which are highest ranked in evilness. @@ -299,14 +269,6 @@ This means if the user types in "abbey" then the most evil word to choose as secret is ``whizz'' (according to our calculations). This word has a zero \pcode{iscore} and the most obscure letters. -\color{red} - The return type for \texttt{ranked\_evil} is \texttt{List[String]}: - - \begin{center} - \texttt{def ranked\_evil(secrets: List[String], word: String) : List[String] = ???} - \end{center} - \color{black} - % %\color{red} %\section*{Correction with \texttt{ranked\_evil}} diff -r b528d1d3d3c3 -r 59e005dcf163 cws/main_cw03.pdf Binary file cws/main_cw03.pdf has changed diff -r b528d1d3d3c3 -r 59e005dcf163 cws/main_cw03.tex --- a/cws/main_cw03.tex Thu Nov 02 13:53:37 2023 +0000 +++ b/cws/main_cw03.tex Thu Nov 02 23:34:53 2023 +0000 @@ -144,10 +144,10 @@ This Scala assignment comes with a reference implementation in form of a \texttt{jar}-file. This allows you to run any test cases on your own -computer. For example you can call Scala on the command line with the -option \texttt{-cp re.jar} and then query any function from the -\texttt{re.scala} template file. As usual you have to prefix the calls -with \texttt{M3} or import this object. Since some tasks +computer. For example you can call \texttt{scala-cli} on the command +line with the option \texttt{--extra-jars re.jar} and then query any function +from the \texttt{re.scala} template file. As usual you have to prefix +the calls with \texttt{M3} or import this object. Since some tasks are time sensitive, you can check the reference implementation as follows: if you want to know, for example, how long it takes to match strings of $a$'s using the regular expression $(a^*)^*\cdot b$ you can @@ -155,7 +155,7 @@ \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] -$ scala -cp re.jar +$ scala-cli --extra-jars re.jar scala> import M3._ scala> for (i <- 0 to 5000000 by 500000) { | println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.") @@ -343,7 +343,7 @@ $acc$. In the fourth case we spill out the $rs$ by appending the $rs$ to the end of the accumulator. Similarly in the last case we append the single regular expression $r$ to the end of the - accumulator. I let you think why the ``end'' is needed. \mbox{}\hfill\mbox{[1 Mark]} + accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]} \item[(5)] Before we can simplify regular expressions, we need what is often called \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors @@ -516,7 +516,7 @@ you have implemented. How long can a string of $a$'s be in your matcher and still stay within the 30 seconds time limit? It should be mu(uu)$^*$ch better than your off-the-shelf matcher in your -bog-standard language. +bog-standard programming language. \begin{center} \begin{tabular}{@{}cc@{}} diff -r b528d1d3d3c3 -r 59e005dcf163 main_solution3/re.scala --- a/main_solution3/re.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_solution3/re.scala Thu Nov 02 23:34:53 2023 +0000 @@ -3,7 +3,6 @@ object M3 { -// Regular Expressions abstract class Rexp case object ZERO extends Rexp case object ONE extends Rexp @@ -18,30 +17,38 @@ def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2)) -// some convenience for typing in regular expressions -import scala.language.implicitConversions -import scala.language.reflectiveCalls + +// some convenience for typing regular expressions 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) + +import scala.language.implicitConversions -implicit def RexpOps (r: Rexp) = new { +given Conversion[String, Rexp] = (s => charlist2rexp(s.toList)) + +extension (r: Rexp) { 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) -} +// some examples for the conversion and extension: + +// val areg : Rexp = "a" | "b" +// => ALTs(List(CHAR('a'), CHAR('b'))) +// +// val sreg : Rexp = "a" ~ "b" +// => SEQs(List(CHAR('a'), CHAR('b'))) +// +// val star_reg : Rexp = ("a" ~ "b").% +// => STAR(SEQs(List(CHAR('a'), CHAR('b')))) + +// ADD YOUR CODE BELOW +//====================== // (1) def nullable (r: Rexp) : Boolean = r match { @@ -194,8 +201,9 @@ -/* -// if nullable(r1) - ALTs(SEQs(der(c, r1)::rs)::(rs filter what is nullable) .map(der(c,_))) -*/ +// This template code is subject to copyright +// by King's College London, 2022. Do not +// make the template code public in any shape +// or form, and do not exchange it with other +// students under any circumstance. diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle.scala --- a/main_testing2/wordle.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle.scala Thu Nov 02 23:34:53 2023 +0000 @@ -9,45 +9,25 @@ // ADD YOUR CODE BELOW //====================== -// def main(args: Array[String]): Unit = { -// val secrets = get_wordle_list("https://nms.kcl.ac.uk/christian.urban/wordle.txt") -// println(ranked_evil(secrets, "beats")== List("fuzzy")) -// println(ranked_evil(secrets, "vitae") == List("fuzzy")) -// println(ranked_evil(secrets, "bento") == List("fuzzy")) -// println(ranked_evil(secrets, "belts") == List("fuzzy")) -// println(ranked_evil(secrets, "abbey") == List("whizz")) -// println(ranked_evil(secrets, "afear") == List("buzzy")) -// println(ranked_evil(secrets, "zincy") == List("jugum")) -// println(ranked_evil(secrets, "zippy") == List("chuff")) - - -// } //(1) def get_wordle_list(url: String) : List[String] = { - try { - Source.fromURL(url).getLines.toList; - } - catch { - case _ : Throwable => List(); - } + Try(Source.fromURL(url).getLines.toList).getOrElse(List()) } + // val secrets = get_wordle_list("https://nms.kcl.ac.uk/christian.urban/wordle.txt") // secrets.length // => 12972 // secrets.filter(_.length != 5) // => Nil -//(2) -def removeN[A](xs: List[A], elem: A, n: Int) : List[A] = { - if (xs.isEmpty || n == 0 || !xs.contains(elem)){ - xs - } - else{ - val (newLst,newLst2) = xs.splitAt(xs.indexOf(elem)) - removeN(newLst ++ newLst2.tail,elem, n-1) - } +//(2) +def removeN[A](xs: List[A], elem: A, n: Int) : List[A] = xs match { + case Nil => Nil + case x :: tail if x == elem && n > 0 => removeN(tail, elem, n - 1) + case x :: tail => x :: removeN(tail, elem, n) } + // removeN(List(1,2,3,2,1), 3, 1) // => List(1, 2, 2, 1) // removeN(List(1,2,3,2,1), 2, 1) // => List(1, 3, 2, 1) // removeN(List(1,2,3,2,1), 1, 1) // => List(2, 3, 2, 1) @@ -61,42 +41,19 @@ def pool(secret: String, word: String) : List[Char] = { - //print(secret.toList, word.toList) - val lst= ((0 to 4).map(x => { - if(!secret(x).equals(word(x))) Some(secret(x)) else None - - }).toList) - lst.flatten + (for(index <- (0 to word.length-1); if (word(index) != secret(index))) yield secret(index).toChar).toList } - - +// t def aux(secret: List[Char], word: List[Char], pool: List[Char]) : List[Tip] = { - - if (secret.length == 1){ - if (secret.head == word.head){ - List(Correct) - } - else if (pool.contains(word.head)){ - List(Present) - } - else { - List(Absent) - } - } - else if (secret.head == word.head){ - List(Correct) ++ aux(secret.tail, word.tail, pool) - } - else if (pool.contains(word.head)){ - List(Present) ++ aux(secret.tail, word.tail, removeN(pool, word.head, 1)) - } + if (secret.isEmpty) List() else { - List(Absent) ++ aux(secret.tail, word.tail, pool) + if (secret.head == word.head) Correct :: aux(secret.tail, word.tail, pool) + else if (pool.contains(word.head)) Present :: aux(secret.tail, word.tail, pool.filterNot(_ == word.head)) + else Absent :: aux(secret.tail, word.tail, pool) } } -def score(secret: String, word: String) : List[Tip] = { - aux(secret.toList,word.toList,pool(secret,word)) -} +def score(secret: String, word: String) : List[Tip] = aux(secret.toList, word.toList, pool(secret, word)) // score("chess", "caves") // => List(Correct, Absent, Absent, Present, Correct) @@ -105,38 +62,31 @@ // score("chess", "eexss") // => List(Present, Absent, Absent, Correct, Correct) // (4) -def eval(t: Tip) : Int = { - if (t == Correct) 10 - else if (t == Present) 1 - else 0 +def eval(t: Tip) : Int = t match { + case Correct => 10 + case Present => 1 + case Absent => 0 } -def iscore(secret: String, word: String) : Int = { - val scoreList = score(secret,word) - scoreList.map(x =>(eval(x))).toList.sum -} +def iscore(secret: String, word: String) : Int = (for(current <- score(secret, word)) yield eval(current)).sum + //iscore("chess", "caves") // => 21 //iscore("chess", "swiss") // => 20 -// (5) +// (5) t def lowest(secrets: List[String], word: String, current: Int, acc: List[String]) : List[String] = { - if(secrets.isEmpty) acc - else if (iscore(secrets.head,word) (x._1, (1-(x._2.size.toDouble/ totalChar)))) - + val occurrences = secrets.mkString.groupBy(identity).mapValues(_.length) + val all_letters = secrets.mkString.length.toDouble + occurrences.map{ case (c, n) => c -> (1 - n/all_letters) }.toMap } -// (7) -def rank(frqs: Map[Char, Double], s: String) = { - s.map(x => (frqs(x))).toList.sum -} - -def ranked_evil(secrets: List[String], word: String) : List[String]= { - val evilWords = evil(secrets,word) - val returnVal = evilWords.map(x => (x, rank(frequencies(secrets),x))).toMap.maxBy(_._2)._1 - List(returnVal) -} +// (7) +def rank(frqs: Map[Char, Double], s: String) : Double = s.map(c => frqs(c)).sum +def ranked_evil(secrets: List[String], word: String): List[String] = { + val frqs = frequencies(secrets) + val ranked_secrets = evil(secrets, word).map(s => (s, rank(frqs, s))) + List((ranked_secrets.sortWith(_._2 > _._2)).map(_._1).head ) +} + } diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test.sh --- a/main_testing2/wordle_test.sh Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test.sh Thu Nov 02 23:34:53 2023 +0000 @@ -16,15 +16,15 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out) } # functional tests function scala_assert { - (ulimit -t 35; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null) } - + # purity test function scala_vars { (sed 's/immutable/ok/g' c$out > cb$out; @@ -42,6 +42,7 @@ tsts0=$(( 0 )) else echo -e " --> SCALA DID NOT RUN wordle.scala\n" >> $out + echo -e " --> try running scala-cli compile wordle.scala on your own computer\n" >> $out tsts0=$(( 1 )) fi diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test1.scala --- a/main_testing2/wordle_test1.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test1.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,11 +1,12 @@ -import M2._ - -val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" -val urban_secrets = get_wordle_list(urban_wordle_url) +def urbanmain() = { + import M2._ -assert(urban_secrets.length == 12972) -assert(urban_secrets.filter(_.length != 5) == Nil) + val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" + val urban_secrets = get_wordle_list(urban_wordle_url) -assert(get_wordle_list(urban_wordle_url ++ "2") == Nil) + assert(urban_secrets.length == 12972) + assert(urban_secrets.filter(_.length != 5) == Nil) + assert(get_wordle_list(urban_wordle_url ++ "2") == Nil) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test2.scala --- a/main_testing2/wordle_test2.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test2.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,17 +1,18 @@ -import M2._ +def urbanmain() = { + import M2._ -assert(removeN(List(1,2,3,2,1), 3, 1) == List(1, 2, 2, 1)) -assert(removeN(List(1,2,3,2,1), 2, 1) == List(1, 3, 2, 1)) -assert(removeN(List(1,2,3,2,1), 1, 1) == List(2, 3, 2, 1)) -assert(removeN(List(1,2,3,2,1), 0, 2) == List(1, 2, 3, 2, 1)) -assert(removeN(List("a", "b", "b"), "b", 1) == List("a", "b")) -assert(removeN(List("b", "a", "b", "b"), "b", 2) == List("a", "b")) -assert(removeN(List("b", "a", "b"), "a", 2) == List("b", "b")) + assert(removeN(List(1,2,3,2,1), 3, 1) == List(1, 2, 2, 1)) + assert(removeN(List(1,2,3,2,1), 2, 1) == List(1, 3, 2, 1)) + assert(removeN(List(1,2,3,2,1), 1, 1) == List(2, 3, 2, 1)) + assert(removeN(List(1,2,3,2,1), 0, 2) == List(1, 2, 3, 2, 1)) + assert(removeN(List("a", "b", "b"), "b", 1) == List("a", "b")) + assert(removeN(List("b", "a", "b", "b"), "b", 2) == List("a", "b")) + assert(removeN(List("b", "a", "b"), "a", 2) == List("b", "b")) -//assert(removeOne(List(1,2,3,2,1), 3) == List(1, 2, 2, 1)) -//assert(removeOne(List(1,2,3,2,1), 2) == List(1, 3, 2, 1)) -//assert(removeOne(List(1,2,3,2,1), 1) == List(2, 3, 2, 1)) -//assert(removeOne(List(1,2,3,2,1), 0) == List(1, 2, 3, 2, 1)) - + //assert(removeOne(List(1,2,3,2,1), 3) == List(1, 2, 2, 1)) + //assert(removeOne(List(1,2,3,2,1), 2) == List(1, 3, 2, 1)) + //assert(removeOne(List(1,2,3,2,1), 1) == List(2, 3, 2, 1)) + //assert(removeOne(List(1,2,3,2,1), 0) == List(1, 2, 3, 2, 1)) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test3a.scala --- a/main_testing2/wordle_test3a.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test3a.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,7 +1,9 @@ - -import M2._ - -assert(pool("chess", "caves").toSet == Set('h', 'e', 's')) -assert(pool("chess", "swiss").toSet == Set('c', 'h', 'e')) +def urbanmain() = { + import M2._ + + assert(pool("chess", "caves").toSet == Set('h', 'e', 's')) + assert(pool("chess", "swiss").toSet == Set('c', 'h', 'e')) +} + diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test3b.scala --- a/main_testing2/wordle_test3b.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test3b.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,12 +1,14 @@ -import M2._ +def urbanmain() = { + import M2._ -assert(score("chess", "caves") == List(Correct, Absent, Absent, Present, Correct)) -assert(score("doses", "slide") == List(Present, Absent, Absent, Present, Present)) -assert(score("chess", "swiss") == List(Absent, Absent, Absent, Correct, Correct)) -assert(score("chess", "eexss") == List(Present, Absent, Absent, Correct, Correct)) + assert(score("chess", "caves") == List(Correct, Absent, Absent, Present, Correct)) + assert(score("doses", "slide") == List(Present, Absent, Absent, Present, Present)) + assert(score("chess", "swiss") == List(Absent, Absent, Absent, Correct, Correct)) + assert(score("chess", "eexss") == List(Present, Absent, Absent, Correct, Correct)) -val urban_p = pool("chess", "caves") + val urban_p = pool("chess", "caves") -assert(aux("chess".toList, "caves".toList, Nil) == List(Correct, Absent, Absent, Absent, Correct)) -assert(aux("chess".toList, "caves".toList, urban_p) == List(Correct, Absent, Absent, Present, Correct)) + assert(aux("chess".toList, "caves".toList, Nil) == List(Correct, Absent, Absent, Absent, Correct)) + assert(aux("chess".toList, "caves".toList, urban_p) == List(Correct, Absent, Absent, Present, Correct)) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test4.scala --- a/main_testing2/wordle_test4.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test4.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,5 +1,7 @@ -import M2._ +def urbanmain() = { + import M2._ -assert(iscore("chess", "caves") == 21) -assert(iscore("chess", "swiss") == 20) + assert(iscore("chess", "caves") == 21) + assert(iscore("chess", "swiss") == 20) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test5.scala --- a/main_testing2/wordle_test5.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test5.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,20 +1,21 @@ -import M2._ -import io.Source +def urbanmain() = { + import M2._ + import io.Source -def urban_get_wordle_list(url: String) : List[String] = { - Source.fromFile(url)("ISO-8859-1").getLines().toList -} -val urban_secrets = urban_get_wordle_list("wordle.txt") + def urban_get_wordle_list(url: String) : List[String] = { + Source.fromFile(url)("ISO-8859-1").getLines().toList + } + val urban_secrets = urban_get_wordle_list("wordle.txt") -//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" -//val urban_secrets = get_wordle_list(urban_wordle_url) + //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" + //val urban_secrets = get_wordle_list(urban_wordle_url) -assert(evil(urban_secrets, "stent").length == 1907) -assert(evil(urban_secrets, "hexes").length == 2966) -assert(evil(urban_secrets, "horse").length == 1203) -assert(evil(urban_secrets, "hoise").length == 971) -assert(evil(urban_secrets, "house").length == 1228) - + assert(evil(urban_secrets, "stent").length == 1907) + assert(evil(urban_secrets, "hexes").length == 2966) + assert(evil(urban_secrets, "horse").length == 1203) + assert(evil(urban_secrets, "hoise").length == 971) + assert(evil(urban_secrets, "house").length == 1228) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test6.scala --- a/main_testing2/wordle_test6.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test6.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,18 +1,20 @@ -import M2._ -import io.Source +def urbanmain() = { + import M2._ + + import io.Source -def urban_get_wordle_list(url: String) : List[String] = { - Source.fromFile(url)("ISO-8859-1").getLines().toList -} -val urban_secrets = urban_get_wordle_list("wordle.txt") + def urban_get_wordle_list(url: String) : List[String] = { + Source.fromFile(url)("ISO-8859-1").getLines().toList + } + val urban_secrets = urban_get_wordle_list("wordle.txt") -//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" -//val urban_secrets = get_wordle_list(urban_wordle_url) + //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" + //val urban_secrets = get_wordle_list(urban_wordle_url) -assert(frequencies(urban_secrets)('y') == 0.9680234350909651) -assert(frequencies(urban_secrets)('e') == 0.897286463151403) -assert(frequencies(urban_secrets)('z') == 0.9933086648165279) - + assert(frequencies(urban_secrets)('y') == 0.9680234350909651) + assert(frequencies(urban_secrets)('e') == 0.897286463151403) + assert(frequencies(urban_secrets)('z') == 0.9933086648165279) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing2/wordle_test7.scala --- a/main_testing2/wordle_test7.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing2/wordle_test7.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,25 +1,28 @@ - -import M2._ - -import io.Source -def urban_get_wordle_list(url: String) : List[String] = { - Source.fromFile(url)("ISO-8859-1").getLines().toList -} -val urban_secrets = urban_get_wordle_list("wordle.txt") +def urbanmain() = { + import M2._ + + import io.Source + + + def urban_get_wordle_list(url: String) : List[String] = { + Source.fromFile(url)("ISO-8859-1").getLines().toList + } + val urban_secrets = urban_get_wordle_list("wordle.txt") -//val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" -//val urban_secrets = get_wordle_list(urban_wordle_url) + //val urban_wordle_url = """https://nms.kcl.ac.uk/christian.urban/wordle.txt""" + //val urban_secrets = get_wordle_list(urban_wordle_url) -assert(ranked_evil(urban_secrets, "abbey") == List("whizz")) -assert(ranked_evil(urban_secrets, "afear") == List("buzzy")) -assert(ranked_evil(urban_secrets, "zincy") == List("jugum")) -assert(ranked_evil(urban_secrets, "zippy") == List("chuff")) + assert(ranked_evil(urban_secrets, "abbey") == List("whizz")) + assert(ranked_evil(urban_secrets, "afear") == List("buzzy")) + assert(ranked_evil(urban_secrets, "zincy") == List("jugum")) + assert(ranked_evil(urban_secrets, "zippy") == List("chuff")) -assert(ranked_evil(urban_secrets, "beats") == List("fuzzy")) -assert(ranked_evil(urban_secrets, "vitae") == List("fuzzy")) -assert(ranked_evil(urban_secrets, "bento") == List("fuzzy")) -assert(ranked_evil(urban_secrets, "belts") == List("fuzzy")) + assert(ranked_evil(urban_secrets, "beats") == List("fuzzy")) + assert(ranked_evil(urban_secrets, "vitae") == List("fuzzy")) + assert(ranked_evil(urban_secrets, "bento") == List("fuzzy")) + assert(ranked_evil(urban_secrets, "belts") == List("fuzzy")) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re.scala --- a/main_testing3/re.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re.scala Thu Nov 02 23:34:53 2023 +0000 @@ -19,240 +19,159 @@ // some convenience for typing 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) + +import scala.language.implicitConversions -implicit def RexpOps (r: Rexp) = new { +given Conversion[String, Rexp] = (s => charlist2rexp(s.toList)) + +extension (r: Rexp) { 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) -} +// some examples for the conversion and extension: -// examples for the implicits: -// ALT(CHAR('a'), CHAR('b')) // val areg : Rexp = "a" | "b" - -// SEQ(CHAR('a'), CHAR('b')) +// => ALTs(List(CHAR('a'), CHAR('b'))) +// // val sreg : Rexp = "a" ~ "b" - +// => SEQs(List(CHAR('a'), CHAR('b'))) +// +// val star_reg : Rexp = ("a" ~ "b").% +// => STAR(SEQs(List(CHAR('a'), CHAR('b')))) // ADD YOUR CODE BELOW //====================== -// (1) +// (1) def nullable (r: Rexp) : Boolean = r match { - case ZERO => false - case ONE => true - case CHAR(_) => false - case ALTs(rs) => (for(reg <- rs) yield nullable(reg)).exists(_ == true) - case SEQs(rs) => (for(reg <- rs) yield nullable(reg)).forall(_ == true) - case STAR(_) => true + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALTs(rs) => rs.exists(nullable) + case SEQs(rs) => rs.forall(nullable) + case STAR(_) => true } -/* -nullable(ZERO) == false -nullable(ONE) == true -nullable(CHAR('a')) == false -nullable(ZERO | ONE) == true -nullable(ZERO | CHAR('a')) == false -nullable(ONE ~ ONE) == true -nullable(ONE ~ CHAR('a')) == false -nullable(STAR(ZERO)) == true -nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true -nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true -*/ - // (2) -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 ALTs(rs) => ALTs(for(reg <- rs) yield der(c, reg)) - case SEQs(Nil) => ZERO - case SEQs(r :: rs) => if(nullable(r)) ALT(SEQs(der(c, r) :: rs), der(c, SEQs(rs))) else SEQs(der(c, r) :: rs) - case STAR(r) => SEQ(der(c,r), STAR(r)) +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 ALTs(rs) => ALTs(rs.map(der(c, _))) + case SEQs(Nil) => ZERO + case SEQs(r1::rs) => + if (nullable(r1)) ALT(SEQs(der(c, r1)::rs), der(c, SEQs(rs))) + else SEQs(der(c, r1) :: rs) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) } -/* -der('a', ZERO | ONE) == (ZERO | ZERO) -der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), SEQs(List(ONE))) -der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a') -der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a'))) -der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a'))) -*/ // (3) def denest(rs: List[Rexp]) : List[Rexp] = rs match { - case Nil => Nil - case ZERO :: rest => denest(rest) - case ALTs(rgs) :: rest => rgs ::: denest(rest) - case r :: rest => r :: denest(rest) + case Nil => Nil + case ZERO::tl => denest(tl) + case ALTs(rs1)::rs2 => rs1 ::: denest(rs2) + case r::rs => r :: denest(rs) } -/* -denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) == List(ONE, ONE, CHAR('a')) -denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE) -*/ - // (4) def flts(rs: List[Rexp], acc: List[Rexp] = Nil) : List[Rexp] = rs match { - case Nil => acc - case ZERO :: rest => List(ZERO) - case ONE :: rest => flts(rest, acc) - case SEQs(rgs) :: rest => flts(rest, acc ::: rgs) - case r :: rest => flts(rest, acc ::: List(r)) + case Nil => acc + case ZERO::rs => ZERO::Nil + case ONE::rs => flts(rs, acc) + case SEQs(rs1)::rs => flts(rs, acc ::: rs1) + case r::rs => flts(rs, acc :+ r) } -/* -flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO) -flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b')) -flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE) -*/ - // (5) def ALTs_smart(rs: List[Rexp]) : Rexp = rs match { - case Nil => ZERO - case List(r) => r - case _ => ALTs(rs) + case Nil => ZERO + case r::Nil => r + case rs => ALTs(rs) } def SEQs_smart(rs: List[Rexp]) : Rexp = rs match { - case Nil => ONE - case List(r) => r - case _ => SEQs(rs) + case Nil => ONE + case ZERO::Nil => ZERO + case r::Nil => r + case rs => SEQs(rs) } -/* -SEQs_smart(Nil) == ONE -SEQs_smart(List(ZERO)) == ZERO -SEQs_smart(List(CHAR('a'))) == CHAR('a') -SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE -SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE)) -ALTs_smart(Nil) == ZERO -ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE -ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO)) -*/ +// (6) -// (6) def simp(r: Rexp) : Rexp = r match { - case ALTs(rs) => ALTs_smart(denest(for(reg <- rs) yield simp(reg)).distinct) - case SEQs(rs) => SEQs_smart(flts(for(reg <- rs) yield simp(reg))) - case _ => r + case ALTs(rs) => + ALTs_smart(denest(rs.map(simp)).distinct) + case SEQs(rs) => + SEQs_smart(flts(rs.map(simp))) + case r => r } -/* -simp(ZERO | ONE) == ONE -simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE) -simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a') -simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a') -simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a') -simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO -simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a') -simp(CHAR('a') | CHAR('a')) == CHAR('a') -simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a') -simp(ONE | CHAR('a')) == (ONE | CHAR('a')) -simp(ALT((CHAR('a') | ZERO) ~ ONE,((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a') -simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO -simp(ALT(ONE | ONE, ONE | ONE)) == ONE -simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a') -simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a')) -simp(ALTs(Nil)) == ZERO -simp(SEQs(List(CHAR('a')))) == CHAR('a') -*/ +//println("Simp tests") +//println(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE))) +//println(simp(((CHAR('a') | ZERO) ~ ONE) | +// (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO)))) -// (7) +// (7) + def ders (s: List[Char], r: Rexp) : Rexp = s match { - case Nil => r - case c :: cs => ders(cs, simp(der(c, r))) -} -def matcher(r: Rexp, s: String): Boolean = { - val derivatives = ders(s.toList, r) - nullable(derivatives) + case Nil => r + case c::s => ders(s, simp(der(c, r))) } -/* -val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -ders("aaaaa".toList, EVIL) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b'))) -ders(List('b'), EVIL) == ONE -ders("bb".toList, EVIL) == ZERO -matcher(EVIL, "a" * 5 ++ "b") == true -matcher(EVIL, "b") == true -matcher(EVIL, "bb") == false -matcher("abc", "abc") == true -matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true -matcher(ONE, "") == true -matcher(ZERO, "") == false -matcher(ONE | CHAR('a'), "") == true -matcher(ONE | CHAR('a'), "a") == true -*/ +// main matcher function +def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r)) // (8) + def size(r: Rexp): Int = r match { - case ZERO => 1 - case ONE => 1 - case CHAR(_) => 1 - case ALTs(rs) => 1 + (for(reg <- rs) yield size(reg)).sum - case SEQs(rs) => 1 + (for(reg <- rs) yield size(reg)).sum - case STAR(r) => 1 + size(r) + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALTs(rs) => 1 + rs.map(size).sum + case SEQs(rs) => 1 + rs.map(size).sum + case STAR(r1) => 1 + size(r1) } -/* -val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -size(der('a', der('a', EVIL))) == 36 -size(der('a', der('a', der('a', EVIL)))) == 83 -size(ders("aaaaaa".toList, EVIL)) == 7 -size(ders(("a" * 50).toList, EVIL)) == 7 -*/ -// Some testing data -//=================== +// some testing data /* - -simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) // => ALTs(List(ONE, CHAR(a))) -simp(((CHAR('a') | ZERO) ~ ONE) | (((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) // => CHAR(a) - -matcher(("a" ~ "b") ~ "c", "ab") // => false -matcher(("a" ~ "b") ~ "c", "abc") // => true - +println(matcher(("a" ~ "b") ~ "c", "abc")) // => true +println(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) // => false -matcher(EVIL, "a" * 1000 ++ "b") // => true - +println(matcher(EVIL, "a" * 1000 ++ "b")) // => true +println(matcher(EVIL, "a" * 1000)) // => false // size without simplifications -size(der('a', der('a', EVIL))) // => 36 -size(der('a', der('a', der('a', EVIL)))) // => 83 +println(size(der('a', der('a', EVIL)))) // => 36 +println(size(der('a', der('a', der('a', EVIL))))) // => 83 // size with simplification -size(simp(der('a', der('a', EVIL)))) // => 7 -size(simp(der('a', der('a', der('a', EVIL))))) // => 7 +println(simp(der('a', der('a', EVIL)))) +println(simp(der('a', der('a', der('a', EVIL))))) + +println(size(simp(der('a', der('a', EVIL))))) // => 7 +println(size(simp(der('a', der('a', der('a', EVIL)))))) // => 7 // Python needs around 30 seconds for matching 28 a's with EVIL. // Java 9 and later increase this to an "astonishing" 40000 a's in -// 30 seconds. +// around 30 seconds. // -// Lets see how long it really takes to match strings with -// 5 Million a's...it should be in the range of a few -// of seconds. +// Lets see how long it takes to match strings with +// 5 Million a's...it should be in the range of a +// few seconds. def time_needed[T](i: Int, code: => T) = { val start = System.nanoTime() @@ -266,15 +185,15 @@ } // another "power" test case -simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next()) == ONE +println(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next()) == ONE) // the Iterator produces the rexp // // SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE) // -// where SEQ is nested 50 times. +// where SEQ is nested 100 times. +*/ -*/ } diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test.sh --- a/main_testing3/re_test.sh Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test.sh Thu Nov 02 23:34:53 2023 +0000 @@ -13,24 +13,22 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out) } # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -nc -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null) } # purity test - function scala_vars { - (sed 's/immutable/ok/g' c$out > cb$out; - egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) + (sed 's/immutable/ok/g' c$out > cb$out; + egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) } - # compilation test echo -e "re.scala runs?" >> $out @@ -41,8 +39,6 @@ tsts=$(( 0 )) else echo -e " --> SCALA DID NOT RUN RE.SCALA\n" >> $out - echo -e " !!!! Have you checked that you are using Scala 2.13.XX (preferably with XX == 10)? !!!\n" >> $out - echo -e " !!!! All help-requests and emails where the problems are due to the use of Scala 3 will be quietly ingnored !!!\n" >> $out tsts=$(( 1 )) fi diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test0.scala --- a/main_testing3/re_test0.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test0.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,6 +1,9 @@ -import M3._ - -assert(ALTs.getClass == ALTs.getClass) -assert(SEQs.getClass == SEQs.getClass) +def urbanmain() = { + import M3._ + + assert(ALTs.getClass == ALTs.getClass) + assert(SEQs.getClass == SEQs.getClass) +} + diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test1.scala --- a/main_testing3/re_test1.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test1.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,13 +1,16 @@ -import M3._ + + +def urbanmain() = { + import M3._ -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) -assert(nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true) -assert(nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true) - + 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) + assert(nullable(ALTs(List(ONE, CHAR('a'), ZERO))) == true) + assert(nullable(SEQs(List(ONE, ALTs(List(ONE, CHAR('a'), ZERO)), STAR(ZERO)))) == true) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test2.scala --- a/main_testing3/re_test2.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test2.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,10 +1,14 @@ -import M3._ + +def urbanmain() = { + import M3._ -assert(der('a', ZERO | ONE) == ALT(ZERO, ZERO)) -assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALTs(List(SEQ(ALT(ONE, ZERO), CHAR('a')), SEQs(List(ONE))))) -assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')) -assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))) -assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))) + assert(der('a', ZERO | ONE) == ALT(ZERO, ZERO)) + assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALTs(List(SEQ(ALT(ONE, ZERO), CHAR('a')), SEQs(List(ONE))))) + assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')) + assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))) + assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))) +} + /* val r0_urban = "a" ~ "b" ~ "c" diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test3.scala --- a/main_testing3/re_test3.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test3.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,22 +1,25 @@ -import M3._ + +def urbanmain() = { + + import M3._ -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) ~ CHAR('a')) == CHAR('a')) -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(CHAR('a') ~ 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')) -assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO) -assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE) -assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')) -assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))) -assert(simp(ALTs(Nil)) == ZERO) -assert(simp(SEQs(List(CHAR('a')))) == CHAR('a')) + 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) ~ CHAR('a')) == CHAR('a')) + 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(CHAR('a') ~ 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')) + assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO) + assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE) + assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')) + assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE, CHAR('a'))) + assert(simp(ALTs(Nil)) == ZERO) + assert(simp(SEQs(List(CHAR('a')))) == CHAR('a')) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test4.scala --- a/main_testing3/re_test4.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test4.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,5 +1,10 @@ -import M3._ + +def urbanmain() = { + + import M3._ -assert(denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) - == List(ONE, ONE, CHAR('a'))) -assert(denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE)) + assert(denest(List(ONE, ZERO, ALTs(List(ONE, CHAR('a'))))) == List(ONE, ONE, CHAR('a'))) + assert(denest(List(ONE ~ ONE, ZERO, ZERO | ONE)) == List(ONE ~ ONE, ZERO, ONE)) + + +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test5.scala --- a/main_testing3/re_test5.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test5.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,6 +1,11 @@ -import M3._ + +def urbanmain() = { + + import M3._ -assert(flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO)) -assert(flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b'))) -assert(flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE)) + assert(flts(List(CHAR('a'), ZERO, ONE), Nil) == List(ZERO)) + assert(flts(List(CHAR('a'), ONE, ONE, CHAR('b')), Nil) == List(CHAR('a'), CHAR('b'))) + assert(flts(List(ONE ~ CHAR('a'), CHAR('b') ~ ONE), Nil) == List(ONE, CHAR('a'), CHAR('b'), ONE)) +} + diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test6.scala --- a/main_testing3/re_test6.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test6.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,10 +1,14 @@ -import M3._ + +def urbanmain() = { + + import M3._ -assert(SEQs_smart(Nil) == ONE) -assert(SEQs_smart(List(ZERO)) == ZERO) -assert(SEQs_smart(List(CHAR('a'))) == CHAR('a')) -assert(SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE) -assert(SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE))) -assert(ALTs_smart(Nil) == ZERO) -assert(ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE) -assert(ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO))) + assert(SEQs_smart(Nil) == ONE) + assert(SEQs_smart(List(ZERO)) == ZERO) + assert(SEQs_smart(List(CHAR('a'))) == CHAR('a')) + assert(SEQs_smart(List(ONE ~ ONE)) == ONE ~ ONE) + assert(SEQs_smart(List(ONE, ONE)) == SEQs(List(ONE, ONE))) + assert(ALTs_smart(Nil) == ZERO) + assert(ALTs_smart(List(ONE ~ ONE)) == ONE ~ ONE) + assert(ALTs_smart(List(ZERO, ZERO)) == ALTs(List(ZERO, ZERO))) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test7.scala --- a/main_testing3/re_test7.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test7.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,19 +1,22 @@ -import M3._ -val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) +def urbanmain() = { + import M3._ + + val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -assert(ders(("a" * 5).toList, EVIL_urban) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b')))) -assert(ders(List('b'), EVIL_urban) == ONE) -assert(ders(List('b','b'), EVIL_urban) == ZERO) -assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true) -assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true) -assert(matcher(EVIL_urban, "a" * 50) == false) -assert(matcher(EVIL_urban, "b") == true) -assert(matcher(EVIL_urban, "bb") == false) -assert(matcher("abc", "abc") == true) -assert(matcher("abc", "ab") == false) -assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true) -assert(matcher(ONE, "") == true) -assert(matcher(ZERO, "") == false) -assert(matcher(ONE | CHAR('a'), "") == true) -assert(matcher(ONE | CHAR('a'), "a") == true) + assert(ders(("a" * 5).toList, EVIL_urban) == SEQs(List(STAR(CHAR('a')), STAR(STAR(CHAR('a'))), CHAR('b')))) + assert(ders(List('b'), EVIL_urban) == ONE) + assert(ders(List('b','b'), EVIL_urban) == ZERO) + assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true) + assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true) + assert(matcher(EVIL_urban, "a" * 50) == false) + assert(matcher(EVIL_urban, "b") == true) + assert(matcher(EVIL_urban, "bb") == false) + assert(matcher("abc", "abc") == true) + assert(matcher("abc", "ab") == false) + assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true) + assert(matcher(ONE, "") == true) + assert(matcher(ZERO, "") == false) + assert(matcher(ONE | CHAR('a'), "") == true) + assert(matcher(ONE | CHAR('a'), "a") == true) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test8.scala --- a/main_testing3/re_test8.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test8.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,8 +1,12 @@ -import M3._ -val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +def urbanmain() = { + + import M3._ + val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -assert(size(der('a', der('a', EVIL_urban))) == 36) -assert(size(der('a', der('a', der('a', EVIL_urban)))) == 83) + assert(size(der('a', der('a', EVIL_urban))) == 36) + assert(size(der('a', der('a', der('a', EVIL_urban)))) == 83) -assert(size(ders("aaaaaa".toList, EVIL_urban)) == 7) -assert(size(ders(("a" * 50).toList, EVIL_urban)) == 7) + assert(size(ders("aaaaaa".toList, EVIL_urban)) == 7) + assert(size(ders(("a" * 50).toList, EVIL_urban)) == 7) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing3/re_test9.scala --- a/main_testing3/re_test9.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing3/re_test9.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,9 +1,13 @@ -import M3._ + +def urbanmain() = { -val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + import M3._ + + val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE) -assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE) -assert(matcher(EVIL_urban, "a" * 1000000) == false) -assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true) + assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE) + assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE) + assert(matcher(EVIL_urban, "a" * 1000000) == false) + assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf.scala --- a/main_testing5/bf.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,164 +1,166 @@ -// Main Part 5 about an Interpreter for -// the Brainf*** language +// Core Part about an Interpreter for +// the Brainf***++ language //============================================== +object M5a { + -object M5a { - -// representation of BF memory +// representation of Bf memory type Mem = Map[Int, Int] + +// (1) Write a function that takes a file name as argument and +// and requests the corresponding file from disk. It Returns the +// content of the file as a String. If the file does not exists, +// the function should Return the empty string. + import io.Source import scala.util._ -// ADD YOUR CODE BELOW -//====================== - -// (1) -def load_bff(name: String) : String = { - Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -} - -// (2) +def load_bff(name: String) : String = + Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -def sread(mem: Mem, mp: Int) : Int = { - Try(mem.apply(mp)).getOrElse(0) -} - -def write(mem: Mem, mp: Int, v: Int) : Mem = { - mem + (mp -> v) -} - -// sread(Map(), 2) == 0 -// sread(Map(2 -> 1), 2) == 1 -// write(Map(), 1, 2) == Map(1 -> 2) -// write(Map(1 -> 0), 1, 2) == Map(1 -> 2) -// val current = sread(Map(2 -> 1), 2) -// write(Map(2 -> 1), 2, current+1) - -// (3) +// (2) 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, provided 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 jumpRight(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ - case '[' => jumpRight(prog, pc+1, level+1) - case ']' => level match { - case 0 => pc+1 - case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level-1) - } - case _ => if (pc+1 >= prog.length) prog.length else jumpRight(prog, pc+1, level) -} -def jumpLeft(prog: String, pc: Int, level: Int) : Int = prog.toList.apply(pc) match{ - case ']' => jumpLeft(prog, pc-1, level+1) - case '[' => level match { - case 0 => pc+1 - case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level-1) - } - case _ => if (pc-1 < 0) -1 else jumpLeft(prog, pc-1, level) -} +def sread(mem: Mem, mp: Int) : Int = + mem.getOrElse(mp, 0) + +def write(mem: Mem, mp: Int, v: Int) : Mem = + mem.updated(mp, v) -// testcases -// jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 -// jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 -// jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 -// jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 -// jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) -// jumpLeft("""[******]***""", 7, 0) // => -1 (outside) +// (3) 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, 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) + } +} + +// test cases +//jumpRight("""--[..+>--].>.++""", 3, 0) // => 10 +//jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3 +//jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12 +//jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18 +//jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside) +//jumpLeft("""[******]***""", 7, 0) // => -1 (outside) +// (4) Complete the compute function that interprets (runs) a brainf***++ +// program: the arguments are a program (represented as a string), a program +// counter, a memory counter and a brainf***++ memory. It Returns the +// memory at the stage when the execution of the brainf***++ program +// finishes. The interpretation finishes once the program counter +// pc is pointing to something outside the program string. +// If the pc points to a character inside the program, the pc, +// memory pointer and memory need to be updated according to +// rules of the brainf***++ language. Then, recursively, the compute +// function continues with the command at the new program +// counter. +// +// Implement the run function that calls compute with the program +// counter and memory counter set to 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) -// (4) -def compute(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = (pc >= 0 && pc < prog.length) match { - case false => mem - case true => prog.toList.apply(pc) match{ - case '>' => compute(prog, pc+1, mp+1, mem) - case '<' => compute(prog, pc+1, mp-1, mem) - case '+' => { - val current = sread(mem, mp) - compute(prog, pc+1, mp, write(mem, mp, current+1)) - } - case '-' => { - val current = sread(mem, mp) - compute(prog, pc+1, mp, write(mem, mp, current-1)) - } - case '.' => { - print(mem.apply(mp).toChar) - compute(prog, pc+1, mp, mem) - } - case '[' => { - if (mem.apply(mp) == 0) compute(prog, jumpRight(prog, pc+1, 0), mp, mem) - else compute(prog, pc+1, mp, mem) - } - case ']' => { - if (mem.apply(mp) != 0) compute(prog, jumpLeft(prog, pc-1, 0), mp, mem) - else compute(prog, pc+1, mp, mem) - } - case _ => compute(prog, pc, mp, mem) - } +def generate(msg: List[Char]) : String = msg match { + case Nil => "" + case c::cs => s"${"+" * c.toInt}.[-]" ++ generate(cs) } -def run(prog: String, m: Mem = Map()) = { - compute(prog, 0, 0, m) -} +//println(generate("Hello World\n".toList)) -// run("[-]", Map(0 -> 100)) == Map(0 -> 0) -// run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10) -// run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42) -// run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(0 -> 0, 1 -> 58, 2 -> 32) -// (5) -def generate(msg: List[Char]) : String = msg match { - case Nil => "" - case c => "+"*c.head.toInt + ".[-]" + generate(msg.tail) -} - -// generate("ABC".toList) - -// run("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]", Map()) - -// some sample bf-programs collected from the Internet -//===================================================== +// some sample bf/bf++-programs collected from the Internet +//========================================================== // some contrived (small) programs //--------------------------------- -// // clears the 0-cell -// run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 +// clears the 0-cell +//run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 -// // moves content of the 0-cell to 1-cell -// run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 +// moves content of the 0-cell to 1-cell +//run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 -// // copies content of the 0-cell to 2-cell and 4-cell -// run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42) +// copies content of the 0-cell to 2-cell and 4-cell +//run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42) -// // prints out numbers 0 to 9 -// run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") +// prints out numbers 0 to 9 +//run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") -// // some more "useful" programs -// //----------------------------- +// some more "useful" programs +//----------------------------- -// // hello world program 1 -// run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""") +// hello world program 1 +//run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ +// ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") -// // hello world program 2 -// run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.""") +// hello world program 2 +//run("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ +// +.<<+++++++++++++++.>.+++.------.--------.>+.>.""") -// // hello world program 3 -// run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") +// hello world program 3 +//run("""+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++.. +// +++.>-.------------.<++++++++.--------.+++.------.--------.>+.""") -// // draws the Sierpinski triangle -// run(load_bff("sierpinski.bf")) +// draws the Sierpinski triangle +//run(load_bff("sierpinski.bf")) -// //fibonacci numbers below 100 -// run("""+++++++++++ +//fibonacci numbers below 100 +//run("""+++++++++++ // >+>>>>++++++++++++++++++++++++++++++++++++++++++++ // >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> // +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- @@ -170,15 +172,15 @@ // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") -// //outputs the square numbers up to 10000 -// run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ +//outputs the square numbers up to 10000 +//run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ // >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] // <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") -// // calculates 2 to the power of 6 -// // (example from a C-to-BF compiler at https://github.com/elikaski/BF-it) -// run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] +// calculates 2 to the power of 6 +//(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) +//run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] @@ -195,28 +197,25 @@ -// // a Mandelbrot set generator in brainf*** written by Erik Bosman +// a Mandelbrot set generator in brainf*** written by Erik Bosman // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) - -// run(load_bff("mandelbrot.bf")) +// +//run(load_bff("mandelbrot.bf")) -// // a benchmark program (counts down from 'Z' to 'A') -// // -// run(load_bff("benchmark.bf")) +// a benchmark program (counts down from 'Z' to 'A') +// +//run(load_bff("benchmark.bf")) -// // calculates the Collatz series for numbers from 1 to 30 -// // -// run(load_bff("collatz.bf")) +// calculates the Collatz series for numbers from 1 to 30 +// +//run(load_bff("collatz.bf")) } - - +//M5a.run(M5a.load_bff("mandelbrot.bf")) +//M5a.run(M5a.load_bff("collatz.bf")) -// This template code is subject to copyright -// by King's College London, 2022. Do not -// make the template code public in any shape -// or form, and do not exchange it with other -// students under any circumstance. +//println(M5a.generate("ABC".toList)) +//M5a.run(M5a.generate("Hello World\n".toList)) diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test.sh --- a/main_testing5/bf_test.sh Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test.sh Thu Nov 02 23:34:53 2023 +0000 @@ -14,20 +14,19 @@ # compilation tests function scala_compile { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out) } # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null) } # purity test - function scala_vars { - (sed 's/immutable/ok/g' c$out > cb$out; - egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) + (sed 's/immutable/ok/g' c$out > cb$out; + egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) } diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test1.scala --- a/main_testing5/bf_test1.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test1.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,4 +1,9 @@ -import M5a._ + +def urbanmain() = { + + import M5a._ -assert(load_bff("benchmark.bf").length == 188) -assert(load_bff("foobar.bf") == "") + assert(load_bff("benchmark.bf").length == 188) + assert(load_bff("foobar.bf") == "") + +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test2.scala --- a/main_testing5/bf_test2.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test2.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,6 +1,10 @@ -import M5a._ + +def urbanmain() = { + + import M5a._ -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)) + 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)) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test3.scala --- a/main_testing5/bf_test3.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test3.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,10 +1,14 @@ -import M5a._ + +def urbanmain() = { + + import M5a._ -assert(jumpRight("[xxxxxx]xxx", 1, 0) == 8) -assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8) -assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8) -assert(jumpRight("[xx[xxx]xxx", 1, 0) == 11) -assert(jumpRight("[x[][]x]xxx", 1, 0) == 8) -assert(jumpLeft("[xxxxxx]xxx", 6, 0) == 1) -assert(jumpLeft("[xxxxxx]xxx", 7, 0) == -1) -assert(jumpLeft("[x[][]x]xxx", 6, 0) == 1) + assert(jumpRight("[xxxxxx]xxx", 1, 0) == 8) + assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8) + assert(jumpRight("[xx[x]x]xxx", 1, 0) == 8) + assert(jumpRight("[xx[xxx]xxx", 1, 0) == 11) + assert(jumpRight("[x[][]x]xxx", 1, 0) == 8) + assert(jumpLeft("[xxxxxx]xxx", 6, 0) == 1) + assert(jumpLeft("[xxxxxx]xxx", 7, 0) == -1) + assert(jumpLeft("[x[][]x]xxx", 6, 0) == 1) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test4.scala --- a/main_testing5/bf_test4.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test4.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,13 +1,16 @@ -import M5a._ + +def urbanmain() = { -assert(run("[-]", Map(0 -> 100)) == Map(0 -> 0)) -assert(run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)) -assert(run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)) + import M5a._ + + assert(run("[-]", Map(0 -> 100)) == Map(0 -> 0)) + assert(run("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)) + assert(run("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)) -val hw_urban = """+++++[->++++++++++<]>--<+++[->>++++++++++ - <<]>>++<<----------[+>.>.<+<]""" -assert(run(hw_urban) == Map(0 -> 0, 1 -> 58, 2 -> 32)) - + val hw_urban = """+++++[->++++++++++<]>--<+++[->>++++++++++ + <<]>>++<<----------[+>.>.<+<]""" + assert(run(hw_urban) == Map(0 -> 0, 1 -> 58, 2 -> 32)) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test5.scala --- a/main_testing5/bf_test5.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test5.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,5 +1,8 @@ -import M5b._ + +def urbanmain() = { -assert(jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == - Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)) + import M5b._ + assert(jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") == Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6)) + +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test6.scala --- a/main_testing5/bf_test6.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test6.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,10 +1,14 @@ -import M5b._ -//println(optimise(load_bff("benchmark.bf")).length) -//println(optimise(load_bff("mandelbrot.bf")).length) +def urbanmain() = { + + import M5b._ -val urban_l1 = optimise(load_bff("benchmark.bf")).length -val urban_l2 = optimise(load_bff("mandelbrot.bf")).length + //println(optimise(load_bff("benchmark.bf")).length) + //println(optimise(load_bff("mandelbrot.bf")).length) -assert(urban_l1 == 181) -assert(urban_l2 == 11203) + val urban_l1 = optimise(load_bff("benchmark.bf")).length + val urban_l2 = optimise(load_bff("mandelbrot.bf")).length + + assert(urban_l1 == 181) + assert(urban_l2 == 11203) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bf_test7.scala --- a/main_testing5/bf_test7.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bf_test7.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,7 +1,11 @@ -import M5b._ + +def urbanmain() = { + + import M5b._ -//println(combine(optimise(load_bff("benchmark.bf"))).length) -//println(combine(optimise(load_bff("mandelbrot.bf"))).length) + //println(combine(optimise(load_bff("benchmark.bf"))).length) + //println(combine(optimise(load_bff("mandelbrot.bf"))).length) -assert(combine(optimise(load_bff("benchmark.bf"))).length == 134) -assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6509) + assert(combine(optimise(load_bff("benchmark.bf"))).length == 134) + assert(combine(optimise(load_bff("mandelbrot.bf"))).length == 6509) +} diff -r b528d1d3d3c3 -r 59e005dcf163 main_testing5/bfc.scala --- a/main_testing5/bfc.scala Thu Nov 02 13:53:37 2023 +0000 +++ b/main_testing5/bfc.scala Thu Nov 02 23:34:53 2023 +0000 @@ -1,6 +1,5 @@ -// Main Part 5 about a "Compiler" for the Brainf*** language -//============================================================ - +// Part 2 about a "Compiler" for the Brainf*** language +//====================================================== object M5b { @@ -11,15 +10,6 @@ // 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 @@ -27,154 +17,296 @@ (end - start)/(n * 1.0e9) } +type Mem = Map[Int, Int] -type Mem = Map[Int, Int] import io.Source import scala.util._ -// ADD YOUR CODE BELOW -//====================== +def load_bff(name: String) : String = + Try(Source.fromFile(name)("ISO-8859-1").mkString).getOrElse("") -// (6) +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 (pc >= prog.length) prog.length - else if (prog(pc) == '[') jumpRight(prog, pc + 1, level + 1) - else if (prog(pc) == ']' && level == 0) pc + 1 - else if (prog(pc) == ']') jumpRight(prog, pc + 1, level - 1) - else jumpRight(prog, pc + 1, level) + 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 jtable(pg: String) : Map[Int, Int] = { - val pairs = for { - i <- 0 until pg.length - if pg.charAt(i) == '[' - j = jumpRight(pg, i+1, 0) - } yield (i, j) - pairs.flatMap { case (i, j) => - List((i, j), (j-1, i+1)) - }.toMap -} - -def write(mem: Mem, mp: Int, v: Int) : Mem = mem + (mp -> v) - -// 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 (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute2(pg, tb, npc, nmp, nmem) +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 run2(pg: String, m: Mem = Map()) = - compute2(pg, jtable(pg), 0, 0, m) - +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 +} -// testcases -// time_needed(1, run2(load_bff("benchmark.bf"))) -// time_needed(1, run2(load_bff("sierpinski.bf"))) +def run(prog: String, m: Mem = Map()) = compute(prog, 0, 0, m) + + +// 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. -// (7) +// (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 + + +// testcase +// jtable("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") +// => Map(69 -> 61, 5 -> 20, 60 -> 70, 27 -> 44, 43 -> 28, 19 -> 6) + -def optimise(s: String) : String = - s.replaceAll("""[^<>+-.,\[\]]""","").replaceAll("""\[-\]""","0") +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 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 (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute3(pg, tb, npc, nmp, nmem) - } + 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 opt_pg = optimise(pg) - val jt = jtable(opt_pg) - compute3(opt_pg, jt, 0, 0, m) +def run3(pg: String, m: Mem = Map()) = { + val pg_opt = optimise(pg) + compute3(pg_opt, jtable(pg_opt), 0, 0, m) } // testcases -// -// optimise(load_bff("benchmark.bf")) // should have inserted 0's -// optimise(load_bff("mandelbrot.bf")).length // => 11203 -// optimise(load_bff("benchmark.bf")).length -// time_needed(1, run3(load_bff("benchmark.bf"))) + +//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"))) + -// (8) -def combine(s: String): String = ??? +// (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. -// testcase -// combine(load_bff("benchmark.bf")) +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 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 +} + + +//combine(load_bff("benchmark.bf")) def compute4(pg: String, tb: Map[Int, Int], pc: Int, mp: Int, mem: Mem) : Mem = { - if (pc >= pg.length) mem - else { - val (npc, nmp, nmem) = pg(pc) match { - case '>' => (pc + 1, mp + 1, mem) - case '<' => (pc + 1, mp - 1, mem) - case '+' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) + 1))) - case '-' => (pc + 1, mp, mem + (mp -> (mem.getOrElse(mp, 0) - 1))) - case '.' => {print(mem.getOrElse(mp,0).toChar);(pc + 1, mp, mem)} - case '[' => if (mem.getOrElse(mp, 0) == 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case ']' => if (mem.getOrElse(mp, 0) != 0) (tb(pc), mp, mem) else (pc + 1, mp, mem) - case _ => (pc + 1, mp, mem) - } - compute3(pg, tb, npc, nmp, nmem) - } + 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 } -// should call first optimise and then combine on the input string -// -def run4(pg: String, m: Mem = Map()) = { - val co_opt_pg = combine(optimise(pg)) - val jt = jtable(co_opt_pg) - compute3(co_opt_pg, jt, 0, 0, m) +def run4(pg: String, m: Mem = Map()) = { + val pg_opt = combine(optimise(pg)) + compute4(pg_opt, jtable(pg_opt), 0, 0, m) } // testcases -// combine(optimise(load_bff("benchmark.bf"))) // => """>A+B[A-A] """>A+B[A-A] c$out 1> c$out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli compile "$1" 2> c$out 1> c$out) } # functional tests function scala_assert { - (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala-cli -i "$1" "$2" -e "urbanmain()" 2> /dev/null 1> /dev/null) } # purity test - function scala_vars { - (sed 's/immutable/ok/g' c$out > cb$out; - egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) + (sed 's/immutable/ok/g' c$out > cb$out; + egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' cb$out 2> /dev/null 1> /dev/null) } - # compilation test echo -e "bfc.scala runs?" >> $out