# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1458430049 0
# Node ID 6a43ea9305ba0150e55df7b8c5b9381ed2ed31c0
# Parent  c9027db225ccb8658b970a29b8ff537aabc53fc2
updated implementations

diff -r c9027db225cc -r 6a43ea9305ba progs/fsharp/README
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/fsharp/README	Sat Mar 19 23:27:29 2016 +0000
@@ -0,0 +1,4 @@
+
+call with
+
+fsharpi re.ml
\ No newline at end of file
diff -r c9027db225cc -r 6a43ea9305ba progs/fsharp/re.ml
--- a/progs/fsharp/re.ml	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/fsharp/re.ml	Sat Mar 19 23:27:29 2016 +0000
@@ -1,7 +1,7 @@
 
 type rexp =
-   NULL 
- | EMPTY 
+   ZERO 
+ | ONE 
  | CHAR of char
  | ALT of rexp * rexp
  | SEQ of rexp * rexp 
@@ -9,7 +9,7 @@
  | RECD of string * rexp;;
 
 type value =
-   Void
+   Empty
  | Chr of char
  | Sequ of value * value
  | Left of value
@@ -24,7 +24,7 @@
 
 (* some helper functions for rexps *)
 let rec seq s = match s with
-  | [] -> EMPTY
+  | [] -> ONE
   | [c] -> CHAR(c)
   | c::cs -> SEQ(CHAR(c), seq cs);;
 
@@ -41,15 +41,15 @@
 let ($) x r = RECD(x, r);;
 
 let alts rs = match rs with 
-  | [] -> NULL
+  | [] -> ZERO
   | [r] -> r
   | r::rs -> List.fold (++) r rs;;
 
 
 (* size of a regular expressions - for testing purposes *)
 let rec size r = match r with
-  | NULL -> 1
-  | EMPTY -> 1
+  | ZERO -> 1
+  | ONE -> 1
   | CHAR(_) -> 1
   | ALT(r1, r2) -> 1 + (size r1) + (size r2)
   | SEQ(r1, r2) -> 1 + (size r1) + (size r2)
@@ -59,8 +59,8 @@
 (* nullable function: tests whether the regular 
    expression can recognise the empty string *)
 let rec nullable r = match r with
-  | NULL -> false
-  | EMPTY -> true
+  | ZERO -> false
+  | ONE -> true
   | CHAR(_) -> false
   | ALT(r1, r2) -> nullable(r1) || nullable(r2)
   | SEQ(r1, r2) -> nullable(r1) && nullable(r2)
@@ -69,9 +69,9 @@
 
 (* derivative of a regular expression r w.r.t. a character c *)
 let rec der c r = match r with 
-  | NULL -> NULL
-  | EMPTY -> NULL
-  | CHAR(d) -> if c = d then EMPTY else NULL
+  | ZERO -> ZERO
+  | ONE -> ZERO
+  | CHAR(d) -> if c = d then ONE else ZERO
   | ALT(r1, r2) -> ALT(der c r1, der c r2)
   | SEQ(r1, r2) -> 
       if nullable r1 then ALT(SEQ(der c r1, r2), der c r2)
@@ -86,7 +86,7 @@
 
 (* extracts a string from value *)
 let rec flatten v = match v with 
-  | Void -> ""
+  | Empty -> ""
   | Chr(c) -> System.Convert.ToString(c)
   | Left(v) -> flatten v
   | Right(v) -> flatten v
@@ -97,7 +97,7 @@
 
 (* extracts an environment from a value *)
 let rec env v = match v with
-  | Void -> []
+  | Empty -> []
   | Chr(c) -> []
   | Left(v) -> env v
   | Right(v) -> env v
@@ -111,7 +111,7 @@
 
 (* the value for a nullable rexp *)
 let rec mkeps r = match r with
-  | EMPTY -> Void
+  | ONE -> Empty
   | ALT(r1, r2) -> 
       if nullable r1 then Left(mkeps r1) else Right(mkeps r2)
   | SEQ(r1, r2) -> Sequ(mkeps r1, mkeps r2)
@@ -127,7 +127,7 @@
   | SEQ(r1, r2), Right(v2) -> Sequ(mkeps r1, inj r2 c v2)
   | ALT(r1, r2), Left(v1) -> Left(inj r1 c v1)
   | ALT(r1, r2), Right(v2) -> Right(inj r2 c v2)
-  | CHAR(d), Void -> Chr(d) 
+  | CHAR(d), Empty -> Chr(d) 
   | RECD(x, r1), _ -> Rec(x, inj r1 c v);;
 
 (* some "rectification" functions for simplification *)
@@ -139,8 +139,8 @@
   | Left(v) -> Left(f1 v);;
 let f_seq f1 f2 = fun v -> match v with 
   Sequ(v1, v2) -> Sequ(f1 v1, f2 v2);;
-let f_seq_Void1 f1 f2 = fun v -> Sequ(f1 Void, f2 v);;
-let f_seq_Void2 f1 f2 = fun v -> Sequ(f1 v, f2 Void);;
+let f_seq_Empty1 f1 f2 = fun v -> Sequ(f1 Empty, f2 v);;
+let f_seq_Empty2 f1 f2 = fun v -> Sequ(f1 v, f2 Empty);;
 let f_rec f = fun v -> match v with
     Rec(x, v) -> Rec(x, f v);;
 
@@ -151,18 +151,18 @@
       let (r1s, f1s) = simp r1 in 
       let (r2s, f2s) = simp r2 in
       (match r1s, r2s with
-          NULL, _ -> (r2s, f_right f2s)
-        | _, NULL -> (r1s, f_left f1s)
+          ZERO, _ -> (r2s, f_right f2s)
+        | _, ZERO -> (r1s, f_left f1s)
         | _, _    -> if r1s = r2s then (r1s, f_left f1s)
                      else (ALT (r1s, r2s), f_alt f1s f2s)) 
   | SEQ(r1, r2) -> 
       let (r1s, f1s) = simp r1 in
       let (r2s, f2s) = simp r2 in
       (match r1s, r2s with
-          NULL, _  -> (NULL, f_right f2s)
-        | _, NULL  -> (NULL, f_left f1s)
-        | EMPTY, _ -> (r2s, f_seq_Void1 f1s f2s)
-        | _, EMPTY -> (r1s, f_seq_Void2 f1s f2s)
+          ZERO, _  -> (ZERO, f_right f2s)
+        | _, ZERO  -> (ZERO, f_left f1s)
+        | ONE, _ -> (r2s, f_seq_Empty1 f1s f2s)
+        | _, ONE -> (r1s, f_seq_Empty2 f1s f2s)
         | _, _     -> (SEQ(r1s, r2s), f_seq f1s f2s))
   | RECD(x, r1) -> 
       let (r1s, f1s) = simp r1 in
diff -r c9027db225cc -r 6a43ea9305ba progs/haskell/re.hs
--- a/progs/haskell/re.hs	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/haskell/re.hs	Sat Mar 19 23:27:29 2016 +0000
@@ -22,8 +22,8 @@
     return ()
 
 data Rexp =
-   NULL 
- | EMPTY 
+   ZERO 
+ | ONE 
  | CHAR Char
  | ALT Rexp Rexp
  | SEQ Rexp Rexp 
@@ -31,7 +31,7 @@
  | RECD String Rexp deriving (Eq, Show) 
 
 data Value =
-   Void
+   Empty
  | Chr Char
  | Sequ Value Value
  | Lf Value
@@ -44,7 +44,7 @@
 
 sequ :: [Char] -> Rexp
 sequ s = case s of
-  [] -> EMPTY
+  [] -> ONE
   [c] -> CHAR c
   c:cs -> SEQ (CHAR c) (sequ cs)
 
@@ -66,14 +66,14 @@
 
 alts :: [Rexp] -> Rexp
 alts rs = case rs of
-  [] -> NULL
+  [] -> ZERO
   [r] -> r
   r:rs -> foldl (ALT) r rs
 
 size :: Rexp -> Int
 size r = case r of
-  NULL -> 1
-  EMPTY -> 1
+  ZERO -> 1
+  ONE -> 1
   CHAR _ -> 1
   ALT r1 r2 -> 1 + (size r1) + (size r2)
   SEQ r1 r2 -> 1 + (size r1) + (size r2)
@@ -82,8 +82,8 @@
 
 nullable :: Rexp -> Bool
 nullable r = case r of
-  NULL -> False
-  EMPTY -> True
+  ZERO -> False
+  ONE -> True
   CHAR _ -> False
   ALT r1 r2 -> nullable(r1) || nullable(r2)
   SEQ r1 r2 -> nullable(r1) && nullable(r2)
@@ -92,9 +92,9 @@
 
 der :: Char -> Rexp -> Rexp
 der c r = case r of
-  NULL -> NULL
-  EMPTY -> NULL
-  CHAR d -> if c == d then EMPTY else NULL
+  ZERO -> ZERO
+  ONE -> ZERO
+  CHAR d -> if c == d then ONE else ZERO
   ALT r1 r2 -> ALT (der c r1) (der c r2)
   SEQ r1 r2 -> 
       if nullable r1 then ALT (SEQ (der c r1) r2) (der c r2)
@@ -109,7 +109,7 @@
 
 flatten :: Value -> String
 flatten v = case v of 
-  Void -> ""
+  Empty -> ""
   Chr c -> [c]
   Lf v -> flatten v
   Rg v -> flatten v
@@ -119,7 +119,7 @@
 
 env :: Value -> [(String, String)]
 env v = case v of 
-  Void -> []
+  Empty -> []
   Chr c -> []
   Lf v -> env v
   Rg v -> env v
@@ -135,7 +135,7 @@
 
 mkeps :: Rexp -> Value
 mkeps r = case r of 
-  EMPTY -> Void
+  ONE -> Empty
   ALT r1 r2 -> 
       if nullable r1 then Lf (mkeps r1) else Rg (mkeps r2)
   SEQ r1 r2 -> Sequ (mkeps r1) (mkeps r2)
@@ -150,7 +150,7 @@
   (SEQ r1 r2, Rg v2) -> Sequ (mkeps r1) (inj r2 c v2)
   (ALT r1 r2, Lf v1) -> Lf (inj r1 c v1)
   (ALT r1 r2, Rg v2) -> Rg (inj r2 c v2)
-  (CHAR d, Void) -> Chr d 
+  (CHAR d, Empty) -> Chr d 
   (RECD x r1, _) -> Rec x (inj r1 c v)
 
 f_id :: Value -> Value
@@ -172,10 +172,10 @@
   Sequ v1 v2 -> Sequ (f1 v1) (f2 v2)
 
 f_seq_void1 :: (Value -> Value) -> (Value -> Value) -> Value -> Value
-f_seq_void1 f1 f2 = \v -> Sequ (f1 Void) (f2 v)
+f_seq_void1 f1 f2 = \v -> Sequ (f1 Empty) (f2 v)
 
 f_seq_void2 :: (Value -> Value) -> (Value -> Value) -> Value -> Value
-f_seq_void2 f1 f2 = \v -> Sequ(f1 v) (f2 Void)
+f_seq_void2 f1 f2 = \v -> Sequ(f1 v) (f2 Empty)
 
 f_rec :: (Value -> Value) -> Value -> Value
 f_rec f = \v -> case v of
@@ -188,8 +188,8 @@
           (r2s, f2s) = simp r2 
       in
         (case (r1s, r2s) of
-            (NULL, _) -> (r2s, f_right f2s)
-            (_, NULL) -> (r1s, f_left f1s)
+            (ZERO, _) -> (r2s, f_right f2s)
+            (_, ZERO) -> (r1s, f_left f1s)
             (_, _)    -> if r1s == r2s then (r1s, f_left f1s)
                          else (ALT r1s r2s, f_alt f1s f2s))
     SEQ r1 r2 -> 
@@ -197,10 +197,10 @@
           (r2s, f2s) = simp r2 
       in
         (case (r1s, r2s) of
-          (NULL, _)  -> (NULL, f_right f2s)
-          (_, NULL)  -> (NULL, f_left f1s)
-          (EMPTY, _) -> (r2s, f_seq_void1 f1s f2s)
-          (_, EMPTY) -> (r1s, f_seq_void2 f1s f2s)
+          (ZERO, _)  -> (ZERO, f_right f2s)
+          (_, ZERO)  -> (ZERO, f_left f1s)
+          (ONE, _) -> (r2s, f_seq_void1 f1s f2s)
+          (_, ONE) -> (r1s, f_seq_void2 f1s f2s)
           (_, _)     -> (SEQ r1s r2s, f_seq f1s f2s))
     RECD x r1 -> 
       let (r1s, f1s) = simp r1 
@@ -210,16 +210,16 @@
 
 der_simp :: Char -> Rexp -> (Rexp, Value -> Value)
 der_simp c r = case r of
-    NULL -> (NULL, f_id)
-    EMPTY -> (NULL, f_id)
-    CHAR(d) -> ((if c == d then EMPTY else NULL), f_id)
+    ZERO -> (ZERO, f_id)
+    ONE -> (ZERO, f_id)
+    CHAR(d) -> ((if c == d then ONE else ZERO), f_id)
     ALT r1 r2 -> 
       let (r1d, f1d) = der_simp c r1
           (r2d, f2d) = der_simp c r2 
       in
         (case (r1d, r2d) of 
-          (NULL, _) -> (r2d, f_right f2d)
-          (_, NULL) -> (r1d, f_left f1d)
+          (ZERO, _) -> (r2d, f_right f2d)
+          (_, ZERO) -> (r1d, f_left f1d)
           (_, _)    -> if r1d == r2d then (r1d, f_left f1d)
                        else (ALT r1d r2d, f_alt f1d f2d))
     SEQ r1 r2 -> 
@@ -230,28 +230,28 @@
             (r2s, f2s) = simp r2 
         in
           (case (r1d, r2s, r2d) of
-             (NULL, _, _)  -> (r2d, f_right f2d)
-             (_, NULL, _)  -> (r2d, f_right f2d)
-             (_, _, NULL)  -> (SEQ r1d r2s, f_left (f_seq f1d f2s))
-             (EMPTY, _, _) -> (ALT r2s r2d, f_alt (f_seq_void1 f1d f2s) f2d)
-             (_, EMPTY, _) -> (ALT r1d r2d, f_alt (f_seq_void2 f1d f2s) f2d)
+             (ZERO, _, _)  -> (r2d, f_right f2d)
+             (_, ZERO, _)  -> (r2d, f_right f2d)
+             (_, _, ZERO)  -> (SEQ r1d r2s, f_left (f_seq f1d f2s))
+             (ONE, _, _) -> (ALT r2s r2d, f_alt (f_seq_void1 f1d f2s) f2d)
+             (_, ONE, _) -> (ALT r1d r2d, f_alt (f_seq_void2 f1d f2s) f2d)
              (_, _, _)     -> (ALT (SEQ r1d r2s) r2d, f_alt (f_seq f1d f2s) f2d))
       else 
         let (r1d, f1d) = der_simp c r1 
             (r2s, f2s) = simp r2 
         in
           (case (r1d, r2s) of
-             (NULL, _)  -> (NULL, f_id)
-             (_, NULL)  -> (NULL, f_id)
-             (EMPTY, _) -> (r2s, f_seq_void1 f1d f2s)
-             (_, EMPTY) -> (r1d, f_seq_void2 f1d f2s)
+             (ZERO, _)  -> (ZERO, f_id)
+             (_, ZERO)  -> (ZERO, f_id)
+             (ONE, _) -> (r2s, f_seq_void1 f1d f2s)
+             (_, ONE) -> (r1d, f_seq_void2 f1d f2s)
              (_, _) -> (SEQ r1d r2s, f_seq f1d f2s))	  
     STAR r1 -> 
       let (r1d, f1d) = der_simp c r1 
       in
         (case r1d of
-           NULL -> (NULL, f_id)
-           EMPTY -> (STAR r1, f_seq_void1 f1d f_id)
+           ZERO -> (ZERO, f_id)
+           ONE -> (STAR r1, f_seq_void1 f1d f_id)
            _ -> (SEQ r1d (STAR r1), f_seq f1d f_id))
     RECD x r1 -> der_simp c r1 
 
diff -r c9027db225cc -r 6a43ea9305ba progs/ocaml/README
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/ocaml/README	Sat Mar 19 23:27:29 2016 +0000
@@ -0,0 +1,4 @@
+
+call
+
+ocaml re.ml
\ No newline at end of file
diff -r c9027db225cc -r 6a43ea9305ba progs/ocaml/re.ml
--- a/progs/ocaml/re.ml	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/ocaml/re.ml	Sat Mar 19 23:27:29 2016 +0000
@@ -1,7 +1,7 @@
 
 type rexp =
-   NULL 
- | EMPTY 
+   ZERO 
+ | ONE 
  | CHAR of char
  | ALT of rexp * rexp
  | SEQ of rexp * rexp 
@@ -9,7 +9,7 @@
  | RECD of string * rexp;;
 
 type value =
-   Void
+   Empty
  | Chr of char
  | Sequ of value * value
  | Left of value
@@ -18,7 +18,7 @@
  | Rec of string * value;;
 
 let rec string_of_val v = match v with
-   Void -> "Void"
+   Empty -> "Empty"
  | Chr(c) -> String.make 1 c
  | Sequ(v1, v2) -> "Seq(" ^ string_of_val v1 ^ "," ^ string_of_val v2 ^ ")"
  | Left(v1) -> "Left(" ^ string_of_val v1 ^ ")"
@@ -38,7 +38,7 @@
 
 (* some helper functions for rexps *)
 let rec seq s = match s with
-    [] -> EMPTY
+    [] -> ONE
   | [c] -> CHAR(c)
   | c::cs -> SEQ(CHAR(c), seq cs);;
 
@@ -55,15 +55,15 @@
 let ($) x r = RECD(x, r);;
 
 let alts rs = match rs with 
-    [] -> NULL
+    [] -> ZERO
   | [r] -> r
   | r::rs -> List.fold_left (++) r rs;;
 
 
 (* size of a regular expressions - for testing purposes *)
 let rec size r = match r with
-    NULL -> 1
-  | EMPTY -> 1
+    ZERO -> 1
+  | ONE -> 1
   | CHAR(_) -> 1
   | ALT(r1, r2) -> 1 + (size r1) + (size r2)
   | SEQ(r1, r2) -> 1 + (size r1) + (size r2)
@@ -73,8 +73,8 @@
 (* nullable function: tests whether the regular 
    expression can recognise the empty string *)
 let rec nullable r = match r with
-    NULL -> false
-  | EMPTY -> true
+    ZERO -> false
+  | ONE -> true
   | CHAR(_) -> false
   | ALT(r1, r2) -> nullable(r1) || nullable(r2)
   | SEQ(r1, r2) -> nullable(r1) && nullable(r2)
@@ -83,9 +83,9 @@
 
 (* derivative of a regular expression r w.r.t. a character c *)
 let rec der c r = match r with 
-    NULL -> NULL
-  | EMPTY -> NULL
-  | CHAR(d) -> if c = d then EMPTY else NULL
+    ZERO -> ZERO
+  | ONE -> ZERO
+  | CHAR(d) -> if c = d then ONE else ZERO
   | ALT(r1, r2) -> ALT(der c r1, der c r2)
   | SEQ(r1, r2) -> 
       if nullable r1 then ALT(SEQ(der c r1, r2), der c r2)
@@ -100,7 +100,7 @@
 
 (* extracts a string from value *)
 let rec flatten v = match v with 
-    Void -> ""
+    Empty -> ""
   | Chr(c) -> String.make 1 c
   | Left(v) -> flatten v
   | Right(v) -> flatten v
@@ -111,7 +111,7 @@
 
 (* extracts an environment from a value *)
 let rec env v = match v with
-    Void -> []
+    Empty -> []
   | Chr(c) -> []
   | Left(v) -> env v
   | Right(v) -> env v
@@ -125,7 +125,7 @@
 
 (* the value for a nullable rexp *)
 let rec mkeps r = match r with
-    EMPTY -> Void
+    ONE -> Empty
   | ALT(r1, r2) -> 
       if nullable r1 then Left(mkeps r1) else Right(mkeps r2)
   | SEQ(r1, r2) -> Sequ(mkeps r1, mkeps r2)
@@ -141,7 +141,7 @@
   | SEQ(r1, r2), Right(v2) -> Sequ(mkeps r1, inj r2 c v2)
   | ALT(r1, r2), Left(v1) -> Left(inj r1 c v1)
   | ALT(r1, r2), Right(v2) -> Right(inj r2 c v2)
-  | CHAR(d), Void -> Chr(d) 
+  | CHAR(d), Empty -> Chr(d) 
   | RECD(x, r1), _ -> Rec(x, inj r1 c v);;
 
 (* some "rectification" functions for simplification *)
@@ -153,8 +153,8 @@
   | Left(v) -> Left(f1 v);;
 let f_seq f1 f2 = fun v -> match v with 
   Sequ(v1, v2) -> Sequ(f1 v1, f2 v2);;
-let f_seq_Void1 f1 f2 = fun v -> Sequ(f1 Void, f2 v);;
-let f_seq_Void2 f1 f2 = fun v -> Sequ(f1 v, f2 Void);;
+let f_seq_Empty1 f1 f2 = fun v -> Sequ(f1 Empty, f2 v);;
+let f_seq_Empty2 f1 f2 = fun v -> Sequ(f1 v, f2 Empty);;
 let f_rec f = fun v -> match v with
     Rec(x, v) -> Rec(x, f v);;
 
@@ -168,18 +168,18 @@
       let (r1s, f1s) = simp r1 in 
       let (r2s, f2s) = simp r2 in
       (match r1s, r2s with
-          NULL, _ -> (r2s, f_right f2s)
-        | _, NULL -> (r1s, f_left f1s)
+          ZERO, _ -> (r2s, f_right f2s)
+        | _, ZERO -> (r1s, f_left f1s)
         | _, _    -> if r1s = r2s then (r1s, f_left f1s)
                      else (ALT (r1s, r2s), f_alt f1s f2s)) 
   | SEQ(r1, r2) -> 
       let (r1s, f1s) = simp r1 in
       let (r2s, f2s) = simp r2 in
       (match r1s, r2s with
-          NULL, _  -> (NULL, f_error)
-        | _, NULL  -> (NULL, f_error)
-        | EMPTY, _ -> (r2s, f_seq_Void1 f1s f2s)
-        | _, EMPTY -> (r1s, f_seq_Void2 f1s f2s)
+          ZERO, _  -> (ZERO, f_error)
+        | _, ZERO  -> (ZERO, f_error)
+        | ONE, _ -> (r2s, f_seq_Empty1 f1s f2s)
+        | _, ONE -> (r1s, f_seq_Empty2 f1s f2s)
         | _, _     -> (SEQ(r1s, r2s), f_seq f1s f2s))
   | RECD(x, r1) -> 
       let (r1s, f1s) = simp r1 in
@@ -188,15 +188,15 @@
 ;;
 
 let rec der_simp c r = match r with
-    NULL -> (NULL, f_id)
-  | EMPTY -> (NULL, f_id)
-  | CHAR(d) -> ((if c = d then EMPTY else NULL), f_id)
+    ZERO -> (ZERO, f_id)
+  | ONE -> (ZERO, f_id)
+  | CHAR(d) -> ((if c = d then ONE else ZERO), f_id)
   | ALT(r1, r2) -> 
       let (r1d, f1d) = der_simp c r1 in
       let (r2d, f2d) = der_simp c r2 in
       (match r1d, r2d with
-          NULL, _ -> (r2d, f_right f2d)
-        | _, NULL -> (r1d, f_left f1d)
+          ZERO, _ -> (r2d, f_right f2d)
+        | _, ZERO -> (r1d, f_left f1d)
         | _, _    -> if r1d = r2d then (r1d, f_left f1d)
                      else (ALT (r1d, r2d), f_alt f1d f2d))
   | SEQ(r1, r2) -> 
@@ -206,26 +206,26 @@
         let (r2d, f2d) = der_simp c r2 in
         let (r2s, f2s) = simp r2 in
         (match r1d, r2s, r2d with
-            NULL, _, _  -> (r2d, f_right f2d)
-          | _, NULL, _  -> (r2d, f_right f2d)
-          | _, _, NULL  -> (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
-          | EMPTY, _, _ -> (ALT(r2s, r2d), f_alt (f_seq_Void1 f1d f2s) f2d)
-          | _, EMPTY, _ -> (ALT(r1d, r2d), f_alt (f_seq_Void2 f1d f2s) f2d)
+            ZERO, _, _  -> (r2d, f_right f2d)
+          | _, ZERO, _  -> (r2d, f_right f2d)
+          | _, _, ZERO  -> (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
+          | ONE, _, _ -> (ALT(r2s, r2d), f_alt (f_seq_Empty1 f1d f2s) f2d)
+          | _, ONE, _ -> (ALT(r1d, r2d), f_alt (f_seq_Empty2 f1d f2s) f2d)
           | _, _, _     -> (ALT(SEQ(r1d, r2s), r2d), f_alt (f_seq f1d f2s) f2d))
       else 
         let (r1d, f1d) = der_simp c r1 in
         let (r2s, f2s) = simp r2 in
         (match r1d, r2s with
-            NULL, _ -> (NULL, f_error)
-          | _, NULL -> (NULL, f_error)
-          | EMPTY, _ -> (r2s, f_seq_Void1 f1d f2s)
-          | _, EMPTY -> (r1d, f_seq_Void2 f1d f2s)
+            ZERO, _ -> (ZERO, f_error)
+          | _, ZERO -> (ZERO, f_error)
+          | ONE, _ -> (r2s, f_seq_Empty1 f1d f2s)
+          | _, ONE -> (r1d, f_seq_Empty2 f1d f2s)
           | _, _ -> (SEQ(r1d, r2s), f_seq f1d f2s))	  
   | STAR(r1) -> 
       let (r1d, f1d) = der_simp c r1 in
       (match r1d with
-          NULL -> (NULL, f_error)
-        | EMPTY -> (STAR r1, f_seq_Void1 f1d f_id)
+          ZERO -> (ZERO, f_error)
+        | ONE -> (STAR r1, f_seq_Empty1 f1d f_id)
         | _ -> (SEQ(r1d, STAR(r1)), f_seq f1d f_id))
   | RECD(x, r1) -> der_simp c r1 
 
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
diff -r c9027db225cc -r 6a43ea9305ba progs/scala/re2.scala
--- a/progs/scala/re2.scala	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/scala/re2.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))
 }
@@ -45,8 +45,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)
@@ -58,8 +58,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)
@@ -69,9 +69,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))
@@ -88,7 +88,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)
@@ -99,7 +99,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)
@@ -108,19 +108,6 @@
   case Rec(x, v) => (x, flatten(v))::env(v)
 }
 
-def mkeps_all(r: Rexp) : Set[Val] = r match {
-  case EMPTY => Set(Void)
-  case ALT(r1, r2) => (nullable(r1), nullable(r2)) match {
-    case (true, true) => mkeps_all(r1).map(Left) ++ mkeps_all(r2).map(Right)
-    case (true, false) => mkeps_all(r1).map(Left)
-    case (false, true) => mkeps_all(r2).map(Right)
-  }
-  case SEQ(r1, r2) => for (v1 <- mkeps_all(r1);
-                           v2 <- mkeps_all(r2)) yield Sequ(v1, v2)
-  case STAR(r) => Set(Stars(Nil), Stars(List(mkeps(r))))
-  case RECD(x, r) => for (v <-  mkeps_all(r)) yield Rec(x, v)
-}
-
 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
@@ -128,12 +115,10 @@
   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))
 }
 
-def inj_all(r: Rexp, c: Char, vs: Set[Val]) : Set[Val] =
-  for (v <- vs) yield inj(r, c, v)
 
 // main lexing function (produces a value)
 def lex(r: Rexp, s: List[Char]) : Val = s match {
diff -r c9027db225cc -r 6a43ea9305ba progs/sml/README
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/sml/README	Sat Mar 19 23:27:29 2016 +0000
@@ -0,0 +1,3 @@
+
+1) call polyml
+2) use "re.ML";
diff -r c9027db225cc -r 6a43ea9305ba progs/sml/re.ML
--- a/progs/sml/re.ML	Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/sml/re.ML	Sat Mar 19 23:27:29 2016 +0000
@@ -1,7 +1,7 @@
 
 datatype rexp =
-   NULL 
- | EMPTY 
+   ZERO
+ | ONE 
  | CHAR of char
  | ALT of rexp * rexp
  | SEQ of rexp * rexp 
@@ -9,7 +9,7 @@
  | RECD of string * rexp
 
 datatype value =
-   Void
+   Empty
  | Chr of char
  | Sequ of value * value
  | Left of value
@@ -22,7 +22,7 @@
 
 (* some helper functions for rexps *)
 fun seq s = case s of
-    [] => EMPTY
+    [] => ONE
   | [c] => CHAR(c)
   | c::cs => SEQ(CHAR(c), seq cs)
 
@@ -43,15 +43,15 @@
 fun op $ (x, r) = RECD(x, r)
 
 fun alts rs = case rs of
-    [] => NULL
+    [] => ZERO
   | [r] => r
   | r::rs => List.foldl (op ++) r rs
 
 
 (* size of a regular expressions - for testing purposes *)
 fun size r = case r of
-    NULL => 1
-  | EMPTY => 1
+    ZERO => 1
+  | ONE => 1
   | CHAR(_) => 1
   | ALT(r1, r2) => 1 + (size r1) + (size r2)
   | SEQ(r1, r2) => 1 + (size r1) + (size r2)
@@ -61,8 +61,8 @@
 (* nullable function: tests whether the regular 
    expression can recognise the empty string *)
 fun nullable r = case r of
-    NULL => false
-  | EMPTY => true
+    ZERO => false
+  | ONE => true
   | CHAR(_) => false
   | ALT(r1, r2) => nullable(r1) orelse nullable(r2)
   | SEQ(r1, r2) => nullable(r1) andalso nullable(r2)
@@ -71,9 +71,9 @@
 
 (* derivative of a regular expression r w.r.t. a character c *)
 fun der c r = case r of
-    NULL => NULL
-  | EMPTY => NULL
-  | CHAR(d) => if c = d then EMPTY else NULL
+    ZERO => ZERO
+  | ONE => ZERO
+  | CHAR(d) => if c = d then ONE else ZERO
   | ALT(r1, r2) => ALT(der c r1, der c r2)
   | SEQ(r1, r2) => 
       if nullable r1 then ALT(SEQ(der c r1, r2), der c r2)
@@ -88,7 +88,7 @@
 
 (* extracts a string from value *)
 fun flatten v = case v of 
-    Void => ""
+    Empty => ""
   | Chr(c) => Char.toString c
   | Left(v) => flatten v
   | Right(v) => flatten v
@@ -99,7 +99,7 @@
 
 (* extracts an environment from a value *)
 fun env v = case v of 
-    Void => []
+    Empty => []
   | Chr(c) => []
   | Left(v) => env v
   | Right(v) => env v
@@ -113,7 +113,7 @@
 
 (* the value for a nullable rexp *)
 fun mkeps r = case r of 
-    EMPTY => Void
+    ONE => Empty
   | ALT(r1, r2) => 
       if nullable r1 then Left(mkeps r1) else Right(mkeps r2)
   | SEQ(r1, r2) => Sequ(mkeps r1, mkeps r2)
@@ -130,7 +130,7 @@
   | (SEQ(r1, r2), Right(v2)) => Sequ(mkeps r1, inj r2 c v2)
   | (ALT(r1, r2), Left(v1)) => Left(inj r1 c v1)
   | (ALT(r1, r2), Right(v2)) => Right(inj r2 c v2)
-  | (CHAR(d), Void) => Chr(d) 
+  | (CHAR(d), Empty) => Chr(d) 
   | (RECD(x, r1), _) => Rec(x, inj r1 c v)
   | _ => (print ("\nr: " ^ PolyML.makestring r ^ "\n");
           print ("v: " ^ PolyML.makestring v ^ "\n");
@@ -145,8 +145,8 @@
   | Left(v) => Left(f1 v)
 fun f_seq f1 f2 = fn v => case v of 
   Sequ(v1, v2) => Sequ(f1 v1, f2 v2)
-fun f_seq_Void1 f1 f2 = fn v => Sequ(f1 Void, f2 v)
-fun f_seq_Void2 f1 f2 = fn v => Sequ(f1 v, f2 Void)
+fun f_seq_Empty1 f1 f2 = fn v => Sequ(f1 Empty, f2 v)
+fun f_seq_Empty2 f1 f2 = fn v => Sequ(f1 v, f2 Empty)
 fun f_rec f = fn v => case v of
     Rec(x, v) => Rec(x, f v)
 
@@ -161,8 +161,8 @@
       let val (r1s, f1s) = simp r1  
           val (r2s, f2s) = simp r2 in
         (case (r1s, r2s) of
-            (NULL, _) => (r2s, f_right f2s)
-          | (_, NULL) => (r1s, f_left f1s)
+            (ZERO, _) => (r2s, f_right f2s)
+          | (_, ZERO) => (r1s, f_left f1s)
           | (_, _)    => if r1s = r2s then (r1s, f_left f1s)
                          else (ALT (r1s, r2s), f_alt f1s f2s))
       end 
@@ -170,10 +170,10 @@
       let val (r1s, f1s) = simp r1 
           val (r2s, f2s) = simp r2 in
         (case (r1s, r2s) of
-          (NULL, _)  => (NULL, f_error)
-        | (_, NULL)  => (NULL, f_error)
-        | (EMPTY, _) => (r2s, f_seq_Void1 f1s f2s)
-        | (_, EMPTY) => (r1s, f_seq_Void2 f1s f2s)
+          (ZERO, _)  => (ZERO, f_error)
+        | (_, ZERO)  => (ZERO, f_error)
+        | (ONE, _) => (r2s, f_seq_Empty1 f1s f2s)
+        | (_, ONE) => (r1s, f_seq_Empty2 f1s f2s)
         | (_, _)     => (SEQ(r1s, r2s), f_seq f1s f2s))
       end  
   | RECD(x, r1) => 
@@ -183,17 +183,17 @@
   | r => (r, f_id)
 
 fun der_simp c r = case r of
-    NULL => (NULL, f_id)
-  | EMPTY => (NULL, f_id)
-  | CHAR(d) => ((if c = d then EMPTY else NULL), f_id)
+    ZERO => (ZERO, f_id)
+  | ONE => (ZERO, f_id)
+  | CHAR(d) => ((if c = d then ONE else ZERO), f_id)
   | ALT(r1, r2) => 
       let 
         val (r1d, f1d) = der_simp c r1 
         val (r2d, f2d) = der_simp c r2 
       in
         case (r1d, r2d) of
-          (NULL, _) => (r2d, f_right f2d)
-        | (_, NULL) => (r1d, f_left f1d)
+          (ZERO, _) => (r2d, f_right f2d)
+        | (_, ZERO) => (r1d, f_left f1d)
         | (_, _)    => if r1d = r2d then (r1d, f_left f1d)
                        else (ALT (r1d, r2d), f_alt f1d f2d)
       end
@@ -206,11 +206,11 @@
           val (r2s, f2s) = simp r2 
         in
           case (r1d, r2s, r2d) of
-            (NULL, _, _)  => (r2d, f_right f2d)
-          | (_, NULL, _)  => (r2d, f_right f2d)
-          | (_, _, NULL)  => (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
-          | (EMPTY, _, _) => (ALT(r2s, r2d), f_alt (f_seq_Void1 f1d f2s) f2d)
-          | (_, EMPTY, _) => (ALT(r1d, r2d), f_alt (f_seq_Void2 f1d f2s) f2d)
+            (ZERO, _, _)  => (r2d, f_right f2d)
+          | (_, ZERO, _)  => (r2d, f_right f2d)
+          | (_, _, ZERO)  => (SEQ(r1d, r2s), f_left (f_seq f1d f2s))
+          | (ONE, _, _) => (ALT(r2s, r2d), f_alt (f_seq_Empty1 f1d f2s) f2d)
+          | (_, ONE, _) => (ALT(r1d, r2d), f_alt (f_seq_Empty2 f1d f2s) f2d)
           | (_, _, _)     => (ALT(SEQ(r1d, r2s), r2d), f_alt (f_seq f1d f2s) f2d)
         end
       else 
@@ -219,10 +219,10 @@
           val (r2s, f2s) = simp r2
         in
           case (r1d, r2s) of
-            (NULL, _) => (NULL, f_error)
-          | (_, NULL) => (NULL, f_error)
-          | (EMPTY, _) => (r2s, f_seq_Void1 f1d f2s)
-          | (_, EMPTY) => (r1d, f_seq_Void2 f1d f2s)
+            (ZERO, _) => (ZERO, f_error)
+          | (_, ZERO) => (ZERO, f_error)
+          | (ONE, _) => (r2s, f_seq_Empty1 f1d f2s)
+          | (_, ONE) => (r1d, f_seq_Empty2 f1d f2s)
           | (_, _) => (SEQ(r1d, r2s), f_seq f1d f2s)
   	end	  
   | STAR(r1) => 
@@ -230,8 +230,8 @@
         val (r1d, f1d) = der_simp c r1 
       in
         case r1d of
-          NULL => (NULL, f_error)
-        | EMPTY => (STAR r1, f_seq_Void1 f1d f_id)
+          ZERO => (ZERO, f_error)
+        | ONE => (STAR r1, f_seq_Empty1 f1d f_id)
         | _ => (SEQ(r1d, STAR(r1)), f_seq f1d f_id)
       end
   | RECD(x, r1) => der_simp c r1