src/HOL/Library/conditional_parametricity.ML
changeset 69593 3dda49e08b9d
parent 67649 1e1782c1aedf
child 74545 6c123914883a
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   123     val assume = [asm_rl];
   123     val assume = [asm_rl];
   124     fun find_and_rotate_tac t i =
   124     fun find_and_rotate_tac t i =
   125       let
   125       let
   126         fun is_correct_rule t =
   126         fun is_correct_rule t =
   127           (case t of
   127           (case t of
   128             Const (@{const_name "HOL.Trueprop"}, _) $ (Const (@{const_name "Transfer.Rel"}, _) $
   128             Const (\<^const_name>\<open>HOL.Trueprop\<close>, _) $ (Const (\<^const_name>\<open>Transfer.Rel\<close>, _) $
   129               _ $ Bound x' $ Bound y') => x = x' andalso y = y'
   129               _ $ Bound x' $ Bound y') => x = x' andalso y = y'
   130           | _ => false);
   130           | _ => false);
   131         val idx = find_index is_correct_rule (t |> Logic.strip_assums_hyp);
   131         val idx = find_index is_correct_rule (t |> Logic.strip_assums_hyp);
   132       in
   132       in
   133         if idx < 0 then no_tac else rotate_tac idx i
   133         if idx < 0 then no_tac else rotate_tac idx i
   184 
   184 
   185 fun rel_abs_tac ctxt = resolve_tac ctxt [@{thm Rel_abs}];
   185 fun rel_abs_tac ctxt = resolve_tac ctxt [@{thm Rel_abs}];
   186 
   186 
   187 fun step_tac' settings ctxt parametricity_thms (tm, i) =
   187 fun step_tac' settings ctxt parametricity_thms (tm, i) =
   188   (case tm |> Logic.strip_assums_concl of
   188   (case tm |> Logic.strip_assums_concl of
   189     Const (@{const_name "HOL.Trueprop"}, _) $ (Const (rel, _) $ _ $ t $ u) =>
   189     Const (\<^const_name>\<open>HOL.Trueprop\<close>, _) $ (Const (rel, _) $ _ $ t $ u) =>
   190     let
   190     let
   191       val (arity_of_t, arity_of_u) = apply2 (strip_comb #> snd #> length) (t, u);
   191       val (arity_of_t, arity_of_u) = apply2 (strip_comb #> snd #> length) (t, u);
   192     in
   192     in
   193       (case rel of
   193       (case rel of
   194         @{const_name "Transfer.Rel"} =>
   194         \<^const_name>\<open>Transfer.Rel\<close> =>
   195           (case (head_of t, head_of u) of
   195           (case (head_of t, head_of u) of
   196             (Abs _, _) => rel_abs_tac ctxt
   196             (Abs _, _) => rel_abs_tac ctxt
   197           | (_, Abs _) => rel_abs_tac ctxt
   197           | (_, Abs _) => rel_abs_tac ctxt
   198           | (const as (Const _), const' as (Const _)) =>
   198           | (const as (Const _), const' as (Const _)) =>
   199             if #use_equality_heuristic settings andalso t aconv u
   199             if #use_equality_heuristic settings andalso t aconv u
   208             if arity_of_t = arity_of_u then if arity_of_t > 0 then rel_app_tac ctxt tm x y arity_of_t
   208             if arity_of_t = arity_of_u then if arity_of_t > 0 then rel_app_tac ctxt tm x y arity_of_t
   209                else assume_tac ctxt
   209                else assume_tac ctxt
   210             else  error_tac' ctxt "Malformed term. Arities of t and u don't match."
   210             else  error_tac' ctxt "Malformed term. Arities of t and u don't match."
   211           | _ => error_tac' ctxt
   211           | _ => error_tac' ctxt
   212             "Unexpected format. Expected  (Abs _, _), (_, Abs _), (Const _, Const _) or (Bound _, Bound _).")
   212             "Unexpected format. Expected  (Abs _, _), (_, Abs _), (Const _, Const _) or (Bound _, Bound _).")
   213          | @{const_name "Conditional_Parametricity.Rel_match"} =>
   213          | \<^const_name>\<open>Conditional_Parametricity.Rel_match\<close> =>
   214              parametricity_thm_match_tac ctxt parametricity_thms arity_of_t
   214              parametricity_thm_match_tac ctxt parametricity_thms arity_of_t
   215       | _ => error_tac' ctxt "Unexpected format. Expected Transfer.Rel or Rel_match marker." ) i
   215       | _ => error_tac' ctxt "Unexpected format. Expected Transfer.Rel or Rel_match marker." ) i
   216     end
   216     end
   217     | Const (@{const_name "HOL.Trueprop"}, _) $ (Const (@{const_name "Transfer.is_equality"}, _) $ _) =>
   217     | Const (\<^const_name>\<open>HOL.Trueprop\<close>, _) $ (Const (\<^const_name>\<open>Transfer.is_equality\<close>, _) $ _) =>
   218         Transfer.eq_tac ctxt i
   218         Transfer.eq_tac ctxt i
   219     | _ => error_tac' ctxt "Unexpected format. Not of form Const (HOL.Trueprop, _) $ _" i);
   219     | _ => error_tac' ctxt "Unexpected format. Not of form Const (HOL.Trueprop, _) $ _" i);
   220 
   220 
   221 fun step_tac settings = SUBGOAL oo step_tac' settings;
   221 fun step_tac settings = SUBGOAL oo step_tac' settings;
   222 
   222 
   225     assume_tac ctxt);
   225     assume_tac ctxt);
   226 
   226 
   227 (* Goal Generation  *)
   227 (* Goal Generation  *)
   228 fun strip_boundvars_from_rel_match t =
   228 fun strip_boundvars_from_rel_match t =
   229   (case t of
   229   (case t of
   230     (Tp as Const (@{const_name "HOL.Trueprop"}, _)) $
   230     (Tp as Const (\<^const_name>\<open>HOL.Trueprop\<close>, _)) $
   231       ((Rm as Const (@{const_name "Conditional_Parametricity.Rel_match"}, _)) $ R $ t $ t') =>
   231       ((Rm as Const (\<^const_name>\<open>Conditional_Parametricity.Rel_match\<close>, _)) $ R $ t $ t') =>
   232         Tp $ (Rm $ apply_Var_to_bounds R $ t $ t')
   232         Tp $ (Rm $ apply_Var_to_bounds R $ t $ t')
   233   | _ => t);
   233   | _ => t);
   234 
   234 
   235 val extract_conditions =
   235 val extract_conditions =
   236   let
   236   let
   249     val tvars = Term.add_tvars t [];
   249     val tvars = Term.add_tvars t [];
   250     val new_frees = map TFree (Term.variant_frees t (map tvar_to_tfree tvars));
   250     val new_frees = map TFree (Term.variant_frees t (map tvar_to_tfree tvars));
   251     val u = subst_atomic_types ((map TVar tvars) ~~ new_frees) t;
   251     val u = subst_atomic_types ((map TVar tvars) ~~ new_frees) t;
   252     val T = fastype_of t;
   252     val T = fastype_of t;
   253     val U = fastype_of u;
   253     val U = fastype_of u;
   254     val R = [T,U] ---> @{typ bool}
   254     val R = [T,U] ---> \<^typ>\<open>bool\<close>
   255     val r = Var (("R", 2 * i), R);
   255     val r = Var (("R", 2 * i), R);
   256     val transfer_rel = Const (@{const_name "Transfer.Rel"}, [R,T,U] ---> @{typ bool});
   256     val transfer_rel = Const (\<^const_name>\<open>Transfer.Rel\<close>, [R,T,U] ---> \<^typ>\<open>bool\<close>);
   257   in HOLogic.mk_Trueprop (transfer_rel $ r $ t $ u) end;
   257   in HOLogic.mk_Trueprop (transfer_rel $ r $ t $ u) end;
   258 
   258 
   259 fun mk_abs_helper T t =
   259 fun mk_abs_helper T t =
   260   let
   260   let
   261     val U = fastype_of t;
   261     val U = fastype_of t;
   292 
   292 
   293 fun mk_param_goal_from_eq_def ctxt thm =
   293 fun mk_param_goal_from_eq_def ctxt thm =
   294   let
   294   let
   295     val t =
   295     val t =
   296       (case Thm.full_prop_of thm of
   296       (case Thm.full_prop_of thm of
   297         (Const (@{const_name "Pure.eq"}, _) $ t' $ _) => t'
   297         (Const (\<^const_name>\<open>Pure.eq\<close>, _) $ t' $ _) => t'
   298       | _ => theorem_format_error ctxt thm);
   298       | _ => theorem_format_error ctxt thm);
   299   in mk_goal ctxt t end;
   299   in mk_goal ctxt t end;
   300 
   300 
   301 (* Transformations and parametricity theorems *)
   301 (* Transformations and parametricity theorems *)
   302 fun transform_class_rule ctxt thm =
   302 fun transform_class_rule ctxt thm =
   303   (case Thm.concl_of thm of
   303   (case Thm.concl_of thm of
   304     Const (@{const_name "HOL.Trueprop"}, _) $ (Const (@{const_name "Transfer.Rel"}, _) $ _ $ t $ u ) =>
   304     Const (\<^const_name>\<open>HOL.Trueprop\<close>, _) $ (Const (\<^const_name>\<open>Transfer.Rel\<close>, _) $ _ $ t $ u ) =>
   305       (if curry Term.aconv_untyped t u andalso is_class_op ctxt t then
   305       (if curry Term.aconv_untyped t u andalso is_class_op ctxt t then
   306         thm RS @{thm Rel_Rel_match}
   306         thm RS @{thm Rel_Rel_match}
   307       else thm)
   307       else thm)
   308   | _ => thm);
   308   | _ => thm);
   309 
   309 
   310 fun is_parametricity_theorem thm =
   310 fun is_parametricity_theorem thm =
   311   (case Thm.concl_of thm of
   311   (case Thm.concl_of thm of
   312     Const (@{const_name "HOL.Trueprop"}, _) $ (Const (rel, _) $ _ $ t $ u ) =>
   312     Const (\<^const_name>\<open>HOL.Trueprop\<close>, _) $ (Const (rel, _) $ _ $ t $ u ) =>
   313       if rel = @{const_name "Transfer.Rel"} orelse
   313       if rel = \<^const_name>\<open>Transfer.Rel\<close> orelse
   314         rel = @{const_name "Conditional_Parametricity.Rel_match"}
   314         rel = \<^const_name>\<open>Conditional_Parametricity.Rel_match\<close>
   315       then curry Term.aconv_untyped t u
   315       then curry Term.aconv_untyped t u
   316       else false
   316       else false
   317   | _ => false);
   317   | _ => false);
   318 
   318 
   319 (* Pre- and postprocessing of theorems *)
   319 (* Pre- and postprocessing of theorems *)
   320 fun mk_Domainp_assm (T, R) =
   320 fun mk_Domainp_assm (T, R) =
   321   HOLogic.mk_eq ((Const (@{const_name Domainp}, Term.fastype_of T --> Term.fastype_of R) $ T), R);
   321   HOLogic.mk_eq ((Const (\<^const_name>\<open>Domainp\<close>, Term.fastype_of T --> Term.fastype_of R) $ T), R);
   322 
   322 
   323 val Domainp_lemma =
   323 val Domainp_lemma =
   324   @{lemma "(!!R. Domainp T = R ==> PROP (P R)) == PROP (P (Domainp T))"
   324   @{lemma "(!!R. Domainp T = R ==> PROP (P R)) == PROP (P (Domainp T))"
   325     by (rule, drule meta_spec,
   325     by (rule, drule meta_spec,
   326       erule meta_mp, rule HOL.refl, simp)};
   326       erule meta_mp, rule HOL.refl, simp)};
   327 
   327 
   328 fun fold_Domainp f (t as Const (@{const_name Domainp},_) $ (Var (_,_))) = f t
   328 fun fold_Domainp f (t as Const (\<^const_name>\<open>Domainp\<close>,_) $ (Var (_,_))) = f t
   329   | fold_Domainp f (t $ u) = fold_Domainp f t #> fold_Domainp f u
   329   | fold_Domainp f (t $ u) = fold_Domainp f t #> fold_Domainp f u
   330   | fold_Domainp f (Abs (_, _, t)) = fold_Domainp f t
   330   | fold_Domainp f (Abs (_, _, t)) = fold_Domainp f t
   331   | fold_Domainp _ _ = I;
   331   | fold_Domainp _ _ = I;
   332 
   332 
   333 fun subst_terms tab t =
   333 fun subst_terms tab t =
   385   Conv.concl_conv ~1 (HOLogic.Trueprop_conv (Conv.fun2_conv (Conv.arg_conv conv)));
   385   Conv.concl_conv ~1 (HOLogic.Trueprop_conv (Conv.fun2_conv (Conv.arg_conv conv)));
   386 
   386 
   387 fun fold_relator_eqs_conv ctxt ct = (Transfer.bottom_rewr_conv (Transfer.get_relator_eq ctxt)) ct;
   387 fun fold_relator_eqs_conv ctxt ct = (Transfer.bottom_rewr_conv (Transfer.get_relator_eq ctxt)) ct;
   388 
   388 
   389 fun mk_is_equality t =
   389 fun mk_is_equality t =
   390   Const (@{const_name is_equality}, Term.fastype_of t --> HOLogic.boolT) $ t;
   390   Const (\<^const_name>\<open>is_equality\<close>, Term.fastype_of t --> HOLogic.boolT) $ t;
   391 
   391 
   392 val is_equality_lemma =
   392 val is_equality_lemma =
   393   @{lemma "(!!R. is_equality R ==> PROP (P R)) == PROP (P (=))"
   393   @{lemma "(!!R. is_equality R ==> PROP (P R)) == PROP (P (=))"
   394     by (unfold is_equality_def, rule, drule meta_spec,
   394     by (unfold is_equality_def, rule, drule meta_spec,
   395       erule meta_mp, rule HOL.refl, simp)};
   395       erule meta_mp, rule HOL.refl, simp)};
   397 fun gen_abstract_equalities ctxt (dest : term -> term * (term -> term)) thm =
   397 fun gen_abstract_equalities ctxt (dest : term -> term * (term -> term)) thm =
   398   let
   398   let
   399     val prop = Thm.prop_of thm
   399     val prop = Thm.prop_of thm
   400     val (t, mk_prop') = dest prop
   400     val (t, mk_prop') = dest prop
   401     (* Only consider "(=)" at non-base types *)
   401     (* Only consider "(=)" at non-base types *)
   402     fun is_eq (Const (@{const_name HOL.eq}, Type ("fun", [T, _]))) =
   402     fun is_eq (Const (\<^const_name>\<open>HOL.eq\<close>, Type ("fun", [T, _]))) =
   403         (case T of Type (_, []) => false | _ => true)
   403         (case T of Type (_, []) => false | _ => true)
   404       | is_eq _ = false
   404       | is_eq _ = false
   405     val add_eqs = Term.fold_aterms (fn t => if is_eq t then insert (op =) t else I)
   405     val add_eqs = Term.fold_aterms (fn t => if is_eq t then insert (op =) t else I)
   406     val eq_consts = rev (add_eqs t [])
   406     val eq_consts = rev (add_eqs t [])
   407     val eqTs = map (snd o dest_Const) eq_consts
   407     val eqTs = map (snd o dest_Const) eq_consts
   438   end;
   438   end;
   439 
   439 
   440 fun prep_rule ctxt = abstract_equalities_transfer ctxt #> abstract_domains_transfer ctxt;
   440 fun prep_rule ctxt = abstract_equalities_transfer ctxt #> abstract_domains_transfer ctxt;
   441 
   441 
   442 fun get_preprocess_theorems ctxt =
   442 fun get_preprocess_theorems ctxt =
   443   Named_Theorems.get ctxt @{named_theorems parametricity_preprocess};
   443   Named_Theorems.get ctxt \<^named_theorems>\<open>parametricity_preprocess\<close>;
   444 
   444 
   445 fun preprocess_theorem ctxt =
   445 fun preprocess_theorem ctxt =
   446   Local_Defs.unfold0 ctxt (get_preprocess_theorems ctxt)
   446   Local_Defs.unfold0 ctxt (get_preprocess_theorems ctxt)
   447   #> transform_class_rule ctxt;
   447   #> transform_class_rule ctxt;
   448 
   448 
   511 
   511 
   512 val parametric_constant_cmd = snd oo gen_parametric_constant default_settings (Attrib.check_src)
   512 val parametric_constant_cmd = snd oo gen_parametric_constant default_settings (Attrib.check_src)
   513   (singleton o Attrib.eval_thms);
   513   (singleton o Attrib.eval_thms);
   514 
   514 
   515 val _ =
   515 val _ =
   516   Outer_Syntax.local_theory @{command_keyword parametric_constant} "proves parametricity"
   516   Outer_Syntax.local_theory \<^command_keyword>\<open>parametric_constant\<close> "proves parametricity"
   517     ((Parse_Spec.opt_thm_name ":" -- Parse.thm) >> parametric_constant_cmd);
   517     ((Parse_Spec.opt_thm_name ":" -- Parse.thm) >> parametric_constant_cmd);
   518 
   518 
   519 end;
   519 end;