Theory LR_Loop
theory LR_Loop
imports LR_Prod
begin
section ‹A cheaper loop check›
text ‹\<^const>‹xrun_hist› stops a run that revisits a stack between two shifts,
by comparing the stack with all stacks since the last shift. The check only
matters for the termination of the code: between shifts the input does not
change, so a revisit means that the run loops (reduces of unit and empty
productions do not shrink the stack \<^cite>‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›), and its result is ‹None› as
the run without a check (‹nrun›). Any check that fires only on a
revisit gives the same result. ‹brun› keeps one stack of the
current segment and compares only with it, saving the current stack after 1,
2, 4, ‹…› steps (Brent's cycle detection
\<^cite>‹"brent1980-monte-carlo-factorization"›), which finds every cycle.›
partial_function (option) nrun ::
‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
('k list × 'w list ⇒ bool) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
'k list × 'w list × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹nrun ctl fin dec st = (case st of (stk, v, tstk) ⇒
if fin (stk, v) then sresult tstk
else Option.bind (ctl (stk, v)) (λ(act, stk', v').
nrun ctl fin dec (stk', v', xtree dec act v tstk)))›
definition bupd :: ‹'k list option × nat × nat ⇒ 'k list ⇒ 'k list option × nat × nat› where
‹bupd d stk = (case d of (sv, c, p) ⇒ if c = p then (Some stk, 1, 2 * p) else (sv, c + 1, p))›
partial_function (option) brun ::
‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
('k list × 'w list ⇒ bool) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
'k list option × nat × nat ⇒
'k list × 'w list × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹brun ctl fin dec d st = (case st of (stk, v, tstk) ⇒
if fin (stk, v) then sresult tstk
else if fst d = Some stk then None
else Option.bind (ctl (stk, v)) (λ(act, stk', v').
brun ctl fin dec (if act = DShift then (None, 1, 1) else bupd d stk)
(stk', v', xtree dec act v tstk)))›
lemmas brun_simps [code] = brun.simps
definition cstep :: ‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
('k list × 'w list ⇒ bool) ⇒ 'k list × 'w list ⇒ 'k list × 'w list ⇒ bool› where
‹cstep ctl fin c c' ⟷ ¬ fin c ∧ (∃a. ctl c = Some (a, c'))›
context
fixes ctl :: ‹'k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option›
and fin :: ‹'k list × 'w list ⇒ bool›
and dec :: ‹'w ⇒ ('t, 'ch, 'm) token_scheme›
assumes keep: ‹⋀stk v a stk' v'. ctl (stk, v) = Some (a, stk', v') ⟹ a ≠ DShift ⟹ v' = v›
begin
abbreviation ctl_step where ‹ctl_step ≡ cstep ctl fin›
lemma nocycle:
assumes h: ‹nrun ctl fin dec st = Some t›
shows ‹ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟹ ¬ ctl_step⇧+⇧+ c' c'›
proof -
have ‹ctl = ctl ⟶ fin = fin ⟶ (∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c')›
proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
(∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c')›], goal_cases)
case (1 f ctl' fin' dec' st t)
obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
show ?case
proof (intro impI allI notI)
fix c'
assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and r: ‹ctl_step⇧*⇧* (fst st, fst (snd st)) c'›
and cyc: ‹ctl_step⇧+⇧+ c' c'›
have ‹ctl_step⇧+⇧+ (stk, v) c'› using rtranclp_tranclp_tranclp[OF r cyc] unfolding st by simp
then obtain c1 where s1: ‹ctl_step (stk, v) c1› and r1: ‹ctl_step⇧*⇧* c1 c'›
by (auto dest: tranclpD)
from s1 obtain a where nf: ‹¬ fin (stk, v)› and sc: ‹ctl (stk, v) = Some (a, c1)›
unfolding cstep_def by blast
obtain stk1 v1 where c1: ‹c1 = (stk1, v1)› by (cases c1)
from "1"(2) nf sc have rec: ‹f ctl' fin' dec' (stk1, v1, xtree dec' a v ts) = Some t›
unfolding st c fi c1 by (auto simp: bind_eq_Some_conv)
have ‹∀c'. ctl_step⇧*⇧* (stk1, v1) c' ⟶ ¬ ctl_step⇧+⇧+ c' c'› using "1"(1)[OF rec] c fi by simp
then show False using r1 cyc unfolding c1 by blast
qed
qed
then show ‹ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟹ ¬ ctl_step⇧+⇧+ c' c'› by blast
qed
lemma x_imp_n:
assumes h: ‹xrun_hist ctl fin dec seen st = Some t›
shows ‹nrun ctl fin dec st = Some t›
proof -
have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ nrun ctl fin dec st = Some t›
proof (rule xrun_hist.raw_induct[OF _ h, where P = ‹λctl' fin' dec' seen st t. ctl' = ctl ⟶
fin' = fin ⟶ dec' = dec ⟶ nrun ctl fin dec st = Some t›], goal_cases)
case (1 f ctl' fin' dec' seen st t)
obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
show ?case
proof (intro impI)
assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and d: ‹dec' = dec›
show ‹nrun ctl fin dec st = Some t›
proof (cases ‹fin (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst nrun.simps) simp
next
case False
from False "1"(2) obtain a stk' v' where
sc: ‹ctl (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl' fin' dec' (if a = DShift then [] else stk # seen) (stk', v', xtree dec' a v ts) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
from "1"(1)[OF rec] c fi d have ‹nrun ctl fin dec (stk', v', xtree dec a v ts) = Some t› by simp
then show ?thesis unfolding st using False sc by (subst nrun.simps) simp
qed
qed
qed
then show ?thesis by blast
qed
lemma n_imp_x:
assumes h: ‹nrun ctl fin dec st = Some t›
shows ‹(∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟹
∀s ∈ set seen. ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st)) ⟹
xrun_hist ctl fin dec seen st = Some t›
proof -
have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ (∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟶
(∀seen. (∀s ∈ set seen. ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
xrun_hist ctl fin dec seen st = Some t)›
proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
dec' = dec ⟶ (∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟶
(∀seen. (∀s ∈ set seen. ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
xrun_hist ctl fin dec seen st = Some t)›], goal_cases)
case (1 f ctl' fin' dec' st t)
obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
show ?case
proof (intro impI allI)
fix seen
assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and d: ‹dec' = dec›
and nc: ‹∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c'›
and inv: ‹∀s ∈ set seen. ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))›
show ‹xrun_hist ctl fin dec seen st = Some t›
proof (cases ‹fin (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst xrun_hist.simps) simp
next
case False
have ns: ‹stk ∉ set seen›
proof
assume ‹stk ∈ set seen›
with inv have ‹ctl_step⇧+⇧+ (stk, v) (stk, v)› unfolding st by auto
with nc show False unfolding st by auto
qed
from False "1"(2) obtain a stk' v' where
sc: ‹ctl (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl' fin' dec' (stk', v', xtree dec' a v ts) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv)
have s1: ‹ctl_step (stk, v) (stk', v')› using False sc unfolding cstep_def by blast
have nc': ‹∀c'. ctl_step⇧*⇧* (stk', v') c' ⟶ ¬ ctl_step⇧+⇧+ c' c'›
using nc s1 unfolding st by (auto intro: converse_rtranclp_into_rtranclp)
have inv': ‹∀s ∈ set (if a = DShift then [] else stk # seen). ctl_step⇧+⇧+ (s, v') (stk', v')›
proof (cases ‹a = DShift›)
case False
then have v': ‹v' = v› using keep[OF sc] by blast
show ?thesis using False inv s1 unfolding st v' by (auto intro: tranclp.trancl_into_trancl)
qed simp
from "1"(1)[OF rec] c fi d nc' inv'
have ‹xrun_hist ctl fin dec (if a = DShift then [] else stk # seen) (stk', v', xtree dec a v ts) = Some t›
by simp
then show ?thesis unfolding st using False ns sc by (subst xrun_hist.simps) simp
qed
qed
qed
then show ‹(∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟹
∀s ∈ set seen. ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st)) ⟹
xrun_hist ctl fin dec seen st = Some t› by blast
qed
lemma b_imp_n:
assumes h: ‹brun ctl fin dec d st = Some t›
shows ‹nrun ctl fin dec st = Some t›
proof -
have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ nrun ctl fin dec st = Some t›
proof (rule brun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' d st t. ctl' = ctl ⟶
fin' = fin ⟶ dec' = dec ⟶ nrun ctl fin dec st = Some t›], goal_cases)
case (1 f ctl' fin' dec' d st t)
obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
show ?case
proof (intro impI)
assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and dd: ‹dec' = dec›
show ‹nrun ctl fin dec st = Some t›
proof (cases ‹fin (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst nrun.simps) simp
next
case False
from False "1"(2) obtain a stk' v' where
sc: ‹ctl (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl' fin' dec' (if a = DShift then (None, 1, 1) else bupd d stk)
(stk', v', xtree dec' a v ts) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
from "1"(1)[OF rec] c fi dd have ‹nrun ctl fin dec (stk', v', xtree dec a v ts) = Some t› by simp
then show ?thesis unfolding st using False sc by (subst nrun.simps) simp
qed
qed
qed
then show ?thesis by blast
qed
lemma fst_bupd: ‹fst (bupd d stk) = Some stk ∨ fst (bupd d stk) = fst d›
by (cases d) (auto simp: bupd_def)
lemma n_imp_b:
assumes h: ‹nrun ctl fin dec st = Some t›
shows ‹(∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟹
(∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟹
brun ctl fin dec d st = Some t›
proof -
have ‹ctl = ctl ⟶ fin = fin ⟶ dec = dec ⟶ (∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟶
(∀d. (∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
brun ctl fin dec d st = Some t)›
proof (rule nrun.raw_induct[OF _ h, where P = ‹λctl' fin' dec' st t. ctl' = ctl ⟶ fin' = fin ⟶
dec' = dec ⟶ (∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟶
(∀d. (∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟶
brun ctl fin dec d st = Some t)›], goal_cases)
case (1 f ctl' fin' dec' st t)
obtain stk v ts where st: ‹st = (stk, v, ts)› by (cases st)
show ?case
proof (intro impI allI)
fix d :: ‹'k list option × nat × nat›
assume c: ‹ctl' = ctl› and fi: ‹fin' = fin› and dd: ‹dec' = dec›
and nc: ‹∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c'›
and inv: ‹∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))›
show ‹brun ctl fin dec d st = Some t›
proof (cases ‹fin (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst brun.simps) simp
next
case False
have ns: ‹fst d ≠ Some stk›
proof
assume ‹fst d = Some stk›
with inv have ‹ctl_step⇧+⇧+ (stk, v) (stk, v)› unfolding st by auto
with nc show False unfolding st by auto
qed
from False "1"(2) obtain a stk' v' where
sc: ‹ctl (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl' fin' dec' (stk', v', xtree dec' a v ts) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv)
have s1: ‹ctl_step (stk, v) (stk', v')› using False sc unfolding cstep_def by blast
have nc': ‹∀c'. ctl_step⇧*⇧* (stk', v') c' ⟶ ¬ ctl_step⇧+⇧+ c' c'›
using nc s1 unfolding st by (auto intro: converse_rtranclp_into_rtranclp)
have inv': ‹∀s. fst (if a = DShift then (None, 1, 1) else bupd d stk) = Some s ⟶
ctl_step⇧+⇧+ (s, v') (stk', v')›
proof (cases ‹a = DShift›)
case False
then have v': ‹v' = v› using keep[OF sc] by blast
show ?thesis using False inv s1 fst_bupd[of d stk] unfolding st v'
by (auto intro: tranclp.trancl_into_trancl)
qed simp
have ih: ‹∀d. (∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, v') (stk', v')) ⟶
brun ctl fin dec d (stk', v', xtree dec a v ts) = Some t›
using "1"(1)[OF rec] c fi dd nc' unfolding fst_conv snd_conv by blast
have ‹brun ctl fin dec (if a = DShift then (None, 1, 1) else bupd d stk) (stk', v', xtree dec a v ts) = Some t›
using spec[OF ih, of ‹if a = DShift then (None, 1, 1) else bupd d stk›] inv' by blast
then show ?thesis unfolding st using False ns sc by (subst brun.simps) simp
qed
qed
qed
then show ‹(∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c') ⟹
(∀s. fst d = Some s ⟶ ctl_step⇧+⇧+ (s, fst (snd st)) (fst st, fst (snd st))) ⟹
brun ctl fin dec d st = Some t› by blast
qed
theorem xrun_hist_brun:
‹xrun_hist ctl fin dec [] st = brun ctl fin dec (None, 1, 1) st›
proof (cases ‹nrun ctl fin dec st›)
case None
have x: ‹xrun_hist ctl fin dec [] st = None›
using x_imp_n None by (cases ‹xrun_hist ctl fin dec [] st›) auto
have b: ‹brun ctl fin dec (None, 1, 1) st = None›
using b_imp_n None by (cases ‹brun ctl fin dec (None, 1, 1) st›) auto
show ?thesis using x b by simp
next
case (Some t)
have nc: ‹∀c'. ctl_step⇧*⇧* (fst st, fst (snd st)) c' ⟶ ¬ ctl_step⇧+⇧+ c' c'› using nocycle[OF Some] by blast
show ?thesis using n_imp_x[OF Some nc] n_imp_b[OF Some nc] by simp
qed
end
lemma kctl_keep:
‹kctl K (stk, v) = Some (a, stk', v') ⟹ a ≠ DShift ⟹ v' = v›
by (auto simp: kctl_def Let_def split: list.splits option.splits prod.splits dact.splits)
lemma dparse_via_prod_loop:
assumes static: ‹sstatic G Shn›
and st: ‹pr0_states G Shn = sts› and gt: ‹pgtab G sts = gtab›
and rt: ‹red_buckets G Shn (length sts) = redtab›
and pcs: ‹pcomps G sts = pc› and pfs: ‹pfins Shn sts = pf›
and i0: ‹st_find sts (lr0_start G Shn) = i⇩0›
and lt: ‹mk_ltabs gtab sts redtab pc pf = L›
and jt: ‹jtabs_of L = J›
and kt: ‹ktabs_of J = K›
shows ‹dparse G Shn w = brun (kctl K) (kfinal K) fst (None, 1, 1) ([i⇩0], map (kenc K) w, [])›
unfolding dparse_via_prod_tables[OF static st gt rt pcs pfs i0 lt jt kt]
by (rule xrun_hist_brun) (rule kctl_keep)
end