src/HOL/Tools/Metis/metis_reconstruct.ML
changeset 70505 1881fb38a1ef
parent 70487 9cb269b49cf7
child 70506 3f5d7fbaa1ea
equal deleted inserted replaced
70503:f0b2635ee17f 70505:1881fb38a1ef
    39   (case find_first (fn (_, (f, _)) => f type_enc = s) metis_name_table of
    39   (case find_first (fn (_, (f, _)) => f type_enc = s) metis_name_table of
    40     SOME ((s, _), (_, swap)) => (s, swap)
    40     SOME ((s, _), (_, swap)) => (s, swap)
    41   | _ => (s, false))
    41   | _ => (s, false))
    42 
    42 
    43 fun atp_term_of_metis type_enc (Metis_Term.Fn (s, tms)) =
    43 fun atp_term_of_metis type_enc (Metis_Term.Fn (s, tms)) =
    44     let val (s, swap) = atp_name_of_metis type_enc (Metis_Name.toString s) in
    44       let val (s, swap) = atp_name_of_metis type_enc (Metis_Name.toString s)
    45       ATerm ((s, []), tms |> map (atp_term_of_metis type_enc) |> swap ? rev)
    45       in ATerm ((s, []), tms |> map (atp_term_of_metis type_enc) |> swap ? rev) end
    46     end
       
    47   | atp_term_of_metis _ (Metis_Term.Var s) =
    46   | atp_term_of_metis _ (Metis_Term.Var s) =
    48     ATerm ((Metis_Name.toString s, []), [])
    47       ATerm ((Metis_Name.toString s, []), [])
    49 
    48 
    50 fun hol_term_of_metis ctxt type_enc sym_tab =
    49 fun hol_term_of_metis ctxt type_enc sym_tab =
    51   atp_term_of_metis type_enc #> term_of_atp ctxt ATP_Problem.CNF type_enc false sym_tab NONE
    50   atp_term_of_metis type_enc #> term_of_atp ctxt ATP_Problem.CNF type_enc false sym_tab NONE
    52 
    51 
    53 fun atp_literal_of_metis type_enc (pos, atom) =
    52 fun atp_literal_of_metis type_enc (pos, atom) =
    78     val _ = List.app (fn t => trace_msg ctxt
    77     val _ = List.app (fn t => trace_msg ctxt
    79                   (fn () => "  final term: " ^ Syntax.string_of_term ctxt t ^
    78                   (fn () => "  final term: " ^ Syntax.string_of_term ctxt t ^
    80                             " of type " ^ Syntax.string_of_typ ctxt (type_of t))) ts'
    79                             " of type " ^ Syntax.string_of_typ ctxt (type_of t))) ts'
    81   in ts' end
    80   in ts' end
    82 
    81 
    83 (* ------------------------------------------------------------------------- *)
    82 
    84 (* FOL step Inference Rules                                                  *)
    83 
    85 (* ------------------------------------------------------------------------- *)
    84 (** FOL step Inference Rules **)
    86 
    85 
    87 fun lookth th_pairs fth =
    86 fun lookth th_pairs fth =
    88   the (AList.lookup (uncurry Metis_Thm.equal) th_pairs fth)
    87   the (AList.lookup (uncurry Metis_Thm.equal) th_pairs fth)
    89   handle Option.Option => raise Fail ("Failed to find Metis theorem " ^ Metis_Thm.toString fth)
    88   handle Option.Option => raise Fail ("Failed to find Metis theorem " ^ Metis_Thm.toString fth)
    90 
    89 
    91 fun cterm_incr_types ctxt idx =
    90 fun cterm_incr_types ctxt idx =
    92   Thm.cterm_of ctxt o map_types (Logic.incr_tvar idx)
    91   Thm.cterm_of ctxt o map_types (Logic.incr_tvar idx)
    93 
    92 
       
    93 
    94 (* INFERENCE RULE: AXIOM *)
    94 (* INFERENCE RULE: AXIOM *)
    95 
    95 
    96 (* This causes variables to have an index of 1 by default. See also
    96 (*This causes variables to have an index of 1 by default. See also
    97    "term_of_atp" in "ATP_Proof_Reconstruct". *)
    97   "term_of_atp" in "ATP_Proof_Reconstruct".*)
    98 val axiom_inference = Thm.incr_indexes 1 oo lookth
    98 val axiom_inference = Thm.incr_indexes 1 oo lookth
    99 
    99 
       
   100 
   100 (* INFERENCE RULE: ASSUME *)
   101 (* INFERENCE RULE: ASSUME *)
   101 
   102 
   102 val EXCLUDED_MIDDLE = @{lemma "P \<Longrightarrow> \<not> P \<Longrightarrow> False" by (rule notE)}
   103 val EXCLUDED_MIDDLE = @{lemma "P \<Longrightarrow> \<not> P \<Longrightarrow> False" by (rule notE)}
   103 
   104 
   104 fun inst_excluded_middle ctxt i_atom =
   105 fun inst_excluded_middle ctxt i_atom =
   105   let
   106   let val [vx] = Term.add_vars (Thm.prop_of EXCLUDED_MIDDLE) []
   106     val th = EXCLUDED_MIDDLE
   107   in infer_instantiate_types ctxt [(vx, Thm.cterm_of ctxt i_atom)] EXCLUDED_MIDDLE end
   107     val [vx] = Term.add_vars (Thm.prop_of th) []
       
   108   in
       
   109     infer_instantiate_types ctxt [(vx, Thm.cterm_of ctxt i_atom)] th
       
   110   end
       
   111 
   108 
   112 fun assume_inference ctxt type_enc concealed sym_tab atom =
   109 fun assume_inference ctxt type_enc concealed sym_tab atom =
   113   inst_excluded_middle ctxt
   110   inst_excluded_middle ctxt
   114     (singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) (Metis_Term.Fn atom))
   111     (singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) (Metis_Term.Fn atom))
   115 
   112 
   125 
   122 
   126     fun find_var x = the (List.find (fn ((a,_),_) => a=x) i_th_vars)
   123     fun find_var x = the (List.find (fn ((a,_),_) => a=x) i_th_vars)
   127     fun subst_translation (x,y) =
   124     fun subst_translation (x,y) =
   128       let
   125       let
   129         val v = find_var x
   126         val v = find_var x
   130         (* We call "polish_hol_terms" below. *)
   127         (*We call "polish_hol_terms" below.*)
   131         val t = hol_term_of_metis ctxt type_enc sym_tab y
   128         val t = hol_term_of_metis ctxt type_enc sym_tab y
   132       in
   129       in
   133         SOME (Thm.cterm_of ctxt (Var v), t)
   130         SOME (Thm.cterm_of ctxt (Var v), t)
   134       end
   131       end
   135       handle Option.Option =>
   132       handle Option.Option =>
   144       let val a = Metis_Name.toString a in
   141       let val a = Metis_Name.toString a in
   145         (case unprefix_and_unascii schematic_var_prefix a of
   142         (case unprefix_and_unascii schematic_var_prefix a of
   146           SOME b => SOME (b, t)
   143           SOME b => SOME (b, t)
   147         | NONE =>
   144         | NONE =>
   148           (case unprefix_and_unascii tvar_prefix a of
   145           (case unprefix_and_unascii tvar_prefix a of
   149             SOME _ => NONE (* type instantiations are forbidden *)
   146             SOME _ => NONE (*type instantiations are forbidden*)
   150           | NONE => SOME (a, t) (* internal Metis var? *)))
   147           | NONE => SOME (a, t) (*internal Metis var?*)))
   151       end
   148       end
   152     val _ = trace_msg ctxt (fn () => "  isa th: " ^ Thm.string_of_thm ctxt i_th)
   149     val _ = trace_msg ctxt (fn () => "  isa th: " ^ Thm.string_of_thm ctxt i_th)
   153     val substs = map_filter remove_typeinst (Metis_Subst.toList fsubst)
   150     val substs = map_filter remove_typeinst (Metis_Subst.toList fsubst)
   154     val (vars, tms) =
   151     val (vars, tms) =
   155       ListPair.unzip (map_filter subst_translation substs)
   152       ListPair.unzip (map_filter subst_translation substs)
   165     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) substs') i_th
   162     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) substs') i_th
   166   end
   163   end
   167   handle THM (msg, _, _) => raise METIS_RECONSTRUCT ("inst_inference", msg)
   164   handle THM (msg, _, _) => raise METIS_RECONSTRUCT ("inst_inference", msg)
   168        | ERROR msg => raise METIS_RECONSTRUCT ("inst_inference", msg)
   165        | ERROR msg => raise METIS_RECONSTRUCT ("inst_inference", msg)
   169 
   166 
       
   167 
   170 (* INFERENCE RULE: RESOLVE *)
   168 (* INFERENCE RULE: RESOLVE *)
   171 
   169 
   172 (*Increment the indexes of only the type variables*)
   170 (*Increment the indexes of only the type variables*)
   173 fun incr_type_indexes ctxt inc th =
   171 fun incr_type_indexes ctxt inc th =
   174   let
   172   let
   176     fun inc_tvar ((a, i), s) = (((a, i), s), Thm.ctyp_of ctxt (TVar ((a, i + inc), s)))
   174     fun inc_tvar ((a, i), s) = (((a, i), s), Thm.ctyp_of ctxt (TVar ((a, i + inc), s)))
   177   in
   175   in
   178     Thm.instantiate (map inc_tvar tvs, []) th
   176     Thm.instantiate (map inc_tvar tvs, []) th
   179   end
   177   end
   180 
   178 
   181 (* Like RSN, but we rename apart only the type variables. Vars here typically
   179 (*Like RSN, but we rename apart only the type variables. Vars here typically
   182    have an index of 1, and the use of RSN would increase this typically to 3.
   180   have an index of 1, and the use of RSN would increase this typically to 3.
   183    Instantiations of those Vars could then fail. *)
   181   Instantiations of those Vars could then fail.*)
   184 fun resolve_inc_tyvars ctxt tha i thb =
   182 fun resolve_inc_tyvars ctxt tha i thb =
   185   let
   183   let
   186     val tha = incr_type_indexes ctxt (1 + Thm.maxidx_of thb) tha
   184     val tha = incr_type_indexes ctxt (1 + Thm.maxidx_of thb) tha
   187     fun res (tha, thb) =
   185     fun res (tha, thb) =
   188       (case Thm.bicompose (SOME ctxt) {flatten = true, match = false, incremented = true}
   186       (case Thm.bicompose (SOME ctxt) {flatten = true, match = false, incremented = true}
   210           |> rpair Envir.init
   208           |> rpair Envir.init
   211           |-> fold (Pattern.unify (Context.Proof ctxt))
   209           |-> fold (Pattern.unify (Context.Proof ctxt))
   212           |> Envir.type_env |> Vartab.dest
   210           |> Envir.type_env |> Vartab.dest
   213           |> map (fn (x, (S, T)) => ((x, S), Thm.ctyp_of ctxt T))
   211           |> map (fn (x, (S, T)) => ((x, S), Thm.ctyp_of ctxt T))
   214       in
   212       in
   215         (* The unifier, which is invoked from "Thm.bicompose", will sometimes refuse to unify
   213         (*The unifier, which is invoked from "Thm.bicompose", will sometimes refuse to unify
   216            "?a::?'a" with "?a::?'b" or "?a::nat" and throw a "TERM" exception (with "add_ffpair" as
   214           "?a::?'a" with "?a::?'b" or "?a::nat" and throw a "TERM" exception (with "add_ffpair" as
   217            first argument). We then perform unification of the types of variables by hand and try
   215           first argument). We then perform unification of the types of variables by hand and try
   218            again. We could do this the first time around but this error occurs seldom and we don't
   216           again. We could do this the first time around but this error occurs seldom and we don't
   219            want to break existing proofs in subtle ways or slow them down. *)
   217           want to break existing proofs in subtle ways or slow them down.*)
   220         if null ps then raise TERM z
   218         if null ps then raise TERM z
   221         else res (apply2 (Drule.instantiate_normalize (ps, [])) (tha, thb))
   219         else res (apply2 (Drule.instantiate_normalize (ps, [])) (tha, thb))
   222       end
   220       end
   223   end
   221   end
   224 
   222 
   228   | simp_not_not (\<^const>\<open>Not\<close> $ t) = s_not (simp_not_not t)
   226   | simp_not_not (\<^const>\<open>Not\<close> $ t) = s_not (simp_not_not t)
   229   | simp_not_not t = t
   227   | simp_not_not t = t
   230 
   228 
   231 val normalize_literal = simp_not_not o Envir.eta_contract
   229 val normalize_literal = simp_not_not o Envir.eta_contract
   232 
   230 
   233 (* Find the relative location of an untyped term within a list of terms as a
   231 (*Find the relative location of an untyped term within a list of terms as a
   234    1-based index. Returns 0 in case of failure. *)
   232   1-based index. Returns 0 in case of failure.*)
   235 fun index_of_literal lit haystack =
   233 fun index_of_literal lit haystack =
   236   let
   234   let
   237     fun match_lit normalize =
   235     fun match_lit normalize =
   238       HOLogic.dest_Trueprop #> normalize
   236       HOLogic.dest_Trueprop #> normalize
   239       #> curry Term.aconv_untyped (lit |> normalize)
   237       #> curry Term.aconv_untyped (lit |> normalize)
   241     (case find_index (match_lit I) haystack of
   239     (case find_index (match_lit I) haystack of
   242        ~1 => find_index (match_lit (simp_not_not o Envir.eta_contract)) haystack
   240        ~1 => find_index (match_lit (simp_not_not o Envir.eta_contract)) haystack
   243      | j => j) + 1
   241      | j => j) + 1
   244   end
   242   end
   245 
   243 
   246 (* Permute a rule's premises to move the i-th premise to the last position. *)
   244 (*Permute a rule's premises to move the i-th premise to the last position.*)
   247 fun make_last i th =
   245 fun make_last i th =
   248   let val n = Thm.nprems_of th in
   246   let val n = Thm.nprems_of th in
   249     if i >= 1 andalso i <= n then Thm.permute_prems (i - 1) 1 th
   247     if i >= 1 andalso i <= n then Thm.permute_prems (i - 1) 1 th
   250     else raise THM ("select_literal", i, [th])
   248     else raise THM ("select_literal", i, [th])
   251   end
   249   end
   252 
   250 
   253 (* Maps a rule that ends "... ==> P ==> False" to "... ==> ~ P" while avoiding
   251 (*Maps a rule that ends "... ==> P ==> False" to "... ==> ~ P" while avoiding
   254    to create double negations. The "select" wrapper is a trick to ensure that
   252   to create double negations. The "select" wrapper is a trick to ensure that
   255    "P ==> ~ False ==> False" is rewritten to "P ==> False", not to "~ P". We
   253   "P ==> ~ False ==> False" is rewritten to "P ==> False", not to "~ P". We
   256    don't use this trick in general because it makes the proof object uglier than
   254   don't use this trick in general because it makes the proof object uglier than
   257    necessary. FIXME. *)
   255   necessary. FIXME.*)
   258 fun negate_head ctxt th =
   256 fun negate_head ctxt th =
   259   if exists (fn t => t aconv \<^prop>\<open>\<not> False\<close>) (Thm.prems_of th) then
   257   if exists (fn t => t aconv \<^prop>\<open>\<not> False\<close>) (Thm.prems_of th) then
   260     (th RS @{thm select_FalseI})
   258     (th RS @{thm select_FalseI})
   261     |> fold (rewrite_rule ctxt o single) @{thms not_atomize_select atomize_not_select}
   259     |> fold (rewrite_rule ctxt o single) @{thms not_atomize_select atomize_not_select}
   262   else
   260   else
   294               resolve_inc_tyvars ctxt (select_literal ctxt j1 i_th1) j2 i_th2
   292               resolve_inc_tyvars ctxt (select_literal ctxt j1 i_th1) j2 i_th2
   295               handle TERM (s, _) => raise METIS_RECONSTRUCT ("resolve_inference", s)))))
   293               handle TERM (s, _) => raise METIS_RECONSTRUCT ("resolve_inference", s)))))
   296       end
   294       end
   297   end
   295   end
   298 
   296 
       
   297 
   299 (* INFERENCE RULE: REFL *)
   298 (* INFERENCE RULE: REFL *)
   300 
   299 
   301 val REFL_THM = Thm.incr_indexes 2 @{lemma "t \<noteq> t \<Longrightarrow> False" by (drule notE) (rule refl)}
   300 val REFL_THM = Thm.incr_indexes 2 @{lemma "t \<noteq> t \<Longrightarrow> False" by (drule notE) (rule refl)}
   302 
   301 
   303 val [refl_x] = Term.add_vars (Thm.prop_of REFL_THM) [];
   302 val [refl_x] = Term.add_vars (Thm.prop_of REFL_THM) [];
   308     val i_t = singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) t
   307     val i_t = singleton (hol_terms_of_metis ctxt type_enc concealed sym_tab) t
   309     val _ = trace_msg ctxt (fn () => "  term: " ^ Syntax.string_of_term ctxt i_t)
   308     val _ = trace_msg ctxt (fn () => "  term: " ^ Syntax.string_of_term ctxt i_t)
   310     val c_t = cterm_incr_types ctxt refl_idx i_t
   309     val c_t = cterm_incr_types ctxt refl_idx i_t
   311   in infer_instantiate_types ctxt [(refl_x, c_t)] REFL_THM end
   310   in infer_instantiate_types ctxt [(refl_x, c_t)] REFL_THM end
   312 
   311 
       
   312 
   313 (* INFERENCE RULE: EQUALITY *)
   313 (* INFERENCE RULE: EQUALITY *)
   314 
   314 
   315 val subst_em = @{lemma "s = t \<Longrightarrow> P s \<Longrightarrow> \<not> P t \<Longrightarrow> False" by (erule notE) (erule subst)}
   315 val subst_em = @{lemma "s = t \<Longrightarrow> P s \<Longrightarrow> \<not> P t \<Longrightarrow> False" by (erule notE) (erule subst)}
   316 val ssubst_em = @{lemma "s = t \<Longrightarrow> P t \<Longrightarrow> \<not> P s \<Longrightarrow> False" by (erule notE) (erule ssubst)}
   316 val ssubst_em = @{lemma "s = t \<Longrightarrow> P t \<Longrightarrow> \<not> P s \<Longrightarrow> False" by (erule notE) (erule ssubst)}
   317 
   317 
   318 fun equality_inference ctxt type_enc concealed sym_tab (pos, atom) fp fr =
   318 fun equality_inference ctxt type_enc concealed sym_tab (pos, atom) fp fr =
   319   let val thy = Proof_Context.theory_of ctxt
   319   let
   320       val m_tm = Metis_Term.Fn atom
   320     val m_tm = Metis_Term.Fn atom
   321       val [i_atom, i_tm] = hol_terms_of_metis ctxt type_enc concealed sym_tab [m_tm, fr]
   321     val [i_atom, i_tm] = hol_terms_of_metis ctxt type_enc concealed sym_tab [m_tm, fr]
   322       val _ = trace_msg ctxt (fn () => "sign of the literal: " ^ Bool.toString pos)
   322     val _ = trace_msg ctxt (fn () => "sign of the literal: " ^ Bool.toString pos)
   323       fun replace_item_list lx 0 (_::ls) = lx::ls
   323     fun replace_item_list lx 0 (_::ls) = lx::ls
   324         | replace_item_list lx i (l::ls) = l :: replace_item_list lx (i-1) ls
   324       | replace_item_list lx i (l::ls) = l :: replace_item_list lx (i-1) ls
   325       fun path_finder_fail tm ps t =
   325     fun path_finder_fail tm ps t =
   326         raise METIS_RECONSTRUCT ("equality_inference (path_finder)",
   326       raise METIS_RECONSTRUCT ("equality_inference (path_finder)",
   327                   "path = " ^ space_implode " " (map string_of_int ps) ^
   327                 "path = " ^ space_implode " " (map string_of_int ps) ^
   328                   " isa-term: " ^ Syntax.string_of_term ctxt tm ^
   328                 " isa-term: " ^ Syntax.string_of_term ctxt tm ^
   329                   (case t of
   329                 (case t of
   330                     SOME t => " fol-term: " ^ Metis_Term.toString t
   330                   SOME t => " fol-term: " ^ Metis_Term.toString t
   331                   | NONE => ""))
   331                 | NONE => ""))
   332       fun path_finder tm [] _ = (tm, Bound 0)
   332     fun path_finder tm [] _ = (tm, Bound 0)
   333         | path_finder tm (p :: ps) (t as Metis_Term.Fn (s, ts)) =
   333       | path_finder tm (p :: ps) (t as Metis_Term.Fn (s, ts)) =
   334           let
   334           let
   335             val s = s |> Metis_Name.toString
   335             val s = s |> Metis_Name.toString
   336                       |> perhaps (try (unprefix_and_unascii const_prefix
   336                       |> perhaps (try (unprefix_and_unascii const_prefix
   337                                        #> the #> unmangled_const_name #> hd))
   337                                        #> the #> unmangled_const_name #> hd))
   338           in
   338           in
   359                     "path_finder: " ^ string_of_int p ^ "  " ^
   359                     "path_finder: " ^ string_of_int p ^ "  " ^
   360                     Syntax.string_of_term ctxt tm_p)
   360                     Syntax.string_of_term ctxt tm_p)
   361                 val (r, t) = path_finder tm_p ps (nth ts p)
   361                 val (r, t) = path_finder tm_p ps (nth ts p)
   362               in (r, list_comb (tm1, replace_item_list t p' args)) end
   362               in (r, list_comb (tm1, replace_item_list t p' args)) end
   363           end
   363           end
   364         | path_finder tm ps t = path_finder_fail tm ps (SOME t)
   364       | path_finder tm ps t = path_finder_fail tm ps (SOME t)
   365       val (tm_subst, body) = path_finder i_atom fp m_tm
   365     val (tm_subst, body) = path_finder i_atom fp m_tm
   366       val tm_abs = Abs ("x", type_of tm_subst, body)
   366     val tm_abs = Abs ("x", type_of tm_subst, body)
   367       val _ = trace_msg ctxt (fn () => "abstraction: " ^ Syntax.string_of_term ctxt tm_abs)
   367     val _ = trace_msg ctxt (fn () => "abstraction: " ^ Syntax.string_of_term ctxt tm_abs)
   368       val _ = trace_msg ctxt (fn () => "i_tm: " ^ Syntax.string_of_term ctxt i_tm)
   368     val _ = trace_msg ctxt (fn () => "i_tm: " ^ Syntax.string_of_term ctxt i_tm)
   369       val _ = trace_msg ctxt (fn () => "located term: " ^ Syntax.string_of_term ctxt tm_subst)
   369     val _ = trace_msg ctxt (fn () => "located term: " ^ Syntax.string_of_term ctxt tm_subst)
   370       val imax = maxidx_of_term (i_tm $ tm_abs $ tm_subst)  (*ill-typed but gives right max*)
   370     val imax = maxidx_of_term (i_tm $ tm_abs $ tm_subst)  (*ill-typed but gives right max*)
   371       val subst' = Thm.incr_indexes (imax+1) (if pos then subst_em else ssubst_em)
   371     val subst' = Thm.incr_indexes (imax+1) (if pos then subst_em else ssubst_em)
   372       val _ = trace_msg ctxt (fn () => "subst' " ^ Thm.string_of_thm ctxt subst')
   372     val _ = trace_msg ctxt (fn () => "subst' " ^ Thm.string_of_thm ctxt subst')
   373       val eq_terms =
   373     val eq_terms =
   374         map (apply2 (Thm.cterm_of ctxt))
   374       map (apply2 (Thm.cterm_of ctxt))
   375           (ListPair.zip (Misc_Legacy.term_vars (Thm.prop_of subst'), [tm_abs, tm_subst, i_tm]))
   375         (ListPair.zip (Misc_Legacy.term_vars (Thm.prop_of subst'), [tm_abs, tm_subst, i_tm]))
   376   in
   376   in
   377     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) eq_terms) subst'
   377     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) eq_terms) subst'
   378   end
   378   end
   379 
   379 
   380 val factor = Seq.hd o distinct_subgoals_tac
   380 val factor = Seq.hd o distinct_subgoals_tac
   382 fun one_step ctxt type_enc concealed sym_tab th_pairs p =
   382 fun one_step ctxt type_enc concealed sym_tab th_pairs p =
   383   (case p of
   383   (case p of
   384     (fol_th, Metis_Proof.Axiom _) => axiom_inference th_pairs fol_th |> factor
   384     (fol_th, Metis_Proof.Axiom _) => axiom_inference th_pairs fol_th |> factor
   385   | (_, Metis_Proof.Assume f_atom) => assume_inference ctxt type_enc concealed sym_tab f_atom
   385   | (_, Metis_Proof.Assume f_atom) => assume_inference ctxt type_enc concealed sym_tab f_atom
   386   | (_, Metis_Proof.Metis_Subst (f_subst, f_th1)) =>
   386   | (_, Metis_Proof.Metis_Subst (f_subst, f_th1)) =>
   387     inst_inference ctxt type_enc concealed sym_tab th_pairs f_subst f_th1 |> factor
   387       inst_inference ctxt type_enc concealed sym_tab th_pairs f_subst f_th1 |> factor
   388   | (_, Metis_Proof.Resolve(f_atom, f_th1, f_th2)) =>
   388   | (_, Metis_Proof.Resolve(f_atom, f_th1, f_th2)) =>
   389     resolve_inference ctxt type_enc concealed sym_tab th_pairs f_atom f_th1 f_th2 |> factor
   389       resolve_inference ctxt type_enc concealed sym_tab th_pairs f_atom f_th1 f_th2 |> factor
   390   | (_, Metis_Proof.Refl f_tm) => refl_inference ctxt type_enc concealed sym_tab f_tm
   390   | (_, Metis_Proof.Refl f_tm) => refl_inference ctxt type_enc concealed sym_tab f_tm
   391   | (_, Metis_Proof.Equality (f_lit, f_p, f_r)) =>
   391   | (_, Metis_Proof.Equality (f_lit, f_p, f_r)) =>
   392     equality_inference ctxt type_enc concealed sym_tab f_lit f_p f_r)
   392       equality_inference ctxt type_enc concealed sym_tab f_lit f_p f_r)
   393 
   393 
   394 fun flexflex_first_order ctxt th =
   394 fun flexflex_first_order ctxt th =
   395   (case Thm.tpairs_of th of
   395   (case Thm.tpairs_of th of
   396     [] => th
   396     [] => th
   397   | pairs =>
   397   | pairs =>
   398       let
   398       let
   399         val thy = Proof_Context.theory_of ctxt
   399         val thy = Proof_Context.theory_of ctxt
   400         val (tyenv, tenv) = fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty)
   400         val (tyenv, tenv) = fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty)
   401   
   401 
   402         fun mkT (v, (S, T)) = ((v, S), Thm.ctyp_of ctxt T)
   402         fun mkT (v, (S, T)) = ((v, S), Thm.ctyp_of ctxt T)
   403         fun mk (v, (T, t)) = ((v, Envir.subst_type tyenv T), Thm.cterm_of ctxt t)
   403         fun mk (v, (T, t)) = ((v, Envir.subst_type tyenv T), Thm.cterm_of ctxt t)
   404   
   404 
   405         val instsT = Vartab.fold (cons o mkT) tyenv []
   405         val instsT = Vartab.fold (cons o mkT) tyenv []
   406         val insts = Vartab.fold (cons o mk) tenv []
   406         val insts = Vartab.fold (cons o mk) tenv []
   407       in
   407       in
   408         Thm.instantiate (instsT, insts) th
   408         Thm.instantiate (instsT, insts) th
   409       end
   409       end
   414 fun is_isabelle_literal_genuine t =
   414 fun is_isabelle_literal_genuine t =
   415   (case t of _ $ (Const (\<^const_name>\<open>Meson.skolem\<close>, _) $ _) => false | _ => true)
   415   (case t of _ $ (Const (\<^const_name>\<open>Meson.skolem\<close>, _) $ _) => false | _ => true)
   416 
   416 
   417 fun count p xs = fold (fn x => if p x then Integer.add 1 else I) xs 0
   417 fun count p xs = fold (fn x => if p x then Integer.add 1 else I) xs 0
   418 
   418 
   419 (* Seldomly needed hack. A Metis clause is represented as a set, so duplicate
   419 (*Seldomly needed hack. A Metis clause is represented as a set, so duplicate
   420    disjuncts are impossible. In the Isabelle proof, in spite of efforts to
   420   disjuncts are impossible. In the Isabelle proof, in spite of efforts to
   421    eliminate them, duplicates sometimes appear with slightly different (but
   421   eliminate them, duplicates sometimes appear with slightly different (but
   422    unifiable) types. *)
   422   unifiable) types.*)
   423 fun resynchronize ctxt fol_th th =
   423 fun resynchronize ctxt fol_th th =
   424   let
   424   let
   425     val num_metis_lits =
   425     val num_metis_lits =
   426       count is_metis_literal_genuine (Metis_LiteralSet.toList (Metis_Thm.clause fol_th))
   426       count is_metis_literal_genuine (Metis_LiteralSet.toList (Metis_Thm.clause fol_th))
   427     val num_isabelle_lits = count is_isabelle_literal_genuine (Thm.prems_of th)
   427     val num_isabelle_lits = count is_isabelle_literal_genuine (Thm.prems_of th)
   445           Goal.prove ctxt' [] [] goal (K tac)
   445           Goal.prove ctxt' [] [] goal (K tac)
   446           |> resynchronize ctxt' fol_th
   446           |> resynchronize ctxt' fol_th
   447       end
   447       end
   448   end
   448   end
   449 
   449 
   450 fun replay_one_inference ctxt type_enc concealed sym_tab (fol_th, inf)
   450 fun replay_one_inference ctxt type_enc concealed sym_tab (fol_th, inf) th_pairs =
   451                          th_pairs =
       
   452   if not (null th_pairs) andalso Thm.prop_of (snd (hd th_pairs)) aconv \<^prop>\<open>False\<close> then
   451   if not (null th_pairs) andalso Thm.prop_of (snd (hd th_pairs)) aconv \<^prop>\<open>False\<close> then
   453     (* Isabelle sometimes identifies literals (premises) that are distinct in
   452     (*Isabelle sometimes identifies literals (premises) that are distinct in
   454        Metis (e.g., because of type variables). We give the Isabelle proof the
   453       Metis (e.g., because of type variables). We give the Isabelle proof the
   455        benefice of the doubt. *)
   454       benefice of the doubt.*)
   456     th_pairs
   455     th_pairs
   457   else
   456   else
   458     let
   457     let
   459       val _ = trace_msg ctxt (fn () => "=============================================")
   458       val _ = trace_msg ctxt (fn () => "=============================================")
   460       val _ = trace_msg ctxt (fn () => "METIS THM: " ^ Metis_Thm.toString fol_th)
   459       val _ = trace_msg ctxt (fn () => "METIS THM: " ^ Metis_Thm.toString fol_th)
   466       val _ = trace_msg ctxt (fn () => "=============================================")
   465       val _ = trace_msg ctxt (fn () => "=============================================")
   467     in
   466     in
   468       (fol_th, th) :: th_pairs
   467       (fol_th, th) :: th_pairs
   469     end
   468     end
   470 
   469 
   471 (* It is normally sufficient to apply "assume_tac" to unify the conclusion with
   470 (*It is normally sufficient to apply "assume_tac" to unify the conclusion with
   472    one of the premises. Unfortunately, this sometimes yields "Variable
   471   one of the premises. Unfortunately, this sometimes yields "Variable
   473    has two distinct types" errors. To avoid this, we instantiate the
   472   has two distinct types" errors. To avoid this, we instantiate the
   474    variables before applying "assume_tac". Typical constraints are of the form
   473   variables before applying "assume_tac". Typical constraints are of the form
   475      ?SK_a_b_c_x SK_d_e_f_y ... SK_a_b_c_x ... SK_g_h_i_z \<equiv>\<^sup>? SK_a_b_c_x,
   474     ?SK_a_b_c_x SK_d_e_f_y ... SK_a_b_c_x ... SK_g_h_i_z \<equiv>\<^sup>? SK_a_b_c_x,
   476    where the nonvariables are goal parameters. *)
   475   where the nonvariables are goal parameters.*)
   477 fun unify_first_prem_with_concl ctxt i th =
   476 fun unify_first_prem_with_concl ctxt i th =
   478   let
   477   let
   479     val goal = Logic.get_goal (Thm.prop_of th) i |> Envir.beta_eta_contract
   478     val goal = Logic.get_goal (Thm.prop_of th) i |> Envir.beta_eta_contract
   480     val prem = goal |> Logic.strip_assums_hyp |> hd
   479     val prem = goal |> Logic.strip_assums_hyp |> hd
   481     val concl = goal |> Logic.strip_assums_concl
   480     val concl = goal |> Logic.strip_assums_concl
   521          |> the_default [] (* FIXME *)
   520          |> the_default [] (* FIXME *)
   522   in
   521   in
   523     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) t_inst) th
   522     infer_instantiate_types ctxt (map (apfst (dest_Var o Thm.term_of)) t_inst) th
   524   end
   523   end
   525 
   524 
   526 val copy_prem = @{lemma "P ==> (P ==> P ==> Q) ==> Q" by assumption}
   525 val copy_prem = @{lemma "P \<Longrightarrow> (P \<Longrightarrow> P \<Longrightarrow> Q) \<Longrightarrow> Q" by assumption}
   527 
   526 
   528 fun copy_prems_tac ctxt [] ns i =
   527 fun copy_prems_tac ctxt [] ns i =
   529     if forall (curry (op =) 1) ns then all_tac else copy_prems_tac ctxt (rev ns) [] i
   528       if forall (curry (op =) 1) ns then all_tac else copy_prems_tac ctxt (rev ns) [] i
   530   | copy_prems_tac ctxt (1 :: ms) ns i = rotate_tac 1 i THEN copy_prems_tac ctxt ms (1 :: ns) i
   529   | copy_prems_tac ctxt (1 :: ms) ns i = rotate_tac 1 i THEN copy_prems_tac ctxt ms (1 :: ns) i
   531   | copy_prems_tac ctxt (m :: ms) ns i =
   530   | copy_prems_tac ctxt (m :: ms) ns i =
   532     eresolve_tac ctxt [copy_prem] i THEN copy_prems_tac ctxt ms (m div 2 :: (m + 1) div 2 :: ns) i
   531       eresolve_tac ctxt [copy_prem] i THEN copy_prems_tac ctxt ms (m div 2 :: (m + 1) div 2 :: ns) i
   533 
   532 
   534 (* Metis generates variables of the form _nnn. *)
   533 (*Metis generates variables of the form _nnn.*)
   535 val is_metis_fresh_variable = String.isPrefix "_"
   534 val is_metis_fresh_variable = String.isPrefix "_"
   536 
   535 
   537 fun instantiate_forall_tac ctxt t i st =
   536 fun instantiate_forall_tac ctxt t i st =
   538   let
   537   let
   539     val params = Logic.strip_params (Logic.get_goal (Thm.prop_of st) i) |> rev
   538     val params = Logic.strip_params (Logic.get_goal (Thm.prop_of st) i) |> rev
   540 
   539 
   541     fun repair (t as (Var ((s, _), _))) =
   540     fun repair (t as (Var ((s, _), _))) =
   542         (case find_index (fn (s', _) => s' = s) params of
   541           (case find_index (fn (s', _) => s' = s) params of
   543           ~1 => t
   542             ~1 => t
   544         | j => Bound j)
   543           | j => Bound j)
   545       | repair (t $ u) =
   544       | repair (t $ u) =
   546         (case (repair t, repair u) of
   545           (case (repair t, repair u) of
   547           (t as Bound j, u as Bound k) =>
   546             (t as Bound j, u as Bound k) =>
   548           (* This is a trick to repair the discrepancy between the fully skolemized term that MESON
   547             (*This is a trick to repair the discrepancy between the fully skolemized term that MESON
   549              gives us (where existentials were pulled out) and the reality. *)
   548               gives us (where existentials were pulled out) and the reality.*)
   550           if k > j then t else t $ u
   549             if k > j then t else t $ u
   551         | (t, u) => t $ u)
   550           | (t, u) => t $ u)
   552       | repair t = t
   551       | repair t = t
   553 
   552 
   554     val t' = t |> repair |> fold (absdummy o snd) params
   553     val t' = t |> repair |> fold (absdummy o snd) params
   555 
   554 
   556     fun do_instantiate th =
   555     fun do_instantiate th =
   616   prod_ord int_ord (prod_ord int_ord (prod_ord bool_ord int_ord)) (apply2 cluster_key p)
   615   prod_ord int_ord (prod_ord int_ord (prod_ord bool_ord int_ord)) (apply2 cluster_key p)
   617 
   616 
   618 val tysubst_ord =
   617 val tysubst_ord =
   619   list_ord (prod_ord Term_Ord.fast_indexname_ord (prod_ord Term_Ord.sort_ord Term_Ord.typ_ord))
   618   list_ord (prod_ord Term_Ord.fast_indexname_ord (prod_ord Term_Ord.sort_ord Term_Ord.typ_ord))
   620 
   619 
   621 structure Int_Tysubst_Table =
   620 structure Int_Tysubst_Table = Table
   622   Table(type key = int * (indexname * (sort * typ)) list
   621 (
   623         val ord = prod_ord int_ord tysubst_ord)
   622   type key = int * (indexname * (sort * typ)) list
   624 
   623   val ord = prod_ord int_ord tysubst_ord
   625 structure Int_Pair_Graph =
   624 )
   626   Graph(type key = int * int val ord = prod_ord int_ord int_ord)
   625 
       
   626 structure Int_Pair_Graph = Graph(
       
   627   type key = int * int
       
   628   val ord = prod_ord int_ord int_ord
       
   629 )
   627 
   630 
   628 fun shuffle_key (((axiom_no, (_, index_no)), _), _) = (axiom_no, index_no)
   631 fun shuffle_key (((axiom_no, (_, index_no)), _), _) = (axiom_no, index_no)
   629 fun shuffle_ord p = prod_ord int_ord int_ord (apply2 shuffle_key p)
   632 fun shuffle_ord p = prod_ord int_ord int_ord (apply2 shuffle_key p)
   630 
   633 
   631 (* Attempts to derive the theorem "False" from a theorem of the form
   634 (*Attempts to derive the theorem "False" from a theorem of the form
   632    "P1 ==> ... ==> Pn ==> False", where the "Pi"s are to be discharged using the
   635   "P1 ==> ... ==> Pn ==> False", where the "Pi"s are to be discharged using the
   633    specified axioms. The axioms have leading "All" and "Ex" quantifiers, which
   636   specified axioms. The axioms have leading "All" and "Ex" quantifiers, which
   634    must be eliminated first. *)
   637   must be eliminated first.*)
   635 fun discharge_skolem_premises ctxt axioms prems_imp_false =
   638 fun discharge_skolem_premises ctxt axioms prems_imp_false =
   636   if Thm.prop_of prems_imp_false aconv \<^prop>\<open>False\<close> then
   639   if Thm.prop_of prems_imp_false aconv \<^prop>\<open>False\<close> then prems_imp_false
   637     prems_imp_false
       
   638   else
   640   else
   639     let
   641     let
   640       val thy = Proof_Context.theory_of ctxt
   642       val thy = Proof_Context.theory_of ctxt
   641 
   643 
   642       fun match_term p =
   644       fun match_term p =