# HG changeset patch # User Christian Urban # Date 1511434607 0 # Node ID 4383809c176a391bd65dfc6fe26f2020283911c6 # Parent 114a89518aea5fe06d758e2b5c1e2dcee16d32f2 updated diff -r 114a89518aea -r 4383809c176a TAs --- a/TAs Tue Nov 21 16:31:11 2017 +0000 +++ b/TAs Thu Nov 23 10:56:47 2017 +0000 @@ -15,4 +15,16 @@ -scala -Dscala.color \ No newline at end of file +scala -Dscala.color + +CW6, Part 1 + 2 + late +154 => 6 (155) +66 => 5 (66) +18 => 4 (18) +13 => 3 (12) +5 => 2 (5) +2 => 1 (2) +21 => 0 (21) +-------- +279 submissions \ No newline at end of file diff -r 114a89518aea -r 4383809c176a cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 114a89518aea -r 4383809c176a cws/cw03.tex --- a/cws/cw03.tex Tue Nov 21 16:31:11 2017 +0000 +++ b/cws/cw03.tex Thu Nov 23 10:56:47 2017 +0000 @@ -1,18 +1,60 @@ \documentclass{article} \usepackage{../style} \usepackage{../langs} +\usepackage{tikz} +\usepackage{pgf} +\usepackage{pgfplots} + +\begin{filecontents}{re-python2.data} +1 0.033 +5 0.036 +10 0.034 +15 0.036 +18 0.059 +19 0.084 +20 0.141 +21 0.248 +22 0.485 +23 0.878 +24 1.71 +25 3.40 +26 7.08 +27 14.12 +28 26.69 +\end{filecontents} + +\begin{filecontents}{re-java.data} +5 0.00298 +10 0.00418 +15 0.00996 +16 0.01710 +17 0.03492 +18 0.03303 +19 0.05084 +20 0.10177 +21 0.19960 +22 0.41159 +23 0.82234 +24 1.70251 +25 3.36112 +26 6.63998 +27 13.35120 +28 29.81185 +\end{filecontents} + \begin{document} -\section*{Coursework 8 (Scala, Regular Expressions)} +\section*{Coursework 8 (Scala, Regular Expressions, Brainf***)} This coursework is worth 10\%. It is about regular expressions, -pattern matching and polymorphism. The first part is due on 30 +pattern matching and an interpreter. The first part is due on 30 November at 11pm; the second, more advanced part, is due on 21 -December at 11pm. You are asked to implement a regular expression -matcher based on derivatives of regular expressions. The reason is -that regular expression matching in Java can be extremely slow -sometimes.\bigskip +December at 11pm. In the first part, you are asked to implement a +regular expression matcher based on derivatives of regular +expressions. The reason is that regular expression matching in Java +can sometimes be extremely slow. The advanced part is about an +interpreter for a very simple programming language.\bigskip \noindent \textbf{Important:} @@ -54,9 +96,11 @@ \subsection*{Part 1 (6 Marks)} The task is to implement a regular expression matcher that is based on -derivatives of regular expressions. The implementation can deal -with the following regular expressions, which have been predefined -in the file re.scala: +derivatives of regular expressions. Most of the functions are defined by +recursion over regular expressions and can be elegantly implemented +using Scala's pattern-matching. The implementation should deal with the +following regular expressions, which have been predefined in the file +\texttt{re.scala}: \begin{center} \begin{tabular}{lcll} @@ -91,7 +135,7 @@ \begin{itemize} \item[(1a)] Implement a function, called \textit{nullable}, by recursion over regular expressions. This function tests whether a - regular expression can match the empty string, that is given a + regular expression can match the empty string. This means given a regular expression it either returns true or false. \begin{center} @@ -163,9 +207,9 @@ \item[(1c)] Implement the function \textit{simp}, which recursively traverses a regular expression from the inside to the outside, and - simplifies every sub-regular-expression on the left (see below) to - the regular expression on the right, except it does not simplify inside - ${}^*$-regular expressions. + on the way simplifies every regular expression on the left (see + below) to the regular expression on the right, except it does not + simplify inside ${}^*$-regular expressions. \begin{center} \begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll} @@ -182,17 +226,18 @@ For example the regular expression \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] - simplifies to just $r_1$. \textbf{Hints:} Regular expressions can be + simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be seen as trees and there are several methods for traversing - trees. One of them corresponds to the inside-out traversal. Also - remember numerical expressions from school: there you had expressions + trees. One of them corresponds to the inside-out traversal, which is + sometimes also called post-order traversal. Furthermore, + remember numerical expressions from school times: there you had expressions like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$ and simplification rules that looked very similar to rules above. You would simplify such numerical expressions by replacing for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then look whether more rules are applicable. If you organise the simplification in an inside-out fashion, it is always clear which - rule should applied next.\\\mbox{}\hfill[1 Mark] + rule should be applied next.\hfill[2 Marks] \item[(1d)] Implement two functions: The first, called \textit{ders}, takes a list of characters and a regular expression as arguments, and @@ -214,81 +259,10 @@ according to \textit{ders} and after that tests whether the resulting derivative regular expression can match the empty string (using \textit{nullable}). For example the \textit{matcher} will produce -true given the regular expression $(a\cdot b)\cdot c$ and the string -$abc$.\\ \mbox{}\hfill[1 Mark] - -\item[(1e)] Implement the function $\textit{replace}\;r\;s_1\;s_2$: it searches - (from the left to -right) in the string $s_1$ all the non-empty substrings that match the -regular expression $r$---these substrings are assumed to be -the longest substrings matched by the regular expression and -assumed to be non-overlapping. All these substrings in $s_1$ matched by $r$ -are replaced by $s_2$. For example given the regular expression - -\[(a \cdot a)^* + (b \cdot b)\] - -\noindent the string $s_1 = aabbbaaaaaaabaaaaabbaaaabb$ and -replacement the string $s_2 = c$ yields the string - -\[ -ccbcabcaccc -\] - -\hfill[2 Marks] -\end{itemize} - - - - -\subsection*{Part 2 (4 Marks)} - -You need to copy all the code from \texttt{re.scala} into -\texttt{re2.scala} in order to complete Part 2. Parts (2a) and (2b) -give you another method and datapoints for testing the \textit{der} -and \textit{simp} functions from Part~1. - -\subsubsection*{Tasks (file re2.scala)} +true for the regular expression $(a\cdot b)\cdot c$ and the string +$abc$, but false if you give it the string $ab$. \hfill[1 Mark] -\begin{itemize} -\item[(2a)] Write a \textbf{polymorphic} function, called - \textit{iterT}, that is \textbf{tail-recursive}(!) and takes an - integer $n$, a function $f$ and an $x$ as arguments. This function - should iterate $f$ $n$-times starting with the argument $x$, like - - \[\underbrace{f(\ldots (f}_{n\text{-times}}(x))) - \] - - More formally that means \textit{iterT} behaves as follows: - - \begin{center} - \begin{tabular}{lcl} - $\textit{iterT}(n, f, x)$ & $\dn$ & - $\begin{cases} - \;x & \textit{if}\;n = 0\\ - \;f(\textit{iterT}(n - 1, f, x)) & \textit{otherwise} - \end{cases}$ - \end{tabular} -\end{center} - - Make sure you write a \textbf{tail-recursive} version of - \textit{iterT}. If you add the annotation \texttt{@tailrec} (see - below) your code should not produce an error message. - - \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - import scala.annotation.tailrec - - @tailrec - def iterT[A](n: Int, f: A => A, x: A): A = ... - \end{lstlisting} - - You can assume that \textit{iterT} will only be called for positive - integers $0 \le n$. Given the type variable \texttt{A}, the type of - $f$ is \texttt{A => A} and the type of $x$ is \texttt{A}. This means - \textit{iterT} can be used, for example, for functions from integers - to integers, or strings to strings, or regular expressions to - regular expressions. \\ \mbox{}\hfill[2 Marks] - -\item[(2b)] Implement a function, called \textit{size}, by recursion +\item[(1e)] Implement a function, called \textit{size}, by recursion over regular expressions. If a regular expression is seen as a tree, then \textit{size} should return the number of nodes in such a tree. Therefore this function is defined as follows: @@ -304,49 +278,12 @@ \end{tabular} \end{center} -You can use \textit{size} and \textit{iterT} in order to test how much -the 'evil' regular expression $(a^*)^* \cdot b$ grows when taking -successive derivatives according the letter $a$ and then compare it to -taking the derivative, but simlifying the derivative after each step. -For example, the calls - - \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] - size(iterT(20, (r: Rexp) => der('a', r), EVIL)) - size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) - \end{lstlisting} - - produce without simplification a regular expression of size of - 7340068 after 20 iterations, while the one with - simplification gives - just 8.\\ \mbox{}\hfill[1 Mark] - - -\item[(2c)] Write a \textbf{polymorphic} function, called - \textit{fixpT}, that takes - a function $f$ and an $x$ as arguments. The purpose - of \textit{fixpT} is to calculate a fixpoint of the function $f$ - starting from the argument $x$. - A fixpoint, say $y$, is when $f(y) = y$ holds. - That means \textit{fixpT} behaves as follows: - - \begin{center} - \begin{tabular}{lcl} - $\textit{fixpT}(f, x)$ & $\dn$ & - $\begin{cases} - \;x & \textit{if}\;f(x) = x\\ - \;\textit{fixpT}(f, f(x)) & \textit{otherwise} - \end{cases}$ - \end{tabular} -\end{center} - - Make sure you calculate in the code of $\textit{fixpT}$ the result - of $f(x)$ only once. Given the type variable \texttt{A} in - $\textit{fixpT}$, the type of $f$ is \texttt{A => A} and the type of - $x$ is \texttt{A}. The file \texttt{re2.scala} gives two example - function where in one the fixpoint is 1 and in the other - it is the string $a$.\\ \mbox{}\hfill[1 Mark] -\end{itemize}\bigskip - +You can use \textit{size} in order to test how much the `evil' regular +expression $(a^*)^* \cdot b$ grows when taking successive derivatives +according the letter $a$ without simplification and then compare it to +taking the derivative, but simplify the result. The sizes +are given in \texttt{re.scala}. \hfill[1 Mark] +\end{itemize} \subsection*{Background} @@ -354,36 +291,101 @@ function might not so easy to be seen. To understand its purpose better, assume a regular expression $r$ can match strings of the form $c\!::\!cs$ (that means strings which start with a character $c$ and have -some rest, or tail, $cs$). If you now take the derivative of $r$ with -respect to the character $c$, then you obtain a regular expressions +some rest, or tail, $cs$). If you take the derivative of $r$ with +respect to the character $c$, then you obtain a regular expression that can match all the strings $cs$. In other words, the regular -expression $\textit{der}\;c\;r$ can match the same strings $c::cs$ +expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$ that can be matched by $r$, except that the $c$ is chopped off. Assume now $r$ can match the string $abc$. If you take the derivative according to $a$ then you obtain a regular expression that can match $bc$ (it is $abc$ where the $a$ has been chopped off). If you now -build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r))$ you +build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you obtain a regular expression that can match the string $c$ (it is $bc$ where $b$ is chopped off). If you finally build the derivative of this according $c$, that is -$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r)))$, you -obtain a regular expression that can match the empty string. You can -test this using the function nullable, which is what your matcher is -doing. +$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain +a regular expression that can match the empty string. You can test +whether this is indeed the case using the function nullable, which is +what your matcher is doing. -The purpose of the simp function is to keep the regular expression -small. Normally the derivative function makes the regular expression -bigger (see the SEQ case and the example in (2b)) and the algorithm -would be slower and slower over time. The simp function counters this -increase in size and the result is that the algorithm is fast -throughout. By the way, this algorithm is by Janusz Brzozowski who -came up with the idea of derivatives in 1964 in his PhD thesis. +The purpose of the $\textit{simp}$ function is to keep the regular +expression small. Normally the derivative function makes the regular +expression bigger (see the SEQ case and the example in (1b)) and the +algorithm would be slower and slower over time. The $\textit{simp}$ +function counters this increase in size and the result is that the +algorithm is fast throughout. By the way, this algorithm is by Janusz +Brzozowski who came up with the idea of derivatives in 1964 in his PhD +thesis. \begin{center}\small \url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)} \end{center} + +If you want to see how badly the regular expression matchers do in +Java and Python with the `evil' regular expression, then have a look +at the graphs below (you can try it out for yourself: have a look at +the file \texttt{catastrophic.java} on KEATS). Compare this with the +matcher you have implemented. How long can the string of $a$'s be +in your matcher and stay within the 30 seconds time limit? + +\begin{center} +\begin{tikzpicture} +\begin{axis}[ + title={Graph: $(a^*)^*\cdot b$ and strings + $\underbrace{a\ldots a}_{n}$}, + xlabel={$n$}, + x label style={at={(1.05,0.0)}}, + ylabel={time in secs}, + enlargelimits=false, + xtick={0,5,...,30}, + xmax=33, + ymax=35, + ytick={0,5,...,30}, + scaled ticks=false, + axis lines=left, + width=6cm, + height=5.0cm, + legend entries={Python, Java}, + legend pos=outer north east] +\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; +\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\end{axis} +\end{tikzpicture} +\end{center} +\newpage + +\subsection*{Part 2 (4 Marks)} + +Comming from Java or C++, you might think Scala is a quite +esotheric programming language. But remember, some serious companies +have built their business on Scala. And there are far more esotheric +languages out there. One is called \emph{brainf***}. Urban M\"uller +developed this language in 1993. A close relative was already +introduced in ... by Corado B\"ohm, an Italian computer pionier, who +unfortunately died a few months ago. One feature of brainf*** is its +minimalistic set of instructions. It has just 8 instructions, all of +which are single characters. Despite this minimalism, this language, +given enough memory, has been shown to be Turing complete. In this +part you will implement an interpreter for this language. + + + +\subsubsection*{Tasks (file bf.scala)} + +\begin{itemize} +\item[(2a)] + +\item[(2b)] + +\item[(2c)] + +\end{itemize}\bigskip + + + + \end{document} diff -r 114a89518aea -r 4383809c176a progs/lecture3.scala --- a/progs/lecture3.scala Tue Nov 21 16:31:11 2017 +0000 +++ b/progs/lecture3.scala Thu Nov 23 10:56:47 2017 +0000 @@ -51,22 +51,41 @@ -// One of only two places where I conceded to mutable -// data structures: The following function generates -// new labels +// Roman Numerals +abstract class RomanDigit +case object I extends RomanDigit +case object V extends RomanDigit +case object X extends RomanDigit +case object L extends RomanDigit +case object C extends RomanDigit +case object D extends RomanDigit +case object M extends RomanDigit + +type RomanNumeral = List[RomanDigit] -var counter = -1 - -def fresh(x: String) = { - counter += 1 - x ++ "_" ++ counter.toString() +def RomanNumeral2Int(rs: RomanNumeral): Int = rs match { + case Nil => 0 + case M::r => 1000 + RomanNumeral2Int(r) + case C::M::r => 900 + RomanNumeral2Int(r) + case D::r => 500 + RomanNumeral2Int(r) + case C::D::r => 400 + RomanNumeral2Int(r) + case C::r => 100 + RomanNumeral2Int(r) + case X::C::r => 90 + RomanNumeral2Int(r) + case L::r => 50 + RomanNumeral2Int(r) + case X::L::r => 40 + RomanNumeral2Int(r) + case X::r => 10 + RomanNumeral2Int(r) + case I::X::r => 9 + RomanNumeral2Int(r) + case V::r => 5 + RomanNumeral2Int(r) + case I::V::r => 4 + RomanNumeral2Int(r) + case I::r => 1 + RomanNumeral2Int(r) } -fresh("x") -fresh("x") - -// this can be avoided, but would have made my code more -// complicated +RomanNumeral2Int(List(I,I,I,I)) // 4 (invalid roman number) +RomanNumeral2Int(List(I,V)) // 4 +RomanNumeral2Int(List(V,I)) // 6 +RomanNumeral2Int(List(I,X)) // 9 +RomanNumeral2Int(List(M,C,M,L,X,X,I,X)) // 1979 +RomanNumeral2Int(List(M,M,X,V,I,I)) // 2017 // Tail recursion @@ -301,11 +320,15 @@ def ~ (r: String) = SEQ(s, r) } +//example regular expressions val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" val sign = "+" | "-" | "" val number = sign ~ digit ~ digit.% +//implement print_re + + // Lazyness with style //===================== diff -r 114a89518aea -r 4383809c176a testing2/knight1_test.sh --- a/testing2/knight1_test.sh Tue Nov 21 16:31:11 2017 +0000 +++ b/testing2/knight1_test.sh Thu Nov 23 10:56:47 2017 +0000 @@ -12,19 +12,27 @@ # compilation tests function scala_compile { - (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out) + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) } # functional tests -function scala_assert { - (ulimit -t 300 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +function scala_assert_slow { + (ulimit -t 120; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +function scala_assert_thirty { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +function scala_assert_quick { + (ulimit -t 10; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) } # purity test function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) + (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) } @@ -34,7 +42,7 @@ if (scala_vars knight1.scala) then - echo " --> fail" >> $out + echo " --> fail: if you do not fix this, you will receive a mark of zero" >> $out tsts0=$(( 1 )) else echo " --> success" >> $out @@ -64,11 +72,12 @@ if [ $tsts1 -eq 0 ] then - echo " is_legal(8, Nil) (3, 4) == true " >> $out - echo " is_legal(8, List((4, 1), (1, 0))) (4, 1) == false " >> $out - echo " is_legal(2, Nil) (0, 0) == true" >> $out + echo "Takes 10 seconds or less to execute: " >> $out + echo " is_legal(8, Nil)(3, 4) == true " >> $out + echo " is_legal(8, List((4, 1), (1, 0)))(4, 1) == false " >> $out + echo " is_legal(2, Nil)(0, 0) == true" >> $out - if (scala_assert "knight1.scala" "knight1a_test.scala") + if (scala_assert_quick "knight1.scala" "knight1a_test.scala") then echo " --> success" >> $out else @@ -80,6 +89,7 @@ if [ $tsts1 -eq 0 ] then + echo "Takes 10 seconds or less to execute: " >> $out echo " legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))" >> $out echo " legal_moves(8, Nil, (7,7)) == List((6,5), (5,6))" >> $out echo " legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))" >> $out @@ -88,7 +98,7 @@ echo " legal_moves(2, Nil, (0,0)) == Nil" >> $out echo " legal_moves(3, Nil, (0,0)) == List((1,2), (2,1))" >> $out - if (scala_assert "knight1.scala" "knight1b_test.scala") + if (scala_assert_quick "knight1.scala" "knight1b_test.scala") then echo " --> success" >> $out else @@ -101,7 +111,7 @@ if [ $tsts1 -eq 0 ] then - echo " all_tours from every position on the board" >> $out + echo " all_tours from every position on the board, in 2 minutes or less" >> $out echo " dim = 1: 1" >> $out echo " 2: 0,0,0,0" >> $out echo " 3: 0,0,0,0,0,0,0,0,0" >> $out @@ -109,7 +119,7 @@ echo " 5: 304,0,56,0,304,0,56,0,56,0,56,0,64,0,56,0,56,0,56,0,304,0,56,0,304" >> $out echo " enum_tours(5, List((0,2)) ) == 56 and all correct?" >> $out - if (scala_assert "knight1.scala" "knight1c_test.scala") + if (scala_assert_slow "knight1.scala" "knight1c_test.scala") then echo " --> success" >> $out else @@ -153,11 +163,12 @@ if [ $tsts1 -eq 0 ] then + echo "Takes 10 seconds or less to execute: " >> $out echo " Let f = (x:(Int, Int)) => if (x._1 > 3) Some(List(x)) else None " >> $out echo " first(List((1,0),(2,0),(3,0),(4,0)), f) == Some(List((4,0)))" >> $out echo " first(List((1,0),(2,0),(3,0)), f) == None" >> $out - if (scala_assert "knight2.scala" "knight2a_test.scala") + if (scala_assert_quick "knight2.scala" "knight2a_test.scala") then echo " --> success" >> $out else @@ -170,10 +181,11 @@ if [ $tsts1 -eq 0 ] then + echo "Takes 30 seconds or less to execute: " >> $out echo " is first_tour(8, List((0, 0))) ok? " >> $out echo " is first_tour(4, List((0, 0))) == None " >> $out - if (scala_assert "knight2.scala" "knight2b_test.scala") + if (scala_assert_thirty "knight2.scala" "knight2b_test.scala") then echo " --> success" >> $out else diff -r 114a89518aea -r 4383809c176a testing2/knight3_test.sh --- a/testing2/knight3_test.sh Tue Nov 21 16:31:11 2017 +0000 +++ b/testing2/knight3_test.sh Thu Nov 23 10:56:47 2017 +0000 @@ -15,19 +15,19 @@ # compilation tests function scala_compile { - (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out) + (ulimit -t 30 ; JAVA_OPTS="-Xmx1g" scala "$1" 2>> $out 1>> $out) } # functional tests function scala_assert { - (ulimit -t 300 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) + (ulimit -t 20 ; JAVA_OPTS="-Xmx1g" scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) } # purity test function scala_vars { - (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable' "$1" 2> /dev/null 1> /dev/null) + (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) } @@ -37,7 +37,7 @@ if (scala_vars knight3.scala) then - echo " --> fail" >> $out + echo " --> fail: if you do not fix this, you will receive a mark of zero" >> $out tsts0=$(( 1 )) else echo " --> success" >> $out @@ -66,6 +66,7 @@ if [ $tsts1 -eq 0 ] then + echo "Takes 20 seconds or less to execute: " >> $out echo " ordered_moves(8, List((3,4), (3,2)), (1, 3)) == List((0,1), (0,5), (2,1), (2,5))" >> $out echo " ordered_moves(8, List((4,0)), (0,0)) == List((2,1), (1,2))" >> $out echo " ordered_moves(8, List((0,4)), (0,0)) == List((1,2), (2,1))" >> $out @@ -97,6 +98,7 @@ if [ $tsts1 -eq 0 ] then + echo "Takes 20 seconds or less to execute: " >> $out echo " first_tour_heuristic(8, List((0,0))) found and ok?" >> $out echo " first_tour_heuristic(40, List((0,0))) found and ok?" >> $out diff -r 114a89518aea -r 4383809c176a testing3/bf.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/bf.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,177 @@ +// Part 2 about an Interpreter for the Brainf*** language +//======================================================== + +object CW8b { + +type Mem = Map[Int, Int] + +// (2a) Complete the functions for safely reading +// and writing brainf*** memory. Safely read should +// Return the value stored in the Map for a given memory +// pointer, if it exists; otherwise Returns 0. The +// writing function generates a new Map with the +// same data, except at the given memory pointer the +// a value v is stored. + + +def sread(mem: Mem, mp: Int) : Int = + mem.getOrElse(mp, 0) + +def write(mem: Mem, mp: Int, v: Int) : Mem = + mem.updated(mp, v) + + +// (2b) Implement the two jumping instructions in the +// brainf*** language. In jumpRight, given a program and +// a program counter move the program counter to the right +// until after the *matching* ]-command. Similarly, +// jumpLeft implements the move to the left to just after +// the *matching* [--command. + +def jumpRight(prog: String, pc: Int, level: Int) : Int = { + if (prog.length <= pc) pc + else (prog(pc), level) match { + case (']', 0) => pc + 1 + case (']', l) => jumpRight(prog, pc + 1, l - 1) + case ('[', l) => jumpRight(prog, pc + 1, l + 1) + case (_, l) => jumpRight(prog, pc + 1, l) + } +} + +def jumpLeft(prog: String, p: Int, level: Int) : Int = { + if (p < 0) p + else (prog(p), level) match { + case ('[', 0) => p + 1 + case ('[', l) => jumpLeft(prog, p - 1, l - 1) + case (']', l) => jumpLeft(prog, p - 1, l + 1) + case (_, l) => jumpLeft(prog, p - 1, l) + } +} + + +// (2c) Complete the run function that interpretes (runs) a brainf*** +// program: the arguments are a program, a program counter, +// a memory counter and a brainf*** memory. It Returns the +// memory at the stage when the excution of the brainf*** program +// finishes. The interpretation finishes once the program counter +// pc is pointing to something outside the program string. +// If the pc points to a character inside the program, the pc, +// memory pointer and memory need to be updated according to +// rules of the brainf*** language. Then, recursively, run +// function continues with the command at the new program +// counter. +// Implement the start function that calls run with the program +// counter and memory counter set to 0. + +def run(prog: String, pc: Int, mp: Int, mem: Mem) : Mem = { + if (0 <= pc && pc < prog.length) { + val (new_pc, new_mp, new_mem) = prog(pc) match { + case '>' => (pc + 1, mp + 1, mem) + case '<' => (pc + 1, mp - 1, mem) + case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) + case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) + case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } + case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) + case '[' => + if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) + case ']' => + if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) + case _ => (pc + 1, mp, mem) + } + run(prog, new_pc, new_mp, new_mem) + } + else mem +} + +def start(prog: String, m: Mem) = run(prog, 0, 0, m) + +// some sample programs collected from the Internet +//================================================== + + +/* +// first some contrived (small) programs + +// clears the 0-cell +start("[-]", Map(0 -> 100)) + +// copies content of the 0-cell to 1-cell +start("[->+<]", Map(0 -> 10)) + +// copies content of the 0-cell to 2-cell and 4-cell +start("[>>+>>+<<<<-]", Map(0 -> 42)) + + +// prints out numbers 0 to 9 +start("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""", Map()) + + +// some more "useful" programs + +// hello world program 1 +start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ + ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) + +// hello world program 2 +start("""++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>+ + +.<<+++++++++++++++.>.+++.------.--------.>+.>.""", Map()) + + +// draws the Sierpinski triangle +start("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ + ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< + ]>.>+[>>]>+]""", Map()) + +//fibonacci numbers below 100 +start("""+++++++++++ + >+>>>>++++++++++++++++++++++++++++++++++++++++++++ + >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> + +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- + <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< + -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] + >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ + +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ + ++++++++++++++++++++++++++++++++++++++++++++.[-]<< + <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", Map()) + + +//outputs the square numbers up to 10000 +start("""++++[>+++++<-]>[<+++++>-]+<+[ + >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ + >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] + <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""", Map()) + + +//collatz numbers (need to be typed in) +start(""">,[[----------[ + >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] + ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ + <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] + >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] + >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> + ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""", Map()) + + +// infinite collatz (never stops) +start(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< + <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ + +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< + [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> + [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ + <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ + ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< + +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- + ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- + >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> + -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ + +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< + <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ + +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< + <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- + [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""", Map()) + + +*/ + +} diff -r 114a89518aea -r 4383809c176a testing3/bf1a_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/bf1a_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,17 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + +lazy val f = Future { + import CW8b._ + + assert(sread(Map(), 2) == 0) + assert(sread(Map(2 -> 1), 2) == 1) + assert(write(Map(), 1, 2) == Map(1 -> 2)) + assert(write(Map(1 -> 0), 1, 2) == Map(1 -> 2)) +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/bf1b_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/bf1b_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,21 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + +lazy val f = Future { + import CW8b._ + + assert(jumpRight("[******]***", 1, 0) == 8) + assert(jumpRight("[**[*]*]***", 1, 0) == 8) + assert(jumpRight("[**[*]*]***", 1, 0) == 8) + assert(jumpRight("[**[***]***", 1, 0) == 11) + assert(jumpRight("[*[][]*]***", 1, 0) == 8) + assert(jumpLeft("[******]***", 6, 0) == 1) + assert(jumpLeft("[******]***", 7, 0) == -1) + assert(jumpLeft("[*[][]*]***", 6, 0) == 1) +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/bf1c_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/bf1c_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,19 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + +lazy val f = Future { + import CW8b._ + + assert(start("[-]", Map(0 -> 100)) == Map(0 -> 0)) + assert(start("[->+<]", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)) + assert(start("[>>+>>+<<<<-]", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)) + assert(start("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<] + <-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""", Map()) == Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87)) + +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/bf_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/bf_test.sh Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,120 @@ +#!/bin/bash +set -e + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback for your submission of CW 8, Part 2." >> $out +echo "" >> $out + + +# compilation tests + +function scala_compile { + (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out) +} + +# functional tests + +function scala_assert { + (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) +} + + +# var, return, ListBuffer test +# +echo "bf.scala does not contain vars, returns etc?" >> $out + +if (scala_vars bf.scala) +then + echo " --> fail" >> $out + tsts0=$(( 1 )) +else + echo " --> success" >> $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "bf.scala runs?" >> $out + + if (scala_compile bf.scala) + then + echo " --> success" >> $out + tsts1=$(( 0 )) + else + echo " --> scala bf.scala did not run successfully" >> $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " sread(Map(), 2) == 0" >> $out + echo " sread(Map(2 -> 1), 2) == 1" >> $out + echo " write(Map(), 1, 2) == Map(1 -> 2)" >> $out + echo " write(Map(1 -> 0), 1, 2) == Map(1 -> 2)" >> $out + + if (scala_assert "bf.scala" "bf1a_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " jumpRight(\"[******]***\", 1, 0) == 8" >> $out + echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out + echo " jumpRight(\"[**[*]*]***\", 1, 0) == 8" >> $out + echo " jumpRight(\"[**[***]***\", 1, 0) == 11" >> $out + echo " jumpRight(\"[*[][]*]***\", 1, 0) == 8" >> $out + echo " jumpLeft(\"[******]***\", 6, 0) == 1" >> $out + echo " jumpLeft(\"[******]***\", 7, 0) == -1" >> $out + echo " jumpLeft(\"[*[][]*]***\", 6, 0) == 1" >> $out + + if (scala_assert "bf.scala" "bf1b_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " start(\"[-]\", Map(0 -> 100)) == Map(0 -> 0)" >> $out + echo " start(\"[->+<]\", Map(0 -> 10)) == Map(0 -> 0, 1 -> 10)" >> $out + echo " start(\"[>>+>>+<<<<-]\", Map(0 -> 42)) == Map(0 -> 0, 2 -> 42, 4 -> 42)" >> $out + echo " start({{hello world prg 1}}, Map()) == " >> $out + echo " Map(0 -> 0, 5 -> 33, 1 -> 0, 6 -> 10, 2 -> 72, 3 -> 100, 4 -> 87)" >> $out + + if (scala_assert "bf.scala" "bf1c_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + + + diff -r 114a89518aea -r 4383809c176a testing3/mark --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/mark Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,8 @@ +#!/bin/sh +###set -e + +trap "exit" INT + +./re_test.sh output1 +./bf_test.sh output2 + diff -r 114a89518aea -r 4383809c176a testing3/re.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,159 @@ +// Part 1 about Regular Expression Matching +//========================================== + +object CW8a { + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp + +// some convenience for typing in regular expressions + +import scala.language.implicitConversions +import scala.language.reflectiveCalls + + +def charlist2rexp(s: List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + +implicit def RexpOps (r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps (s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +// (1a) Complete the function nullable according to +// the definition given in the coursework; this +// function checks whether a regular expression +// can match the empty string + +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true +} + +// (1b) Complete the function der according to +// the definition given in the coursework; this +// function calculates the derivative of a +// regular expression w.r.t. a character + +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) +} + +// (1c) Complete the function der according to +// the specification given in the coursework; this +// function simplifies a regular expression; +// however it does not simplify inside STAR-regular +// expressions + +def simp(r: Rexp) : Rexp = r match { + case ALT(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, r2s) => r2s + case (r1s, ZERO) => r1s + case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) + } + case SEQ(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, _) => ZERO + case (_, ZERO) => ZERO + case (ONE, r2s) => r2s + case (r1s, ONE) => r1s + case (r1s, r2s) => SEQ(r1s, r2s) + } + case r => r +} + +// (1d) Complete the two functions below; the first +// calculates the derivative w.r.t. a string; the second +// is the regular expression matcher taking a regular +// expression and a string and checks whether the +// string matches the regular expression + +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, simp(der(c, r))) +} + +// main matcher function +def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r)) + +// (1e) Complete the size function for regular +// expressions according to the specification +// given in the coursework. + +def size(r: Rexp): Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size (r2) + case SEQ(r1, r2) => 1 + size(r1) + size (r2) + case STAR(r1) => 1 + size(r1) +} + + + +// some testing data +/* +matcher(("a" ~ "b") ~ "c", "abc") // => true +matcher(("a" ~ "b") ~ "c", "ab") // => false + +// the supposedly 'evil' regular expression (a*)* b +val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +matcher(EVIL, "a" * 1000 ++ "b") // => true +matcher(EVIL, "a" * 1000) // => false + +// size without simplifications +size(der('a', der('a', EVIL))) // => 28 +size(der('a', der('a', der('a', EVIL)))) // => 58 + +// size with simplification +size(simp(der('a', der('a', EVIL)))) // => 8 +size(simp(der('a', der('a', der('a', EVIL))))) // => 8 + +// Java needs around 30 seconds for matching 28 a's with EVIL. +// +// Lets see how long it takes to match strings with +// 0.5 Million a's...it should be in the range of some +// seconds. + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + +for (i <- 0 to 5000000 by 500000) { + println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i)))) +} +*/ + +} diff -r 114a89518aea -r 4383809c176a testing3/re1a_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re1a_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,21 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + +lazy val f = Future { + import CW8a._ + + assert(nullable(ZERO) == false) + assert(nullable(ONE) == true) + assert(nullable(CHAR('a')) == false) + assert(nullable(ZERO | ONE) == true) + assert(nullable(ZERO | CHAR('a')) == false) + assert(nullable(ONE ~ ONE) == true) + assert(nullable(ONE ~ CHAR('a')) == false) + assert(nullable(STAR(ZERO)) == true) +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/re1b_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re1b_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,18 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + + +lazy val f = Future { + import CW8a._ + + assert(der('a', ZERO | ONE) == (ZERO | ZERO)) + assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)) + assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))) + assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))) +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/re1c_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re1c_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,21 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + + +lazy val f = Future { + import CW8a._ + + assert(simp(ZERO | ONE) == ONE) + assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)) + assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')) + assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO) + assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')) + assert(simp(CHAR('a') | CHAR('a')) == CHAR('a')) + assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a'))) +} + +Await.result(f, 30 second) diff -r 114a89518aea -r 4383809c176a testing3/re1d_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re1d_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,41 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + + + +lazy val f = Future { + import CW8a._ + + val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + + //println("1") + assert(ders(List.fill(5)('a'), EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))) + //println("2") + assert(ders(List('b'), EVIL_urban) == ONE) + //println("3") + assert(ders(List('b','b'), EVIL_urban) == ZERO) + //println("4") + assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true) + //println("5") + assert(matcher(EVIL_urban, "b") == true) + //println("6") + assert(matcher(EVIL_urban, "bb") == false) + //println("7") + assert(matcher("abc", "abc") == true) + //println("8") + assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true) + //println("9") + assert(matcher(ONE, "") == true) + //println("10") + assert(matcher(ZERO, "") == false) + //println("11") + assert(matcher(ONE | CHAR('a'), "") == true) + //println("12") + assert(matcher(ONE | CHAR('a'), "a") == true) +} + +Await.result(f, 90 second) diff -r 114a89518aea -r 4383809c176a testing3/re1e_test.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re1e_test.scala Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,19 @@ + +import scala.concurrent._ +import scala.concurrent.duration._ +import ExecutionContext.Implicits.global +import scala.language.postfixOps +import scala.language.reflectiveCalls + +lazy val f = Future { + import CW8a._ + + val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + + assert(size(der('a', der('a', EVIL_urban))) == 28) + assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58) + + assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8) +} + +Await.result(f, 120 second) diff -r 114a89518aea -r 4383809c176a testing3/re_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/testing3/re_test.sh Thu Nov 23 10:56:47 2017 +0000 @@ -0,0 +1,161 @@ +#!/bin/bash +set -e + +out=${1:-output} + +echo "" > $out + +echo "Below is the feedback for your submission of CW 8, Part 1." >> $out +echo "" >> $out + + +# compilation tests + +function scala_compile { + (ulimit -t 30 -m 1024000 ; scala "$1" 2>> $out 1>> $out) +} + +# functional tests + +function scala_assert { + (ulimit -t 30 -m 1024000 ; scala -i "$1" "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par|ListBuffer|mutable|new Array' "$1" 2> /dev/null 1> /dev/null) +} + + +# var, return, ListBuffer test +# +echo "re.scala does not contain vars, returns etc?" >> $out + +if (scala_vars re.scala) +then + echo " --> fail" >> $out + tsts0=$(( 1 )) +else + echo " --> yes" >> $out + tsts0=$(( 0 )) +fi + + +# compilation test +if [ $tsts0 -eq 0 ] +then + echo "re.scala runs?" >> $out + + if (scala_compile re.scala) + then + echo " --> yes" >> $out + tsts1=$(( 0 )) + else + echo " --> scala re.scala did not run successfully" >> $out + tsts1=$(( 1 )) + fi +else + tsts1=$(( 1 )) +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " nullable(ZERO) == false" >> $out + echo " nullable(ONE) == true" >> $out + echo " nullable(CHAR('a')) == false" >> $out + echo " nullable(ZERO | ONE) == true" >> $out + echo " nullable(ZERO | CHAR('a')) == false" >> $out + echo " nullable(ONE ~ ONE) == true" >> $out + echo " nullable(ONE ~ CHAR('a')) == false" >> $out + echo " nullable(STAR(ZERO)) == true" >> $out + + if (scala_assert "re.scala" "re1a_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " der('a', ZERO | ONE) == (ZERO | ZERO)" >> $out + echo " der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)" >> $out + echo " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" >> $out + echo " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" >> $out + + if (scala_assert "re.scala" "re1b_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + + +if [ $tsts1 -eq 0 ] +then + echo " simp(ZERO | ONE) == ONE" >> $out + echo " simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)" >> $out + echo " simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')" >> $out + echo " simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO" >> $out + echo " simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')" >> $out + echo " simp(CHAR('a') | CHAR('a')) == CHAR('a')" >> $out + echo " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" >> $out + + if (scala_assert "re.scala" "re1c_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + +if [ $tsts1 -eq 0 ] +then + echo " let EVIL = (a*)* b" >> $out + echo " ders(List.fill(5)('a'),EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" >> $out + echo " ders(List('b'),EVIL) == ONE" >> $out + echo " ders(List('b','b'),EVIL) == ZERO" >> $out + echo " matcher(EVIL, \"a\" * 5 ++ \"b\") == true" >> $out + echo " matcher(EVIL, \"b\") == true" >> $out + echo " matcher(EVIL, \"bb\") == false" >> $out + echo " matcher(\"abc\", \"abc\") == true" >> $out + echo " matcher((\"ab\" | \"a\") ~ (ONE | \"bc\"), \"abc\") == true" >> $out + echo " matcher(ONE, \"\") == true" >> $out + echo " matcher(ZERO, \"\") == false" >> $out + echo " matcher(ONE | CHAR('a'), \"\") == true" >> $out + echo " matcher(ONE | CHAR('a'), \"a\") == true" >> $out + + if (scala_assert "re.scala" "re1d_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + + +if [ $tsts1 -eq 0 ] +then + echo " let EVIL = (a*)* b" >> $out + echo " size(der('a', der('a', EVIL))) == 28" >> $out + echo " size(der('a', der('a', der('a', EVIL)))) == 58" >> $out + echo " size(ders(\"aaaaaa\".toList, EVIL)) == 8" >> $out + + if (scala_assert "re.scala" "re1e_test.scala") + then + echo " --> success" >> $out + else + echo " --> test failed" >> $out + fi +fi + +