47 \ INV {A^B = c * a^b} \ |
47 \ INV {A^B = c * a^b} \ |
48 \ DO a := a*a; b := b div 2 OD; \ |
48 \ DO a := a*a; b := b div 2 OD; \ |
49 \ c := c*a; b := b-1 \ |
49 \ c := c*a; b := b-1 \ |
50 \ OD \ |
50 \ OD \ |
51 \ {c = A^B}"; |
51 \ {c = A^B}"; |
52 by(hoare_tac (Asm_full_simp_tac) 1); |
52 by (hoare_tac (Asm_full_simp_tac) 1); |
53 by (exhaust_tac "b" 1); |
53 by (exhaust_tac "b" 1); |
54 by (hyp_subst_tac 1); |
54 by (hyp_subst_tac 1); |
55 by (asm_full_simp_tac (simpset() addsimps [mod_less]) 1); |
55 by (asm_full_simp_tac (simpset() addsimps [mod_less]) 1); |
56 by (asm_simp_tac (simpset() addsimps [mult_assoc]) 1); |
56 by (asm_simp_tac (simpset() addsimps [mult_assoc]) 1); |
57 qed "power_by_mult"; |
57 qed "power_by_mult"; |
114 \ INV {!j. j<i --> A!j ~= 0} \ |
114 \ INV {!j. j<i --> A!j ~= 0} \ |
115 \ DO i := i+1 OD \ |
115 \ DO i := i+1 OD \ |
116 \ {(i < length A --> A!i = 0) & \ |
116 \ {(i < length A --> A!i = 0) & \ |
117 \ (i = length A --> (!j. j < length A --> A!j ~= 0))}"; |
117 \ (i = length A --> (!j. j < length A --> A!j ~= 0))}"; |
118 by (hoare_tac Asm_full_simp_tac 1); |
118 by (hoare_tac Asm_full_simp_tac 1); |
119 by(blast_tac (claset() addSEs [less_SucE]) 1); |
119 by (blast_tac (claset() addSEs [less_SucE]) 1); |
120 qed "zero_search"; |
120 qed "zero_search"; |
121 |
121 |
122 (* |
122 (* |
123 The `partition' procedure for quicksort. |
123 The `partition' procedure for quicksort. |
124 `A' is the array to be sorted (modelled as a list). |
124 `A' is the array to be sorted (modelled as a list). |
144 \ DO u := u-1 OD; \ |
144 \ DO u := u-1 OD; \ |
145 \ IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI \ |
145 \ IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI \ |
146 \ OD \ |
146 \ OD \ |
147 \ {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}"; |
147 \ {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}"; |
148 (* expand and delete abbreviations first *) |
148 (* expand and delete abbreviations first *) |
149 by(asm_simp_tac HOL_basic_ss 1); |
149 by (asm_simp_tac HOL_basic_ss 1); |
150 by(REPEAT(etac thin_rl 1)); |
150 by (REPEAT(etac thin_rl 1)); |
151 by (hoare_tac Asm_full_simp_tac 1); |
151 by (hoare_tac Asm_full_simp_tac 1); |
152 by(asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1); |
152 by (asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1); |
153 by(Clarify_tac 1); |
153 by (Clarify_tac 1); |
154 by(asm_full_simp_tac (simpset() addsimps [nth_list_update]) 1); |
154 by (asm_full_simp_tac (simpset() addsimps [nth_list_update]) 1); |
155 by(blast_tac (claset() addSEs [less_SucE] addIs [Suc_leI]) 1); |
155 by (blast_tac (claset() addSEs [less_SucE] addIs [Suc_leI]) 1); |
156 br conjI 1; |
156 by (rtac conjI 1); |
157 by(Clarify_tac 1); |
157 by (Clarify_tac 1); |
158 bd (pred_less_imp_le RS le_imp_less_Suc) 1; |
158 by (dtac (pred_less_imp_le RS le_imp_less_Suc) 1); |
159 by(blast_tac (claset() addSEs [less_SucE]) 1); |
159 by (blast_tac (claset() addSEs [less_SucE]) 1); |
160 br less_imp_diff_less 1; |
160 by (rtac less_imp_diff_less 1); |
161 by(Blast_tac 1); |
161 by (Blast_tac 1); |
162 by(Clarify_tac 1); |
162 by (Clarify_tac 1); |
163 by(asm_simp_tac (simpset() addsimps [nth_list_update]) 1); |
163 by (asm_simp_tac (simpset() addsimps [nth_list_update]) 1); |
164 by(Clarify_tac 1); |
164 by (Clarify_tac 1); |
165 by(Simp_tac 1); |
165 by (Simp_tac 1); |
166 by(Clarify_tac 1); |
166 by (Clarify_tac 1); |
167 by(Asm_simp_tac 1); |
167 by (Asm_simp_tac 1); |
168 br conjI 1; |
168 by (rtac conjI 1); |
169 by(Clarify_tac 1); |
169 by (Clarify_tac 1); |
170 br order_antisym 1; |
170 by (rtac order_antisym 1); |
171 by(Asm_simp_tac 1); |
171 by (Asm_simp_tac 1); |
172 by(Asm_simp_tac 1); |
172 by (Asm_simp_tac 1); |
173 by(Clarify_tac 1); |
173 by (Clarify_tac 1); |
174 by(Asm_simp_tac 1); |
174 by (Asm_simp_tac 1); |
175 qed "Partition"; |
175 qed "Partition"; |