|
1 (* Title: HOLCF/Fun_Cpo.thy |
|
2 Author: Franz Regensburger |
|
3 Author: Brian Huffman |
|
4 *) |
|
5 |
|
6 header {* Class instances for the full function space *} |
|
7 |
|
8 theory Fun_Cpo |
|
9 imports Adm |
|
10 begin |
|
11 |
|
12 subsection {* Full function space is a partial order *} |
|
13 |
|
14 instantiation "fun" :: (type, below) below |
|
15 begin |
|
16 |
|
17 definition |
|
18 below_fun_def: "(op \<sqsubseteq>) \<equiv> (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x)" |
|
19 |
|
20 instance .. |
|
21 end |
|
22 |
|
23 instance "fun" :: (type, po) po |
|
24 proof |
|
25 fix f :: "'a \<Rightarrow> 'b" |
|
26 show "f \<sqsubseteq> f" |
|
27 by (simp add: below_fun_def) |
|
28 next |
|
29 fix f g :: "'a \<Rightarrow> 'b" |
|
30 assume "f \<sqsubseteq> g" and "g \<sqsubseteq> f" thus "f = g" |
|
31 by (simp add: below_fun_def fun_eq_iff below_antisym) |
|
32 next |
|
33 fix f g h :: "'a \<Rightarrow> 'b" |
|
34 assume "f \<sqsubseteq> g" and "g \<sqsubseteq> h" thus "f \<sqsubseteq> h" |
|
35 unfolding below_fun_def by (fast elim: below_trans) |
|
36 qed |
|
37 |
|
38 lemma fun_below_iff: "f \<sqsubseteq> g \<longleftrightarrow> (\<forall>x. f x \<sqsubseteq> g x)" |
|
39 by (simp add: below_fun_def) |
|
40 |
|
41 lemma fun_belowI: "(\<And>x. f x \<sqsubseteq> g x) \<Longrightarrow> f \<sqsubseteq> g" |
|
42 by (simp add: below_fun_def) |
|
43 |
|
44 lemma fun_belowD: "f \<sqsubseteq> g \<Longrightarrow> f x \<sqsubseteq> g x" |
|
45 by (simp add: below_fun_def) |
|
46 |
|
47 subsection {* Full function space is chain complete *} |
|
48 |
|
49 text {* Properties of chains of functions. *} |
|
50 |
|
51 lemma fun_chain_iff: "chain S \<longleftrightarrow> (\<forall>x. chain (\<lambda>i. S i x))" |
|
52 unfolding chain_def fun_below_iff by auto |
|
53 |
|
54 lemma ch2ch_fun: "chain S \<Longrightarrow> chain (\<lambda>i. S i x)" |
|
55 by (simp add: chain_def below_fun_def) |
|
56 |
|
57 lemma ch2ch_lambda: "(\<And>x. chain (\<lambda>i. S i x)) \<Longrightarrow> chain S" |
|
58 by (simp add: chain_def below_fun_def) |
|
59 |
|
60 text {* upper bounds of function chains yield upper bound in the po range *} |
|
61 |
|
62 lemma ub2ub_fun: |
|
63 "range S <| u \<Longrightarrow> range (\<lambda>i. S i x) <| u x" |
|
64 by (auto simp add: is_ub_def below_fun_def) |
|
65 |
|
66 text {* Type @{typ "'a::type => 'b::cpo"} is chain complete *} |
|
67 |
|
68 lemma is_lub_lambda: |
|
69 "(\<And>x. range (\<lambda>i. Y i x) <<| f x) \<Longrightarrow> range Y <<| f" |
|
70 unfolding is_lub_def is_ub_def below_fun_def by simp |
|
71 |
|
72 lemma lub_fun: |
|
73 "chain (S::nat \<Rightarrow> 'a::type \<Rightarrow> 'b::cpo) |
|
74 \<Longrightarrow> range S <<| (\<lambda>x. \<Squnion>i. S i x)" |
|
75 apply (rule is_lub_lambda) |
|
76 apply (rule cpo_lubI) |
|
77 apply (erule ch2ch_fun) |
|
78 done |
|
79 |
|
80 lemma thelub_fun: |
|
81 "chain (S::nat \<Rightarrow> 'a::type \<Rightarrow> 'b::cpo) |
|
82 \<Longrightarrow> (\<Squnion>i. S i) = (\<lambda>x. \<Squnion>i. S i x)" |
|
83 by (rule lub_fun [THEN lub_eqI]) |
|
84 |
|
85 instance "fun" :: (type, cpo) cpo |
|
86 by intro_classes (rule exI, erule lub_fun) |
|
87 |
|
88 subsection {* Chain-finiteness of function space *} |
|
89 |
|
90 lemma maxinch2maxinch_lambda: |
|
91 "(\<And>x. max_in_chain n (\<lambda>i. S i x)) \<Longrightarrow> max_in_chain n S" |
|
92 unfolding max_in_chain_def fun_eq_iff by simp |
|
93 |
|
94 lemma maxinch_mono: |
|
95 "\<lbrakk>max_in_chain i Y; i \<le> j\<rbrakk> \<Longrightarrow> max_in_chain j Y" |
|
96 unfolding max_in_chain_def |
|
97 proof (intro allI impI) |
|
98 fix k |
|
99 assume Y: "\<forall>n\<ge>i. Y i = Y n" |
|
100 assume ij: "i \<le> j" |
|
101 assume jk: "j \<le> k" |
|
102 from ij jk have ik: "i \<le> k" by simp |
|
103 from Y ij have Yij: "Y i = Y j" by simp |
|
104 from Y ik have Yik: "Y i = Y k" by simp |
|
105 from Yij Yik show "Y j = Y k" by auto |
|
106 qed |
|
107 |
|
108 instance "fun" :: (type, discrete_cpo) discrete_cpo |
|
109 proof |
|
110 fix f g :: "'a \<Rightarrow> 'b" |
|
111 show "f \<sqsubseteq> g \<longleftrightarrow> f = g" |
|
112 unfolding fun_below_iff fun_eq_iff |
|
113 by simp |
|
114 qed |
|
115 |
|
116 subsection {* Full function space is pointed *} |
|
117 |
|
118 lemma minimal_fun: "(\<lambda>x. \<bottom>) \<sqsubseteq> f" |
|
119 by (simp add: below_fun_def) |
|
120 |
|
121 instance "fun" :: (type, pcpo) pcpo |
|
122 by default (fast intro: minimal_fun) |
|
123 |
|
124 lemma inst_fun_pcpo: "\<bottom> = (\<lambda>x. \<bottom>)" |
|
125 by (rule minimal_fun [THEN UU_I, symmetric]) |
|
126 |
|
127 lemma app_strict [simp]: "\<bottom> x = \<bottom>" |
|
128 by (simp add: inst_fun_pcpo) |
|
129 |
|
130 lemma lambda_strict: "(\<lambda>x. \<bottom>) = \<bottom>" |
|
131 by (rule UU_I, rule minimal_fun) |
|
132 |
|
133 subsection {* Propagation of monotonicity and continuity *} |
|
134 |
|
135 text {* The lub of a chain of monotone functions is monotone. *} |
|
136 |
|
137 lemma adm_monofun: "adm monofun" |
|
138 by (rule admI, simp add: thelub_fun fun_chain_iff monofun_def lub_mono) |
|
139 |
|
140 text {* The lub of a chain of continuous functions is continuous. *} |
|
141 |
|
142 lemma adm_cont: "adm cont" |
|
143 by (rule admI, simp add: thelub_fun fun_chain_iff) |
|
144 |
|
145 text {* Function application preserves monotonicity and continuity. *} |
|
146 |
|
147 lemma mono2mono_fun: "monofun f \<Longrightarrow> monofun (\<lambda>x. f x y)" |
|
148 by (simp add: monofun_def fun_below_iff) |
|
149 |
|
150 lemma cont2cont_fun: "cont f \<Longrightarrow> cont (\<lambda>x. f x y)" |
|
151 apply (rule contI2) |
|
152 apply (erule cont2mono [THEN mono2mono_fun]) |
|
153 apply (simp add: cont2contlubE thelub_fun ch2ch_cont) |
|
154 done |
|
155 |
|
156 lemma cont_fun: "cont (\<lambda>f. f x)" |
|
157 using cont_id by (rule cont2cont_fun) |
|
158 |
|
159 text {* |
|
160 Lambda abstraction preserves monotonicity and continuity. |
|
161 (Note @{text "(\<lambda>x. \<lambda>y. f x y) = f"}.) |
|
162 *} |
|
163 |
|
164 lemma mono2mono_lambda: |
|
165 assumes f: "\<And>y. monofun (\<lambda>x. f x y)" shows "monofun f" |
|
166 using f by (simp add: monofun_def fun_below_iff) |
|
167 |
|
168 lemma cont2cont_lambda [simp]: |
|
169 assumes f: "\<And>y. cont (\<lambda>x. f x y)" shows "cont f" |
|
170 by (rule contI, rule is_lub_lambda, rule contE [OF f]) |
|
171 |
|
172 text {* What D.A.Schmidt calls continuity of abstraction; never used here *} |
|
173 |
|
174 lemma contlub_lambda: |
|
175 "(\<And>x::'a::type. chain (\<lambda>i. S i x::'b::cpo)) |
|
176 \<Longrightarrow> (\<lambda>x. \<Squnion>i. S i x) = (\<Squnion>i. (\<lambda>x. S i x))" |
|
177 by (simp add: thelub_fun ch2ch_lambda) |
|
178 |
|
179 end |