diff -r 3954579ebdaf -r 4b22587fb667 thys2/zre7.sc --- a/thys2/zre7.sc Sat Jan 22 10:48:09 2022 +0000 +++ b/thys2/zre7.sc Sat Jan 22 21:42:50 2022 +0000 @@ -8,7 +8,7 @@ //import pprint._ import scala.util.Try - +import pprint._ abstract class Val @@ -76,7 +76,7 @@ def check_before_down(c: Ctx, r: Rexp, d: Int = 0) : List[Zipper] = { mems.get((pos, r)) match { case Some(m) => - //m.parents = c::m.parents + m.parents = c::m.parents//:::List(c) m.result.find(tup2 => tup2._1 == pos) match { // case Some((i, v)) => // original_up(v, c, d) @@ -88,6 +88,8 @@ mems = mems + ((pos, r) -> m) original_down(r, m, d) } + // val m = Mem(c::Nil, MList.empty[(Int, Val)]) + // original_down(r, m, d) } //mems pstart r --> m parents [(pend, vres), ...] @@ -95,13 +97,41 @@ //012 //seq a a //0 a~a --> m ... [(2, Sequ a a)] - + // c match { + // case StarC(mst, vst, rst) => print(s"StarC $vst\t") + // case SeqC(mse, pr, unp) => print(s"SeqC $unp\t") + // case AltC(mal, w) => print(s"AltC ${w(Empty)}\t") + // case RootC => print("Root") + // } +def reorderCtx(cs: List[Ctx]): List[Ctx] = { + Nil +} def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = { m.result += (pos -> vres) - m.parents.flatMap((c: Ctx) => + //m.parents = m.parents.reverse + + // if(m.parents.size > 1){//println() + // println() + // println("each of the contexts") + // m.parents.reverse.foreach (c => + // println(simpleCtxDisplay(c)) + // ) + // println("after distinctCtx") + // distinctCtx(m.parents.reverse).foreach(c => + // println(simpleCtxDisplay(c)) + // ) + // //println(s"vs is $vss") + + // } + //.distinctBy(zipBackToRegex(_)) + (m.parents).distinctBy(zipBackToRegex(_)).flatMap((c: Ctx) => original_up(vres, c, rec_depth) - ) + ) + // m.parents.reverse.flatMap((c: Ctx) => + // original_up(vres, c, rec_depth) + // ) + // original_up(vres, m.parents.last, rec_depth) } def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match { @@ -112,19 +142,21 @@ else Nil } - case (ONE, m) => mem_up(Empty, m, d + 1) - case (SEQ(r1, r2), m) => - - val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)]) - - check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) + case (ONE, m) => Nil//mem_up(Empty, m, d + 1) + case (SEQ(r1, r2), m) => + // if(nullable(r1)){ + // val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)]) + // check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) ::: + // check_before_down(SeqC(mprime, mkeps(r1)::Nil, Nil), r2, d) + // } + // else + check_before_down(SeqC(m, Nil, List(r2)), r1, d) case (ALT(r1, r2), m) => - check_before_down(AltC(m, Left(_)), r1, d) ::: check_before_down(AltC(m, Right(_)), r2, d) case (STAR(r0), m) => - - check_before_down(StarC(m, Nil, r0), r0, d) + check_before_down(StarC(m, Nil, r0), r0, d) ::: + mem_up(Stars(Nil), m, d + 1) case (_, _) => throw new Exception("original down unexpected r or m") } @@ -134,21 +166,22 @@ (v, c) match { case (v, SeqC(m, v1::Nil, Nil)) => mem_up(Sequ(v1, v), m, d + 1) - case (v, SeqC(m, Nil, u1::Nil)) => - check_before_down(SeqC(m, v::Nil, Nil), u1, d) + case (v, SeqC(m, vs, u1::Nil)) => + check_before_down(SeqC(m, v::vs, Nil), u1, d) case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match { case Some( (i, vPrime) ) => m.result += (i -> wrap(v)) Nil case None => mem_up(wrap(v), m, d + 1) - } //mem_up(AL1(r), par) + } //mem_up(AL1(v), par) //case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC") case (v, RootC) => Nil - case (v, StarC(m, vs, r0) ) => mem_up(Stars(v::vs), m, d + 1) ::: - check_before_down(StarC(m, v::vs, r0), r0, d) + case (v, StarC(m, vs, r0) ) => //mem_up(Stars(v::vs), m, d + 1) //::: + check_before_down(StarC(m, v::vs, r0), r0, d) ::: + mem_up(Stars((v::vs).reverse), m, d + 1) case (_, _) => throw new Exception("hit unexpected context") } @@ -157,8 +190,12 @@ def derive(p: Int, z: Zipper) : List[Zipper] = { pos = p + //println(s"z's actual size is ${actualZipperSize(z::Nil)}") + z match { - case (v, m) => mem_up(v, m) + case (v, m) => + + mem_up(v, m) case _ => throw new Exception("error") } } @@ -168,7 +205,7 @@ val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)]) val c_top = SeqC(m_top, Nil, r::Nil) val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)]) - println(s"initial zipper is (ZERO, $m_r)") + println(s"initial zipper is (Empty, $m_r)") (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter // val dummyRexp = ONE // val dummyMem = Mem() @@ -195,7 +232,7 @@ //TODO: when multiple results stored in m, which one to choose? case AltC(m, wrap) => plug_mem(wrap(v), m) - case StarC(m, vs, r0) => plug_mem(Stars(v::vs), m) + case StarC(m, vs, r0) => plug_mem(Stars((v::vs).reverse), m) } } @@ -308,7 +345,7 @@ // println("printing out re0") // println(asciir) // val re1s = lex(re0, "aabc") - + def actualZipperSize(zs: List[Zipper]) : Int = zs match { case Nil => 0 case z::zs1 => countParents(z._2) + actualZipperSize(zs1) @@ -326,51 +363,128 @@ case StarC(m, _, _) => countParents(m) } } +//(a+aa)* \a --> (1 + a)(a+aa)* --> (a+aa)* + (1+a)(a+aa)* -def zipperSimp(zs: List[Zipper]) : List[Zipper] = { - zs.distinctBy(z => zipBackMem(z._2)) -} +//a(a+aa)* + 1(a+aa)* + (a+aa)* -def zipBackToRegex(c: Ctx, r: Rexp = ONE) : List[Rexp] = { +//a~(a + aa)* \a -> 1 ~ (a + aa)* +//va <-----> m --> SeqC(m1, pr, "a") --> AltC(m4, Right)--> StarC(m2, vs, "a" + "aa") --> SeqC(m) ---> Root +// ^ +// ---> AltC(m4, Left) +def zipBackToRegex(c: Ctx, r: Rexp = ONE) : Rexp = { c match { - case RootC => r::Nil - case SeqC(m, pr, Nil) => zipBackMem(m, r) - case SeqC(m, pr, unp::Nil) => zipBackMem(m, SEQ(r, unp)) - case AltC(m, w) => zipBackMem(m, r) - case StarC(m, vs, r0) => zipBackMem(m, SEQ(r, STAR(r0))) + case RootC => r + case SeqC(m, pr, Nil) => zipBackToRegex(m.parents.head, r) + case SeqC(m, pr, unp::Nil) => zipBackToRegex(m.parents.head, SEQ(r, unp)) + case AltC(m, w) => zipBackToRegex(m.parents.head, r) + case StarC(m, vs, r0) => zipBackToRegex(m.parents.head, SEQ(r, STAR(r0))) } } -def zipBackMem(m: Mem, r: Rexp = ONE) : List[Rexp] = { - m.parents.flatMap(c => zipBackToRegex(c, r)) +def zipperSimp(z: Zipper) : Unit = z match { + case (v, m) => //m.parents = m.parents.distinctBy(c => zipBackToRegex(c)) } +def distinctCtx(cs: List[Ctx]) : List[Ctx] = cs.distinctBy(c => zipBackToRegex(c)) + + +def simpleCtxDisplay(c: Ctx, indent : Int = 0) : String = c match { + case SeqC(m, pr, unp) => "Sc[m:" ++ printMem(m, indent + 1) ++ + "pr:" ++ pr.map(v => shortValOutput(v)).mkString(", ") ++ " unp:" ++ unp.map(r2 => shortRexpOutput(r2)).mkString(", ") ++ "]" + case AltC(m, w) => + w(Empty) match { + case Left(_) => s"Ac(m:${printMem(m, indent + 1)}, Left(_))" + case Right(_) => s"Ac(m:${printMem(m, indent + 1)}, Right(_))" + case Empty => s"Ac(m:${printMem(m, indent + 1)}, id)" + } + case StarC(m, vs, r0) => s"StarC[m:" ++ printMem(m, indent + 1) ++ + "vs:" ++ vs.map(v => shortValOutput(v)).mkString(", ") ++ " r0: " ++ shortRexpOutput(r0) + case RootC => "Root" + //case AL1(r) => s"(+${shortRexpOutput(r)})" + //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" + //case RTOP => "RTOP" + } + +def printMem(m: Mem, indent: Int = 0) : String = { + "M(par:" ++ + m.parents.map(c => simpleCtxDisplay(c, indent + 1)).mkString("(",",", ")") ++ + ("， results:") ++ + (for(iRexp <- m.result) + yield iRexp match {case (p: Int, v: Val) => s"$p->${shortValOutput(v)}"} + ).mkString("(",",", ")") ++ + ")" +} + +def shortRexpOutput(r: Rexp) : String = r match { + case CHAR(c) => c.toString + case ONE => "1" + case ZERO => "0" + case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" + case ALT(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")" + case STAR(r) => "[" ++ shortRexpOutput(r) ++ "]*" + //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" + case RTOP => "RTOP" + } + +def shortValOutput(v: Val) : String = v match { + case Left(v) => "L(" ++ shortValOutput(v) ++ ")" + case Right(v) => "R(" ++ shortValOutput(v) ++ ")" + case Empty => "e" + case Sequ(v1, v2) => "[" ++ shortValOutput(v1) ++ "~" ++ shortValOutput(v2) ++ "]" + case Chr(a) => a.toString + case Stars(vs) => "Stars" ++ vs.map(shortValOutput(_)).mkString("[", ",", "]") + case _ => "???" +} + + //def crystalizeZipper -mems.clear() -val re1 = ("a" | "aa").% -val re1ss = lex(re1, "aaaaa") +for(i <- 1 to 10) { + mems.clear() +println(s"there are $i number of a's") +val re1 = (("a" | "b") ~ "c" | ("b" | "e") ~ "c" ) ~ "f"//("a" | "aa" |"ab").% +val re1Lexed = lex(re1, "bcf")//"a"*i+"b") + +//drawZippers(re1Lexed) +println("size of actual zipper (including memoized contexts") +println(actualZipperSize(re1Lexed)) +//println(re1Lexed) +//re1Lexed.foreach(zipperSimp(_)) +//println(actualZipperSize(re1S)) +val re1resPlugged = plug_all(re1Lexed) +//println(actualZipperSize(re1Lexed)) -//drawZippers(re1ss) -println(actualZipperSize(re1ss)) -//println(re1ss) -val re1S = zipperSimp(re1ss) -//println(actualZipperSize(re1S)) +println("value extracted") +re1resPlugged.foreach(v => { + val Sequ(Empty, vp) = v + println(vp) +} +) + val mb = 1024*1024 +val runtime = Runtime.getRuntime +println("ALL RESULTS IN MB") +println("** Used Memory: " + (runtime.totalMemory - runtime.freeMemory) / mb) +println("** Free Memory: " + runtime.freeMemory / mb) +println("** Total Memory: " + runtime.totalMemory / mb) +println("** Max Memory: " + runtime.maxMemory / mb) + +} mems.clear() -val re2 = ALT("a", "bc") +val re2 = SEQ(ONE, "a") val re2res = lex(re2, "a") -// //lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) ))) +//lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) ))) println(re2res) val re2resPlugged = plug_all(re2res) - re2resPlugged.foreach(v => { - val Sequ(Empty, vp) = v - println(vp) -}) +re2resPlugged.foreach(v => { + val Sequ(Empty, vp) = v + println(vp) +} +) // println("remaining regex") // println(re1ss.flatMap(z => zipBackMem(z._2)))