equal
deleted
inserted
replaced
1 (* Title: HOL/UNITY/Comp/AllocImpl.thy |
1 (* Title: HOL/UNITY/Comp/AllocImpl.thy |
2 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
2 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
3 Copyright 1998 University of Cambridge |
3 Copyright 1998 University of Cambridge |
4 *) |
4 *) |
5 |
5 |
6 section{*Implementation of a multiple-client allocator from a single-client allocator*} |
6 section\<open>Implementation of a multiple-client allocator from a single-client allocator\<close> |
7 |
7 |
8 theory AllocImpl imports AllocBase "../Follows" "../PPROD" begin |
8 theory AllocImpl imports AllocBase "../Follows" "../PPROD" begin |
9 |
9 |
10 |
10 |
11 (** State definitions. OUTPUT variables are locals **) |
11 (** State definitions. OUTPUT variables are locals **) |
236 declare funPair_o_distrib [simp] |
236 declare funPair_o_distrib [simp] |
237 declare Always_INT_distrib [simp] |
237 declare Always_INT_distrib [simp] |
238 declare o_apply [simp del] |
238 declare o_apply [simp del] |
239 |
239 |
240 |
240 |
241 subsection{*Theorems for Merge*} |
241 subsection\<open>Theorems for Merge\<close> |
242 |
242 |
243 context Merge |
243 context Merge |
244 begin |
244 begin |
245 |
245 |
246 lemma Merge_Allowed: |
246 lemma Merge_Allowed: |
305 done |
305 done |
306 |
306 |
307 end |
307 end |
308 |
308 |
309 |
309 |
310 subsection{*Theorems for Distributor*} |
310 subsection\<open>Theorems for Distributor\<close> |
311 |
311 |
312 context Distrib |
312 context Distrib |
313 begin |
313 begin |
314 |
314 |
315 lemma Distr_Increasing_Out: |
315 lemma Distr_Increasing_Out: |
369 done |
369 done |
370 |
370 |
371 end |
371 end |
372 |
372 |
373 |
373 |
374 subsection{*Theorems for Allocator*} |
374 subsection\<open>Theorems for Allocator\<close> |
375 |
375 |
376 lemma alloc_refinement_lemma: |
376 lemma alloc_refinement_lemma: |
377 "!!f::nat=>nat. (\<Inter>i \<in> lessThan n. {s. f i \<le> g i s}) |
377 "!!f::nat=>nat. (\<Inter>i \<in> lessThan n. {s. f i \<le> g i s}) |
378 \<subseteq> {s. (\<Sum>x \<in> lessThan n. f x) \<le> (\<Sum>x \<in> lessThan n. g x s)}" |
378 \<subseteq> {s. (\<Sum>x \<in> lessThan n. f x) \<le> (\<Sum>x \<in> lessThan n. g x s)}" |
379 apply (induct_tac "n") |
379 apply (induct_tac "n") |