src/Pure/goal.ML
author wenzelm
Fri Oct 23 17:17:11 2015 +0200 (2015-10-23)
changeset 61508 2c7e2ae6173d
parent 60948 b710a5087116
child 61527 d05f3d86a758
permissions -rw-r--r--
clarified modules;
tuned signature;
     1 (*  Title:      Pure/goal.ML
     2     Author:     Makarius
     3 
     4 Goals in tactical theorem proving, with support for forked proofs.
     5 *)
     6 
     7 signature BASIC_GOAL =
     8 sig
     9   val parallel_proofs: int Unsynchronized.ref
    10   val SELECT_GOAL: tactic -> int -> tactic
    11   val PREFER_GOAL: tactic -> int -> tactic
    12   val CONJUNCTS: tactic -> int -> tactic
    13   val PRECISE_CONJUNCTS: int -> tactic -> int -> tactic
    14 end;
    15 
    16 signature GOAL =
    17 sig
    18   include BASIC_GOAL
    19   val init: cterm -> thm
    20   val protect: int -> thm -> thm
    21   val conclude: thm -> thm
    22   val check_finished: Proof.context -> thm -> thm
    23   val finish: Proof.context -> thm -> thm
    24   val norm_result: Proof.context -> thm -> thm
    25   val skip_proofs_enabled: unit -> bool
    26   val future_enabled: int -> bool
    27   val future_enabled_timing: Time.time -> bool
    28   val future_result: Proof.context -> thm future -> term -> thm
    29   val prove_internal: Proof.context -> cterm list -> cterm -> (thm list -> tactic) -> thm
    30   val is_schematic: term -> bool
    31   val prove_common: Proof.context -> int option -> string list -> term list -> term list ->
    32     ({prems: thm list, context: Proof.context} -> tactic) -> thm list
    33   val prove_future: Proof.context -> string list -> term list -> term ->
    34     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    35   val prove: Proof.context -> string list -> term list -> term ->
    36     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    37   val prove_global_future: theory -> string list -> term list -> term ->
    38     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    39   val prove_global: theory -> string list -> term list -> term ->
    40     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    41   val prove_sorry: Proof.context -> string list -> term list -> term ->
    42     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    43   val prove_sorry_global: theory -> string list -> term list -> term ->
    44     ({prems: thm list, context: Proof.context} -> tactic) -> thm
    45   val restrict: int -> int -> thm -> thm
    46   val unrestrict: int -> thm -> thm
    47   val conjunction_tac: int -> tactic
    48   val precise_conjunction_tac: int -> int -> tactic
    49   val recover_conjunction_tac: tactic
    50   val norm_hhf_tac: Proof.context -> int -> tactic
    51   val assume_rule_tac: Proof.context -> int -> tactic
    52 end;
    53 
    54 structure Goal: GOAL =
    55 struct
    56 
    57 (** goals **)
    58 
    59 (*
    60   -------- (init)
    61   C ==> #C
    62 *)
    63 fun init C = Thm.instantiate ([], [((("A", 0), propT), C)]) Drule.protectI;
    64 
    65 (*
    66   A1 ==> ... ==> An ==> C
    67   ------------------------ (protect n)
    68   A1 ==> ... ==> An ==> #C
    69 *)
    70 fun protect n th = Drule.comp_no_flatten (th, n) 1 Drule.protectI;
    71 
    72 (*
    73   A ==> ... ==> #C
    74   ---------------- (conclude)
    75   A ==> ... ==> C
    76 *)
    77 fun conclude th = Drule.comp_no_flatten (th, Thm.nprems_of th) 1 Drule.protectD;
    78 
    79 (*
    80   #C
    81   --- (finish)
    82    C
    83 *)
    84 fun check_finished ctxt th =
    85   if Thm.no_prems th then th
    86   else
    87     raise THM ("Proof failed.\n" ^ Pretty.string_of (Goal_Display.pretty_goal ctxt th), 0, [th]);
    88 
    89 fun finish ctxt = check_finished ctxt #> conclude;
    90 
    91 
    92 
    93 (** results **)
    94 
    95 (* normal form *)
    96 
    97 fun norm_result ctxt =
    98   Drule.flexflex_unique (SOME ctxt)
    99   #> Raw_Simplifier.norm_hhf_protect ctxt
   100   #> Thm.strip_shyps
   101   #> Drule.zero_var_indexes;
   102 
   103 
   104 (* scheduling parameters *)
   105 
   106 fun skip_proofs_enabled () =
   107   let val skip = Options.default_bool "skip_proofs" in
   108     if Proofterm.proofs_enabled () andalso skip then
   109       (warning "Proof terms enabled -- cannot skip proofs"; false)
   110     else skip
   111   end;
   112 
   113 val parallel_proofs = Unsynchronized.ref 1;
   114 
   115 fun future_enabled n =
   116   Multithreading.enabled () andalso ! parallel_proofs >= n andalso
   117   is_some (Future.worker_task ());
   118 
   119 fun future_enabled_timing t =
   120   future_enabled 1 andalso
   121     Time.toReal t >= Options.default_real "parallel_subproofs_threshold";
   122 
   123 
   124 (* future_result *)
   125 
   126 fun future_result ctxt result prop =
   127   let
   128     val assms = Assumption.all_assms_of ctxt;
   129     val As = map Thm.term_of assms;
   130 
   131     val xs = map Free (fold Term.add_frees (prop :: As) []);
   132     val fixes = map (Thm.cterm_of ctxt) xs;
   133 
   134     val tfrees = fold Term.add_tfrees (prop :: As) [];
   135     val instT = map (fn (a, S) => (((a, 0), S), Thm.ctyp_of ctxt (TFree (a, S)))) tfrees;
   136 
   137     val global_prop =
   138       Logic.varify_types_global (fold_rev Logic.all xs (Logic.list_implies (As, prop)))
   139       |> Thm.cterm_of ctxt
   140       |> Thm.weaken_sorts' ctxt;
   141     val global_result = result |> Future.map
   142       (Drule.flexflex_unique (SOME ctxt) #>
   143         Thm.adjust_maxidx_thm ~1 #>
   144         Drule.implies_intr_list assms #>
   145         Drule.forall_intr_list fixes #>
   146         Thm.generalize (map #1 tfrees, []) 0 #>
   147         Thm.strip_shyps);
   148     val local_result =
   149       Thm.future global_result global_prop
   150       |> Thm.close_derivation
   151       |> Thm.instantiate (instT, [])
   152       |> Drule.forall_elim_list fixes
   153       |> fold (Thm.elim_implies o Thm.assume) assms;
   154   in local_result end;
   155 
   156 
   157 
   158 (** tactical theorem proving **)
   159 
   160 (* prove_internal -- minimal checks, no normalization of result! *)
   161 
   162 fun prove_internal ctxt casms cprop tac =
   163   (case SINGLE (tac (map (Assumption.assume ctxt) casms)) (init cprop) of
   164     SOME th => Drule.implies_intr_list casms (finish ctxt th)
   165   | NONE => error "Tactic failed");
   166 
   167 
   168 (* prove variations *)
   169 
   170 fun is_schematic t =
   171   Term.exists_subterm Term.is_Var t orelse
   172   Term.exists_type (Term.exists_subtype Term.is_TVar) t;
   173 
   174 fun prove_common ctxt fork_pri xs asms props tac =
   175   let
   176     val thy = Proof_Context.theory_of ctxt;
   177 
   178     val schematic = exists is_schematic props;
   179     val immediate = is_none fork_pri;
   180     val future = future_enabled 1;
   181     val skip = not immediate andalso not schematic andalso future andalso skip_proofs_enabled ();
   182 
   183     val pos = Position.thread_data ();
   184     fun err msg =
   185       cat_error msg
   186         ("The error(s) above occurred for the goal statement" ^ Position.here pos ^ ":\n" ^
   187           Syntax.string_of_term ctxt (Logic.list_implies (asms, Logic.mk_conjunction_list props)));
   188 
   189     fun cert_safe t = Thm.cterm_of ctxt (Envir.beta_norm (Term.no_dummy_patterns t))
   190       handle TERM (msg, _) => err msg | TYPE (msg, _, _) => err msg;
   191     val casms = map cert_safe asms;
   192     val cprops = map cert_safe props;
   193 
   194     val (prems, ctxt') = ctxt
   195       |> Variable.add_fixes_direct xs
   196       |> fold Variable.declare_term (asms @ props)
   197       |> Assumption.add_assumes casms
   198       ||> Variable.set_body true;
   199 
   200     val stmt = Thm.weaken_sorts' ctxt' (Conjunction.mk_conjunction_balanced cprops);
   201 
   202     fun tac' args st =
   203       if skip then ALLGOALS (Skip_Proof.cheat_tac ctxt) st before Skip_Proof.report ctxt
   204       else tac args st;
   205     fun result () =
   206       (case SINGLE (tac' {prems = prems, context = ctxt'}) (init stmt) of
   207         NONE => err "Tactic failed"
   208       | SOME st =>
   209           let
   210             val _ =
   211               Context.subthy_id (Thm.theory_id_of_thm st, Context.theory_id thy) orelse
   212                 err "Bad background theory of goal state";
   213             val res =
   214               (finish ctxt' st
   215                 |> Drule.flexflex_unique (SOME ctxt')
   216                 |> Thm.check_shyps ctxt'
   217                 |> Thm.check_hyps (Context.Proof ctxt'))
   218               handle THM (msg, _, _) => err msg | ERROR msg => err msg;
   219           in
   220             if Unify.matches_list (Context.Proof ctxt') [Thm.term_of stmt] [Thm.prop_of res]
   221             then res
   222             else err ("Proved a different theorem: " ^ Syntax.string_of_term ctxt' (Thm.prop_of res))
   223           end);
   224     val res =
   225       if immediate orelse schematic orelse not future orelse skip then result ()
   226       else
   227         future_result ctxt'
   228           (Execution.fork {name = "Goal.prove", pos = Position.thread_data (), pri = the fork_pri}
   229             result)
   230           (Thm.term_of stmt);
   231   in
   232     res
   233     |> length props > 1 ? Thm.close_derivation
   234     |> Conjunction.elim_balanced (length props)
   235     |> map (Assumption.export false ctxt' ctxt)
   236     |> Variable.export ctxt' ctxt
   237     |> map Drule.zero_var_indexes
   238   end;
   239 
   240 fun prove_future_pri ctxt pri xs asms prop tac =
   241   hd (prove_common ctxt (SOME pri) xs asms [prop] tac);
   242 
   243 fun prove_future ctxt = prove_future_pri ctxt ~1;
   244 
   245 fun prove ctxt xs asms prop tac = hd (prove_common ctxt NONE xs asms [prop] tac);
   246 
   247 fun prove_global_future thy xs asms prop tac =
   248   Drule.export_without_context (prove_future (Proof_Context.init_global thy) xs asms prop tac);
   249 
   250 fun prove_global thy xs asms prop tac =
   251   Drule.export_without_context (prove (Proof_Context.init_global thy) xs asms prop tac);
   252 
   253 fun prove_sorry ctxt xs asms prop tac =
   254   if Config.get ctxt quick_and_dirty then
   255     prove ctxt xs asms prop (fn _ => ALLGOALS (Skip_Proof.cheat_tac ctxt))
   256   else (if future_enabled 1 then prove_future_pri ctxt ~2 else prove ctxt) xs asms prop tac;
   257 
   258 fun prove_sorry_global thy xs asms prop tac =
   259   Drule.export_without_context
   260     (prove_sorry (Proof_Context.init_global thy) xs asms prop tac);
   261 
   262 
   263 
   264 (** goal structure **)
   265 
   266 (* rearrange subgoals *)
   267 
   268 fun restrict i n st =
   269   if i < 1 orelse n < 1 orelse i + n - 1 > Thm.nprems_of st
   270   then raise THM ("Goal.restrict", i, [st])
   271   else rotate_prems (i - 1) st |> protect n;
   272 
   273 fun unrestrict i = conclude #> rotate_prems (1 - i);
   274 
   275 (*with structural marker*)
   276 fun SELECT_GOAL tac i st =
   277   if Thm.nprems_of st = 1 andalso i = 1 then tac st
   278   else (PRIMITIVE (restrict i 1) THEN tac THEN PRIMITIVE (unrestrict i)) st;
   279 
   280 (*without structural marker*)
   281 fun PREFER_GOAL tac i st =
   282   if i < 1 orelse i > Thm.nprems_of st then Seq.empty
   283   else (PRIMITIVE (rotate_prems (i - 1)) THEN tac THEN PRIMITIVE (rotate_prems (1 - i))) st;
   284 
   285 
   286 (* multiple goals *)
   287 
   288 fun precise_conjunction_tac 0 i = eq_assume_tac i
   289   | precise_conjunction_tac 1 i = SUBGOAL (K all_tac) i
   290   | precise_conjunction_tac n i = PRIMITIVE (Drule.with_subgoal i (Conjunction.curry_balanced n));
   291 
   292 val adhoc_conjunction_tac = REPEAT_ALL_NEW
   293   (SUBGOAL (fn (goal, i) =>
   294     if can Logic.dest_conjunction goal then resolve0_tac [Conjunction.conjunctionI] i
   295     else no_tac));
   296 
   297 val conjunction_tac = SUBGOAL (fn (goal, i) =>
   298   precise_conjunction_tac (length (Logic.dest_conjunctions goal)) i ORELSE
   299   TRY (adhoc_conjunction_tac i));
   300 
   301 val recover_conjunction_tac = PRIMITIVE (fn th =>
   302   Conjunction.uncurry_balanced (Thm.nprems_of th) th);
   303 
   304 fun PRECISE_CONJUNCTS n tac =
   305   SELECT_GOAL (precise_conjunction_tac n 1
   306     THEN tac
   307     THEN recover_conjunction_tac);
   308 
   309 fun CONJUNCTS tac =
   310   SELECT_GOAL (conjunction_tac 1
   311     THEN tac
   312     THEN recover_conjunction_tac);
   313 
   314 
   315 (* hhf normal form *)
   316 
   317 fun norm_hhf_tac ctxt =
   318   resolve_tac ctxt [Drule.asm_rl]  (*cheap approximation -- thanks to builtin Logic.flatten_params*)
   319   THEN' SUBGOAL (fn (t, i) =>
   320     if Drule.is_norm_hhf t then all_tac
   321     else rewrite_goal_tac ctxt Drule.norm_hhf_eqs i);
   322 
   323 
   324 (* non-atomic goal assumptions *)
   325 
   326 fun non_atomic (Const ("Pure.imp", _) $ _ $ _) = true
   327   | non_atomic (Const ("Pure.all", _) $ _) = true
   328   | non_atomic _ = false;
   329 
   330 fun assume_rule_tac ctxt = norm_hhf_tac ctxt THEN' CSUBGOAL (fn (goal, i) =>
   331   let
   332     val ((_, goal'), ctxt') = Variable.focus_cterm NONE goal ctxt;
   333     val goal'' = Drule.cterm_rule (singleton (Variable.export ctxt' ctxt)) goal';
   334     val Rs = filter (non_atomic o Thm.term_of) (Drule.strip_imp_prems goal'');
   335     val tacs = Rs |> map (fn R =>
   336       eresolve_tac ctxt [Raw_Simplifier.norm_hhf ctxt (Thm.trivial R)] THEN_ALL_NEW assume_tac ctxt);
   337   in fold_rev (curry op APPEND') tacs (K no_tac) i end);
   338 
   339 end;
   340 
   341 structure Basic_Goal: BASIC_GOAL = Goal;
   342 open Basic_Goal;