progs/scala/re-annotated2.sc
changeset 361 8bb064045b4e
parent 360 e752d84225ec
child 644 9f984ff20020
--- a/progs/scala/re-annotated2.sc	Mon Feb 22 03:22:26 2021 +0000
+++ b/progs/scala/re-annotated2.sc	Thu Feb 25 22:46:58 2021 +0000
@@ -51,15 +51,7 @@
 // an abbreviation for binary alternatives
 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2))
 
-abstract class 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
-case class Right(v: Val) extends Val
-case class Stars(vs: List[Val]) extends Val
-case class Recd(x: String, v: Val) extends Val
-   
+
 // some convenience for typing in regular expressions
 def charlist2rexp(s: List[Char]): Rexp = s match {
   case Nil => ONE
@@ -83,17 +75,6 @@
   def $ (r: Rexp) = RECD(s, r)
 }
 
-def size(r: Rexp) : Int = r match {
-  case ZERO => 1
-  case ONE => 1
-  case ALT(r1, r2) => 1 + size(r1) + size(r2)
-  case SEQ(r1, r2) => 1 + size(r1) + size(r2)
-  case STAR(r) => 1 + size(r)
-  case RECD(_, r) => 1 + size(r)
-  case CHARSET(_) => 1
-}
-
-
 
 // Bitcoded + Annotation
 //=======================
@@ -134,43 +115,8 @@
 // internalise(("a" | "ab") ~ ("b" | ""))
 
 
-// decoding of a value from a bitsequence
-// (this is not tail-recursive and therefore a potential bottleneck)
-def vdecode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
-  case (ONE, bs) => (Empty, bs)
-  case (ALT(r1, r2), Z::bs) => {
-    val (v, bs1) = vdecode_aux(r1, bs)
-    (Left(v), bs1)
-  }
-  case (ALT(r1, r2), S::bs) => {
-    val (v, bs1) = vdecode_aux(r2, bs)
-    (Right(v), bs1)
-  }
-  case (SEQ(r1, r2), bs) => {
-    val (v1, bs1) = vdecode_aux(r1, bs)
-    val (v2, bs2) = vdecode_aux(r2, bs1)
-    (Sequ(v1, v2), bs2)
-  }
-  case (STAR(r1), Z::bs) => {
-    val (v, bs1) = vdecode_aux(r1, bs)
-    val (Stars(vs), bs2) = vdecode_aux(STAR(r1), bs1)
-    (Stars(v::vs), bs2)
-  }
-  case (STAR(_), S::bs) => (Stars(Nil), bs)
-  case (RECD(s, r1), bs) => 
-    val (v, bs1) = vdecode_aux(r1, bs)
-    (Recd(s, v), bs1)
-  case (CHARSET(_), C(c)::bs) => (Chr(c), bs)
-}
-
-def vdecode(r: Rexp, bs: Bits) = vdecode_aux(r, bs) match {
-  case (v, Nil) => v
-  case _ => throw new Exception("Not decodable")
-}
-
 // decoding of sequence of string tokens from a bitsequence
-// tail-recursive version using an accumulator (alternative for 
-// vdecode)
+// tail-recursive version using an accumulator
 @tailrec
 def sdecode_aux(rs: List[Rexp], bs: Bits, acc: List[String]) : List[String] = (rs, bs) match {
   case (Nil, _) => acc
@@ -226,7 +172,7 @@
 
 // derivative w.r.t. a string (iterates bder)
 @tailrec
-def bders (s: List[Char], r: ARexp) : ARexp = s match {
+def bders(s: List[Char], r: ARexp) : ARexp = s match {
   case Nil => r
   case c::s => bders(s, bder(c, r))
 }
@@ -238,8 +184,8 @@
 }
 
 // calls blex and decodes the value
-def blexing(r: Rexp, s: String) : Val = 
-  vdecode(r, blex(internalise(r), s.toList))
+def blexing(r: Rexp, s: String) = 
+  sdecode(r, blex(internalise(r), s.toList))
 
 
 // example by Tudor
@@ -283,45 +229,30 @@
   case c::cs => blex_simp(bsimp(bder(c, r)), cs)
 }
 
-// blexing_simp decodes a value from the bitsequence (potentially slow)
-// blexing2_simp decodes a string-list from the bitsequence
-def blexing_simp(r: Rexp, s: String) : Val = 
-  vdecode(r, blex_simp(internalise(r), s.toList))
-
-def blexing2_simp(r: Rexp, s: String) : List[String] = 
+// blexing_simp decodes a string-list from the bitsequence
+def blexing_simp(r: Rexp, s: String) : List[String] = 
   sdecode(r, blex_simp(internalise(r), s.toList))
 
 
 //println(blexing_simp(reg, "aab"))
 
 
-// extracts a string from value
-def flatten(v: Val) : String = v match {
-  case Empty => ""
-  case Chr(c) => c.toString
-  case Left(v) => flatten(v)
-  case Right(v) => flatten(v)
-  case Sequ(v1, v2) => flatten(v1) + flatten(v2)
-  case Stars(vs) => vs.map(flatten).mkString
+
+def size(r: Rexp) : Int = r match {
+  case ZERO => 1
+  case ONE => 1
+  case CHARSET(_) => 1
+  case ALT(r1, r2) => 1 + size(r1) + size(r2)
+  case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+  case STAR(r) => 1 + size(r)
+  case RECD(_, r) => 1 + size(r)
 }
 
-// extracts an environment from a value
-def env(v: Val) : List[(String, String)] = v match {
-  case Empty => Nil
-  case Chr(c) => Nil
-  case Left(v) => env(v)
-  case Right(v) => env(v)
-  case Sequ(v1, v2) => env(v1) ::: env(v2)
-  case Stars(vs) => vs.flatMap(env)
-  case Recd(x, v) => (x, flatten(v))::env(v)
-}
-
-def bsize(a: ARexp) = size(erase(a))
+def bsize(r: ARexp) = size(erase(r))
 
 // Some Tests
 //============
 
-
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
   for (j <- 1 to i) code
@@ -329,30 +260,50 @@
   (end - start)/(i * 1.0e9)
 }
 
+val ones = SEQ(SEQ(CHAR('/'), CHAR('*')), SEQ(STAR(CHAR('1')), SEQ(CHAR('*'), CHAR('/'))))
+println("sizes unsimplified")
+println(bsize(bders("/*".toList, internalise(ones))))     // 12
+println(bsize(bders("/*1".toList, internalise(ones))))    // 25
+println(bsize(bders("/*11".toList, internalise(ones))))   // 34
+println(bsize(bders("/*111".toList, internalise(ones))))  // 43
+println(bsize(bders("/*1111".toList, internalise(ones)))) // 52
+println("sizes simplified")
+println(bsize(bsimp(bders("/*".toList, internalise(ones)))))     // 6
+println(bsize(bsimp(bders("/*1".toList, internalise(ones)))))    // 6
+println(bsize(bsimp(bders("/*11".toList, internalise(ones)))))   // 6
+println(bsize(bsimp(bders("/*111".toList, internalise(ones)))))  // 6
+println(bsize(bsimp(bders("/*1111".toList, internalise(ones))))) // 6
+
+println("ones:")
+for(i <- 0 to 10000 by 1000) {
+    println(s"$i: ${time_needed(1, blexing_simp(ones, "/*" ++ "1" * i ++ "*/"))}")
+}
+
+
+
+
+System.exit(1)
+
 val evil1 = STAR(STAR("a")) ~ "b"
 val evil2 = STAR(STAR(STAR("a"))) ~ "b"
 val evil3 = STAR("aa" | "a")
 
-/*
 println("evil1")
 for(i <- 0 to 10000 by 1000) {
-    println(time_needed(1, blexing2_simp(evil1, "a"*i ++ "b")))
+    println(time_needed(1, blexing_simp(evil1, "a" * i ++ "b")))
 }
-*/
 
-/*
+
 println("evil2")
 for(i <- 0 to 10000 by 1000) {
-    println(time_needed(1, blexing2_simp(evil2, "a"*i ++ "b")))
+    println(time_needed(1, blexing_simp(evil2, "a" * i ++ "b")))
 }
-*/
 
-/*
+
 println("evil3")
 for(i <- 0 to 10000 by 1000) {
-    println(time_needed(1, blexing2_simp(evil3, "a"*i)))
+    println(time_needed(1, blexing_simp(evil3, "a" * i)))
 }
-*/
 
 // WHILE LANGUAGE
 //================
@@ -384,16 +335,17 @@
 
 // Some Simple While Tests
 //========================
+println("WHILE TESTS")
+
+
 
 val prog0 = """read n"""
 println(s"test: $prog0")
-println(env(blexing_simp(WHILE_REGS, prog0)))
-println(blexing2_simp(WHILE_REGS, prog0))
+println(blexing_simp(WHILE_REGS, prog0))
 
 val prog1 = """read  n; write n"""  
 println(s"test: $prog1")
-println(env(blexing_simp(WHILE_REGS, prog1)))
-println(blexing2_simp(WHILE_REGS, prog1))
+println(blexing_simp(WHILE_REGS, prog1))
 
 val prog2 = """
 write "Fib";
@@ -411,8 +363,8 @@
 """
 
 println("lexing fib program (once)")
-println(blexing2_simp(WHILE_REGS, prog2).filter(s => s == "" || !s.startsWith("w")))
+println(blexing_simp(WHILE_REGS, prog2).filter(s => s == "" || !s.startsWith("w")))
 
 val n = 200
 println(s"lexing fib program ($n times, size ${prog2.length * n})")
-println(time_needed(1, blexing2_simp(WHILE_REGS, prog2 * n)))
+println(time_needed(1, blexing_simp(WHILE_REGS, prog2 * n)))