diff -r d5776c6018f0 -r 39b7ff2cf1bc progs/cw1.scala
--- a/progs/cw1.scala	Wed May 10 17:03:21 2017 +0100
+++ b/progs/cw1.scala	Sun May 21 00:43:02 2017 +0100
@@ -1,137 +1,90 @@
+// CW 1
 import scala.language.implicitConversions    
 import scala.language.reflectiveCalls 
 
-abstract class Rexp {
-  def simp : Rexp = this
-}
+abstract class Rexp
+case object ZERO extends Rexp                            // matches nothing
+case object ONE extends Rexp                             // matches the empty string
+case class CHAR(c: Char) extends Rexp                    // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp          // alternative
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp          // sequence
+case class STAR(r: Rexp) extends Rexp                    // star
+case class RANGE(cs: Set[Char]) extends Rexp             // set of characters
+case class PLUS(r: Rexp) extends Rexp                    // plus
+case class OPT(r: Rexp) extends Rexp                     // optional
+case class NTIMES(r: Rexp, n: Int) extends Rexp          // n-times
+case class UPNTIMES(r: Rexp, n: Int) extends Rexp        // up n-times
+case class FROMNTIMES(r: Rexp, n: Int) extends Rexp      // from n-times
+case class NMTIMES(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times
+case class NOT(r: Rexp) extends Rexp                     // not
+case class CFUN(f: Char => Boolean) extends Rexp         // subsuming CHAR and RANGE
 
-case object NULL extends Rexp
-case object EMPTY extends Rexp
-case class CHAR(c: Char) extends Rexp
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp {
-  override def toString = r1.toString + " | " + r2.toString
-  override def simp = (r1.simp, r2.simp) match {
-    case (NULL, r) => r
-    case (r, NULL) => r
-    case (r, EMPTY) => if (nullable(r)) r else ALT(r, EMPTY)
-    case (EMPTY, r) => if (nullable(r)) r else ALT(r, EMPTY)
-    case (r1, r2) => if (r1 == r2) r1 else ALT(r1, r2)
-  }
-}
-case class RANGE(cs: List[Char]) extends Rexp {
-  //override def toString = cs.mkString("[",",","]")
-  override def toString = "[" + cs.head + " .. " + cs.last + "]"
-}
-object RANGE {
-  def apply(s: String) : RANGE = RANGE(s.toList)
-}
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp {
-  override def toString = r1.toString + " ~ " + r2.toString
-  override def simp = (r1.simp, r2.simp) match {
-    case (NULL, _) => NULL
-    case (_, NULL) => NULL
-    case (EMPTY, r) => r
-    case (r, EMPTY) => r
-    case (r1, r2) => SEQ(r1, r2)
-  }
-}
-case class PLUS(r: Rexp) extends Rexp {
-  override def simp = r.simp match {
-    case NULL => EMPTY
-    case EMPTY => EMPTY
-    case r => PLUS(r)
-  }
-}
-case class STAR(r: Rexp) extends Rexp {
-  override def simp = r.simp match {
-    case NULL => EMPTY
-    case EMPTY => EMPTY
-    case r => STAR(r)
-  }
-}
-case class NTIMES(r: Rexp, n: Int) extends Rexp {
-  override def simp = if (n == 0) EMPTY else 
-    r.simp match {
-      case NULL => NULL
-      case EMPTY => EMPTY
-      case r => NTIMES(r, n)
-    }
-}
-case class NUPTOM(r: Rexp, n: Int, m: Int) extends Rexp {
-  override def simp = if (m == 0) EMPTY else 
-    r.simp match {
-      case NULL => NULL
-      case EMPTY => EMPTY
-      case r => NUPTOM(r, n, m)
-    }
-}
-def NMTIMES(r: Rexp, n: Int, m: Int) = {
-  if(m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")
-  else NUPTOM(r, n, m - n)
-}
-
-
-case class NOT(r: Rexp) extends Rexp {
-  override def simp = NOT(r.simp)
-}
-case class OPT(r: Rexp) extends Rexp {
-  override def simp = OPT(r.simp)
-}
 
 // nullable function: tests whether the regular 
 // expression can recognise the empty string
 def nullable (r: Rexp) : Boolean = r match {
-  case NULL => false
-  case EMPTY => true
+  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
+  case RANGE(_) => false
   case PLUS(r) => nullable(r)
-  case NTIMES(r, i) => if (i == 0) true else nullable(r)
-  case NUPTOM(r, i, j) => if (i == 0) true else nullable(r)
-  case RANGE(_) => false
-  case NOT(r) => !(nullable(r))
   case OPT(_) => true
-}
-
-def zeroable (r: Rexp) : Boolean = r match {
-  case NULL => true
-  case EMPTY => false
-  case CHAR(_) => false
-  case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
-  case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
-  case STAR(_) => false
-  case PLUS(r) => zeroable(r)
-  case NTIMES(r, i) => if (i == 0) false else zeroable(r)
-  case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r)
-  case RANGE(_) => false
-  case NOT(r) => !(zeroable(r))
-  case OPT(_) => false
+  case NTIMES(r, n) => if (n == 0) true else nullable(r)
+  case UPNTIMES(_, _) => true
+  case FROMNTIMES(r, n) => if (n == 0) true else nullable(r)
+  case NMTIMES(r, n, m) => if (n == 0) true else nullable(r)
+  case NOT(r) => !(nullable(r))
+  case CFUN(_) => false
 }
 
 // derivative of a regular expression w.r.t. a character
 def der (c: Char, r: Rexp) : Rexp = r match {
-  case NULL => NULL
-  case EMPTY => NULL
-  case CHAR(d) => if (c == d) EMPTY else NULL
+  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(r) => SEQ(der(c, r), STAR(r))
+  case RANGE(cs) => if (cs contains c) ONE else ZERO
   case PLUS(r) => SEQ(der(c, r), STAR(r))
-  case NTIMES(r, i) => 
-    if (i == 0) NULL else der(c, SEQ(r, NTIMES(r, i - 1)))
-  case NUPTOM(r, i, j) =>
-    if (i == 0 && j == 0) NULL else 
-    if (i == 0) ALT(der(c, NTIMES(r, j)), der(c, NUPTOM(r, 0, j - 1)))
-    else der(c, SEQ(r, NUPTOM(r, i - 1, j)))
-  case RANGE(cs) => if (cs contains c) EMPTY else NULL
+  case OPT(r) => der(c, r)
+  case NTIMES(r, n) => 
+    if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
+  case UPNTIMES(r, n) =>
+    if (n == 0) ZERO else SEQ(der(c, r), UPNTIMES(r, n - 1))
+  case FROMNTIMES(r, n) =>
+    if (n == 0) ZERO else SEQ(der(c, r), FROMNTIMES(r, n - 1))
+  case NMTIMES(r, n, m) =>
+    if (m < n) ZERO else
+    if (n == 0 && m == 0) ZERO else 
+    if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1)) 
+    else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1)) 
   case NOT(r) => NOT(der (c, r))
-  case OPT(r) => der(c, r)
+  case CFUN(f) => if (f(c)) ONE else ZERO
 }
 
+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
+}
+
+
 // derivative w.r.t. a string (iterates der)
 def ders (s: List[Char], r: Rexp) : Rexp = s match {
   case Nil => r
@@ -140,15 +93,18 @@
 
 def ders_simp (s: List[Char], r: Rexp) : Rexp = s match {
   case Nil => r
-  case c::s => ders_simp(s, der(c, r).simp)
+  case c::s => ders_simp(s, simp(der(c, r)))
 }
 
-// main matcher function
-def matcher(r: Rexp, s: String) : Boolean = nullable(ders_simp(s.toList, r))
+// main matcher function including simplification
+def matcher(r: Rexp, s: String) : Boolean = 
+  nullable(ders_simp(s.toList, r))
+
+
 
 // some convenience for typing in regular expressions
 def charlist2rexp(s : List[Char]) : Rexp = s match {
-  case Nil => EMPTY
+  case Nil => ONE
   case c::Nil => CHAR(c)
   case c::s => SEQ(CHAR(c), charlist2rexp(s))
 }
@@ -168,12 +124,29 @@
   def ~ (r: String) = SEQ(s, r)
 }
 
+val r1 = NTIMES("a", 3)
+val r2 = NTIMES(OPT("a"), 3)
+val r3 = UPNTIMES("a", 3)
+val r4 = UPNTIMES(OPT("a"), 3)
+val r5 = NMTIMES("a", 3, 5)
+val r6 = NMTIMES(OPT("a"), 3, 5)
+
+val rs = List(r1, r2, r3, r4, r5, r6)
+
+rs.map(matcher(_, ""))
+rs.map(matcher(_, "a"))
+rs.map(matcher(_, "aa"))
+rs.map(matcher(_, "aaa"))
+rs.map(matcher(_, "aaaa"))
+rs.map(matcher(_, "aaaaa"))
+rs.map(matcher(_, "aaaaaa"))
+
 println("EMAIL:")
-val LOWERCASE = "abcdefghijklmnopqrstuvwxyz"
-val DIGITS = "0123456789"
-val EMAIL = PLUS(RANGE(LOWERCASE + DIGITS + "_" + "." + "-")) ~ "@" ~ 
-            PLUS(RANGE(LOWERCASE + DIGITS + "." + "-")) ~ "." ~
-            NMTIMES(RANGE(LOWERCASE + "."), 2, 6)
+val LOWERCASE = ('a' to 'z').toSet
+val DIGITS = ('0' to '9').toSet
+val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | ("_.-").toSet)) ~ "@" ~ 
+              PLUS(CFUN(LOWERCASE | DIGITS | (".-").toSet)) ~ "." ~
+              NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6) }
 
 val my_email = "christian.urban@kcl.ac.uk"
 
@@ -182,7 +155,7 @@
 println(ders_simp(my_email.toList, EMAIL))
 
 println("COMMENTS:")
-val ALL = RANGE(LOWERCASE + " ")
+val ALL = CFUN((c:Char) => true)
 val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ "*/"
 
 println(matcher(COMMENT, "/**/"))