9 |
9 |
10 theory LBVSpec = Step : |
10 theory LBVSpec = Step : |
11 |
11 |
12 types |
12 types |
13 certificate = "state_type option list" |
13 certificate = "state_type option list" |
14 class_certificate = "sig \\<Rightarrow> certificate" |
14 class_certificate = "sig \<Rightarrow> certificate" |
15 prog_certificate = "cname \\<Rightarrow> class_certificate" |
15 prog_certificate = "cname \<Rightarrow> class_certificate" |
16 |
16 |
17 constdefs |
17 constdefs |
18 wtl_inst :: "[instr,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \\<Rightarrow> bool" |
18 wtl_inst :: "[instr,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \<Rightarrow> bool" |
19 |
19 |
20 "wtl_inst i G rT s s' cert max_pc pc \\<equiv> app (i,G,rT,s) \\<and> |
20 "wtl_inst i G rT s s' cert max_pc pc \<equiv> app (i,G,rT,s) \<and> |
21 (let s'' = the (step (i,G,s)) in |
21 (let s'' = the (step (i,G,s)) in |
22 (\\<forall> pc' \\<in> (succs i pc). pc' < max_pc \\<and> |
22 (\<forall> pc' \<in> (succs i pc). pc' < max_pc \<and> |
23 ((pc' \\<noteq> pc+1) \\<longrightarrow> cert!pc' \\<noteq> None \\<and> G \\<turnstile> s'' <=s the (cert!pc'))) \\<and> |
23 ((pc' \<noteq> pc+1) \<longrightarrow> cert!pc' \<noteq> None \<and> G \<turnstile> s'' <=s the (cert!pc'))) \<and> |
24 (if (pc+1) \\<in> (succs i pc) then |
24 (if (pc+1) \<in> (succs i pc) then |
25 s' = s'' |
25 s' = s'' |
26 else |
26 else |
27 cert ! (pc+1) = Some s'))" |
27 cert ! (pc+1) = Some s'))" |
28 |
28 |
29 lemma [simp]: |
29 lemma [simp]: |
30 "succs i pc = {pc+1} \\<Longrightarrow> |
30 "succs i pc = {pc+1} \<Longrightarrow> |
31 wtl_inst i G rT s s' cert max_pc pc = (app (i,G,rT,s) \\<and> pc+1 < max_pc \\<and> (s' = the (step (i,G,s))))" |
31 wtl_inst i G rT s s' cert max_pc pc = (app (i,G,rT,s) \<and> pc+1 < max_pc \<and> (s' = the (step (i,G,s))))" |
32 by (unfold wtl_inst_def, auto) |
32 by (unfold wtl_inst_def, auto) |
33 |
33 |
34 lemma [simp]: |
34 lemma [simp]: |
35 "succs i pc = {} \\<Longrightarrow> wtl_inst i G rT s s' cert max_pc pc = (app (i,G,rT,s) \\<and> cert!(pc+1) = Some s')" |
35 "succs i pc = {} \<Longrightarrow> wtl_inst i G rT s s' cert max_pc pc = (app (i,G,rT,s) \<and> cert!(pc+1) = Some s')" |
36 by (unfold wtl_inst_def, auto) |
36 by (unfold wtl_inst_def, auto) |
37 |
37 |
38 |
38 |
39 constdefs |
39 constdefs |
40 wtl_inst_option :: "[instr,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \\<Rightarrow> bool" |
40 wtl_inst_option :: "[instr,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \<Rightarrow> bool" |
41 "wtl_inst_option i G rT s0 s1 cert max_pc pc \\<equiv> |
41 "wtl_inst_option i G rT s0 s1 cert max_pc pc \<equiv> |
42 (case cert!pc of |
42 (case cert!pc of |
43 None \\<Rightarrow> wtl_inst i G rT s0 s1 cert max_pc pc |
43 None \<Rightarrow> wtl_inst i G rT s0 s1 cert max_pc pc |
44 | Some s0' \\<Rightarrow> (G \\<turnstile> s0 <=s s0') \\<and> |
44 | Some s0' \<Rightarrow> (G \<turnstile> s0 <=s s0') \<and> |
45 wtl_inst i G rT s0' s1 cert max_pc pc)" |
45 wtl_inst i G rT s0' s1 cert max_pc pc)" |
46 |
46 |
47 consts |
47 consts |
48 wtl_inst_list :: "[instr list,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \\<Rightarrow> bool" |
48 wtl_inst_list :: "[instr list,jvm_prog,ty,state_type,state_type,certificate,p_count,p_count] \<Rightarrow> bool" |
49 primrec |
49 primrec |
50 "wtl_inst_list [] G rT s0 s2 cert max_pc pc = (s0 = s2)" |
50 "wtl_inst_list [] G rT s0 s2 cert max_pc pc = (s0 = s2)" |
51 |
51 |
52 "wtl_inst_list (instr#is) G rT s0 s2 cert max_pc pc = |
52 "wtl_inst_list (instr#is) G rT s0 s2 cert max_pc pc = |
53 (\\<exists>s1. wtl_inst_option instr G rT s0 s1 cert max_pc pc \\<and> |
53 (\<exists>s1. wtl_inst_option instr G rT s0 s1 cert max_pc pc \<and> |
54 wtl_inst_list is G rT s1 s2 cert max_pc (pc+1))" |
54 wtl_inst_list is G rT s1 s2 cert max_pc (pc+1))" |
55 |
55 |
56 constdefs |
56 constdefs |
57 wtl_method :: "[jvm_prog,cname,ty list,ty,nat,instr list,certificate] \\<Rightarrow> bool" |
57 wtl_method :: "[jvm_prog,cname,ty list,ty,nat,instr list,certificate] \<Rightarrow> bool" |
58 "wtl_method G C pTs rT mxl ins cert \\<equiv> |
58 "wtl_method G C pTs rT mxl ins cert \<equiv> |
59 let max_pc = length ins |
59 let max_pc = length ins |
60 in |
60 in |
61 0 < max_pc \\<and> |
61 0 < max_pc \<and> |
62 (\\<exists>s2. wtl_inst_list ins G rT |
62 (\<exists>s2. wtl_inst_list ins G rT |
63 ([],(Some(Class C))#((map Some pTs))@(replicate mxl None)) |
63 ([],(Some(Class C))#((map Some pTs))@(replicate mxl None)) |
64 s2 cert max_pc 0)" |
64 s2 cert max_pc 0)" |
65 |
65 |
66 wtl_jvm_prog :: "[jvm_prog,prog_certificate] \\<Rightarrow> bool" |
66 wtl_jvm_prog :: "[jvm_prog,prog_certificate] \<Rightarrow> bool" |
67 "wtl_jvm_prog G cert \\<equiv> |
67 "wtl_jvm_prog G cert \<equiv> |
68 wf_prog (\\<lambda>G C (sig,rT,maxl,b). |
68 wf_prog (\<lambda>G C (sig,rT,maxl,b). |
69 wtl_method G C (snd sig) rT maxl b (cert C sig)) G" |
69 wtl_method G C (snd sig) rT maxl b (cert C sig)) G" |
70 |
70 |
71 text {* \medskip *} |
71 text {* \medskip *} |
72 |
72 |
73 lemma rev_eq: "\\<lbrakk>length a = n; length x = n; rev a @ b # c = rev x @ y # z\\<rbrakk> \\<Longrightarrow> a = x \\<and> b = y \\<and> c = z" |
73 lemma rev_eq: "\<lbrakk>length a = n; length x = n; rev a @ b # c = rev x @ y # z\<rbrakk> \<Longrightarrow> a = x \<and> b = y \<and> c = z" |
74 by auto |
74 by auto |
75 |
75 |
76 lemma wtl_inst_unique: |
76 lemma wtl_inst_unique: |
77 "wtl_inst i G rT s0 s1 cert max_pc pc \\<longrightarrow> |
77 "wtl_inst i G rT s0 s1 cert max_pc pc \<longrightarrow> |
78 wtl_inst i G rT s0 s1' cert max_pc pc \\<longrightarrow> s1 = s1'" (is "?P i") |
78 wtl_inst i G rT s0 s1' cert max_pc pc \<longrightarrow> s1 = s1'" (is "?P i") |
79 by (unfold wtl_inst_def, auto) |
79 by (unfold wtl_inst_def, auto) |
80 |
80 |
81 lemma wtl_inst_option_unique: |
81 lemma wtl_inst_option_unique: |
82 "\\<lbrakk>wtl_inst_option i G rT s0 s1 cert max_pc pc; |
82 "\<lbrakk>wtl_inst_option i G rT s0 s1 cert max_pc pc; |
83 wtl_inst_option i G rT s0 s1' cert max_pc pc\\<rbrakk> \\<Longrightarrow> s1 = s1'" |
83 wtl_inst_option i G rT s0 s1' cert max_pc pc\<rbrakk> \<Longrightarrow> s1 = s1'" |
84 by (cases "cert!pc") (auto simp add: wtl_inst_unique wtl_inst_option_def) |
84 by (cases "cert!pc") (auto simp add: wtl_inst_unique wtl_inst_option_def) |
85 |
85 |
86 lemma wtl_inst_list_unique: |
86 lemma wtl_inst_list_unique: |
87 "\\<forall> s0 pc. wtl_inst_list is G rT s0 s1 cert max_pc pc \\<longrightarrow> |
87 "\<forall> s0 pc. wtl_inst_list is G rT s0 s1 cert max_pc pc \<longrightarrow> |
88 wtl_inst_list is G rT s0 s1' cert max_pc pc \\<longrightarrow> s1=s1'" (is "?P is") |
88 wtl_inst_list is G rT s0 s1' cert max_pc pc \<longrightarrow> s1=s1'" (is "?P is") |
89 proof (induct "?P" "is") |
89 proof (induct (open) ?P "is") |
90 case Nil |
90 case Nil |
91 show "?P []" by simp |
91 show "?P []" by simp |
92 |
92 |
93 case Cons |
93 case Cons |
94 show "?P (a # list)" |
94 show "?P (a # list)" |
108 show "s1 = s1'" by blast |
108 show "s1 = s1'" by blast |
109 qed |
109 qed |
110 qed |
110 qed |
111 |
111 |
112 lemma wtl_partial: |
112 lemma wtl_partial: |
113 "\\<forall> pc' pc s. |
113 "\<forall> pc' pc s. |
114 wtl_inst_list is G rT s s' cert mpc pc \\<longrightarrow> \ |
114 wtl_inst_list is G rT s s' cert mpc pc \<longrightarrow> \ |
115 pc' < length is \\<longrightarrow> \ |
115 pc' < length is \<longrightarrow> \ |
116 (\\<exists> a b s1. a @ b = is \\<and> length a = pc' \\<and> \ |
116 (\<exists> a b s1. a @ b = is \<and> length a = pc' \<and> \ |
117 wtl_inst_list a G rT s s1 cert mpc pc \\<and> \ |
117 wtl_inst_list a G rT s s1 cert mpc pc \<and> \ |
118 wtl_inst_list b G rT s1 s' cert mpc (pc+length a))" (is "?P is") |
118 wtl_inst_list b G rT s1 s' cert mpc (pc+length a))" (is "?P is") |
119 proof (induct "?P" "is") |
119 proof (induct (open) ?P "is") |
120 case Nil |
120 case Nil |
121 show "?P []" by auto |
121 show "?P []" by auto |
122 |
122 |
123 case Cons |
123 case Cons |
124 show "?P (a#list)" |
124 show "?P (a#list)" |
125 proof (intro allI impI) |
125 proof (intro allI impI) |
126 fix pc' pc s |
126 fix pc' pc s |
127 assume length: "pc' < length (a # list)" |
127 assume length: "pc' < length (a # list)" |
128 assume wtl: "wtl_inst_list (a # list) G rT s s' cert mpc pc" |
128 assume wtl: "wtl_inst_list (a # list) G rT s s' cert mpc pc" |
129 show "\\<exists> a' b s1. |
129 show "\<exists> a' b s1. |
130 a' @ b = a#list \\<and> length a' = pc' \\<and> \ |
130 a' @ b = a#list \<and> length a' = pc' \<and> \ |
131 wtl_inst_list a' G rT s s1 cert mpc pc \\<and> \ |
131 wtl_inst_list a' G rT s s1 cert mpc pc \<and> \ |
132 wtl_inst_list b G rT s1 s' cert mpc (pc+length a')" |
132 wtl_inst_list b G rT s1 s' cert mpc (pc+length a')" |
133 (is "\\<exists> a b s1. ?E a b s1") |
133 (is "\<exists> a b s1. ?E a b s1") |
134 proof (cases "pc'") |
134 proof (cases (open) pc') |
135 case 0 |
135 case 0 |
136 with wtl |
136 with wtl |
137 have "?E [] (a#list) s" by simp |
137 have "?E [] (a#list) s" by simp |
138 thus ?thesis by blast |
138 thus ?thesis by blast |
139 next |
139 next |
220 with a |
220 with a |
221 show ?thesis by (rule wtl_append1) |
221 show ?thesis by (rule wtl_append1) |
222 qed |
222 qed |
223 |
223 |
224 lemma "wtl_append": |
224 lemma "wtl_append": |
225 "\\<lbrakk>wtl_inst_list a G rT s0 s1 cert (length (a@i#b)) 0; |
225 "\<lbrakk>wtl_inst_list a G rT s0 s1 cert (length (a@i#b)) 0; |
226 wtl_inst_option i G rT s1 s2 cert (length (a@i#b)) (length a); |
226 wtl_inst_option i G rT s1 s2 cert (length (a@i#b)) (length a); |
227 wtl_inst_list b G rT s2 s3 cert (length (a@i#b)) (Suc (length a))\\<rbrakk> \\<Longrightarrow> |
227 wtl_inst_list b G rT s2 s3 cert (length (a@i#b)) (Suc (length a))\<rbrakk> \<Longrightarrow> |
228 wtl_inst_list (a@[i]) G rT s0 s2 cert (length (a@i#b)) 0" |
228 wtl_inst_list (a@[i]) G rT s0 s2 cert (length (a@i#b)) 0" |
229 proof - |
229 proof - |
230 assume a: "wtl_inst_list a G rT s0 s1 cert (length (a@i#b)) 0" |
230 assume a: "wtl_inst_list a G rT s0 s1 cert (length (a@i#b)) 0" |
231 assume i: "wtl_inst_option i G rT s1 s2 cert (length (a@i#b)) (length a)" |
231 assume i: "wtl_inst_option i G rT s1 s2 cert (length (a@i#b)) (length a)" |
232 assume b: "wtl_inst_list b G rT s2 s3 cert (length (a@i#b)) (Suc (length a))" |
232 assume b: "wtl_inst_list b G rT s2 s3 cert (length (a@i#b)) (Suc (length a))" |
233 |
233 |
234 have "\\<forall> s0 pc. wtl_inst_list a G rT s0 s1 cert (pc+length (a@i#b)) pc \\<longrightarrow> |
234 have "\<forall> s0 pc. wtl_inst_list a G rT s0 s1 cert (pc+length (a@i#b)) pc \<longrightarrow> |
235 wtl_inst_option i G rT s1 s2 cert (pc+length (a@i#b)) (pc + length a) \\<longrightarrow> |
235 wtl_inst_option i G rT s1 s2 cert (pc+length (a@i#b)) (pc + length a) \<longrightarrow> |
236 wtl_inst_list b G rT s2 s3 cert (pc+length (a@i#b)) (Suc pc + length a) \\<longrightarrow> |
236 wtl_inst_list b G rT s2 s3 cert (pc+length (a@i#b)) (Suc pc + length a) \<longrightarrow> |
237 wtl_inst_list (a@[i]) G rT s0 s2 cert (pc+length (a@i#b)) pc" (is "?P a") |
237 wtl_inst_list (a@[i]) G rT s0 s2 cert (pc+length (a@i#b)) pc" (is "?P a") |
238 proof (induct "?P" "a") |
238 proof (induct (open) ?P a) |
239 case Nil |
239 case Nil |
240 show "?P []" by (simp del: split_paired_Ex) |
240 show "?P []" by (simp del: split_paired_Ex) |
241 case Cons |
241 case Cons |
242 show "?P (a#list)" (is "\\<forall>s0 pc. ?x s0 pc \\<longrightarrow> ?y s0 pc \\<longrightarrow> ?z s0 pc \\<longrightarrow> ?p s0 pc") |
242 show "?P (a#list)" (is "\<forall>s0 pc. ?x s0 pc \<longrightarrow> ?y s0 pc \<longrightarrow> ?z s0 pc \<longrightarrow> ?p s0 pc") |
243 proof intro |
243 proof intro |
244 fix s0 pc |
244 fix s0 pc |
245 assume y: "?y s0 pc" |
245 assume y: "?y s0 pc" |
246 assume z: "?z s0 pc" |
246 assume z: "?z s0 pc" |
247 assume "?x s0 pc" |
247 assume "?x s0 pc" |