--- 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

Binary file cws/cw03.pdf has changed

--- 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}
 
 

--- 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
 //=====================

--- 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

--- 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
   

--- /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())
+
+
+*/ 
+
+}

--- /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)

--- /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)

--- /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)

--- /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
+
+
+
+

--- /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
+

--- /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))))
+}
+*/
+
+}

--- /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)

--- /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)

--- /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)

--- /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)

--- /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)

--- /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
+
+