Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Wed Dec 21 01:19:25 2016 +0000
+++ b/cws/cw03.tex Wed Dec 21 03:06:18 2016 +0000
@@ -327,18 +327,17 @@
\end{itemize}\bigskip
+\subsection*{Background}
-\noindent
-\textbf{Background} Although easily implementable in Scala, the idea
-behind the derivative 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 that can match all the strings $cs$. In other
-words, the regular 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.
+Although easily implementable in Scala, the idea behind the derivative
+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
+that can match all the strings $cs$. In other words, the regular
+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
--- a/marking/mark03b Wed Dec 21 01:19:25 2016 +0000
+++ b/marking/mark03b Wed Dec 21 03:06:18 2016 +0000
@@ -38,7 +38,7 @@
#
echo "re2.scala does not contain vars, returns etc?" | tee -a $out
-if (scala_vars re.scala)
+if (scala_vars re2.scala)
then
echo " --> fail" | tee -a $out
tsts0=$(( 1 ))
@@ -65,20 +65,48 @@
tsts1=$(( 1 ))
fi
-#if [ $tsts1 -eq 0 ]
-#then
-# echo " nullable(ZERO) == false" | tee -a $out
-# echo " nullable(ONE) == true" | tee -a $out
-#
-# if (scala_assert "re.scala.bak" "../../../marking/re1a_test.scala")
-# then
-# echo " --> success" | tee -a $out
-# marks=$(( marks + 1 ))
-# else
-# echo " --> test failed" | tee -a $out
-# fi
-#fi
+if [ $tsts1 -eq 0 ]
+then
+ echo " iterT(200000, (x: Int) => x + 1, 0) == 200000" | tee -a $out
+ echo " iterT(100, (x: BigInt) => x * 2, BigInt(2)) == BigInt(\"2535301200456458802993406410752\")" | tee -a $out
+ echo " iterT(10, (x: String) => x ++ \"a\", \"a\") == \"aaaaaaaaaaa\"" | tee -a $out
+
+ if (scala_assert "re2.scala" "../../../marking/re2a_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 2 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+if [ $tsts1 -eq 0 ]
+then
+ echo " size(iterT(20, (r: Rexp) => der('a', r), EVIL)) == 7340068" | tee -a $out
+ echo " size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) == 8" | tee -a $out
+
+ if (scala_assert "re2.scala" "../../../marking/re2b_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
+
+if [ $tsts1 -eq 0 ]
+then
+ echo " fixpT((x:Int) => if (200000 < x) x else x + 1, 0) == 200001" | tee -a $out
+ echo " fixpT((x:Long) => if (20 < x) x else x + 1, 0L) == 21L" | tee -a $out
+
+ if (scala_assert "re2.scala" "../../../marking/re2c_test.scala")
+ then
+ echo " --> success" | tee -a $out
+ marks=$(( marks + 1 ))
+ else
+ echo " --> test failed" | tee -a $out
+ fi
+fi
## final marks
echo "Overall mark for CW 8, Part 2" | tee -a $out
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/re2a_test.scala Wed Dec 21 03:06:18 2016 +0000
@@ -0,0 +1,14 @@
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+
+
+lazy val f = Future {
+ assert(iterT(200000, (x: Int) => x + 1, 0) == 200000)
+ assert(iterT(100, (x: BigInt) => x * 2, BigInt(2)) == BigInt("2535301200456458802993406410752"))
+ assert(iterT(10, (x: String) => x ++ "a", "a") == "aaaaaaaaaaa")
+}
+
+Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/re2b_test.scala Wed Dec 21 03:06:18 2016 +0000
@@ -0,0 +1,50 @@
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
+
+def nullable_urban (r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable_urban(r1) || nullable_urban(r2)
+ case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2)
+ case STAR(_) => true
+}
+
+def der_urban (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_urban(c, r1), der_urban(c, r2))
+ case SEQ(r1, r2) =>
+ if (nullable(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2))
+ else SEQ(der_urban(c, r1), r2)
+ case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1))
+}
+
+def simp_urban(r: Rexp) : Rexp = r match {
+ case ALT(r1, r2) => (simp_urban(r1), simp_urban(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_urban(r1), simp_urban(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
+}
+
+
+lazy val f = Future {
+ assert(size(iterT(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068)
+ assert(size(iterT(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8)
+}
+
+Await.result(f, 120 second)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/marking/re2c_test.scala Wed Dec 21 03:06:18 2016 +0000
@@ -0,0 +1,13 @@
+import scala.concurrent._
+import scala.concurrent.duration._
+import ExecutionContext.Implicits.global
+import scala.language.postfixOps
+
+
+
+lazy val f = Future {
+ assert(fixpT((x:Int) => if (200000 < x) x else x + 1, 0) == 200001)
+ assert(fixpT((x:Long) => if (20 < x) x else x + 1, 0L) == 21L)
+}
+
+Await.result(f, 120 second)