src/HOL/TPTP/TPTP_Proof_Reconstruction.thy
changeset 55596 928b9f677165
child 55597 25d7b485df81
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/HOL/TPTP/TPTP_Proof_Reconstruction.thy	Wed Feb 19 15:57:02 2014 +0000
     1.3 @@ -0,0 +1,2223 @@
     1.4 +(*  Title:      HOL/TPTP/TPTP_Proof_Reconstruction.thy
     1.5 +    Author:     Nik Sultana, Cambridge University Computer Laboratory
     1.6 +
     1.7 +Proof reconstruction for Leo-II.
     1.8 +
     1.9 +TODO:
    1.10 +  use RemoveRedundantQuantifications instead of the ad hoc use of
    1.11 +   remove_redundant_quantification_in_lit and remove_redundant_quantification
    1.12 +*)
    1.13 +
    1.14 +theory TPTP_Proof_Reconstruction
    1.15 +imports TPTP_Parser TPTP_Interpret
    1.16 +(* keywords "import_leo2_proof" :: thy_decl *) (*FIXME currently unused*)
    1.17 +begin
    1.18 +
    1.19 +
    1.20 +section "Setup"
    1.21 +
    1.22 +ML {*
    1.23 +  val tptp_unexceptional_reconstruction = Attrib.setup_config_bool @{binding tptp_unexceptional_reconstruction} (K false)
    1.24 +  fun unexceptional_reconstruction ctxt = Config.get ctxt tptp_unexceptional_reconstruction
    1.25 +  val tptp_informative_failure = Attrib.setup_config_bool @{binding tptp_informative_failure} (K false)
    1.26 +  fun informative_failure ctxt = Config.get ctxt tptp_informative_failure
    1.27 +  val tptp_trace_reconstruction = Attrib.setup_config_bool @{binding tptp_trace_reconstruction} (K false)
    1.28 +  val tptp_max_term_size = Attrib.setup_config_int @{binding tptp_max_term_size} (K 0) (*0=infinity*)
    1.29 +
    1.30 +  fun exceeds_tptp_max_term_size ctxt size =
    1.31 +    let
    1.32 +      val max = Config.get ctxt tptp_max_term_size
    1.33 +    in
    1.34 +      if max = 0 then false
    1.35 +      else size > max
    1.36 +    end
    1.37 +*}
    1.38 +
    1.39 +(*FIXME move to TPTP_Proof_Reconstruction_Test_Units*)
    1.40 +declare [[
    1.41 +  tptp_unexceptional_reconstruction = false, (*NOTE should be "false" while testing*)
    1.42 +  tptp_informative_failure = true
    1.43 +]]
    1.44 +
    1.45 +ML_file "TPTP_Parser/tptp_reconstruct_library.ML"
    1.46 +ML "open TPTP_Reconstruct_Library"
    1.47 +ML_file "TPTP_Parser/tptp_reconstruct.ML"
    1.48 +
    1.49 +(*FIXME fudge*)
    1.50 +declare [[
    1.51 +  blast_depth_limit = 10,
    1.52 +  unify_search_bound = 5
    1.53 +]]
    1.54 +
    1.55 +
    1.56 +section "Proof reconstruction"
    1.57 +text {*There are two parts to proof reconstruction:
    1.58 +\begin{itemize}
    1.59 +  \item interpreting the inferences
    1.60 +  \item building the skeleton, which indicates how to compose
    1.61 +    individual inferences into subproofs, and then compose the
    1.62 +    subproofs to give the proof).
    1.63 +\end{itemize}
    1.64 +
    1.65 +One step detects unsound inferences, and the other step detects
    1.66 +unsound composition of inferences.  The two parts can be weakly
    1.67 +coupled. They rely on a "proof index" which maps nodes to the
    1.68 +inference information. This information consists of the (usually
    1.69 +prover-specific) name of the inference step, and the Isabelle
    1.70 +formalisation of the inference as a term. The inference interpretation
    1.71 +then maps these terms into meta-theorems, and the skeleton is used to
    1.72 +compose the inference-level steps into a proof.
    1.73 +
    1.74 +Leo2 operates on conjunctions of clauses. Each Leo2 inference has the
    1.75 +following form, where Cx are clauses:
    1.76 +
    1.77 +           C1 && ... && Cn
    1.78 +          -----------------
    1.79 +          C'1 && ... && C'n
    1.80 +
    1.81 +Clauses consist of disjunctions of literals (shown as Px below), and might
    1.82 +have a prefix of !-bound variables, as shown below.
    1.83 +
    1.84 +  ! X... { P1 || ... || Pn}
    1.85 +
    1.86 +Literals are usually assigned a polarity, but this isn't always the
    1.87 +case; you can come across inferences looking like this (where A is an
    1.88 +object-level formula):
    1.89 +
    1.90 +             F
    1.91 +          --------
    1.92 +          F = true
    1.93 +
    1.94 +The symbol "||" represents literal-level disjunction and "&&" is
    1.95 +clause-level conjunction. Rules will typically lift formula-level
    1.96 +conjunctions; for instance the following rule lifts object-level
    1.97 +disjunction:
    1.98 +
    1.99 +          {    (A | B) = true    || ... } && ...
   1.100 +          --------------------------------------
   1.101 +          { A = true || B = true || ... } && ...
   1.102 +
   1.103 +
   1.104 +Using this setup, efficiency might be gained by only interpreting
   1.105 +inferences once, merging identical inference steps, and merging
   1.106 +identical subproofs into single inferences thus avoiding some effort.
   1.107 +We can also attempt to minimising proof search when interpreting
   1.108 +inferences.
   1.109 +
   1.110 +It is hoped that this setup can target other provers by modifying the
   1.111 +clause representation to fit them, and adapting the inference
   1.112 +interpretation to handle the rules used by the prover. It should also
   1.113 +facilitate composing together proofs found by different provers.
   1.114 +*}
   1.115 +
   1.116 +
   1.117 +subsection "Instantiation"
   1.118 +
   1.119 +lemma polar_allE [rule_format]:
   1.120 +  "\<lbrakk>(\<forall>x. P x) = True; (P x) = True \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
   1.121 +  "\<lbrakk>(\<exists>x. P x) = False; (P x) = False \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
   1.122 +by auto
   1.123 +
   1.124 +lemma polar_exE [rule_format]:
   1.125 +  "\<lbrakk>(\<exists>x. P x) = True; \<And>x. (P x) = True \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
   1.126 +  "\<lbrakk>(\<forall>x. P x) = False; \<And>x. (P x) = False \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R"
   1.127 +by auto
   1.128 +
   1.129 +ML {*
   1.130 +(*This carries out an allE-like rule but on (polarised) literals.
   1.131 + Instead of yielding a free variable (which is a hell for the
   1.132 + matcher) it seeks to use one of the subgoals' parameters.
   1.133 + This ought to be sufficient for emulating extcnf_combined,
   1.134 + but note that the complexity of the problem can be enormous.*)
   1.135 +fun inst_parametermatch_tac ctxt thms i = fn st =>
   1.136 +  let
   1.137 +    val gls =
   1.138 +      prop_of st
   1.139 +      |> Logic.strip_horn
   1.140 +      |> fst
   1.141 +
   1.142 +    val parameters =
   1.143 +      if null gls then []
   1.144 +      else
   1.145 +        rpair (i - 1) gls
   1.146 +        |> uncurry nth
   1.147 +        |> strip_top_all_vars []
   1.148 +        |> fst
   1.149 +        |> map fst (*just get the parameter names*)
   1.150 +  in
   1.151 +    if null parameters then no_tac st
   1.152 +    else
   1.153 +      let
   1.154 +        fun instantiate param =
   1.155 +           (map (eres_inst_tac ctxt [(("x", 0), param)]) thms
   1.156 +                   |> FIRST')
   1.157 +        val attempts = map instantiate parameters
   1.158 +      in
   1.159 +        (fold (curry (op APPEND')) attempts (K no_tac)) i st
   1.160 +      end
   1.161 +  end
   1.162 +
   1.163 +(*Attempts to use the polar_allE theorems on a specific subgoal.*)
   1.164 +fun forall_pos_tac ctxt = inst_parametermatch_tac ctxt @{thms polar_allE}
   1.165 +*}
   1.166 +
   1.167 +ML {*
   1.168 +(*This is similar to inst_parametermatch_tac, but prefers to
   1.169 +  match variables having identical names. Logically, this is
   1.170 +  a hack. But it reduces the complexity of the problem.*)
   1.171 +fun nominal_inst_parametermatch_tac ctxt thm i = fn st =>
   1.172 +  let
   1.173 +    val gls =
   1.174 +      prop_of st
   1.175 +      |> Logic.strip_horn
   1.176 +      |> fst
   1.177 +
   1.178 +    val parameters =
   1.179 +      if null gls then []
   1.180 +      else
   1.181 +        rpair (i - 1) gls
   1.182 +        |> uncurry nth
   1.183 +        |> strip_top_all_vars []
   1.184 +        |> fst
   1.185 +        |> map fst (*just get the parameter names*)
   1.186 +  in
   1.187 +    if null parameters then no_tac st
   1.188 +    else
   1.189 +      let
   1.190 +        fun instantiates param =
   1.191 +           eres_inst_tac ctxt [(("x", 0), param)] thm
   1.192 +
   1.193 +        val quantified_var = head_quantified_variable i st
   1.194 +      in
   1.195 +        if is_none quantified_var then no_tac st
   1.196 +        else
   1.197 +          if member (op =) parameters (the quantified_var |> fst) then
   1.198 +            instantiates (the quantified_var |> fst) i st
   1.199 +          else
   1.200 +            K no_tac i st
   1.201 +      end
   1.202 +  end
   1.203 +*}
   1.204 +
   1.205 +
   1.206 +subsection "Prefix massaging"
   1.207 +
   1.208 +ML {*
   1.209 +exception NO_GOALS
   1.210 +
   1.211 +(*Get quantifier prefix of the hypothesis and conclusion, reorder
   1.212 +  the hypothesis' quantifiers to have the ones appearing in the
   1.213 +  conclusion first.*)
   1.214 +fun canonicalise_qtfr_order ctxt i = fn st =>
   1.215 +  let
   1.216 +    val gls =
   1.217 +      prop_of st
   1.218 +      |> Logic.strip_horn
   1.219 +      |> fst
   1.220 +  in
   1.221 +    if null gls then raise NO_GOALS
   1.222 +    else
   1.223 +      let
   1.224 +        val (params, (hyp_clause, conc_clause)) =
   1.225 +          rpair (i - 1) gls
   1.226 +          |> uncurry nth
   1.227 +          |> strip_top_all_vars []
   1.228 +          |> apsnd Logic.dest_implies
   1.229 +
   1.230 +        val (hyp_quants, hyp_body) =
   1.231 +          HOLogic.dest_Trueprop hyp_clause
   1.232 +          |> strip_top_All_vars
   1.233 +          |> apfst rev
   1.234 +
   1.235 +        val conc_quants =
   1.236 +          HOLogic.dest_Trueprop conc_clause
   1.237 +          |> strip_top_All_vars
   1.238 +          |> fst
   1.239 +
   1.240 +        val new_hyp =
   1.241 +          (* fold absfree new_hyp_prefix hyp_body *)
   1.242 +          (*HOLogic.list_all*)
   1.243 +          fold_rev (fn (v, ty) => fn t => HOLogic.mk_all (v, ty, t))
   1.244 +           (prefix_intersection_list
   1.245 +             hyp_quants conc_quants)
   1.246 +           hyp_body
   1.247 +          |> HOLogic.mk_Trueprop
   1.248 +
   1.249 +         val thm = Goal.prove ctxt [] []
   1.250 +           (Logic.mk_implies (hyp_clause, new_hyp))
   1.251 +           (fn _ =>
   1.252 +              (REPEAT_DETERM (HEADGOAL (rtac @{thm allI})))
   1.253 +              THEN (REPEAT_DETERM
   1.254 +                    (HEADGOAL
   1.255 +                     (nominal_inst_parametermatch_tac ctxt @{thm allE})))
   1.256 +              THEN HEADGOAL atac)
   1.257 +      in
   1.258 +        dtac thm i st
   1.259 +      end
   1.260 +    end
   1.261 +*}
   1.262 +
   1.263 +
   1.264 +subsection "Some general rules and congruences"
   1.265 +
   1.266 +(*this isn't an actual rule used in Leo2, but it seems to be
   1.267 +  applied implicitly during some Leo2 inferences.*)
   1.268 +lemma polarise: "P ==> P = True" by auto
   1.269 +
   1.270 +ML {*
   1.271 +fun is_polarised t =
   1.272 +  (TPTP_Reconstruct.remove_polarity true t; true)
   1.273 +  handle TPTP_Reconstruct.UNPOLARISED _ => false
   1.274 +
   1.275 +val polarise_subgoal_hyps =
   1.276 +  COND' (SOME #> TERMPRED is_polarised (fn _ => true)) (K no_tac) (dtac @{thm polarise})
   1.277 +*}
   1.278 +
   1.279 +lemma simp_meta [rule_format]:
   1.280 +  "(A --> B) == (~A | B)"
   1.281 +  "(A | B) | C == A | B | C"
   1.282 +  "(A & B) & C == A & B & C"
   1.283 +  "(~ (~ A)) == A"
   1.284 +  (* "(A & B) == (~ (~A | ~B))" *)
   1.285 +  "~ (A & B) == (~A | ~B)"
   1.286 +  "~(A | B) == (~A) & (~B)"
   1.287 +by auto
   1.288 +
   1.289 +
   1.290 +subsection "Emulation of Leo2's inference rules"
   1.291 +
   1.292 +(*this is not included in simp_meta since it would make a mess of the polarities*)
   1.293 +lemma expand_iff [rule_format]:
   1.294 + "((A :: bool) = B) \<equiv> (~ A | B) & (~ B | A)"
   1.295 +by (rule eq_reflection, auto)
   1.296 +
   1.297 +lemma polarity_switch [rule_format]:
   1.298 +  "(\<not> P) = True \<Longrightarrow> P = False"
   1.299 +  "(\<not> P) = False \<Longrightarrow> P = True"
   1.300 +  "P = False \<Longrightarrow> (\<not> P) = True"
   1.301 +  "P = True \<Longrightarrow> (\<not> P) = False"
   1.302 +by auto
   1.303 +
   1.304 +lemma solved_all_splits: "False = True \<Longrightarrow> False" by simp
   1.305 +ML {*
   1.306 +val solved_all_splits_tac =
   1.307 +  TRY (etac @{thm conjE} 1)
   1.308 +  THEN rtac @{thm solved_all_splits} 1
   1.309 +  THEN atac 1
   1.310 +*}
   1.311 +
   1.312 +lemma lots_of_logic_expansions_meta [rule_format]:
   1.313 +  "(((A :: bool) = B) = True) == (((A \<longrightarrow> B) = True) & ((B \<longrightarrow> A) = True))"
   1.314 +  "((A :: bool) = B) = False == (((~A) | B) = False) | (((~B) | A) = False)"
   1.315 +
   1.316 +  "((F = G) = True) == (! x. (F x = G x)) = True"
   1.317 +  "((F = G) = False) == (! x. (F x = G x)) = False"
   1.318 +
   1.319 +  "(A | B) = True == (A = True) | (B = True)"
   1.320 +  "(A & B) = False == (A = False) | (B = False)"
   1.321 +  "(A | B) = False == (A = False) & (B = False)"
   1.322 +  "(A & B) = True == (A = True) & (B = True)"
   1.323 +  "(~ A) = True == A = False"
   1.324 +  "(~ A) = False == A = True"
   1.325 +  "~ (A = True) == A = False"
   1.326 +  "~ (A = False) == A = True"
   1.327 +by (rule eq_reflection, auto)+
   1.328 +
   1.329 +(*this is used in extcnf_combined handler*)
   1.330 +lemma eq_neg_bool: "((A :: bool) = B) = False ==> ((~ (A | B)) | ~ ((~ A) | (~ B))) = False"
   1.331 +by auto
   1.332 +
   1.333 +lemma eq_pos_bool:
   1.334 +  "((A :: bool) = B) = True ==> ((~ (A | B)) | ~ (~ A | ~ B)) = True"
   1.335 +  "(A = B) = True \<Longrightarrow> A = True \<or> B = False"
   1.336 +  "(A = B) = True \<Longrightarrow> A = False \<or> B = True"
   1.337 +by auto
   1.338 +
   1.339 +(*next formula is more versatile than
   1.340 +    "(F = G) = True \<Longrightarrow> \<forall>x. ((F x = G x) = True)"
   1.341 +  since it doesn't assume that clause is singleton. After splitqtfr,
   1.342 +  and after applying allI exhaustively to the conclusion, we can
   1.343 +  use the existing functions to find the "(F x = G x) = True"
   1.344 +  disjunct in the conclusion*)
   1.345 +lemma eq_pos_func: "\<And> x. (F = G) = True \<Longrightarrow> (F x = G x) = True"
   1.346 +by auto
   1.347 +
   1.348 +(*make sure the conclusion consists of just "False"*)
   1.349 +lemma flip:
   1.350 +  "((A = True) ==> False) ==> A = False"
   1.351 +  "((A = False) ==> False) ==> A = True"
   1.352 +by auto
   1.353 +
   1.354 +(*FIXME try to use Drule.equal_elim_rule1 directly for this*)
   1.355 +lemma equal_elim_rule1: "(A \<equiv> B) \<Longrightarrow> A \<Longrightarrow> B" by auto
   1.356 +lemmas leo2_rules =
   1.357 + lots_of_logic_expansions_meta[THEN equal_elim_rule1]
   1.358 +
   1.359 +(*FIXME is there any overlap with lots_of_logic_expansions_meta or leo2_rules?*)
   1.360 +lemma extuni_bool2 [rule_format]: "(A = B) = False \<Longrightarrow> (A = True) | (B = True)" by auto
   1.361 +lemma extuni_bool1 [rule_format]: "(A = B) = False \<Longrightarrow> (A = False) | (B = False)" by auto
   1.362 +lemma extuni_triv [rule_format]: "(A = A) = False \<Longrightarrow> R" by auto
   1.363 +
   1.364 +(*Order (of A, B, C, D) matters*)
   1.365 +lemma dec_commut_eq [rule_format]:
   1.366 +  "((A = B) = (C = D)) = False \<Longrightarrow> (B = C) = False | (A = D) = False"
   1.367 +  "((A = B) = (C = D)) = False \<Longrightarrow> (B = D) = False | (A = C) = False"
   1.368 +by auto
   1.369 +lemma dec_commut_disj [rule_format]:
   1.370 +  "((A \<or> B) = (C \<or> D)) = False \<Longrightarrow> (B = C) = False \<or> (A = D) = False"
   1.371 +by auto
   1.372 +
   1.373 +lemma extuni_func [rule_format]: "(F = G) = False \<Longrightarrow> (! X. (F X = G X)) = False" by auto
   1.374 +
   1.375 +
   1.376 +subsection "Emulation: tactics"
   1.377 +
   1.378 +ML {*
   1.379 +(*Instantiate a variable according to the info given in the
   1.380 +  proof annotation. Through this we avoid having to come up
   1.381 +  with instantiations during reconstruction.*)
   1.382 +fun bind_tac ctxt prob_name ordered_binds =
   1.383 +  let
   1.384 +    val thy = Proof_Context.theory_of ctxt
   1.385 +    fun term_to_string t =
   1.386 +        Print_Mode.with_modes [""]
   1.387 +          (fn () => Output.output (Syntax.string_of_term ctxt t)) ()
   1.388 +    val ordered_instances =
   1.389 +      TPTP_Reconstruct.interpret_bindings prob_name thy ordered_binds []
   1.390 +      |> map (snd #> term_to_string)
   1.391 +      |> permute
   1.392 +
   1.393 +    (*instantiate a list of variables, order matters*)
   1.394 +    fun instantiate_vars ctxt vars : tactic =
   1.395 +      map (fn var =>
   1.396 +            Rule_Insts.eres_inst_tac ctxt
   1.397 +             [(("x", 0), var)] @{thm allE} 1)
   1.398 +          vars
   1.399 +      |> EVERY
   1.400 +
   1.401 +    fun instantiate_tac vars =
   1.402 +      instantiate_vars ctxt vars
   1.403 +      THEN (HEADGOAL atac)
   1.404 +  in
   1.405 +    HEADGOAL (canonicalise_qtfr_order ctxt)
   1.406 +    THEN (REPEAT_DETERM (HEADGOAL (rtac @{thm allI})))
   1.407 +    THEN REPEAT_DETERM (HEADGOAL (nominal_inst_parametermatch_tac ctxt @{thm allE}))
   1.408 +    (*now only the variable to instantiate should be left*)
   1.409 +    THEN FIRST (map instantiate_tac ordered_instances)
   1.410 +  end
   1.411 +*}
   1.412 +
   1.413 +ML {*
   1.414 +(*Simplification tactics*)
   1.415 +local
   1.416 +  fun rew_goal_tac thms ctxt i =
   1.417 +    rewrite_goal_tac ctxt thms i
   1.418 +    |> CHANGED
   1.419 +in
   1.420 +  val expander_animal =
   1.421 +    rew_goal_tac (@{thms simp_meta} @ @{thms lots_of_logic_expansions_meta})
   1.422 +
   1.423 +  val simper_animal =
   1.424 +    rew_goal_tac @{thms simp_meta}
   1.425 +end
   1.426 +*}
   1.427 +
   1.428 +lemma prop_normalise [rule_format]:
   1.429 +  "(A | B) | C == A | B | C"
   1.430 +  "(A & B) & C == A & B & C"
   1.431 +  "A | B == ~(~A & ~B)"
   1.432 +  "~~ A == A"
   1.433 +by auto
   1.434 +ML {*
   1.435 +(*i.e., break_conclusion*)
   1.436 +fun flip_conclusion_tac ctxt =
   1.437 +  let
   1.438 +    val default_tac =
   1.439 +      (TRY o CHANGED o (rewrite_goal_tac ctxt @{thms prop_normalise}))
   1.440 +      THEN' rtac @{thm notI}
   1.441 +      THEN' (REPEAT_DETERM o etac @{thm conjE})
   1.442 +      THEN' (TRY o (expander_animal ctxt))
   1.443 +  in
   1.444 +    default_tac ORELSE' resolve_tac @{thms flip}
   1.445 +  end
   1.446 +*}
   1.447 +
   1.448 +
   1.449 +subsection "Skolemisation"
   1.450 +
   1.451 +lemma skolemise [rule_format]:
   1.452 +  "\<forall> P. (~ (! x. P x)) \<longrightarrow> ~ (P (SOME x. ~ P x))"
   1.453 +proof -
   1.454 +  have "\<And> P. (~ (! x. P x)) \<Longrightarrow> ~ (P (SOME x. ~ P x))"
   1.455 +  proof -
   1.456 +    fix P
   1.457 +    assume ption: "~ (! x. P x)"
   1.458 +    hence a: "? x. ~ P x" by force
   1.459 +
   1.460 +    have hilbert : "\<And> P. (? x. P x) \<Longrightarrow> (P (SOME x. P x))"
   1.461 +    proof -
   1.462 +      fix P
   1.463 +      assume "(? x. P x)"
   1.464 +      thus "(P (SOME x. P x))"
   1.465 +        apply auto
   1.466 +        apply (rule someI)
   1.467 +        apply auto
   1.468 +        done
   1.469 +    qed
   1.470 +
   1.471 +    from a show "~ P (SOME x. ~ P x)"
   1.472 +    proof -
   1.473 +      assume "? x. ~ P x"
   1.474 +      hence "\<not> P (SOME x. \<not> P x)" by (rule hilbert)
   1.475 +      thus ?thesis .
   1.476 +    qed
   1.477 +  qed
   1.478 +  thus ?thesis by blast
   1.479 +qed
   1.480 +
   1.481 +lemma polar_skolemise [rule_format]:
   1.482 +  "\<forall> P. (! x. P x) = False \<longrightarrow> (P (SOME x. ~ P x)) = False"
   1.483 +proof -
   1.484 +  have "\<And> P. (! x. P x) = False \<Longrightarrow> (P (SOME x. ~ P x)) = False"
   1.485 +  proof -
   1.486 +    fix P
   1.487 +    assume ption: "(! x. P x) = False"
   1.488 +    hence "\<not> (\<forall> x. P x)" by force
   1.489 +    hence "\<not> All P" by force
   1.490 +    hence "\<not> (P (SOME x. \<not> P x))" by (rule skolemise)
   1.491 +    thus "(P (SOME x. \<not> P x)) = False" by force
   1.492 +  qed
   1.493 +  thus ?thesis by blast
   1.494 +qed
   1.495 +
   1.496 +lemma leo2_skolemise [rule_format]:
   1.497 +  "\<forall> P sk. (! x. P x) = False \<longrightarrow> (sk = (SOME x. ~ P x)) \<longrightarrow> (P sk) = False"
   1.498 +by (clarify, rule polar_skolemise)
   1.499 +
   1.500 +lemma lift_forall [rule_format]:
   1.501 +  "!! x. (! x. A x) = True ==> (A x) = True"
   1.502 +  "!! x. (? x. A x) = False ==> (A x) = False"
   1.503 +by auto
   1.504 +lemma lift_exists [rule_format]:
   1.505 +  "\<lbrakk>(All P) = False; sk = (SOME x. \<not> P x)\<rbrakk> \<Longrightarrow> P sk = False"
   1.506 +  "\<lbrakk>(Ex P) = True; sk = (SOME x. P x)\<rbrakk> \<Longrightarrow> P sk = True"
   1.507 +apply (drule polar_skolemise, simp)
   1.508 +apply (simp, drule someI_ex, simp)
   1.509 +done
   1.510 +
   1.511 +ML {*
   1.512 +(*FIXME LHS should be constant. Currently allow variables for testing. Probably should still allow Vars (but not Frees) since they'll act as intermediate values*)
   1.513 +fun conc_is_skolem_def t =
   1.514 +  case t of
   1.515 +      Const (@{const_name HOL.eq}, _) $ t' $ (Const (@{const_name Hilbert_Choice.Eps}, _) $ _) =>
   1.516 +      let
   1.517 +        val (h, args) =
   1.518 +          strip_comb t'
   1.519 +          |> apfst (strip_abs #> snd #> strip_comb #> fst)
   1.520 +        val get_const_name = dest_Const #> fst
   1.521 +        val h_property =
   1.522 +          is_Free h orelse
   1.523 +          is_Var h orelse
   1.524 +          (is_Const h
   1.525 +           andalso (get_const_name h <> get_const_name @{term HOL.Ex})
   1.526 +           andalso (get_const_name h <> get_const_name @{term HOL.All})
   1.527 +           andalso (h <> @{term Hilbert_Choice.Eps})
   1.528 +           andalso (h <> @{term HOL.conj})
   1.529 +           andalso (h <> @{term HOL.disj})
   1.530 +           andalso (h <> @{term HOL.eq})
   1.531 +           andalso (h <> @{term HOL.implies})
   1.532 +           andalso (h <> @{term HOL.The})
   1.533 +           andalso (h <> @{term HOL.Ex1})
   1.534 +           andalso (h <> @{term HOL.Not})
   1.535 +           andalso (h <> @{term HOL.iff})
   1.536 +           andalso (h <> @{term HOL.not_equal}))
   1.537 +        val args_property =
   1.538 +          fold (fn t => fn b =>
   1.539 +           b andalso is_Free t) args true
   1.540 +      in
   1.541 +        h_property andalso args_property
   1.542 +      end
   1.543 +    | _ => false
   1.544 +*}
   1.545 +
   1.546 +ML {*
   1.547 +(*Hack used to detect if a Skolem definition, with an LHS Var, has had the LHS instantiated into an unacceptable term.*)
   1.548 +fun conc_is_bad_skolem_def t =
   1.549 +  case t of
   1.550 +      Const (@{const_name HOL.eq}, _) $ t' $ (Const (@{const_name Hilbert_Choice.Eps}, _) $ _) =>
   1.551 +      let
   1.552 +        val (h, args) = strip_comb t'
   1.553 +        val get_const_name = dest_Const #> fst
   1.554 +        val const_h_test =
   1.555 +          if is_Const h then
   1.556 +            (get_const_name h = get_const_name @{term HOL.Ex})
   1.557 +             orelse (get_const_name h = get_const_name @{term HOL.All})
   1.558 +             orelse (h = @{term Hilbert_Choice.Eps})
   1.559 +             orelse (h = @{term HOL.conj})
   1.560 +             orelse (h = @{term HOL.disj})
   1.561 +             orelse (h = @{term HOL.eq})
   1.562 +             orelse (h = @{term HOL.implies})
   1.563 +             orelse (h = @{term HOL.The})
   1.564 +             orelse (h = @{term HOL.Ex1})
   1.565 +             orelse (h = @{term HOL.Not})
   1.566 +             orelse (h = @{term HOL.iff})
   1.567 +             orelse (h = @{term HOL.not_equal})
   1.568 +          else true
   1.569 +        val h_property =
   1.570 +          not (is_Free h) andalso
   1.571 +          not (is_Var h) andalso
   1.572 +          const_h_test
   1.573 +        val args_property =
   1.574 +          fold (fn t => fn b =>
   1.575 +           b andalso is_Free t) args true
   1.576 +      in
   1.577 +        h_property andalso args_property
   1.578 +      end
   1.579 +    | _ => false
   1.580 +*}
   1.581 +
   1.582 +ML {*
   1.583 +fun get_skolem_conc t =
   1.584 +  let
   1.585 +    val t' =
   1.586 +      strip_top_all_vars [] t
   1.587 +      |> snd
   1.588 +      |> try_dest_Trueprop
   1.589 +  in
   1.590 +    case t' of
   1.591 +        Const (@{const_name HOL.eq}, _) $ t' $ (Const (@{const_name Hilbert_Choice.Eps}, _) $ _) => SOME t'
   1.592 +      | _ => NONE
   1.593 +  end
   1.594 +
   1.595 +fun get_skolem_conc_const t =
   1.596 +  lift_option
   1.597 +   (fn t' =>
   1.598 +     head_of t'
   1.599 +     |> strip_abs_body
   1.600 +     |> head_of
   1.601 +     |> dest_Const)
   1.602 +   (get_skolem_conc t)
   1.603 +*}
   1.604 +
   1.605 +(*
   1.606 +Technique for handling quantifiers:
   1.607 +  Principles:
   1.608 +  * allE should always match with a !!
   1.609 +  * exE should match with a constant,
   1.610 +     or bind a fresh !! -- currently not doing the latter since it never seems to arised in normal Leo2 proofs.
   1.611 +*)
   1.612 +
   1.613 +ML {*
   1.614 +fun forall_neg_tac candidate_consts ctxt i = fn st =>
   1.615 +  let
   1.616 +    val thy = Proof_Context.theory_of ctxt
   1.617 +
   1.618 +    val gls =
   1.619 +      prop_of st
   1.620 +      |> Logic.strip_horn
   1.621 +      |> fst
   1.622 +
   1.623 +    val parameters =
   1.624 +      if null gls then ""
   1.625 +      else
   1.626 +        rpair (i - 1) gls
   1.627 +        |> uncurry nth
   1.628 +        |> strip_top_all_vars []
   1.629 +        |> fst
   1.630 +        |> map fst (*just get the parameter names*)
   1.631 +        |> (fn l =>
   1.632 +              if null l then ""
   1.633 +              else
   1.634 +                space_implode " " l
   1.635 +                |> pair " "
   1.636 +                |> op ^)
   1.637 +
   1.638 +  in
   1.639 +    if null gls orelse null candidate_consts then no_tac st
   1.640 +    else
   1.641 +      let
   1.642 +        fun instantiate const_name =
   1.643 +          dres_inst_tac ctxt [(("sk", 0), const_name ^ parameters)] @{thm leo2_skolemise}
   1.644 +        val attempts = map instantiate candidate_consts
   1.645 +      in
   1.646 +        (fold (curry (op APPEND')) attempts (K no_tac)) i st
   1.647 +      end
   1.648 +  end
   1.649 +*}
   1.650 +
   1.651 +ML {*
   1.652 +exception SKOLEM_DEF of term (*The tactic wasn't pointed at a skolem definition*)
   1.653 +exception NO_SKOLEM_DEF of (*skolem const name*)string * Binding.binding * term (*The tactic could not find a skolem definition in the theory*)
   1.654 +fun absorb_skolem_def ctxt prob_name_opt i = fn st =>
   1.655 +  let
   1.656 +    val thy = Proof_Context.theory_of ctxt
   1.657 +
   1.658 +    val gls =
   1.659 +      prop_of st
   1.660 +      |> Logic.strip_horn
   1.661 +      |> fst
   1.662 +
   1.663 +    val conclusion =
   1.664 +      if null gls then
   1.665 +        (*this should never be thrown*)
   1.666 +        raise NO_GOALS
   1.667 +      else
   1.668 +        rpair (i - 1) gls
   1.669 +        |> uncurry nth
   1.670 +        |> strip_top_all_vars []
   1.671 +        |> snd
   1.672 +        |> Logic.strip_horn
   1.673 +        |> snd
   1.674 +
   1.675 +    fun skolem_const_info_of t =
   1.676 +      case t of
   1.677 +          Const (@{const_name HOL.Trueprop}, _) $ (Const (@{const_name HOL.eq}, _) $ t' $ (Const (@{const_name Hilbert_Choice.Eps}, _) $ _)) =>
   1.678 +          head_of t'
   1.679 +          |> strip_abs_body (*since in general might have a skolem term, so we want to rip out the prefixing lambdas to get to the constant (which should be at head position)*)
   1.680 +          |> head_of
   1.681 +          |> dest_Const
   1.682 +        | _ => raise SKOLEM_DEF t
   1.683 +
   1.684 +    val const_name =
   1.685 +      skolem_const_info_of conclusion
   1.686 +      |> fst
   1.687 +
   1.688 +    val def_name = const_name ^ "_def"
   1.689 +
   1.690 +    val bnd_def = (*FIXME consts*)
   1.691 +      const_name
   1.692 +      |> space_implode "." o tl o space_explode "." (*FIXME hack to drop theory-name prefix*)
   1.693 +      |> Binding.qualified_name
   1.694 +      |> Binding.suffix_name "_def"
   1.695 +
   1.696 +    val bnd_name =
   1.697 +      case prob_name_opt of
   1.698 +          NONE => bnd_def
   1.699 +        | SOME prob_name =>
   1.700 +(*            Binding.qualify false
   1.701 +             (TPTP_Problem_Name.mangle_problem_name prob_name)
   1.702 +*)
   1.703 +             bnd_def
   1.704 +
   1.705 +    val thm =
   1.706 +      if Name_Space.defined_entry (Theory.axiom_space thy) def_name then
   1.707 +        Thm.axiom thy def_name
   1.708 +      else
   1.709 +        if is_none prob_name_opt then
   1.710 +          (*This mode is for testing, so we can be a bit
   1.711 +            looser with theories*)
   1.712 +          Thm.add_axiom_global (bnd_name, conclusion) thy
   1.713 +          |> fst |> snd
   1.714 +        else
   1.715 +          raise (NO_SKOLEM_DEF (def_name, bnd_name, conclusion))
   1.716 +  in
   1.717 +    rtac (Drule.export_without_context thm) i st
   1.718 +  end
   1.719 +  handle SKOLEM_DEF _ => no_tac st
   1.720 +*}
   1.721 +
   1.722 +ML {*
   1.723 +(*
   1.724 +In current system, there should only be 2 subgoals: the one where
   1.725 +the skolem definition is being built (with a Var in the LHS), and the other subgoal using Var.
   1.726 +*)
   1.727 +(*arity must be greater than 0. if arity=0 then
   1.728 +  there's no need to use this expensive matching.*)
   1.729 +fun find_skolem_term ctxt consts_candidate arity = fn st =>
   1.730 +  let
   1.731 +    val _ = @{assert} (arity > 0)
   1.732 +
   1.733 +    val gls =
   1.734 +      prop_of st
   1.735 +      |> Logic.strip_horn
   1.736 +      |> fst
   1.737 +
   1.738 +    (*extract the conclusion of each subgoal*)
   1.739 +    val conclusions =
   1.740 +      if null gls then
   1.741 +        raise NO_GOALS
   1.742 +      else
   1.743 +        map (strip_top_all_vars [] #> snd #> Logic.strip_horn #> snd) gls
   1.744 +        (*Remove skolem-definition conclusion, to avoid wasting time analysing it*)
   1.745 +        |> List.filter (try_dest_Trueprop #> conc_is_skolem_def #> not)
   1.746 +        (*There should only be a single goal*) (*FIXME this might not always be the case, in practice*)
   1.747 +        (* |> tap (fn x => @{assert} (is_some (try the_single x))) *)
   1.748 +
   1.749 +    (*look for subterms headed by a skolem constant, and whose
   1.750 +      arguments are all parameter Vars*)
   1.751 +    fun get_skolem_terms args (acc : term list) t =
   1.752 +      case t of
   1.753 +          (c as Const _) $ (v as Free _) =>
   1.754 +            if c = consts_candidate andalso
   1.755 +             arity = length args + 1 then
   1.756 +              (list_comb (c, v :: args)) :: acc
   1.757 +            else acc
   1.758 +        | t1 $ (v as Free _) =>
   1.759 +            get_skolem_terms (v :: args) acc t1 @
   1.760 +             get_skolem_terms [] acc t1
   1.761 +        | t1 $ t2 =>
   1.762 +            get_skolem_terms [] acc t1 @
   1.763 +             get_skolem_terms [] acc t2
   1.764 +        | Abs (_, _, t') => get_skolem_terms [] acc t'
   1.765 +        | _ => acc
   1.766 +  in
   1.767 +    map (strip_top_All_vars #> snd) conclusions
   1.768 +    |> map (get_skolem_terms [] [])
   1.769 +    |> List.concat
   1.770 +    |> distinct (op =)
   1.771 +  end
   1.772 +*}
   1.773 +
   1.774 +ML {*
   1.775 +fun instantiate_skols ctxt consts_candidates i = fn st =>
   1.776 +  let
   1.777 +    val thy = Proof_Context.theory_of ctxt
   1.778 +
   1.779 +    val gls =
   1.780 +      prop_of st
   1.781 +      |> Logic.strip_horn
   1.782 +      |> fst
   1.783 +
   1.784 +    val (params, conclusion) =
   1.785 +      if null gls then
   1.786 +        raise NO_GOALS
   1.787 +      else
   1.788 +        rpair (i - 1) gls
   1.789 +        |> uncurry nth
   1.790 +        |> strip_top_all_vars []
   1.791 +        |> apsnd (Logic.strip_horn #> snd)
   1.792 +
   1.793 +    fun skolem_const_info_of t =
   1.794 +      case t of
   1.795 +          Const (@{const_name HOL.Trueprop}, _) $ (Const (@{const_name HOL.eq}, _) $ lhs $ (Const (@{const_name Hilbert_Choice.Eps}, _) $ rhs)) =>
   1.796 +          let
   1.797 +            (*the parameters we will concern ourselves with*)
   1.798 +            val params' =
   1.799 +              Term.add_frees lhs []
   1.800 +              |> distinct (op =)
   1.801 +            (*check to make sure that params' <= params*)
   1.802 +            val _ = @{assert} (List.all (member (op =) params) params')
   1.803 +            val skolem_const_ty =
   1.804 +              let
   1.805 +                val (skolem_const_prety, no_params) =
   1.806 +                  Term.strip_comb lhs
   1.807 +                  |> apfst (dest_Var #> snd) (*head of lhs consists of a logical variable. we just want its type.*)
   1.808 +                  |> apsnd length
   1.809 +
   1.810 +                val _ = @{assert} (length params = no_params)
   1.811 +
   1.812 +                (*get value type of a function type after n arguments have been supplied*)
   1.813 +                fun get_val_ty n ty =
   1.814 +                  if n = 0 then ty
   1.815 +                  else get_val_ty (n - 1) (dest_funT ty |> snd)
   1.816 +              in
   1.817 +                get_val_ty no_params skolem_const_prety
   1.818 +              end
   1.819 +
   1.820 +          in
   1.821 +            (skolem_const_ty, params')
   1.822 +          end
   1.823 +        | _ => raise (SKOLEM_DEF t)
   1.824 +
   1.825 +(*
   1.826 +find skolem const candidates which, after applying distinct members of params' we end up with, give us something of type skolem_const_ty.
   1.827 +
   1.828 +given a candidate's type, skolem_const_ty, and params', we get some pemutations of params' (i.e. the order in which they can be given to the candidate in order to get skolem_const_ty). If the list of permutations is empty, then we cannot use that candidate.
   1.829 +*)
   1.830 +(*
   1.831 +only returns a single matching -- since terms are linear, and variable arguments are Vars, order shouldn't matter, so we can ignore permutations.
   1.832 +doesn't work with polymorphism (for which we'd need to use type unification) -- this is OK since no terms should be polymorphic, since Leo2 proofs aren't.
   1.833 +*)
   1.834 +    fun use_candidate target_ty params acc cur_ty =
   1.835 +      if null params then
   1.836 +        if Type.eq_type Vartab.empty (cur_ty, target_ty) then
   1.837 +          SOME (rev acc)
   1.838 +        else NONE
   1.839 +      else
   1.840 +        let
   1.841 +          val (arg_ty, val_ty) = Term.dest_funT cur_ty
   1.842 +          (*now find a param of type arg_ty*)
   1.843 +          val (candidate_param, params') =
   1.844 +            find_and_remove
   1.845 +             (snd #> pair arg_ty #> Type.eq_type Vartab.empty)
   1.846 +             params
   1.847 +        in
   1.848 +          use_candidate target_ty params' (candidate_param :: acc) val_ty
   1.849 +        end
   1.850 +        handle TYPE ("dest_funT", _, _) => NONE
   1.851 +             | DEST_LIST => NONE
   1.852 +
   1.853 +    val (skolem_const_ty, params') = skolem_const_info_of conclusion
   1.854 +
   1.855 +(*
   1.856 +For each candidate, build a term and pass it to Thm.instantiate, whic in turn is chained with PRIMITIVE to give us this_tactic.
   1.857 +
   1.858 +Big picture:
   1.859 +  we run the following:
   1.860 +    drule leo2_skolemise THEN' this_tactic
   1.861 +
   1.862 +NOTE: remember to APPEND' instead of ORELSE' the two tactics relating to skolemisation
   1.863 +*)
   1.864 +
   1.865 +    val filtered_candidates =
   1.866 +      map (dest_Const
   1.867 +           #> snd
   1.868 +           #> use_candidate skolem_const_ty params' [])
   1.869 +       consts_candidates (* prefiltered_candidates *)
   1.870 +      |> pair consts_candidates (* prefiltered_candidates *)
   1.871 +      |> ListPair.zip
   1.872 +      |> filter (snd #> is_none #> not)
   1.873 +      |> map (apsnd the)
   1.874 +
   1.875 +    val skolem_terms =
   1.876 +      let
   1.877 +        fun make_result_t (t, args) =
   1.878 +          (* list_comb (t, map Free args) *)
   1.879 +          if length args > 0 then
   1.880 +            hd (find_skolem_term ctxt t (length args) st)
   1.881 +          else t
   1.882 +      in
   1.883 +        map make_result_t filtered_candidates
   1.884 +      end
   1.885 +
   1.886 +    (*prefix a skolem term with bindings for the parameters*)
   1.887 +    (* val contextualise = fold absdummy (map snd params) *)
   1.888 +    val contextualise = fold absfree params
   1.889 +
   1.890 +    val skolem_cts = map (contextualise #> cterm_of thy) skolem_terms
   1.891 +
   1.892 +
   1.893 +(*now the instantiation code*)
   1.894 +
   1.895 +    (*there should only be one Var -- that is from the previous application of drule leo2_skolemise. We look for it at the head position in some equation at a conclusion of a subgoal.*)
   1.896 +    val var_opt =
   1.897 +      let
   1.898 +        val pre_var =
   1.899 +          gls
   1.900 +          |> map
   1.901 +              (strip_top_all_vars [] #> snd #>
   1.902 +               Logic.strip_horn #> snd #>
   1.903 +               get_skolem_conc)
   1.904 +          |> switch (fold (fn x => fn l => if is_some x then the x :: l else l)) []
   1.905 +          |> map (switch Term.add_vars [])
   1.906 +          |> List.concat
   1.907 +
   1.908 +        fun make_var pre_var =
   1.909 +          the_single pre_var
   1.910 +          |> Var
   1.911 +          |> cterm_of thy
   1.912 +          |> SOME
   1.913 +      in
   1.914 +        if null pre_var then NONE
   1.915 +        else make_var pre_var
   1.916 +     end
   1.917 +
   1.918 +    fun instantiate_tac from to =
   1.919 +      Thm.instantiate ([], [(from, to)])
   1.920 +      |> PRIMITIVE
   1.921 +
   1.922 +    val tectic =
   1.923 +      if is_none var_opt then no_tac
   1.924 +      else
   1.925 +        fold (curry (op APPEND)) (map (instantiate_tac (the var_opt)) skolem_cts) no_tac
   1.926 +
   1.927 +  in
   1.928 +    tectic st
   1.929 +  end
   1.930 +*}
   1.931 +
   1.932 +ML {*
   1.933 +fun new_skolem_tac ctxt consts_candidates =
   1.934 +  let
   1.935 +    fun tec thm =
   1.936 +      dtac thm
   1.937 +      THEN' instantiate_skols ctxt consts_candidates
   1.938 +  in
   1.939 +    if null consts_candidates then K no_tac
   1.940 +    else FIRST' (map tec @{thms lift_exists})
   1.941 +  end
   1.942 +*}
   1.943 +
   1.944 +(*
   1.945 +need a tactic to expand "? x . P" to "~ ! x. ~ P"
   1.946 +*)
   1.947 +ML {*
   1.948 +fun ex_expander_tac ctxt i =
   1.949 +   let
   1.950 +     val simpset =
   1.951 +       empty_simpset ctxt (*NOTE for some reason, Bind exception gets raised if ctxt's simpset isn't emptied*)
   1.952 +       |> Simplifier.add_simp @{lemma "Ex P == (~ (! x. ~ P x))" by auto}
   1.953 +   in
   1.954 +     CHANGED (asm_full_simp_tac simpset i)
   1.955 +   end
   1.956 +*}
   1.957 +
   1.958 +
   1.959 +subsubsection "extuni_dec"
   1.960 +
   1.961 +ML {*
   1.962 +(*n-ary decomposition. Code is based on the n-ary arg_cong generator*)
   1.963 +fun extuni_dec_n ctxt arity =
   1.964 +  let
   1.965 +    val _ = @{assert} (arity > 0)
   1.966 +    val is =
   1.967 +      upto (1, arity)
   1.968 +      |> map Int.toString
   1.969 +    val arg_tys = map (fn i => TFree ("arg" ^ i ^ "_ty", HOLogic.typeS)) is
   1.970 +    val res_ty = TFree ("res" ^ "_ty", HOLogic.typeS)
   1.971 +    val f_ty = arg_tys ---> res_ty
   1.972 +    val f = Free ("f", f_ty)
   1.973 +    val xs = map (fn i =>
   1.974 +      Free ("x" ^ i, TFree ("arg" ^ i ^ "_ty", HOLogic.typeS))) is
   1.975 +    (*FIXME DRY principle*)
   1.976 +    val ys = map (fn i =>
   1.977 +      Free ("y" ^ i, TFree ("arg" ^ i ^ "_ty", HOLogic.typeS))) is
   1.978 +
   1.979 +    val hyp_lhs = list_comb (f, xs)
   1.980 +    val hyp_rhs = list_comb (f, ys)
   1.981 +    val hyp_eq =
   1.982 +      HOLogic.eq_const res_ty $ hyp_lhs $ hyp_rhs
   1.983 +    val hyp =
   1.984 +      HOLogic.eq_const HOLogic.boolT $ hyp_eq $ @{term False}
   1.985 +      |> HOLogic.mk_Trueprop
   1.986 +    fun conc_eq i =
   1.987 +      let
   1.988 +        val ty = TFree ("arg" ^ i ^ "_ty", HOLogic.typeS)
   1.989 +        val x = Free ("x" ^ i, ty)
   1.990 +        val y = Free ("y" ^ i, ty)
   1.991 +        val eq = HOLogic.eq_const ty $ x $ y
   1.992 +      in
   1.993 +        HOLogic.eq_const HOLogic.boolT $ eq $ @{term False}
   1.994 +      end
   1.995 +
   1.996 +    val conc_disjs = map conc_eq is
   1.997 +
   1.998 +    val conc =
   1.999 +      if length conc_disjs = 1 then
  1.1000 +        the_single conc_disjs
  1.1001 +      else
  1.1002 +        fold
  1.1003 +         (fn t => fn t_conc => HOLogic.mk_disj (t_conc, t))
  1.1004 +         (tl conc_disjs) (hd conc_disjs)
  1.1005 +
  1.1006 +    val t =
  1.1007 +      Logic.mk_implies (hyp, HOLogic.mk_Trueprop conc)
  1.1008 +  in
  1.1009 +    Goal.prove ctxt [] [] t (fn _ => auto_tac ctxt)
  1.1010 +    |> Drule.export_without_context
  1.1011 +  end
  1.1012 +*}
  1.1013 +
  1.1014 +ML {*
  1.1015 +(*Determine the arity of a function which the "dec"
  1.1016 +  unification rule is about to be applied.
  1.1017 +  NOTE:
  1.1018 +    * Assumes that there is a single hypothesis
  1.1019 +*)
  1.1020 +fun find_dec_arity i = fn st =>
  1.1021 +  let
  1.1022 +    val gls =
  1.1023 +      prop_of st
  1.1024 +      |> Logic.strip_horn
  1.1025 +      |> fst
  1.1026 +  in
  1.1027 +    if null gls then raise NO_GOALS
  1.1028 +    else
  1.1029 +      let
  1.1030 +        val (params, (literal, conc_clause)) =
  1.1031 +          rpair (i - 1) gls
  1.1032 +          |> uncurry nth
  1.1033 +          |> strip_top_all_vars []
  1.1034 +          |> apsnd Logic.strip_horn
  1.1035 +          |> apsnd (apfst the_single)
  1.1036 +
  1.1037 +        val get_ty =
  1.1038 +          HOLogic.dest_Trueprop
  1.1039 +          #> strip_top_All_vars
  1.1040 +          #> snd
  1.1041 +          #> HOLogic.dest_eq (*polarity's "="*)
  1.1042 +          #> fst
  1.1043 +          #> HOLogic.dest_eq (*the unification constraint's "="*)
  1.1044 +          #> fst
  1.1045 +          #> head_of
  1.1046 +          #> dest_Const
  1.1047 +          #> snd
  1.1048 +
  1.1049 +       fun arity_of ty =
  1.1050 +         let
  1.1051 +           val (_, res_ty) = dest_funT ty
  1.1052 +
  1.1053 +         in
  1.1054 +           1 + arity_of res_ty
  1.1055 +         end
  1.1056 +         handle (TYPE ("dest_funT", _, _)) => 0
  1.1057 +
  1.1058 +      in
  1.1059 +        arity_of (get_ty literal)
  1.1060 +      end
  1.1061 +  end
  1.1062 +
  1.1063 +(*given an inference, it returns the parameters (i.e., we've already matched the leading & shared quantification in the hypothesis & conclusion clauses), and the "raw" inference*)
  1.1064 +fun breakdown_inference i = fn st =>
  1.1065 +  let
  1.1066 +    val gls =
  1.1067 +      prop_of st
  1.1068 +      |> Logic.strip_horn
  1.1069 +      |> fst
  1.1070 +  in
  1.1071 +    if null gls then raise NO_GOALS
  1.1072 +    else
  1.1073 +      rpair (i - 1) gls
  1.1074 +      |> uncurry nth
  1.1075 +      |> strip_top_all_vars []
  1.1076 +  end
  1.1077 +
  1.1078 +(*build a custom elimination rule for extuni_dec, and instantiate it to match a specific subgoal*)
  1.1079 +fun extuni_dec_elim_rule ctxt arity i = fn st =>
  1.1080 +  let
  1.1081 +    val rule = extuni_dec_n ctxt arity
  1.1082 +
  1.1083 +    val rule_hyp =
  1.1084 +      prop_of rule
  1.1085 +      |> Logic.dest_implies
  1.1086 +      |> fst (*assuming that rule has single hypothesis*)
  1.1087 +
  1.1088 +    (*having run break_hypothesis earlier, we know that the hypothesis
  1.1089 +      now consists of a single literal. We can (and should)
  1.1090 +      disregard the conclusion, since it hasn't been "broken",
  1.1091 +      and it might include some unwanted literals -- the latter
  1.1092 +      could cause "diff" to fail (since they won't agree with the
  1.1093 +      rule we have generated.*)
  1.1094 +
  1.1095 +    val inference_hyp =
  1.1096 +      snd (breakdown_inference i st)
  1.1097 +      |> Logic.dest_implies
  1.1098 +      |> fst (*assuming that inference has single hypothesis,
  1.1099 +               as explained above.*)
  1.1100 +  in
  1.1101 +    TPTP_Reconstruct_Library.diff_and_instantiate ctxt rule rule_hyp inference_hyp
  1.1102 +  end
  1.1103 +
  1.1104 +fun extuni_dec_tac ctxt i = fn st =>
  1.1105 +  let
  1.1106 +    val arity = find_dec_arity i st
  1.1107 +
  1.1108 +    fun elim_tac i st =
  1.1109 +      let
  1.1110 +        val rule =
  1.1111 +          extuni_dec_elim_rule ctxt arity i st
  1.1112 +          (*in case we itroduced free variables during
  1.1113 +            instantiation, we generalise the rule to make
  1.1114 +            those free variables into logical variables.*)
  1.1115 +          |> Thm.forall_intr_frees
  1.1116 +          |> Drule.export_without_context
  1.1117 +      in dtac rule i st end
  1.1118 +      handle NO_GOALS => no_tac st
  1.1119 +
  1.1120 +    fun closure tac =
  1.1121 +     (*batter fails if there's no toplevel disjunction in the
  1.1122 +       hypothesis, so we also try atac*)
  1.1123 +      SOLVE o (tac THEN' (batter ORELSE' atac))
  1.1124 +    val search_tac =
  1.1125 +      ASAP
  1.1126 +        (rtac @{thm disjI1} APPEND' rtac @{thm disjI2})
  1.1127 +        (FIRST' (map closure
  1.1128 +                  [dresolve_tac @{thms dec_commut_eq},
  1.1129 +                   dtac @{thm dec_commut_disj},
  1.1130 +                   elim_tac]))
  1.1131 +  in
  1.1132 +    (CHANGED o search_tac) i st
  1.1133 +  end
  1.1134 +*}
  1.1135 +
  1.1136 +
  1.1137 +subsubsection "standard_cnf"
  1.1138 +(*Given a standard_cnf inference, normalise it
  1.1139 +     e.g. ((A & B) & C \<longrightarrow> D & E \<longrightarrow> F \<longrightarrow> G) = False
  1.1140 +     is changed to
  1.1141 +          (A & B & C & D & E & F \<longrightarrow> G) = False
  1.1142 + then custom-build a metatheorem which validates this:
  1.1143 +          (A & B & C & D & E & F \<longrightarrow> G) = False
  1.1144 +       -------------------------------------------
  1.1145 +          (A = True) & (B = True) & (C = True) &
  1.1146 +          (D = True) & (E = True) & (F = True) & (G = False)
  1.1147 + and apply this metatheorem.
  1.1148 +
  1.1149 +There aren't any "positive" standard_cnfs in Leo2's calculus:
  1.1150 +  e.g.,  "(A \<longrightarrow> B) = True \<Longrightarrow> A = False | (A = True & B = True)"
  1.1151 +since "standard_cnf" seems to be applied at the preprocessing
  1.1152 +stage, together with splitting.
  1.1153 +*)
  1.1154 +
  1.1155 +ML {*
  1.1156 +(*Conjunctive counterparts to Term.disjuncts_aux and Term.disjuncts*)
  1.1157 +fun conjuncts_aux (Const (@{const_name HOL.conj}, _) $ t $ t') conjs =
  1.1158 +     conjuncts_aux t (conjuncts_aux t' conjs)
  1.1159 +  | conjuncts_aux t conjs = t :: conjs
  1.1160 +
  1.1161 +fun conjuncts t = conjuncts_aux t []
  1.1162 +
  1.1163 +(*HOL equivalent of Logic.strip_horn*)
  1.1164 +local
  1.1165 +  fun imp_strip_horn' acc (Const (@{const_name HOL.implies}, _) $ A $ B) =
  1.1166 +        imp_strip_horn' (A :: acc) B
  1.1167 +    | imp_strip_horn' acc t = (acc, t)
  1.1168 +in
  1.1169 +  fun imp_strip_horn t =
  1.1170 +    imp_strip_horn' [] t
  1.1171 +    |> apfst rev
  1.1172 +end
  1.1173 +*}
  1.1174 +
  1.1175 +ML {*
  1.1176 +(*Returns whether the antecedents are separated by conjunctions
  1.1177 +  or implications; the number of antecedents; and the polarity
  1.1178 +  of the original clause -- I think this will always be "false".*)
  1.1179 +fun standard_cnf_type ctxt i : thm -> (TPTP_Reconstruct.formula_kind * int * bool) option = fn st =>
  1.1180 +  let
  1.1181 +    val gls =
  1.1182 +      prop_of st
  1.1183 +      |> Logic.strip_horn
  1.1184 +      |> fst
  1.1185 +
  1.1186 +    val hypos =
  1.1187 +      if null gls then raise NO_GOALS
  1.1188 +      else
  1.1189 +        rpair (i - 1) gls
  1.1190 +        |> uncurry nth
  1.1191 +        |> TPTP_Reconstruct.strip_top_all_vars []
  1.1192 +        |> snd
  1.1193 +        |> Logic.strip_horn
  1.1194 +        |> fst
  1.1195 +
  1.1196 +    (*hypothesis clause should be singleton*)
  1.1197 +    val _ = @{assert} (length hypos = 1)
  1.1198 +
  1.1199 +    val (t, pol) = the_single hypos
  1.1200 +      |> try_dest_Trueprop
  1.1201 +      |> TPTP_Reconstruct.strip_top_All_vars
  1.1202 +      |> snd
  1.1203 +      |> TPTP_Reconstruct.remove_polarity true
  1.1204 +
  1.1205 +    (*literal is negative*)
  1.1206 +    val _ = @{assert} (not pol)
  1.1207 +
  1.1208 +    val (antes, conc) = imp_strip_horn t
  1.1209 +
  1.1210 +    val (ante_type, antes') =
  1.1211 +      if length antes = 1 then
  1.1212 +        let
  1.1213 +          val conjunctive_antes =
  1.1214 +            the_single antes
  1.1215 +            |> conjuncts
  1.1216 +        in
  1.1217 +          if length conjunctive_antes > 1 then
  1.1218 +            (TPTP_Reconstruct.Conjunctive NONE,
  1.1219 +             conjunctive_antes)
  1.1220 +          else
  1.1221 +            (TPTP_Reconstruct.Implicational NONE,
  1.1222 +             antes)
  1.1223 +        end
  1.1224 +      else
  1.1225 +        (TPTP_Reconstruct.Implicational NONE,
  1.1226 +         antes)
  1.1227 +  in
  1.1228 +    if null antes then NONE
  1.1229 +    else SOME (ante_type, length antes', pol)
  1.1230 +  end
  1.1231 +*}
  1.1232 +
  1.1233 +ML {*
  1.1234 +(*Given a certain standard_cnf type, build a metatheorem that would
  1.1235 +  validate it*)
  1.1236 +fun mk_standard_cnf ctxt kind arity =
  1.1237 +  let
  1.1238 +    val _ = @{assert} (arity > 0)
  1.1239 +    val vars =
  1.1240 +      upto (1, arity + 1)
  1.1241 +      |> map (fn i => Free ("x" ^ Int.toString i, HOLogic.boolT))
  1.1242 +
  1.1243 +    val consequent = hd vars
  1.1244 +    val antecedents = tl vars
  1.1245 +
  1.1246 +    val conc =
  1.1247 +      fold
  1.1248 +       (curry HOLogic.mk_conj)
  1.1249 +       (map (fn var => HOLogic.mk_eq (var, @{term True})) antecedents)
  1.1250 +       (HOLogic.mk_eq (consequent, @{term False}))
  1.1251 +
  1.1252 +    val pre_hyp =
  1.1253 +      case kind of
  1.1254 +          TPTP_Reconstruct.Conjunctive NONE =>
  1.1255 +            curry HOLogic.mk_imp
  1.1256 +             (if length antecedents = 1 then the_single antecedents
  1.1257 +              else
  1.1258 +                fold (curry HOLogic.mk_conj) (tl antecedents) (hd antecedents))
  1.1259 +             (hd vars)
  1.1260 +        | TPTP_Reconstruct.Implicational NONE =>
  1.1261 +            fold (curry HOLogic.mk_imp) antecedents consequent
  1.1262 +
  1.1263 +    val hyp = HOLogic.mk_eq (pre_hyp, @{term False})
  1.1264 +
  1.1265 +    val t =
  1.1266 +      Logic.mk_implies (HOLogic.mk_Trueprop  hyp, HOLogic.mk_Trueprop conc)
  1.1267 +  in
  1.1268 +    Goal.prove ctxt [] [] t (fn _ => HEADGOAL (blast_tac ctxt))
  1.1269 +    |> Drule.export_without_context
  1.1270 +  end
  1.1271 +*}
  1.1272 +
  1.1273 +ML {*
  1.1274 +(*Applies a d-tactic, then breaks it up conjunctively.
  1.1275 +  This can be used to transform subgoals as follows:
  1.1276 +     (A \<longrightarrow> B) = False  \<Longrightarrow> R
  1.1277 +              |
  1.1278 +              v
  1.1279 +  \<lbrakk>A = True; B = False\<rbrakk> \<Longrightarrow> R
  1.1280 +*)
  1.1281 +fun weak_conj_tac drule =
  1.1282 +  dtac drule THEN' (REPEAT_DETERM o etac @{thm conjE})
  1.1283 +*}
  1.1284 +
  1.1285 +ML {*
  1.1286 +val uncurry_lit_neg_tac =
  1.1287 +  dtac @{lemma "(A \<longrightarrow> B \<longrightarrow> C) = False \<Longrightarrow> (A & B \<longrightarrow> C) = False" by auto}
  1.1288 +  #> REPEAT_DETERM
  1.1289 +*}
  1.1290 +
  1.1291 +ML {*
  1.1292 +fun standard_cnf_tac ctxt i = fn st =>
  1.1293 +  let
  1.1294 +    fun core_tactic i = fn st =>
  1.1295 +      case standard_cnf_type ctxt i st of
  1.1296 +          NONE => no_tac st
  1.1297 +        | SOME (kind, arity, _) =>
  1.1298 +            let
  1.1299 +              val rule = mk_standard_cnf ctxt kind arity;
  1.1300 +            in
  1.1301 +              (weak_conj_tac rule THEN' atac) i st
  1.1302 +            end
  1.1303 +  in
  1.1304 +    (uncurry_lit_neg_tac
  1.1305 +     THEN' TPTP_Reconstruct_Library.reassociate_conjs_tac ctxt
  1.1306 +     THEN' core_tactic) i st
  1.1307 +  end
  1.1308 +*}
  1.1309 +
  1.1310 +
  1.1311 +subsubsection "Emulator prep"
  1.1312 +
  1.1313 +ML {*
  1.1314 +datatype cleanup_feature =
  1.1315 +    RemoveHypothesesFromSkolemDefs
  1.1316 +  | RemoveDuplicates
  1.1317 +
  1.1318 +datatype loop_feature =
  1.1319 +    Close_Branch
  1.1320 +  | ConjI
  1.1321 +  | King_Cong
  1.1322 +  | Break_Hypotheses
  1.1323 +  | Donkey_Cong (*simper_animal + ex_expander_tac*)
  1.1324 +  | RemoveRedundantQuantifications
  1.1325 +  | Assumption
  1.1326 +
  1.1327 +  (*Closely based on Leo2 calculus*)
  1.1328 +  | Existential_Free
  1.1329 +  | Existential_Var
  1.1330 +  | Universal
  1.1331 +  | Not_pos
  1.1332 +  | Not_neg
  1.1333 +  | Or_pos
  1.1334 +  | Or_neg
  1.1335 +  | Equal_pos
  1.1336 +  | Equal_neg
  1.1337 +  | Extuni_Bool2
  1.1338 +  | Extuni_Bool1
  1.1339 +  | Extuni_Dec
  1.1340 +  | Extuni_Bind
  1.1341 +  | Extuni_Triv
  1.1342 +  | Extuni_FlexRigid
  1.1343 +  | Extuni_Func
  1.1344 +  | Polarity_switch
  1.1345 +  | Forall_special_pos
  1.1346 +
  1.1347 +datatype feature =
  1.1348 +    ConstsDiff
  1.1349 +  | StripQuantifiers
  1.1350 +  | Flip_Conclusion
  1.1351 +  | Loop of loop_feature list
  1.1352 +  | LoopOnce of loop_feature list
  1.1353 +  | InnerLoopOnce of loop_feature list
  1.1354 +  | CleanUp of cleanup_feature list
  1.1355 +  | AbsorbSkolemDefs
  1.1356 +*}
  1.1357 +
  1.1358 +ML {*
  1.1359 +fun can_feature x l =
  1.1360 +  let
  1.1361 +    fun sublist_of_clean_up el =
  1.1362 +      case el of
  1.1363 +          CleanUp l'' => SOME l''
  1.1364 +        | _ => NONE
  1.1365 +    fun sublist_of_loop el =
  1.1366 +      case el of
  1.1367 +          Loop l'' => SOME l''
  1.1368 +        | _ => NONE
  1.1369 +    fun sublist_of_loop_once el =
  1.1370 +      case el of
  1.1371 +          LoopOnce l'' => SOME l''
  1.1372 +        | _ => NONE
  1.1373 +    fun sublist_of_inner_loop_once el =
  1.1374 +      case el of
  1.1375 +          InnerLoopOnce l'' => SOME l''
  1.1376 +        | _ => NONE
  1.1377 +
  1.1378 +    fun check_sublist sought_sublist opt_list =
  1.1379 +      if List.all is_none opt_list then false
  1.1380 +      else
  1.1381 +        fold_options opt_list
  1.1382 +        |> List.concat
  1.1383 +        |> pair sought_sublist
  1.1384 +        |> subset (op =)
  1.1385 +  in
  1.1386 +    case x of
  1.1387 +        CleanUp l' =>
  1.1388 +          map sublist_of_clean_up l
  1.1389 +          |> check_sublist l'
  1.1390 +      | Loop l' =>
  1.1391 +          map sublist_of_loop l
  1.1392 +          |> check_sublist l'
  1.1393 +      | LoopOnce l' =>
  1.1394 +          map sublist_of_loop_once l
  1.1395 +          |> check_sublist l'
  1.1396 +      | InnerLoopOnce l' =>
  1.1397 +          map sublist_of_inner_loop_once l
  1.1398 +          |> check_sublist l'
  1.1399 +      | _ => List.exists (curry (op =) x) l
  1.1400 +  end;
  1.1401 +
  1.1402 +fun loop_can_feature loop_feats l =
  1.1403 +  can_feature (Loop loop_feats) l orelse
  1.1404 +  can_feature (LoopOnce loop_feats) l orelse
  1.1405 +  can_feature (InnerLoopOnce loop_feats) l;
  1.1406 +
  1.1407 +@{assert} (can_feature ConstsDiff [StripQuantifiers, ConstsDiff]);
  1.1408 +
  1.1409 +@{assert}
  1.1410 +  (can_feature (CleanUp [RemoveHypothesesFromSkolemDefs])
  1.1411 +    [CleanUp [RemoveHypothesesFromSkolemDefs, RemoveDuplicates]]);
  1.1412 +
  1.1413 +@{assert}
  1.1414 +  (can_feature (Loop []) [Loop [Existential_Var]]);
  1.1415 +
  1.1416 +@{assert}
  1.1417 +  (not (can_feature (Loop []) [InnerLoopOnce [Existential_Var]]));
  1.1418 +*}
  1.1419 +
  1.1420 +ML {*
  1.1421 +exception NO_LOOP_FEATS
  1.1422 +fun get_loop_feats (feats : feature list) =
  1.1423 +  let
  1.1424 +    val loop_find =
  1.1425 +      fold (fn x => fn loop_feats_acc =>
  1.1426 +        if is_some loop_feats_acc then loop_feats_acc
  1.1427 +        else
  1.1428 +          case x of
  1.1429 +              Loop loop_feats => SOME loop_feats
  1.1430 +            | LoopOnce loop_feats => SOME loop_feats
  1.1431 +            | InnerLoopOnce loop_feats => SOME loop_feats
  1.1432 +            | _ => NONE)
  1.1433 +       feats
  1.1434 +       NONE
  1.1435 +  in
  1.1436 +    if is_some loop_find then the loop_find
  1.1437 +    else raise NO_LOOP_FEATS
  1.1438 +  end;
  1.1439 +
  1.1440 +@{assert}
  1.1441 +  (get_loop_feats [Loop [King_Cong, Break_Hypotheses, Existential_Free, Existential_Var, Universal]] =
  1.1442 +   [King_Cong, Break_Hypotheses, Existential_Free, Existential_Var, Universal])
  1.1443 +*}
  1.1444 +
  1.1445 +(*use as elim rule to remove premises*)
  1.1446 +lemma insa_prems: "\<lbrakk>Q; P\<rbrakk> \<Longrightarrow> P" by auto
  1.1447 +ML {*
  1.1448 +fun cleanup_skolem_defs feats =
  1.1449 +  let
  1.1450 +    (*remove hypotheses from skolem defs,
  1.1451 +     after testing that they look like skolem defs*)
  1.1452 +    val dehypothesise_skolem_defs =
  1.1453 +      COND' (SOME #> TERMPRED (fn _ => true) conc_is_skolem_def)
  1.1454 +        (REPEAT_DETERM o etac @{thm insa_prems})
  1.1455 +        (K no_tac)
  1.1456 +  in
  1.1457 +    if can_feature (CleanUp [RemoveHypothesesFromSkolemDefs]) feats then
  1.1458 +      ALLGOALS (TRY o dehypothesise_skolem_defs)
  1.1459 +    else all_tac
  1.1460 +  end
  1.1461 +*}
  1.1462 +
  1.1463 +ML {*
  1.1464 +fun remove_duplicates_tac feats =
  1.1465 +  (if can_feature (CleanUp [RemoveDuplicates]) feats then
  1.1466 +     ALLGOALS distinct_subgoal_tac
  1.1467 +   else all_tac)
  1.1468 +*}
  1.1469 +
  1.1470 +ML {*
  1.1471 +(*given a goal state, indicates the skolem constants committed-to in it (i.e. appearing in LHS of a skolem definition)*)
  1.1472 +val which_skolem_concs_used = fn st =>
  1.1473 +  let
  1.1474 +    val feats = [CleanUp [RemoveHypothesesFromSkolemDefs, RemoveDuplicates]]
  1.1475 +    val scrubup_tac =
  1.1476 +      cleanup_skolem_defs feats
  1.1477 +      THEN remove_duplicates_tac feats
  1.1478 +  in
  1.1479 +    scrubup_tac st
  1.1480 +    |> break_seq
  1.1481 +    |> tap (fn (_, rest) => @{assert} (null (Seq.list_of rest)))
  1.1482 +    |> fst
  1.1483 +    |> TERMFUN (snd (*discard hypotheses*)
  1.1484 +                 #> get_skolem_conc_const) NONE
  1.1485 +    |> switch (fold (fn x => fn l => if is_some x then the x :: l else l)) []
  1.1486 +    |> map Const
  1.1487 +  end
  1.1488 +*}
  1.1489 +
  1.1490 +ML {*
  1.1491 +fun exists_tac ctxt feats consts_diff =
  1.1492 +  let
  1.1493 +    val ex_var =
  1.1494 +      if loop_can_feature [Existential_Var] feats andalso consts_diff <> [] then
  1.1495 +        new_skolem_tac ctxt consts_diff
  1.1496 +        (*We're making sure that each skolem constant is used once in instantiations.*)
  1.1497 +      else K no_tac
  1.1498 +
  1.1499 +    val ex_free =
  1.1500 +      if loop_can_feature [Existential_Free] feats andalso consts_diff = [] then
  1.1501 +        eresolve_tac @{thms polar_exE}
  1.1502 +      else K no_tac
  1.1503 +  in
  1.1504 +    ex_var APPEND' ex_free
  1.1505 +  end
  1.1506 +
  1.1507 +fun forall_tac ctxt feats =
  1.1508 +  if loop_can_feature [Universal] feats then
  1.1509 +    forall_pos_tac ctxt
  1.1510 +  else K no_tac
  1.1511 +*}
  1.1512 +
  1.1513 +
  1.1514 +subsubsection "Finite types"
  1.1515 +(*lift quantification from a singleton literal to a singleton clause*)
  1.1516 +lemma forall_pos_lift:
  1.1517 +"\<lbrakk>(! X. P X) = True; ! X. (P X = True) \<Longrightarrow> R\<rbrakk> \<Longrightarrow> R" by auto
  1.1518 +
  1.1519 +(*predicate over the type of the leading quantified variable*)
  1.1520 +
  1.1521 +ML {*
  1.1522 +val extcnf_forall_special_pos_tac =
  1.1523 +  let
  1.1524 +    val bool =
  1.1525 +      ["True", "False"]
  1.1526 +
  1.1527 +    val bool_to_bool =
  1.1528 +      ["% _ . True", "% _ . False", "% x . x", "Not"]
  1.1529 +
  1.1530 +    val tecs =
  1.1531 +      map (fn t_s =>
  1.1532 +       eres_inst_tac @{context} [(("x", 0), t_s)] @{thm allE}
  1.1533 +       THEN' atac)
  1.1534 +  in
  1.1535 +    (TRY o etac @{thm forall_pos_lift})
  1.1536 +    THEN' (atac
  1.1537 +           ORELSE' FIRST'
  1.1538 +            (*FIXME could check the type of the leading quantified variable, instead of trying everything*)
  1.1539 +            (tecs (bool @ bool_to_bool)))
  1.1540 +  end
  1.1541 +*}
  1.1542 +
  1.1543 +
  1.1544 +subsubsection "Emulator"
  1.1545 +
  1.1546 +lemma efq: "[|A = True; A = False|] ==> R" by auto
  1.1547 +ML {*
  1.1548 +val efq_tac =
  1.1549 +  (etac @{thm efq} THEN' atac)
  1.1550 +  ORELSE' atac
  1.1551 +*}
  1.1552 +
  1.1553 +ML {*
  1.1554 +(*This is applied to all subgoals, repeatedly*)
  1.1555 +fun extcnf_combined_main ctxt feats consts_diff =
  1.1556 +  let
  1.1557 +    (*This is applied to subgoals which don't have a conclusion
  1.1558 +      consisting of a Skolem definition*)
  1.1559 +    fun extcnf_combined_tac' ctxt i = fn st =>
  1.1560 +      let
  1.1561 +        val skolem_consts_used_so_far = which_skolem_concs_used st
  1.1562 +        val consts_diff' = subtract (op =) skolem_consts_used_so_far consts_diff
  1.1563 +
  1.1564 +        fun feat_to_tac feat =
  1.1565 +          case feat of
  1.1566 +              Close_Branch => trace_tac' "mark: closer" efq_tac
  1.1567 +            | ConjI => trace_tac' "mark: conjI" (rtac @{thm conjI})
  1.1568 +            | King_Cong => trace_tac' "mark: expander_animal" (expander_animal ctxt)
  1.1569 +            | Break_Hypotheses => trace_tac' "mark: break_hypotheses" break_hypotheses
  1.1570 +            | RemoveRedundantQuantifications => K all_tac
  1.1571 +(*
  1.1572 +FIXME Building this into the loop instead.. maybe not the ideal choice
  1.1573 +            | RemoveRedundantQuantifications =>
  1.1574 +                trace_tac' "mark: strip_unused_variable_hyp"
  1.1575 +                 (REPEAT_DETERM o remove_redundant_quantification_in_lit)
  1.1576 +*)
  1.1577 +
  1.1578 +            | Assumption => atac
  1.1579 +(*FIXME both Existential_Free and Existential_Var run same code*)
  1.1580 +            | Existential_Free => trace_tac' "mark: forall_neg" (exists_tac ctxt feats consts_diff')
  1.1581 +            | Existential_Var => trace_tac' "mark: forall_neg" (exists_tac ctxt feats consts_diff')
  1.1582 +            | Universal => trace_tac' "mark: forall_pos" (forall_tac ctxt feats)
  1.1583 +            | Not_pos => trace_tac' "mark: not_pos" (dtac @{thm leo2_rules(9)})
  1.1584 +            | Not_neg => trace_tac' "mark: not_neg" (dtac @{thm leo2_rules(10)})
  1.1585 +            | Or_pos => trace_tac' "mark: or_pos" (dtac @{thm leo2_rules(5)}) (*could add (6) for negated conjunction*)
  1.1586 +            | Or_neg => trace_tac' "mark: or_neg" (dtac @{thm leo2_rules(7)})
  1.1587 +            | Equal_pos => trace_tac' "mark: equal_pos" (dresolve_tac (@{thms eq_pos_bool} @ [@{thm leo2_rules(3)}, @{thm eq_pos_func}]))
  1.1588 +            | Equal_neg => trace_tac' "mark: equal_neg" (dresolve_tac [@{thm eq_neg_bool}, @{thm leo2_rules(4)}])
  1.1589 +            | Donkey_Cong => trace_tac' "mark: donkey_cong" (simper_animal ctxt THEN' ex_expander_tac ctxt)
  1.1590 +
  1.1591 +            | Extuni_Bool2 => trace_tac' "mark: extuni_bool2" (dtac @{thm extuni_bool2})
  1.1592 +            | Extuni_Bool1 => trace_tac' "mark: extuni_bool1" (dtac @{thm extuni_bool1})
  1.1593 +            | Extuni_Bind => trace_tac' "mark: extuni_triv" (etac @{thm extuni_triv})
  1.1594 +            | Extuni_Triv => trace_tac' "mark: extuni_triv" (etac @{thm extuni_triv})
  1.1595 +            | Extuni_Dec => trace_tac' "mark: extuni_dec_tac" (extuni_dec_tac ctxt)
  1.1596 +            | Extuni_FlexRigid => trace_tac' "mark: extuni_flex_rigid" (atac ORELSE' asm_full_simp_tac ctxt)
  1.1597 +            | Extuni_Func => trace_tac' "mark: extuni_func" (dtac @{thm extuni_func})
  1.1598 +            | Polarity_switch => trace_tac' "mark: polarity_switch" (eresolve_tac @{thms polarity_switch})
  1.1599 +            | Forall_special_pos => trace_tac' "mark: dorall_special_pos" extcnf_forall_special_pos_tac
  1.1600 +
  1.1601 +        val core_tac =
  1.1602 +          get_loop_feats feats
  1.1603 +          |> map feat_to_tac
  1.1604 +          |> FIRST'
  1.1605 +      in
  1.1606 +        core_tac i st
  1.1607 +      end
  1.1608 +
  1.1609 +    (*This is applied to all subgoals, repeatedly*)
  1.1610 +    fun extcnf_combined_tac ctxt i =
  1.1611 +      COND (TERMPRED (fn _ => true) conc_is_skolem_def (SOME i))
  1.1612 +        no_tac
  1.1613 +        (extcnf_combined_tac' ctxt i)
  1.1614 +
  1.1615 +    val core_tac = CHANGED (ALLGOALS (IF_UNSOLVED o TRY o extcnf_combined_tac ctxt))
  1.1616 +
  1.1617 +    val full_tac = REPEAT core_tac
  1.1618 +
  1.1619 +  in
  1.1620 +    CHANGED
  1.1621 +      (if can_feature (InnerLoopOnce []) feats then
  1.1622 +         core_tac
  1.1623 +       else full_tac)
  1.1624 +  end
  1.1625 +
  1.1626 +val interpreted_consts =
  1.1627 +  [@{const_name HOL.All}, @{const_name HOL.Ex},
  1.1628 +   @{const_name Hilbert_Choice.Eps},
  1.1629 +   @{const_name HOL.conj},
  1.1630 +   @{const_name HOL.disj},
  1.1631 +   @{const_name HOL.eq},
  1.1632 +   @{const_name HOL.implies},
  1.1633 +   @{const_name HOL.The},
  1.1634 +   @{const_name HOL.Ex1},
  1.1635 +   @{const_name HOL.Not},
  1.1636 +   (* @{const_name HOL.iff}, *) (*FIXME do these exist?*)
  1.1637 +   (* @{const_name HOL.not_equal}, *)
  1.1638 +   @{const_name HOL.False},
  1.1639 +   @{const_name HOL.True},
  1.1640 +   @{const_name "==>"}]
  1.1641 +
  1.1642 +fun strip_qtfrs_tac ctxt =
  1.1643 +  REPEAT_DETERM (HEADGOAL (rtac @{thm allI}))
  1.1644 +  THEN REPEAT_DETERM (HEADGOAL (etac @{thm exE}))
  1.1645 +  THEN HEADGOAL (canonicalise_qtfr_order ctxt)
  1.1646 +  THEN
  1.1647 +    ((REPEAT (HEADGOAL (nominal_inst_parametermatch_tac ctxt @{thm allE})))
  1.1648 +     APPEND (REPEAT (HEADGOAL (inst_parametermatch_tac ctxt [@{thm allE}]))))
  1.1649 +  (*FIXME need to handle "@{thm exI}"?*)
  1.1650 +
  1.1651 +(*difference in constants between the hypothesis clause and the conclusion clause*)
  1.1652 +fun clause_consts_diff thm =
  1.1653 +  let
  1.1654 +    val t =
  1.1655 +      prop_of thm
  1.1656 +      |> Logic.dest_implies
  1.1657 +      |> fst
  1.1658 +
  1.1659 +      (*This bit should not be needed, since Leo2 inferences don't have parameters*)
  1.1660 +      |> TPTP_Reconstruct.strip_top_all_vars []
  1.1661 +      |> snd
  1.1662 +
  1.1663 +    val do_diff =
  1.1664 +      Logic.dest_implies
  1.1665 +      #> uncurry TPTP_Reconstruct.new_consts_between
  1.1666 +      #> filter
  1.1667 +           (fn Const (n, _) =>
  1.1668 +             not (member (op =) interpreted_consts n))
  1.1669 +  in
  1.1670 +    if head_of t = Logic.implies then do_diff t
  1.1671 +    else []
  1.1672 +  end
  1.1673 +*}
  1.1674 +
  1.1675 +ML {*
  1.1676 +(*remove quantification in hypothesis clause (! X. t), if
  1.1677 +  X not free in t*)
  1.1678 +fun remove_redundant_quantification ctxt i = fn st =>
  1.1679 +  let
  1.1680 +    val gls =
  1.1681 +      prop_of st
  1.1682 +      |> Logic.strip_horn
  1.1683 +      |> fst
  1.1684 +  in
  1.1685 +    if null gls then raise NO_GOALS
  1.1686 +    else
  1.1687 +      let
  1.1688 +        val (params, (hyp_clauses, conc_clause)) =
  1.1689 +          rpair (i - 1) gls
  1.1690 +          |> uncurry nth
  1.1691 +          |> TPTP_Reconstruct.strip_top_all_vars []
  1.1692 +          |> apsnd Logic.strip_horn
  1.1693 +      in
  1.1694 +        (*this is to fail gracefully in case this tactic is applied to a goal which doesn't have a single hypothesis*)
  1.1695 +        if length hyp_clauses > 1 then no_tac st
  1.1696 +        else
  1.1697 +          let
  1.1698 +            val hyp_clause = the_single hyp_clauses
  1.1699 +            val sep_prefix =
  1.1700 +              HOLogic.dest_Trueprop
  1.1701 +              #> TPTP_Reconstruct.strip_top_All_vars
  1.1702 +              #> apfst rev
  1.1703 +            val (hyp_prefix, hyp_body) = sep_prefix hyp_clause
  1.1704 +            val (conc_prefix, conc_body) = sep_prefix conc_clause
  1.1705 +          in
  1.1706 +            if null hyp_prefix orelse
  1.1707 +              member (op =) conc_prefix (hd hyp_prefix) orelse
  1.1708 +              member (op =)  (Term.add_frees hyp_body []) (hd hyp_prefix) then
  1.1709 +              no_tac st
  1.1710 +            else
  1.1711 +              eres_inst_tac ctxt [(("x", 0), "(@X. False)")] @{thm allE} i st
  1.1712 +          end
  1.1713 +     end
  1.1714 +  end
  1.1715 +*}
  1.1716 +
  1.1717 +ML {*
  1.1718 +fun remove_redundant_quantification_ignore_skolems ctxt i =
  1.1719 +  COND (TERMPRED (fn _ => true) conc_is_skolem_def (SOME i))
  1.1720 +    no_tac
  1.1721 +    (remove_redundant_quantification ctxt i)
  1.1722 +*}
  1.1723 +
  1.1724 +lemma drop_redundant_literal_qtfr:
  1.1725 +  "(! X. P) = True \<Longrightarrow> P = True"
  1.1726 +  "(? X. P) = True \<Longrightarrow> P = True"
  1.1727 +  "(! X. P) = False \<Longrightarrow> P = False"
  1.1728 +  "(? X. P) = False \<Longrightarrow> P = False"
  1.1729 +by auto
  1.1730 +
  1.1731 +ML {*
  1.1732 +(*remove quantification in the literal "(! X. t) = True/False"
  1.1733 +  in the singleton hypothesis clause, if X not free in t*)
  1.1734 +fun remove_redundant_quantification_in_lit ctxt i = fn st =>
  1.1735 +  let
  1.1736 +    val gls =
  1.1737 +      prop_of st
  1.1738 +      |> Logic.strip_horn
  1.1739 +      |> fst
  1.1740 +  in
  1.1741 +    if null gls then raise NO_GOALS
  1.1742 +    else
  1.1743 +      let
  1.1744 +        val (params, (hyp_clauses, conc_clause)) =
  1.1745 +          rpair (i - 1) gls
  1.1746 +          |> uncurry nth
  1.1747 +          |> TPTP_Reconstruct.strip_top_all_vars []
  1.1748 +          |> apsnd Logic.strip_horn
  1.1749 +      in
  1.1750 +        (*this is to fail gracefully in case this tactic is applied to a goal which doesn't have a single hypothesis*)
  1.1751 +        if length hyp_clauses > 1 then no_tac st
  1.1752 +        else
  1.1753 +          let
  1.1754 +            fun literal_content (Const (@{const_name HOL.eq}, _) $ lhs $ (rhs as @{term True})) = SOME (lhs, rhs)
  1.1755 +              | literal_content (Const (@{const_name HOL.eq}, _) $ lhs $ (rhs as @{term False})) = SOME (lhs, rhs)
  1.1756 +              | literal_content t = NONE
  1.1757 +
  1.1758 +            val hyp_clause =
  1.1759 +              the_single hyp_clauses
  1.1760 +              |> HOLogic.dest_Trueprop
  1.1761 +              |> literal_content
  1.1762 +
  1.1763 +          in
  1.1764 +            if is_none hyp_clause then
  1.1765 +              no_tac st
  1.1766 +            else
  1.1767 +              let
  1.1768 +                val (hyp_lit_prefix, hyp_lit_body) =
  1.1769 +                  the hyp_clause
  1.1770 +                  |> (fn (t, polarity) =>
  1.1771 +                       TPTP_Reconstruct.strip_top_All_vars t
  1.1772 +                       |> apfst rev)
  1.1773 +              in
  1.1774 +                if null hyp_lit_prefix orelse
  1.1775 +                  member (op =)  (Term.add_frees hyp_lit_body []) (hd hyp_lit_prefix) then
  1.1776 +                  no_tac st
  1.1777 +                else
  1.1778 +                  dresolve_tac @{thms drop_redundant_literal_qtfr} i st
  1.1779 +              end
  1.1780 +          end
  1.1781 +     end
  1.1782 +  end
  1.1783 +*}
  1.1784 +
  1.1785 +ML {*
  1.1786 +fun remove_redundant_quantification_in_lit_ignore_skolems ctxt i =
  1.1787 +  COND (TERMPRED (fn _ => true) conc_is_skolem_def (SOME i))
  1.1788 +    no_tac
  1.1789 +    (remove_redundant_quantification_in_lit ctxt i)
  1.1790 +*}
  1.1791 +
  1.1792 +ML {*
  1.1793 +fun extcnf_combined_tac ctxt prob_name_opt feats skolem_consts = fn st =>
  1.1794 +  let
  1.1795 +    val thy = Proof_Context.theory_of ctxt
  1.1796 +
  1.1797 +    (*Initially, st consists of a single goal, showing the
  1.1798 +      hypothesis clause implying the conclusion clause.
  1.1799 +      There are no parameters.*)
  1.1800 +    val consts_diff =
  1.1801 +      union (op =) skolem_consts
  1.1802 +       (if can_feature ConstsDiff feats then
  1.1803 +          clause_consts_diff st
  1.1804 +        else [])
  1.1805 +
  1.1806 +    val main_tac =
  1.1807 +      if can_feature (LoopOnce []) feats orelse can_feature (InnerLoopOnce []) feats then
  1.1808 +        extcnf_combined_main ctxt feats consts_diff
  1.1809 +      else if can_feature (Loop []) feats then
  1.1810 +        BEST_FIRST (TERMPRED (fn _ => true) conc_is_skolem_def NONE, size_of_thm)
  1.1811 +(*FIXME maybe need to weaken predicate to include "solved form"?*)
  1.1812 +         (extcnf_combined_main ctxt feats consts_diff)
  1.1813 +      else all_tac (*to allow us to use the cleaning features*)
  1.1814 +
  1.1815 +    (*Remove hypotheses from Skolem definitions,
  1.1816 +      then remove duplicate subgoals,
  1.1817 +      then we should be left with skolem definitions:
  1.1818 +        absorb them as axioms into the theory.*)
  1.1819 +    val cleanup =
  1.1820 +      cleanup_skolem_defs feats
  1.1821 +      THEN remove_duplicates_tac feats
  1.1822 +      THEN (if can_feature AbsorbSkolemDefs feats then
  1.1823 +              ALLGOALS (absorb_skolem_def ctxt prob_name_opt)
  1.1824 +            else all_tac)
  1.1825 +
  1.1826 +    val have_loop_feats =
  1.1827 +      (get_loop_feats feats; true)
  1.1828 +      handle NO_LOOP_FEATS => false
  1.1829 +
  1.1830 +    val tec =
  1.1831 +      (if can_feature StripQuantifiers feats then
  1.1832 +         (REPEAT (CHANGED (strip_qtfrs_tac ctxt)))
  1.1833 +       else all_tac)
  1.1834 +      THEN (if can_feature Flip_Conclusion feats then
  1.1835 +             HEADGOAL (flip_conclusion_tac ctxt)
  1.1836 +           else all_tac)
  1.1837 +
  1.1838 +      (*after stripping the quantifiers any remaining quantifiers
  1.1839 +        can be simply eliminated -- they're redundant*)
  1.1840 +      (*FIXME instead of just using allE, instantiate to a silly
  1.1841 +         term, to remove opportunities for unification.*)
  1.1842 +      THEN (REPEAT_DETERM (etac @{thm allE} 1))
  1.1843 +
  1.1844 +      THEN (REPEAT_DETERM (rtac @{thm allI} 1))
  1.1845 +
  1.1846 +      THEN (if have_loop_feats then
  1.1847 +              REPEAT (CHANGED
  1.1848 +              ((ALLGOALS (TRY o clause_breaker)) (*brush away literals which don't change*)
  1.1849 +               THEN
  1.1850 +                (*FIXME move this to a different level?*)
  1.1851 +                (if loop_can_feature [Polarity_switch] feats then
  1.1852 +                   all_tac
  1.1853 +                 else
  1.1854 +                   (TRY (IF_UNSOLVED (HEADGOAL (remove_redundant_quantification_ignore_skolems ctxt))))
  1.1855 +                   THEN (TRY (IF_UNSOLVED (HEADGOAL (remove_redundant_quantification_in_lit_ignore_skolems ctxt)))))
  1.1856 +               THEN (TRY main_tac)))
  1.1857 +            else
  1.1858 +              all_tac)
  1.1859 +      THEN IF_UNSOLVED cleanup
  1.1860 +
  1.1861 +  in
  1.1862 +    DEPTH_SOLVE (CHANGED tec) st
  1.1863 +  end
  1.1864 +*}
  1.1865 +
  1.1866 +
  1.1867 +subsubsection "unfold_def"
  1.1868 +
  1.1869 +(*this is used when handling unfold_tac, because the skeleton includes the definitions conjoined with the goal. it turns out that, for my tactic, the definitions are harmful. instead of modifying the skeleton (which may be nontrivial) i'm just dropping the information using this lemma. obviously, and from the name, order matters here.*)
  1.1870 +lemma drop_first_hypothesis [rule_format]: "\<lbrakk>A; B\<rbrakk> \<Longrightarrow> B" by auto
  1.1871 +
  1.1872 +(*Unfold_def works by reducing the goal to a meta equation,
  1.1873 +  then working on it until it can be discharged by atac,
  1.1874 +  or reflexive, or else turned back into an object equation
  1.1875 +  and broken down further.*)
  1.1876 +lemma un_meta_polarise: "(X \<equiv> True) \<Longrightarrow> X" by auto
  1.1877 +lemma meta_polarise: "X \<Longrightarrow> X \<equiv> True" by auto
  1.1878 +
  1.1879 +ML {*
  1.1880 +fun unfold_def_tac ctxt depends_on_defs = fn st =>
  1.1881 +  let
  1.1882 +    (*This is used when we end up with something like
  1.1883 +        (A & B) \<equiv> True \<Longrightarrow> (B & A) \<equiv> True.
  1.1884 +      It breaks down this subgoal until it can be trivially
  1.1885 +      discharged.
  1.1886 +     *)
  1.1887 +    val kill_meta_eqs_tac =
  1.1888 +      dtac @{thm un_meta_polarise}
  1.1889 +      THEN' rtac @{thm meta_polarise}
  1.1890 +      THEN' (REPEAT_DETERM o (etac @{thm conjE}))
  1.1891 +      THEN' (REPEAT_DETERM o (rtac @{thm conjI} ORELSE' atac))
  1.1892 +
  1.1893 +    val continue_reducing_tac =
  1.1894 +      rtac @{thm meta_eq_to_obj_eq} 1
  1.1895 +      THEN (REPEAT_DETERM (ex_expander_tac ctxt 1))
  1.1896 +      THEN TRY (polarise_subgoal_hyps 1) (*no need to REPEAT_DETERM here, since there should only be one hypothesis*)
  1.1897 +      THEN TRY (dtac @{thm eq_reflection} 1)
  1.1898 +      THEN (TRY ((CHANGED o rewrite_goal_tac ctxt
  1.1899 +              (@{thm expand_iff} :: @{thms simp_meta})) 1))
  1.1900 +      THEN HEADGOAL (rtac @{thm reflexive}
  1.1901 +                     ORELSE' atac
  1.1902 +                     ORELSE' kill_meta_eqs_tac)
  1.1903 +
  1.1904 +    val tectic =
  1.1905 +      (rtac @{thm polarise} 1 THEN atac 1)
  1.1906 +      ORELSE
  1.1907 +        (REPEAT_DETERM (etac @{thm conjE} 1 THEN etac @{thm drop_first_hypothesis} 1)
  1.1908 +         THEN PRIMITIVE (Conv.fconv_rule Drule.eta_long_conversion)
  1.1909 +         THEN (REPEAT_DETERM (ex_expander_tac ctxt 1))
  1.1910 +         THEN (TRY ((CHANGED o rewrite_goal_tac ctxt @{thms simp_meta}) 1))
  1.1911 +         THEN PRIMITIVE (Conv.fconv_rule Drule.eta_long_conversion)
  1.1912 +         THEN
  1.1913 +           (HEADGOAL atac
  1.1914 +           ORELSE
  1.1915 +            (unfold_tac ctxt depends_on_defs
  1.1916 +             THEN IF_UNSOLVED continue_reducing_tac)))
  1.1917 +  in
  1.1918 +    tectic st
  1.1919 +  end
  1.1920 +*}
  1.1921 +
  1.1922 +
  1.1923 +subsection "Handling split 'preprocessing'"
  1.1924 +
  1.1925 +lemma split_tranfs:
  1.1926 +  "! x. P x & Q x \<equiv> (! x. P x) & (! x. Q x)"
  1.1927 +  "~ (~ A) \<equiv> A"
  1.1928 +  "? x. A \<equiv> A"
  1.1929 +  "(A & B) & C \<equiv> A & B & C"
  1.1930 +  "A = B \<equiv> (A --> B) & (B --> A)"
  1.1931 +by (rule eq_reflection, auto)+
  1.1932 +
  1.1933 +(*Same idiom as ex_expander_tac*)
  1.1934 +ML {*
  1.1935 +fun split_simp_tac (ctxt : Proof.context) i =
  1.1936 +   let
  1.1937 +     val simpset =
  1.1938 +       fold Simplifier.add_simp @{thms split_tranfs} (empty_simpset ctxt)
  1.1939 +   in
  1.1940 +     CHANGED (asm_full_simp_tac simpset i)
  1.1941 +   end
  1.1942 +*}
  1.1943 +
  1.1944 +
  1.1945 +subsection "Alternative reconstruction tactics"
  1.1946 +ML {*
  1.1947 +(*An "auto"-based proof reconstruction, where we attempt to reconstruct each inference
  1.1948 +  using auto_tac. A realistic tactic would inspect the inference name and act
  1.1949 +  accordingly.*)
  1.1950 +fun auto_based_reconstruction_tac ctxt prob_name n =
  1.1951 +  let
  1.1952 +    val thy = Proof_Context.theory_of ctxt
  1.1953 +    val pannot = TPTP_Reconstruct.get_pannot_of_prob thy prob_name
  1.1954 +  in
  1.1955 +    TPTP_Reconstruct.inference_at_node
  1.1956 +     thy
  1.1957 +     prob_name (#meta pannot) n
  1.1958 +      |> the
  1.1959 +      |> (fn {inference_fmla, ...} =>
  1.1960 +          Goal.prove ctxt [] [] inference_fmla
  1.1961 +           (fn pdata => auto_tac (#context pdata)))
  1.1962 +  end
  1.1963 +*}
  1.1964 +
  1.1965 +(*An oracle-based reconstruction, which is only used to test the shunting part of the system*)
  1.1966 +oracle oracle_iinterp = "fn t => t"
  1.1967 +ML {*
  1.1968 +fun oracle_based_reconstruction_tac ctxt prob_name n =
  1.1969 +  let
  1.1970 +    val thy = Proof_Context.theory_of ctxt
  1.1971 +    val pannot = TPTP_Reconstruct.get_pannot_of_prob thy prob_name
  1.1972 +  in
  1.1973 +    TPTP_Reconstruct.inference_at_node
  1.1974 +     thy
  1.1975 +     prob_name (#meta pannot) n
  1.1976 +      |> the
  1.1977 +      |> (fn {inference_fmla, ...} => cterm_of thy inference_fmla)
  1.1978 +      |> oracle_iinterp
  1.1979 +  end
  1.1980 +*}
  1.1981 +
  1.1982 +
  1.1983 +subsection "Leo2 reconstruction tactic"
  1.1984 +
  1.1985 +ML {*
  1.1986 +exception UNSUPPORTED_ROLE
  1.1987 +exception INTERPRET_INFERENCE
  1.1988 +
  1.1989 +(*Failure reports can be adjusted to avoid interrupting
  1.1990 +  an overall reconstruction process*)
  1.1991 +fun fail ctxt x =
  1.1992 +  if unexceptional_reconstruction ctxt then
  1.1993 +    (warning x; raise INTERPRET_INFERENCE)
  1.1994 +  else error x
  1.1995 +
  1.1996 +fun interpret_leo2_inference_tac ctxt prob_name node =
  1.1997 +  let
  1.1998 +    val thy = Proof_Context.theory_of ctxt
  1.1999 +
  1.2000 +    val _ =
  1.2001 +      if Config.get ctxt tptp_trace_reconstruction then
  1.2002 +        tracing ("interpret_inference reconstructing node" ^ node ^ " of " ^ TPTP_Problem_Name.mangle_problem_name prob_name)
  1.2003 +      else ()
  1.2004 +
  1.2005 +    val pannot = TPTP_Reconstruct.get_pannot_of_prob thy prob_name
  1.2006 +
  1.2007 +    fun nonfull_extcnf_combined_tac feats =
  1.2008 +      extcnf_combined_tac ctxt (SOME prob_name)
  1.2009 +       [ConstsDiff,
  1.2010 +        StripQuantifiers,
  1.2011 +        InnerLoopOnce (Break_Hypotheses :: (*FIXME RemoveRedundantQuantifications :: *) feats),
  1.2012 +        AbsorbSkolemDefs]
  1.2013 +       []
  1.2014 +
  1.2015 +    val source_inf_opt =
  1.2016 +      AList.lookup (op =) (#meta pannot)
  1.2017 +      #> the
  1.2018 +      #> #source_inf_opt
  1.2019 +
  1.2020 +    (*FIXME integrate this with other lookup code, or in the early analysis*)
  1.2021 +    local
  1.2022 +      fun node_is_of_role role node =
  1.2023 +        AList.lookup (op =) (#meta pannot) node |> the
  1.2024 +        |> #role
  1.2025 +        |> (fn role' => role = role')
  1.2026 +
  1.2027 +      fun roled_dependencies_names role =
  1.2028 +        let
  1.2029 +          fun values () =
  1.2030 +            case role of
  1.2031 +                TPTP_Syntax.Role_Definition =>
  1.2032 +                  map (apsnd Binding.dest) (#defs pannot)
  1.2033 +              | TPTP_Syntax.Role_Axiom =>
  1.2034 +                  map (apsnd Binding.dest) (#axs pannot)
  1.2035 +              | _ => raise UNSUPPORTED_ROLE
  1.2036 +          in
  1.2037 +            if is_none (source_inf_opt node) then []
  1.2038 +            else
  1.2039 +              case the (source_inf_opt node) of
  1.2040 +                  TPTP_Proof.Inference (_, _, parent_inf) =>
  1.2041 +                    List.map TPTP_Proof.parent_name parent_inf
  1.2042 +                    |> List.filter (node_is_of_role role)
  1.2043 +                    |> (*FIXME currently definitions are not
  1.2044 +                         included in the proof annotations, so
  1.2045 +                         i'm using all the definitions available
  1.2046 +                         in the proof. ideally i should only
  1.2047 +                         use the ones in the proof annotation.*)
  1.2048 +                       (fn x =>
  1.2049 +                         if role = TPTP_Syntax.Role_Definition then
  1.2050 +                           let fun values () = map (apsnd Binding.dest) (#defs pannot)
  1.2051 +                           in
  1.2052 +                             map snd (values ())
  1.2053 +                           end
  1.2054 +                         else
  1.2055 +                         map (fn node => AList.lookup (op =) (values ()) node |> the) x)
  1.2056 +                | _ => []
  1.2057 +         end
  1.2058 +
  1.2059 +      val roled_dependencies =
  1.2060 +        roled_dependencies_names
  1.2061 +        #> map (#3 #> Global_Theory.get_thm thy)
  1.2062 +    in
  1.2063 +      val depends_on_defs = roled_dependencies TPTP_Syntax.Role_Definition
  1.2064 +      val depends_on_axs = roled_dependencies TPTP_Syntax.Role_Axiom
  1.2065 +      val depends_on_defs_names = roled_dependencies_names TPTP_Syntax.Role_Definition
  1.2066 +    end
  1.2067 +
  1.2068 +    fun get_binds source_inf_opt =
  1.2069 +      case the source_inf_opt of
  1.2070 +          TPTP_Proof.Inference (_, _, parent_inf) =>
  1.2071 +            List.map
  1.2072 +              (fn TPTP_Proof.Parent _ => []
  1.2073 +                | TPTP_Proof.ParentWithDetails (_, parent_details) => parent_details)
  1.2074 +              parent_inf
  1.2075 +            |> List.concat
  1.2076 +        | _ => []
  1.2077 +
  1.2078 +    val inference_name =
  1.2079 +      case TPTP_Reconstruct.inference_at_node thy prob_name (#meta pannot) node of
  1.2080 +          NONE => fail ctxt "Cannot reconstruct rule: no information"
  1.2081 +        | SOME {inference_name, ...} => inference_name
  1.2082 +    val default_tac = HEADGOAL (blast_tac ctxt)
  1.2083 +  in
  1.2084 +    case inference_name of
  1.2085 +      "fo_atp_e" =>
  1.2086 +        HEADGOAL (etac (oracle_based_reconstruction_tac ctxt prob_name node))
  1.2087 +    | "copy" =>
  1.2088 +         HEADGOAL
  1.2089 +          (atac
  1.2090 +           ORELSE'
  1.2091 +              (rtac @{thm polarise}
  1.2092 +               THEN' atac))
  1.2093 +    | "polarity_switch" => nonfull_extcnf_combined_tac [Polarity_switch]
  1.2094 +    | "solved_all_splits" => solved_all_splits_tac
  1.2095 +    | "extcnf_not_pos" => nonfull_extcnf_combined_tac [Not_pos]
  1.2096 +    | "extcnf_forall_pos" => nonfull_extcnf_combined_tac [Universal]
  1.2097 +    | "negate_conjecture" => fail ctxt "Should not handle negate_conjecture here"
  1.2098 +    | "unfold_def" => unfold_def_tac ctxt depends_on_defs
  1.2099 +    | "extcnf_not_neg" => nonfull_extcnf_combined_tac [Not_neg]
  1.2100 +    | "extcnf_or_neg" => nonfull_extcnf_combined_tac [Or_neg]
  1.2101 +    | "extcnf_equal_pos" => nonfull_extcnf_combined_tac [Equal_pos]
  1.2102 +    | "extcnf_equal_neg" => nonfull_extcnf_combined_tac [Equal_neg]
  1.2103 +    | "extcnf_forall_special_pos" =>
  1.2104 +         nonfull_extcnf_combined_tac [Forall_special_pos]
  1.2105 +         ORELSE HEADGOAL (blast_tac ctxt)
  1.2106 +    | "extcnf_or_pos" => nonfull_extcnf_combined_tac [Or_pos]
  1.2107 +    | "extuni_bool2" => nonfull_extcnf_combined_tac [Extuni_Bool2]
  1.2108 +    | "extuni_bool1" => nonfull_extcnf_combined_tac [Extuni_Bool1]
  1.2109 +    | "extuni_dec" =>
  1.2110 +        HEADGOAL atac
  1.2111 +        ORELSE nonfull_extcnf_combined_tac [Extuni_Dec]
  1.2112 +    | "extuni_bind" => nonfull_extcnf_combined_tac [Extuni_Bind]
  1.2113 +    | "extuni_triv" => nonfull_extcnf_combined_tac [Extuni_Triv]
  1.2114 +    | "extuni_flex_rigid" => nonfull_extcnf_combined_tac [Extuni_FlexRigid]
  1.2115 +    | "prim_subst" => nonfull_extcnf_combined_tac [Assumption]
  1.2116 +    | "bind" =>
  1.2117 +        let
  1.2118 +          val ordered_binds = get_binds (source_inf_opt node)
  1.2119 +        in
  1.2120 +          bind_tac ctxt prob_name ordered_binds
  1.2121 +        end
  1.2122 +    | "standard_cnf" => HEADGOAL (standard_cnf_tac ctxt)
  1.2123 +    | "extcnf_forall_neg" =>
  1.2124 +        nonfull_extcnf_combined_tac
  1.2125 +         [Existential_Var(* , RemoveRedundantQuantifications *)] (*FIXME RemoveRedundantQuantifications*)
  1.2126 +    | "extuni_func" =>
  1.2127 +        nonfull_extcnf_combined_tac [Extuni_Func, Existential_Var]
  1.2128 +    | "replace_leibnizEQ" => nonfull_extcnf_combined_tac [Assumption]
  1.2129 +    | "replace_andrewsEQ" => nonfull_extcnf_combined_tac [Assumption]
  1.2130 +    | "split_preprocessing" =>
  1.2131 +         (REPEAT (HEADGOAL (split_simp_tac ctxt)))
  1.2132 +         THEN TRY (PRIMITIVE (Conv.fconv_rule Drule.eta_long_conversion))
  1.2133 +         THEN HEADGOAL atac
  1.2134 +
  1.2135 +    (*FIXME some of these could eventually be handled specially*)
  1.2136 +    | "fac_restr" => default_tac
  1.2137 +    | "sim" => default_tac
  1.2138 +    | "res" => default_tac
  1.2139 +    | "rename" => default_tac
  1.2140 +    | "flexflex" => default_tac
  1.2141 +    | other => fail ctxt ("Unknown inference rule: " ^ other)
  1.2142 +  end
  1.2143 +*}
  1.2144 +
  1.2145 +ML {*
  1.2146 +fun interpret_leo2_inference ctxt prob_name node =
  1.2147 +  let
  1.2148 +    val thy = Proof_Context.theory_of ctxt
  1.2149 +    val pannot = TPTP_Reconstruct.get_pannot_of_prob thy prob_name
  1.2150 +
  1.2151 +    val (inference_name, inference_fmla) =
  1.2152 +      case TPTP_Reconstruct.inference_at_node thy prob_name (#meta pannot) node of
  1.2153 +          NONE => fail ctxt "Cannot reconstruct rule: no information"
  1.2154 +        | SOME {inference_name, inference_fmla, ...} =>
  1.2155 +            (inference_name, inference_fmla)
  1.2156 +
  1.2157 +    val proof_outcome =
  1.2158 +      let
  1.2159 +        fun prove () =
  1.2160 +          Goal.prove ctxt [] [] inference_fmla
  1.2161 +           (fn pdata => interpret_leo2_inference_tac
  1.2162 +            (#context pdata) prob_name node)
  1.2163 +      in
  1.2164 +        if informative_failure ctxt then SOME (prove ())
  1.2165 +        else try prove ()
  1.2166 +      end
  1.2167 +
  1.2168 +  in case proof_outcome of
  1.2169 +      NONE => fail ctxt (Pretty.string_of
  1.2170 +        (Pretty.block
  1.2171 +          [Pretty.str ("Failed inference reconstruction for '" ^
  1.2172 +            inference_name ^ "' at node " ^ node ^ ":\n"),
  1.2173 +           Syntax.pretty_term ctxt inference_fmla]))
  1.2174 +    | SOME thm => thm
  1.2175 +  end
  1.2176 +*}
  1.2177 +
  1.2178 +ML {*
  1.2179 +(*filter a set of nodes based on which inference rule was used to
  1.2180 +  derive a node*)
  1.2181 +fun nodes_by_inference (fms : TPTP_Reconstruct.formula_meaning list) inference_rule =
  1.2182 +  let
  1.2183 +    fun fold_fun n l =
  1.2184 +      case TPTP_Reconstruct.node_info fms #source_inf_opt n of
  1.2185 +          NONE => l
  1.2186 +        | SOME (TPTP_Proof.File _) => l
  1.2187 +        | SOME (TPTP_Proof.Inference (rule_name, _, _)) =>
  1.2188 +            if rule_name = inference_rule then n :: l
  1.2189 +            else l
  1.2190 +  in
  1.2191 +    fold fold_fun (map fst fms) []
  1.2192 +  end
  1.2193 +*}
  1.2194 +
  1.2195 +ML {*
  1.2196 +fun leo2_on_load (pannot : TPTP_Reconstruct.proof_annotation) thy =
  1.2197 +  let
  1.2198 +    val ctxt = Proof_Context.init_global thy
  1.2199 +    val dud = ("", Binding.empty, @{term False})
  1.2200 +    val pre_skolem_defs =
  1.2201 +      nodes_by_inference (#meta pannot) "extcnf_forall_neg" @
  1.2202 +       nodes_by_inference (#meta pannot) "extuni_func"
  1.2203 +      |> map (fn x =>
  1.2204 +              (interpret_leo2_inference ctxt (#problem_name pannot) x; dud)
  1.2205 +               handle NO_SKOLEM_DEF (s, bnd, t) => (s, bnd, t))
  1.2206 +      |> filter (fn (x, _, _) => x <> "") (*In case no skolem constants were introduced in that inference*)
  1.2207 +    val skolem_defs = map (fn (x, y, _) => (x, y)) pre_skolem_defs
  1.2208 +    val thy' =
  1.2209 +      fold (fn skolem_def => fn thy =>
  1.2210 +             let
  1.2211 +               val ((s, thm), thy') = Thm.add_axiom_global skolem_def thy
  1.2212 +               (* val _ = warning ("Added skolem definition " ^ s ^ ": " ^  @{make_string thm}) *) (*FIXME use of make_string*)
  1.2213 +             in thy' end)
  1.2214 +       (map (fn (_, y, z) => (y, z)) pre_skolem_defs)
  1.2215 +       thy
  1.2216 +  in
  1.2217 +    ({problem_name = #problem_name pannot,
  1.2218 +      skolem_defs = skolem_defs,
  1.2219 +      defs = #defs pannot,
  1.2220 +      axs = #axs pannot,
  1.2221 +      meta = #meta pannot},
  1.2222 +     thy')
  1.2223 +  end
  1.2224 +*}
  1.2225 +
  1.2226 +end
  1.2227 \ No newline at end of file