src/HOL/HOLCF/Cfun.thy
changeset 69597 ff784d5a5bfb
parent 69216 1a52baa70aed
child 78099 4d9349989d94
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    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)