diff -r c9027db225cc -r 6a43ea9305ba progs/scala/re.scala
--- a/progs/scala/re.scala	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/scala/re.scala	Sat Mar 19 23:27:29 2016 +0000
@@ -3,8 +3,8 @@
 import scala.annotation.tailrec   
 
 abstract class Rexp 
-case object NULL extends Rexp
-case object EMPTY extends 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 
@@ -12,7 +12,7 @@
 case class RECD(x: String, r: Rexp) extends Rexp
 
 abstract class Val
-case object Void extends Val
+case object Empty extends Val
 case class Chr(c: Char) extends Val
 case class Sequ(v1: Val, v2: Val) extends Val
 case class Left(v: Val) extends Val
@@ -22,7 +22,7 @@
    
 // 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))
 }
@@ -44,8 +44,8 @@
 }
 
 def pretty(r: Rexp) : String = r match {
-  case NULL => "0"
-  case EMPTY => "e"
+  case ZERO => "0"
+  case ONE => "e"
   case CHAR(c) => c.toString 
   case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")"
   case SEQ(r1, r2) => pretty(r1) ++ pretty(r2)
@@ -54,7 +54,7 @@
 }
 
 def vpretty(v: Val) : String = v match {
-  case Void => "()"
+  case Empty => "()"
   case Chr(c) => c.toString
   case Left(v) => "Left(" ++ vpretty(v) ++ ")"
   case Right(v) => "Right(" ++ vpretty(v) ++ ")"
@@ -66,8 +66,8 @@
 
 // size of a regular expressions - for testing purposes 
 def size(r: Rexp) : Int = r match {
-  case NULL => 1
-  case EMPTY => 1
+  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)
@@ -77,21 +77,21 @@
 
 // extracts a set of candidate values from a "non-starred" regular expression
 def values(r: Rexp) : Set[Val] = r match {
-  case NULL => Set()
-  case EMPTY => Set(Void)
+  case ZERO => Set()
+  case ONE => Set(Empty)
   case CHAR(c) => Set(Chr(c))
   case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ 
                       (for (v2 <- values(r2)) yield Right(v2))
   case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)
-  case STAR(r) => Set(Void) ++ values(r)   // to do more would cause the set to be infinite
+  case STAR(r) => Set(Empty) ++ values(r)   // to do more would cause the set to be infinite
   case RECD(_, r) => values(r)
 }
 
 // zeroable function: tests whether the regular 
 // expression cannot regognise any string
 def zeroable (r: Rexp) : Boolean = r match {
-  case NULL => true
-  case EMPTY => false
+  case ZERO => true
+  case ONE => false
   case CHAR(_) => false
   case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
   case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
@@ -103,8 +103,8 @@
 // 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)
@@ -114,9 +114,9 @@
 
 // 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))
@@ -133,7 +133,7 @@
 
 // extracts a string from value
 def flatten(v: Val) : String = v match {
-  case Void => ""
+  case Empty => ""
   case Chr(c) => c.toString
   case Left(v) => flatten(v)
   case Right(v) => flatten(v)
@@ -143,7 +143,7 @@
 }
 
 def flattens(v: Val) : List[String] = v match {
-  case Void => List("")
+  case Empty => List("")
   case Chr(c) => List(c.toString)
   case Left(v) => flattens(v)
   case Right(v) => flattens(v)
@@ -155,7 +155,7 @@
 
 // extracts an environment from a value
 def env(v: Val) : List[(String, String)] = v match {
-  case Void => Nil
+  case Empty => Nil
   case Chr(c) => Nil
   case Left(v) => env(v)
   case Right(v) => env(v)
@@ -166,7 +166,7 @@
 
 // injection part
 def mkeps(r: Rexp) : Val = r match {
-  case EMPTY => Void
+  case ONE => Empty
   case ALT(r1, r2) => 
     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
@@ -182,7 +182,7 @@
   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
-  case (CHAR(d), Void) => Chr(c) 
+  case (CHAR(d), Empty) => Chr(c) 
   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
 }
 
@@ -207,8 +207,8 @@
 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
   case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
 }
-def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))
-def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))
+def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Empty), f2(v))
+def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Empty))
 def F_RECD(f: Val => Val) = (v:Val) => v match {
   case Rec(x, v) => Rec(x, f(v))
 }
@@ -221,8 +221,8 @@
     val (r1s, f1s) = simp(r1)
     val (r2s, f2s) = simp(r2)
     (r1s, r2s) match {
-      case (NULL, _) => (r2s, F_RIGHT(f2s))
-      case (_, NULL) => (r1s, F_LEFT(f1s))
+      case (ZERO, _) => (r2s, F_RIGHT(f2s))
+      case (_, ZERO) => (r1s, F_LEFT(f1s))
       case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
                 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) 
     }
@@ -231,10 +231,10 @@
     val (r1s, f1s) = simp(r1)
     val (r2s, f2s) = simp(r2)
     (r1s, r2s) match {
-      case (NULL, _) => (NULL, F_ERROR)
-      case (_, NULL) => (NULL, F_ERROR)
-      case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))
-      case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))
+      case (ZERO, _) => (ZERO, F_ERROR)
+      case (_, ZERO) => (ZERO, F_ERROR)
+      case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
+      case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
       case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
     }
   }
@@ -260,7 +260,7 @@
 
 // enumerates regular expressions until a certain depth
 def enum(n: Int, s: String) : Set[Rexp] = n match {
-  case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR)
+  case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR)
   case n => {
     val rs = enum(n - 1, s)
     rs ++
@@ -270,7 +270,7 @@
 }
 
 def ordr(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match {
-  case (Void, EMPTY, Void) => true
+  case (Empty, ONE, Empty) => true
   case (Chr(c1), CHAR(c2), Chr(c3)) if (c1 == c2 && c1 == c3) => true
   case (Left(v1), ALT(r1, r2), Left(v2)) => ordr(v1, r1, v2)
   case (Right(v1), ALT(r1, r2), Right(v2)) => ordr(v1, r2, v2)
@@ -282,7 +282,7 @@
 }     
 
 def ord(v1: Val, v2: Val) : Boolean = (v1, v2) match {
-  case (Void, Void) => true
+  case (Empty, Empty) => true
   case (Chr(c1), Chr(c2)) if (c1 == c2) => true
   case (Left(v1), Left(v2)) => ord(v1, v2)
   case (Right(v1), Right(v2)) => ord(v1, v2)
@@ -559,7 +559,7 @@
 }
 
 
-val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
+val a0 = (ONE | "a") ~ (ONE | "ab")
 val a1 = der('a', a0)
 pretty(a1)
 val m = mkeps(a1)
@@ -567,7 +567,7 @@
 val v = inj(a0, 'a', m)
 vpretty(v)
 
-val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
+val a0 = (ONE | "a") ~ (ONE | "ab")
 val a1 = der('a', a0)
 pretty(a1)
 values(a1).toList