112 *}; |
112 *}; |
113 |
113 |
114 lemma exec_append: |
114 lemma exec_append: |
115 "ALL stack. exec (xs @ ys) stack env = |
115 "ALL stack. exec (xs @ ys) stack env = |
116 exec ys (exec xs stack env) env" (is "?P xs"); |
116 exec ys (exec xs stack env) env" (is "?P xs"); |
117 proof (induct ?P xs in type: list); |
117 proof (induct ?P xs type: list); |
118 show "?P []"; by simp; |
118 show "?P []"; by simp; |
119 |
119 |
120 fix x xs; assume "?P xs"; |
120 fix x xs; assume "?P xs"; |
121 show "?P (x # xs)" (is "?Q x"); |
121 show "?P (x # xs)" (is "?Q x"); |
122 proof (induct ?Q x in type: instr); |
122 proof (induct ?Q x type: instr); |
123 show "!!val. ?Q (Const val)"; by (simp!); |
123 show "!!val. ?Q (Const val)"; by (simp!); |
124 show "!!adr. ?Q (Load adr)"; by (simp!); |
124 show "!!adr. ?Q (Load adr)"; by (simp!); |
125 show "!!fun. ?Q (Apply fun)"; by (simp!); |
125 show "!!fun. ?Q (Apply fun)"; by (simp!); |
126 qed; |
126 qed; |
127 qed; |
127 qed; |
128 |
128 |
129 theorem correctness: "execute (compile e) env = eval e env"; |
129 theorem correctness: "execute (compile e) env = eval e env"; |
130 proof -; |
130 proof -; |
131 have "ALL stack. exec (compile e) stack env = |
131 have "ALL stack. exec (compile e) stack env = |
132 eval e env # stack" (is "?P e"); |
132 eval e env # stack" (is "?P e"); |
133 proof (induct ?P e in type: expr); |
133 proof (induct ?P e type: expr); |
134 show "!!adr. ?P (Variable adr)"; by simp; |
134 show "!!adr. ?P (Variable adr)"; by simp; |
135 show "!!val. ?P (Constant val)"; by simp; |
135 show "!!val. ?P (Constant val)"; by simp; |
136 show "!!fun e1 e2. (?P e1 ==> ?P e2 ==> ?P (Binop fun e1 e2))"; |
136 show "!!fun e1 e2. (?P e1 ==> ?P e2 ==> ?P (Binop fun e1 e2))"; |
137 by (simp add: exec_append); |
137 by (simp add: exec_append); |
138 qed; |
138 qed; |