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