use the same code for extensionalization in Metis and Sledgehammer and generalize that code so that it gracefully handles negations (e.g. negated conjecture), formulas of the form (%x. t) = u, etc.
authorblanchet
Thu May 12 15:29:19 2011 +0200 (2011-05-12)
changeset 42747f132d13fcf75
parent 42746 7e227e9de779
child 42748 a37095d03074
use the same code for extensionalization in Metis and Sledgehammer and generalize that code so that it gracefully handles negations (e.g. negated conjecture), formulas of the form (%x. t) = u, etc.
src/HOL/Metis_Examples/Clausify.thy
src/HOL/Tools/Meson/meson.ML
src/HOL/Tools/Meson/meson_clausify.ML
src/HOL/Tools/Metis/metis_tactics.ML
src/HOL/Tools/Sledgehammer/sledgehammer_atp_translate.ML
     1.1 --- a/src/HOL/Metis_Examples/Clausify.thy	Thu May 12 15:29:19 2011 +0200
     1.2 +++ b/src/HOL/Metis_Examples/Clausify.thy	Thu May 12 15:29:19 2011 +0200
     1.3 @@ -12,6 +12,37 @@
     1.4  declare [[unify_search_bound = 100]]
     1.5  declare [[unify_trace_bound = 100]]
     1.6  
     1.7 +sledgehammer_params [prover = e, blocking, timeout = 10]
     1.8 +
     1.9 +
    1.10 +text {* Extensionality *}
    1.11 +
    1.12 +lemma plus_1_not_0: "n + (1\<Colon>nat) \<noteq> 0"
    1.13 +by simp
    1.14 +
    1.15 +definition inc :: "nat \<Rightarrow> nat" where
    1.16 +"inc x = x + 1"
    1.17 +
    1.18 +lemma "inc \<noteq> (\<lambda>y. 0)"
    1.19 +sledgehammer [expect = some] (inc_def plus_1_not_0)
    1.20 +by (metis inc_def plus_1_not_0)
    1.21 +
    1.22 +lemma "inc = (\<lambda>y. y + 1)"
    1.23 +sledgehammer [expect = some] (inc_def)
    1.24 +by (metis inc_def)
    1.25 +
    1.26 +lemma "(\<lambda>y. y + 1) = inc"
    1.27 +sledgehammer [expect = some] (inc_def)
    1.28 +by (metis inc_def)
    1.29 +
    1.30 +definition add_swap :: "nat \<Rightarrow> nat \<Rightarrow> nat" where
    1.31 +"add_swap = (\<lambda>x y. y + x)"
    1.32 +
    1.33 +lemma "add_swap m n = n + m"
    1.34 +sledgehammer [expect = some] (add_swap_def)
    1.35 +by (metis add_swap_def)
    1.36 +
    1.37 +
    1.38  text {* Definitional CNF for facts *}
    1.39  
    1.40  declare [[meson_max_clauses = 10]]
    1.41 @@ -83,6 +114,7 @@
    1.42         (r 3 0 \<and> r 3 1 \<and> r 3 2 \<and> r 3 3)"
    1.43  by (metisFT rax)
    1.44  
    1.45 +
    1.46  text {* Definitional CNF for goal *}
    1.47  
    1.48  axiomatization p :: "nat \<Rightarrow> nat \<Rightarrow> bool" where
    1.49 @@ -108,6 +140,7 @@
    1.50                     (p 0 1 \<or> \<not> x) \<and> (p 1 0 \<or> \<not> x) \<and> (p a b \<or> \<not> x)"
    1.51  by (metisFT pax)
    1.52  
    1.53 +
    1.54  text {* New Skolemizer *}
    1.55  
    1.56  declare [[metis_new_skolemizer]]
     2.1 --- a/src/HOL/Tools/Meson/meson.ML	Thu May 12 15:29:19 2011 +0200
     2.2 +++ b/src/HOL/Tools/Meson/meson.ML	Thu May 12 15:29:19 2011 +0200
     2.3 @@ -22,6 +22,8 @@
     2.4    val choice_theorems : theory -> thm list
     2.5    val skolemize_with_choice_theorems : Proof.context -> thm list -> thm -> thm
     2.6    val skolemize : Proof.context -> thm -> thm
     2.7 +  val extensionalize_conv : Proof.context -> conv
     2.8 +  val extensionalize_theorem : Proof.context -> thm -> thm
     2.9    val is_fol_term: theory -> term -> bool
    2.10    val make_clauses_unsorted: thm list -> thm list
    2.11    val make_clauses: thm list -> thm list
    2.12 @@ -610,12 +612,37 @@
    2.13      skolemize_with_choice_theorems ctxt (choice_theorems thy)
    2.14    end
    2.15  
    2.16 +fun is_Abs (Abs _) = true
    2.17 +  | is_Abs _ = false
    2.18 +
    2.19 +(* Removes the lambdas from an equation of the form "t = (%x. u)".  *)
    2.20 +fun extensionalize_conv ctxt ct =
    2.21 +  case term_of ct of
    2.22 +    Const (@{const_name HOL.eq}, _) $ t1 $ t2 =>
    2.23 +    ct |> (if is_Abs t1 orelse is_Abs t2 then
    2.24 +             Conv.rewr_conv @{thm fun_eq_iff [THEN eq_reflection]}
    2.25 +             then_conv extensionalize_conv ctxt
    2.26 +           else
    2.27 +             Conv.comb_conv (extensionalize_conv ctxt))
    2.28 +  | _ $ _ => Conv.comb_conv (extensionalize_conv ctxt) ct
    2.29 +  | Abs _ => Conv.abs_conv (extensionalize_conv o snd) ctxt ct
    2.30 +  | _ => Conv.all_conv ct
    2.31 +
    2.32 +val extensionalize_theorem = Conv.fconv_rule o extensionalize_conv
    2.33 +
    2.34  (* "RS" can fail if "unify_search_bound" is too small. *)
    2.35 -fun try_skolemize ctxt th =
    2.36 -  try (skolemize ctxt) th
    2.37 -  |> tap (fn NONE => trace_msg ctxt (fn () => "Failed to skolemize " ^
    2.38 -                                              Display.string_of_thm ctxt th)
    2.39 -           | _ => ())
    2.40 +fun try_skolemize_etc ctxt =
    2.41 +  Raw_Simplifier.rewrite_rule (unfold_set_const_simps ctxt)
    2.42 +  (* Extensionalize "th", because that makes sense and that's what Sledgehammer
    2.43 +     does, but also keep an unextensionalized version of "th" for backward
    2.44 +     compatibility. *)
    2.45 +  #> (fn th => insert Thm.eq_thm_prop (extensionalize_theorem ctxt th) [th])
    2.46 +  #> map_filter (fn th => try (skolemize ctxt) th
    2.47 +                          |> tap (fn NONE =>
    2.48 +                                     trace_msg ctxt (fn () =>
    2.49 +                                         "Failed to skolemize " ^
    2.50 +                                          Display.string_of_thm ctxt th)
    2.51 +                                   | _ => ()))
    2.52  
    2.53  fun add_clauses th cls =
    2.54    let val ctxt0 = Variable.global_thm_context th
    2.55 @@ -645,7 +672,7 @@
    2.56  fun gocls cls = name_thms "Goal#" (map make_goal (neg_clauses cls));
    2.57  
    2.58  fun skolemize_prems_tac ctxt prems =
    2.59 -  cut_facts_tac (map_filter (try_skolemize ctxt) prems) THEN' REPEAT o etac exE
    2.60 +  cut_facts_tac (maps (try_skolemize_etc ctxt) prems) THEN' REPEAT o etac exE
    2.61  
    2.62  (*Basis of all meson-tactics.  Supplies cltac with clauses: HOL disjunctions.
    2.63    Function mkcl converts theorems to clauses.*)
     3.1 --- a/src/HOL/Tools/Meson/meson_clausify.ML	Thu May 12 15:29:19 2011 +0200
     3.2 +++ b/src/HOL/Tools/Meson/meson_clausify.ML	Thu May 12 15:29:19 2011 +0200
     3.3 @@ -10,7 +10,6 @@
     3.4    val new_skolem_var_prefix : string
     3.5    val new_nonskolem_var_prefix : string
     3.6    val is_zapped_var_name : string -> bool
     3.7 -  val extensionalize_theorem : thm -> thm
     3.8    val introduce_combinators_in_cterm : cterm -> thm
     3.9    val introduce_combinators_in_theorem : thm -> thm
    3.10    val cluster_of_zapped_var_name : string -> (int * (int * int)) * bool
    3.11 @@ -87,16 +86,6 @@
    3.12  
    3.13  (**** REPLACING ABSTRACTIONS BY COMBINATORS ****)
    3.14  
    3.15 -val fun_cong_all = @{thm fun_eq_iff [THEN iffD1]}
    3.16 -
    3.17 -(* Removes the lambdas from an equation of the form "t = (%x. u)".
    3.18 -   (Cf. "extensionalize_term" in "Sledgehammer_Translate".) *)
    3.19 -fun extensionalize_theorem th =
    3.20 -  case prop_of th of
    3.21 -    _ $ (Const (@{const_name HOL.eq}, Type (_, [Type (@{type_name fun}, _), _]))
    3.22 -         $ _ $ Abs _) => extensionalize_theorem (th RS fun_cong_all)
    3.23 -  | _ => th
    3.24 -
    3.25  fun is_quasi_lambda_free (Const (@{const_name Meson.skolem}, _) $ _) = true
    3.26    | is_quasi_lambda_free (t1 $ t2) =
    3.27      is_quasi_lambda_free t1 andalso is_quasi_lambda_free t2
    3.28 @@ -321,7 +310,7 @@
    3.29      val (th, ctxt) = Variable.import true [th] ctxt |>> snd |>> the_single
    3.30      val th = th |> Conv.fconv_rule Object_Logic.atomize
    3.31                  |> Raw_Simplifier.rewrite_rule (unfold_set_const_simps ctxt)
    3.32 -                |> extensionalize_theorem
    3.33 +                |> extensionalize_theorem ctxt
    3.34                  |> make_nnf ctxt
    3.35    in
    3.36      if new_skolemizer then
     4.1 --- a/src/HOL/Tools/Metis/metis_tactics.ML	Thu May 12 15:29:19 2011 +0200
     4.2 +++ b/src/HOL/Tools/Metis/metis_tactics.ML	Thu May 12 15:29:19 2011 +0200
     4.3 @@ -132,20 +132,9 @@
     4.4                    (if Config.get ctxt verbose then "\n" ^ loc ^ ": " ^ msg
     4.5                     else ""))
     4.6  
     4.7 -(* Extensionalize "th", because that makes sense and that's what Sledgehammer
     4.8 -   does, but also keep an unextensionalized version of "th" for backward
     4.9 -   compatibility. *)
    4.10 -fun also_extensionalize_theorem th =
    4.11 -  let val th' = Meson_Clausify.extensionalize_theorem th in
    4.12 -    if Thm.eq_thm (th, th') then [th]
    4.13 -    else th :: Meson.make_clauses_unsorted [th']
    4.14 -  end
    4.15 -
    4.16  fun neg_clausify ctxt =
    4.17    single
    4.18    #> Meson.make_clauses_unsorted
    4.19 -  #> maps (Raw_Simplifier.rewrite_rule (Meson.unfold_set_const_simps ctxt)
    4.20 -           #> also_extensionalize_theorem)
    4.21    #> map Meson_Clausify.introduce_combinators_in_theorem
    4.22    #> Meson.finish_cnf
    4.23  
     5.1 --- a/src/HOL/Tools/Sledgehammer/sledgehammer_atp_translate.ML	Thu May 12 15:29:19 2011 +0200
     5.2 +++ b/src/HOL/Tools/Sledgehammer/sledgehammer_atp_translate.ML	Thu May 12 15:29:19 2011 +0200
     5.3 @@ -355,24 +355,11 @@
     5.4    subst_atomic (map (fn (j, T) => (Free (concealed_bound_name j, T), Bound j))
     5.5                      (0 upto length Ts - 1 ~~ Ts))
     5.6  
     5.7 -(* Removes the lambdas from an equation of the form "t = (%x. u)".
     5.8 -   (Cf. "extensionalize_theorem" in "Meson_Clausify".) *)
     5.9 -fun extensionalize_term t =
    5.10 -  let
    5.11 -    fun aux j (@{const Trueprop} $ t') = @{const Trueprop} $ aux j t'
    5.12 -      | aux j (t as Const (s, Type (_, [Type (_, [_, T']),
    5.13 -                                        Type (_, [_, res_T])]))
    5.14 -                    $ t2 $ Abs (var_s, var_T, t')) =
    5.15 -        if s = @{const_name HOL.eq} orelse s = @{const_name "=="} then
    5.16 -          let val var_t = Var ((var_s, j), var_T) in
    5.17 -            Const (s, T' --> T' --> res_T)
    5.18 -              $ betapply (t2, var_t) $ subst_bound (var_t, t')
    5.19 -            |> aux (j + 1)
    5.20 -          end
    5.21 -        else
    5.22 -          t
    5.23 -      | aux _ t = t
    5.24 -  in aux (maxidx_of_term t + 1) t end
    5.25 +fun extensionalize_term ctxt t =
    5.26 +  let val thy = Proof_Context.theory_of ctxt in
    5.27 +    t |> cterm_of thy |> Meson.extensionalize_conv ctxt
    5.28 +      |> prop_of |> Logic.dest_equals |> snd
    5.29 +  end
    5.30  
    5.31  fun introduce_combinators_in_term ctxt kind t =
    5.32    let val thy = Proof_Context.theory_of ctxt in
    5.33 @@ -436,7 +423,7 @@
    5.34      val t = t |> need_trueprop ? HOLogic.mk_Trueprop
    5.35                |> Raw_Simplifier.rewrite_term thy
    5.36                       (Meson.unfold_set_const_simps ctxt) []
    5.37 -              |> extensionalize_term
    5.38 +              |> extensionalize_term ctxt
    5.39                |> presimp ? presimplify_term thy
    5.40                |> perhaps (try (HOLogic.dest_Trueprop))
    5.41                |> introduce_combinators_in_term ctxt kind