src/Tools/induct.ML
changeset 54742 7a86358a3c0b
parent 53168 d998de7f0efc
child 55951 c07d184aebe9
equal deleted inserted replaced
54741:010eefa0a4f3 54742:7a86358a3c0b
    58   (*proof methods*)
    58   (*proof methods*)
    59   val arbitrary_tac: Proof.context -> int -> (string * typ) list -> int -> tactic
    59   val arbitrary_tac: Proof.context -> int -> (string * typ) list -> int -> tactic
    60   val add_defs: (binding option * (term * bool)) option list -> Proof.context ->
    60   val add_defs: (binding option * (term * bool)) option list -> Proof.context ->
    61     (term option list * thm list) * Proof.context
    61     (term option list * thm list) * Proof.context
    62   val atomize_term: theory -> term -> term
    62   val atomize_term: theory -> term -> term
    63   val atomize_cterm: conv
    63   val atomize_cterm: Proof.context -> conv
    64   val atomize_tac: int -> tactic
    64   val atomize_tac: Proof.context -> int -> tactic
    65   val inner_atomize_tac: int -> tactic
    65   val inner_atomize_tac: Proof.context -> int -> tactic
    66   val rulified_term: thm -> theory * term
    66   val rulified_term: thm -> theory * term
    67   val rulify_tac: int -> tactic
    67   val rulify_tac: Proof.context -> int -> tactic
    68   val simplified_rule: Proof.context -> thm -> thm
    68   val simplified_rule: Proof.context -> thm -> thm
    69   val simplify_tac: Proof.context -> int -> tactic
    69   val simplify_tac: Proof.context -> int -> tactic
    70   val trivial_tac: int -> tactic
    70   val trivial_tac: int -> tactic
    71   val rotate_tac: int -> int -> int -> tactic
    71   val rotate_tac: int -> int -> int -> tactic
    72   val internalize: int -> thm -> thm
    72   val internalize: Proof.context -> int -> thm -> thm
    73   val guess_instance: Proof.context -> thm -> int -> thm -> thm Seq.seq
    73   val guess_instance: Proof.context -> thm -> int -> thm -> thm Seq.seq
    74   val cases_tac: Proof.context -> bool -> term option list list -> thm option ->
    74   val cases_tac: Proof.context -> bool -> term option list list -> thm option ->
    75     thm list -> int -> cases_tactic
    75     thm list -> int -> cases_tactic
    76   val get_inductT: Proof.context -> term option list list -> thm list list
    76   val get_inductT: Proof.context -> term option list list -> thm list list
    77   type case_data = (((string * string list) * string list) list * int) (* FIXME -> rule_cases.ML *)
    77   type case_data = (((string * string list) * string list) list * int) (* FIXME -> rule_cases.ML *)
   431 
   431 
   432 val equal_def' = Thm.symmetric Induct_Args.equal_def;
   432 val equal_def' = Thm.symmetric Induct_Args.equal_def;
   433 
   433 
   434 fun mark_constraints n ctxt = Conv.fconv_rule
   434 fun mark_constraints n ctxt = Conv.fconv_rule
   435   (Conv.prems_conv ~1 (Conv.params_conv ~1 (K (Conv.prems_conv n
   435   (Conv.prems_conv ~1 (Conv.params_conv ~1 (K (Conv.prems_conv n
   436      (Raw_Simplifier.rewrite false [equal_def']))) ctxt));
   436      (Raw_Simplifier.rewrite ctxt false [equal_def']))) ctxt));
   437 
   437 
   438 val unmark_constraints = Conv.fconv_rule
   438 fun unmark_constraints ctxt =
   439   (Raw_Simplifier.rewrite true [Induct_Args.equal_def]);
   439   Conv.fconv_rule (Raw_Simplifier.rewrite ctxt true [Induct_Args.equal_def]);
   440 
   440 
   441 
   441 
   442 (* simplify *)
   442 (* simplify *)
   443 
   443 
   444 fun simplify_conv' ctxt =
   444 fun simplify_conv' ctxt =
   502           |> tap (trace_rules ctxt casesN)
   502           |> tap (trace_rules ctxt casesN)
   503           |> Seq.of_list |> Seq.maps (Seq.try inst_rule));
   503           |> Seq.of_list |> Seq.maps (Seq.try inst_rule));
   504   in
   504   in
   505     fn i => fn st =>
   505     fn i => fn st =>
   506       ruleq
   506       ruleq
   507       |> Seq.maps (Rule_Cases.consume [] facts)
   507       |> Seq.maps (Rule_Cases.consume ctxt [] facts)
   508       |> Seq.maps (fn ((cases, (_, more_facts)), rule) =>
   508       |> Seq.maps (fn ((cases, (_, more_facts)), rule) =>
   509         let
   509         let
   510           val rule' = rule
   510           val rule' = rule
   511             |> simp ? (simplified_rule' ctxt #> unmark_constraints);
   511             |> simp ? (simplified_rule' ctxt #> unmark_constraints ctxt);
   512         in
   512         in
   513           CASES (Rule_Cases.make_common (thy,
   513           CASES (Rule_Cases.make_common (thy,
   514               Thm.prop_of (Rule_Cases.internalize_params rule')) cases)
   514               Thm.prop_of (Rule_Cases.internalize_params rule')) cases)
   515             ((Method.insert_tac more_facts THEN' rtac rule' THEN_ALL_NEW
   515             ((Method.insert_tac more_facts THEN' rtac rule' THEN_ALL_NEW
   516                 (if simp then TRY o trivial_tac else K all_tac)) i) st
   516                 (if simp then TRY o trivial_tac else K all_tac)) i) st
   530 
   530 
   531 fun atomize_term thy =
   531 fun atomize_term thy =
   532   Raw_Simplifier.rewrite_term thy Induct_Args.atomize []
   532   Raw_Simplifier.rewrite_term thy Induct_Args.atomize []
   533   #> Object_Logic.drop_judgment thy;
   533   #> Object_Logic.drop_judgment thy;
   534 
   534 
   535 val atomize_cterm = Raw_Simplifier.rewrite true Induct_Args.atomize;
   535 fun atomize_cterm ctxt = Raw_Simplifier.rewrite ctxt true Induct_Args.atomize;
   536 
   536 
   537 val atomize_tac = rewrite_goal_tac Induct_Args.atomize;
   537 fun atomize_tac ctxt = rewrite_goal_tac ctxt Induct_Args.atomize;
   538 
   538 
   539 val inner_atomize_tac =
   539 fun inner_atomize_tac ctxt =
   540   rewrite_goal_tac (map Thm.symmetric conjunction_congs) THEN' atomize_tac;
   540   rewrite_goal_tac ctxt (map Thm.symmetric conjunction_congs) THEN' atomize_tac ctxt;
   541 
   541 
   542 
   542 
   543 (* rulify *)
   543 (* rulify *)
   544 
   544 
   545 fun rulify_term thy =
   545 fun rulify_term thy =
   551     val thy = Thm.theory_of_thm thm;
   551     val thy = Thm.theory_of_thm thm;
   552     val rulify = rulify_term thy;
   552     val rulify = rulify_term thy;
   553     val (As, B) = Logic.strip_horn (Thm.prop_of thm);
   553     val (As, B) = Logic.strip_horn (Thm.prop_of thm);
   554   in (thy, Logic.list_implies (map rulify As, rulify B)) end;
   554   in (thy, Logic.list_implies (map rulify As, rulify B)) end;
   555 
   555 
   556 val rulify_tac =
   556 fun rulify_tac ctxt =
   557   rewrite_goal_tac (Induct_Args.rulify @ conjunction_congs) THEN'
   557   rewrite_goal_tac ctxt (Induct_Args.rulify @ conjunction_congs) THEN'
   558   rewrite_goal_tac Induct_Args.rulify_fallback THEN'
   558   rewrite_goal_tac ctxt Induct_Args.rulify_fallback THEN'
   559   Goal.conjunction_tac THEN_ALL_NEW
   559   Goal.conjunction_tac THEN_ALL_NEW
   560   (rewrite_goal_tac [@{thm Pure.conjunction_imp}] THEN' Goal.norm_hhf_tac);
   560   (rewrite_goal_tac ctxt [@{thm Pure.conjunction_imp}] THEN' Goal.norm_hhf_tac ctxt);
   561 
   561 
   562 
   562 
   563 (* prepare rule *)
   563 (* prepare rule *)
   564 
   564 
   565 fun rule_instance ctxt inst rule =
   565 fun rule_instance ctxt inst rule =
   566   Drule.cterm_instantiate (prep_inst ctxt align_left I (Thm.prop_of rule, inst)) rule;
   566   Drule.cterm_instantiate (prep_inst ctxt align_left I (Thm.prop_of rule, inst)) rule;
   567 
   567 
   568 fun internalize k th =
   568 fun internalize ctxt k th =
   569   th |> Thm.permute_prems 0 k
   569   th |> Thm.permute_prems 0 k
   570   |> Conv.fconv_rule (Conv.concl_conv (Thm.nprems_of th - k) atomize_cterm);
   570   |> Conv.fconv_rule (Conv.concl_conv (Thm.nprems_of th - k) (atomize_cterm ctxt));
   571 
   571 
   572 
   572 
   573 (* guess rule instantiation -- cannot handle pending goal parameters *)
   573 (* guess rule instantiation -- cannot handle pending goal parameters *)
   574 
   574 
   575 local
   575 local
   681       SOME concl =>
   681       SOME concl =>
   682         (compose_tac (false, spec_rule (goal_prefix n goal) concl, 1) THEN' rtac asm_rl) i
   682         (compose_tac (false, spec_rule (goal_prefix n goal) concl, 1) THEN' rtac asm_rl) i
   683     | NONE => all_tac)
   683     | NONE => all_tac)
   684   end);
   684   end);
   685 
   685 
   686 fun miniscope_tac p = CONVERSION o
   686 fun miniscope_tac p =
   687   Conv.params_conv p (K (Raw_Simplifier.rewrite true [Thm.symmetric Drule.norm_hhf_eq]));
   687   CONVERSION o
       
   688     Conv.params_conv p (fn ctxt =>
       
   689       Raw_Simplifier.rewrite ctxt true [Thm.symmetric Drule.norm_hhf_eq]);
   688 
   690 
   689 in
   691 in
   690 
   692 
   691 fun arbitrary_tac _ _ [] = K all_tac
   693 fun arbitrary_tac _ _ [] = K all_tac
   692   | arbitrary_tac ctxt n xs = SUBGOAL (fn (goal, i) =>
   694   | arbitrary_tac ctxt n xs = SUBGOAL (fn (goal, i) =>
   741 fun gen_induct_tac mod_cases ctxt simp def_insts arbitrary taking opt_rule facts =
   743 fun gen_induct_tac mod_cases ctxt simp def_insts arbitrary taking opt_rule facts =
   742   let
   744   let
   743     val thy = Proof_Context.theory_of ctxt;
   745     val thy = Proof_Context.theory_of ctxt;
   744 
   746 
   745     val ((insts, defs), defs_ctxt) = fold_map add_defs def_insts ctxt |>> split_list;
   747     val ((insts, defs), defs_ctxt) = fold_map add_defs def_insts ctxt |>> split_list;
   746     val atomized_defs = map (map (Conv.fconv_rule atomize_cterm)) defs;
   748     val atomized_defs = map (map (Conv.fconv_rule (atomize_cterm defs_ctxt))) defs;
   747 
   749 
   748     fun inst_rule (concls, r) =
   750     fun inst_rule (concls, r) =
   749       (if null insts then `Rule_Cases.get r
   751       (if null insts then `Rule_Cases.get r
   750        else (align_left "Rule has fewer conclusions than arguments given"
   752        else (align_left "Rule has fewer conclusions than arguments given"
   751           (map Logic.strip_imp_concl (Logic.dest_conjunctions (Thm.concl_of r))) insts
   753           (map Logic.strip_imp_concl (Logic.dest_conjunctions (Thm.concl_of r))) insts
   772         val cases' = if Thm.eq_thm_prop (rule', rule'') then cases else nonames cases;
   774         val cases' = if Thm.eq_thm_prop (rule', rule'') then cases else nonames cases;
   773       in Rule_Cases.make_nested (Thm.prop_of rule'') (rulified_term rule'') cases' end;
   775       in Rule_Cases.make_nested (Thm.prop_of rule'') (rulified_term rule'') cases' end;
   774   in
   776   in
   775     (fn i => fn st =>
   777     (fn i => fn st =>
   776       ruleq
   778       ruleq
   777       |> Seq.maps (Rule_Cases.consume (flat defs) facts)
   779       |> Seq.maps (Rule_Cases.consume defs_ctxt (flat defs) facts)
   778       |> Seq.maps (fn (((cases, concls), (more_consumes, more_facts)), rule) =>
   780       |> Seq.maps (fn (((cases, concls), (more_consumes, more_facts)), rule) =>
   779         (PRECISE_CONJUNCTS (length concls) (ALLGOALS (fn j =>
   781         (PRECISE_CONJUNCTS (length concls) (ALLGOALS (fn j =>
   780           (CONJUNCTS (ALLGOALS
   782           (CONJUNCTS (ALLGOALS
   781             let
   783             let
   782               val adefs = nth_list atomized_defs (j - 1);
   784               val adefs = nth_list atomized_defs (j - 1);
   789                    rotate_tac k (length adefs) THEN'
   791                    rotate_tac k (length adefs) THEN'
   790                    arbitrary_tac defs_ctxt k (List.partition (member op = frees) xs |> op @)
   792                    arbitrary_tac defs_ctxt k (List.partition (member op = frees) xs |> op @)
   791                  else
   793                  else
   792                    arbitrary_tac defs_ctxt k xs)
   794                    arbitrary_tac defs_ctxt k xs)
   793              end)
   795              end)
   794           THEN' inner_atomize_tac) j))
   796           THEN' inner_atomize_tac defs_ctxt) j))
   795         THEN' atomize_tac) i st |> Seq.maps (fn st' =>
   797         THEN' atomize_tac defs_ctxt) i st |> Seq.maps (fn st' =>
   796             guess_instance ctxt (internalize more_consumes rule) i st'
   798             guess_instance ctxt (internalize ctxt more_consumes rule) i st'
   797             |> Seq.map (rule_instance ctxt (burrow_options (Variable.polymorphic ctxt) taking))
   799             |> Seq.map (rule_instance ctxt (burrow_options (Variable.polymorphic ctxt) taking))
   798             |> Seq.maps (fn rule' =>
   800             |> Seq.maps (fn rule' =>
   799               CASES (rule_cases ctxt rule' cases)
   801               CASES (rule_cases ctxt rule' cases)
   800                 (rtac rule' i THEN
   802                 (rtac rule' i THEN
   801                   PRIMITIVE (singleton (Proof_Context.export defs_ctxt ctxt))) st'))))
   803                   PRIMITIVE (singleton (Proof_Context.export defs_ctxt ctxt))) st'))))
   802     THEN_ALL_NEW_CASES
   804     THEN_ALL_NEW_CASES
   803       ((if simp then simplify_tac ctxt THEN' (TRY o trivial_tac)
   805       ((if simp then simplify_tac ctxt THEN' (TRY o trivial_tac)
   804         else K all_tac)
   806         else K all_tac)
   805        THEN_ALL_NEW rulify_tac)
   807        THEN_ALL_NEW rulify_tac ctxt)
   806   end;
   808   end;
   807 
   809 
   808 val induct_tac = gen_induct_tac (K I);
   810 val induct_tac = gen_induct_tac (K I);
   809 
   811 
   810 
   812 
   847           |> tap (trace_rules ctxt coinductN)
   849           |> tap (trace_rules ctxt coinductN)
   848           |> Seq.of_list |> Seq.maps (Seq.try inst_rule));
   850           |> Seq.of_list |> Seq.maps (Seq.try inst_rule));
   849   in
   851   in
   850     SUBGOAL_CASES (fn (goal, i) => fn st =>
   852     SUBGOAL_CASES (fn (goal, i) => fn st =>
   851       ruleq goal
   853       ruleq goal
   852       |> Seq.maps (Rule_Cases.consume [] facts)
   854       |> Seq.maps (Rule_Cases.consume ctxt [] facts)
   853       |> Seq.maps (fn ((cases, (_, more_facts)), rule) =>
   855       |> Seq.maps (fn ((cases, (_, more_facts)), rule) =>
   854         guess_instance ctxt rule i st
   856         guess_instance ctxt rule i st
   855         |> Seq.map (rule_instance ctxt (burrow_options (Variable.polymorphic ctxt) taking))
   857         |> Seq.map (rule_instance ctxt (burrow_options (Variable.polymorphic ctxt) taking))
   856         |> Seq.maps (fn rule' =>
   858         |> Seq.maps (fn rule' =>
   857           CASES (Rule_Cases.make_common (thy,
   859           CASES (Rule_Cases.make_common (thy,