# HG changeset patch # User Christian Urban # Date 1482289578 0 # Node ID ae4708c851ee063a15122894d4593d7128854ec5 # Parent 21f41e08457d6bcb6cc7b62b320d051ef3b7874f updated diff -r 21f41e08457d -r ae4708c851ee cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 21f41e08457d -r ae4708c851ee cws/cw03.tex --- 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 diff -r 21f41e08457d -r ae4708c851ee marking/mark03b --- 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 diff -r 21f41e08457d -r ae4708c851ee marking/re2a_test.scala --- /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) diff -r 21f41e08457d -r ae4708c851ee marking/re2b_test.scala --- /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) diff -r 21f41e08457d -r ae4708c851ee marking/re2c_test.scala --- /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)