diff -r e752d84225ec -r 8bb064045b4e progs/scala/re-annotated2.sc --- 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)))