9 subsection "The compiler" |
9 subsection "The compiler" |
10 |
10 |
11 consts compile :: "com \<Rightarrow> instr list" |
11 consts compile :: "com \<Rightarrow> instr list" |
12 primrec |
12 primrec |
13 "compile \<SKIP> = []" |
13 "compile \<SKIP> = []" |
14 "compile (x:==a) = [ASIN x a]" |
14 "compile (x:==a) = [SET x a]" |
15 "compile (c1;c2) = compile c1 @ compile c2" |
15 "compile (c1;c2) = compile c1 @ compile c2" |
16 "compile (\<IF> b \<THEN> c1 \<ELSE> c2) = |
16 "compile (\<IF> b \<THEN> c1 \<ELSE> c2) = |
17 [JMPF b (length(compile c1) + 1)] @ compile c1 @ |
17 [JMPF b (length(compile c1) + 1)] @ compile c1 @ |
18 [JMPF (%x. False) (length(compile c2))] @ compile c2" |
18 [JMPF (\<lambda>x. False) (length(compile c2))] @ compile c2" |
19 "compile (\<WHILE> b \<DO> c) = [JMPF b (length(compile c) + 1)] @ compile c @ |
19 "compile (\<WHILE> b \<DO> c) = [JMPF b (length(compile c) + 1)] @ compile c @ |
20 [JMPB (length(compile c)+1)]" |
20 [JMPB (length(compile c)+1)]" |
21 |
21 |
22 subsection "Compiler correctness" |
22 subsection "Compiler correctness" |
23 |
23 |
66 by(simp add: rtrancl_is_UN_rel_pow) |
66 by(simp add: rtrancl_is_UN_rel_pow) |
67 |
67 |
68 constdefs |
68 constdefs |
69 forws :: "instr \<Rightarrow> nat set" |
69 forws :: "instr \<Rightarrow> nat set" |
70 "forws instr == case instr of |
70 "forws instr == case instr of |
71 ASIN x a \<Rightarrow> {0} | |
71 SET x a \<Rightarrow> {0} | |
72 JMPF b n \<Rightarrow> {0,n} | |
72 JMPF b n \<Rightarrow> {0,n} | |
73 JMPB n \<Rightarrow> {}" |
73 JMPB n \<Rightarrow> {}" |
74 backws :: "instr \<Rightarrow> nat set" |
74 backws :: "instr \<Rightarrow> nat set" |
75 "backws instr == case instr of |
75 "backws instr == case instr of |
76 ASIN x a \<Rightarrow> {} | |
76 SET x a \<Rightarrow> {} | |
77 JMPF b n \<Rightarrow> {} | |
77 JMPF b n \<Rightarrow> {} | |
78 JMPB n \<Rightarrow> {n}" |
78 JMPB n \<Rightarrow> {n}" |
79 |
79 |
80 consts closed :: "nat \<Rightarrow> nat \<Rightarrow> instr list \<Rightarrow> bool" |
80 consts closed :: "nat \<Rightarrow> nat \<Rightarrow> instr list \<Rightarrow> bool" |
81 primrec |
81 primrec |
261 assume H: "\<langle>?W,[],s\<rangle> -n\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
261 assume H: "\<langle>?W,[],s\<rangle> -n\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
262 show "\<langle>?w,s\<rangle> \<longrightarrow>\<^sub>c t" |
262 show "\<langle>?w,s\<rangle> \<longrightarrow>\<^sub>c t" |
263 proof cases |
263 proof cases |
264 assume b: "b s" |
264 assume b: "b s" |
265 then obtain m where m: "n = Suc m" |
265 then obtain m where m: "n = Suc m" |
266 and 1: "\<langle>?C @ [?j2],[?j1],s\<rangle> -m\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
266 and "\<langle>?C @ [?j2],[?j1],s\<rangle> -m\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
267 using H by fastsimp |
267 using H by fastsimp |
268 then obtain r n1 n2 where n1: "\<langle>?C,[],s\<rangle> -n1\<rightarrow> \<langle>[],rev ?C,r\<rangle>" |
268 then obtain r n1 n2 where n1: "\<langle>?C,[],s\<rangle> -n1\<rightarrow> \<langle>[],rev ?C,r\<rangle>" |
269 and n2: "\<langle>[?j2],rev ?C @ [?j1],r\<rangle> -n2\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
269 and n2: "\<langle>[?j2],rev ?C @ [?j1],r\<rangle> -n2\<rightarrow> \<langle>[],rev ?W,t\<rangle>" |
270 and n12: "m = n1+n2" |
270 and n12: "m = n1+n2" |
271 using execn_decomp[of _ "[?j2]"] |
271 using execn_decomp[of _ "[?j2]"] |