src/HOL/Tools/Function/induction_schema.ML
changeset 54742 7a86358a3c0b
parent 52467 24c6ddb48cb8
child 55642 63beb38e9258
equal deleted inserted replaced
54741:010eefa0a4f3 54742:7a86358a3c0b
    36 datatype ind_scheme = IndScheme of
    36 datatype ind_scheme = IndScheme of
    37  {T: typ, (* sum of products *)
    37  {T: typ, (* sum of products *)
    38   branches: scheme_branch list,
    38   branches: scheme_branch list,
    39   cases: scheme_case list}
    39   cases: scheme_case list}
    40 
    40 
    41 val ind_atomize = Raw_Simplifier.rewrite true @{thms induct_atomize}
    41 fun ind_atomize ctxt = Raw_Simplifier.rewrite ctxt true @{thms induct_atomize}
    42 val ind_rulify = Raw_Simplifier.rewrite true @{thms induct_rulify}
    42 fun ind_rulify ctxt = Raw_Simplifier.rewrite ctxt true @{thms induct_rulify}
    43 
    43 
    44 fun meta thm = thm RS eq_reflection
    44 fun meta thm = thm RS eq_reflection
    45 
    45 
    46 val sum_prod_conv = Raw_Simplifier.rewrite true
    46 fun sum_prod_conv ctxt = Raw_Simplifier.rewrite ctxt true
    47   (map meta (@{thm split_conv} :: @{thms sum.cases}))
    47   (map meta (@{thm split_conv} :: @{thms sum.cases}))
    48 
    48 
    49 fun term_conv thy cv t =
    49 fun term_conv thy cv t =
    50   cv (cterm_of thy t)
    50   cv (cterm_of thy t)
    51   |> prop_of |> Logic.dest_equals |> snd
    51   |> prop_of |> Logic.dest_equals |> snd
   185   in
   185   in
   186     map f cases
   186     map f cases
   187   end
   187   end
   188 
   188 
   189 
   189 
   190 fun mk_ind_goal thy branches =
   190 fun mk_ind_goal ctxt branches =
   191   let
   191   let
       
   192     val thy = Proof_Context.theory_of ctxt
       
   193 
   192     fun brnch (SchemeBranch { P, xs, ws, Cs, ... }) =
   194     fun brnch (SchemeBranch { P, xs, ws, Cs, ... }) =
   193       HOLogic.mk_Trueprop (list_comb (P, map Free xs))
   195       HOLogic.mk_Trueprop (list_comb (P, map Free xs))
   194       |> fold_rev (curry Logic.mk_implies) Cs
   196       |> fold_rev (curry Logic.mk_implies) Cs
   195       |> fold_rev (Logic.all o Free) ws
   197       |> fold_rev (Logic.all o Free) ws
   196       |> term_conv thy ind_atomize
   198       |> term_conv thy (ind_atomize ctxt)
   197       |> Object_Logic.drop_judgment thy
   199       |> Object_Logic.drop_judgment thy
   198       |> HOLogic.tupled_lambda (foldr1 HOLogic.mk_prod (map Free xs))
   200       |> HOLogic.tupled_lambda (foldr1 HOLogic.mk_prod (map Free xs))
   199   in
   201   in
   200     SumTree.mk_sumcases HOLogic.boolT (map brnch branches)
   202     SumTree.mk_sumcases HOLogic.boolT (map brnch branches)
   201   end
   203   end
   202 
   204 
   203 fun mk_induct_rule ctxt R x complete_thms wf_thm ineqss
   205 fun mk_induct_rule ctxt R x complete_thms wf_thm ineqss
   204   (IndScheme {T, cases=scases, branches}) =
   206   (IndScheme {T, cases=scases, branches}) =
   205   let
   207   let
       
   208     val thy = Proof_Context.theory_of ctxt
       
   209     val cert = cterm_of thy
       
   210 
   206     val n = length branches
   211     val n = length branches
   207     val scases_idx = map_index I scases
   212     val scases_idx = map_index I scases
   208 
   213 
   209     fun inject i ts =
   214     fun inject i ts =
   210       SumTree.mk_inj T n (i + 1) (foldr1 HOLogic.mk_prod ts)
   215       SumTree.mk_inj T n (i + 1) (foldr1 HOLogic.mk_prod ts)
   211     val P_of = nth (map (fn (SchemeBranch { P, ... }) => P) branches)
   216     val P_of = nth (map (fn (SchemeBranch { P, ... }) => P) branches)
   212 
   217 
   213     val thy = Proof_Context.theory_of ctxt
   218     val P_comp = mk_ind_goal ctxt branches
   214     val cert = cterm_of thy
       
   215 
       
   216     val P_comp = mk_ind_goal thy branches
       
   217 
   219 
   218     (* Inductive Hypothesis: !!z. (z,x):R ==> P z *)
   220     (* Inductive Hypothesis: !!z. (z,x):R ==> P z *)
   219     val ihyp = Logic.all_const T $ Abs ("z", T,
   221     val ihyp = Logic.all_const T $ Abs ("z", T,
   220       Logic.mk_implies
   222       Logic.mk_implies
   221         (HOLogic.mk_Trueprop (
   223         (HOLogic.mk_Trueprop (
   268                   |> import
   270                   |> import
   269               in
   271               in
   270                 sih
   272                 sih
   271                 |> Thm.forall_elim (cert (inject idx rcargs))
   273                 |> Thm.forall_elim (cert (inject idx rcargs))
   272                 |> Thm.elim_implies (import ineq) (* Psum rcargs *)
   274                 |> Thm.elim_implies (import ineq) (* Psum rcargs *)
   273                 |> Conv.fconv_rule sum_prod_conv
   275                 |> Conv.fconv_rule (sum_prod_conv ctxt)
   274                 |> Conv.fconv_rule ind_rulify
   276                 |> Conv.fconv_rule (ind_rulify ctxt)
   275                 |> (fn th => th COMP ipres) (* P rs *)
   277                 |> (fn th => th COMP ipres) (* P rs *)
   276                 |> fold_rev (Thm.implies_intr o cprop_of) cGas
   278                 |> fold_rev (Thm.implies_intr o cprop_of) cGas
   277                 |> fold_rev Thm.forall_intr cGvs
   279                 |> fold_rev Thm.forall_intr cGvs
   278               end
   280               end
   279 
   281 
   310           |> fold_rev (Thm.implies_intr o cprop_of) C_hyps
   312           |> fold_rev (Thm.implies_intr o cprop_of) C_hyps
   311           |> fold_rev (Thm.forall_intr o cert o Free) ws
   313           |> fold_rev (Thm.forall_intr o cert o Free) ws
   312 
   314 
   313         val Pxs = cert (HOLogic.mk_Trueprop (P_comp $ x))
   315         val Pxs = cert (HOLogic.mk_Trueprop (P_comp $ x))
   314           |> Goal.init
   316           |> Goal.init
   315           |> (Simplifier.rewrite_goals_tac (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.cases}))
   317           |> (Simplifier.rewrite_goals_tac ctxt
   316               THEN CONVERSION ind_rulify 1)
   318                 (map meta (branch_hyp :: @{thm split_conv} :: @{thms sum.cases}))
       
   319               THEN CONVERSION (ind_rulify ctxt) 1)
   317           |> Seq.hd
   320           |> Seq.hd
   318           |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep)
   321           |> Thm.elim_implies (Conv.fconv_rule Drule.beta_eta_conversion bstep)
   319           |> Goal.finish ctxt
   322           |> Goal.finish ctxt
   320           |> Thm.implies_intr (cprop_of branch_hyp)
   323           |> Thm.implies_intr (cprop_of branch_hyp)
   321           |> fold_rev (Thm.forall_intr o cert) fxs
   324           |> fold_rev (Thm.forall_intr o cert) fxs
   373           |> cert
   376           |> cert
   374       in
   377       in
   375         indthm
   378         indthm
   376         |> Drule.instantiate' [] [SOME inst]
   379         |> Drule.instantiate' [] [SOME inst]
   377         |> simplify (put_simpset SumTree.sumcase_split_ss ctxt'')
   380         |> simplify (put_simpset SumTree.sumcase_split_ss ctxt'')
   378         |> Conv.fconv_rule ind_rulify
   381         |> Conv.fconv_rule (ind_rulify ctxt'')
   379       end
   382       end
   380 
   383 
   381     val res = Conjunction.intr_balanced (map_index project branches)
   384     val res = Conjunction.intr_balanced (map_index project branches)
   382       |> fold_rev Thm.implies_intr (map cprop_of newgoals @ steps)
   385       |> fold_rev Thm.implies_intr (map cprop_of newgoals @ steps)
   383       |> Drule.generalize ([], [Rn])
   386       |> Drule.generalize ([], [Rn])