src/HOL/Tools/Function/function_core.ML
changeset 36945 9bec62c10714
parent 36936 c52d1c130898
child 37145 01aa36932739
equal deleted inserted replaced
36944:dbf831a50e4a 36945:9bec62c10714
   152     val gs = map inst pre_gs
   152     val gs = map inst pre_gs
   153     val lhs = inst pre_lhs
   153     val lhs = inst pre_lhs
   154     val rhs = inst pre_rhs
   154     val rhs = inst pre_rhs
   155 
   155 
   156     val cqs = map (cterm_of thy) qs
   156     val cqs = map (cterm_of thy) qs
   157     val ags = map (assume o cterm_of thy) gs
   157     val ags = map (Thm.assume o cterm_of thy) gs
   158 
   158 
   159     val case_hyp = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (x, lhs))))
   159     val case_hyp = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (x, lhs))))
   160   in
   160   in
   161     ClauseContext { ctxt = ctxt', qs = qs, gs = gs, lhs = lhs, rhs = rhs,
   161     ClauseContext { ctxt = ctxt', qs = qs, gs = gs, lhs = lhs, rhs = rhs,
   162       cqs = cqs, ags = ags, case_hyp = case_hyp }
   162       cqs = cqs, ags = ags, case_hyp = case_hyp }
   163   end
   163   end
   164 
   164 
   186     val ClauseContext { ctxt, qs, cqs, ags, ... } = cdata
   186     val ClauseContext { ctxt, qs, cqs, ags, ... } = cdata
   187     val cert = Thm.cterm_of (ProofContext.theory_of ctxt)
   187     val cert = Thm.cterm_of (ProofContext.theory_of ctxt)
   188 
   188 
   189     (* Instantiate the GIntro thm with "f" and import into the clause context. *)
   189     (* Instantiate the GIntro thm with "f" and import into the clause context. *)
   190     val lGI = GIntro_thm
   190     val lGI = GIntro_thm
   191       |> forall_elim (cert f)
   191       |> Thm.forall_elim (cert f)
   192       |> fold forall_elim cqs
   192       |> fold Thm.forall_elim cqs
   193       |> fold Thm.elim_implies ags
   193       |> fold Thm.elim_implies ags
   194 
   194 
   195     fun mk_call_info (rcfix, rcassm, rcarg) RI =
   195     fun mk_call_info (rcfix, rcassm, rcarg) RI =
   196       let
   196       let
   197         val llRI = RI
   197         val llRI = RI
   198           |> fold forall_elim cqs
   198           |> fold Thm.forall_elim cqs
   199           |> fold (forall_elim o cert o Free) rcfix
   199           |> fold (Thm.forall_elim o cert o Free) rcfix
   200           |> fold Thm.elim_implies ags
   200           |> fold Thm.elim_implies ags
   201           |> fold Thm.elim_implies rcassm
   201           |> fold Thm.elim_implies rcassm
   202 
   202 
   203         val h_assum =
   203         val h_assum =
   204           HOLogic.mk_Trueprop (G $ rcarg $ (h $ rcarg))
   204           HOLogic.mk_Trueprop (G $ rcarg $ (h $ rcarg))
   240   in if j < i then
   240   in if j < i then
   241     let
   241     let
   242       val compat = lookup_compat_thm j i cts
   242       val compat = lookup_compat_thm j i cts
   243     in
   243     in
   244       compat         (* "!!qj qi. Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *)
   244       compat         (* "!!qj qi. Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *)
   245       |> fold forall_elim (cqsj @ cqsi) (* "Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *)
   245       |> fold Thm.forall_elim (cqsj @ cqsi) (* "Gsj => Gsi => lhsj = lhsi ==> rhsj = rhsi" *)
   246       |> fold Thm.elim_implies agsj
   246       |> fold Thm.elim_implies agsj
   247       |> fold Thm.elim_implies agsi
   247       |> fold Thm.elim_implies agsi
   248       |> Thm.elim_implies ((assume lhsi_eq_lhsj) RS sym) (* "Gsj, Gsi, lhsi = lhsj |-- rhsj = rhsi" *)
   248       |> Thm.elim_implies ((Thm.assume lhsi_eq_lhsj) RS sym) (* "Gsj, Gsi, lhsi = lhsj |-- rhsj = rhsi" *)
   249     end
   249     end
   250     else
   250     else
   251     let
   251     let
   252       val compat = lookup_compat_thm i j cts
   252       val compat = lookup_compat_thm i j cts
   253     in
   253     in
   254       compat        (* "!!qi qj. Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *)
   254       compat        (* "!!qi qj. Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *)
   255       |> fold forall_elim (cqsi @ cqsj) (* "Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *)
   255       |> fold Thm.forall_elim (cqsi @ cqsj) (* "Gsi => Gsj => lhsi = lhsj ==> rhsi = rhsj" *)
   256       |> fold Thm.elim_implies agsi
   256       |> fold Thm.elim_implies agsi
   257       |> fold Thm.elim_implies agsj
   257       |> fold Thm.elim_implies agsj
   258       |> Thm.elim_implies (assume lhsi_eq_lhsj)
   258       |> Thm.elim_implies (Thm.assume lhsi_eq_lhsj)
   259       |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *)
   259       |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *)
   260     end
   260     end
   261   end
   261   end
   262 
   262 
   263 (* Generates the replacement lemma in fully quantified form. *)
   263 (* Generates the replacement lemma in fully quantified form. *)
   272     val ih_elim_case =
   272     val ih_elim_case =
   273       Conv.fconv_rule (ih_conv (K (case_hyp RS eq_reflection))) ih_elim
   273       Conv.fconv_rule (ih_conv (K (case_hyp RS eq_reflection))) ih_elim
   274 
   274 
   275     val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs
   275     val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs
   276     val h_assums = map (fn RCInfo {h_assum, ...} =>
   276     val h_assums = map (fn RCInfo {h_assum, ...} =>
   277       assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs
   277       Thm.assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs
   278 
   278 
   279     val (eql, _) =
   279     val (eql, _) =
   280       Function_Ctx_Tree.rewrite_by_tree thy h ih_elim_case (Ris ~~ h_assums) tree
   280       Function_Ctx_Tree.rewrite_by_tree thy h ih_elim_case (Ris ~~ h_assums) tree
   281 
   281 
   282     val replace_lemma = (eql RS meta_eq_to_obj_eq)
   282     val replace_lemma = (eql RS meta_eq_to_obj_eq)
   283       |> implies_intr (cprop_of case_hyp)
   283       |> Thm.implies_intr (cprop_of case_hyp)
   284       |> fold_rev (implies_intr o cprop_of) h_assums
   284       |> fold_rev (Thm.implies_intr o cprop_of) h_assums
   285       |> fold_rev (implies_intr o cprop_of) ags
   285       |> fold_rev (Thm.implies_intr o cprop_of) ags
   286       |> fold_rev forall_intr cqs
   286       |> fold_rev Thm.forall_intr cqs
   287       |> Thm.close_derivation
   287       |> Thm.close_derivation
   288   in
   288   in
   289     replace_lemma
   289     replace_lemma
   290   end
   290   end
   291 
   291 
   299     val cctxj as ClauseContext {ags = agsj', lhs = lhsj', rhs = rhsj', qs = qsj', cqs = cqsj', ...} =
   299     val cctxj as ClauseContext {ags = agsj', lhs = lhsj', rhs = rhsj', qs = qsj', cqs = cqsj', ...} =
   300       mk_clause_context x ctxti cdescj
   300       mk_clause_context x ctxti cdescj
   301 
   301 
   302     val rhsj'h = Pattern.rewrite_term thy [(fvar,h)] [] rhsj'
   302     val rhsj'h = Pattern.rewrite_term thy [(fvar,h)] [] rhsj'
   303     val compat = get_compat_thm thy compat_store i j cctxi cctxj
   303     val compat = get_compat_thm thy compat_store i j cctxi cctxj
   304     val Ghsj' = map (fn RCInfo {h_assum, ...} => assume (cterm_of thy (subst_bounds (rev qsj', h_assum)))) RCsj
   304     val Ghsj' = map (fn RCInfo {h_assum, ...} => Thm.assume (cterm_of thy (subst_bounds (rev qsj', h_assum)))) RCsj
   305 
   305 
   306     val RLj_import = RLj
   306     val RLj_import = RLj
   307       |> fold forall_elim cqsj'
   307       |> fold Thm.forall_elim cqsj'
   308       |> fold Thm.elim_implies agsj'
   308       |> fold Thm.elim_implies agsj'
   309       |> fold Thm.elim_implies Ghsj'
   309       |> fold Thm.elim_implies Ghsj'
   310 
   310 
   311     val y_eq_rhsj'h = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (y, rhsj'h))))
   311     val y_eq_rhsj'h = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (y, rhsj'h))))
   312     val lhsi_eq_lhsj' = assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (lhsi, lhsj'))))
   312     val lhsi_eq_lhsj' = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (mk_eq (lhsi, lhsj'))))
   313        (* lhs_i = lhs_j' |-- lhs_i = lhs_j' *)
   313        (* lhs_i = lhs_j' |-- lhs_i = lhs_j' *)
   314   in
   314   in
   315     (trans OF [case_hyp, lhsi_eq_lhsj']) (* lhs_i = lhs_j' |-- x = lhs_j' *)
   315     (trans OF [case_hyp, lhsi_eq_lhsj']) (* lhs_i = lhs_j' |-- x = lhs_j' *)
   316     |> implies_elim RLj_import
   316     |> Thm.implies_elim RLj_import
   317       (* Rj1' ... Rjk', lhs_i = lhs_j' |-- rhs_j'_h = rhs_j'_f *)
   317       (* Rj1' ... Rjk', lhs_i = lhs_j' |-- rhs_j'_h = rhs_j'_f *)
   318     |> (fn it => trans OF [it, compat])
   318     |> (fn it => trans OF [it, compat])
   319       (* lhs_i = lhs_j', Gj', Rj1' ... Rjk' |-- rhs_j'_h = rhs_i_f *)
   319       (* lhs_i = lhs_j', Gj', Rj1' ... Rjk' |-- rhs_j'_h = rhs_i_f *)
   320     |> (fn it => trans OF [y_eq_rhsj'h, it])
   320     |> (fn it => trans OF [y_eq_rhsj'h, it])
   321       (* lhs_i = lhs_j', Gj', Rj1' ... Rjk', y = rhs_j_h' |-- y = rhs_i_f *)
   321       (* lhs_i = lhs_j', Gj', Rj1' ... Rjk', y = rhs_j_h' |-- y = rhs_i_f *)
   322     |> fold_rev (implies_intr o cprop_of) Ghsj'
   322     |> fold_rev (Thm.implies_intr o cprop_of) Ghsj'
   323     |> fold_rev (implies_intr o cprop_of) agsj'
   323     |> fold_rev (Thm.implies_intr o cprop_of) agsj'
   324       (* lhs_i = lhs_j' , y = rhs_j_h' |-- Gj', Rj1'...Rjk' ==> y = rhs_i_f *)
   324       (* lhs_i = lhs_j' , y = rhs_j_h' |-- Gj', Rj1'...Rjk' ==> y = rhs_i_f *)
   325     |> implies_intr (cprop_of y_eq_rhsj'h)
   325     |> Thm.implies_intr (cprop_of y_eq_rhsj'h)
   326     |> implies_intr (cprop_of lhsi_eq_lhsj')
   326     |> Thm.implies_intr (cprop_of lhsi_eq_lhsj')
   327     |> fold_rev forall_intr (cterm_of thy h :: cqsj')
   327     |> fold_rev Thm.forall_intr (cterm_of thy h :: cqsj')
   328   end
   328   end
   329 
   329 
   330 
   330 
   331 
   331 
   332 fun mk_uniqueness_case thy globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei =
   332 fun mk_uniqueness_case thy globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei =
   336     val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs
   336     val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs
   337 
   337 
   338     val ih_intro_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ih_intro
   338     val ih_intro_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ih_intro
   339 
   339 
   340     fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case)
   340     fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case)
   341       |> fold_rev (implies_intr o cprop_of) CCas
   341       |> fold_rev (Thm.implies_intr o cprop_of) CCas
   342       |> fold_rev (forall_intr o cterm_of thy o Free) RIvs
   342       |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs
   343 
   343 
   344     val existence = fold (curry op COMP o prep_RC) RCs lGI
   344     val existence = fold (curry op COMP o prep_RC) RCs lGI
   345 
   345 
   346     val P = cterm_of thy (mk_eq (y, rhsC))
   346     val P = cterm_of thy (mk_eq (y, rhsC))
   347     val G_lhs_y = assume (cterm_of thy (HOLogic.mk_Trueprop (G $ lhs $ y)))
   347     val G_lhs_y = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (G $ lhs $ y)))
   348 
   348 
   349     val unique_clauses =
   349     val unique_clauses =
   350       map2 (mk_uniqueness_clause thy globals compat_store clausei) clauses rep_lemmas
   350       map2 (mk_uniqueness_clause thy globals compat_store clausei) clauses rep_lemmas
   351 
   351 
   352     fun elim_implies_eta A AB =
   352     fun elim_implies_eta A AB =
   353       Thm.compose_no_flatten true (A, 0) 1 AB |> Seq.list_of |> the_single
   353       Thm.compose_no_flatten true (A, 0) 1 AB |> Seq.list_of |> the_single
   354 
   354 
   355     val uniqueness = G_cases
   355     val uniqueness = G_cases
   356       |> forall_elim (cterm_of thy lhs)
   356       |> Thm.forall_elim (cterm_of thy lhs)
   357       |> forall_elim (cterm_of thy y)
   357       |> Thm.forall_elim (cterm_of thy y)
   358       |> forall_elim P
   358       |> Thm.forall_elim P
   359       |> Thm.elim_implies G_lhs_y
   359       |> Thm.elim_implies G_lhs_y
   360       |> fold elim_implies_eta unique_clauses
   360       |> fold elim_implies_eta unique_clauses
   361       |> implies_intr (cprop_of G_lhs_y)
   361       |> Thm.implies_intr (cprop_of G_lhs_y)
   362       |> forall_intr (cterm_of thy y)
   362       |> Thm.forall_intr (cterm_of thy y)
   363 
   363 
   364     val P2 = cterm_of thy (lambda y (G $ lhs $ y)) (* P2 y := (lhs, y): G *)
   364     val P2 = cterm_of thy (lambda y (G $ lhs $ y)) (* P2 y := (lhs, y): G *)
   365 
   365 
   366     val exactly_one =
   366     val exactly_one =
   367       ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)]
   367       ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)]
   368       |> curry (op COMP) existence
   368       |> curry (op COMP) existence
   369       |> curry (op COMP) uniqueness
   369       |> curry (op COMP) uniqueness
   370       |> simplify (HOL_basic_ss addsimps [case_hyp RS sym])
   370       |> simplify (HOL_basic_ss addsimps [case_hyp RS sym])
   371       |> implies_intr (cprop_of case_hyp)
   371       |> Thm.implies_intr (cprop_of case_hyp)
   372       |> fold_rev (implies_intr o cprop_of) ags
   372       |> fold_rev (Thm.implies_intr o cprop_of) ags
   373       |> fold_rev forall_intr cqs
   373       |> fold_rev Thm.forall_intr cqs
   374 
   374 
   375     val function_value =
   375     val function_value =
   376       existence
   376       existence
   377       |> implies_intr ihyp
   377       |> Thm.implies_intr ihyp
   378       |> implies_intr (cprop_of case_hyp)
   378       |> Thm.implies_intr (cprop_of case_hyp)
   379       |> forall_intr (cterm_of thy x)
   379       |> Thm.forall_intr (cterm_of thy x)
   380       |> forall_elim (cterm_of thy lhs)
   380       |> Thm.forall_elim (cterm_of thy lhs)
   381       |> curry (op RS) refl
   381       |> curry (op RS) refl
   382   in
   382   in
   383     (exactly_one, function_value)
   383     (exactly_one, function_value)
   384   end
   384   end
   385 
   385 
   394       Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x),
   394       Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x),
   395         HOLogic.mk_Trueprop (Const ("Ex1", (ranT --> boolT) --> boolT) $
   395         HOLogic.mk_Trueprop (Const ("Ex1", (ranT --> boolT) --> boolT) $
   396           Abs ("y", ranT, G $ Bound 1 $ Bound 0))))
   396           Abs ("y", ranT, G $ Bound 1 $ Bound 0))))
   397       |> cterm_of thy
   397       |> cterm_of thy
   398 
   398 
   399     val ihyp_thm = assume ihyp |> Thm.forall_elim_vars 0
   399     val ihyp_thm = Thm.assume ihyp |> Thm.forall_elim_vars 0
   400     val ih_intro = ihyp_thm RS (f_def RS ex1_implies_ex)
   400     val ih_intro = ihyp_thm RS (f_def RS ex1_implies_ex)
   401     val ih_elim = ihyp_thm RS (f_def RS ex1_implies_un)
   401     val ih_elim = ihyp_thm RS (f_def RS ex1_implies_un)
   402       |> instantiate' [] [NONE, SOME (cterm_of thy h)]
   402       |> instantiate' [] [NONE, SOME (cterm_of thy h)]
   403 
   403 
   404     val _ = trace_msg (K "Proving Replacement lemmas...")
   404     val _ = trace_msg (K "Proving Replacement lemmas...")
   410 
   410 
   411     val _ = trace_msg (K "Proving: Graph is a function")
   411     val _ = trace_msg (K "Proving: Graph is a function")
   412     val graph_is_function = complete
   412     val graph_is_function = complete
   413       |> Thm.forall_elim_vars 0
   413       |> Thm.forall_elim_vars 0
   414       |> fold (curry op COMP) ex1s
   414       |> fold (curry op COMP) ex1s
   415       |> implies_intr (ihyp)
   415       |> Thm.implies_intr (ihyp)
   416       |> implies_intr (cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ x)))
   416       |> Thm.implies_intr (cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ x)))
   417       |> forall_intr (cterm_of thy x)
   417       |> Thm.forall_intr (cterm_of thy x)
   418       |> (fn it => Drule.compose_single (it, 2, acc_induct_rule)) (* "EX! y. (?x,y):G" *)
   418       |> (fn it => Drule.compose_single (it, 2, acc_induct_rule)) (* "EX! y. (?x,y):G" *)
   419       |> (fn it => fold (forall_intr o cterm_of thy o Var) (Term.add_vars (prop_of it) []) it)
   419       |> (fn it => fold (Thm.forall_intr o cterm_of thy o Var) (Term.add_vars (prop_of it) []) it)
   420 
   420 
   421     val goalstate =  Conjunction.intr graph_is_function complete
   421     val goalstate =  Conjunction.intr graph_is_function complete
   422       |> Thm.close_derivation
   422       |> Thm.close_derivation
   423       |> Goal.protect
   423       |> Goal.protect
   424       |> fold_rev (implies_intr o cprop_of) compat
   424       |> fold_rev (Thm.implies_intr o cprop_of) compat
   425       |> implies_intr (cprop_of complete)
   425       |> Thm.implies_intr (cprop_of complete)
   426   in
   426   in
   427     (goalstate, values)
   427     (goalstate, values)
   428   end
   428   end
   429 
   429 
   430 (* wrapper -- restores quantifiers in rule specifications *)
   430 (* wrapper -- restores quantifiers in rule specifications *)
   542 
   542 
   543 fun inst_RC thy fvar f (rcfix, rcassm, rcarg) =
   543 fun inst_RC thy fvar f (rcfix, rcassm, rcarg) =
   544   let
   544   let
   545     fun inst_term t = subst_bound(f, abstract_over (fvar, t))
   545     fun inst_term t = subst_bound(f, abstract_over (fvar, t))
   546   in
   546   in
   547     (rcfix, map (assume o cterm_of thy o inst_term o prop_of) rcassm, inst_term rcarg)
   547     (rcfix, map (Thm.assume o cterm_of thy o inst_term o prop_of) rcassm, inst_term rcarg)
   548   end
   548   end
   549 
   549 
   550 
   550 
   551 
   551 
   552 (**********************************************************
   552 (**********************************************************
   560     fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm =
   560     fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm =
   561       let
   561       let
   562         val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *)
   562         val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *)
   563         val z_smaller = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ lhs)) (* "R z lhs" *)
   563         val z_smaller = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ lhs)) (* "R z lhs" *)
   564       in
   564       in
   565         ((assume z_smaller) RS ((assume lhs_acc) RS acc_downward))
   565         ((Thm.assume z_smaller) RS ((Thm.assume lhs_acc) RS acc_downward))
   566         |> (fn it => it COMP graph_is_function)
   566         |> (fn it => it COMP graph_is_function)
   567         |> implies_intr z_smaller
   567         |> Thm.implies_intr z_smaller
   568         |> forall_intr (cterm_of thy z)
   568         |> Thm.forall_intr (cterm_of thy z)
   569         |> (fn it => it COMP valthm)
   569         |> (fn it => it COMP valthm)
   570         |> implies_intr lhs_acc
   570         |> Thm.implies_intr lhs_acc
   571         |> asm_simplify (HOL_basic_ss addsimps [f_iff])
   571         |> asm_simplify (HOL_basic_ss addsimps [f_iff])
   572         |> fold_rev (implies_intr o cprop_of) ags
   572         |> fold_rev (Thm.implies_intr o cprop_of) ags
   573         |> fold_rev forall_intr_rename (map fst oqs ~~ cqs)
   573         |> fold_rev forall_intr_rename (map fst oqs ~~ cqs)
   574       end
   574       end
   575   in
   575   in
   576     map2 mk_psimp clauses valthms
   576     map2 mk_psimp clauses valthms
   577   end
   577   end
   586 fun mk_partial_induct_rule thy globals R complete_thm clauses =
   586 fun mk_partial_induct_rule thy globals R complete_thm clauses =
   587   let
   587   let
   588     val Globals {domT, x, z, a, P, D, ...} = globals
   588     val Globals {domT, x, z, a, P, D, ...} = globals
   589     val acc_R = mk_acc domT R
   589     val acc_R = mk_acc domT R
   590 
   590 
   591     val x_D = assume (cterm_of thy (HOLogic.mk_Trueprop (D $ x)))
   591     val x_D = Thm.assume (cterm_of thy (HOLogic.mk_Trueprop (D $ x)))
   592     val a_D = cterm_of thy (HOLogic.mk_Trueprop (D $ a))
   592     val a_D = cterm_of thy (HOLogic.mk_Trueprop (D $ a))
   593 
   593 
   594     val D_subset = cterm_of thy (Logic.all x
   594     val D_subset = cterm_of thy (Logic.all x
   595       (Logic.mk_implies (HOLogic.mk_Trueprop (D $ x), HOLogic.mk_Trueprop (acc_R $ x))))
   595       (Logic.mk_implies (HOLogic.mk_Trueprop (D $ x), HOLogic.mk_Trueprop (acc_R $ x))))
   596 
   596 
   604     val ihyp = Term.all domT $ Abs ("z", domT,
   604     val ihyp = Term.all domT $ Abs ("z", domT,
   605       Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x),
   605       Logic.mk_implies (HOLogic.mk_Trueprop (R $ Bound 0 $ x),
   606         HOLogic.mk_Trueprop (P $ Bound 0)))
   606         HOLogic.mk_Trueprop (P $ Bound 0)))
   607       |> cterm_of thy
   607       |> cterm_of thy
   608 
   608 
   609     val aihyp = assume ihyp
   609     val aihyp = Thm.assume ihyp
   610 
   610 
   611     fun prove_case clause =
   611     fun prove_case clause =
   612       let
   612       let
   613         val ClauseInfo {cdata = ClauseContext {ctxt, qs, cqs, ags, gs, lhs, case_hyp, ...},
   613         val ClauseInfo {cdata = ClauseContext {ctxt, qs, cqs, ags, gs, lhs, case_hyp, ...},
   614           RCs, qglr = (oqs, _, _, _), ...} = clause
   614           RCs, qglr = (oqs, _, _, _), ...} = clause
   620             fconv_rule (Conv.binder_conv
   620             fconv_rule (Conv.binder_conv
   621               (K (arg1_conv (arg_conv (arg_conv case_hyp_conv)))) ctxt) aihyp
   621               (K (arg1_conv (arg_conv (arg_conv case_hyp_conv)))) ctxt) aihyp
   622         end
   622         end
   623 
   623 
   624         fun mk_Prec (RCInfo {llRI, RIvs, CCas, rcarg, ...}) = sih
   624         fun mk_Prec (RCInfo {llRI, RIvs, CCas, rcarg, ...}) = sih
   625           |> forall_elim (cterm_of thy rcarg)
   625           |> Thm.forall_elim (cterm_of thy rcarg)
   626           |> Thm.elim_implies llRI
   626           |> Thm.elim_implies llRI
   627           |> fold_rev (implies_intr o cprop_of) CCas
   627           |> fold_rev (Thm.implies_intr o cprop_of) CCas
   628           |> fold_rev (forall_intr o cterm_of thy o Free) RIvs
   628           |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs
   629 
   629 
   630         val P_recs = map mk_Prec RCs   (*  [P rec1, P rec2, ... ]  *)
   630         val P_recs = map mk_Prec RCs   (*  [P rec1, P rec2, ... ]  *)
   631 
   631 
   632         val step = HOLogic.mk_Trueprop (P $ lhs)
   632         val step = HOLogic.mk_Trueprop (P $ lhs)
   633           |> fold_rev (curry Logic.mk_implies o prop_of) P_recs
   633           |> fold_rev (curry Logic.mk_implies o prop_of) P_recs
   634           |> fold_rev (curry Logic.mk_implies) gs
   634           |> fold_rev (curry Logic.mk_implies) gs
   635           |> curry Logic.mk_implies (HOLogic.mk_Trueprop (D $ lhs))
   635           |> curry Logic.mk_implies (HOLogic.mk_Trueprop (D $ lhs))
   636           |> fold_rev mk_forall_rename (map fst oqs ~~ qs)
   636           |> fold_rev mk_forall_rename (map fst oqs ~~ qs)
   637           |> cterm_of thy
   637           |> cterm_of thy
   638 
   638 
   639         val P_lhs = assume step
   639         val P_lhs = Thm.assume step
   640           |> fold forall_elim cqs
   640           |> fold Thm.forall_elim cqs
   641           |> Thm.elim_implies lhs_D
   641           |> Thm.elim_implies lhs_D
   642           |> fold Thm.elim_implies ags
   642           |> fold Thm.elim_implies ags
   643           |> fold Thm.elim_implies P_recs
   643           |> fold Thm.elim_implies P_recs
   644 
   644 
   645         val res = cterm_of thy (HOLogic.mk_Trueprop (P $ x))
   645         val res = cterm_of thy (HOLogic.mk_Trueprop (P $ x))
   646           |> Conv.arg_conv (Conv.arg_conv case_hyp_conv)
   646           |> Conv.arg_conv (Conv.arg_conv case_hyp_conv)
   647           |> symmetric (* P lhs == P x *)
   647           |> Thm.symmetric (* P lhs == P x *)
   648           |> (fn eql => equal_elim eql P_lhs) (* "P x" *)
   648           |> (fn eql => Thm.equal_elim eql P_lhs) (* "P x" *)
   649           |> implies_intr (cprop_of case_hyp)
   649           |> Thm.implies_intr (cprop_of case_hyp)
   650           |> fold_rev (implies_intr o cprop_of) ags
   650           |> fold_rev (Thm.implies_intr o cprop_of) ags
   651           |> fold_rev forall_intr cqs
   651           |> fold_rev Thm.forall_intr cqs
   652       in
   652       in
   653         (res, step)
   653         (res, step)
   654       end
   654       end
   655 
   655 
   656     val (cases, steps) = split_list (map prove_case clauses)
   656     val (cases, steps) = split_list (map prove_case clauses)
   657 
   657 
   658     val istep = complete_thm
   658     val istep = complete_thm
   659       |> Thm.forall_elim_vars 0
   659       |> Thm.forall_elim_vars 0
   660       |> fold (curry op COMP) cases (*  P x  *)
   660       |> fold (curry op COMP) cases (*  P x  *)
   661       |> implies_intr ihyp
   661       |> Thm.implies_intr ihyp
   662       |> implies_intr (cprop_of x_D)
   662       |> Thm.implies_intr (cprop_of x_D)
   663       |> forall_intr (cterm_of thy x)
   663       |> Thm.forall_intr (cterm_of thy x)
   664 
   664 
   665     val subset_induct_rule =
   665     val subset_induct_rule =
   666       acc_subset_induct
   666       acc_subset_induct
   667       |> (curry op COMP) (assume D_subset)
   667       |> (curry op COMP) (Thm.assume D_subset)
   668       |> (curry op COMP) (assume D_dcl)
   668       |> (curry op COMP) (Thm.assume D_dcl)
   669       |> (curry op COMP) (assume a_D)
   669       |> (curry op COMP) (Thm.assume a_D)
   670       |> (curry op COMP) istep
   670       |> (curry op COMP) istep
   671       |> fold_rev implies_intr steps
   671       |> fold_rev Thm.implies_intr steps
   672       |> implies_intr a_D
   672       |> Thm.implies_intr a_D
   673       |> implies_intr D_dcl
   673       |> Thm.implies_intr D_dcl
   674       |> implies_intr D_subset
   674       |> Thm.implies_intr D_subset
   675 
   675 
   676     val simple_induct_rule =
   676     val simple_induct_rule =
   677       subset_induct_rule
   677       subset_induct_rule
   678       |> forall_intr (cterm_of thy D)
   678       |> Thm.forall_intr (cterm_of thy D)
   679       |> forall_elim (cterm_of thy acc_R)
   679       |> Thm.forall_elim (cterm_of thy acc_R)
   680       |> assume_tac 1 |> Seq.hd
   680       |> assume_tac 1 |> Seq.hd
   681       |> (curry op COMP) (acc_downward
   681       |> (curry op COMP) (acc_downward
   682         |> (instantiate' [SOME (ctyp_of thy domT)]
   682         |> (instantiate' [SOME (ctyp_of thy domT)]
   683              (map (SOME o cterm_of thy) [R, x, z]))
   683              (map (SOME o cterm_of thy) [R, x, z]))
   684         |> forall_intr (cterm_of thy z)
   684         |> Thm.forall_intr (cterm_of thy z)
   685         |> forall_intr (cterm_of thy x))
   685         |> Thm.forall_intr (cterm_of thy x))
   686       |> forall_intr (cterm_of thy a)
   686       |> Thm.forall_intr (cterm_of thy a)
   687       |> forall_intr (cterm_of thy P)
   687       |> Thm.forall_intr (cterm_of thy P)
   688   in
   688   in
   689     simple_induct_rule
   689     simple_induct_rule
   690   end
   690   end
   691 
   691 
   692 
   692 
   734           |> Function_Ctx_Tree.export_term (fixes, assumes)
   734           |> Function_Ctx_Tree.export_term (fixes, assumes)
   735           |> fold_rev (curry Logic.mk_implies o prop_of) ags
   735           |> fold_rev (curry Logic.mk_implies o prop_of) ags
   736           |> fold_rev mk_forall_rename (map fst oqs ~~ qs)
   736           |> fold_rev mk_forall_rename (map fst oqs ~~ qs)
   737           |> cterm_of thy
   737           |> cterm_of thy
   738 
   738 
   739         val thm = assume hyp
   739         val thm = Thm.assume hyp
   740           |> fold forall_elim cqs
   740           |> fold Thm.forall_elim cqs
   741           |> fold Thm.elim_implies ags
   741           |> fold Thm.elim_implies ags
   742           |> Function_Ctx_Tree.import_thm thy (fixes, assumes)
   742           |> Function_Ctx_Tree.import_thm thy (fixes, assumes)
   743           |> fold Thm.elim_implies used (*  "(arg, lhs) : R'"  *)
   743           |> fold Thm.elim_implies used (*  "(arg, lhs) : R'"  *)
   744 
   744 
   745         val z_eq_arg = HOLogic.mk_Trueprop (mk_eq (z, arg))
   745         val z_eq_arg = HOLogic.mk_Trueprop (mk_eq (z, arg))
   746           |> cterm_of thy |> assume
   746           |> cterm_of thy |> Thm.assume
   747 
   747 
   748         val acc = thm COMP ih_case
   748         val acc = thm COMP ih_case
   749         val z_acc_local = acc
   749         val z_acc_local = acc
   750           |> Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv (K (symmetric (z_eq_arg RS eq_reflection)))))
   750           |> Conv.fconv_rule
       
   751               (Conv.arg_conv (Conv.arg_conv (K (Thm.symmetric (z_eq_arg RS eq_reflection)))))
   751 
   752 
   752         val ethm = z_acc_local
   753         val ethm = z_acc_local
   753           |> Function_Ctx_Tree.export_thm thy (fixes,
   754           |> Function_Ctx_Tree.export_thm thy (fixes,
   754                z_eq_arg :: case_hyp :: ags @ assumes)
   755                z_eq_arg :: case_hyp :: ags @ assumes)
   755           |> fold_rev forall_intr_rename (map fst oqs ~~ cqs)
   756           |> fold_rev forall_intr_rename (map fst oqs ~~ cqs)
   783     val ihyp = Term.all domT $ Abs ("z", domT,
   784     val ihyp = Term.all domT $ Abs ("z", domT,
   784       Logic.mk_implies (HOLogic.mk_Trueprop (R' $ Bound 0 $ x),
   785       Logic.mk_implies (HOLogic.mk_Trueprop (R' $ Bound 0 $ x),
   785         HOLogic.mk_Trueprop (acc_R $ Bound 0)))
   786         HOLogic.mk_Trueprop (acc_R $ Bound 0)))
   786       |> cterm_of thy
   787       |> cterm_of thy
   787 
   788 
   788     val ihyp_a = assume ihyp |> Thm.forall_elim_vars 0
   789     val ihyp_a = Thm.assume ihyp |> Thm.forall_elim_vars 0
   789 
   790 
   790     val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x))
   791     val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x))
   791 
   792 
   792     val (hyps, cases) = fold (mk_nest_term_case thy globals R' ihyp_a) clauses ([], [])
   793     val (hyps, cases) = fold (mk_nest_term_case thy globals R' ihyp_a) clauses ([], [])
   793   in
   794   in
   794     R_cases
   795     R_cases
   795     |> forall_elim (cterm_of thy z)
   796     |> Thm.forall_elim (cterm_of thy z)
   796     |> forall_elim (cterm_of thy x)
   797     |> Thm.forall_elim (cterm_of thy x)
   797     |> forall_elim (cterm_of thy (acc_R $ z))
   798     |> Thm.forall_elim (cterm_of thy (acc_R $ z))
   798     |> curry op COMP (assume R_z_x)
   799     |> curry op COMP (Thm.assume R_z_x)
   799     |> fold_rev (curry op COMP) cases
   800     |> fold_rev (curry op COMP) cases
   800     |> implies_intr R_z_x
   801     |> Thm.implies_intr R_z_x
   801     |> forall_intr (cterm_of thy z)
   802     |> Thm.forall_intr (cterm_of thy z)
   802     |> (fn it => it COMP accI)
   803     |> (fn it => it COMP accI)
   803     |> implies_intr ihyp
   804     |> Thm.implies_intr ihyp
   804     |> forall_intr (cterm_of thy x)
   805     |> Thm.forall_intr (cterm_of thy x)
   805     |> (fn it => Drule.compose_single(it,2,wf_induct_rule))
   806     |> (fn it => Drule.compose_single(it,2,wf_induct_rule))
   806     |> curry op RS (assume wfR')
   807     |> curry op RS (Thm.assume wfR')
   807     |> forall_intr_vars
   808     |> forall_intr_vars
   808     |> (fn it => it COMP allI)
   809     |> (fn it => it COMP allI)
   809     |> fold implies_intr hyps
   810     |> fold Thm.implies_intr hyps
   810     |> implies_intr wfR'
   811     |> Thm.implies_intr wfR'
   811     |> forall_intr (cterm_of thy R')
   812     |> Thm.forall_intr (cterm_of thy R')
   812     |> forall_elim (cterm_of thy (inrel_R))
   813     |> Thm.forall_elim (cterm_of thy (inrel_R))
   813     |> curry op RS wf_in_rel
   814     |> curry op RS wf_in_rel
   814     |> full_simplify (HOL_basic_ss addsimps [in_rel_def])
   815     |> full_simplify (HOL_basic_ss addsimps [in_rel_def])
   815     |> forall_intr (cterm_of thy Rrel)
   816     |> Thm.forall_intr (cterm_of thy Rrel)
   816   end
   817   end
   817 
   818 
   818 
   819 
   819 
   820 
   820 (* Tail recursion (probably very fragile)
   821 (* Tail recursion (probably very fragile)
   917     val xclauses = PROFILE "xclauses"
   918     val xclauses = PROFILE "xclauses"
   918       (map7 (mk_clause_info globals G f) (1 upto n) clauses abstract_qglrs trees
   919       (map7 (mk_clause_info globals G f) (1 upto n) clauses abstract_qglrs trees
   919         RCss GIntro_thms) RIntro_thmss
   920         RCss GIntro_thms) RIntro_thmss
   920 
   921 
   921     val complete =
   922     val complete =
   922       mk_completeness globals clauses abstract_qglrs |> cert |> assume
   923       mk_completeness globals clauses abstract_qglrs |> cert |> Thm.assume
   923 
   924 
   924     val compat =
   925     val compat =
   925       mk_compat_proof_obligations domT ranT fvar f abstract_qglrs
   926       mk_compat_proof_obligations domT ranT fvar f abstract_qglrs
   926       |> map (cert #> assume)
   927       |> map (cert #> Thm.assume)
   927 
   928 
   928     val compat_store = store_compat_thms n compat
   929     val compat_store = store_compat_thms n compat
   929 
   930 
   930     val (goalstate, values) = PROFILE "prove_stuff"
   931     val (goalstate, values) = PROFILE "prove_stuff"
   931       (prove_stuff lthy globals G f R xclauses complete compat
   932       (prove_stuff lthy globals G f R xclauses complete compat