--- 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)))