33 |
33 |
34 syntax "_cabs" :: "[logic, logic] \<Rightarrow> logic" |
34 syntax "_cabs" :: "[logic, logic] \<Rightarrow> logic" |
35 |
35 |
36 parse_translation \<open> |
36 parse_translation \<open> |
37 (* rewrite (_cabs x t) => (Abs_cfun (%x. t)) *) |
37 (* rewrite (_cabs x t) => (Abs_cfun (%x. t)) *) |
38 [Syntax_Trans.mk_binder_tr (@{syntax_const "_cabs"}, @{const_syntax Abs_cfun})] |
38 [Syntax_Trans.mk_binder_tr (\<^syntax_const>\<open>_cabs\<close>, \<^const_syntax>\<open>Abs_cfun\<close>)] |
39 \<close> |
39 \<close> |
40 |
40 |
41 print_translation \<open> |
41 print_translation \<open> |
42 [(@{const_syntax Abs_cfun}, fn _ => fn [Abs abs] => |
42 [(\<^const_syntax>\<open>Abs_cfun\<close>, fn _ => fn [Abs abs] => |
43 let val (x, t) = Syntax_Trans.atomic_abs_tr' abs |
43 let val (x, t) = Syntax_Trans.atomic_abs_tr' abs |
44 in Syntax.const @{syntax_const "_cabs"} $ x $ t end)] |
44 in Syntax.const \<^syntax_const>\<open>_cabs\<close> $ x $ t end)] |
45 \<close> \<comment> \<open>To avoid eta-contraction of body\<close> |
45 \<close> \<comment> \<open>To avoid eta-contraction of body\<close> |
46 |
46 |
47 text \<open>Syntax for nested abstractions\<close> |
47 text \<open>Syntax for nested abstractions\<close> |
48 |
48 |
49 syntax (ASCII) |
49 syntax (ASCII) |
55 parse_ast_translation \<open> |
55 parse_ast_translation \<open> |
56 (* rewrite (LAM x y z. t) => (_cabs x (_cabs y (_cabs z t))) *) |
56 (* rewrite (LAM x y z. t) => (_cabs x (_cabs y (_cabs z t))) *) |
57 (* cf. Syntax.lambda_ast_tr from src/Pure/Syntax/syn_trans.ML *) |
57 (* cf. Syntax.lambda_ast_tr from src/Pure/Syntax/syn_trans.ML *) |
58 let |
58 let |
59 fun Lambda_ast_tr [pats, body] = |
59 fun Lambda_ast_tr [pats, body] = |
60 Ast.fold_ast_p @{syntax_const "_cabs"} |
60 Ast.fold_ast_p \<^syntax_const>\<open>_cabs\<close> |
61 (Ast.unfold_ast @{syntax_const "_cargs"} (Ast.strip_positions pats), body) |
61 (Ast.unfold_ast \<^syntax_const>\<open>_cargs\<close> (Ast.strip_positions pats), body) |
62 | Lambda_ast_tr asts = raise Ast.AST ("Lambda_ast_tr", asts); |
62 | Lambda_ast_tr asts = raise Ast.AST ("Lambda_ast_tr", asts); |
63 in [(@{syntax_const "_Lambda"}, K Lambda_ast_tr)] end |
63 in [(\<^syntax_const>\<open>_Lambda\<close>, K Lambda_ast_tr)] end |
64 \<close> |
64 \<close> |
65 |
65 |
66 print_ast_translation \<open> |
66 print_ast_translation \<open> |
67 (* rewrite (_cabs x (_cabs y (_cabs z t))) => (LAM x y z. t) *) |
67 (* rewrite (_cabs x (_cabs y (_cabs z t))) => (LAM x y z. t) *) |
68 (* cf. Syntax.abs_ast_tr' from src/Pure/Syntax/syn_trans.ML *) |
68 (* cf. Syntax.abs_ast_tr' from src/Pure/Syntax/syn_trans.ML *) |
69 let |
69 let |
70 fun cabs_ast_tr' asts = |
70 fun cabs_ast_tr' asts = |
71 (case Ast.unfold_ast_p @{syntax_const "_cabs"} |
71 (case Ast.unfold_ast_p \<^syntax_const>\<open>_cabs\<close> |
72 (Ast.Appl (Ast.Constant @{syntax_const "_cabs"} :: asts)) of |
72 (Ast.Appl (Ast.Constant \<^syntax_const>\<open>_cabs\<close> :: asts)) of |
73 ([], _) => raise Ast.AST ("cabs_ast_tr'", asts) |
73 ([], _) => raise Ast.AST ("cabs_ast_tr'", asts) |
74 | (xs, body) => Ast.Appl |
74 | (xs, body) => Ast.Appl |
75 [Ast.Constant @{syntax_const "_Lambda"}, |
75 [Ast.Constant \<^syntax_const>\<open>_Lambda\<close>, |
76 Ast.fold_ast @{syntax_const "_cargs"} xs, body]); |
76 Ast.fold_ast \<^syntax_const>\<open>_cargs\<close> xs, body]); |
77 in [(@{syntax_const "_cabs"}, K cabs_ast_tr')] end |
77 in [(\<^syntax_const>\<open>_cabs\<close>, K cabs_ast_tr')] end |
78 \<close> |
78 \<close> |
79 |
79 |
80 text \<open>Dummy patterns for continuous abstraction\<close> |
80 text \<open>Dummy patterns for continuous abstraction\<close> |
81 translations |
81 translations |
82 "\<Lambda> _. t" \<rightharpoonup> "CONST Abs_cfun (\<lambda>_. t)" |
82 "\<Lambda> _. t" \<rightharpoonup> "CONST Abs_cfun (\<lambda>_. t)" |
124 |
124 |
125 |
125 |
126 subsubsection \<open>Beta-reduction simproc\<close> |
126 subsubsection \<open>Beta-reduction simproc\<close> |
127 |
127 |
128 text \<open> |
128 text \<open> |
129 Given the term @{term "(\<Lambda> x. f x)\<cdot>y"}, the procedure tries to |
129 Given the term \<^term>\<open>(\<Lambda> x. f x)\<cdot>y\<close>, the procedure tries to |
130 construct the theorem @{term "(\<Lambda> x. f x)\<cdot>y \<equiv> f y"}. If this |
130 construct the theorem \<^term>\<open>(\<Lambda> x. f x)\<cdot>y \<equiv> f y\<close>. If this |
131 theorem cannot be completely solved by the cont2cont rules, then |
131 theorem cannot be completely solved by the cont2cont rules, then |
132 the procedure returns the ordinary conditional \<open>beta_cfun\<close> |
132 the procedure returns the ordinary conditional \<open>beta_cfun\<close> |
133 rule. |
133 rule. |
134 |
134 |
135 The simproc does not solve any more goals that would be solved by |
135 The simproc does not solve any more goals that would be solved by |
196 lemmas monofun_Rep_cfun = cont_Rep_cfun [THEN cont2mono] |
196 lemmas monofun_Rep_cfun = cont_Rep_cfun [THEN cont2mono] |
197 |
197 |
198 lemmas monofun_Rep_cfun1 = cont_Rep_cfun1 [THEN cont2mono] |
198 lemmas monofun_Rep_cfun1 = cont_Rep_cfun1 [THEN cont2mono] |
199 lemmas monofun_Rep_cfun2 = cont_Rep_cfun2 [THEN cont2mono] |
199 lemmas monofun_Rep_cfun2 = cont_Rep_cfun2 [THEN cont2mono] |
200 |
200 |
201 text \<open>contlub, cont properties of @{term Rep_cfun} in each argument\<close> |
201 text \<open>contlub, cont properties of \<^term>\<open>Rep_cfun\<close> in each argument\<close> |
202 |
202 |
203 lemma contlub_cfun_arg: "chain Y \<Longrightarrow> f\<cdot>(\<Squnion>i. Y i) = (\<Squnion>i. f\<cdot>(Y i))" |
203 lemma contlub_cfun_arg: "chain Y \<Longrightarrow> f\<cdot>(\<Squnion>i. Y i) = (\<Squnion>i. f\<cdot>(Y i))" |
204 by (rule cont_Rep_cfun2 [THEN cont2contlubE]) |
204 by (rule cont_Rep_cfun2 [THEN cont2contlubE]) |
205 |
205 |
206 lemma contlub_cfun_fun: "chain F \<Longrightarrow> (\<Squnion>i. F i)\<cdot>x = (\<Squnion>i. F i\<cdot>x)" |
206 lemma contlub_cfun_fun: "chain F \<Longrightarrow> (\<Squnion>i. F i)\<cdot>x = (\<Squnion>i. F i\<cdot>x)" |
215 by (rule monofun_Rep_cfun2 [THEN monofunE]) |
215 by (rule monofun_Rep_cfun2 [THEN monofunE]) |
216 |
216 |
217 lemma monofun_cfun: "f \<sqsubseteq> g \<Longrightarrow> x \<sqsubseteq> y \<Longrightarrow> f\<cdot>x \<sqsubseteq> g\<cdot>y" |
217 lemma monofun_cfun: "f \<sqsubseteq> g \<Longrightarrow> x \<sqsubseteq> y \<Longrightarrow> f\<cdot>x \<sqsubseteq> g\<cdot>y" |
218 by (rule below_trans [OF monofun_cfun_fun monofun_cfun_arg]) |
218 by (rule below_trans [OF monofun_cfun_fun monofun_cfun_arg]) |
219 |
219 |
220 text \<open>ch2ch - rules for the type @{typ "'a \<rightarrow> 'b"}\<close> |
220 text \<open>ch2ch - rules for the type \<^typ>\<open>'a \<rightarrow> 'b\<close>\<close> |
221 |
221 |
222 lemma chain_monofun: "chain Y \<Longrightarrow> chain (\<lambda>i. f\<cdot>(Y i))" |
222 lemma chain_monofun: "chain Y \<Longrightarrow> chain (\<lambda>i. f\<cdot>(Y i))" |
223 by (erule monofun_Rep_cfun2 [THEN ch2ch_monofun]) |
223 by (erule monofun_Rep_cfun2 [THEN ch2ch_monofun]) |
224 |
224 |
225 lemma ch2ch_Rep_cfunR: "chain Y \<Longrightarrow> chain (\<lambda>i. f\<cdot>(Y i))" |
225 lemma ch2ch_Rep_cfunR: "chain Y \<Longrightarrow> chain (\<lambda>i. f\<cdot>(Y i))" |
233 |
233 |
234 lemma ch2ch_LAM [simp]: |
234 lemma ch2ch_LAM [simp]: |
235 "(\<And>x. chain (\<lambda>i. S i x)) \<Longrightarrow> (\<And>i. cont (\<lambda>x. S i x)) \<Longrightarrow> chain (\<lambda>i. \<Lambda> x. S i x)" |
235 "(\<And>x. chain (\<lambda>i. S i x)) \<Longrightarrow> (\<And>i. cont (\<lambda>x. S i x)) \<Longrightarrow> chain (\<lambda>i. \<Lambda> x. S i x)" |
236 by (simp add: chain_def cfun_below_iff) |
236 by (simp add: chain_def cfun_below_iff) |
237 |
237 |
238 text \<open>contlub, cont properties of @{term Rep_cfun} in both arguments\<close> |
238 text \<open>contlub, cont properties of \<^term>\<open>Rep_cfun\<close> in both arguments\<close> |
239 |
239 |
240 lemma lub_APP: "chain F \<Longrightarrow> chain Y \<Longrightarrow> (\<Squnion>i. F i\<cdot>(Y i)) = (\<Squnion>i. F i)\<cdot>(\<Squnion>i. Y i)" |
240 lemma lub_APP: "chain F \<Longrightarrow> chain Y \<Longrightarrow> (\<Squnion>i. F i\<cdot>(Y i)) = (\<Squnion>i. F i)\<cdot>(\<Squnion>i. Y i)" |
241 by (simp add: contlub_cfun_fun contlub_cfun_arg diag_lub) |
241 by (simp add: contlub_cfun_fun contlub_cfun_arg diag_lub) |
242 |
242 |
243 lemma lub_LAM: |
243 lemma lub_LAM: |
254 apply (rule bottomI) |
254 apply (rule bottomI) |
255 apply (erule subst) |
255 apply (erule subst) |
256 apply (rule minimal [THEN monofun_cfun_arg]) |
256 apply (rule minimal [THEN monofun_cfun_arg]) |
257 done |
257 done |
258 |
258 |
259 text \<open>type @{typ "'a \<rightarrow> 'b"} is chain complete\<close> |
259 text \<open>type \<^typ>\<open>'a \<rightarrow> 'b\<close> is chain complete\<close> |
260 |
260 |
261 lemma lub_cfun: "chain F \<Longrightarrow> (\<Squnion>i. F i) = (\<Lambda> x. \<Squnion>i. F i\<cdot>x)" |
261 lemma lub_cfun: "chain F \<Longrightarrow> (\<Squnion>i. F i) = (\<Lambda> x. \<Squnion>i. F i\<cdot>x)" |
262 by (simp add: lub_cfun lub_fun ch2ch_lambda) |
262 by (simp add: lub_cfun lub_fun ch2ch_lambda) |
263 |
263 |
264 |
264 |
265 subsection \<open>Continuity simplification procedure\<close> |
265 subsection \<open>Continuity simplification procedure\<close> |
266 |
266 |
267 text \<open>cont2cont lemma for @{term Rep_cfun}\<close> |
267 text \<open>cont2cont lemma for \<^term>\<open>Rep_cfun\<close>\<close> |
268 |
268 |
269 lemma cont2cont_APP [simp, cont2cont]: |
269 lemma cont2cont_APP [simp, cont2cont]: |
270 assumes f: "cont (\<lambda>x. f x)" |
270 assumes f: "cont (\<lambda>x. f x)" |
271 assumes t: "cont (\<lambda>x. t x)" |
271 assumes t: "cont (\<lambda>x. t x)" |
272 shows "cont (\<lambda>x. (f x)\<cdot>(t x))" |
272 shows "cont (\<lambda>x. (f x)\<cdot>(t x))" |
277 by (rule cont_apply) |
277 by (rule cont_apply) |
278 qed |
278 qed |
279 |
279 |
280 text \<open> |
280 text \<open> |
281 Two specific lemmas for the combination of LCF and HOL terms. |
281 Two specific lemmas for the combination of LCF and HOL terms. |
282 These lemmas are needed in theories that use types like @{typ "'a \<rightarrow> 'b \<Rightarrow> 'c"}. |
282 These lemmas are needed in theories that use types like \<^typ>\<open>'a \<rightarrow> 'b \<Rightarrow> 'c\<close>. |
283 \<close> |
283 \<close> |
284 |
284 |
285 lemma cont_APP_app [simp]: "cont f \<Longrightarrow> cont g \<Longrightarrow> cont (\<lambda>x. ((f x)\<cdot>(g x)) s)" |
285 lemma cont_APP_app [simp]: "cont f \<Longrightarrow> cont g \<Longrightarrow> cont (\<lambda>x. ((f x)\<cdot>(g x)) s)" |
286 by (rule cont2cont_APP [THEN cont2cont_fun]) |
286 by (rule cont2cont_APP [THEN cont2cont_fun]) |
287 |
287 |
288 lemma cont_APP_app_app [simp]: "cont f \<Longrightarrow> cont g \<Longrightarrow> cont (\<lambda>x. ((f x)\<cdot>(g x)) s t)" |
288 lemma cont_APP_app_app [simp]: "cont f \<Longrightarrow> cont g \<Longrightarrow> cont (\<lambda>x. ((f x)\<cdot>(g x)) s t)" |
289 by (rule cont_APP_app [THEN cont2cont_fun]) |
289 by (rule cont_APP_app [THEN cont2cont_fun]) |
290 |
290 |
291 |
291 |
292 text \<open>cont2mono Lemma for @{term "\<lambda>x. LAM y. c1(x)(y)"}\<close> |
292 text \<open>cont2mono Lemma for \<^term>\<open>\<lambda>x. LAM y. c1(x)(y)\<close>\<close> |
293 |
293 |
294 lemma cont2mono_LAM: |
294 lemma cont2mono_LAM: |
295 "\<lbrakk>\<And>x. cont (\<lambda>y. f x y); \<And>y. monofun (\<lambda>x. f x y)\<rbrakk> |
295 "\<lbrakk>\<And>x. cont (\<lambda>y. f x y); \<And>y. monofun (\<lambda>x. f x y)\<rbrakk> |
296 \<Longrightarrow> monofun (\<lambda>x. \<Lambda> y. f x y)" |
296 \<Longrightarrow> monofun (\<lambda>x. \<Lambda> y. f x y)" |
297 by (simp add: monofun_def cfun_below_iff) |
297 by (simp add: monofun_def cfun_below_iff) |
298 |
298 |
299 text \<open>cont2cont Lemma for @{term "\<lambda>x. LAM y. f x y"}\<close> |
299 text \<open>cont2cont Lemma for \<^term>\<open>\<lambda>x. LAM y. f x y\<close>\<close> |
300 |
300 |
301 text \<open> |
301 text \<open> |
302 Not suitable as a cont2cont rule, because on nested lambdas |
302 Not suitable as a cont2cont rule, because on nested lambdas |
303 it causes exponential blow-up in the number of subgoals. |
303 it causes exponential blow-up in the number of subgoals. |
304 \<close> |
304 \<close> |
330 by (simp add: cont2cont_LAM) |
330 by (simp add: cont2cont_LAM) |
331 |
331 |
332 |
332 |
333 subsection \<open>Miscellaneous\<close> |
333 subsection \<open>Miscellaneous\<close> |
334 |
334 |
335 text \<open>Monotonicity of @{term Abs_cfun}\<close> |
335 text \<open>Monotonicity of \<^term>\<open>Abs_cfun\<close>\<close> |
336 |
336 |
337 lemma monofun_LAM: "cont f \<Longrightarrow> cont g \<Longrightarrow> (\<And>x. f x \<sqsubseteq> g x) \<Longrightarrow> (\<Lambda> x. f x) \<sqsubseteq> (\<Lambda> x. g x)" |
337 lemma monofun_LAM: "cont f \<Longrightarrow> cont g \<Longrightarrow> (\<And>x. f x \<sqsubseteq> g x) \<Longrightarrow> (\<Lambda> x. f x) \<sqsubseteq> (\<Lambda> x. g x)" |
338 by (simp add: cfun_below_iff) |
338 by (simp add: cfun_below_iff) |
339 |
339 |
340 text \<open>some lemmata for functions with flat/chfin domain/range types\<close> |
340 text \<open>some lemmata for functions with flat/chfin domain/range types\<close> |
433 by (simp add: cfun_eq_iff) |
433 by (simp add: cfun_eq_iff) |
434 |
434 |
435 text \<open> |
435 text \<open> |
436 Show that interpretation of (pcpo, \<open>_\<rightarrow>_\<close>) is a category. |
436 Show that interpretation of (pcpo, \<open>_\<rightarrow>_\<close>) is a category. |
437 \<^item> The class of objects is interpretation of syntactical class pcpo. |
437 \<^item> The class of objects is interpretation of syntactical class pcpo. |
438 \<^item> The class of arrows between objects @{typ 'a} and @{typ 'b} is interpret. of @{typ "'a \<rightarrow> 'b"}. |
438 \<^item> The class of arrows between objects \<^typ>\<open>'a\<close> and \<^typ>\<open>'b\<close> is interpret. of \<^typ>\<open>'a \<rightarrow> 'b\<close>. |
439 \<^item> The identity arrow is interpretation of @{term ID}. |
439 \<^item> The identity arrow is interpretation of \<^term>\<open>ID\<close>. |
440 \<^item> The composition of f and g is interpretation of \<open>oo\<close>. |
440 \<^item> The composition of f and g is interpretation of \<open>oo\<close>. |
441 \<close> |
441 \<close> |
442 |
442 |
443 lemma ID2 [simp]: "f oo ID = f" |
443 lemma ID2 [simp]: "f oo ID = f" |
444 by (rule cfun_eqI, simp) |
444 by (rule cfun_eqI, simp) |