Theory LR_Fast
theory LR_Fast
imports LR_Driver
begin
section ‹A faster closure for the set-anchored driver›
text ‹Profiling a parser generated for a large grammar puts nearly all of a step's time
in \<^const>‹xclosure_auto›, the closure of the frame a step pushes. Its
rounds (\<^const>‹xround›) fold every slot of the round into the
accumulator of the previous round, so each round unions the previous
representation again and the \<^const>‹FinRep› lists grow with duplicates.
\<^text>‹dclosure› runs the same rounds from a fresh accumulator and
stops when a round adds nothing. Its items equal those of
\<^const>‹xclosure_auto› up to the sets their anchor representations
denote (\<^text>‹xeq›), and every driver operation only looks at those
sets, so a driver that caches \<^text>‹dclosure› (\<^text>‹drun_nh_c›)
returns what \<^const>‹drun_nh› returns.›
subsection ‹Item lists equal up to anchor sets›
definition xrel :: ‹(nat set ⇒ nat set ⇒ bool) ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list ⇒ bool› where
‹xrel P xs ys ⟷ list_all2 (λ(p, m, R) (p', m', R'). p = p' ∧ m = m' ∧ P (irep_set R) (irep_set R')) xs ys›
abbreviation xeq :: ‹('n, 't) xitem list ⇒ ('n, 't) xitem list ⇒ bool› where
‹xeq ≡ xrel (=)›
lemma xrel_refl: ‹(⋀S. P S S) ⟹ xrel P xs xs›
unfolding xrel_def by (induction xs) auto
lemma xeq_refl [simp]: ‹xeq xs xs›
by (rule xrel_refl) simp
lemma xeq_sym: ‹xeq xs ys ⟹ xeq ys xs›
unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)
lemma xrel_mono: ‹xrel P xs ys ⟹ (⋀S T. P S T ⟹ Q S T) ⟹ xrel Q xs ys›
unfolding xrel_def by (erule list_all2_mono) (auto split: prod.split_asm)
lemma ximg_mono: ‹irep_set R ⊆ irep_set R' ⟹ ximg pr (p, m, R) ⊆ ximg pr (p, m, R')›
by (cases p) auto
lemma xrel_ximg:
‹xrel (⊆) xs ys ⟹ ⋃ (ximg pr ` set xs) ⊆ ⋃ (ximg pr ` set ys)›
unfolding xrel_def
proof (induction rule: list_all2_induct)
case (Cons x xs y ys)
obtain p m R p' m' R' where ‹x = (p, m, R)› ‹y = (p', m', R')› by (metis prod.collapse)
with Cons.hyps(1) ximg_mono[of R R' pr p m] have ‹ximg pr x ⊆ ximg pr y› by simp
with Cons.IH show ?case by auto
qed simp
lemma xeq_ximg: ‹xeq xs ys ⟹ ⋃ (ximg pr ` set xs) = ⋃ (ximg pr ` set ys)›
by (intro equalityI xrel_ximg) (auto elim: xrel_mono dest: xeq_sym)
lemma xslots_xrel:
assumes ‹xrel P xs ys› and ‹list_all2 (λa b. P (irep_set a) (irep_set b)) cls cls'›
shows ‹xrel P (xslots G xs cls) (xslots G ys cls')›
proof -
have ‹list_all2 (λ(p, m, R) (p', m', R'). p = p' ∧ m = m' ∧ P (irep_set R) (irep_set R'))
(map2 (λpr R. (pr, 0, R)) (iprods G) cls) (map2 (λpr R. (pr, 0, R)) (iprods G) cls')›
using assms(2) by (auto simp: list_all2_conv_all_nth)
with assms(1) show ?thesis unfolding xrel_def xslots_def by (rule list_all2_appendI)
qed
subsection ‹Rounds from a fresh accumulator›
definition dround :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ indrep list ⇒ indrep list› where
‹dround G xs cls = map (λpr. fold (xcontrib pr) (xslots G xs cls) (FinRep [])) (iprods G)›
fun diter :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ indrep list› where
‹diter G xs 0 = map (λ_. FinRep []) (iprods G)›
| ‹diter G xs (Suc s) = dround G xs (diter G xs s)›
lemma diter_length [simp]: ‹length (diter G xs s) = length (iprods G)›
by (cases s) (simp_all add: dround_def)
lemma xiter_mono:
‹p < length (iprods G) ⟹ irep_set (xiter G xs s ! p) ⊆ irep_set (xiter G xs (Suc s) ! p)›
by (simp only: xiter.simps(2) xround_nth[OF xiter_length] fold_xcontrib_set) blast
lemma xiter_Suc_set:
‹p < length (iprods G) ⟹
irep_set (xiter G xs (Suc s) ! p) = ⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs s)))›
proof (induction s arbitrary: p)
case 0
then show ?case by (simp only: xiter.simps(2) xround_nth[OF xiter_length] fold_xcontrib_set) simp
next
case (Suc s)
have ‹list_all2 (λa b. irep_set a ⊆ irep_set b) (xiter G xs s) (xiter G xs (Suc s))›
using xiter_mono[of _ G xs s] by (simp only: list_all2_conv_all_nth xiter_length) blast
then have ‹xrel (⊆) (xslots G xs (xiter G xs s)) (xslots G xs (xiter G xs (Suc s)))›
by (rule xslots_xrel[OF xrel_refl, rotated]) simp from xrel_ximg[OF this, of ‹iprods G ! p›] Suc.IH[OF Suc.prems] show ?case
by (simp only: xiter.simps(2)[of G xs ‹Suc s›] xround_nth[OF xiter_length Suc.prems] fold_xcontrib_set) blast
qed
lemma xiter_diter:
assumes ‹xeq f f'›
shows ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f s) (diter G f' s)›
proof (induction s)
case 0
then show ?case by (simp add: list_all2_conv_all_nth)
next
case (Suc s)
have eq: ‹⋃ (ximg pr ` set (xslots G f (xiter G f s))) = ⋃ (ximg pr ` set (xslots G f' (diter G f' s)))› for pr
by (rule xeq_ximg[OF xslots_xrel[OF assms Suc.IH]])
show ?case
unfolding list_all2_conv_all_nth
proof (intro conjI allI impI)
fix p assume ‹p < length (xiter G f (Suc s))›
then have p: ‹p < length (iprods G)› by (simp only: xiter_length)
show ‹irep_set (xiter G f (Suc s) ! p) = irep_set (diter G f' (Suc s) ! p)›
using p by (simp only: xiter_Suc_set[OF p] eq diter.simps dround_def nth_map fold_xcontrib_set) simp
qed (simp only: xiter_length diter_length)qed
definition dclosure :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list› where
‹dclosure G xs = xslots G xs (diter G xs (xfuel G xs))›
lemma xstable_diter:
assumes ‹xeq f f'›
shows ‹xstable G f (xiter G f t) ⟷ list_all2 irep_subset (diter G f' (Suc t)) (diter G f' t)›
proof -
have a: ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f t) (diter G f' t)›
and b: ‹list_all2 (λa b. irep_set a = irep_set b) (xiter G f (Suc t)) (diter G f' (Suc t))›
by (rule xiter_diter[OF assms])+
have ‹xstable G f (xiter G f t) ⟷ list_all2 irep_subset (xiter G f (Suc t)) (xiter G f t)›
by (simp only: xstable_def xiter.simps(2))
also have ‹… ⟷ list_all2 irep_subset (diter G f' (Suc t)) (diter G f' t)›
using a b by (simp only: list_all2_conv_all_nth irep_subset_correct xiter_length diter_length) auto
finally show ?thesis .
qed
lemma xfuel_xeq: ‹xeq f f' ⟹ xfuel G f = xfuel G f'›
unfolding xfuel_def using xstable_diter[of f f'] xstable_diter[of f' f'] by simp
lemma xclosure_auto_dclosure: ‹xeq f f' ⟹ xeq (xclosure_auto G f) (dclosure G f')›
unfolding xclosure_auto_def xclosure_def dclosure_def
by (simp only: xfuel_xeq[of f f']) (rule xslots_xrel[OF _ xiter_diter])
text ‹Executably, the rounds are iterated once, as for \<^const>‹xclosure_auto›.›
lemma dclosure_code [code]:
‹dclosure G xs = xslots G xs (fst (the (while_option
(λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
(diter G xs 0, dround G xs (diter G xs 0)))))›
proof -
obtain k where ‹xstable G xs (xiter G xs k)›
using xcls_stable_ex by blast
then have ‹while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0 = Some (xfuel G xs)›
unfolding xfuel_def by (rule nat_search_Some)
moreover have
‹map_option (λt. (diter G xs t, diter G xs (Suc t)))
(while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0) =
while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
(diter G xs 0, diter G xs (Suc 0))›
by (rule while_option_commute
[where f = ‹λt. (diter G xs t, diter G xs (Suc t))› and s = 0])
(simp_all add: xstable_diter[OF xeq_refl])
ultimately have
‹Some (diter G xs (xfuel G xs), diter G xs (Suc (xfuel G xs))) =
while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround G xs nxt))
(diter G xs 0, dround G xs (diter G xs 0))›
by simp
from this[symmetric] show ?thesis
by (simp add: dclosure_def)
qed
text ‹For the code, a round builds the slot list once and keeps of it only the
items before a nonterminal, with their images; each production then folds
over the images for its left-hand side.›
definition dnx :: ‹('n, 't) xitem list ⇒ ('n × indrep) list› where
‹dnx sl = List.map_filter (λ((A, rhs), m, R).
if m < length rhs then (case rhs ! m of (Nt B, r) ⇒ Some (B, irep_img r R) | _ ⇒ None)
else None) sl›
lemma fold_xcontrib_dnx:
‹fold (xcontrib pr) sl acc =
fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc) (dnx sl) acc›
by (induction sl arbitrary: acc)
(auto simp: dnx_def split: sym.splits prod.splits)
lemma dround_code [code]:
‹dround G xs cls = (let nx = dnx (xslots G xs cls) in
map (λpr. fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc) nx (FinRep []))
(iprods G))›
unfolding dround_def Let_def by (simp add: fold_xcontrib_dnx)
subsection ‹Nonterminals as numbers›
text ‹The left-hand sides of a round are compared as numbers: a nonterminal is
numbered by its first position among the left-hand sides of the productions,
the per-production numbers are a table (\<^text>‹dtab›) that the
\<^text>‹parser› command evaluates once, and the numbers of the kernel's
successors are computed once per closure (\<^text>‹dkn›).›
fun ntidx :: ‹'n list ⇒ 'n ⇒ nat› where
‹ntidx [] B = 0›
| ‹ntidx (A # As) B = (if A = B then 0 else Suc (ntidx As B))›
lemma ntidx_eq_iff: ‹A ∈ set As ⟹ ntidx As B = ntidx As A ⟷ B = A›
by (induction As) auto
definition dtab_of :: ‹'n list ⇒ 'n × ('n, 't) rhs ⇒ nat × nat option› where
‹dtab_of ns = (λ(A, rhs). (ntidx ns A,
case rhs of (Nt B, _) # _ ⇒ Some (ntidx ns B) | _ ⇒ None))›
definition dtab :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list› where
‹dtab G = map (dtab_of (map fst (iprods G))) (iprods G)›
definition dkn :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ (nat × indrep) list› where
‹dkn G xs = map (λ(B, I). (ntidx (map fst (iprods G)) B, I)) (dnx xs)›
definition dround_t :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list ⇒ (nat × indrep) list ⇒
indrep list ⇒ indrep list› where
‹dround_t G dt kn cls = (let
nx = filter (λ(_, I). I ≠ FinRep []) (kn @ List.map_filter (λ(((l, f), (A, rhs)), R).
case f of None ⇒ None
| Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
(zip (zip dt (iprods G)) cls))
in map (λ(l, f). fold (λ(b, I) acc. if b = l then irep_union I acc else acc) nx (FinRep [])) dt)›
lemma dnx_append: ‹dnx (xs @ ys) = dnx xs @ dnx ys›
unfolding dnx_def by (induction xs) (simp_all split: option.split)
lemma dnx_slots:
‹map (λ(B, I). (ntidx ns B, I)) (dnx (map2 (λpr R. (pr, 0, R)) ps cls)) =
List.map_filter (λ(((l, f), (A, rhs)), R). case f of None ⇒ None
| Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
(zip (zip (map (dtab_of ns) ps) ps) cls)›
proof (induction ps arbitrary: cls)
case (Cons pr ps)
then show ?case
by (cases cls) (auto simp: dnx_def dtab_of_def split: list.splits sym.splits prod.splits)
qed (simp add: dnx_def)
lemma fold_ntidx:
assumes ‹A ∈ set ns›
shows ‹fold (λ(b, I) acc. if b = ntidx ns A then irep_union I acc else acc)
(map (λ(B, I). (ntidx ns B, I)) nx) acc =
fold (λ(B, I) acc. if B = A then irep_union I acc else acc) nx acc›
by (induction nx arbitrary: acc) (auto simp: ntidx_eq_iff[OF assms])
text ‹Images that are empty as representations are dropped: a union with them
changes nothing, not even the representation.›
lemma fold_union_filter:
‹fold (λ(b, I) acc. if b = l then irep_union I acc else acc) (filter (λ(_, I). I ≠ FinRep []) nx) acc =
fold (λ(b, I) acc. if b = l then irep_union I acc else acc) nx acc›
proof (induction nx arbitrary: acc)
case (Cons x nx)
have ‹irep_union (FinRep []) acc = acc› for acc by (cases acc) simp_all
with Cons show ?case by (cases x) auto
qed simp
lemma dround_t_dround: ‹dround_t G (dtab G) (dkn G xs) cls = dround G xs cls›
proof -
let ?ns = ‹map fst (iprods G)›
let ?h = ‹λ(B, I). (ntidx ?ns B, I)›
have nx: ‹dkn G xs @ List.map_filter (λ(((l, f), (A, rhs)), R). case f of None ⇒ None
| Some b ⇒ (case rhs of (_, r) # _ ⇒ Some (b, irep_img r R) | [] ⇒ None))
(zip (zip (dtab G) (iprods G)) cls) = map ?h (dnx (xslots G xs cls))›
unfolding dkn_def dtab_def xslots_def dnx_append map_append dnx_slots ..
have fe: ‹fold (λ(b, I) acc. if b = fst (dtab_of ?ns pr) then irep_union I acc else acc)
(map ?h (dnx (xslots G xs cls))) (FinRep []) =
fold (λ(B, I) acc. if B = fst pr then irep_union I acc else acc)
(dnx (xslots G xs cls)) (FinRep [])› if ‹pr ∈ set (iprods G)› for pr
proof -
have ‹fst pr ∈ set ?ns› using that by simp
moreover have ‹fst (dtab_of ?ns pr) = ntidx ?ns (fst pr)› by (simp add: dtab_of_def split: prod.split)
ultimately show ?thesis by (simp only: fold_ntidx)
qed
show ?thesis
unfolding dround_t_def dround_code Let_def nx unfolding dtab_def map_map
by (intro map_cong refl) (simp only: comp_apply case_prod_beta fold_union_filter fe)
qed
definition dclosure_t :: ‹('n, 't) is_cfg ⇒ (nat × nat option) list ⇒
('n, 't) xitem list ⇒ ('n, 't) xitem list› where
‹dclosure_t G dt xs = (let kn = dkn G xs in xslots G xs (fst (the (while_option
(λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, dround_t G dt kn nxt))
(map (λ_. FinRep []) dt, dround_t G dt kn (map (λ_. FinRep []) dt))))))›
lemma dclosure_t_eq: ‹dclosure_t G (dtab G) xs = dclosure G xs›
proof -
have ‹map (λ_. FinRep []) (dtab G) = diter G xs 0› by (simp add: dtab_def)
then show ?thesis
unfolding dclosure_t_def dclosure_code Let_def dround_t_dround by simp
qed
subsection ‹The driver operations respect set-equality›
lemma list_all2_nth_refl:
‹list_all2 R xs ys ⟹ (⋀x. R x x) ⟹ R (xs ! k) (ys ! k)›
proof (induction arbitrary: k rule: list_all2_induct)
case Nil then show ?case by simp
next
case (Cons x xs y ys) then show ?case by (cases k) simp_all
qed
lemma list_all2_hd_refl: ‹list_all2 R xs ys ⟹ (⋀x. R x x) ⟹ R (hd xs) (hd ys)›
using list_all2_nth_refl[of R xs ys 0] by (cases xs; cases ys) simp_all
lemma lgoto_xeq:
‹xeq xs ys ⟹ irep_set RA = irep_set RB ⟹ xeq (lgoto xs X RA) (lgoto ys X RB)›
unfolding xrel_def lgoto_def
by (induction rule: list_all2_induct) (auto split: prod.split_asm)
lemma red_set_xeq: ‹xeq xs ys ⟹ irep_set (red_set xs pr) = irep_set (red_set ys pr)›
unfolding xrel_def red_set_def
by (induction rule: list_all2_induct) (auto split: prod.split_asm)
lemma comps_xeq:
‹xeq xs ys ⟹ map fst (filter (λ(pr, m, R). m = length (snd pr)) xs) =
map fst (filter (λ(pr, m, R). m = length (snd pr)) ys)›
unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)
lemma dlic_cong: ‹irep_set RS = irep_set RS' ⟹ dlic i cells w pr RS = dlic i cells w pr RS'›
unfolding dlic_def by (simp split: list.splits)
lemma dcands_xeq:
assumes a: ‹xeq CL CL'›
shows ‹dcands G i cells CL gc = dcands G i cells CL' gc›
proof -
have eq: ‹(λpr. irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr)) =
(λpr. irep_nonempty (red_set CL' pr) ∧ dlic i cells w pr (red_set CL' pr))› for w
by (rule ext) (metis red_set_xeq[OF a] dlic_cong irep_nonempty_correct)
show ?thesis unfolding dcands_def Let_def comps_xeq[OF a] eq ..
qed
lemma live_xeq: ‹xeq xs ys ⟹ live xs = live ys›
unfolding xrel_def live_def
by (induction rule: list_all2_induct) (auto split: prod.split_asm)
lemma gfinal_xeq:
‹list_all2 xeq Ys Ys' ⟹ gfinal G Shn (Ys, v) = gfinal G Shn (Ys', v)›
proof -
assume a: ‹list_all2 xeq Ys Ys'›
have ‹xeq (hd Ys) (hd Ys')› by (rule list_all2_hd_refl[OF a]) simp
then have ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Ys) =
list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Ys')›
unfolding xrel_def by (induction rule: list_all2_induct) (auto split: prod.split_asm)
moreover have ‹Ys = [] ⟷ Ys' = []› using a by (auto dest: list_all2_lengthD)
ultimately show ?thesis unfolding gfinal_def by simp
qed
definition gxeq :: ‹('n, 't) gconfig ⇒ ('n, 't) gconfig ⇒ bool› where
‹gxeq gc gc' ⟷ list_all2 xeq (fst gc) (fst gc') ∧ snd gc = snd gc'›
lemma mstep_cached_xeq:
assumes c: ‹list_all2 xeq cstk cstk'› and g: ‹gxeq gc gc'›
shows ‹rel_option gxeq (mstep_cached G cstk gc act) (mstep_cached G cstk' gc' act)›
proof -
obtain Xs w Xs' where gc: ‹gc = (Xs, w)› ‹gc' = (Xs', w)› and x: ‹list_all2 xeq Xs Xs'›
using g unfolding gxeq_def by (cases gc; cases gc') auto
have len: ‹length Xs = length Xs'› using x by (rule list_all2_lengthD)
have hd: ‹xeq (hd cstk) (hd cstk')› by (rule list_all2_hd_refl[OF c]) simp
have nth: ‹xeq (cstk ! k) (cstk' ! k)› for k by (rule list_all2_nth_refl[OF c]) simp
have dr: ‹list_all2 xeq (drop k Xs) (drop k Xs')› for k using x by (rule list_all2_dropI)
show ?thesis
proof (cases act)
case DShift
then show ?thesis
using lgoto_xeq[OF hd] x len unfolding gc by (auto simp: mstep_cached_def gxeq_def split: list.splits)
next
case (DReduce pr)
have rs: ‹irep_set (red_set (hd cstk) pr) = irep_set (red_set (hd cstk') pr)›
by (rule red_set_xeq[OF hd])
then show ?thesis
using DReduce lgoto_xeq[OF nth rs] dr len unfolding gc
by (auto simp: mstep_cached_def gxeq_def Let_def)
qed
qed
lemma dlive_xeq: ‹gxeq gc gc' ⟹ dlive gc = dlive gc'›
proof -
assume g: ‹gxeq gc gc'›
then have x: ‹list_all2 xeq (fst gc) (fst gc')› unfolding gxeq_def by simp
have ‹xeq (hd (fst gc)) (hd (fst gc'))› by (rule list_all2_hd_refl[OF x]) simp
moreover have ‹fst gc = [] ⟷ fst gc' = []› using x by (auto dest: list_all2_lengthD)
ultimately show ?thesis unfolding dlive_def by (auto split: prod.splits dest: live_xeq)
qed
lemma dpick_xeq:
assumes c: ‹list_all2 xeq cstk cstk'› and g: ‹gxeq gc gc'›
shows ‹rel_option (λ(a, g) (a', g'). a = a' ∧ gxeq g g') (dpick G cstk gc acts) (dpick G cstk' gc' acts)›
proof (induction acts)
case (Cons act acts)
show ?case
proof (cases ‹mstep_cached G cstk gc act›)
case None
with mstep_cached_xeq[OF c g, of G act] have ‹mstep_cached G cstk' gc' act = None›
by (cases ‹mstep_cached G cstk' gc' act›) simp_all
with None Cons.IH show ?thesis by simp
next
case (Some g1)
with mstep_cached_xeq[OF c g, of G act] obtain g1' where
‹mstep_cached G cstk' gc' act = Some g1'› and r: ‹gxeq g1 g1'›
by (cases ‹mstep_cached G cstk' gc' act›) simp_all
with Some Cons.IH dlive_xeq[OF r] show ?thesis by simp
qed
qed simp
subsection ‹The driver over \<^text>‹dclosure››
lemma dcands_gxeq: ‹gxeq gc gc' ⟹ dcands G i cells CL gc = dcands G i cells CL gc'›
unfolding gxeq_def dcands_def by (cases gc; cases gc') (auto dest: list_all2_lengthD)
definition dstep_c :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst option› where
‹dstep_c G gt sts redtab dt st = (case st of (gc, cstk, istk, v, tstk) ⇒
let i = (case istk of [] ⇒ length sts | j # _ ⇒ j);
cells = (if i < length redtab then redtab ! i else []);
CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
in (case dpick G cstk gc (dcands G i cells CL gc) of
None ⇒ None
| Some (act, gc') ⇒ Some (case act of
DShift ⇒ (gc',
dclosure_t G dt (hd (fst gc')) # cstk,
dnext gt sts i (Tm (tok (hd v))) # istk,
tl v,
Leaf (hd v) # tstk)
| DReduce pr ⇒ (gc',
dclosure_t G dt (hd (fst gc')) # drop (length (snd pr)) cstk,
dnext gt sts (istk ! length (snd pr)) (Nt (fst pr))
# drop (length (snd pr)) istk,
v,
Node (fst pr) (rev (take (length (snd pr)) tstk))
# drop (length (snd pr)) tstk))))›
definition dst_rel :: ‹('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst ⇒ bool› where
‹dst_rel st st' ⟷ gxeq (fst st) (fst st') ∧
list_all2 xeq (fst (snd st)) (fst (snd st')) ∧ snd (snd st) = snd (snd st')›
lemma dstep_xeq:
assumes r: ‹dst_rel st st'›
shows ‹rel_option dst_rel (dstep G gt sts redtab st) (dstep_c G gt sts redtab (dtab G) st')›
proof -
obtain gc cstk istk v tstk gc' cstk' where
st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and
g: ‹gxeq gc gc'› and c: ‹list_all2 xeq cstk cstk'›
using r unfolding dst_rel_def by (cases st; cases st') auto
have cl: ‹xeq (case cstk of [] ⇒ [] | c # _ ⇒ c) (case cstk' of [] ⇒ [] | c # _ ⇒ c)›
using c by (cases cstk; cases cstk') auto
define i where ‹i = (case istk of [] ⇒ length sts | j # _ ⇒ j)›
define cells where ‹cells = (if i < length redtab then redtab ! i else [])›
define acts where ‹acts = dcands G i cells (case cstk of [] ⇒ [] | c # _ ⇒ c) gc›
have acts': ‹dcands G i cells (case cstk' of [] ⇒ [] | c # _ ⇒ c) gc' = acts›
unfolding acts_def dcands_xeq[OF cl] dcands_gxeq[OF g] ..
have p: ‹rel_option (λ(a, g) (a', g'). a = a' ∧ gxeq g g') (dpick G cstk gc acts) (dpick G cstk' gc' acts)›
by (rule dpick_xeq[OF c g])
have u: ‹dcands G (case istk of [] ⇒ length sts | j # _ ⇒ j)
(if (case istk of [] ⇒ length sts | j # _ ⇒ j) < length redtab
then redtab ! (case istk of [] ⇒ length sts | j # _ ⇒ j) else [])
(case cstk of [] ⇒ [] | c # _ ⇒ c) gc = acts›
‹dcands G (case istk of [] ⇒ length sts | j # _ ⇒ j)
(if (case istk of [] ⇒ length sts | j # _ ⇒ j) < length redtab
then redtab ! (case istk of [] ⇒ length sts | j # _ ⇒ j) else [])
(case cstk' of [] ⇒ [] | c # _ ⇒ c) gc' = acts›
using acts' unfolding acts_def cells_def i_def by simp_all
show ?thesis
proof (cases ‹dpick G cstk gc acts›)
case None
with p have ‹dpick G cstk' gc' acts = None› by (cases ‹dpick G cstk' gc' acts›) auto
with None show ?thesis
unfolding st dstep_def dstep_c_def Let_def prod.case u by simp
next
case (Some p1)
then obtain act g1 where p1: ‹dpick G cstk gc acts = Some (act, g1)› by (cases p1) auto
with p obtain g1' where p1': ‹dpick G cstk' gc' acts = Some (act, g1')› and g1: ‹gxeq g1 g1'›
by (cases ‹dpick G cstk' gc' acts›) auto
have x1: ‹list_all2 xeq (fst g1) (fst g1')› using g1 unfolding gxeq_def by simp
have h: ‹xeq (xclosure_auto G (hd (fst g1))) (dclosure_t G (dtab G) (hd (fst g1')))›
unfolding dclosure_t_eq by (rule xclosure_auto_dclosure, rule list_all2_hd_refl[OF x1]) simp
have ‹list_all2 xeq (drop k cstk) (drop k cstk')› for k using c by (rule list_all2_dropI)
with h g1 c show ?thesis
unfolding st dstep_def dstep_c_def Let_def prod.case u
by (simp add: p1 p1' dst_rel_def split: dact.splits)
qed
qed
lemma gfinal_gxeq: ‹gxeq gc gc' ⟹ gfinal G Shn gc = gfinal G Shn gc'›
unfolding gxeq_def by (cases gc; cases gc') (auto dest: gfinal_xeq)
partial_function (option) drun_nh_c ::
‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹drun_nh_c G Shn gt sts redtab dt st =
(case st of (gc, cstk, istk, v, tstk) ⇒
if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
else Option.bind (dstep_c G gt sts redtab dt st) (drun_nh_c G Shn gt sts redtab dt))›
lemmas drun_nh_c_simps [code] = drun_nh_c.simps
lemma drun_nh_imp_c:
assumes ‹drun_nh G Shn gt sts redtab st = Some t›
shows ‹∀st'. dst_rel st st' ⟶ drun_nh_c G Shn gt sts redtab (dtab G) st' = Some t›
proof (rule drun_nh.raw_induct[OF _ assms], goal_cases)
case (1 f G Shn gt sts redtab st t)
show ?case
proof (intro allI impI)
fix st' assume r: ‹dst_rel st st'›
obtain gc cstk istk v tstk gc' cstk' where
st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and g: ‹gxeq gc gc'›
using r unfolding dst_rel_def by (cases st; cases st') auto
show ‹drun_nh_c G Shn gt sts redtab (dtab G) st' = Some t›
proof (cases ‹gfinal G Shn gc›)
case True
with "1"(2) gfinal_gxeq[OF g] show ?thesis
unfolding st by (subst drun_nh_c.simps) simp
next
case False
with "1"(2) obtain st⇩1 where sp: ‹dstep G gt sts redtab st = Some st⇩1›
and rec: ‹f G Shn gt sts redtab st⇩1 = Some t›
unfolding st by (auto simp: bind_eq_Some_conv)
from dstep_xeq[OF r, of G gt sts redtab] sp obtain st⇩1' where
sp': ‹dstep_c G gt sts redtab (dtab G) st' = Some st⇩1'› and r1: ‹dst_rel st⇩1 st⇩1'›
by (cases ‹dstep_c G gt sts redtab (dtab G) st'›) auto
from "1"(1)[OF rec] r1 have ‹drun_nh_c G Shn gt sts redtab (dtab G) st⇩1' = Some t› by blast
with False gfinal_gxeq[OF g] sp' show ?thesis
unfolding st by (subst drun_nh_c.simps) simp
qed
qed
qed
lemma drun_nh_c_imp:
assumes ‹drun_nh_c G Shn gt sts redtab dt st' = Some t›
shows ‹dt = dtab G ⟶ (∀st. dst_rel st st' ⟶ drun_nh G Shn gt sts redtab st = Some t)›
proof (rule drun_nh_c.raw_induct[OF _ assms], goal_cases)
case (1 f G Shn gt sts redtab dt st' t)
show ?case
proof (intro allI impI)
fix st assume d: ‹dt = dtab G› and r: ‹dst_rel st st'›
note prem = "1"(2)[unfolded d]
obtain gc cstk istk v tstk gc' cstk' where
st: ‹st = (gc, cstk, istk, v, tstk)› ‹st' = (gc', cstk', istk, v, tstk)› and g: ‹gxeq gc gc'›
using r unfolding dst_rel_def by (cases st; cases st') auto
show ‹drun_nh G Shn gt sts redtab st = Some t›
proof (cases ‹gfinal G Shn gc›)
case True
with prem gfinal_gxeq[OF g] show ?thesis
unfolding st by (subst drun_nh.simps) simp
next
case False
with prem gfinal_gxeq[OF g] obtain st⇩1' where sp': ‹dstep_c G gt sts redtab (dtab G) st' = Some st⇩1'›
and rec: ‹f G Shn gt sts redtab (dtab G) st⇩1' = Some t›
unfolding st by (auto simp: bind_eq_Some_conv)
from dstep_xeq[OF r, of G gt sts redtab] sp' obtain st⇩1 where
sp: ‹dstep G gt sts redtab st = Some st⇩1› and r1: ‹dst_rel st⇩1 st⇩1'›
by (cases ‹dstep G gt sts redtab st›) auto
from "1"(1)[OF rec] r1 have ‹drun_nh G Shn gt sts redtab st⇩1 = Some t› by blast
with False sp show ?thesis
unfolding st by (subst drun_nh.simps) simp
qed
qed
qed
lemma drun_nh_eq_c:
‹dst_rel st st' ⟹ drun_nh G Shn gt sts redtab st = drun_nh_c G Shn gt sts redtab (dtab G) st'›
using drun_nh_imp_c[of G Shn gt sts redtab st] drun_nh_c_imp[of G Shn gt sts redtab ‹dtab G› st']
by (metis not_Some_eq)
lemma dparse_via_tables_nh_c:
assumes st: ‹pr0_states G Shn = sts›
and gt: ‹pgtab G sts = gtab›
and rt: ‹red_buckets G Shn (length sts) = redtab›
and xi: ‹xinit G Shn = xin›
and xc: ‹dclosure G xin = xclos›
and i0: ‹st_find sts (lr0_start G Shn) = i⇩0›
and dt: ‹dtab G = dtb›
shows ‹dparse G Shn w =
drun_nh_c G Shn gtab sts redtab dtb (([xin], tcols w), [xclos], [i⇩0], w, [])›
proof -
have ‹dst_rel (([xin], tcols w), [xclosure_auto G xin], [i⇩0], w, [])
(([xin], tcols w), [xclos], [i⇩0], w, [])›
using xclosure_auto_dclosure[OF xeq_refl, of G xin] unfolding xc dst_rel_def gxeq_def by simp
then show ?thesis
unfolding dparse_via_tables_nh[OF st gt rt xi refl i0] dt[symmetric] by (rule drun_nh_eq_c)
qed
text ‹\<^const>‹dstep_act› over \<^text>‹dclosure›, for drivers that need the
action (the error diagnostics).›
definition dstep_act_c :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ (nat × nat option) list ⇒
('m, 'ch, 'n, 't) dst ⇒ (('n, 't) dact × ('m, 'ch, 'n, 't) dst) option› where
‹dstep_act_c G gt sts redtab dt st = (case st of (gc, cstk, istk, v, tstk) ⇒
let i = (case istk of [] ⇒ length sts | j # _ ⇒ j);
cells = (if i < length redtab then redtab ! i else []);
CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
in (case dpick G cstk gc (dcands G i cells CL gc) of
None ⇒ None
| Some (act, gc') ⇒ Some (act, case act of
DShift ⇒ (gc',
dclosure_t G dt (hd (fst gc')) # cstk,
dnext gt sts i (Tm (tok (hd v))) # istk,
tl v,
Leaf (hd v) # tstk)
| DReduce pr ⇒ (gc',
dclosure_t G dt (hd (fst gc')) # drop (length (snd pr)) cstk,
dnext gt sts (istk ! length (snd pr)) (Nt (fst pr))
# drop (length (snd pr)) istk,
v,
Node (fst pr) (rev (take (length (snd pr)) tstk))
# drop (length (snd pr)) tstk))))›
end