Theory LR_Int
theory LR_Int
imports LR_Simple
begin
section ‹The simple driver on integer indices›
text ‹With binary naturals, converting a state index to an integer for every
array access costs about half of a step. The tables are stored with natural
numbers, which keeps them static data, and converted once into tables with
integer indices; the driver then runs on a stack of integer indices.›
partial_function (option) zrun_hist ::
‹('k list × ('m, 'ch, 't) tword ⇒ (('n, 't) dact × 'k list × ('m, 'ch, 't) tword) option) ⇒
('k list × ('m, 'ch, 't) tword ⇒ bool) ⇒ 'k list list ⇒
'k list × ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹zrun_hist ctl fin seen st = (case st of (stk, v, tstk) ⇒
if fin (stk, v) then sresult tstk
else if stk ∈ set seen then None
else Option.bind (ctl (stk, v)) (λ(act, stk', v').
zrun_hist ctl fin (if act = DShift then [] else stk # seen)
(stk', v', stree act v tstk)))›
lemmas zrun_hist_simps [code] = zrun_hist.simps
text ‹\<^const>‹zrun_hist› on encoded stacks computes \<^const>‹srun_hist›, if the
steps and final tests agree under an injective encoding of stack entries.›
locale run_transfer =
fixes enc :: ‹nat ⇒ 'k›
and ctl1 :: ‹('m, 'ch, 't) sctl_t ⇒ (('n, 't) dact × ('m, 'ch, 't) sctl_t) option›
and fin1 :: ‹('m, 'ch, 't) sctl_t ⇒ bool›
and ctl2 :: ‹'k list × ('m, 'ch, 't) tword ⇒ (('n, 't) dact × 'k list × ('m, 'ch, 't) tword) option›
and fin2 :: ‹'k list × ('m, 'ch, 't) tword ⇒ bool›
assumes inj: ‹inj enc›
and ctl: ‹⋀stk v. ctl2 (map enc stk, v) =
map_option (λ(a, stk', v'). (a, map enc stk', v')) (ctl1 (stk, v))›
and fin: ‹⋀stk v. fin2 (map enc stk, v) = fin1 (stk, v)›
begin
lemma mem_map_enc: ‹map enc stk ∈ map enc ` set seen ⟷ stk ∈ set seen›
using inj_mapI[OF inj] by (auto simp: inj_image_mem_iff)
lemma s_imp_z:
assumes h: ‹srun_hist ctl1 fin1 seen st = Some t›
shows ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
proof -
have ‹ctl1 = ctl1 ⟶ fin1 = fin1 ⟶
zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
proof (rule srun_hist.raw_induct[OF _ h, where P = ‹λctl fin seen st t. ctl = ctl1 ⟶ fin = fin1 ⟶
zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›], goal_cases)
case (1 f ctl fin seen st t)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
show ?case
proof (intro impI)
assume c: ‹ctl = ctl1› and fi: ‹fin = fin1›
show ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc (fst st), snd st) = Some t›
proof (cases ‹fin1 (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst zrun_hist.simps) (simp add: fin)
next
case False
from False "1"(2) have nk: ‹stk ∉ set seen› unfolding st c fi by (auto split: if_splits)
from False "1"(2) obtain a stk' v' where
sc: ‹ctl1 (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl fin (if a = DShift then [] else stk # seen) (stk', v', stree a v tstk) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
from "1"(1)[OF rec] c fi
have ‹zrun_hist ctl2 fin2 (map (map enc) (if a = DShift then [] else stk # seen))
(map enc stk', v', stree a v tstk) = Some t› by simp
then show ?thesis unfolding st using False nk sc
by (subst zrun_hist.simps) (cases ‹a = DShift›; simp add: fin ctl mem_map_enc)
qed
qed
qed
then show ?thesis by blast
qed
lemma z_imp_s:
assumes h: ‹zrun_hist ctl2 fin2 seen2 st2 = Some t›
shows ‹seen2 = map (map enc) seen ⟹ st2 = (map enc stk, v, tstk) ⟹
srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
proof -
have ‹ctl2 = ctl2 ⟶ fin2 = fin2 ⟶ (∀seen stk v tstk. seen2 = map (map enc) seen ⟶
st2 = (map enc stk, v, tstk) ⟶ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›
proof (rule zrun_hist.raw_induct[OF _ h, where P = ‹λctl fin seen2 st2 t. ctl = ctl2 ⟶ fin = fin2 ⟶
(∀seen stk v tstk. seen2 = map (map enc) seen ⟶
st2 = (map enc stk, v, tstk) ⟶ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›], goal_cases)
case (1 f ctl fin seen2 st2 t)
show ?case
proof (intro impI allI)
fix seen stk v tstk
assume c: ‹ctl = ctl2› and fi: ‹fin = fin2› and se: ‹seen2 = map (map enc) seen›
and st: ‹st2 = (map enc stk, v, tstk)›
show ‹srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
proof (cases ‹fin1 (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst srun_hist.simps) (simp add: fin)
next
case False
from False "1"(2) have nk: ‹stk ∉ set seen›
unfolding st c fi se by (auto simp: fin mem_map_enc split: if_splits)
from False "1"(2) obtain a stk2 v' where
sc: ‹ctl2 (map enc stk, v) = Some (a, stk2, v')›
and rec: ‹f ctl fin (if a = DShift then [] else map enc stk # seen2) (stk2, v', stree a v tstk) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv fin split: if_splits)
from sc obtain stk' where sc1: ‹ctl1 (stk, v) = Some (a, stk', v')› and stk2: ‹stk2 = map enc stk'›
unfolding ctl by (auto split: prod.splits)
have ‹srun_hist ctl1 fin1 (if a = DShift then [] else stk # seen) (stk', v', stree a v tstk) = Some t›
using "1"(1)[OF rec] c fi se stk2 by simp
then show ?thesis using False nk sc1 by (subst srun_hist.simps) simp
qed
qed
qed
then show ‹seen2 = map (map enc) seen ⟹ st2 = (map enc stk, v, tstk) ⟹
srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t› by blast
qed
theorem zrun_hist_eq:
‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc stk, v, tstk) = srun_hist ctl1 fin1 seen (stk, v, tstk)›
proof (cases ‹srun_hist ctl1 fin1 seen (stk, v, tstk)›)
case None
show ?thesis
proof (cases ‹zrun_hist ctl2 fin2 (map (map enc) seen) (map enc stk, v, tstk)›)
case (Some t)
from z_imp_s[OF Some refl refl] None show ?thesis by simp
qed (simp add: None)
next
case (Some t)
from s_imp_z[OF Some] Some show ?thesis by simp
qed
end
subsection ‹Integer tables and the integer step›